2018数据结构总复习
第一章 概论
1.1数据结构的定义和分类
1.数据结构的定义
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
2.数据结构包括的内容
（1）逻辑结构：数据元素之间的逻辑关系。
（2）存储结构：数据元素及其关系在计算机存储器内的表示。 （3）操作：数据的运算（检索、排序、插入、删除、修改）。
1.2为什么学习数据结构
1.学习数据结构的作用
（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 （2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。
（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。
2.电话号码查询问题
（1）要写出好的查找算法，取决于这张表的结构及存储方式。 （2）电话号码表的结构和存储方式决定了查找（算法）的效率。
1.3算法的概念和特点
1.算法的概念和特点
算法是由若干条指令组成的有穷序列，具有以下特点： （1）输入：具有0个或多个输入的外界量。 （2）输出：至少产生1个输出。
（3）有穷性：每一条指令的执行次数必须是有限的。 （4）确定性：每条指令的含义都必须明确，无二义性。 （5）可行性：每条指令的执行时间都是有限的。
2.算法与程序的区别
（1）一个程序不一定满足有穷性，但算法一定。
（2）程序中的指令必须是机器可执行的，而算法无此限制。
（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。
1 / 62
1.4算法分析
1.时间复杂度
算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。算法效率的度量，采用时间复杂度。
常见函数的时间复杂度按数量递增排列及增长率： 常数阶O(1)
对数阶O(log2n) 线性阶O(n)
线性对数阶O(n log2n)
2
平方阶O(n)
3
立方阶O(n) ……
k
k次方阶O(n)
n
指数阶O(2)
2.空间复杂度
空间复杂度是指算法在计算机内执行时所需存储空间的度量，记作：S(n) = O(f(n))。
3.算法分析的目的
目的在于选择合适算法和改进算法
1.5 例题
例1：
for ( i=1; i y = y+1; //语句1 for ( j=0; j<=(2*n); j++ ) x++; //语句2 } 解：语句1频度为(n-1)；语句2频度为(n-1)*(2n+1)=2n2-n-1，因此时间复杂度T(n)=2n2-2=O(n2)。 例2： i=1; //语句1 while (i<=n) i=i*2; //语句2 解：语句1频度为1；设语句2频度为f(n)，则有2f(n)<=n，即f(n)<=log2n，去极大值，f(n)=log2n，因此时间复杂度T(n)=1+log2n=O(log2n)。 2 / 62 第二章 线性表 2.1 线性表的概念和运算 1.线性表的概念 线性表是 n (n≥0) 个类型相同的数据元素组成的有限序列。其中数据元素的个数n为线性表的长度，当n=0时称为空表。 2.线性表的特点 对于非空的线性表，有且仅有一个开始结点和一个终端结点；开始结点没有直接前趋，有且仅有一个直接后继；终端结点没有直接后继，有且仅有一个直接前趋；其余任何结点有且仅有一个直接前趋和一个直接后继。 3.线性表的计算 (1) 置空表 SETNULL(L) ：将线性表L置为空表。 (2) 求长度 LENGTH(L) ：返回是线性表L中结点的个数。 (3) 取结点 GET(L, i ) ：当1 ≤ i ≤ LENGTH(L)时，返回线性表L中的第 i 个结点，否则返回NULL。 (4) 定位 LOCATE(L, x) ：当线性表L中存在一个值为x的结点时，结果是该结点的位置；若表L中存在多个值为x的结点，则返回首次找到的结点位置；若表L中不存在值为x的结点，则返回一个特殊值表示值为x的结点不存在。 (5) 插入 INSERT(L, x, i) ：在线性表L的第i个位置插入一个值为x的新结点。这里1 ≤ i ≤ n+1，n是原表L的长度。 (6) 删除 DELETE(L, i) ：删除线性表L的第i个结点。这里1 ≤ i ≤ n，n是原表L的长度。 2.2 线性表的存储结构 1.顺序存储： （1）定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻。 （2）顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。 （3）地址计算：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则地址计算公式：LOC(ai) = LOC(a1) + ( i-1)*L。 （4）结构定义： #define MAXSIZE 1024 //线性表的最大长度 typedef int datatype; //线性表数据元素类型 typedef struct { datatype data[MAXSIZE]; int last; //指示线性表的终端结点在表中的下标值 }sequenlist; 2.链式存储： 3 / 62