《数据结构(C语言版)》复习重点.doc

《数据结构(语言版)》复习重点
重点在二、三、六、七、九、十章，考试内容两大类：概念，算法

第章、绪论
. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
其类基本结构：集合、线性结构、树形结构、图状结构或网状结构
. 逻辑结构：是数据元素之间的逻辑关系的描述。
. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。
其种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构
. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
其个重要特性：有穷性、确定性、可行性、输入、输出
. 时间复杂度：算法中基本操作重复执行的次数是问题规模的某个函数(),算法的时间度量记作，()(()) ；他表示随问题规模的增大，算法执行时间的增长率和()的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。
例如： () {;}
() (<){ ;}
() (<)
(<){ ;}
含基本操作“增”的语句的频度分别为、和²，则这个程序段的时间复杂度分别为()、()和(²)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶( )、指数阶(的次方)等。
. 空间复杂度：算法所需存储空间的度量记作，()(())。

第章、线性表
. 线性表：是最常用最简单的一种数据结构，一个线性表是个数据元素的有限序列。
. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。
存储位置计算：假设线性表的每个元素需占用个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第个数据元素的存储位置为()()()* 式中()是线性表第一个元素的存储位置，通常称做线性表的起始位置或基地址。
. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。
数据元素的存储映像称为结点，包括个域：存数据的数据域、存后继存储位置的指针域。
) 线性链表(单链表)特点：每个结点只包含个指针域。
在单链表的第一个结点之前附设的一个结点，称之为头结点。
假设是型变量，则为单链表的头指针，它指向表中第一个结点；>为第一个结点地址，>为空表。
生成结点：()(())
回收结点：()

) 循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是或>是否为空，而是它们是否等于头指针。

) 双向链表特点：有个指针域，其一指向直接后继，另一指向直接前趋。

第章、栈和队列
. 栈：是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底，不含有元素的空表称为空栈；栈又称为后进先出的线性表。
. 队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为队头。
) 链队列：用链表示的队列。一个队列需要两个分别指示队头和队尾的指针（分别成为头指针和尾指针）才能确定唯一。和单链表一样，也给链队列添加一个头结点，并令头指针指向头结点。

) 循环队列：与顺序栈类似，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针和分别指示队列头元素及队列尾元素的位置。初始化建空队列时，令 ，每当插入新的队列尾元素时，“尾指针增”；每当删除队列头元素时，“头指针增”。

第章、串
. 串：是由零个或多个字符组成的有限序列。

第章、数组和广义表
. 数组特点：与线性表一样，所有数据元素都必须属于同一数据类型。
. 数组的顺序存储结构：由于数组一般不作插入或删除操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不会发生变动，因此采用顺序存储结构表示数组。
存储位置计算：假设每个数据元素需占用个存储单元，则二维数组中任一元素的存储位置可由下式确定
以行序为主序的存储结构：()()(*)*
以列序为主序的存储结构：()()(*)*
式中()是的存储位置；()是的存储位置，即二维数组的起始存储位置，也称基地址或基址；在以行序为主序的存储结构时为每行存储元素的个数(列数)，在以列序为主序的存储结构时为每列存储元素的个数(行数)。
. 广义表：是线性表的推广，也有人称其为列表（，用复数形式以示与统称的表的区别）。记作(,…) ，其中是广义表(,…)的名称，是它的长度。在线性表的定义中，(≤≤)只限于是单个元素。而在广义表的定义中，可以是单个元素，也可以是广义表，分别称为广义表的原子和子表。
例如：

第章、树和二叉树
. 二叉树：是一种树型的结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
. 二叉树的性质：
) 性质：在二叉树的第层上至多有的减次方个结点(≥)。
) 性质：深度为的二叉树至多有的次方减个结点(≥)。
深度为的二叉树至少有个结点(≥)。
深度为的完全二叉树至少有的次方减的减次方个结点(≥)。
) 性质：对任何一棵二叉树，如果其终端结点数为，度为的结点数为，则。
) 性质：具有个结点的完全二叉树的深度为[]。
) 性质：如果对一棵有个结点的完全二叉树（其深度为[]）的结点按层序编号（从第层到第[]层，每层从左到右），则对任一结点（≤≤）有：
) 如果，则结点是二叉树的根，无双亲；如果>，则其双亲()是结点[]。
) 如果>，则结点无左孩子（结点为叶子结点）；否则其左孩子()是结点。
) 如果>，则结点无右孩子；否则其右孩子()是结点。
. 满二叉树：一颗深度为且有 的次方减个结点的二叉树。
. 完全二叉树：深度为的，有个结点的二叉树，当且仅当其每一个结点都与深度为的满二叉树中编号从至的结点一一对应。
. 遍历二叉树：
) 根据二叉树写遍历结果：

) 先序遍历（先根遍历）：
*

) 中序遍历（中根遍历）：
*

) 后序遍历（后根遍历）：
*

) 根据遍历结果画二叉树：
一棵二叉树的先序、中序和后序序列分别如下，其中有部分未给出，试求出空格处的结点字符，并画出该二叉树。
先序：
中序：
后序：
解题思路：
) 由先序或后序确定根结点；如本题后序最后一个为，根结点为，所以先序第一个空就为。
) 在中序找出根结点，根结点左侧为左子树，右侧为右子树；如本题为左子树，为右子树。
) 由先序确定紧跟在根结点后的左子树根；如本题紧跟在后的是，为左子树根，中序根结点的左子树只有一个空，所以为。
) 继续由中序确定左子树根的左右子树，左侧为左子树，右侧为右子树；如本题的左子树为，右子树为，所以先序第二个空为。
) 重复)、)步骤确定整棵左子树；如本题先序中紧跟在后的是，为的右子树，由中序中看出左子树为，右子树为，补充后序填空，前两空分别为和。
) 由后序确定右子树根的左子树，再由中序确定右子树根；如本题紧跟在后的是，为右子树根的左子树，已知中序为右子树，只可能第一个空，那第二个空为，补全先序、中序、后序填空并可画出二叉树。
. 森林与二叉树的转换：
) 树转换成二叉树：连兄弟，留长子，删孩子。
) 连线，连接所有兄弟结点。
) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。
) 整理，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。
) 注意，由于树根没有兄弟结点，固树转换为二叉树后，二叉树根结点的右子树必为空。

) 森林转换成二叉树：连树根及兄弟，留长子，删孩子。
) 连线，连接每棵树的根结点及所有兄弟结点。
) 删线，仅保留双亲与长子结点的连线，删除与其他孩子结点之间的连线。
) 整理，第一棵树根结点为二叉树根结点，原有的长子结点为左子树，从兄弟转换为孩子的结点为右子树。

) 二叉树转换成树：连左孩子的右孩子及其右孩子…，删原树右孩子。
) 连线，若某结点存在左孩子，则将这个左孩子的右孩子结点、左孩子的右孩子的右孩子结点、左孩子的右孩子的右孩子的右孩子结点…都与结点连线。
) 删线，删除原二叉树的所有双亲与右孩子结点的连线。
) 整理，原二叉树根结点为树根结点。

) 二叉树转换成森林：连左孩子的右孩子及其右孩子…，删原树右孩子。
) 连线，若某结点存在左孩子，则将这个左孩子的右孩子结点、左孩子的右孩子的右孩子结点、左孩子的右孩子的右孩子的右孩子结点…都与结点连线。
) 删线，删除原二叉树的所有双亲与右孩子结点的连线。
) 整理，调整为多棵树的森林。

. 赫夫曼树：又称最优树，是一类带权路径长度最短的树。

) 两个最小数值组成一对，小的在前，大的在后；如上图中与最小，在前，在后。
) 将两个最小数值的和算作一个数，再与其他数重复)步骤；如上图中与的和为，与最小，在前，在后。
) 最后计算，它等于每个数值乘以从根结点到这个数值的连线个数的积之和；如上图中****。
. 赫夫曼编码：
) 在赫夫曼树上，左分支代表，右分支代表。
) 由根结点到指定结点的路径(从上到下把、连起来)，就是该结点的赫夫曼编码；如上图()中为，为，为，为。

第章、图
. 图：多个结点，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。
. 无向完全图：有()条边的无向图。
. 有向完全图：有()条边的有向图。
. 入度：以顶点为头的弧的数目称为的入度。
. 出度：以为尾的弧的数目称为的出度。
. 连通图：在无向图中，任意两个顶点之间都有路径。
. 连通分量：在无向图中的极大连通子图。

. 邻接矩阵：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个数等于边个数的倍，第行和第列中非零元素的个数等于该结点的度。

. 邻接表：无向图的邻接矩阵关于主对角线对称，在整个矩阵中非零元素的个数等于边个数的倍，第行和第列中非零元素的个数等于该结点的度。

. 深度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，选择一个访问（从左到右，从上到下）；再从该顶点出发，搜索与之相关联且未访问过的顶点，选择一个访问；重复上步骤，直到没有相关联且未访问过的顶点；后退一个顶点继续搜索访问，直到所有顶点都被访问过。

) 从出发，先找到的关联顶点。
) 由出发，找到；由出发，没有关联的顶点。
) 回到，从出发，找到；由出发，没有关联的顶点。
) 回到，再回到，由出发，找到。
) 从出发，找到，因为已经被访问过了，所以不访问。
所以最后顺序是, , , , 。
. 广度优先遍历：从图中某个顶点出发，搜索与之相关联的顶点，逐个访问（从左到右，从上到下）；再从这些顶点出发，搜索与之相关联且未访问过的顶点，逐个访问；重复上步骤，直到所有顶点都被访问过。

) 从出发，先找到的关联顶点、。
) 由出发，找到、；由出发，找到，因为已经被访问过了，所以不访问。
) 由出发，没有关联的顶点；由出发，没有关联的顶点。
所以最后顺序是, , , , 。
. 最小生成树：
) 普里姆算法：连相邻权值最小的。

) 克鲁斯卡尔算法：先连权值最小的，再依次连。

. 拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作。

. 关键路径：路径长度最长的路径。

) 如图，先求各事件的最早发生时间（顺序为）
的最早发生时间为，的最早发生时间为，的最早发生时间为，的最早发生时间为。对于，需要，均发生，发生且完成的时间为；发生且完成的时间为，因而的最早发生时间为。同理可求出各顶点的最早发生时间：

()
) 求各事件的最晚发生时间（顺序为）
的最晚时间为，的最晚时间为，的最晚时间为，的最晚时间为，的最晚时间为的最晚时间减去和的最晚时间减去两者较小的，则的最晚时间为，同理可得其他顶点的最晚发生时间：

()
则[]与[]相等的事件即为关键事件
即：，，，，，
可得关键路径：，，，，或，，，，
) 求各活动的最早发生时间

()

) 求各活动的最晚发生时间

()

则[]与[]相等的活动即为关键活动
即：，，，，，
可得关键路径：，，，，或，，，，
. 最短路径：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。
) 迪杰斯特拉算法：

) 弗洛伊德算法：

方法：两条线，从左上角开始计算一直到右下角 如下所示：
给出矩阵，其中矩阵是邻接矩阵，而矩阵记录两点之间最短路径所必须经过的点。

最后即为所求结果。
第章、查找
. 查找表：是由同一类型的数据元素（或记录）构成的集合。
. 关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。
. 静态查找表：查询某个特定的数据元素是否在查找表中，检索某个特定的数据元素的各种属性。
) 顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
其存储结构要求：以顺序表或线性链表表示的静态查找表。
其平均查找长度：假设每个记录的查找概率相等，即，则在等概率情况下顺序查找的平均查找长度为，()。
) 折半查找法（二分查找法）：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
其存储结构要求：以有序表表示的静态查找表。
其平均查找长度：假设表中每个记录的查找概率相等（），则查找成功时折半查找的平均查找长度为，()*()。
) 索引顺序表查找法（分块查找法）：先确定待查记录所在的块（子表），然后在块中顺序查找。
其存储结构要求：以索引顺序表表示的静态查找表。
其平均查找长度：将长度为的表均匀地分成块，每块含有个记录，即[]；又假设表中每个记录的查找概率相等，则每块查找概率为，块中每个记录的查找概率为，若用顺序查找确定所在块，则分块查找的平均查找长度为，()；若用折半查找确定所在块，则分块查找的平均查找长度为，≈()。
. 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。
) 二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；、它的左、右子树也分别为二叉排序树。
) 平衡二叉树（树）：它或者是一棵空树；或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过。若将二叉树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是 、和。只要二叉树上有一个结点的平衡因子的绝对值大于，则该二叉树就是不平衡的。

下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图①、②，①是该情况的最简单的图形，②是该情况的一般的图形。
设为最小不平衡子树的根结点，为刚插入的点
左左：即在的左孩子的左孩子上插入一个结点（该结点也可以是,如图①），即可以是，也可以是的左孩子（如图②），也可以是的右孩子（不在画出）。

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

实现：找到根结点，与它的右孩子进行交换即可使二叉树树再次平衡；
左右：即在的左孩子的右孩子上插入一个结点（该结点也可以是,如图①），即可以是，也可以是的右孩子（如图②），也可以是的左孩子（不在画出）。

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

实现：找到根结点，让的右孩子与的右孩子的左孩子进行交换，然后再让与此时的右孩子进行交换，最终达到平衡；
上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大树中的最小不平衡子树，一定要想清楚，别迷了！另外一定要注意这个交换操作，比如与交换（在上，在下），一定要占据的位置！什么意思？就是要放在（覆盖）储存的那块内存上，再通俗点说，若是的左孩子，则交换后要做的左孩子；这就是所谓的占据的位置！
. 哈希表：
) 构造方法：
) 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即()或() · ，其中和为常数（这种散列函数叫做自身函数）。若其中(）中已经有值了，就往下一个找，直到(）中没有值了，就放进去。
) 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
) 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
) 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
) 除留余数法：取关键字被某个不大于散列表表长的数除后所得的余数为散列地址。即 () <。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对的选择很重要，一般取素数或，若选的不好，容易产生同义词。
) 处理冲突方法：
) 开放定址法：(() ) ，…，(<），其中(）为散列函数，为散列表长，为增量序列，可有下列三种取法：
. ，…，，称线性探测再散列；
. ^^^^，^，…，±^,(<）称二次探测再散列；
. 伪随机数序列，称伪随机探测再散列。
) 再哈希法：()，…， 均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
) 链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间[]上，则设立一个指针型向量 []；其每个分量的初始状态都是空指针。凡哈希地址为的记录都插入到头指针为[]的链表中。在链表中的插入位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。
) 建立一个公共溢出区：假设哈希函数的值域为[]，则设向量[]为基本表，每个分量存放一个记录，另设立向量[]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们有哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

第章、内部排序
. 排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。
. 直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增的有序表。

. 希尔排序（缩小增量排序）：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

. 冒泡排序：首先将一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即[]>[]），则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。以此类推，直至第个记录和第个记录的关键字进行过比较为止。

. 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

. 堆排序：只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。