数据结构重要知识点总结 第1篇
回顾2：二叉树怎样还原为树？
要点：逆操作，把所有右孩子变为兄弟！
讨论1：森林如何转为二叉树？
法一：① 各森林先各自转为二叉树；② 依次连到前一个二叉树的右子树上。
法二：森林直接变兄弟，再转为二叉树
讨论2：二叉树如何还原为森林？
要点：把最右边的子树变为森林，其余右子树变为兄弟
数据结构重要知识点总结 第2篇
用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z）,请写出C语言程序。
#include
#include
typedef struct node{
char data;
struct node *next;
}node;
node *p,*q,*head; //一般需要3个指针变量
int n ; // 数据元素的个数
int m=sizeof(node); /*结构类型定义好之后，每个node类型的长度就固定了，
m求一次即可*/
void build( ) //字母链表的生成。要一个个慢慢链入
int i;
head=(node*)malloc(m); //m=sizeof(node) 前面已求出
p=head;
for( i=1; i<26; i++) //因尾结点要特殊处理，故i≠26
p->data=i+‘a’-1; // 第一个结点值为字符a
p->next=(node*)malloc(m); //为后继结点“挖坑”！
p=p->next；} //让指针变量P指向后一个结点
p->data=i+‘a’-1; //最后一个元素要单独处理
p->next=NULL ; //单链表尾结点的指针域要置空！
void display() //字母链表的输出
p=head;
while (p) //当指针不空时循环（仅限于无头结点的情况）
printf(_%c_,p->data);
p=p->next; //让指针不断“顺藤摸瓜”
（2）单链表的修改(或读取）
思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，
然后才能：p>data=new_value
读取第i个数据元素的核心语句是：
Linklist *find(Linklist *head ,int i)
int j=1;
Linklist *p;
P=head->next;
While((p!=NULL)&&(j
p=p->next;
j++;
return p;
单链表的插入
链表插入的核心语句：
Step 1：s->next=p->next;
Step 2：p->next=s ；
6.单链表的删除
删除动作的核心语句（要借助辅助指针变量q）：
q = p->next; //首先保存b的指针，靠它才能找到c；
p->next=q->next; //将a、c两结点相连，淘汰b结点；
free(q) ； //彻底释放b结点空间
7.双向链表的插入操作：
设p已指向第 i 元素，请在第 i 元素前插入元素 x：
① ai-1的后继从 ai ( 指针是p)变为 x（指针是s) :
s->next = p ; p->prior->next = s ;
② ai 的前驱从 ai-1 ( 指针是p->prior)变为 x ( 指针是s);
s->prior = p ->prior ; p->prior = s ;
8.双向链表的删除操作：
设p指向第 i 个元素，删除第 i 个 元素
后继方向：ai-1的后继由 ai ( 指针p)变为 ai+1(指针 p ->next );
p ->prior->next = p->next ;
前驱方向：ai+1的前驱由 ai ( 指针p)变为ai-1 (指针 p -> prior );
p->next->prior = p ->prior ;
数据结构重要知识点总结 第3篇
技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。
int Search_Seq( SSTable ST , KeyType key ){
[0].key =key;
for( i=; [ i ].key!=key; - - i );
return i;
} // Search_Seq
//ASL＝（1＋n）/2，时间效率为 O(n)，这是查找成功的情况:
顺序查找的特点：
优点：算法简单，且对顺序结构或链表结构均适用。
缺点： ASL 太大，时间效率太低。
二、折半查找（二分或对分查找）
若关键字不在表中，怎样得知并及时停止查找？
典型标志是：当查找范围的上界≤下界时停止查找。
ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以：
m
1n+1
å
j-1
ASL=j×2=log(n+1)-1»logn
nn
j=1
数据结构重要知识点总结 第4篇
设p指向第 i 个元素，删除第 i 个 元素
后继方向：ai-1的后继由 ai ( 指针p)变为 ai+1(指针 p ->next );
p ->prior->next = p->next ;
前驱方向：ai+1的前驱由 ai ( 指针p)变为ai-1 (指针 p -> prior );
p->next->prior = p ->prior ;
数据结构重要知识点总结 第5篇
选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。
1）简单选择排序
思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。
优点：实现简单
缺点：每趟只能确定一个元素，表长为n时需要n-1趟
前提：顺序存储结构
Void SelectSort(SqList &L ) {
for (i=1; i
j = SelectMinKey(L,i);
if( i!=j ) r[i] «r[j];
} //for
} //SelectSort
2）锦标赛排序 (又称树形选择排序)
基本思想：与体育比赛时的淘汰赛类似。
首先对 n 个记录的关键字进行两两比较，得到 én/2ù 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 én/2ù 个较小者之间再进行两两比较，…，如此重复，直到选出最小关键字的记录为止。
优点：减少比较次数，加快排序速度
缺点：空间效率低
3）堆排序
1.堆的定义：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。
解释：如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。
2. 怎样建堆？
步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。
数据结构重要知识点总结 第6篇
时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。
其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2)
空间效率：仅占用1个缓冲单元——O（1）
算法的稳定性：因为25*排序后仍然在25的后面——稳定
直接插入排序算法的实现：
void InsertSort ( SqList &L ) { //对顺序表L作直接插入排序
for ( i = 2; i <=; i++) //假定第一个记录有序
{ [0]= [i];
j=i-1 ; //先将待插入的元素放入“哨兵”位置
while（L[0] .key
{ [j+1]= [j];
j-- ; } //只要子表元素比哨兵大就不断后移
[j+1]= [0]; //直到子表元素小于哨兵，将哨兵值送入
//当前要插入的位置（包括插入到表首）
2） 折半插入排序
既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。
优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。
时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。
空间效率：仍为 O（1）
稳 定 性： 稳定
若记录是链表结构，用直接插入排序行否？
答：行，而且无需移动元素，时间效率更高！
但请注意：单链表结构无法实现“折半查找”
3） 表插入排序
基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。
优点：在排序过程中不移动元素，只修改指针。
此方法具有链表排序和地址排序的特点
表插入排序算法分析：
① 无需移动记录，只需修改指针值。但由于比较次数没有减少，故时间效率仍为O(n2) 。
② 空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。
③ 稳定性：25和25*排序前后次序未变，稳定。
注：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。
5）希尔（shell）排序
基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。
数据结构重要知识点总结 第7篇
数据结构的基本运算：修改、插入、删除、查找、排序
1) 修改——通过数组的下标便可访问某个特定元素并修改之。
核心语句: V[i]=x;
顺序表修改操作的时间效率是 O(1)
2) 插入——在线性表的第i个位置前插入一个元素
实现步骤：
①将第n至第i 位的元素向后移动一个位置；
②将要插入的元素写到第i个位置；
③表长加1。
注意：事先应判断: 插入位置i 是否合法?表是否已满?
应当符合条件： 1≤i≤n+1 或 i=[1, n+1]
核心语句：
for (j=n; j>=i; j--)
a[j+1]=a[ j ];
a[ i ]=x;
n++;
数据结构重要知识点总结 第8篇
思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小
者放到r[2]位置；…如此进行下去，直到全部有序为止。
优点：实现简单
缺点：每趟只能确定一个元素，表长为n时需要n-1趟
前提：顺序存储结构
数据结构重要知识点总结 第9篇
相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。
不同点：① 运算规则不同：
线性表为随机存取；
而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；
队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。
数据结构重要知识点总结 第10篇
结点类型定义：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一结点的指针
}Qnode , * QueuePtr ;
链队列类型定义：
typedef struct {
QueuePtr front ; //队首指针
QueuePtr rear ; //队尾指针
} LinkQueue;
数据结构重要知识点总结 第11篇
特点：表结构在查找过程中动态生成。
要求：对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key 的记录。
① 二叉排序树的定义
----或是一棵空树；或者是具有如下性质的非空二叉树：
（1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值；
（3）它的左右子树也分别为二叉排序树。
② 二叉排序树的插入与删除
思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。
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 } //继续向左搜索
K> p->data : {q=p；p=p->R_child } //继续向右搜索
} //查找不成功则插入到二叉排序树中
s =(BiTree)malloc(sizeof(BiTNode));
s->data=K; s ->L_child=NULL; s ->R_child=NULL;
//查找不成功，生成一个新结点s，插入到二叉排序树叶子处
case {
t=NULL： t=s; //若t为空，则插入的结点s作为根结点
K < q->data: q->L_child=s; //若K比叶子小，挂左边
K > q->data: q->R_child=s; //若K比叶子大，挂右边
return OK
③ 二叉排序树的删除操作如何实现？
如何删除一个结点？
假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针；
*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：
*p有两棵子树时，如何进行删除操作？
设删除前的中序遍历序列为：…. PL s p PR f
//显然p的直接前驱是s ，s是*p左子树最右下方的结点
希望删除p后，其它元素的相对位置不变。有两种解决方法：
法1：令*p的左子树为 *f的左子树，*p的右子树接为*s的右子树； //即 fL=PL ; SR=PR ;
法2：直接令*s代替*p // *s为*p左子树最右下方的结点
二叉排序树的
④ 平衡二叉树的定义：又称AVL树，即它或者是一颗空树，或者是它的左子树和右子树都是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。
平衡因子：——该结点的左子树的深度减去它的右子树的深度。
平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。
平衡旋转可以归纳为四类：
数据结构重要知识点总结 第12篇
基本思想：与体育比赛时的淘汰赛类似。
首先对 n 个记录的关键字进行两两比较，得到 n/2 个优胜者(关键字小者)，作为
第一步比较的结果保留下来。然后在这 n/2 个较小者之间再进行两两比较，…，如此
重复，直到选出最小关键字的记录为止。
优点：减少比较次数，加快排序速度
缺点：空间效率低
数据结构重要知识点总结 第13篇
一、顺序存储结构
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。
若是完全/满二叉树则可以做到唯一复原。
不是完全二叉树：一律转为完全二叉树！
方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。
缺点：①浪费空间；②插入、删除不便
二、链式存储结构
用二叉链表即可方便表示。一般从根结点开始存储。
优点：①不浪费空间；②插入、删除方便
数据结构重要知识点总结 第14篇
思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的
数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要
包含每个子表的起始地址（即头指针）。
特点：块间有序，块内无序。
查找：块间折半，块内线性
查找步骤分两步进行：
① 对索引表使用折半查找法（因为索引表是有序表）；
② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
查找效率ASL分析：
数据结构重要知识点总结 第15篇
队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
链队列
结点类型定义：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一结点的指针
}Qnode , * QueuePtr ;
链队列类型定义：
typedef struct {
QueuePtr front ; //队首指针
QueuePtr rear ; //队尾指针
} LinkQueue;
链队示意图：
① 空链队的特征：front=rear
② 链队会满吗？一般不会，因为删除时有free动作。除非内存不足！
③ 入队（尾部插入）：rear->next=S; rear=S;
出队（头部删除）：front->next=p->next;
2.顺序队
顺序队类型定义：
#define QUEUE-MAXSIZE 100 //最大队列长度
typedef struct {
QElemType *base; //队列的基址
int front; //队首指针
int rear; //队尾指针
}SqQueue
建队核心语句：
q . base=(QElemType *)malloc(sizeof (QElemType ）
* QUEUE_MAXSIZE; //分配空间
顺序队示意图：
循环队列：
队空条件 : front = rear (初始化时：front = rear )
队满条件： front = (rear+1) % N (N=maxsize)
队列长度（即数据元素个数）：L=（N＋rear－front）% N
1）初始化一个空队列
Status InitQueue ( SqQueue &q ) //初始化空循环队列 q
q . base=(QElemType *)malloc(sizeof(QElemType）
* QUEUE_MAXSIZE); //分配空间
if (!) exit(OVERFLOW);//内存分配失败，退出程序
=; //置空队列
return OK;
} //InitQueue;
2）入队操作
Status EnQueue(SqQueue &q, QElemType e)
{//向循环队列 q 的队尾加入一个元素 e
if ( () % QUEUE_MAXSIZE = = )
return ERROR ; //队满则上溢，无法再入队
= ( q . rear + 1 ) % QUEUE_MAXSIZE;
[ ] = e; //新元素e入队
return OK;
}// EnQueue;
3）出队操作
Status DeQueue ( SqQueue &q, QElemType &e)
{//若队列不空，删除循环队列q的队头元素，
//由 e 返回其值，并返回OK
if ( = = ) return ERROR;//队列空
() % QUEUE_MAXSIZE ;
e = [ ] ;
return OK;
}// DeQueue
数据结构重要知识点总结 第16篇
求MST最常用的是以下两种：Kruskal（克鲁斯卡尔）算法、Prim（普里姆）算法
Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。
Prime算法特点: 将顶点归并，与边数无关，适于稠密网。
在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
两种常见的最短路径问题：
一、 单源最短路径—用Dijkstra（迪杰斯特拉）算法
二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法
一、单源最短路径 (Dijkstra算法)一顶点到其余各顶点（v0→j）
目的： 设一有向图G=（V, E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。
二、所有顶点之间的最短路径
可以通过调用n次Dijkstra算法来完成，还有更简单的一个算法：Floyd算法（自学）。
学习重点： 图是应用最广泛的一种数据结构，本章也是这门课程的重点。
数据结构重要知识点总结 第17篇
插入元素到栈顶的操作，称为入栈。
从栈顶删除最后一个元素的操作，称为出栈。
对于向上生成的堆栈:
入栈口诀：堆栈指针top “先压后加” : S[top++]=an+1
出栈口诀：堆栈指针top “先减后弹” : e=S[--top]
◆ 栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。
顺序栈入栈函数PUSH（）
status Push(ElemType e)
{ if(top>M){上溢}
else s[top++]=e;
顺序栈出栈函数POP()
status Pop( )
{ if(top=L) { 下溢 }
else { e=s[--top]; return(e);}
数据结构重要知识点总结 第18篇
Huffman树：最优二叉树（带权路径长度最短的树）
Huffman编码：不等长编码。
树的带权路径长度： （树中所有叶子结点的带权路径长度之和）
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。
构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即
森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉
树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。
数据结构重要知识点总结 第19篇
对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法
先选定一个整数，把待排序文件中的所有记录分成若干个组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行排序，然后重复上述分组和排序的工 作。当到达 gap=1 时，所有记录在统一组内排好序。
最初希尔提出的增量是 gap=n/2，每一次排序完让增量减少一半 gap/=2，直到 gap=1 时，排序相当于直接插入排序。
后来有人提出了 gap=(gap/3)+1，每次排序让增量成为原来的 1/3，+1 是防止 gap<=3 时 gap/=3 结果为 0 情况的发生，导致 gap 最后不为 1，无法完成插入排序
选择 gap=(gap/3)+1 更稳定，能够尽可能地减少比较和交换的次数，以提高排序的效率。通过采用这种递减的方式，可以更好地分组元素，使得在每一轮排序中能够更快地将较小的元素移动到前面。序列被划分为较小的子序列，并通过插入排序的方式对每个子序列进行排序。这样做的好处是在初始阶段，较大的元素可以更快地向后移动，从而减少了后续比较和交换的次数。
当 gap>1 时都是预排序，目的是让数组更接近于有序。当 gap==1 时，数组已经接近有序了，相当于直接插入，这样就会很快
希尔排序的时间复杂度并不好计算，因为 gap 的取值方法很多，官方给出的时间复杂度是 O(N^)
选择排序的最好情况的时间复杂度为 n+(n-2)+(n-4)+...（优化后的做法：同时找 max 和 min）相当于 n²，最坏情况和平均情况时间复杂度都为 O(n²)
空间复杂度为 O(1) ，是一种原地排序算法
是一种不稳定的排序算法，比如：4，9，4，1，8，第一次找到最小元素 1 ，与第一个 4 交换位置，那第一个 4 和中间的 4 顺序就变了
通过堆来进行选择数据
一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作
最好情况下，要排序的数据已经是有序的了，只需要进行一次冒泡操作就可以结束 了，所以最好情况时间复杂度是 O(n)。而最坏的情况下，要排序的数据刚好是倒序排列的，需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以空间复杂度为 O(1) ，是一个原地排序算法
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法
在相对有序的情况下，选择插入排序更好。比如 1 2 3 5 4 6 这个排序，冒泡排序需要 ((N-1)+(N-2)) 比较（因为冒泡排序排好后，还需要再排多一次，才能确定排好序了），插入排序需要 N 次比较。
分治思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
快速排序是一种二叉树结构的交换排序方法
快排的处理过程是由上到下 的，先分区，然后再处理子问题
时间复杂度：O(NlogN)，空间复杂度：O(logN)
快排在有序的情况下时间复杂度最坏：n+(n-1)+(n-2)+... 时间复杂度为 O(n²)，空间复杂度为 O(n)。
快速排序优化：三数取中法
选出一个关键字 key，一般是头 / 尾。经过一次单趟后，key 放到了正确的位置，key 左边的值比 key 小，key 右边的值比 key 大。再让 key 的左边区间有序、key 的右边区间有序。
这个算法右边先走可以保证相遇位置小于 key。
当快速排序递归到较小区间时，可以切换到插入排序，这样可以减少递归调用的次数，降低开销，并利用插入排序的优势来提高整体性能
递归在极端场景下，如果栈帧深度太深，栈空间不够用，会出现栈溢出
递归改成非递归一般有 2 种方法
快排的非递归是在模拟递归的过程，所以时间复杂度并没有本质的变化，但可以减少栈空间的开销
快速排序整体的综合性能和使用场景都比较好，所以才敢叫快速排序
将已有序的子序列合并，得到完全有序的序列：先使每个子序列有序，再使子序列段间有序
执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好 / 最坏 / 平均情况，时间复杂度都是 O(nlogn)
尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用，临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)
是一个稳定的排序算法
又称为鸽巢原理，是对哈希直接定址法的变形应用
1、统计相同元素的出现次数
2、根据统计的结果将序列回收到原来的序列中
数据结构重要知识点总结 第20篇
顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。
链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。
◆ 顺序表适宜于做查找这样的静态操作；
◆ 链表宜于做插入、删除这样的动态操作。
◆ 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
◆ 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
数据结构重要知识点总结 第21篇
基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列
中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时
间效率会高很多。
数据结构重要知识点总结 第22篇
性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）。
性质2: 深度为k的二叉树至多有2k-1个结点（k>0）。
性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1
性质4: 具有n个结点的完全二叉树的深度必为 ë
性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。
数据结构重要知识点总结 第23篇
数据结构的形式定义为：数据结构是一个二元组
Data Structure=()
其中：D 是数据元素的有限集，S 是 D 上关系的有限集
其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取
其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间
其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销
数据结构重要知识点总结 第24篇
算法目的：确定主串中所含子串第一次出现的位置（定位）
定位问题称为串的模式匹配，典型函数为Index(S,T,pos)
BF算法的实现—即编写Index(S, T, pos)函数
BF算法设计思想：
将主串S的第pos个字符和模式T的第1个字符比较，
若相等，继续逐个比较后续字符；
若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0。
Int Index_BP(SString S, SString T, int pos)
{ //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
// 其中，T非空，1≤pos≤StrLength(S)
i=pos; j=1;
while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围，
if (S[i] = = T[j] ) {++i, ++j; } //则继续比较后续字符
else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配
if(j>T[0]) return i-T[0]; //T子串指针j正常到尾，说明匹配成功， else return 0; //否则属于i>S[0]情况，i先到尾就不正常
} //Index_BP
数据结构重要知识点总结 第25篇
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。
② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。
讨论：树若采用“先转换，后遍历”方式，结果是否一样？
1. 树的先根遍历与二叉树的先序遍历相同；
2. 树的后根遍历相当于二叉树的中序遍历；
3. 树没有中序遍历，因为子树无左右之分。
① 先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先根遍历第一棵树的根结点的子树森林；
先根遍历除去第一棵树之后剩余的树构成的森林。
② 中序遍历
若森林为空，返回；
中根遍历森林中第一棵树的根结点的子树森林；
访问第一棵树的根结点；
中根遍历除去第一棵树之后剩余的树构成的森林。
数据结构重要知识点总结 第26篇
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
静态顺序表只适用于确定知道需要存多少数据的场景。
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。所以创建链表和销毁链表需要二级指针或者一级指针引用。plist 是指向第一个节点的指针，想要在函数中改变 plist 的值（指向），必须要把 plist 指针的地址作为实参传过去，形参用二级指针接收，这样在函数中对二级指针解引用得到 plist 的值，就可以改变 plist 的值（指向）了
单链表不适合在 pos 位置之前插入元素，因为需要遍历链表找到 pos 位置的前一个节点，时间复杂度为 O(N)。
单链表更适合在 pos 位置之后插入，如果在后面插入，只需要知道 pos 位置即可。
C++ 官方库里面的单链表也是在之后插入。
删除 pos 位置同样需要传入单链表的二级指针。
因为需要遍历链表找到 pos 位置的前一个节点，以改变其指向，时间复杂度大。
栈&队列（重点）
队列内有效长度为：(rear - front + N) % N 这里加上数组长度起到类似绝对值的作用
数据结构重要知识点总结 第27篇
意味着malloc 返回一个指向 void 类型的指针，（ElemType) 是一个类型转换，它将 malloc 返回的 void 指针转换为 ElemType* 类型的指针，ElemType 是一个通用类型名称或抽象名称
插入是 e = [i - 1]，删除是 [i - 1] = e
插入是 j = ; j >= i; j–，删除是 j = i; j < ; j++
插入是（后移） [j] = [j - 1]，删除是（前移） [j - 1] = [j]
头结点和头指针的区别：不管带不带头结点，头指针始终指向链表的第一个结点；而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息
数据结构重要知识点总结 第28篇
Status EnQueue(SqQueue &q, QElemType e)
{//向循环队列 q 的队尾加入一个元素 e
if ( () % QUEUE_MAXSIZE = = )
return ERROR ; //队满则上溢，无法再入队
= ( q . rear + 1 ) % QUEUE_MAXSIZE;
[ ] = e; //新元素e入队
return OK;
}// EnQueue;
数据结构重要知识点总结 第29篇
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。
② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。
讨论：树若采用“先转换，后遍历”方式，结果是否一样？
1. 树的先根遍历与二叉树的先序遍历相同；
2. 树的后根遍历相当于二叉树的中序遍历；
3. 树没有中序遍历，因为子树无左右之分。
① 先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先根遍历第一棵树的根结点的子树森林；
先根遍历除去第一棵树之后剩余的树构成的森林。
② 中序遍历
若森林为空，返回；
中根遍历森林中第一棵树的根结点的子树森林；
访问第一棵树的根结点；
中根遍历除去第一棵树之后剩余的树构成的森林。
数据结构重要知识点总结 第30篇
基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律
前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素
并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。
优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！
前提：顺序存储结构
时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加
空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot)
稳 定 性： 不 稳 定 —因为有跳跃式交换。
数据结构重要知识点总结 第31篇
Huffman树：最优二叉树（带权路径长度最短的树）
Huffman编码：不等长编码。
树的带权路径长度：（树中所有叶子结点的带权路径长度之和）
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。
构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。
数据结构重要知识点总结 第32篇
基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一
旦下趟没有交换发生，还可以提前结束排序。
前提：顺序存储结构
冒泡排序的算法分析：
时间效率：O（n2) —因为要考虑最坏情况
空间效率：O（1） —只在交换时用到一个缓冲单元
稳 定 性： 稳定 —25和25*在排序前后的次序未改变
冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表
尾），还可以对前面的元素作一些整理，所以比一般的排序要快。
数据结构重要知识点总结 第33篇
3) 删除——删除线性表的第i个位置上的元素
实现步骤：
①将第i+1 至第n 位的元素向前移动一个位置；
②表长减1。
注意：事先需要判断，删除位置i 是否合法?
应当符合条件：1≤i≤n 或 i=[1, n]
核心语句：
for ( j=i+1; j<=n; j++ )
a[j-1]=a[j];
n--;
顺序表删除一元素的时间效率为:T（n)=(n-1)/2 ≈O(n)
顺序表插入、删除算法的平均空间复杂度为O(1)
数据结构重要知识点总结 第34篇
深度优先搜索（遍历）步骤：
① 访问起始点 v;
② 若v的第1个邻接点没访问过，深度遍历此邻接点；
③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。
基本思想：——仿树的先序遍历过程。
广度优先搜索（遍历）步骤：
① 在访问了起始点v之后，依次访问 v的邻接点；
② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；
③ 直到所有顶点都被访问过为止。
数据结构重要知识点总结 第35篇
1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，
链表中结点个数等于一行中非零元素的个数。
2. 区别：
对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），
但邻接表不唯一（链接次序与顶点编号无关）。
3. 用途：
邻接矩阵多用于稠密图的存储
而邻接表多用于稀疏图的存储
数据结构重要知识点总结 第36篇
树：由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1
时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是
棵树，被称作这个根的子树 。
二叉树：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左
子树和右子树的二叉树组成。
术语：P88
数据结构重要知识点总结 第37篇
深度优先搜索（遍历）步骤：
① 访问起始点 v;
② 若v的第1个邻接点没访问过，深度遍历此邻接点；
③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。
基本思想：——仿树的先序遍历过程。
广度优先搜索（遍历）步骤：
① 在访问了起始点v之后，依次访问 v的邻接点；
② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；
③ 直到所有顶点都被访问过为止。
数据结构重要知识点总结 第38篇
一、顺序存储结构
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。
若是完全/满二叉树则可以做到唯一复原。
不是完全二叉树：一律转为完全二叉树！
方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。
缺点：①浪费空间；②插入、删除不便
二、链式存储结构
用二叉链表即可方便表示。一般从根结点开始存储。
优点：①不浪费空间；②插入、删除方便
数据结构重要知识点总结 第39篇
基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐
个修改为已经整理（排序）过的后继记录地址。
优点：在排序过程中不移动元素，只修改指针。
此方法具有链表排序和地址排序的特点
表插入排序算法分析：
① 无需移动记录，只需修改指针值。但由于比较次数没有减少，故时间效率仍为O(n2) 。
② 空间效率肯定低，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。
③ 稳定性：25和25*排序前后次序未变，稳定。
注：此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。
数据结构重要知识点总结 第40篇
特点：表结构在查找过程中动态生成。
要求：对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回；否则插入
关键字等于key 的记录。
① 二叉排序树的定义
----或是一棵空树；或者是具有如下性质的非空二叉树：
（1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值；
（3）它的左右子树也分别为二叉排序树。
② 二叉排序树的插入与删除
思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。
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 } //继续向左搜索
K> p->data : {q=p；p=p->R_child } //继续向右搜索
}
} //查找不成功则插入到二叉排序树中
s =(BiTree)malloc(sizeof(BiTNode));
s->data=K; s ->L_child=NULL; s ->R_child=NULL;
//查找不成功，生成一个新结点s，插入到二叉排序树叶子处
case {
t=NULL： t=s; //若t为空，则插入的结点s作为根结点
K < q->data: q->L_child=s; //若K比叶子小，挂左边
K > q->data: q->R_child=s; //若K比叶子大，挂右边
}
return OK
③ 二叉排序树的删除操作如何实现？
如何删除一个结点？
假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针；
*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：
*p有两棵子树时，如何进行删除操作？
设删除前的中序遍历序列为：…. PL s p PR f
//显然p的直接前驱是s ，s是*p左子树最右下方的结点
希望删除p后，其它元素的相对位置不变。有两种解决方法：
法1：令*p的左子树为 *f的左子树，*p的右子树接为*s的右子树； //即 fL=PL ;
SR=PR ;
法2：直接令*s代替*p // *s为*p左子树最右下方的结点
二叉排序树的
④ 平衡二叉树的定义：又称AVL树，即它或者是一颗空树，或者是它的左子树和右子树都
是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。
平衡因子：——该结点的左子树的深度减去它的右子树的深度。
平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，
使之恢复平衡。我们称调整平衡过程为平衡旋转。
平衡旋转可以归纳为四类：
数据结构重要知识点总结 第41篇
3) 删除——删除线性表的第i个位置上的元素
实现步骤：
①将第i+1 至第n 位的元素向前移动一个位置；
②表长减1。
注意：事先需要判断，删除位置i 是否合法?
应当符合条件：1≤i≤n 或 i=[1, n]
核心语句：
for ( j=i+1; j<=n; j++ )
a[j-1]=a[j];
n--;
顺序表删除一元素的时间效率为:T（n)=(n-1)/2 ≈O(n)
顺序表插入、删除算法的平均空间复杂度为O(1)
数据结构重要知识点总结 第42篇
Status DeQueue ( SqQueue &q, QElemType &e)
{//若队列不空，删除循环队列q的队头元素，
//由 e 返回其值，并返回OK
if ( = = ) return ERROR;//队列空
() % QUEUE_MAXSIZE ;
e = [ ] ;
return OK;
}// DeQueue
数据结构重要知识点总结 第43篇
算法目的：确定主串中所含子串第一次出现的位置（定位）
定位问题称为串的模式匹配，典型函数为Index(S,T,pos)
BF算法的实现—即编写Index(S, T, pos)函数
BF算法设计思想：
将主串S的第pos个字符和模式T的第1个字符比较，
若相等，继续逐个比较后续字符；
若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列
第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0。
Int Index_BP(SString S, SString T, int pos)
{ //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
// 其中，T非空，1≤pos≤StrLength(S)
i=pos; j=1;
while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围，
{
if (S[i] = = T[j] ) {++i, ++j; } //则继续比较后续字符
else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配
}
if(j>T[0]) return i-T[0]; //T子串指针j正常到尾，说明匹配成功， else return 0; //
否则属于i>S[0]情况，i先到尾就不正常
} //Index_BP
数据结构重要知识点总结 第44篇
在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。
时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。
其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2)
空间效率：仅占用1个缓冲单元——O（1）
算法的稳定性：因为25*排序后仍然在25的后面——稳定
直接插入排序算法的实现：
void InsertSort ( SqList &L ) { //对顺序表L作直接插入排序
for ( i = 2; i <=; i++) //假定第一个记录有序
{ [0]= [i];
j=i-1 ; //先将待插入的元素放入“哨兵”位置
while（L[0] .key { [j+1]= [j]; j-- ; } //只要子表元素比哨兵大就不断后移 [j+1]= [0]; //直到子表元素小于哨兵，将哨兵值送入 //当前要插入的位置（包括插入到表首） } } 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊 的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点：① 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事 件模拟、OS作业调度和简化设计等。 1.堆的定义：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之 为堆。 解释：如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则 此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶） 必最大（或最小）。 2. 怎样建堆？ 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根 结点为止。 既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。 优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。 时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。 空间效率：仍为 O（1） 稳 定 性： 稳定 若记录是链表结构，用直接插入排序行否？ 答：行，而且无需移动元素，时间效率更高！ 但请注意：单链表结构无法实现“折半查找” 设p已指向第 i 元素，请在第 i 元素前插入元素 x： ① ai-1的后继从 ai ( 指针是p)变为 x（指针是s) : s->next = p ; p->prior->next = s ; ② ai 的前驱从 ai-1 ( 指针是p->prior)变为 x ( 指针是s); s->prior = p ->prior ; p->prior = s ; 树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合 子树之间不能有交集，否则就不是树形结构 每棵子树的根结点有且只有一个前驱 树是递归定义的 节点的度：一个节点含有的子树的个数称为该节点的度。 叶节点或终端节点：度为 0 的节点称为叶节点。 非终端节点或分支节点：度不为 0 的节点。 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。 兄弟节点：具有相同父节点的节点互称为兄弟节点。 树的度：一棵树中，最大的节点的度称为树的度。 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。 树的高度或深度：树中节点的最大层次。 堂兄弟节点：双亲在同一层的节点互为堂兄弟。 节点的祖先：从根到该节点所经分支上的所有节点。 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 森林：由 m（m>0）棵互不相交的树的集合称为森林。 二叉树要么为空，要么就是由一个根节点加上两棵别称为左子树和右子树的二叉树组成 二叉树不存在度大于 2 的结点 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，那么这个二叉树就是满二叉树 完全二叉树：对于深度为 K 且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1~n 的结点一一对应时，称之为完全二叉树 满二叉树是一种特殊的完全二叉树 若规定根节点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点 若规定根节点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h-1 任何一棵二叉树，如果度为 0 其叶结点个数为 n，度为 2 的分支结点个数为 m，则有 n=m+1 若规定根节点的层数为 1，具有 n 个结点的满二叉树的深度：h= log(n+1) 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为 i 的结点 普通的二叉树不适合用数组来存储，因为可能会存在大量的空间浪费，而完全二叉树更适合使用顺序结构存储。通常把堆用顺序结构的数组来存储。 二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树 堆（Heap）是计算机科学中一类特殊的数据结构的统称 堆通常是一个可以被看作一棵完全二叉树的数组对象 堆是非线性数据结构 最值总在 0 号位。堆中某个节点的值总是不大于或不小于其父节点的值 TopK 问题：在一堆数据里面找到前 K 个最大 / 最小的数 使用堆排序效率也更高 使用堆排序，一般都使用最大堆 堆的创建 前提：左右子树必须是一个堆（包括大堆和小堆）才能调整 从最后一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆 因为这样可以把最后一个非叶子节点的子树的左右子树看成是一个 (大 / 小) 堆，满足向下调整的前提条件，此时才能使用向下调整算法 建堆的时间复杂度为：O(N) 从上到下，从第一个节点（根节点）的左孩子开始，依次遍历完所有节点，分别对每个节点进行向上调整，一直到最后一个节点，就可以建成一个 (大 / 小) 堆 把数组中的第一个元素看作是一个堆，剩余的元素依次插入到这个堆中，这跟堆的插入接口原理相同，就是向上调整 建堆的时间复杂度为 O(nlog₂n) 使用向上调整算法建堆需要进行多次调整操作，而使用向下调整算法只需要进行一次调整操作。向下调整算法也更为直观，容易理解和实现，一般会选择使用向下调整算法来创建堆 利用堆删除的思想来进行排序 升序 -- 建大堆 -- 每次选出一个最大的数放到最后 可以，但不推荐。 降序 -- 建小堆 -- 每次选出一个最小的数放到最后 先插入一个 10 到数组的尾上，再进行 向上调整算法 ，直到满足堆 删除堆是删除堆顶的数据 ，将堆顶的数据跟最后一个数据作交换，然后删除数组最后一个数据（尾删），再进行向下调整算法 一般需要使用队列 可以是一棵空树 它的左右子树也分别为二叉搜索树 对二叉搜索树进行中序遍历，正好是一个升序序列（左子树 --> 根 --> 右子树） 增删查的时间复杂度为 O(h)，h 是树的高度，最坏情况是 h 是 N 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能 只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值 每一个关键码 key 都有与之对应的值 Value，即 向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1 （需要对树中的结点进行调整），即可降低树的高度（高度可保持在 O(log₂n)），从而减少平均搜索长度（时间复杂度 O(log₂n)） 它的左右子树都是 AVL 树 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1/0/1）。更新以后，parent 的平衡因子可能有三种情况：0，正负 1， 正负 2 1、更新以后，parent 的平衡因子是 0（说明插入之前 parent 的平衡因子之前一定为 1/-1），说明父亲所在子树高度没变，此时满足 AVL 树的性质，插入成功，不需要继续往上更新 2、更新以后，parent 的平衡因子是 1/-1（说明插入之前 parent 的平衡因子一定为 0），说明父亲所在子树高度增加，需要继续往上更新（最坏情况：往上一直更新到根节点） 3、更新以后，parent 的平衡因子是 2/-2，说明父亲所在子树出现了不平衡，需要对其进行旋转处理 因为在 2、4 等节点数的情况下，不可能做到左右高度相等的情况 AVL 树节点是一个三叉链结构，除了指向左右孩子的指针，还有一个指向其父亲的指针，数据域是键值对，即 pair 对象，还引入了平衡因子（用来判断是否需要进行平衡操作） 旋转的本质：在遵循二叉搜索树的规则下，让左右均衡，降低整棵树的高度 新节点插入较高左子树的左侧 —— 左左：右单旋 parent 的平衡因子为 -2，parent 左孩子平衡因子为 -1。父亲左边高，右边低，所以要让父亲往右旋 观察发现：平衡因子都是负数，说明左边高，也说明了引发旋转的路径是一条直线，所以要右旋 操作： 1、让 subL 的右子树 subLR 成为 parent 的左子树（因为 subLR 的右子树根节点值 > 30，< 60） 2、让 parent 成为 subL 的右子树（因为 60 > 30） 3、让 subL 变成这个子树的根。这一步操作前需要先判断下：parent 是根节点，还是一个普通子树 4、根据树的结构，更新 parent 和 subL 的平衡因子为 0 在旋转过程中，更新双亲指针的指向，有几种情况需要考虑 新节点插入较高右子树的右侧 —— 右右：左单旋 parent 的平衡因子为 2，parent 左孩子平衡因子为 1。父亲右边高，左边低，所以要让父亲往左旋 观察发现：平衡因子都是正数，说明右边高，也说明了引发旋转的路径是一条直线，所以要左旋 操作： 1、让 subR 的左子树 subRL 成为 parent 的右子树（因为 subRL 的左子树根节点值 > 30，< 60） 2、让 parent 成为 subR 的左子树（因为 30 < 60） 3、让 subR 变成这个子树的根。这一步操作前需要先判断下 parent 是根节点，还是一个普通子树 4、根据树的结构，更新 parent 和 subR 的平衡因子为 0 在旋转过程中，更新双亲指针的指向，有几种情况需要考虑 新节点插入较高左子树的右侧 —— 左右：先左单旋再右单旋（左右双旋） 需要的是先对 parent 的左孩子进行一次左旋，再对 parent 进行一次右旋 parent 的平衡因子为 -2，parent 左孩子的平衡因子为 1 观察发现：平衡因子是一负一正，说明左孩子右边高，父亲左边高，也说明了引发旋转的路径是一条折线，所以要先对左孩子进行左旋操作，再对父亲进行右旋操作 插入新节点的位置不同，经过左右双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有 3 种情况 新节点插入到了 parent 左孩子的右子树的左边 新节点插入到了 parent 左孩子的右子树的右边 新节点就是 parent 左孩子的右孩子 节点 60 的左右子树被分走了，左子树最终成为了节点 30 的右子树，右子树最终成了节点 90 的左子树 新节点插入较高右子树的左侧 —— 右左：先右单旋再左单旋（右左双旋） 需要的是先对 parent 的右孩子进行一次右旋，再对 parent 进行一次左旋 parent 的平衡因子为 2， parent 右孩子平衡因子为 -1 观察发现：平衡因子是一正一负，说明右孩子左边高，父亲右边高，也说明了引发旋转的路径是一条折线，所以先对右孩子进行右旋操作，再对父亲进行左旋操作 插入新节点的位置不同，经过右左双旋后，得到树的结构也会有所不同，平衡因子也会有所不同，有 3 种情况 新节点插入到了 parent 右孩子的左子树的左边 新节点插入到了 parent 右孩子的左子树的右边 新节点就是 parent 右孩子的左孩子 节点 60 的左右子树被分走了，左子树 b 最终成了节点 30 的右子树，右子树 c 最终成了节点 90 的左子树 假如以 parent 为根的子树不平衡（parent 的平衡因子为 2/-2），则分情况考虑 1、parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR 2、parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL 旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新 如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，最差的是在删除时有可能一直要让旋转持续到根的位置 红黑树，是一种二叉搜索树，近似平衡（控制最长路径不超过最短路径的 2 倍，不包括 NIL），变了一种方式来控制树的平衡，相较于 AVL 树而言，舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整 最长路径刚好是最短路径的 2 倍的原因 当某条路径最短时，这条路径必然都是由黑色结点构成的 当某条路径最长时，这条路径必然是由红色和黑色节点交替构成的 为了实现关联式容器简单，红黑树的实现中增加一个头结点。因为根节点必须为黑色，又为了与根节点进行区分，所以将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，_left 域指向红黑树中最小的节点，_right 域指向红黑树中最大的节点 当插入红色新节点 cur 后，如果父亲 p 存在且为红，说明破坏红黑树性质了，需要平衡化操作 记录 cur 的父亲 p 和祖父 g 的位置，然后判断父亲 p 的位置： 1、如果父亲 p 是祖父 g 的左孩子（说明叔叔 u 是祖父 g 的右孩子，先判断叔叔的状态） 如果叔叔 u 存在且为红，则直接先变色处理，然后再往上调整 1）先调整颜色：父亲 p 和叔叔 u 变黑，祖父 g 变红 2）再往上调整：原先祖父 g 当成新的 cur，判断新 cur 的父亲 p 如果叔叔 u 不存在 / 叔叔 u 存在且为黑，此时先判断 cur 的位置 1）如果 cur 是父亲 p 的左孩子（此时 cur、p、g 是一条直线） 2）如果 cur 是父亲 p 的右孩子（此时 cur、p、g 是一条折线） 3）上述情况处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整 2、如果父亲 p 是祖父 g 的右孩子（说明叔叔 u 是祖父 g 的左孩子，先判断叔叔的状态） 如果叔叔 u 存在且为红，则直接先变色处理，然后再往上调整 1）先调整颜色：父亲 p 和 叔叔 u 变黑，祖父 g 变红 2）再往上调整：原先祖父 g 当成新的 cur，判断新 cur 的父亲 p 如果叔叔 u 不存在 / 叔叔 u 存在且为黑，此时先判断 cur 的位置 1）如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条直线） 2）如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条折线） 3）上述两种情况处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整 停止调整是循环的出口，否则就要一直调整到根节点或者父亲 p 存在且为黑时 1、检测其是否满足二叉搜索树（中序遍历是否为有序序列） 2、检测其是否满足红黑树的性质 算法（Algorithm）就是定义良好的计算过程，它取一个或一组的值为输入，并产生出一个或一组值作为输出。算法就是一系列的计算步骤，用来将输入数据转化成输出结果。 衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。 函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。数据结构重要知识点总结 第45篇
数据结构重要知识点总结 第46篇
数据结构重要知识点总结 第47篇
数据结构重要知识点总结 第48篇
数据结构重要知识点总结 第49篇
数据结构重要知识点总结 第50篇