数据结构知识点总结 第1篇
1. 顺序查找
2. 顺序查找的性能分析
3. 顺序查找算法的特点
分块查找性能评价
易错点：1. 注意mod的是m（表长），而不是求哈希值mod的那个东西了 2. 公式是基于hash（key）进行变化的，不是对原数进行变化
再哈希法：就是对出现的重复的哈希值再进行一次运算
链地址法：类似邻接表的形式，把所有映射值相同的元素都放到内部一个链表中
公共溢出区法：把出现冲突的数据直接放在另一个空间中存储起来
AVL树：自平衡二叉查找树，一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树 节点的平衡因子：节点的xxx的高度减去它的右子树的高度
装填因子：α=填入表中记录个数 / 哈希表长度，α越大，产生冲突的可能性越大，平均查找长度也就越大
二叉排序树：xxxxxx不为空，xxxxxx上节点的值均小于根节点，xxx右子树不为空，xxx右子树上节点的值均大于根节点，左右子树均为二叉排序树(这是一个递归的定义)
数据结构知识点总结 第2篇
基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律
前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素
并依此规xxx调整，直到每个子表的元素只剩一个。此时便为有序序列了。
优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！
前提：顺序存储结构
时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加
空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot)
稳 定 性： 不 稳 定 —因为有跳跃式交换。
数据结构知识点总结 第3篇
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规xxx交换。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一
旦下趟没有交换发生，还可以提前结束排序。
前提：顺序存储结构
冒泡排序的算法分析：
时间效率：O（n2) —因为要考虑最坏情况
空间效率：O（1） —只在交换时用到一个缓冲单元
稳 定 性： 稳定 —25和25*在排序前后的次序未改变
冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表
尾），还可以对前面的元素作一些整理，所以比一般的排序要快。
数据结构知识点总结 第4篇
深度优先搜索（遍历）步骤：
① 访问起始点 v;
② xxxv的第1个邻接点没访问过，深度遍历此邻接点；
③ xxx当前邻接点已访问过，再找v的第2个邻接点重新遍历。
基本思想：——仿树的先序遍历过程。
广度优先搜索（遍历）步骤：
① 在访问了起始点v之后，依次访问 v的邻接点；
② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；
③ 直到所有顶点都被访问过为止。
数据结构知识点总结 第5篇
Status DeQueue ( SqQueue &q, QElemType &e)
{//xxx不空，删除循环队列q的队头元素，
//由 e 返回其值，并返回OK
if ( = = ) return ERROR;//队列空
() % QUEUE_MAXSIZE ;
e = [ ] ;
return OK;
}// DeQueue
数据结构知识点总结 第6篇
基本思想：先将整个待排记录序列分割成xxx干子序列,分别进行直接插入排序，待整个序列
中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
优点：让关键字值小的元素能很快前移，且序列xxx基本有序时，再用直接插入排序处理，时
间效率会高很多。
数据结构知识点总结 第7篇
栈
栈的基本概念
栈的定义：只允许一端进行插入和删除操作的线性表
栈顶：栈允许进行插入和删除的那一端
栈底：固定的，不允许进行插入和删除的一端。
栈是一个先进后出的线性表
栈的基本操作
顺序栈：
顺序在的基本操作：
利用栈底位置不变的特性，让两个栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
链栈
采用链式存储的栈，通常采用单链表实现，并规定所有操作在单链表的表头进行，且链栈没有头结点，Lhead指向栈顶元素
队列的定义：只允许在表的一段进行插入，表的另一端进行删除
队列的基本操作
队列的顺序存储
分配一块连续的存储单元存放队列中的元素，并设置两个指针front和rear分别指示队头元素和队尾元素的位置。
结构体描述
循环队列
将顺序队列想象成一个环状空间，也就是逻辑上将存储队列元素的表看成一个环，xxx循环队列
队列的链式存储结构
队列的链式表示xxx链队列
双端队列
双端队列是指允许两端都可以进行入队和出队操作的
栈和队列的应用
矩阵
压缩矩阵：指多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值的多个矩阵元素压缩存储到一个存储空间中
稀疏矩阵
矩阵元素个数远大于非零元素个数的矩阵
1．掌握树型结构的定义。
2．掌握二叉树的定义、性质及各种存贮结构。
3．掌握遍历二叉树、线索二叉树及其他基本操作。
4．掌握树、森林与二叉树的相互转换；理解树的遍历；掌握哈夫曼树及其应用。
1．掌握图的定义和术语。
2．掌握图的存贮结构；理解图的基本操作。
3．掌握图的遍历算法；了解利用图的遍历解决图的应用问题。
4．理解图的有关应用：求最小生成树、求最短路径、拓扑排序及关键路径等算法的基本思想。
1．掌握静态查找表。
2．掌握二叉排序树和平衡二叉树。
3．理解B－树；了解B＋树。
4．掌握哈希表。
5．掌握各种查找方法的时间性能分析。
掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序；理解基数排序。
插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成，由插入排序的思想可以引申三个重要的排序算法：直接插入排序，折半插入排序和希尔排序。
根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法，假设在排序过程中，待排序表L[1...n]在某次排序过程重的某一个时刻状态如下:
要将元素L(i) 插入已有序的子序列L[1...i-1],需要执行以下操作（为避免混淆，下面用L[]表示一个表，而用L()表示一个元素）：
1. 查找出L(i)在L(1...i-1)中的插入位置k。
2. 将L[k...i-1]中的所有元素依次后移一个位置。
3. 将L(i)复制到L(k)。
为了实现对L[1...n]的排序，可以将L(2)~L(n)依次插入前面已经排好的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行n-1次就能得到一个有序的表，插入排序在现实上通常采用就地排序（空间复杂度O(1)）因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
下面是直接插入排序的代码：
直接插入排序算法的性能分析如下：
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。
在最坏情况下，表中元素顺序刚好与顺序结果中的元素顺序相反（逆序），总的比较次数达到最大，为(i+1)。
平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数约为。
因此，直接插入排序算法的时间复杂度为O().
稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素对位置发生变化的情况，xxx直接插入排序是一个稳定的排序算法。
适用性：直接插入排序算法适用于顺存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。
从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：
1. 从嵌满的有序子表中查找出待插入元素应该_入的位置；
2. 给插入位置腾出空间，将待插入元素复制到表中插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，xxx先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下：
从上述算法中，不难看出折半插入排序不仅减少了比较元素的次数，约为O(nlog2 n),该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n;而元素的移动次数并未改变，它依赖于待排序表的初始状态，因此，折半插入排序的时间复杂度仍为O(),但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。
从前面的分析可知，直接插入排序算法的时间复杂度为O(),但xxx待排序列为“正序”时，其时间复杂度可提高至O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。
希尔排序的基本思想是：先将待排序表分割成xxx干形如xxxL[i,i+d,i+2d,...,i+kd]的“特殊”子表，xxx把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的过程如下:先取一个小于n 的步长d1,把表中的全部记录分成d1组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长d2
希尔排序算法的代码如下：
希尔排序算法的性能分析如下：
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1).
时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O()。在最坏情况下希尔排序的时间复杂度为O()。
稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
适用性：希尔排序算法仅适用于线性表为顺序存储的情况。
所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。
冒泡排序的基本思想是：从后往前（或从前往后）两两比较相邻元素的值，xxx为逆序（xxxA[i-1]>A[i]）,xxx交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”（或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置......这样最多做n-1趟冒泡就能把所有元素排好序。
如图所示冒泡排序的过程，第一趟冒泡时：27<,不交换；13<27,不交换；76>13,交换；97>13,交换；65>13,交换；38>13，交换；49>13,交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，依次类推，到第5趟结束后没有发生交换，说明表已有序，冒泡排序结束。
冒泡排序算法的代码如下：
冒泡排序的性能分析如下：
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1);
时间效率：当初始序列有序时，显然第一趟冒泡后flag 依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为O(n);当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素3次交换元素位置。这种情况下，
比较次数=,移动次数=
从而，最坏情况下的时间复杂度为O() ,其平均时间复杂度也为O()。
稳定性:由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序方法。
注意：冒泡排序中产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
快速排序的基本思想是基于分治的：：在待排序表L[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分L[1..k-1]和L[k+1...n],使得L[1...K-1]中的所有元素小于pivot ,L[k+1...n]中的所有元素大于等于pivot,xxxpivot放在了其最终L(K)上，这个过程称为一趟快速排序（或一次划分）。然后分别递归地随两个子表重复上述过程，直至每部分内只有一个元素或空为止，xxx所有元素放在了其最终位置上。
一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和j ,初值分别为low和high,取第一个元素49为枢轴复制到变量pivot。
指针j从high往前搜索找到第一个小于枢轴的元素27，将27交换到i所指位置。
对算法的最好理解方式是搜总模拟一遍这些算法。
xxx分算法已知，记为Partition(),返回的是上述的k，注意到L(K)已经在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地条用快速排序算法进行排序，具体的程序结构如下：
从上面的代码不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。从快速排序算法提出至今，已有许多不同的划分操作版本，但考研所考察的快速排序的划分操作基本以xxx的教材《数据结构》为主，假设每次总以当前表中第一个元素作为枢轴来对表进行划分，xxx将表中比枢轴大的元素向右移动，将比枢轴小的元素向左移动，使得一趟Partition()操作后，表中的元素被枢轴值一分为二。代码如下：
快速排序算法的性能分析如下：
空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为O();最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n);平均情况下，栈的深度为O(log)。
时间效率：快速排序的运行时间于划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1 个元素和0个元素时，这种最大限度的不对称性xxx发生在每层递归上，xxx对应于初始排序表基本有序或记恨逆序时，就得到最坏情况下的时间复杂度为O()。
有很多方法可以提高算法的效率:一种方法是尽量选取一个可以将数据中分的枢轴元素，xxx从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可是得最坏情况在实际排序中几乎不会发生。
在最理想的状态下，xxxPartition()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2,在这种情况下的，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog)。好在快速排序平均情况下运行时间与其最佳情况下的运行时间很接近，而不是接近最坏情况下的运行时间。快速排序是所有的内部排序算法中平均性能最优的排序算法。
稳定性： 在划分算法中，xxx右端区间有两个关键字相同，且均下雨基准的记录，xxx在交换到左端区间后，它们的相对位置就会发生变化，xxx快速排序是一种不稳地的排序方法。例如表L={3,2,2}经过一趟排序后L={2,2,3},最终排序序列也是L={2,2,3},显然，2与2的相对次序发生了变化。
注意：在快速排序算法中，并不产生有序子序列，但没每趟排序后会将枢轴（基准）元素方法其最终的位置上。
选择排序的基本思想是：每一趟（如第i趟）在后面n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。
根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：假设排序表为L[1...n],第i趟排序xxx从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得真个排序表有序。
简单选择排序算法的代码如下：
简单选择排序算法的性能分析如下：
空间效率：仅使用常数个辅助单元，故空间效率为O(1);
时间效率:从上述伪代码中不难看出，在简单选择排序的过程中，元素移动的操作次数很少，不会超过3（n-1）次，最好的情况下是移动0次，此时对应的表已经有序；但元素比较的次数与序列的初始状态无关，始终是n(n-1)/2次，因此时间复杂度始终是O()。
稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变，例如，表L={2,2,1},经过一趟排序后L={1,2,2},最终排序序列也是L={1,2,2},显示，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。
堆的定义如下，n个关键字序列L[1...n]成为堆，当且仅当该序列满足：
1. L(i)>=L(2i)且L(i)>(2i+1)或
2. L(i)<=L(2i)且L(i)<=L(2i+1) (1<=i<=)
可以将该一维数组视为一颗完全二叉树，满足条件1的成为大根堆（大顶堆），大根堆的最大元素存放在根节点，且其任一非根节点的值小于等于其双亲结点值。满足条件2的推成为小根堆（小顶堆），小根堆的定义刚好相反，根节点是最小元素。该图所示就是一个大根堆：
堆排序的思路很简单：首先将存放在L[1...n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆低元素送入堆顶。此时根节点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：
1，如何将无序序列构造成初始堆？
2.输出堆顶元素后，如何将剩余元素调整成新的堆？
堆排序的关键是构造初始堆。n个节点的完全二叉树，最后一个节点是第个节点的孩子。对第个节点为根的子树筛选（对于大根堆，xxx根节点的关键字小于左右孩子中关键字较大者，xxx交换），使该子树成为堆。之后向前依次对各个节点（-1~1）为根的子树进行筛选，看该节点值是否大于其左右子节点的值，xxx不大于，xxx将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整对的方法建堆，直到根结点。
如图所示，初始时调整L(4)子树，09<32,交换，交换，交换后满足堆的定义；向前继续调整L(3)子树，78<左右孩子的较大者87，交换，交换后满足堆的定义；向前调整L(2)子树，17<左右孩子的较大者45，交换后满足堆的定义；向前调整至根结点L(1),53<左右孩子的较大者87，交换，交换后破坏了L(3)子树的推，采用上述方法对L(3)进行调整，53<左右孩子的较大者78，交换，至此该完全二叉树满足堆的定义。
输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将09和左右孩子的较大者78交换，交换后破坏了L(3)子树的堆，继续堆L(3)子树向下筛选，将09和左右孩子大的较大者65交换，交换后得到了新堆，调整过程如图所示。
下面是建立大根堆的算法：
调整的时间与树高有关，为O(h)。在建含n个元素的堆时，关键字的比较总次数不超过4n,时间复杂度为O(n),这说明在线性时间内将一个无序数组建成一个堆。
下面是堆排序算法：
同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作如图所示：
堆排序适合关键字较多的情况，例如，在1亿个数中选出前100个最大值？首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，xxx小于堆顶xxx舍弃，否xxx用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数xxx为所求。
堆排序算法的性能分析如下：
空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1);
时间效率：建堆时间为O(n),之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),故在最好，最坏和平均情况下，堆排序的时间复杂度为O(n)。
稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序算法。例如，表L={1,2,2},构造初始堆时可能将2交换到堆顶，此时L={2,1,2},最总排序序列为L={1,2,2},显然，2与2的相对次序已发生变化。
数据结构知识点总结 第8篇
算法目的：确定主串中所含子串第一次出现的位置（定位）
定位问题称为串的模式匹配，典型函数为Index(S,T,pos)
BF算法的实现—xxx编写Index(S, T, pos)函数
BF算法设计思想：
将主串S的第pos个字符和模式T的第1个字符比较，
xxx相等，继续逐个比较后续字符；
xxx不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列
第一个字符的序号，xxx匹配成功。
否xxx，匹配失败，返回值 0。
Int Index_BP(SString S, SString T, int pos)
{ //xxx串T在主串S中第pos个字符之后的位置。xxx不存在，xxx函数值为0.
// 其中，T非空，1≤pos≤StrLength(S)
i=pos; j=1;
while ( i<=S[0] && j<=T[0] ) //xxx,j二指针在正常长度范围，
{
if (S[i] = = T[j] ) {++i, ++j; } //xxx继续比较后续字符
else {i=i-j+2; j=1;} //xxx不相等，指针后退重新开始匹配
}
if(j>T[0]) return i-T[0]; //T子串指针j正常到尾，说明匹配成功， else return 0; //
否xxx属于i>S[0]情况，i先到尾就不正常
} //Index_BP
数据结构知识点总结 第9篇
1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，
链表中结点个数等于一行中非零元素的个数。
2. 区别：
对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），
但邻接表不唯一（链接次序与顶点编号无关）。
3. 用途：
邻接矩阵多用于稠密图的存储
而邻接表多用于稀疏图的存储
数据结构知识点总结 第10篇
既然子表有序且为顺序存储结构，xxx插入时采用折半查找定可加速。
优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。
时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。
空间效率：仍为 O（1）
稳 定 性： 稳定
xxx记录是链表结构，用直接插入排序行否？
答：行，而且无需移动元素，时间效率更高！
但请注意：单链表结构无法实现“折半查找”
数据结构知识点总结 第11篇
特点：表结构在查找过程中动态生成。
要求：对于给定值key, xxx表中存在其关键字等于key的记录，xxx查找成功返回；否xxx插入
关键字等于key 的记录。
① 二叉排序树的定义
----或是一棵空树；或者是具有如下性质的非空二叉树：
（1）xxx的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值；
（3）它的左右子树也分别为二叉排序树。
② 二叉排序树的插入与删除
思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功xxx返回。
SearchBST (K, &t) { //K为待查关键字，t为根结点指针
p=t; //p为查找过程中进行扫描的指针
while（p!=NULL）{
case {
K= p->data: {查找成功，return }
K< p->data : {q=p；p=p->L_child } //继续向xxx
K> p->data : {q=p；p=p->R_child } //继续向右搜索
}
} //查找不成功xxx插入到二叉排序树中
s =(BiTree)malloc(sizeof(BiTNode));
s->data=K; s ->L_child=NULL; s ->R_child=NULL;
//查找不成功，生成一个新结点s，插入到二叉排序树叶子处
case {
t=NULL： t=s; //xxxt为空，xxx插入的结点s作为根结点
K < q->data: q->L_child=s; //xxxK比叶子小，挂左边
K > q->data: q->R_child=s; //xxxK比叶子大，挂右边
}
return OK
③ 二叉排序树的删除操作如何实现？
如何删除一个结点？
假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针；
*f表示*p的双亲结点指针；并假定*p是*f的左孩子；xxx可能有三种情况：
*p有两棵子树时，如何进行删除操作？
设删除前的中序遍历序列为：…. PL s p PR f
//xxx的直接前驱是s ，s是*pxxx最右下方的结点
希望删除p后，其它元素的相对位置不变。有两种解决方法：
法1：令*p的xxx为 *f的xxx，*p的右子树接为*s的右子树； //xxx fL=PL ;
SR=PR ;
法2：直接令*s代替*p // *s为*pxxx最右下方的结点
二叉排序树的
④ 平衡二叉树的定义：又称AVL树，xxx它或者是一颗空树，或者是它的xxx和右子树都
是平衡二叉树，且xxx与右子树的深度之差的绝对值不超过1。
平衡因子：——该结点的xxx的深度减去它的右子树的深度。
平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，
使之恢复平衡。我们称调整平衡过程为平衡旋转。
平衡旋转可以归纳为四类：
数据结构知识点总结 第12篇
C/C++编程学习基地_wv=1027&k=52AMV0JN
本文链接：
关于我们 | 我要投稿 | 免责申明
Copyright © 2020-2022 Rights Reserved.豫ICP备2022013469号-1
数据结构知识点总结 第13篇
（下标从一开始）
算法步骤:
初始化距离: dis[i] = ，dis[1] = 0；
for i : 1 ~ n // xxx n 个节点，每次找到距源点 s 距离最短的节点
for v : 1 ~ n
t <= 不在 s 中的距离源点最近的点
if (t == n) break; // 提前到 n 节点
st <= t
for v : 1 ~ n
用 t 更新其它点的距离：dis[j] = min(dis[j], dis[t] + g[t][j])
初始化距离数组dis为INF（0x3f），并置dis[s] = 0。
将源点加入队列，并标记该节点在队列中。
当队列不空时，取队头元素进行拓展(遍历邻接表),将从源点拓展出去的距离更小的节点加入队列（首先拓展节点不在队列中）。
SPFA判断负环
dis[x] 表示 单源点s 到 x 的最短距离 dis[x] = dis[t] + w[i]
cnt[x] 表示 从 s 到 x 经过的边数 cnt[x] = cnt[t] + 1
xxxcnt[x] >= n xxx表示存在负环 n 表示总节点数
Bellman-Ford算法（可带负权边，解决有边数限制的最短路 Onm）（了解xxx可）
for 所有节点（或者题目中所要求的限制次数）
//备份dis
for 所有边 a，b，w
dis[b] = min(dis[b], dis[a] + w); // 松弛操作
初始化 dis 为INF
for i : 0 - n
t <= 找到集合外距离最近的点（该点与集合内所有有连通边中最短的边）
用 t 更新其他点到集合的距离
st[t] = true // 把 t 加到集合中去
注意：因为初始化未加入任意节点，所以需要遍历 n 次。
Kruskal算法（稀疏图 O mlogm）
将所有边按权重从小到大排序（快排）
xxx每条边 a，b，权重 c
if a,b不连通
将这条边加入集合中
（当且仅当图中不含奇数环（自己到自己的边数量为奇数））
数据结构知识点总结 第14篇
指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。
遍历规xxx———
二叉树由根、xxx、右子树构成，定义为D、 L、R
xxx限定先左后右，xxx有三种实现方案：
DLR LDR LRD
先序遍历 中序遍历 后序遍历
