数据结构期末复习

写在最前面：给好朋友写的算半个错题集的文章，很多都不是原创。不过我觉得考试里面的选择题、填空题、判断题大部分都能在里面找到相应的知识点，以后可能会来完善吧，知识概念比较多，没有关于算法的代码（因为本人是在太菜惹）

绪论
当问题的规模n趋向无穷大时，算法执行时间T（n）的数量级被称为算法的时间复杂度。通常情况下，鉴于运算空间较充足，人们都以算法的时间复杂度作为算法优劣的衡量指标。
空间复杂度也是问题规模n的函数。
评价一个算法时间性能的主要标准是算法的时间复杂度。
数据项：数据的最小单位
数据元素：数据的基本单位
数据结构是带有结构的各数据元素的集合
一些表面上很不相同的数据可以有相同的逻辑结构
一个递归算法必须包括终止条件和递归部分

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。

关于时间复杂度的判断：
i=1;      
while(i<=n)         
i=i3; 答案：O(log3 n)  
解释：语句i=i3;的执行次数log3 n。

1. 线性结构
   第一章 线性表
   将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是n次。
   解释：当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
   线性表中结点的集合是有限的，结点间的关系是一对一的。
   创建一个包括n个结点的有序单链表的时间复杂度是O(n²)。         解释：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，时间复杂度为O（n），所以确定合适的插入位置的单链表，时间复杂度是O(n2)。

注意线性表和广义表两个名词的区别！
线性表，最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。
顺序存储结构的地址在内存中是连续的所以可以通过计算地址实现随机存取，与此相对，链式存储结构的存储地址不一定连续，只能通过第i个结点的指针顺序存取。

顺序表（随机存取结构）
可随机访问任一个元素是顺序表的特点。
顺序表中基本操作的实现（插入，删除，求表长）
代码：
若长度为n的线性表采用顺序存储结构，在其第i个插入一个新元素的算法的时间复杂度为O(n)。
顺序存储可以实现“随机存取”，因此访问结点的时间复杂度为O(1)，而插入、删除结点由于涉及到大量移动元素，故其时间复杂度为O(n)。
一个向量（即一批地址连续的存储单元）第一个元素的存储地址是N，每个元素的长度（所占用的存储单元）为n，则第i个元素的地址是N+i*n。
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第（1 2 3 4 5 5和1之间的确隔了4个数）5个元素的地址是108【100+4】（注意：不是110）
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是n（当第一个有序表所有的元素都小于或大于第二个表中的元素）
除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
在一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为63.5（平均要移动的个数：n/2；）
补充1：n个元素的顺序表中，查找：平均移动的元素个数为(n+1)/2
补充2：n个元素的顺序表中，插入：平均移动的元素个数为n/2
补充3：n个元素的顺序表中，删除：平均移动的元素个数为(n-1)/2

链表（顺序存取结构）：
线性表若采用链式存储结构，要求内存中可用存储单元的地址连续或不连续都可以
顺序表存储密度等于1
链表适用于需不断对表进行插入，删除
创建一个包括n个结点的有序单链表的时间复杂度是O(n的平方) （创建表O(n)，排序也是如此）
存储密度=单链表数据项所占空间/结点所占空间

链栈的基本操作：

单链表存储密度小于1是因为结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1。原因是在数据结构中，存储密度：结点数据本身所占的存储量和整个结点结构所占的存储量之比。
在单链表中增加头结点，是因为通过比较带头结点与不带头结点单链表的建立、插入、删除等基本操作,说明带头结点单链表的算法简单、易懂、容易实现。
循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
②在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是静态链表。
顺序存储的线性表可以随机存取，在随机查找时，顺序表比较有优势，但由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。

链表具有的特点是，插入删除不需要移动元素，不必事先估计存储空间，所需空间与线性表长度成正比。

对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为用尾指针表示的循环单链表

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（N），因为要想使插入的元素后仍然有序，就是把所有节点（n个节点）都遍历下，所以是N。
建立一个有n个元素的有序单链表的时间复杂度是O(n^{2)，因为对单链表而言，一些快速的排序算法，不能用，只能用直接插入等o(n}2) 级的排序算法来实现排序。而有序单链表每次插入到链表尾结点，那么每次插入都要从头扫到尾，然后1+2+3+… m = O(m^2)这样。

带头结点的单链表head为空的判定条件head-nextNULL
不带头结点的单链表head为空的判定条件是headNULL

循环列表的概念
循环链表的主要优点是在表中任一结点出发都能扫描整个链表。

第二章 栈和队列
栈和队列的共同点是只允许在端点处插入和删除元素。
一个递归算法必须包括终止条件和递归部分。

队列（先进先出）
解决缓冲区问题，用到队列（先进先出的线性表）
循环队列用数组A【0，m-1】存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（rear-front+m）%m
数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（n+r-f)%n 
解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列， 差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。 
总结（尾-头+总数）再对总数取余。

队列只允许在队尾（rear）的一端进行插入操作，在队头（front）的一端进行删除操作

当利用大小为n的数组顺序存储一个队列时,该队列的最后一个元素的下标为(n-1 )
当利用大小为n的数组顺序存储一个队列时，该队列最大的容量为n-1
假设数组是type array[n]
type* front,*rear;
front=rear=array;
入队操作
*rear=x;
rear++;
出队操作
front++;
数组下标最大是n-1

用链接方式存储的队列，在进行删除运算时头，尾指针可能都要修改（一般情况下只修改头指针，但是，当删除的是队列中的最后一个元素时，队尾指针也丢失了，因此需要对队尾指针重新赋值）

最大容量为n的循环队列，队满(rear+1)%n == front;；队空rear == front;

循环队列存储在数组A[0…m]中，则入队时的操作为rear=(rear+1)%(m+1) 
解释：数组A[0…m]中共含有m+1个元素，故在求模运算时应除以m+1。

队列的基本运算：
① 在队尾插入一个新元素，指针移动到新队尾
② 删除队列中的队头元素，指针移动到新队头
③ 判断一个队列是否为空，该函数为布尔函数，若队列为空，返回真值；反之返回假值。
④ 初始化队列，建立一个空队列Q
⑤ 读取队头元素的值

栈（先进后出）
栈在递归调用，函数调用，表达式求值都有所应用
【栈是堆栈，是一种“特殊”的线性表，这种线性表的插入和删除运算只允许在表的一端进行】
若已知一个栈的进栈序列是1,2,3,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为n-i+1
正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是top=top-1

判断表达式中括号配对用到栈

栈的插入和删除运算只允许在表的一端进行，允许进行插入和删除运算的这一端称为栈顶（top），另一端称为栈底（Bottom），不允许进行插入和删除运算。向栈中插入一个新元素称为入栈或压栈，从栈中删除一个元素称为出栈或退栈。处于栈顶位置的数据元素称为栈顶元素，栈顶元素的位置由栈顶指针变量记录。当栈中不含任何数据元素时称为空栈。

链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作x=top->data;top=top->link；解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点， 即摘除栈顶结点。
从一个栈顶指针为HS的链栈中删除一个结点时，用X保存被删结点的值，则执行x=HS-＞data，因为HS是一个指针，所以不能把一个数赋值给HS，即HS = HS->data是错误的，HS就不再指向该链表了，指向了内存地址为data的地方。呵呵，程序跑飞了。
正确的应该是x=HS->data;HS=HS->next;
总结：先将结点的值保存，然后原本指向结点指针指向下一个，该结点就被删除了

若一个栈以向量V[1…n]存储，初始栈顶指针top设置为n+1，则元素x进栈的正确操作是top–；V[top] = x;（V[1…n]存储和top设置为n+1，可以看出：元素从数组向量的高端地址进栈）

对于在出栈序列中任意元素，其之后值小于该元素的元素必须是降序排列，否则就是不可能的序列。
原因如下:
1.所有元素都是从小到大顺序进栈, 所以栈顶元素一定比栈中的其他元素(如果有的话)大;
2.根据"后进先出"的原则, 在出栈序列中, 曾经同一时刻存在于栈的元素, 值最大的栈顶元素会排在其他元素的前面;
3.栈中的每一个元素都有机会成为栈顶元素;
综合以上三点, 就是一个类似于降序的选择排序过程(每次都挑选最大的元素放在最前面), 使得曾经同一时刻存在于栈的元素按照降序排列, 即每一个元素后值比该元素小的元素都呈降序排列)
另注: 对于任一个元素后面的值比该元素大的元素, 它们既可以是升序(进栈后立即出栈), 也可以是降序(进栈后都等待比它更大的元素进栈) , 因此不能作为判断依据.

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是3
解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、 e3、e6、e5和e1（队列先进先出）即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈（栈先进后出），易知栈S中最多同时存在3个元素，故栈S的容量至少为3。

（5）设有一个递归算法如下
int fact(int n) 
{//n大于等于0             
if(n<=0) return 1; 
else return n*fact(n-1);
} 
则计算fact(n)需要调用该函数的次数为 n+1 
解释：特殊值法。设n=0，易知仅调用一次fact(n)函数

第三章 串
串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。

串的模式匹配目的在于判断串t是否是串s的子串。通常，将串s称为目标串，串t称为模式串。如果串t是串s的子串，则返回其在主串s中首次出现的起始位置，并返回匹配成功；反之匹配不成功，串t不在串s中。
BF算法采用顺序存储结构实现；KMP是改进的算法。
BF算法的思想：从目标串s的第一个字符开始和模式串的第一个字符进行比较，若相等，依次比较后续字符，否则从目标串s的第二个字符开始重新与模式串的第一个字进行比较，重复该过程。
最好的情况下，时间复杂度是（m+n），最坏的情况下，时间复杂度是（mn）
KMP算法改进的地方：每一次滑动过程中发现字符比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后？，继续进行比较，完成串的模式匹配。
KMP算法的时间复杂度是O（mn），但在一般情况下，其实际的执行时间近似于O（m+n）。
KMP算法在第一个字符就发生失配的情况下，算法效率最低，时间复杂度与BF算法一致，可以说是退化成BF算法；当模式串t中没有出现相同字符时，此时KMP算法的效能最佳，每次都可以实现当前最大量化的移动距离。

第四章 内部排序
如何辨别排序？
看排序的条件部分，那是排序算法的所在，函数主体就是交换语句。

什么是排序算法稳定性？
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。
不稳定排序有：希尔排序、简单选择排序、快速排序、堆排序；
稳定排序有：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。
希尔排序不能保证每趟排序至少能将一个元素放到其最终的位置上。 
解释：快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。

插入排序：
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法。
直接插入排序的基本思想：将一条待排序的记录按其关键字的大小插入到已经有序的记录中，直到所有记录插入完成，并成为一个递增序列。向有序表中插入记录主要完成如下操作：
① 搜索插入位置
② 移动插入点及其以后的记录空出插入位置
③ 插入记录
而插入位置是空出的i-j+1。
在一个长度为 n 的顺序表中第 i 个元素（1<=i<=n） 之前插入一个元素时，需向后移动n-i+1个元素。
空间复杂度是O（1），因为在排序过程中只需要一个辅助空间。
时间复杂度在最好的情况下是O（n），最坏的情况下是O（n²），平均是O（n²）
是否稳定性算法：是

选择排序：
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的。
时间复杂度：平均 O(n^2) 最优 O(n^2) 最差 O(n^2)
空间复杂度：O(1)
是否稳定排序算法：是（在判断用>=时，非稳定）

冒泡（交换）排序：
重复走访要排序的序列，两两比较顺序错误就交换，依此类推，直到走完要排序序列，这时最大（最小）数浮动到数列末尾。
时间复杂度：平均 O(n^2) 最优 O(n^2) 最差 O(n^2)
空间复杂度：O(1)
是否稳定排序算法：是
对n个不同的关键字由小到大进行冒泡排序，从大到小排列好的情况下比较的次数最多，即对关键字进行冒泡排序，关键字逆序时比较次数最多。
对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为n(n-1)/2。
解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1 次，即(n-1)+(n-2)+…+1= n(n-1)/2。

快速排序：
又称划分交换排序。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）。
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成。
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
快速排序是冒泡排序的一种改进排序方法。
其基本思想是：选择某个记录的关键字作为基准关键字（一般选择第一个记录的关键字），将待排序记录分割成两部分，一部分记录的关键字比基准字小，另一部记录的关键字比基准关键字大。然后，在每个部分内继续排序，直到整个记录有序为止。首先选取待排序数组的第一个数为基准关键字，然后分别从初始序列两端开始“探测”，没探测到就继续往前走。把基准数的值存起来，然后先从右往左（一定要先从右边开始）找一个小于基准关键字的数，然后把j所指的位置放到i指针所指的地方。再移动i指针，从左往右找一个大于基准关键字的数，找到后把i指针所指的数放到j指针的位置。这个过程并不是同时进行，而是回合制的单方面放置数值。这里可以用两个变量i和j，分别指向序列最左边和最右边。当i<j时，碰到相对应的数就直接交换；当i=j时，将该数与基准数交换位置；当i>j时，将j对应的数字与基准数做交换。快速排序的每一轮处理其实就是将这一趟的基准数（基准关键字）归位，直到所有的数都归位为止，排序就结束了。
空间复杂度：最好的情况下栈的空间是O（log2 n）；最坏的情况下栈的空间是O（n）。快速排序是递归的，执行时需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致，平均情况下是O（nlog2n）
时间复杂度：最好的情况下O（nlog2 n）；最坏的情况下O（n²）；平均情况下是O（nlog2 n），并且是同数量级，平均性能最好的一个。
是否稳定排序算法：否 （如：[ 4, 2, 3, 2] -> [2, 2, 3, 4]）这里的 4 - 2 交换，导致原有的 2、2排序被打乱。
快速排序在下列被排序的数据完全无序情况下最易发挥其长处，被排序的数据已基本有序是快速排序的最坏情况。

堆排序（一种选择排序）：
新建堆然后从堆中逐条取出元素。
堆：一种树状数据结构，需要满足如下性质：

1. 堆中的某个节点的值总是大于（大根堆）等于或小于（小根堆）等于其父节点的值；
2. 堆总是一棵完全二叉树；
   时间复杂度：平均 O(nlog2n) 最优 O(nlog2n) 最差 O(nlog2n)
   空间复杂度：堆排序空间复杂度为O(1) O(log2n) - 递归堆栈
   是否稳定排序算法：否

归并排序：
归并操作：将两个有序集合合并成一个有序集合。
建立在归并操作基础上的一种有效排序方式。
采用分治法：
1、分割：递归地把当前序列平均分割成两半。
2、集成：将上一步得到的有序子序列集成到一起（归并）。
时间复杂度：平均 O(nlogn) 最优 O(nlogn) 最差 O(nlogn)
空间复杂度：O（n） O(logn)
是否稳定性算法: 是

希尔排序：
也称递减增量排序算法，是插入排序的一种更高效的改进版本。它是基于插入排序的一下两点性质改进点：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2、插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
即通过指定步长排序，使得原有序列变得尽可能有序，从而使得最后一步的插入排序的效率极大提升，从而使得总排序时间高效。
时间复杂度：平均 O(nlogn) 最差 O(n^2)
空间复杂度：O(1)
是否稳定算法：是(这里使用的递归 n/2 的步长代码实现是，有些版本可能不是)

第五章 查找
折半查找代码：
int search(keytype key[],int n,keytype k)
{
int low=0,high=n-1,mid;
while(low<=high)（如果不满条件即跳出循环→查找失败）
{
mid=(low+high)/2;
if(key[mid]==k)
return mid; //查找成功，返回mid
if(k>key[mid])
low=mid+1; //在后半序列中查找
else
high=mid-1; //在前半序列中查找
}
return -1;//查找失败，返回-1
}

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为 (n+1)/2。       
解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

一、哈希表是什么？
散列表（Hash table，也叫哈希表），是根据关键码值(Key-Value)而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数所以我们可以知道：
哈希表的优点在于，查找效率高O（1），但是耗费空间。
思想我个人认为是空间换取时间……
二、哈希函数的构造方法：
1、直接定址法：取关键字或关键字的某个线性函数值为哈希地址。
2、数字分析法：假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3、平方取中法：取关键字平方后的中间几位为哈希地址。
4、斐波那契（Fibonacci）散列法
5、折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
6、除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p,(p<=m)，这是一种最简单，也是最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD），也可在折叠、平方取中等运算之后取模。
7、随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较切当。
三、哈希表的缺陷：
哈希表总会不可避免的产生冲突（尤其是在数据量大的时候），这个时候就需要一个方法来解决冲突，以下是几种常用的解决冲突的方法：
1、开放定址法
2、再哈希法
3、链地址法
4、建立一个公共溢出区

哈希表要会算，根据合适情况选最合适的。
关于哈希查找的说法，采用链地址法处理冲突时，查找一个元素的时间是不相同的，因为在同义词构成的单链表中，查找该单链表表中不同元素，所消耗的时间不同；采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的；用链地址法处理冲突，不会引起二次聚集现象；用链地址法处理冲突，适合表长不确定的情况

设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是9。
解释：关键字15放入位置4，关键字38放入位置5，关键字61放入位置6，关键字84 放入位置7，再添加关键字49，计算得到地址为5，冲突，用二次探测法解决冲突得到新地址为6，仍冲突，再用用二次探测法解决冲突，得到新地址为4，仍冲突，再用用二次探测法解决冲突，得到新地址为9，不冲突，即将关键字49放入位置9。

平衡二叉树：

二叉排序树的生成：
创建一个新结点时，把关键字存放在结点数据域中，如果二叉排序树为空，则新结点为二叉排序树的根；如果二叉排序树不空，将当前关键字与根节点的关键字进行比较，若小与根节点的关键字，则插入到根节点的左子树中，否则插入到根节点的右子树中。反复递归，直到所有的结点作为一个新的叶子插入到已有的二叉排序树中为止。
二叉排序树排序时要调整。

设二叉排序树中有n个结点,则在二叉排序树的平均查找长度为最坏情况是深度为N的单支树为（N+1）/2，最好的是形态均匀和折半查找一样大约为 LOG2 N。若已经构造完成，则按照1（第一层）*1（第一层只有一个节点）+2（第二层）*2（第二层只有两个节点）+…….按照画出的图来进行计算。

采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字不一定都是同义词。                  解释：所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。

分块查找
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用分块查找法。            
解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块， 就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。

m阶B-树的根结点至多有m棵子树，所有叶子都在同一层次上，非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树。
关于B-和B+树的叙述中，B-树和B+树都是平衡的多叉树，B-树和B+树都可用于文件的索引结构，B-树和B+树都能有效地支持随机检索。
m阶B-树是一棵m叉平衡排序树。

① 树形结构
第六章 二叉树
二叉树的遍历算法很重要

代码：
先序遍历：
① 访问根节点
② 先序遍历左子树
③ 先序遍历右子树
中序遍历：
① 先序遍历左子树
② 访问根节点
③ 先序遍历右子树
后序遍历：
① 先序遍历左子树
② 先序遍历右子树
② 访问根节点

树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。

对于一棵具有n个结点的二叉树，若一个结点的编号为i（0<i<n-1）【下标从0开始】，则它的左孩子结点的编号为2i,右孩子结点的编号为2i+1,双亲结点的编号为i/2。

深度为h的满m叉树的第k层有m的k次方 - 1 个结点。(1=<k=<h)           解释：深度为h的满m叉树共有m的h次方 - 1个结点，第k层有m的k次方 - 1 个结点

已知一棵完全二叉树有N个节点，则在该二叉树中叶子节点数为（N+1）/2个，其深度为k=【log2n】（求以2为底的对数，结果取整数，算出几就是几）+1层。
n等于0时，是空二叉树。
完全二叉树特点是：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都排在靠左的的位置上。显然，一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。【看清楚主语，不要搞反了】

利用二叉链表存储树，则根结点的右指针是空。        
解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用后序遍历方法最合适。
解释：后序遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。

一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足只有一个叶子结点。 
解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点。

在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为2n-1【这种题可以画图找规律】
树的某个结点子树个数称为该结点的度；而树的度数是指该树中所有结点度数的最大值；度数为零的结点称为终端结点（即树叶或叶子）；树中结点最大层次称为树的高度。

二叉树是有序树
二叉树有5种基本形态（空二叉树，仅有根结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，左右结点均非空的二叉树）
在二叉树的第i层上至多有2的(i-1)次方个结点
深度为k的二叉树至多有2的k次方-1个结点
叶子数 = 度为2的结点数 + 1
满二叉树（深度为k且含有(2的k次方-1)个结点），注意与完全二叉树的区分，别记混
完全二叉树，度为1的结点个数为0或1个

二叉树的左右子树有次序之分且度数不超过2的树是二叉树。
二叉树度数最大为2，二叉树五种基本形态：空二叉树，仅有根节点的二叉树，左子树为空的二叉树，右子树为空的二叉树，左右子树均不为空的二叉树。

一棵完全二叉树上有1001个结点，其中叶子结点的个数是501个    解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1（可以画图，根的头上没有分支），A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。
设哈夫曼树中有199个结点，则该哈夫曼树中有100个叶子结点。 解释：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1（度为0的叶子结点数是度为2结点数加1），则总结点数n= n0+n2=2*n0-1，得到n0=100。

一个具有1025个结点的二叉树的高h为11至1025之间      
解释：若每层仅有一个结点，则树高h为1025；且其最小树高为 log2 1025 + 1=11，即h在11至1025之间。

若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为X的左子树中最右结点。那么按照中序遍历的顺序，X的上一个刚刚访问过的结点就应为X左子树最右的节点。

引入二叉线索树的目的是加快查找结点的前驱或后继的速度。

设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有n + 1 个

把一棵树转换为二叉树后，这棵二叉树的形态是唯一的（因为二叉树是有序的）和森林的转换也是唯一的。

n（n≥2）个权值均不相同的字符构成哈夫曼树，不一定是完全二叉树，树中一定没有度为1的结点，树中两个权值最小的结点一定是兄弟结点，树中任一非叶结点的权值一定不小于下一层任一结点的权值 
解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。

二叉树转换为森林：
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。
（1）从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
（2）将每棵分离后的二叉树转换为树。

二叉树转换为树：
是树转换为二叉树的逆过程。
（1）加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
（2）去线。删除原二叉树中所有结点与其右孩子结点的连线。
（3）层次调整。

一棵完全二叉树上有1001个结点，其中叶子结点的个数501
n0 = n2 + 1
n0+n1+n2 = 1001
在完全二叉树中，n1 = 0或1
利用二叉链表存储树，则根结点的右指针为空（左孩子右兄弟，注意：问的是根结点）
在一棵度为4的数T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是82
n0+n1+n2+n3+n4-1 = n1+2乘以n2+3乘以n3+4*n4
一颗非空的二叉树的先序遍历序列和后序遍历序列正好相反，则二叉树
一定满足：只有一个叶子结点
或一定满足：所有的结点均无左孩子或所有的结点均无右孩子

线索二叉树会有多少空的指针域，会比较浪费空间。

AVL树（平衡二叉树） 、二叉排序树 、哈夫曼树都是二叉树。

哈夫曼树：
先找小的数字，合起来之后再放原集合中。
哈夫曼树中没有度为1的结点
哈夫曼树中两个权值最小的结点一定是兄弟结点
哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值
构造哈夫曼树步骤是，选择两个权值最小的点构造树，新树根权值为左右子树权值之和，新的权值放回到序列中，继续按照上述步骤构造树，直到只有一颗树为止。
权值排序一下：2 3 5 6 8
选择2和3构造树，权值序列变为
5 5 6 8
/
2 3
选择 5 5
6 8 10
/
5 5
/
2 3
选择 6,8构造权值14的树 然后选择 10,14，最终哈夫曼树为：
24 深度为0
/
10 14 深度为1
/ \ /
5 5 6 8 深度为2
/
2 3 深度为3
树带权路径长度WPL = 23 + 33 + 52 + 62 + 82 = 53
就是每个叶子结点的权值深度之和。
深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。

第七章 树
树的存储结构是二叉链表。
常用树的遍历方法有两种：先序遍历和后序遍历
二叉树和树是完全不同的概念，不能理解为树，教材上说树有且只有一个根结点，而二叉树可以为空。
B树不属于二叉树。
树的度是树内各结点的度的最大值.（结点拥有的子树数称为结点的度）
树的深度： 树中结点的最大层次
如果结点A有3个兄弟，B是A的双亲，则结点B的度是4，结点A有3个兄弟，那么算上本身，双亲B存在的3个子树，度为3+1=4

③ 复杂结构
第八章 图
连通图的遍历方法主要有两种：深度优先搜索遍历DFS和广度优先搜索遍历BFS。
深度优先搜类似于树的先序遍历；广度优先搜索类似于树的层次遍历。
BFS的规则：假定图中某个顶点Vi为出发点，再访问顶点Vi后，依次搜索访问Vi的各个未被访问过的邻接点Vk、Vm、Vn……。然后，顺序搜索访问Vk的各个未被访问过的邻接点……。即从Vi开始，由近及远，先左后右，按层次依次访问与Vi有路径相通且路径长度分别为1、2、……的顶点，直至连通图中所有顶点都被访问一次。
连通图：在无【有】向图中，如果顶点Vi到顶点Vj有路径，则称Vi和Vj连通。如果图中任意两个顶点之间都连通（就是路是通的），则称该图为连通图【强连通图】。否则，在非连通图中，将其极大连通子图称为连通分量【强连通分量】。
无论是DFS还是BFS对一个连通分支只需要执行一次就可以找到所有该连通分支的顶点。即两个连通分支，BFS算法只需要执行两次即可遍历完所有顶点。

图的代码实现（基本操作）

对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为n²

顶点v的度是指和v相关联的边的数目，几位TD（v）。图的入度是以顶点v、为头的弧的数目，记为ID（v）；出度是以顶点v为尾的弧的数目，记为OD（v）。

迪杰斯特拉和弗洛伊德算法是用来算最短路径的
迪杰斯特拉算法是按路径长度递增的次序产生最短路径。在不断选取最短路径的顶点时，顶点之间的逐步联通将影响路径长度的变化，选取最短路径进行求解。
从题目要求的顶点开始，第一次是一个节点到其他节点，第二次是走过第一个节点和第二个节点然后再到其他节点，然后依次累加。每次都会得出一个最短路径。
值得注意的是，Dijskra算法本身主要时间耗费在更新和迭代dist数组和path数组的两个循环上，故Dijskra算法本身的时间复杂度为O（n^{2）,但现在我们要求多源点问题，需要对Dijskra算法执行n次，故解决多源点最短路径的时间复杂度为O（n}3）

图的顺序存储——邻接矩阵；图的链式存储——邻接表。
邻接矩阵无论是何种图（UDG、DG、UDN、DN）空间复杂度为O（n^2）,所占用空间为n²；而对于邻接表而言，无向图与有向图所占用空间是不同的，邻接表是由顶点集和边集构成，顶点集存入了n个顶点，边集存入了2e条边（无向图相当于双向边，所以是2e）那么空间复杂度的阶级为O（n+e），所占用的存储n+2e个单位（链表的每一个顶点视为一个单位）。

对于无向图，具有 n(n-1)/2 条边，则称为无向完全图
对于有向图，具有 n(n-1) 条弧，则称为有向完全图
带权的图通常称为网
在一个无向图中，所有顶点的度数之和等于图的边数的2倍
n个顶点的连通图用邻接矩阵表示时，该矩阵至少有**2(n-1)**个非零元素
G是一个非连通无向图，共有28条边，则该图至少有9个顶点（若是连通图刚好8个顶点，但是，这是非连通图，要更大一些）
拓扑排序可以判断一个有向图是否有环
无向图的邻接矩阵是对称的

一个有 N 个顶点的有向图最多有N(N-1)条边。
n个顶点的强连通图中至少含有n条有向边，
对于一个具有n个顶点的有向图的边数最多有(n(n-1) )，也是有向完全图。
在一个图中，所有顶点的度数之和等于图的边数的2倍。
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的1倍（有向图所有顶点入度之和等于所有顶点出度之和）。
n个顶点的连通图用邻接矩阵表示时，该矩阵至少有2(n-1)个非零元素。

图的BFS生成树的树高比DFS生成树的树高小或相等。  
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS（广度）生成树的树高比DFS（深度）生成树的树高小。

若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是连通图，即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。

Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏 图G的最小生成树。

拓扑排序方法可以判断出一个有向图是否有环。

有关图的遍历：
深度优先搜索（通常借助栈来实现算法）
广度优先搜索（通常借助队列来实现算法）
连通图的深度优先搜索是一个递归过程，图的广度优先搜索中邻接点的寻找具有“先进先出”的特征，图的遍历要求每一顶点仅被访问一次。
非连通图能用深度优先搜索法

G是一个非连通无向图，共有28条边，则该图至少有【8*（8-1）/2（公式）+1（一个不连通的点）】个顶点，但在这里要求最少的顶点数，所以尽可能让每个顶点之间都有边，这样在边的数量给定的情况下，顶点就是最少的了，这个可以构造性的方法来说明构造:假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图连通无向图构成条件:边=顶点数*(顶点数-1)/2顶点数>=1，最后加上一个不连通的点变成非连通无向图。

用邻接表存储n个顶点，e条边的无向图G时（顶点集和边集每个结点至少2个域，数据域和指针域），则e小于多少n(n-1)/4才算是省空间的。用邻接表存储无向图，顶点集存储n个顶点，需要n个单位空间，每一个单位空间有两个域，所以顶点集需要占用空间为2n；边集需要2e个单位空间（无向图相当于双向边，所以是2e），每一个空间也就是每一个链节有两个域，那么边集占用的空间为4e；所以邻接表存储图G需要占用的总空间为2n+4e。若用邻接矩阵存储图G，邻接矩阵占用总空间为n^{2+n（矩阵本身的大小加上顶点数组Vertex）。又因为邻接矩阵适合存储稠密图，邻接表适合存储稀疏图，所以可以得到以下不等式：2n+4e<n}2+n，计算结果为e< n(n-1)/4。

若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数（第i行元素之和）即为顶点Vi的出度；第i列元素之和，可以得出Vi的入度。

用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。

对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点单链表中的结点数为k2
图的邻接表，反映的是节点的 出度 邻接情况； 图的逆邻接表，反映的是节点的 入度 邻接情况

最小生成树（找最短路径）：
在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树（最小生成树）
普里姆算法（加点法），适用于稠密图
克鲁斯卡尔算法（加边法），适用于稀疏图

拓扑排序（找关键路径）：
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

第九章 数组、矩阵和广义表
广义表(Lists，又称列表)，一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
广义表的长度是元素个数，深度是括号层数。
设广义表L=((a，b，c))，则L的长度和深度分别为1和2，只有一个元素长度是1，唯一的元素里嵌套一层，所以深度是2

广义表((a,b,c,d))的表头是(a,b,c,d)  ，表尾是（）。 
解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表， ((a,b,c,d))的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表尾一定是个广义表，((a,b,c,d))的表尾为空表( )。
广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为d 
解释：Tail(A)=(b,(c,d),(e,(f,g)))；
Tail(Tail(A))=( (c,d),(e,(f,g)))；
Head(Tail(Tail(A)))=  (c,d)；
Tail(Head(Tail(Tail(A))))=(d)；
Head(Tail(Head(Tail(Tail(A)))))=d。
总结：Tail去表头，Head留表头

数组A[0…4,-1…-3,5…7]中含有元素的个数45个
解释：共有5【0,1,2,3,4】*3【-1,-2,-3】3【5,6,7】=45个元素
设二维数组A[1… m，1… n]（即m行n列）按行存储在数组B[1… mn]中，则二维数组元素A[i,j]在一维数组B中的下标为(i-1)*n+j       
解释：特殊值法。取i=j=1，易知A[1,1]的的下标为1，四个选项中仅有A选项能 确定的值为1。
关于数组的计算：
二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8（从0开始，一共有9行，一行十个元素）,列下标 j=1,2,…,10（一共有10列，1列9个元素）。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素A[3,10] 的起始地址相同。设每个字符占一个字节。
原因：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A[8,5]的起 始地址为：M（首地址）+[（8-0）*10【前面有满满的8行，每行10个元素】+（5-1）【而最后的一行前面有4个元素】]*1（每个字符占一个字节）=M+84；若数组按列先存储，易计算出元素A[3,10]的起始地址为：M+[（10-1）*9【满满的9列，每列9个元素】+（3-0）【注意下标从0开始】]*1=M+84。故选B

若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中，则在B中确定aij（i<j）的位置k的关系为j*(j-1)/2+i 。

④ 文件结构
第十章 文件
第十一章 外部排序