《数据结构C语言》复习重点

1、数 据 结 构 ( C 语 言 版 ) 复 习 重 点重点在二、三、六、七、九、十章，考试内容两大类：概念，算法第 1 章、绪论1. 数据：是对客观事物的符号表示， 在计算机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。2. 数据元素 ：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3. 数据结构 ：是相互之间存在一种或多种特定关系的数据元素的集合。其 4类基本结构 ：集合、线性结构、树形结构、图状结构或网状结构4. 逻辑结构 ：是数据元素之间的逻辑关系的描述。5. 物理结构 (存储结构 )：是数据结构在计算机中的表示(又称映像)。其 4种存储结构 ：顺序存

2、数结构、链式存数结构、索引存数结构、散列存数结构6. 算法 ：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一 个或多个操作。其 5个重要特性 ：有穷性、确定性、可行性、输入、输出7. 时间复杂度：算法中基本操作重复执行的次数是问题规模 n的某个函数f(n),算法的时间度 量记作，T(n)=0(f(n);他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长 率相同，称做算法的 渐进时间复杂度 ，简称 时间复杂度 。例如 ： (a) +x;s=0;(b) for(i=1;i=n;+i)+x;s += x;(c) for(j=1;j=n;+j)for(k=1;kn

3、ext 为第 一个结点地址， L-next=NULL 为空表。生成结点 ： p=(LinkList)malloc(sizeof(LNode)回收结点 ： free(q)2) 循环链表特点 ：表中最后一个结点的指针域指向头结点，整个链表形成一个环。 循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是P 或 P-next 是否为空，而是它们是否等于头指针。3) 双向链表特点 ：有 2 个指针域，其一指向直接后继，另一指向直接前趋。第 3 章、栈和队列1. 栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为 栈顶 ，表头端称为 栈底， 不含有元素的空表称为 空栈；栈又称为 后进先

4、出 的线性表。2. 队列：是一种 先进先出 的线性表，它只允许在表的一端进行插入，而另一端删除元素。允 许插入的一端叫做 队尾 ，允许删除的一端则称为 队头。1) 链队列 ：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针(分别成为头指 针和尾指针)才能确定唯一。和单链表一样，也给链队列添加一个头结点，并令头指针指向 头结点。2) 循环队列 ：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列头到队列尾的 元素之外， 尚需附设两个指针 front 和 rear 分别指示队列头元素及队列尾元素的位置。 初始 化建空队列时，令 front = rear = 0，每当插入新的队列尾元素

5、时，“尾指针增 1”；每当删除队列头元素时，“头指针增 1”。第 4 章、串1. 串：是由零个或多个字符组成的有限序列。第 5 章、数组和广义表1. 数组特点 ：与线性表一样，所有数据元素都必须属于同一数据类型。2. 数组的顺序存储结构 ：由于数组一般不作插入或删除操作， 一旦建立了数组， 则结构中的 数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。存储位置计算：假设每个数据元素需占用L个存储单元，则二维数组 A中任一元素aij的存 储位置可由下式确定以行序为主序的存储结构： LOC(i,j)=LOC(0,0)+(b2*i+j)*L以列序为主序的存储结构： LOC(i

6、,j)=LOC(0,0)+(b2*j+i)*L式中LOC(i,j)是aij的存储位置；LOC(0,0)是aOO的存储位置，即二维数组 A的起始存储位 置，也称基地址或基址；b2在以行序为主序的存储结构时为每行存储元素的个数 (列数)，在 以列序为主序的存储结构时为每列存储元素的个数 (行数)。3. 广义表：是线性表的推广，也有人称其为列表(lists,用复数形式以示与统称的表list的 区别)。记作LS=(a1,a2,an)，其中LS是广义表(a1,a2,a的名称，n是它的长度。在线性 表的定义中，ai(1 i 1)。2) 性质2：深度为k的二叉树至多有2的k次方减1个结点(k 1)。深度为k

7、的二叉树至少有k个结点(k 1)。深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(k 1)。3）性质3:对任何一棵二叉树T,如果其终端结点数为nO,度为2的结点数为n2,则nO=n2+1。4）性质4:具有n个结点的完全二叉树的深度为Iog2n+1 。5）性质5:如果对一棵有n个结点的完全二叉树（其深度为Iog2n+1 ）的结点按层序编号 （从第1层到第Iog2n+1层，每层从左到右），则对任一结点i （K i 1，则其双亲PARENT（i）是结点i/2。b）如果2in，贝U结点i无左孩子（结点i为叶子结点）；否则其左孩子 LCHILD（i）是结点 2i。c）如果2i+1n，贝U结点

8、i无右孩子；否则其右孩子 RCHILD（i）是结点2i+1。3. 满二叉树：一颗深度为k且有2的k次方减1个结点的二叉树。4. 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点对应。5. 遍历二叉树：1）根据二叉树写遍历结果：a）先序遍历（先根遍历）：-+ a * b - c d / e fb）中序遍历（中根遍历）：a + b * c - d - e / fc）后序遍历（后根遍历）：a b c d - * + e f / -DLRLDRLRDABGD2）根据遍历结果画二叉树： 一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出，

9、试求出空格处的结点字符，并画出该二叉树。先 序：_B_EHI_FG_K_中序：D _HEIA _CJG _后序：_h_ebf_kg_a_解题思路：a）由先序或后序确定根结点；如本题后序最后一个为A,根结点为A,所以先序第一个空就为 Aob）在中序找出根结点，根结点左侧为左子树，右侧为 右子树；如本题 D_HEI为左子树，_CJG_右子树c）由先序确定紧跟在根结点后的左子树根；如本题紧 跟在A后的是B, B为左子树根，中序根结点的左子树 只有一个空，所以为Bod）继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树；如本题B的左子树为D,右子树为HEI ,所以先序第二个空为Doe）重复c

10、）、d）步骤确定整棵左子树；如本题先序中紧跟在D后的是E, E为B的右子树，由中序中看出E左子树为H,右子树为I，补充后序填空，前两空分别为 D和I of）由后序确定右子树根的左子树，再由中序确定右子树根；如本题紧跟在 B后的是F, F为 右子树根的左子树，已知中序_CJG右子树，F只可能第一个空，那第二个空为 K,补全 先序、中序、后序填空并可画出二叉树。6. 森林与二叉树的转换：1）树转换成二叉树：连兄弟，留长子，删孩子。a）连线，连接所有兄弟结点。b）删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c）整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。d）注意

11、，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。2) 森林转换成二叉树 ：连树根及兄弟，留长子，删孩子。a) 连线，连接每棵树的根结点及所有兄弟结点。b) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。c) 整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树， 从兄弟转换为孩子的 结点为右子树。3) 二叉树转换成树：连左孩子的右孩子及其右孩子，删原树右孩子。a) 连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点 XLR左孩子的右孩子的 右孩子结点XLRR左孩子的右孩子的右孩子的右孩子结点 XLRR都与X结点连线。b) 删线，删除原二叉

12、树的所有双亲与右孩子结点的连线。c) 整理，原二叉树根结点为树根结点。4) 二叉树转换成森林：连左孩子的右孩子及其右孩子，删原树右孩子。a) 连线，若某结点X存在左孩子XL,则将这个左孩子的右孩子结点 XLR左孩子的右孩子的 右孩子结点XLRR左孩子的右孩子的右孩子的右孩子结点 XLRR都与X结点连线。b) 删线，删除原二叉树的所有双亲与右孩子结点的连线。c) 整理，调整为多棵树的森林。7. 赫夫曼树 ：又称最优树，是一类带权路径长度最短的树。a) 两个最小数值组成一对，小的在前，大的在后；如上图中 2与4最小， 2在前， 4在后。b) 将两个最小数值的和算作一个数，再与其他数重复a)步骤；如

13、上图中2与4的和为6，5与 6 最小， 5 在前， 6 在后。c) 最后计算WPL它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中 WPL=2*3+4*3+5*2+7*1=35。8. 赫夫曼编码 ：a) 在赫夫曼树上，左分支代表 0，右分支代表 1。b) 由根结点到指定结点的路径 (从上到下把 0 1连起来) ，就是该结点的赫夫曼编码；如上 图 (d) 中 a 为 0 ， b 为 10， c 为 110， d 为 111。第 7章 图1. 图：多个结点，结点之间的关系可以是任意的， 图中任意两个数据元素之间都有可能相关。2. 无向完全图 ：有 n(n-1)/2 条边的无向图。3

14、. 有向完全图：有n(n-1)条边的有向图。4. 入度：以顶点V为头的弧的数目称为V的入度。5. 出度：以V为尾的弧的数目称为V的出度。6. 连通图 ：在无向图中，任意两个顶点之间都有路径。7. 连通分量 ：在无向图中的极大连通子图。8. 邻接矩阵 ：无向图的邻接矩阵关于主对角线对称， 在整个矩阵中非零元素的个数等于边个 数的 2 倍，第 i 行和第 i 列中非零元素的个数等于该结点的度。9. 邻接表：无向图的邻接矩阵关于主对角线对称， 在整个矩阵中非零元素的个数等于边个数 的 2 倍，第 i 行和第 i 列中非零元素的个数等于该结点的度。10. 深度优先遍历 ：从图中某个顶点出发，搜索与之相

15、关联的顶点，选择一个访问(从左到 右，从上到下)；再从该顶点出发，搜索与之相关联且未访问过的顶点，选择一个访问；重 复上步骤，直到没有相关联且未访问过的顶点；后退一个顶点继续搜索访问，直到所有顶点 都被访问过。a) 从V0出发，先找到V0的关联顶点V3。b) 由V3出发，找到V1 ;由V1出发，没有关联的顶点。c) 回到V3,从V3出发，找到V2;由V2出发，没有关联的顶点。d) 回到V3,再回到V0,由V0出发，找到V4。e）从V4出发，找到V1因为V1已经被访问过了，所以不访问。 所以最后顺序是 V0, V3, V1, V2, V4。11. 广度优先遍历 ：从图中某个顶点出发，搜索与之相关

16、联的顶点，逐个访问（从左到右， 从上到下）；再从这些顶点出发，搜索与之相关联且未访问过的顶点，逐个访问；重复上步 骤，直到所有顶点都被访问过。a）从V0出发，先找到V0的关联顶点V3、V4。b）由V3出发，找到V1 V2;由V4出发，找到V1,因为V1已经被访问过了，所以不访问。c）由V1出发，没有关联的顶点；由V2出发，没有关联的顶点。 所以最后顺序是 V0, V3, V4, V1, V2。12. 最小生成树 ：1）普里姆算法 ：连相邻权值最小的。2）克鲁斯卡尔算法 ：先连权值最小的，再依次连。13. 拓扑排序 ：由某个集合上的一个偏序得到该集合上的一个全序的操作。14. 关键路径 ：路径长

17、度最长的路径。1） 如图，先求各事件的最早发生时间（顺序为 V1V9）V1的最早发生时间为0，V2的最早发生时间为6，V3的最早发生时间为4，V4的最早发生时 间为5。对于V5,需要V2, V3均发生，V2发生且完成的时间为6+1=7; V3发生且完成的时 间为4+仁5,因而V5的最早发生时间为7。同理可求出各顶点的最早发生时间：V1V2V3V4V5V6V7V8V9e(i)0645771614182） 求各事件的最晚发生时间（顺序为V9V1)V9 的最晚时间为 18， V8 的最晚时间为18-a11=14，V7 的最晚时间为18-a10=16， V6 的最晚时间为l4-a9=10,V5的最晚时

18、间为V7的最晚时间减去a7和V8的最晚时间减去a8两者较小的，则V5的最晚时间为7,同理可得其他顶点的最晚发生时间：V1V2V3l(i) 0 6 6V4V587V610V7V81614V918则li与ei相等的事件即为关键事件即： V1， V2， V5， V7， V8，V9可得关键路径：V1, V2, V5, V7, V9或V1， V2， V5，V8， V93） 求各活动的最早发生时间a1a2a3a4a5a6a7a8a9a10a11e(i)00064577716144） 求各活动的最晚发生时间a1a2a3a4a5a6a7a8a9a10a11l(i)6-6=06-4=28-5=37-1=67-1

19、=610-2=816-9=714-7=714-4=1018-2=1618-4=14则li与ei相等的活动即为关键活动即： a1， a4， a7， a8， a10，a11可得关键路径：V1, V2, V5, V7, V9或V1， V2， V5，V8， V915. 最短路径 ：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最 小的一条路径。1） 迪杰斯特拉算法 ：2） 弗洛伊德算法 ：方法：两条线，从左上角开始计算一直到右下角 如下所示：给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点。 最后A3即为所求结果。第 9 章、查找1. 查找表 ：

20、是由同一类型的数据元素（或记录）构成的集合。2. 关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素 （或记录）。3. 静态查找表 ：查询某个特定的数据元素是否在查找表中， 检索某个特定的数据元素的各种 属性。1）顺序查找法 ：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记 录的关键字和给定值比较相等，则查找成功，找到所查记录；反之若直至第一个记录，其关 键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。其存储结构要求 ：以顺序表或线性链表表示的静态查找表。其平均查找长度 ：假设每个记录的查找概率相等，即 Pi=1/n ，则在等概率情

21、况下顺序查找的 平均查找长度为， ASL=（n+1）/2 。2）折半查找法 （二分查找法 ）：先确定待查记录所在的范围（区间），然后逐步缩小范围直 到找到或找不到该记录为止。其存储结构要求 ：以有序表表示的静态查找表。其平均查找长度 ：假设表中每个记录的查找概率相等（ Pi=1/n ），则查找成功时折半查找的 平均查找长度为， ASL=（n+1）/n*log2（n+1）-1 。3）索引顺序表查找法 （分块查找法 ）：先确定待查记录所在的块（子表），然后在块中顺序 查找。其存储结构要求 ：以索引顺序表表示的静态查找表。其平均查找长度：将长度为n的表均匀地分成b块，每块含有s个记录，即b=n/s;

22、又假 设表中每个记录的查找概率相等，则每块查找概率为 1/b ，块中每个记录的查找概率为 1/s， 若用顺序查找确定所在块，则分块查找的平均查找长度为， ASL=（n/s+s）/2+1 ;若用折半查找 确定所在块，则分块查找的平均查找长度为， ASL- Iog2（ n/s+1）+s/2 。4. 动态查找表 ：在查找过程中同时插入查找表中不存在的数据元素， 或者从查找表中删除已 存在的某个数据元素。1）二叉排序树 ：或者是一棵空树;或者是具有下列性质的二叉树： 1 、若它的左子树不空， 则左子树上所有结点的值均小于它的根结点的值; 2、若它的右子树不空，则右子树上所有结 点的值均大于它的根结点的

23、值; 3、它的左、右子树也分别为二叉排序树。2）平衡二叉树（AVL树）：它或者是一棵空树；或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。若将二叉树上 结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图、，是该情 况的最简单的图形，是该情况的一般的图形。设x为最小不平衡子树的根结点，y为刚插入的点左左：即在x的左孩子a的左孩子c上

24、插入一个结点y （该结点也可以是c,如图），即y 可以是c,也可以是c的左孩子（如图），也可以是 c的右孩子（不在画出）。图就不用说了，结点x和结点a变换，则树平衡了；那么图就是树中的一般情况了 a结 点有右孩子d,那要进行x和a变换，那么a的右孩子放哪啊？很简单，如图放在 x的左孩 子上；分析：xd,da,所以d可作为x的左孩子，且可作为a的右孩子中的孩子。下边这样 的类似情况不再一一分析，自己分析分析 实现：找到根结点x，与它的左孩子a进行交换即可使二叉树树再次平衡；右右：即在x的右孩子a的右孩子c上插入一个结点y （该结点也可以是c,如图），即y 可以是c,也可以是c的右孩子（如图），也

25、可以是 c的左孩子（不在画出）。实现：找到根结点x，与它的右孩子a进行交换即可使二叉树树再次平衡；左右：即在x的左孩子a的右孩子c上插入一个结点y （该结点也可以是c,如图），即y 可以是c,也可以是c的右孩子（如图），也可以是 c的左孩子（不在画出）。这个左右和下边的右左，稍微复杂了点，需要进行两次交换，才能达到平衡，注意这时y是c 的右孩子，最终 y 作为 x 的左孩子；若 y 是 c 的左孩子，最终 y 作为 a 的右孩子，画图分 析一下 下边类似，不再敖述。实现：找到根结点x，让x的左孩子a与x的左孩子a的右孩子c进行交换，然后再让x与x 此时的左孩子c进行交换，最终达到平衡；右左：即

26、在x的右孩子a的左孩子c上插入一个结点y （该结点也可以是c,如图），即y 可以是c,也可以是c的右孩子（如图），也可以是 c的左孩子（不在画出）。实现：找到根结点x，让x的右孩子a与x的右孩子a的左孩子c进行交换，然后再让x与x 此时的右孩子c进行交换，最终达到平衡； 上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大树中的最小 不平衡子树，一定要想清楚，别迷了！另外一定要注意这个交换操作，比如 a 与 b 交换（ a 在上，b在下），b 一定要占据a的位置！什么意思？就是b要放在（覆盖）储存a的那块内 存上，再通俗点说，若a是x的左孩子，则交换后b要做x的左孩子；这就是所谓的b占据 a 的位置！5. 哈希表 ：1） 构造方法 ：a）直接定址法 ：取关键字或关键字的某个线性函数值为散列地址。即 H（key）=key 或 H（key） =a key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中 H（key）中已经 有值了，就往下一个找，直到 H（key）中没有值了，就放进去。b）数字分析法 ：分析一组数据， 比如一组员工的出生年月日，