文档介绍：公共基础知识
第1章数据结构与算法
2017/11/27
第1页
数据结构与算法
本章内容
算法
数据结构基本概念
线性链表
树与二叉树
查找技术
线性表及其顺序存储结构
栈和队列
排序技术
*
2
第1章数据结构与算法
1. 1 算法
算法的基本概念
1. 算法的基本特征
算法是指解决问题方案的准确而完整的描述。即用来完成某个特定任务的正确的、有限步骤序列。
*
3
第1章数据结构与算法
例题:
算法的有穷性是指
算法程序的运行时间是有限的
算法程序所处理的数据量是有限的
算法程序的长度是有限的
算法只能被有限的用户使用
下列叙述正确的是
算法的执行效率与数据的存储结构有关
算法的空间复杂度是指算法程序中指令(或语句)的条数
算法的有穷性是指算法必须能在执行有限个步骤之后终止
以上三种说法都不对
*
4
第1章数据结构与算法
一个算法由两个基本要素组成:
1) 对数据对象的运算和操作
包括以下四类:
算术运算
逻辑运算
关系运算
数据传输
2) 算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具包括自然语言描述、程序设计语言描述、流程图描述等。
一个算法一般可以用顺序、选择、循环三种基本结构组合而成。
2. 算法的基本要素
*
5
第1章数据结构与算法
3. 算法设计基本方法
列举法
归纳法
递推
递归
减半递推技术
回溯法
*
6
第1章数据结构与算法
算法的复杂度包括时间复杂度和空间复杂度。
1)算法的时间复杂度:是指执行算法所需要的计算工作量。
2)算法的空间复杂度:是指执行算法所需要的存储空间。
算法复杂度
*
7
第1章数据结构与算法
算法的时间复杂度
一般把程序运行时语句的执行次数作为估算程序执行时间的量度。
例:估算以下函数的时间复杂度。
Dim a(5) As Integer
Const n=5
k=0 ‘执行 1 次 for i=1 To n Step 1 ‘执行 n 次 if a(i)<a(k) Then k=i ‘执行n-1次 Print k ‘执行 1 次 }
语句执行频度:
f(n)=2n+1
当n一定大时:
算法的工作量=f(n)
算法的空间复杂度
执行一个算法所需要的内存空间的多少。包括程序本身所占空间、数据所占空间、处理数据所占的附加空间、算法执行过程中所需的额外空间。
*
8
第1章数据结构与算法
例题:
算法的空间复杂度是指
算法程序的长度
算法程序中的指令条数
算法程序所占的存储空间
执行算法需要的内存空间
下列叙述中正确的是
一个算法的空间复杂度大,则其时间复杂度也必定大
一个算法的空间复杂度大,则其时间复杂度必定小
一个算法的时间复杂度大,则其空间复杂度必定小
上述三种说法都不对
*
9
第1章数据结构与算法
数据结构的基本概念
数据结构主要研究三方面的问题:
数据的逻辑结构
数据的存储结构
对各种数据结构进行的运算
这三个方面是软件设计的基础。
*
10
第1章数据结构与算法