2018数据结构总复习
第一章概论
11数据结构的定义和分类
1数据结构的定义
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
2数据结构包括的内容
（1）逻辑结构：数据元素之间的逻辑关系。（2）存储结构：数据元素及其关系在计算机存储器内的表示。（3）操作：数据的运算（检索、排序、插入、删除、修改）。
12为什么学习数据结构
1学习数据结构的作用
（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。（2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。
2电话号码查询问题
（1）要写出好的查找算法，取决于这张表的结构及存储方式。（2）电话号码表的结构和存储方式决定了查找（算法）的效率。
13算法的概念和特点
1算法的概念和特点
算法是由若干条指令组成的有穷序列，具有以下特点：（1）输入：具有0个或多个输入的外界量。（2）输出：至少产生1个输出。（3）有穷性：每一条指令的执行次数必须是有限的。（4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条指令的执行时间都是有限的。
2算法与程序的区别
（1）一个程序不一定满足有穷性，但算法一定。（2）程序中的指令必须是机器可执行的，而算法无此限制。（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。
162
f14算法分析
1时间复杂度
算法中基本操作重复执行的次数是问题规模
的某个函数，用T
表示，若有某个辅助函数f
，使得当
趋近于无穷大时，T
f
的极限值为不等于零的常数，则称f
是T
的同数量级函数。记作T
Of
，称Of
为算法的渐近时间复杂度，简称时间复杂度。算法效率的度量，采用时间复杂度。
常见函数的时间复杂度按数量递增排列及增长率：常数阶O1对数阶Olog2
线性阶O
线性对数阶O
log2
平方阶O
2立方阶O
3
……k次方阶O
k指数阶O2
2空间复杂度
空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S
Of
。
3算法分析的目的
目的在于选择合适算法和改进算法
15例题
例1：
fori1i
i
yy1
语句1
forj0j2
j
x
语句2

解：语句1频度为
1；语句2频度为
12
12
2
1，因此时间复杂度T
2
22O
2。
例2：
i1
语r