数据结构——系列思维导图思维导图模板

1绪论

数据结构的基本概念

数据元素

数据的基本单位（整体）（行）-由若干数据项组成

数据项

数据的最小单位（列）

数据对象

性质相同的数据元素的集合——字符型变量

数据结构

数据结构是带结构（关系）的数据元素集合

有说数据间的关系就是数据结构

数据结构包括

数据元素

元素间关系

数据元素的前后关系——逻辑结构

数据元素在计算机中的存储方式——物理结构

数据的逻辑结构

独立于计算机，抽象出来的，从逻辑关系上描述数据的一种数学模型。

与数据元素本身的形式、内容、相对位置、个数、存储无关

包含两个要素

数据元素

关系

线性结构

线性表、栈、队列

非线性结构

集合、树、图

数据的物理结构

数据对象在计算机中的存储表示

存数据对象时，既要存储各数据元素数据。也要存储数据元素之间的逻辑关系

数据物理结构（四种基本存储结构）

顺序存储结构

需要一块连续的存储区域，方式：逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系体系

链式存储结构

不需要所有结点占用一片连续的存储空间，结点间的逻辑关系由附加的引用字段（指针）来表示

索引存储结构

存储方式：采用附加的索引表方式存储结点信息，索引表由若干索引项（关键字、地址）组成

散列存储结构

存储方式：根据结点的关键字直接算出该结点的存储地址（通过散列函数，哈希函数）

无论顺序存储还是链式存储，每个结点都要占用一片连续的存储区域

同一逻辑结构采用不同的存储方法可以得到不同的存储结构

数据的运算

运算的定义：是针对数据逻辑结构的，即针对这种逻辑结构需要进行什么运算。比如队列中的入队，出队。

运算的实现：是针对数据存储结构的，即针对逻辑结构会有不同的存储结构。比如实现的运算相同，但不同的存储结构其实现方式不同。

数据结构的三要素：逻辑结构，物理结构，运算。

注意⚠️

选择什么样的数据的存储结构会影响存储空间分配的方便程度，会影响数据运算的速度。

数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称

即若定义一个具体的结构类型，根据这个类型具体的业务需求可确定值的范围以及可进行的操作。

抽象数据类型ADT

是指由用户定义的，表示应用问题的数学模型以及定义在这个模型上的一组操作的总称（结构体）

数据对象

数据对象间的关系

数据对象的基本操作

ADT是抽象数据组织及与之相关的操作。

当定义一个抽象数据类型时，其实我们是用数学化的语言定义数据的逻辑结构和数据的运算。而与使用哪种物理结构无关。

而只有当我们需要用计算机去实现此数据结构时才需要考虑存储结构。

总结：

定义了一个ADT，就是定义了数据的逻辑结构和运算，也就是定义了一个数据结构。

构成一个完整的数据结构定义。

确定一种存储结构，就意味着要在计算机中表示出数据的逻辑结构。存储结构不同，运算的具体实现不同。

确定了存储结构，才能实现数据结构。

算法和算法分析

算法

定义：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作。

算法的五个特性：

有穷性：一个算法总是在执行有限步后结束，且每一步都是在有穷时间内完成。

所以算法必须有穷，但程序可以无穷无尽的进行下去，比如微信。还有死循环也不具备有穷性，因为有限步后结束不了。。。

确定性：算法的每一条语句指令都必须由确定的含义，别人理解时候不产生二义性。

任何条件下算法只有唯一的执行路径，即1：1，相同输入得相同输出

不是一次输入得这个，一次输入得那个。

可行性：算法可行，即算法中描述的操作均可由有限次已成型的基本运算实现。

即可由代码实现。

输入：可以有0个或多个输入。

输出：可以有1个或多个输出。

一个好的算法包括四个方面：

正确性：

算法应能正确的解决问题。

可读性：

代码可读，可让人们理解。

健壮性：

当输入非法数据时，算法能适当地作出反应并进行处理，而不会产生莫名其妙的结果。

高效率和低存储量：

速度快，内存小。

时间复杂度低，空间复杂度低。

算法执行的效率与数据的逻辑结构，物理结构，程序的控制结构，输入的数据量问题规模n，语句频度（T与n关系），解决问题的策略等有关。

算法最终必须由计算机程序实现

❌

同一个算法，实现语言的等级越低，执行效率越高，越快

算法效率的度量

评价算法的优劣：

事前估计

算法时间开销T(n)与问题规模n的关系

T表示Time时间

算法空间开销(内存)与问题规模n之间的关系

S表示Space空间

时间复杂度

执行算法的语句次数/语句频度

算法的时间复杂度与选择的程序设计语言无关

关注基本操作执行的次数

T与n的关系

现实中常讨论最坏情况下的时间复杂度，所以，所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界。

算法时间复杂度 / 时间开销取决于

问题的规模

待处理数据的状态

（如某些算法受数据初始状态杂乱程度的影响）

不考虑与空间复杂度的关系

强调相同规模n下的情况下，O(n)才总比O(n²)快。否则不一定

算法时间复杂度并不是指算法执行时所用的具体时间，时间复杂度是一个函数（定量的描述了算法的运行时间）

T(n) = O(f(n))

n是指问题规模；即输入的数据量；数据的个数；数据的规模

O(1)算法运行时间与数据量大小无关。

O(n)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n倍。

O(n²)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n²倍。

计算原则

循环次数最多原则

要循环次数最多的那段代码

加法原则

要量级最大的代码块代码

乘法原则

内外嵌套且无关：内外乘积

计算方法

分单层循环①②③④⑤步

①找出循环条件；②设循环次数a，③找a与i关系；④代入条件；⑤出结果

和多层循环①②步

①看内外是否无关

②若内外无关，就各算各的，相当于两次单层循环任何乘起来

②若内外有关，则列累加求和式，由右向左算，最后再当单层循环算①②③④⑤步

空间复杂度

算法所需存储空间的量度

执行当前算法需要占用多少辅助空间

S(n) = O(f(n))

原地工作：

含义：原地工作是指不需要任何额外的辅助空间

算法所需要的辅助空间（临时空间）不随问题规模n而变化，即辅助空间与n无关

则此算法的空间复杂度为一个常量。记作O(1)

栈

定义

栈是操作受限的线性表，仅允许在表尾（栈顶）进行插入和删除操作
栈的表头称作栈底，栈的表尾称作栈顶。

特点：后进先出：LIFO
先进后出：FILO

存储

栈的顺序存储结构：顺序栈

定义：栈由两个指针组成，栈底指针指向栈底，栈顶指针初值指向栈顶，插入top+1，删除top-1，所以栈顶指针总是指向栈顶元素的下一个位置

top指向当前栈顶元素的位置。

所以top指针就表示新的栈顶。（数据可能残留在内存中，只是逻辑上被删除）

栈的链式存储结构：链栈

实现：采用不带头结点的单链表实现。规定栈的所有操作都只在此单链表表头进行。

单链表——头插法

优点：不存在栈满溢出的情况

顺序栈操作

顺序栈结构体：
typedef struct{
SElemType *base; //栈构造之前和销毁之后，base=NULL
SElemType *top;
int stacksize; //表示当前已分配的存储空间
}Sqstack

初始化：
Status InitStack(SqStack &S){
S.base = (SElemType *)malloc (STACK_INIT_SIZE * sizeof(SELemType));
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}

销毁：
Status DestroyStack_Sq(Sqstack &S) {

}

取栈顶元素：
Status GetTop(SqStack S, SElemType &e){
if(S.top == S.base) return ERROR;
e = *(S.top - 1); //
return OK;
}

进栈：
Status push(SqStack &S, SElemType e){
*(S.top++) = e; //*S.top = e; S.top++;
}

出栈：
Status pop(SqStack &S, SElemType e){
e = *(--S.top); //S.top--; e = *S.top
}

栈空：S.top = S.base;

栈满：S.top == MaxSize-1

顺序栈的操作（2）

初始化：S.top = -1; //top现在指向栈顶元素

栈顶元素：S.top[S.top]

进栈：栈不满时，栈顶指针先+1，再赋值值到栈顶元素

S.data[++S.top] = x;

出栈：栈非空时，先存栈顶元素，再将栈顶指针-1

x = S.data[S.top--]

栈空：S.top == -1;

栈满：S.top == MaxSize-1;

栈长：S.top + 1;

共享栈（双端栈）

定义：

若需要用到两个相同类型的栈，可用一个数组data[0...maxSize-1]来实现这两个栈，称为共享栈（共享一个一维数组）。
数组的左右两个端点分别是两个栈的栈底，一个栈的栈底为数组始端0，另一个栈道栈底为数组末端MaxSize-1
当元素进栈时，栈顶向共享空间的中间延伸。

优点：

可以更新有效的利用存储空间，节省存储空间，两个栈的空间可以相互调节，只有在整个存储空间被两个栈占满（即两个栈栈顶相遇）时，才发生上溢（降低上溢发生的几率）。

存取数据的时间复杂度是O(1)

操作：

栈空：top1 = -1 top2 = MaxSize

栈满：top1 + 1 == top2;

top2-top1 = 1;

进栈：top1++; data[top1] = x; top2--; data[top2] = x;
S.data[++top1] = x; S.data[--top2] = x;

出栈：x = data[top1]; top1--; x = data[top2]; top2++;
x = S.data[top1--]; x = S.data[top2++];

设计：

为了便于管理，可以将共享栈设计为一个结构体类型。

#define MaxSize 100;
typedef struct{
SElemType data[MaxSize]; //建立一个data[]数组
int top1, top2; //两个栈的栈顶指针
}DStack;

栈的应用题型

表达式求值：

中缀转后缀的三种方式：

逐步法：逐步根据原中缀表达式优先级，并按照“左优先”原则，做变换（符号移至操作数末尾）。

暴力法：1️⃣将每两个操作数用括号括起来，2️⃣将操作符提出至括号后，3️⃣去掉括号。

二叉法：将表达式画成二叉树，再根据后序遍历得后缀表达式

递归函数判断：

栈与递归有着紧密的联系。递归模型包括递归出口和递归体两个方面，递归出口是递归算法的出口即递归终止的条件；递归体是递推的关系式。

若题目问某个递归函数执行次序/次数，可以画出对应递归调用树。

即某个函数的执行次序等于其在递归调用树的层次遍历次序。

递归函数：

对于一个问题的递归算法求解和其相对应的非递归算法求解相比：非递归算法效率更高一些。反而递归算法有一些冗余的重复的计算。

消除递归不一定需要使用栈。

使用栈可以模拟递归的过程，以此来消除递归。

但对于单向递归或尾递归来说，可以用迭代的方式（非递归）来消除递归。

括号匹配的校验

数制转换

行编辑程序的输入缓冲区

迷宫求解

车辆调度中求出栈车厢序列，

队列的应用题型

内存缓存区

打印机打印序列

FIFO页面替换算法

考点

递归的时候用栈。
程序调用是一个递归过程，用栈实现，首先从main函数进入，即栈的进栈过程。
函数调用是一个递归的过程。

由于栈具有后进先出的特性，所以根据入栈（出栈）序列能判断出出栈（入栈）序列。

这个入栈出栈序列可以相同，可以互为逆序。

即使确定了入栈次序，也不能就此来确确定定出栈序列。

因为不知其中元素的出栈时间。

n个元素进栈，出栈元素的不同排列个数为：卡特兰数 C2n的n / n+1

题型

写出出入栈序列

判断可能取值的个数

共享栈判初始，栈空，满

[1, n] 栈底：top1=1, top2=n
栈满：top1 + 1 = top2;

[0, n-1] 栈底：top1=-1, top2=n
栈满：top2-top1 = 1;

向一个栈顶指针为top的链栈，插入一个x结点：
先将x的next指针域指向top，再将栈顶指针指向x
x->next = top; top = x;

通常情况下，递归算法在计算机中的执行过程中会有很多重复的计算或是验证步骤，所以递归算法比非递归算法效率低。

调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录和函数的局部变量压入系统提供的栈中。

向栈顶指针为top的链栈（不带头结点）中插入一个x结点：x->next = top; top = x;

即在不带头结点的链表首部插入一个元素。

若已知栈的输入序列12345....n，若问输出第一个元素为i，那么第j个输出的元素是？

因为i不确定，所以没有i-j，j-i+1 这种出栈规律。

队列

定义

队列queue，是一种限制存取位置的线性表，它只允许在表的一端（表尾，队尾）进行插入，另一端（表头，队头）进行删除。

特点

队列的插入和删除操作分别在各自一端进行，每个元素按照进入的次序出队。即先进先出 FIFO。

存储

队列的顺序存储结构：顺序队列

SqQueue结构体声明：
#define MaxSize 100
typedef struct {
QElemType data[MaxSize];
int front, rear;
} SqQueue；

front队头指针指向队列队头元素位置，rear队尾指针指向队列队尾元素的下一个位置。

顺序队列满了怎么办？
‌又不能像顺序栈一样进行数组再分配扩大数组空间。

将顺序队列臆想为一个环状的空间——循环队列
（插入队尾指针增1，通过模来运算）

1️⃣少用一个队列空间，即队列空间大小为m时，认为有m-1个元素时队满。
队空：q->front == q->rear;
队满：(q->rear+1)%MaxSize == q->front; （约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志）
队列长度：(rear - front + m) % m;

2️⃣增设表示队列元素个数的数据成员size。
队空：size == 0 && front == rear;
队满：size == MaxSize && front == rear;

3️⃣增设tag标签数据成员以区分队满与空（队空队满代码一样，那就再设一个变量记录此时队列状态）
队空：tag == 0；因删除导致front = rear
队满：tag != 0；因插入导致front = rear

循环队列：【0， m-1】front指向队头元素前一个位置，rear指向队尾元素。<=>front指向队头元素，rear指向队尾元素的下一个位置一样
入队时队尾指针前进1：(rear + 1) % QueueSize（QueueSize循环队列的最大长度）
出队时队头指针前进1：(front + 1) % QueueSize

队空：q.rear = q.front

队满：(rear+1) % m == front
循环队列的元素个数 / 队列长度：(rear - front + QueueSize) % QueueSize

+1的原因是下标默认值为-1

循环队列：【0， m-1】front指向队头元素，rear指向队尾元素

队空：q.rear = q.front

队满：
队列长度（队列中元素个数）：
当rear>front时，当前队列的元素个数是：rear - front + 1
当rear<front时，当前队列的元素个数是：rear - front + m + 1
综合上述两种情况：当前队列的元素个数是：(rear - front + m + 1) MOD m

循环队列：【0， m-1】默认front，rear

队空：

队满：
当前队列中元素个数是：(rear - front + m) % m

操作：
队空（初始化）：q->front == q->rear;
队满：q->rear == MaxSize;
进队：data[rear] = x; rear++; q->data[q->rear] = x; q->rear++;
出队：x = data[rear]; front++; x = q->data[q->front]; q->front++;

队列的链式存储结构：链队列

实现：采用单链表来实现队列，在单链表表头删除，表尾插入。

本质：

是一个同时带有队头指针（指队头结点）和队尾指针（指队尾结点）的 单链表

特点：同链栈一样，不存在队满溢出的情况

链队列在做删除运算时，看成单链表的删除操作：
当队列有多个元素时，只需修改头指针即可。
当队列只有一个元素时，该结点既是头又是为尾，则需要修改尾指针置空。

适合：

用单链表表示的链队列适合于数据元素变动较大的情形，且不存在队列满产生溢出的问题

LinkQueue结构体声明：
typedef struct qnode{
QElemType data;
struct qnode *next;
}DataNode;

typedef struct{
DataNode *front;
DataNpde *rear;
}LinkQuNode;

操作：
队空：q->front = q->rear;
队满：不考虑
入队：插入到单链表表尾
出队：删除单链表表首结点

(q->front ==NULL; 且 q->rear == NULL;)

初始化：q->front = q->rear = NULL;
进队：
void enQueue(LinkQuNode *&q, QElemType e) {
DataNode *p;
p = (DataNode*) malloc (sizeof(DataNode));
p->data = e;
p->next = NULL;
if(q->front == NULL). //若进队时候，队列为空，则新进入的结点既是对首结点又是队尾结点
q->front = q->rear =p;
else{
q->rear->next = p; //若进队时候，队不为空，则把新结点链接到队尾，并用尾指针指向p
q->rear = p;
}
}
出队：
bool deQueue(LinkQueueNode *&q, QElem) {

}

链队列的判空条件

带头结点

front == rear q==null

不带头结点

front+1 == rear q->next=null

双端队列

定义：是指队列的两端都可以进行进队和出队操作，不受限制，其元素的逻辑关系仍为线性关系。

问：既然队列前后端都可以出入队，那是不是可以想得到什么序列就得到什么序列？
例如dcab这个序列，可以ab后端进，cd前端进，最后都从前端出。
但是abcd入队，出队dacb是不无论如何也出不来的。因为c不论是前端进出还是后端进出，都无法在ab之间。

特点：双端队列中，元素从前端进后段出或从后段进前端出，都体现了队列先进先出的特性。
而元素从前端进前端出或从后端进后段出，则体现了栈的后进先出的特性。

实际使用中，可以自定义双端队列的两端进出规则。
若再次限定双端队列中从某端进队的元素只能从某端出队，则该双端队列即变为了两个栈底相邻的栈。

若只能从左进（限制入队），左右都能出，则说明已知入队序列，想要得到目标序列就看左右两边怎么出队了。

若只能从右出（限制出队），两边都能进，则说明目标序列只能从右边出来，看左右两边怎么进能得到目标序列。

队列的应用

题型

做自定义双端队列出入时，已知入队顺序，判不可能的出队顺序。

F1：自己按逻辑排一下，顺一下。

F2：以第一个入队元素A为中心，在队列中向左向右看都是顺序，没有逆序，则可实现。

F3：以ab或是其他挨着的序列看，无论ab是从一端进还是两端进，只要已知入队顺序，则在队列中，ab必相挨。

一旦涉及顺序队列中判断front，rear指针位置时，注意套公式。

rear = (rear+1) % MaxSize

front = (front+1) % MaxSize

栈和队列本质都是线性表，线性结构。他俩的本质区别是：插入、删除操作的限定不同。

不能说ADT一致：因为ADT包含三项：逻辑结构，存储结构，运算。栈队列运算说不同的。

能根据首尾指针计算出队列长度的一定是顺序存储时。链式存储计算不出长度。

错因：哪种链表适合队列：一定根据队列的特点去选择链表种类：即两端操作。

即找有首尾指针的队列，此时循环没用，人家队列不需要循环，循环画蛇添足。

错因：利用两个队列输出序列。

数组和特殊矩阵

定义

前言：矩阵在计算机图形学、工程计算中占有举足轻重的地位，而在数据结构中，我们的精力重心放在如何让将矩阵更有效地存储在内存中，并能方便地提取矩阵中元素。

逻辑表示：A = (a1, a2, ... , an) 其中ai（1 <= i <= n）表示数组A的第i个元素。

一维数组是由n（n=>1）个相同数据类型元素组成的有限序列

每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广

一个二维数组（矩阵）可以看作是每个数据元素都是相同数据类型的一维数组的一维数组。

二维数组也叫矩阵，行列相等的叫方阵。

性质

数组一旦被定义，其维数和维界就不再改变。即数据元素数目固定，一旦定义来一个数组，其数据元素的数目不再有增减的变化。

数组中通常只有两种操作：
不做插入与删除上因为定义好数组后长度就固定了

读操作：给定一组下标，读取相应的数据元素。

写操作：给定一组下标，存储或修改相应的数据元素。

数组中的数据元素数目固定。一旦定义来一个数组，其数据元素的数目不再有增减的变化。

数组中的数据元素具有相同的数据类型。

数组中的数据元素都和一组唯一的下标一一对应。

数组是一种随机存储结构，具有随机存取的特性，即可随机存取数组中的任意数据元素。

数组的存储结构

通常将数组的所有元素存储到存储器的一块地址连续的内存单元中，即数组特别适合采用顺序存储结构来存储。

一维数组的存储结构：

设：每个元素占用k个内存单元
LOC(ai) = LOC(a1) + (i-1)*k (1 <= i <= n)

二维数组的存储结构：

设：m行n列的二维数组Am*n
每个元素占用k个存储单元
A[1,1] - A[m,n]

二维数组按行优先存储：LOC(ai,j) = LOC(a1,1) + [(i-1)*n + (j-1)]*k

LOC(ai,j) = LOC(a0,0) + (i * n + j) * k

二维数组按列优先存储：LOC(ai,j) = LOC(a1,1) + [(j-1)*m + (i-1)]*k

LOC(ai,j) = LOC(a0,0) + (j * m + i) * k

特殊矩阵

定义：特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。所以利用此种规律对数组进行压缩存储进而提高存储空间效率。

特殊矩阵包括：
均为方阵，即m=n
（行数=列数）

对称矩阵：若一个方阵A[n][n]满足ai,j=aj,i ( i 属于[0, n-1] )，则称其为n阶对称矩阵。
( i 属于[1, n] )

对称矩阵按主对角元素对称，其上下三角部分对应元素相等，所以存储时可以只存主对角元素+上/下三角元素。(存一半就行)

对称矩阵的存储：

在以行序为主序的存储方式下，存下三角元素（i => j）至一维数组B：b k = (i+1)*i / 2 + j

k = i * (i-1) / 2 + j-1

在以行序为主序的存储方式下，存上三角元素（i < j）至一维数组B：b k = (j+1)*j / 2 + i

k = j * (j-1) / 2 + i-1

三角矩阵：包含上三角矩阵和下三角矩阵。( i 属于[0, n-1] ) ( i 属于[1, n] )

上三角矩阵：上三角矩阵的上三角为正常序列（i<=j），下三角为常数C的n阶方阵。

下三角矩阵：下三角矩阵的下三角为正常序列（i > j），上三角为常数C的n阶方阵。

对角矩阵：若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。（只有对角线和对角线的两侧有值，其余元素均为0）其主对角线上、下方各有b条非零元素构成的次对角线，称b为矩阵半带宽，（2b+1）为矩阵的带宽，若b=1，则为三对角矩阵。
定义二：i-j的绝对值>1时，ai,j = 0 ( i 属于[0, n-1] ) ( i 属于[1, n] ) 压缩到一维数组B长度为3n-2。 B中存放下标：k=2i+j-3

三对角矩阵的压缩存储

A中行下标为0的行和行下标为n-1的行都只有两个非零元素，其余各行有三个非零元素。

1 <=i; j<=n; | i-j |

前i行存储元素总数2+3(i-1)

在第i行分为三种情况

i.1 : k = 2+3(i-1) = 3i-1

此时 j = i-1，即k=2i + i-1 = 2i+j

i.2 : k = 2+3(i-1) + 1 = 3i

此时 j = i，即k=2i + i = 2i+j

i.3 : k = 2+3(i-1) + 2 = 3i+1

此时 j = i+1，即k=2i + i+1 = 2i+j

【1-n】，若已知 B[k] ，则有i = ⌊(k+1) / 3 + 1⌋, j = k-2i+3 ，所以存aij

例：当k=2时，i=2，j=1，所以存a21

若特殊矩阵存在b矩阵是 [1, n] 以1开头的，那还是按0的公式算，最后+1即可。

稀疏矩阵：

稀疏矩阵中的非零元素的个数相较于矩阵元素总个数来说非常小，且分布没有规律。

⚠️稀疏矩阵压缩存储后便失去了随机存取的特性

稀疏矩阵的存储

三元组表示法：稀疏矩阵中的每一个非零元素由一个三元组（i, j, ai,j）<行，列，值>唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表——>

顺序存储 => 形成三元组顺序表（三元组表）

十字链表表示法：当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储来表示三元组的线性表。——>

采用链式存储结构来表示三元组线性表，链表中的每个非零元素既是某个行链表中的一个结点，又是某个列链表的一个结点。整个矩阵构成十字交叉的链表。

采用两个分别存储行链表的头指针和列链表的头指针的一维数组来表示。

题型

对称矩阵中，上三角按列优先 = 下三角按行优先 计算时候：（上列 <=> 下行）（公式中 i 换成 j ）（所求的具体下标中 i，j 也互换）

对称矩阵的计算：对对称矩阵进行压缩存储，B中只存下三角元素，而所求点位A[i, j]于上三角，则需把此上三角点位对应至下三角A[j, i]

三角矩阵的计算：首先看需要求的矩阵位置点位于上三角还是下三角，然后对应看题目要求的存储方式，再去对应公式计算。

矩阵0，1开始放到数组B [0，n-1] 算经典公式

若矩阵0，1 放到数组B [1，n]，则还按经典公式算，最后 +1 即可

补充

将元素ai,j存放在bk中

对称矩阵上下三角对应元素相等，所以存一半就行

上三角存储：
1——n
2——n-1
3——n-2
......
i——n-i+1

树与二叉树

树

树的定义：

树是n（n => 0）个结点的有限集合T，满足：（当n=0时，称为空树）
1️⃣有且仅有一个特定的被称为“根”的结点。
2️⃣其余结点分为m（m > 0）个互不相交的子集T1、T2、T3，其中每个子集又是一棵树，称为根的子树。

树的定义是递归的，所以树是一种递归的数据结构。

特点：

树是一种非线性的数据结构，一对多。

树中每个元素（除根结点外）均有一个直接前驱（辫子），有零个或多个后继。——故n个结点有n-1条边。

树适合表示具有层次结构的数据

与树有关的术语：

结点的度：一个结点的子树个数。
树的度：该树中结点的最大度数。

度为 k 的树也称 k叉树，其中每个结点最多有k个子树

度=m，则为m叉树

基本结点介绍：

分支结点（非终端结点）：

度不为零的结点。N1，2

叶子结点（终端结点）：

度为0的结点。N0

⚠️在树的分支结构中，每个结点的分支数就是该结点的度数。
如：对于度为1的结点，其分支数为1，为单分支结点；度为2的结点，其分支数为2.，称为双分支结点。

孩子结点和双亲结点：树中某个结点的子树的根，该结点则为孩子的双亲结点。

兄弟结点：同双亲的孩子结点互称为兄弟。

堂兄弟结点：双亲结点是兄弟关系的结点（即在同一层）。

子孙结点和和祖先结点：

以某结点为根的子树中的任意结点称为该结点的子孙。

该结点的祖先是从树的根结点到该结点所经分支上的所有结点。

树的层次、深度和高度：

树的层次：从根结点开始，根为第1层，其子结点为第2层，以此类推。

树中结点的最大层数称为树的高度或深度。

树的深度：从根结点开始 自上而下数。

树的高度：从叶结点开始 自下而上数

有序树和无序树

有序树：树中结点的各子树从左到右有次序，位置不可互换；若互换，则称为一棵不同的树。

无序树：树中结点的各子树交换，不影响树的基本排列。

路径与路径长度；

路径：树中两个结点的路径是指两个结点之间所经过的结点的序列。

路径长度：在此路径上所经过的结点个数。

⚠️树中的分支是有向的，即从双亲指向孩子，所以树中的路径树从上到下的。

同一双亲的孩子之间不存在路径。

树的路径长度是指树根到每个结点的路径长度的总和。

树的等价和同构：

若在两棵树中，各结点对应相等，各结点的对应关系也相等，则称这两棵树相等或等价。

若在两棵树中，适当重命名其中一棵树的结点可以使两棵树等价，则称为树的同构。

森林：

森林是m（m => 0）棵互不相交的树的集合。

显然，删除一个树的根，就可以得到一个森林；反之加上一个结点作为树根，将这m棵树作为该结点的子树，森林就变为一棵树。

所以树与森林可以相互转换。

树的性质：

树的结点数 = 所有结点的度数 + 1 = 总度数 + 1 = 分支数 + 1

写两个式子：

n = n0 + n1 + n2 + n3 （设n0 n1 n2 n3 分别是度为0123的结点个数）等于各度数的结点数量之和

n = 0*n0 + 1*n1 + 2*n2 + 3*n3 + 1

度为m的树中，第i层上至多有 m的i-1次 个结点。

高度为h的m叉树至多有( m的h次-1 ) / (m-1)。

具有n个结点的m叉树的最小高度是logm(n*(m-1)+1)。

树的题型：

根到每个结点的路径长度最大值为：h-1。

树有n个结点，度为m，要使此树最高：h = n - (m-1) 【即除最后一层外，每层结点数为1，即只有最后一层为m】。

已知结点总数n，度数m，求树的最小高度，那就是把每一层的每一结点都排满度数 n - (1 + m + m的2次 + m的3次...) 或者套公式：logm(n*(m-1)+1)。

已知树高h，度数m，求结点总数，则n至少为 h + (m-1)；至多为 1 + m + m 的2次 + ... + m的h-1次 = ( m的h次-1 ) / (m-1)。

若结点数量为n，则边的数量为n-1。

二叉树

二叉树的定义：

二叉树（Binary Tree）是 n (n=>0)个结点的有限集合。（二叉树可以为空）

二叉树由一个根结点及两棵互不相交的，分别称作该根的左子树和右子树的二叉树组成。（递归定义）

二叉树的主要特征：

每个结点最多只能有两棵子树，度<=2（即二叉树不存在度 > 2的结点），并且这两棵子树有左右顺序之分，其次序不能随意颠倒。

度<=2的有序树

二叉树与度为2的有序树的区别；

度为2的树最最少 (至少) 有三个结点，但是二叉树是可以为空的。

度为2的有序树的孩子虽然有左右之分，但若只有一个孩子，则不分左右。（因为有序树孩子的左右次序是相对于另一个孩子而言的）

而二叉树即使只有一个孩子，也要严格区分左右，即左孩子和右孩子。（因为二叉树的孩子左右是确定好的，不是相对于另一个的）

总结：由此来看，二叉树与树是两个不同的概念。二叉树既不是树的特殊情况，也不是有序树的特殊情形。

几种特殊的二叉树：

1️⃣满二叉树：(Full Binary Tree)

定义：满二叉树的每一层上的结点数都达到了最大（即给定高度的二叉树中，满二叉树结点数最多）

特点：

满二叉树的深度为k，则有2的k次-1个结点。

满二叉树中的每层都含有最多的结点。

满二叉树中不存在度为1的结点（除叶子结点外），每个分支结点的度数都是2。

满二叉树的每个分支结点均有两棵高度相同的子树，且所有叶结点均在最下面一层。

即满二叉树的叶结点全在最后一层。

可对满二叉树的结点进行连续编号，一般约定，从根结点开始，按“自上而下，自左向右”按层序排序编号。

对于编号为 i 的结点来说，其双亲为⌊i/2⌋，左孩子为2i，右孩子为2i+1。

【若 i 属于[0，n-1] 】

其双亲为 i-1/2，左孩子为 2i+1，右孩子为 2i+2。

例：i=5 的双亲结点为：⌊5/2⌋=2

2️⃣完全二叉树：(Complete Binary Tree)

定义：若高度为h，结点数为n的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号从1-n的结点一一对应。

即深度为k的满二叉树中编号从1～n的前n个结点构成了一棵深度为k的完全二叉树。【2的k-1次<= n <=2的k次-1】

在完全二叉树中，至多只有最下面两层的结点的度可以小于2，并且

最下层的结点都集中在该层的最左边的若干位置。比满二叉树少了最右边的几个叶结点。

特点：

一棵完全二叉树，前 h-1 层为满二叉树

即高度为h的完全二叉树中，其1～h-1层构成了一个高度为h-1的满二叉树。共有2的h-1次-1个结点。

具有n个结点的完全二叉树的深度/高度为 ⌊log₂ n⌋+1 / ⌈log₂(n+1)⌉ = ⌊log₂ 2n⌋

完全二叉树的高度是所有二叉树中最小的高度。

完全二叉树中n1的取值只可能为0或1。

在完全二叉树中，若有度为 1 的结点，则只有一个结点 且该结点只有左孩子而无右孩子。

完全二叉树

叶结点特点

叶结点只可能在层数最大的两层中出现。

i > ⌊i/2⌋ 为叶子结点。

例：完全二叉树最后一个结点为n，其父结点为 s = ⌊n/2⌋，叶结点个数：n0 = n-s

在完全二叉树中，若某一个结点没有左孩子，则其一定没有右孩子，即必定为叶结点。【因为根据定义，完全二叉树必须先有左孩子、再有右孩子】

若已知完全二叉树的第 i 层出现了叶结点，说明此树高h = i 或 i+1

为完全二叉树按层序编号后，一旦出现某个结点( i )为叶结点或 i 只有左孩子，则 > i 的结点全为叶子结点。

若编号n为奇数，则每个分支结点均有左右孩子；若编号n为偶数，则编号最大的分支结点只有左孩子无右孩子。其余分支结点左右孩子均有。

满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。

空二叉树和只有根结点的二叉树既是满二叉树，也是完全二叉树。

对于一棵有n个结点的完全二叉树（其深度为⌊log₂ n⌋+1 ）的结点按层序编号

（从第1层到⌊log₂ n⌋+1层），每层中从左到右，则对任一结点 i (1 <= i <= n)，

i=1为根，有：

【找双亲】若 i>1 ，i双亲是结点 ⌊i/2⌋（下取整），即：

当i为偶数时，则其双亲是 i/2（ i是双亲的左孩子）；

当i为奇数时，其双亲的编号为(i-1)/2（ i是双亲的右孩子）。

【找左孩子】若2i <= n，则结点 i 的左孩子编号为 2i，否则无左孩子（即结点i 为叶结点）。

故 i > n/2（下取整）必定是叶子

【找右孩子】若2i+1 <= n，则结点i 右孩子编号为 2i+1，否则无右孩子。

结点 i 所在的层次 (深度) 为 ⌊log₂ n⌋+1

3️⃣平衡二叉树：(Balance Binary Tree)

定义：在平衡二叉树中，任意一个结点的左子树和右子树深度之差的绝对值不超过 (<=) 1。

特点：

平衡二叉树有更高的搜索效率。

平衡二叉树本质上是二叉排序树。❓

从平衡因子定义看，完全二叉树任一结点平衡因子绝对值<=1，但完全二叉树不一定是排序树，所以不是平衡二叉树。

4️⃣二叉排序树：(Sort Binary Tree)

定义：在二叉排序树中，左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字。

特点：

二叉排序树的左子树，右子树又是一棵二叉排序树。（且是递归定义）

二叉排序树方便关键字的检索，插入操作。

二叉树的性质：

二叉树第 i 层上的结点数为2的i-1次。(i => 1)

深度为 k 的二叉树至多有2的k次-1个结点。(全满)【以2为公比的等比数列求和（0～k-1）】

三叉树共有结点数：1/2 * 3的k次-1

高度为 h 的二叉树至多有2的h次-1个结点。

三叉树共有结点数：1/2 * 3的h次-1

对任何一个二叉树，都有：n0 = n2 + 1。

n与n0关系：n = 2n0 - 1 +n1

具有n个结点的二叉树，要求其最小高度：——>当二叉树构成完全二叉树时，高度最小。h = log₂ n + 1 = log₂ 50 + 1 = 5+1 = 6。所以h=6。

一般二叉树高度：⌊log₂n⌋+1 ～ n

二叉树的题型：

可以问：构造二叉树时：

结点最多：——> 满二叉树。若为完全二叉树，则根据前h-1层为满二叉树，数形结合的看。

结点最少：——> 1+(h-1)*2。

高度最高：——> h = n （二叉树高度范围：⌊log₂ n⌋+1 ~ n ）

高度最低：——> 完全二叉树在二叉树中高度最低。（最小深度）

二叉树高度为 h，且只有度为0，2，则结点数至少( 最少 )有：1 + 2(h-1) = 2h-1 （即第一层一个，其余h-1层均有两个结点）

二叉树的存储结构：

顺序存储结构：

二叉树的顺序存储就是将所有结点存储到一组连续的存储单元中（数组），并能通过结点间的物理位置关系反映逻辑关系（双亲和孩子关系）。

顺序存储时，结点间的次序关系要能反映结点间的逻辑关系。用数组下标（编号）来表示结点之间的父子关系。（根据二叉树的性质）

需要存逻辑，就按满二叉树存。

编号过程：首先把树根结点定为1，然后按照层次从上而下，每层从左至右的顺序，对每一结点进行编号。

即将二叉树上编号为 i 的结点存储在一维数组下标 i-1 的分量中。

当一结点为 i ，i 属于[1, n] 时，其双亲为⌊i/2⌋，左孩子为2i，右孩子为2i+1。

当一结点为 i ，i 属于[0, n-1] 时，其双亲为⌊i-1/2⌋，左孩子为2i+1，右孩子为2i+2。

优点：

便于访问每一结点的双亲和左右孩子。

顺序存储的随机存取，i，2i-1，2i+1。

二叉树的顺序存储结构适用于完全二叉树和满二叉树。

这样既能充分利用、节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

缺点：

对退化的二叉树（每个结点都是单分支），或单分支较多的一般二叉树来说不实用，空间浪费较为严重，空间利用率低。

存储一般二叉树的时候，为了能让数组下标反映二叉树中结点的关系，所以添加用0表示的空结点，让其与完全二叉树对照，再存到一维数组的相应分量中。

最坏情况下，高度为 h 的h个结点的单支树，竟然需要2的h次 -1个存储单元。

顺序存储的二叉树插入、删除等操作不方便。

链式存储结构：

一般二叉树通常采用链式存储结构存储。

即为二叉链表存储结构——参考双链表：一个data数据结点，两个指针，一个左指针，一个右指针。

若增加父结点的指针，双亲域，即为三叉链表。

特点：对于n个结点，有2n个指针域；n-1个前驱指针 (辫子，非空指针)；n+1个空链域。【2n-(n-1)=总分支-非空指针=空指针】

利用n+1个空链域存储结点直接前驱与后继，形成线索链表。

声明：

typedef struct BTNode {

ElemType data;

struct BTNode *lchild;

struct BTNode *rchild;

}BTNode

静态链表存储：

二叉树的遍历：

定义：二叉树的的遍历( Traversal )是指沿某条搜索路径巡访二叉树，对每个结点访问一次且仅访问一次。

这里的访问是指对结点进行某种处理，包括：读、写、修改和输出结点信息。

作用：通过一次完整的遍历，可使二叉树的结点信息由非线性排列变为某种意义上的线性序列。

遍历种类：

由L D R，分别表示遍历左子树、访问根结点、遍历右子树，则可得到三种递归的遍历方法：

先序(根)遍历：

根左右

中序(根)遍历：

左根右

递归算法：

void preOrder(BTNode *T)

{

if (T != NULL)

{

visit(T->data);

preOrder(T->LChild);

preOrder(T->RChild);

}

void inOrder(BTNode *T)
{
if (T != NULL)
{
preOrder(T->LChild);

visit(T->data);
preOrder(T->RChild);
}
}

void preOrder(BTNode *T)
{
if (T != NULL)
{
preOrder(T->LChild);
preOrder(T->RChild);

visit(T->data);
}
}

后序(根)遍历：

左右根

特点：

以上三种遍历方法中，递归遍历左右子树的先后顺序是不变的( 即访问所有叶子结点的先后顺序完全相同 )，都是先左后右。

只是访问根结点的顺序不同，所以“序”指 根结点的访问顺序。

因为每个结点仅访问一次，故 二叉树的遍历时间复杂度都是O(n)。

二叉树递归遍历都需要借助工作栈，其中先序序列为入栈顺序，中序序列为出栈顺序。

递归工作栈的深度即为树的深度

递归算法和非递归算法的转换【借助栈】，即二叉树的中序非递归算法借助栈实现。

层序遍历：

定义：是指从第一层( 即根 )开始，按从上到下，每层从左到右的顺序对结点逐个进行访问。

特点：因上下层结点之间具有父子关系，所以在层序遍历中必然是先访问的结点，其孩子也先访问。

层序遍历借助队列实现。

遍历过程：设置一个队列（初始化为空）来保存待访问的结点( 已访问结点的孩子 )，首先将二叉树的根结点A入队，然后出队，visit访问出队结点（此时可对结点加操作），根A出完后，将其所有孩子入队BC；队头B出队，访问B，将B的所有孩子入队；C出队，访问C，将C的所有孩子入队。

简述概括：访问完一个结点，出队，入队其孩子结点。访问叶结点时，都不需要再入队。

层序遍历可推出：根结点（第一个），每一层都是左子树的根和右子树的根。

由遍历序列反过来构造二叉树：

由二叉树的先序遍历和中序遍历可以唯一地确定一棵二叉树。

由二叉树的后序遍历和中序遍历可以唯一地确定一棵二叉树。

由二叉树的层序遍历和中序遍历可以唯一地确定一棵二叉树。

由二叉树的先序遍历和后序遍历不能唯一地确定一棵二叉树，但可以确定二叉树中结点的祖先关系。

当两个结点的前序序列为XY，而后序序列为YX时候，则X为Y的祖先

例：前序ae bdc 后序bcd ea，所以a为根结点，e为a的孩子结点。

此时在a的孩子结点中，先序ebdc，后序bcde，可知e是bcd的祖先。

层序遍历可推出：根结点（第一个），每一层都是左子树的根和右子树的根。
中序遍历：利用层序遍历推出的根结点来分左右。

前序遍历可推出：第一个为根结点，然后在中序分出的左右子树中对应到第一个为子树根结点。
中序遍历：利用谦虚遍历推出的根结点来分左右。

后序遍历可推出：最后一个为根结点，然后在中序分出的各子树中最后一个为子树根结点。
中序遍历：利用后序遍历推出的根结点来分左右。

二叉树遍历的题型：

以先序序列abcd的不同二叉树共有多少个？

本题本质是求以序列 a b c d 入栈，可以得到多少个出栈序列。1/n+1 C2n n = 14。

该题是二叉树前序遍历和中序遍历的递归算法中，递归工作栈的状态变化得出。前序序列和中序序列的关系是：

相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序➕中序可以得出唯一的一棵二叉树。

某二叉树的前序序列与后序序列正好完全相反，则该二叉树一定是 只有根结点或单支树（只有左子树或只有右子树）即二叉树的高度等于结点数 h=n。

也意味着一个结点不可能同时有左右孩子。

即仅有N1

最后结点问题：

二叉树中序遍历的最后一个结点一定是从根开始沿着右子树指针走到底的结点。

二叉树前序遍历的最后一个结点

若不为叶子结点且左子树不为空，则前序遍历最后一个结点在其左子树中。

若为叶子结点则与中序遍历最后一个结点一样。

这类题简易做法：

前序与中序

非叶子结点：根左右，左根右。

看根左与左根，所以不一致。

叶子结点：根左右，左根右。

看最后面右，所以可能一致。最后想有没有特例。

中序遍历的最后一个结点一定是前序遍历的最后一个结点。

而前序遍历的最后一个结点不一定是中序遍历的最后一个结点。

即对于前序来说有左根和根左的区别。

同理补充后序与中序

三种遍历中唯一不变的是：都是先遍历左子树，再遍历右子树；就是因为遍历根结点的顺序不同才造就了二叉树前序、中序、后序的遍历。

因为访问左右子树顺序相同，因此访问叶结点的先后顺序也完全相同。

二叉树中有两个结点m、n，若m是n的结点，则使用 后序遍历 可得到m-n的路径。

删除二叉链表的所有结点，并释放存储空间最适合 后序遍历。

线索二叉树：

线索二叉树的引入背景：先来对比传统二叉树与线索二叉树：遍历二叉树后存储至传统二叉链表，其仅能体现一种父子关系，(即只能到孩子结点而不能回头访问双亲结点)，不能直接得到结点在遍历中的前驱或后继。

定义：利用空链域存放指向结点的直接前驱或后继的指针。这种附加的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。

规定：若某一结点无左子树，则令lchild指向其前驱结点，若无右子树，则令rchild指向其后继结点；

再增加两个标志域标识指针域，用以指向左右孩子或前驱后继。

标志域说明：

ltag = 0 lchild域指示结点的左孩子

ltag = 1 lchild域指示结点的直接前驱

rtag = 0 rchild域指示结点的右孩子

rtag = 1 rchild域指示结点的直接后继

⭐️作用：引入线索二叉树，就是为了加快查找结点前驱和后继的速度。这样就可以像遍历单链表那样方便、更快地遍历二叉树。

特点：线索二叉树是一种物理结构。线索二叉树即加上线索的二叉链表，还是属于链表，链表是链式存储结构。

二叉树是逻辑结构，所以线索二叉树是二叉树在计算机内部的一种存储结构。

对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。线索化的本质就是二叉树的遍历。

线索

线索二叉树的线索实际上指向的是 相应遍历序列特定结点的前驱结点和后继结点。

线索二叉树的存储结构：

typedef struct ThreadNode

{

ElemType data;

struct ThreadNode *lchild, *rchild;

int ltag, rtag;

}ThreadNode, *ThreadTree;

线索二叉树的题型：

空指针的计算：

设n个结点，共有2n个指针，用了n-1个，除根结点，2n-(n-1) = n+1 个空指针。

每个叶结点有2个指针，每个度为1的结点有一个指针，所以空指针= 2n0 + n1 ，又因为n0=n2+1，所以指针个数为：n0+n1+n2+1 = n+1。

不是每个结点通过线索都可以直接找到其前驱和后继。

总结：先序不好找前驱，后序不好找后继【不能有效解决此问题，其中双亲结点的前后驱未知，即此时线索帮不上忙，只能按常规方法全遍历所得】

先序线索二叉树中查先序后继很容易，而查先序前驱需要知道结点的双亲结点。

同理后序线索二叉树中查后序前驱也容易，查后序后继需要知道结点的双亲结点，二叉链表中没有存放双亲的指针。

一棵左子树为空的二叉树在先序线索化后，其中空链域有两个：左子树与最后一个结点。

x是中序线索树中一个有左孩子的结点，x不为根，则x的前驱是：为左子树的最右结点（并不是最右叶结点）（因为是中序）

前序、中序线索树遍历，通过指针（末层结点指向前驱后继），可以遍历整棵二叉树；而后序线索树从右结点末尾访问根结点时，存在右孩子而无指针直接指向父结点，从而无法完成二叉树的遍历。因此后序遍历还是需要栈的支持。栈——>递归

构造线索二叉树：

线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索。

所以线索化的过程就是在遍历的过程中修改中空指针的过程。可用递归算法。

对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序、中序和后序。

线索化的实质就是遍历一次二叉树。

设指针p指向当前访问的结点，指针pre指向刚才访问过的结点，由此记录下遍历过程中访问结点的先后关系。

例：以结点p为根的子树的中序线索化：

void InThreading (ThreadTree &p, ThreadTree &pre)

{

if(p)

{

InThreading(p->lchild) //左子树递归线索化

if( !p->lchild ) //如果p左孩子为空

{

p->ltag = 1; //为p加上左线索

p->lchild = pre; //p的左孩子指向pre（前驱）

}

else p->ltag = 0; //ltag=0表示有左孩子

if( !pre->rchild ) //如果pre的右孩子为空

{

pre->rtag = 1; //给pre加上右线索

pre->rchild = p //pre的右孩子指向p（后继）

}

else pre->rtag = 0;

pre = p; //保持pre指向p的前驱

（标记当前结点成为刚刚访问过的结点）

InThreading(p->rchild);//右子树递归线索化

}

建立中序线索二叉树：

void createThreadTree (ThreadTree T)

{

ThreadTreee pre = NULL;

if( !T=NULL )

{

InThreading (T, pre); //线索二叉树

pre->rchild = NULL; //处理遍历的最后一个结点

pre->rtag = 1;

}

优化：增加头结点，方便从前往后或从后往前遍历线索二叉树：

void createThreadTree (ThreadTree &head, ThreadTree T)
{

head = new ThreadTree; //建立头节点

head->ltag = 0; //若树非空，头结点左孩子为树根

head->rtag = 1; //头结点右孩子指针为线索

head->rchild = head; //初始化右指针

if( !T ) head->lchild = head; //若树为空，左指针也指向自己

else

{

head->lchild = T; pre=head; //头结点左孩子指向根，pre初值指向头结点

InThreading (T); //对以T为根的二叉树进行中序线索化
pre->rchild = head; //线结点索化后，pre为最右结点，指向头结点
pre->rtag = 1;

head->rchild = pre; //头结点的右线索指向pre
}
}

树🌲与森林🌳

树🌲、森林🌳与二叉🍴树的转换题型

只有满二叉树 的高度为h，对应的森林才包含h棵树。

在树转化为二叉树时，若有几个叶结点具有共同的双亲（比如三个两个，这几个还为叶子），则转换成二叉树后仅剩一个叶结点，即最右侧结点。

从3个叶结点——>仅剩1个叶结点。

上述问题可问：什么时候树的叶子数会等于其对应二叉树叶子数呢？

答：若树中任意两个叶结点都不存在相同的双亲，两边叶子数才有可能相等。

森林转化为二叉树后，二叉树的根结点及其左子树由第一棵树转化得到。

二叉树根结点的右子树由剩余森林组成，如图以此划分。

问：F——>B的过程中，F中有n个非终端结点/分支结点，则B中右指针域为空的结点有几个？

答：根据森林与二叉树的转换规则——左孩子右兄弟表示法，二叉树右指针域为空代表着该结点没有兄弟结点。

森林中，每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子（如上图）。因此最后一棵树的右指针为空。

另外，每个非终端结点，其所有孩子转化之后，最后一个孩子的右指针也为空，所以共计空指针个数：n+1。

问：孩子兄弟表示法中，存在6个空的左指针域，7个空的右指针域，5个结点左右指针域均为空，分别表示什么含义？

答：左孩子右兄弟法中，左指针域为空指结点没有孩子结点即6个叶结点，7个没有兄弟结点的结点，5个结点既没有孩子又没有兄弟。

x是树T的一个非根结点，B是T对应的二叉树，在B中，x是双亲结点的右孩子：表明x必是其双亲结点的右兄弟，换句话讲：x必有左兄弟。

在森林转化为对应二叉树的过程中

相当于用左孩子右兄弟表示法表示森林：

二叉树 B中的父子关系对应森林中关系是父子关系或兄弟关系。

已知树有2011个结点，其中叶结点个数116，则该树对应的二叉树中无右孩子的结点个数为：

2011-116+1=1896

此过程中树的每个分支结点n中最右结点无右孩子，根结点全部转换后也无右孩子。其数目：n+1

⌊log₂ n⌋

题型：

在二叉排序树中，如果先删除分支结点后再插入它，则会导致二叉排序树的重构，其结果与之前不再相同。

树与森林

树的存储结构：

树的存储要求既要存储结点的数据元素，也要存储结点之间的逻辑关系。能唯一的反映树中各结点之间的逻辑关系

树的常用三个存储结构：

双亲表示法：（顺序存储）

定义：用一组连续的存储空间存储树的所有结点，同时在结点中附加一个指示器(伪指针)，指示其双亲结点在数组中的位置。根结点下标为0，伪指针域为-1

特点：

该存储结构利用了每个结点( 根结点除外 )，只有唯一双亲的性质，可以很方便地找到任一结点的双亲结点。若无则找到了根结点。

双亲表示法容易找双亲，但若找结点的孩子时，需要从头到尾遍历整个结构。

应用：适合于找双亲多，找孩子少的情景——>并查集

注意：区别树的顺序存储结构与二叉树的顺序存储结构的不同：树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了各结点间的关系。

二叉树的顺序存储结构中，数组下标既代表了结点的编号，也代表了二叉树中各结点的关系。

当然二叉树属于树，所以可以用树的存储结构存储。但树不能用二叉树的存储结构。

孩子表示法：（顺序+链式存储）

定义：是指将每个结点的孩子结点用单链表链接，则n个结点有n个孩子链表，此时n个结点就有n个孩子链表（叶结点的孩子链表为空表），

这n个结点头指针即每一个双亲又构成一个线性表，以顺序结构存储。

特点：

孩子表示法容易找孩子，找双亲时需要遍历孩子链表。

应用：适合于找孩子多，找双亲少的情景——>服务流程树（如：客服系统）

孩子兄弟表示法：（链式存储）

定义：孩子兄弟表示法，又称二叉树表示法，二叉链表表示法。即以二叉链表作为树的存储结构。每个结点包含三部分：结点值；指向该结点的第一个孩子结点和下一个兄弟结点（沿此域可以找到该结点的所有兄弟结点）。分别命名：firstchild域，nextsibling域。转换成的BT 左孩子表示父子，右孩子表示兄弟。

特点：

孩子兄弟表示法容易找孩子。

例：若要访问结点x的第i个结点，只要先从firstchild域中找到第一个孩子结点，然后沿着孩子结点的nextsibling域连续走

i-1步，便可找到x结点的i孩子。

优点：最方便实现树转换成二叉树的操作。

缺点：是从当前结点找其双亲结点比较麻烦。若为每个结点添加parents域，则也能方便的查找到其双亲。

存储结构优化：

将双亲表示法与孩子表示法的优缺相结合，即给n个有孩子链表的n个结点加上伪指针指示其双亲在数组中的位置。

树、森林与二叉树的转换：

定义：由于二叉树与树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的对应关系。

特点：

给定一棵树，总可以找到唯一的一棵二叉树与树对应。

从物理结构来看，树与二叉树的二叉链表是相同的，只是指针拐个弯，解释不同。

根据树的二叉链表吧表示定义可知，任何一棵树对应的二叉树，其右子树必空。

树转二叉树的规则；每个结点的左指针指向它的第一个孩子，右结点指向它在树中的相邻右兄弟。——《左孩儿右兄弟》规则

由于根结点没有兄弟，所以所以对应的二叉树没有右子树。

题型：（画出）

树转二叉树：

层序处理，将结点所有孩子串成糖葫芦斜着放在其左子树。

二叉树转树：

层序处理，将结点左孩子串成的糖葫芦拆开，平放在此结点下方。

—————————————————————————————————————————————————————————————————————

森林转二叉树：

森林中各棵树的根结点为平级兄弟结点，将所有树的根用右指针串成糖葫芦斜着放。

然后再进行各棵树内部的树转二叉树。

二叉树转森林：

将二叉树根结点及其右子树糖葫芦串拆开作为森林内部多棵树的根结点。

然后在森林内部进行二叉树转树。

树和森林的遍历：

树的遍历（三种） 是指用某种方式反问树中的每个结点，且仅访问一次。

先根遍历：若树非空，先访问根结点，再依次遍历根结点的每棵子树。遍历子树时仍遵循 先根后子树 的规则。

== 对应二叉树的 先序遍历

后根遍历：若树非空，先访问根结点的每棵子树，再访问根结点。遍历子树时仍遵循 先子树后根 的规则。

== 对应二叉树的 中序遍历

层序遍历：按层序依次访问各结点。

森林的遍历 (两种)

先序遍历：

访问森林中第一棵树的根结点。

先序遍历第一棵树中根结点的子树森林。

先序遍历除第一课树之后剩余的树。

== 对应二叉树的 先序遍历

中序遍历：

中序遍历森林中第一棵树根结点的子树树林。

访问第一棵树的根结点。

中序遍历除第一棵树之后剩余的树。

== 对应二叉树的 中序遍历

题型：

一棵树转换成二叉树后，其左分支表示树中的孩子关系，二叉树的右分支表示树中的兄弟关系。

因为树根结点没有兄弟结点，所以对应二叉树没有右分支。

一棵树转成二叉树后，由于只有一棵树，所以根结点是没有右子树的；根据左孩子，右兄弟规则，得出转换成的二叉树是唯一的。

森林转二叉树的本质：相当于用孩子兄弟表示法表示此森林。

二叉树与森林的关系：森林中树的棵树等于其对应二叉树的的根结点及其右孩子(兄弟)数目。或丛根结点开始不断访问根结点右孩子。

k叉树，已知每个非叶子结点都有k个孩子，则称T为 正则k叉树。

若T有m个非叶子结点，问T有几个叶子结点？

n = n0 + nk

树中所含边数为e （这些边均是由这个m个非叶子结点发出的，所以e=m*k）

又因为 e = n-1 n=e+1 = mk+1 = n0+m

所以n0 = m(k-1)+1

若T的高度为h，则T结点树最多为？，最少为？

最多则为1 -> h-1为满二叉树，h层均为叶结点：公式h = log k [n *(k-1)+1] 得

n*(k-1) = k得h-1次 n=k得h-1次 / k-1。

最少结点的正则k叉树树形为：第一层一个根结点，第2-h层分别只有1个分支结点和k-1个叶结点，

h层有k个叶结点，故2 -> h 每层均有k个结点。所以n = 1 + (h-1)k

将森林F转换成对应二叉树T时，F中叶结点的个数 等于 T中左孩子指针为空的结点个数。

解：孩子兄弟表示法又叫 左孩子右兄弟表示法，森林中的叶结点因为没有孩子结点，当转换为二叉树时，该结点就没有左孩子结点。

子主题

解：因为看右子树，最右侧结点就是森林根结点。

一棵树中的叶子数在什么时候等于其对应的二叉树的叶子数？

解：在树转二叉树时，若几个叶结点具有共同的双亲，则转换成二叉树后就仅有一个叶结点。（即最右侧结点）

若树中的任意两个叶结点都不存在相同的双亲，树中叶子数才等于对应二叉树的叶子数。

利用二叉链表存储森林时，根结点的右指针可能为空，也可能不为空。

若森林只有一棵树，则根结点的右指针为空。

若森林中不只一棵树，根据树转二叉树，是用孩子兄弟表示法表示树得，根结点右指针不为空。根结点右指针指向森林中第二棵树的根结点。

F ——> B 若F中有n个非终端结点，则B中右指针域为空的结点有几个？

解：什么叫右指针域为空？

二叉树B右指针域为空代表着该结点没有兄弟结点。森林中的树从第二棵树开始连接在第一棵树的右子树

中，因此最后一棵树的根结点右子树为空。

同理，每个非终端结点，的孩子层序处理，转换后，最后一个孩子的右指针也为空。

综上：对应二叉树中无右孩子结点的个数 = 分支结点数 + 1.

在森林的二叉树中，若M、N是同以父结点的左儿子和右儿子，在在该森林中，M和N可能无公共关系。

n个结点的树，有n-1条边。

所以在一棵树中，结点总是比边数多一。引申至森林，结点数比边数多几，就是森林中包含几棵树。

子主题

程序 = 数据结构 + 算法

数据结构：如何用数据描述表示现实世界的问题，包括数值型问题，非数值型问题。

描述

算法：就树如何高效地处理数据，以解决实际问题。

处理

线性表

(Linear List)

定义：线性表是 相同数据类型 的n(n >= 0)个数据元素的有限序列

相同数据类型是指每个数据元素所占空间一样大

第 i 个是表示位序，从1开始。数组下标从0开始。

特点：

顺序表可以随机存取O(1)，插入和删除是O(n)
链式存储的查询是O(n)，插入和删除是O(1)
单链表只能单向按顺序查找

顺序表

定义：用顺序存储的方式实现线性表。顺序存储即把逻辑上相邻的元素存储在物理结构也相邻的存储单元中。

元素之间的关系可以由存储单元的邻接关系直接表现。

顺序存储的线性表中移动元素的次数

插入：(n + 0)n/2 * 1/n = n/2

删除：(n-1 + 0)n/2 * 1/n = (n-1)/2

以行序为主序的存储：(i-1)*j + j.
以列序为主序的存储：(j-1)*i + i.
注意⚠️数组是从0还是1开始，0则多加一行公式 i,j

在长度为n的顺序表第i个位置插入一个元素时，元素移动次数为n-i+1，即要移动该位置及其之后的所有元素

当已知顺序表中元素的查找概率时，为使查找成功的平均查找长度达到最小，则应交换表中元素次序，查找概率大的放在顺序表的前列

顺序表的实现：

静态分配：利用静态数组存储顺序表。数组长度一旦确定即不可改变

子主题

链表

考点

链式存储的定义和特点

单链表

线性表的链式存储结构称为链表。每个存储结点不仅包括结点本身信息，且饱含元素与元素之间的逻辑关系信息，分别称数据域与指针域。
链式存储设计时，各个不同结点的存储的存储空间可以不连续，但结点内的存储单元地址必须连续。

单链表：
单向性，单链表中只有一个指示直接后继的指针域（因此从某个结点出发只能顺着指针往后查找其他结点，若查找结点的直接前驱，则需重新从表头出发）。

单链表中访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)

单链表带头结点的优点：
1️⃣使链表首结点的插入和删除操作与其他结点一致。无需特殊处理。
2️⃣无论单链表是否为空，均有头结点，统一空表与非空表的处理过程。

头插法与尾插法：
头插法：是将新的结点插入到当前链表的表头上（插入在头结点之后，原开始结点之前）。形成一个“逆序”的序列。
s->next = L->next; L->next = s;
尾插法：是将新的结点插入到当前链表的表尾上（将s插入到r尾指针之后）。形成一个“顺序”的序列。
r->next = s; r=s; (原r 与现r)

带头结点的单链表：
空表： head->next == NULL;

不带头结点的单链表：
空表：head == NULL; //头指针直接指向第一个结点

双链表

双链表的结点中有两个指针域，一个指向直接后继，一个指向直接前驱。

优点：

双链表可以从任一结点出发可以快速找到某一结点的前驱结点和后继结点。

从任一结点出发可以快速访问其他结点。

双链表的头插法与尾插法：
头插法：
s->data = a[i]; //创建数据结点s
s->next = L->next;
if(L->next != NULL) //若L存在数据指针则需要修改前驱指针
L-> next->prior = s;
L->next = s;
s->prior = L;

尾插法：
r = L; //r始终指向尾结点，开始时指向头结点
s->data = a[i];
r->next = s； //将s插入r之后
s->prior = r;
r = s; //将r指向尾结点

双链表的头插法：
void CreatListF(DLinkNode *&L, ElemType a[], int n)
{
DLinkNode *s; int i;
L=(DLinkNode*)malloc(sixeof(DLinkNode)); //创建头结点
L->prior=L->next = NULL; //前后指针域置为空
for(i=0; i<n; i++) //循环建立数据结点
{
s=(DLinkNode*)malloc(sizeof(DLinkNode)); //创建s结点
s->data = a[i];
s->next = L->next;
if(L->next != NULL)
L->next->prior = s;
L->next = s;
s->prior = L;
}
}

双链表的尾插法：
void CreatListR(DLinkNode *&L, ElemType a[], int n)
{
DLinkNode *s, *r;
int i;
L=(DLinkNode*)malloc(sizeof(DLinkNode)); //创建头结点
r = L; //r始终指向尾结点，开始时指向头结点
for(i=0; i<n; i++)
{
s=(DLinkNode*)malloc(size(DLinkNode));
s->data = a[i];
r->next = s；   //将s插入r之后
s->prior = r;
r = s;               //将r指向尾结点
}
r->next = NULL; //尾结点next域置为空
}

循环链表

单循环链表：单循环链表的尾结点 next域指向头结点，使整个单链表形成一个环。

因此从表中任一结点出发，都可以找到链表中的其他结点。

有的单循环链表不设头指针，只设尾指针。
这是因为单循环链表有了尾指针之后 r->next 就转化为了头指针——>这样对表头表尾的操作就都成了O(1)。

单循环链表在实现约瑟夫问题时不需要头结点。

双循环链表：双循环链表的尾指针next指向头结点，而头指针的prior指针指向尾结点，这样使整个双链表形成两个环。

因此从表中任一接结点出发，都可以找到链表中的其他结点。

静态链表

静态链表是利用一维数组去描述一个线性链表。

与指针型描述的线性链表有所不同。

静态链表类型说明：
#define MAXSIZE 1000
typedef struct
{
ElemType data;
int cur;
}component, SLinkList[MAXSIZE];

静态链表的整形变量cur便于在不设“指针”类型的高级程序语言中使用链表结构。这样数组的一个分量表示一个结点，游标（指针域cur）代替指针用以指示结点在数组中的相对位置。
数组的0结点看成头结点，其指针域指示链表的第一个结点。

静态链表结构需要预先分配一个较大的存储空间，但在做线性表的插入和删除操作时不需要移动元素，只需要修改指针，故仍具有链式存储结构的主要优点。

题型总结

单链表

给不带头结点的单链表的头上插入一个新结点，相当于无头结点的头插法：
将t的下一结点指向h，然后将t改为新的头结点。
t->next = h; h=t;

一个单链表中，有头尾两个指针，执行什么操作与链表的长度有关
删除第一个元素。删除最后一个元素。在第一个元素前插入一个元素。在最后一个元素后插入一个元素。
单链表中想找到最后一个元素只能按顺序遍历。

单链表中删除时候：先存再删

当删除最后一个结点时候要进行特处：if(p == q) p=h;

p是尾指针，p=q就表示要删除的是尾结点，所以在删除尾结点后，要将尾指针指向头结点。

以单链表方式存储的队列，在进行删除时候一般只用修改队头指针即可，但有一种情况就是出队以后是空队列了，

需要修队尾指针以对准队头指针。所以链队列的删除运算时，头尾指针都有可能修改。

如删除链表的第一个元素：【先存后删】
【p尾指针，q临时指针存待删结点】
q = h->next;
h->next = h->next-next； (h->next = q->next;)
if(p==q) //p=q的含义是，待删除结点事尾元素时候
p=h; //将尾指针指向头结点
free(q);

删除链表的第一个元素时（带头尾指针）：h,p,q 头尾临时指针
1️⃣存 2️⃣删 3️⃣若p q指向同一个位置4️⃣将p指向头结点5️⃣释放第一个元素
q = h->next; h->next = h->next->next; if(p==q) p=h; free(q);

两个升序合并为一个降序链表：最坏情况下的时间复杂度：
逆置mn中最长的链表，对上另外一个链表的逆序就行O(max(m,n))

若用单链表来表示队列，则选用带尾结点单循环链表来实现表头出队（删除），表尾入队（插入）。

给定n个元素的一维数组，建立一个有序单链表的最低时间复杂度是：O(n*log2n)

先建表，后依次插入建立有序表 O(n的平方)

先排序，后依次建表 O(n*log2n)

所有单链表，不管是循环单链表还是有尾指针的单链表，在删除尾结点时要十分注意！O(n)。因为删除结点后需要找到其前驱，将尾指针指向尾结点前驱。

所以删除表尾元素的时间复杂度与与表长有关。

注意⚠️所有的删除都要找到删除元素的前驱

只要是单链表删除结点都需要格外注意

若用单链表来表示队列（队列：队尾插入，队头删除），所以用带尾指针的循环单链表。

两个单链表的拼接：将长度为n的链接在长度为m的单链表之后时间复杂度为：其实就是找到m链表的尾指针，然后将其指向n头结点即可。

线性表a0--a100中，删除a50需要移动多少个元素？

答：0 / 50个，因为题干中给的是线性表，没说是顺序存储还是链式存储

双链表

删除p指针：【先连p的前驱，后连p的后继】
p->next->prior = p->prior; p->prior->next = p->next

*p之后插入*s：

先处理待插入结点的后继，再处理后一结点的前驱；
然后处理前一结点的后继，再处理待插入结点的前驱。
s->next = p->next; p->next->prior = s; p->next = s; s->prior = p;
1️⃣ ——> 2️⃣ <——
3️⃣ ——> 4️⃣ <——

先处理待插入结点的前驱，再处理待插入结点的后继；
然后处理前一结点的后继，再处理后一结点的前驱。
s->prior = p; s->next = p->next; p->next = s; s->next->prior = s;
1️⃣ <—— 2️⃣ ——>
3️⃣ ——> 4️⃣ <——

先处理待插入结点的前驱，再处理待插入结点的后继；
然后处理后一结点的前驱，再处理前一结点的后继。
s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;
1️⃣ <—— 2️⃣ ——>
3️⃣ <—— 4️⃣ ——>

*p之前插入*q：

先处理前一结点的后继，再处理待插入结点的后继；
然后处理待插入结点的前驱，再处理后一结点的前驱
p->prior->next = q; q->next = p; q->prior = p->prior; p->prior = q;
1️⃣ ——> 2️⃣ ——>
3️⃣ <—— 4️⃣ <——

循环链表

单循环链表

非循环链表可以没用头结点，有头结点只是更好，操作一致
循环链表必须要有头结点，否则循环没有意义，找不到循环的头了（没有腰带扣啦）

单循环链表的主要优点：从表中任一点出发都能扫描遍历到整个链表

单循环链表的判空条件：head->next == head;

单循环链表的判空条件：L->next == L 【翻译过来就是头结点的指针域与 L的值相等。而不是与L的地址相等】

某线性表常用的操作是：
在最后一个结点后插入一个新结点或删除第一个元素最适合用：带有尾指针的单循环链表
在最后一个结点后插入一个新结点或删除最后一个结点宜采用：双向链表

要实现在链表末尾的插入和删除操作，最好选用？

其实问题的核心就是要访问被删除结点以及被删除结点的前驱。

这样的话带尾结点的单循环链表还不够，因为带尾指针只是能更快的访问到尾结点，访问到尾结点的前驱还需要再遍历一圈。

所以选用带头结点的双循环链表即可，这样从头结点出发到过来访问尾结点以及其前驱。

带头结点的双循环链表好万能。

若删除循环单链表的首元结点所花费的时间为O(n)，则判断该结构是带头结点还是不带头结点，带不带尾指针？

如果是带头结点，要找到被删除结点的前驱结点。首元结点即第一个数据结点，

所以其前驱正是头结点，此时带带头/尾指针找到前驱都是O(1)。

如果是不带头结点，首元结点的前驱就是链表的尾结点。

所以带头指针的找前驱是O(n)，带尾结点的不带头结点的找前驱是O(1)。

某线性表用带头结点的循环单链表存储。头指针为head，当head->next->next == head成立时，线性表的长度可能为？

0或1

这时需要记得特处。因为题干没有说明是否为空，因为空链表也合适此代码。

head->next 就是首元结点，首元结点的next抱住头结点。

线性表为空时，长度L为0。线性表有了首元结点后，长度L就是1。

双循环链表

双循环链表的插入与删除。

在双链表中必须带头结点，带头结点的双链表可以在表中迅速找到任意位置 != 随机存取

双链表最突出的特点是：访问前后相邻结点更加灵活、便利。

静态链表

定义：静态链表是使用一维数组实现的链式存储结构

一维数组还能实现很多结构：栈，树，图

特点：整体需要分配较大的连续的存储空间。
适合插入、删除操作，不需要移动大量元素。
静态链表一旦定义，其容量固定不变。
还是不适合随机存储哈

会造成浪费现象

顺序存储与链式存储的对比

顺序存储结构只能通过其物理上的顺序邻接来体现逻辑结构

链式结构使用的是指针，指针的创建与设置比较万能，代表性强故可更方便的表示各逻辑结构

顺序表可以用以为数组表示，所以顺序表与一维数组在逻辑结构上相同？

答：顺序表的三大特点：有限；数据类型相同；必须连续存储。而一维数组可以不用连续存储。

且栈，队列，树都可以用一维数组表示。

线性表的顺序存储结构是一种随机存取的存储结构。

存取方式是指读/写方式，顺序表支持随机存取，根据起始地址+元素符号，可以很方便的访问任何一个元素。

串

串的定义：

字符串简称串，串，是由零个或多个字符组成的序列。是线性结构，也是一种特殊的线性表。

S=“String177”，S是串名，“ ”‘ ’括起来的是串值，串中字符的个数n是串长，n=0是空串。

子串：串中任意多个连续的字符组成的子序列称为该串的子串。

主串：包含子串的串。

某个字符在串中的序号称为该字符在串中的位置。

空格串！= 空串，由一个或多个空格组成。

串与线性表的区别：

1️⃣两种数据结构所操作的数据对象不同：串——>字符集，线性表——>数据种类多。

2️⃣串的基本操作以子串作为操作对象。

线性表的操作以单个元素作为操作对象。

串的存储结构：

定长顺序存储表示：

舍弃0号位的定长数组 +最后用len变量标记串长度。

块链存储表示：

采用链表的方式存储，每个结点存储多个字符，若最后一个结点未满，就填入 # 补足。

串的基本操作：

求子串 SubString（&sub , S , pos , len）

用sub返回串s第pos个字符起长度为len的子串

串定位 Index（S, T）

若主串S中存在与串T值相同的子串，则返回它在主串第一次出现的位置。

串比较 StrCompare（S, T）

S>T，返回值>0

S=T，返回值=0

S<T，返回值<0

串连接 Concat（&T, S1, S2）

用T返回S1，S2连接而成的新串。

求串长 StrLength（S）

返回串S的元素个数

串的模式匹配：

串的模式匹配：在主串S中，查找是否存在子串T；若存在，则返回T得位置Index

BF算法朴素模式匹配算法：——O(m*n)

KMP算法：——O(m+n)

KMP算法Pro：

图

图的基本概念：

定义：

图由结点的有穷集合v和边的集合E组成。为与树形结构区别，在图结构中将结点称为顶点。

边是顶点的有序偶对。若两顶点之间存在一条边，则表示这两个顶点具有相邻关系。

有向图/无向图

已知图有n个顶点

对于无向图：最多有n(n-1)/2条边。

此时为无向完全图。

对于有向图：最多有 n(n-1) 条边。

此时为有向完全图。

无向图的连通分量：找极大连通子图。

无向图的生成树：找极小连通子图【显然无环】。

路径与路径长度

路径定义：路径是顶点和相邻顶点序偶构成的边所形成的序列。

路径长度是指路径上边的数目。

简单路径：顶点序列中，顶点不重复出现的路径。

连通分量与强连通分量

连通分量：无向图中极大连通子图。

强连通分量：有向图中极大强连通子图。

强连通分量是极大连通子图，即任意两个顶点之间有方向相反的两条路径。

根据以上定义可得：若一个顶点只有出边或入边，则该顶点必定单独构成一个强连通分量。

其余任意两个顶点间若有两条方向相反的路径，所以可以构成另外一个强连通分量。

何为极大：极大就是无法再大，包含所有顶点而无法继续扩展顶点。得到可从一点出发向所有与其相邻顶点。

若图本来就不连通，那么每个子部分若包含其本身所有顶点和边，其就是极大连通子图。

图之习题：

【图中至多至少

的题最关键的

就是找临界值】

已知无向图有n个顶点

若使无向图连通(连通图)，不形成环，则至少需要 n-1 条边。

即无向连通图的最小边数，若e<n-1，则一定不连通。

n=6，确保为一个连通图需要几条边：C52+1 / n*(n-1)/2 = 10条

先让五个顶点构成一个完全无向图+一条边称为连通图

n = 51, e = 21，求此无向图连通分量最多为？

已知有向图有n个顶点

若是强连通图，则至少需要 n 条边

顶点的度最大可达：2n-2

有向图中顶点的度 = 出度+入度，一个顶点可与n-1个顶点建立联系 = 2n-2

无向图：

非连通图的最极端情况：由一个完全图+一个独立顶点构成。

问由28条边的非连通无向图至少有几个顶点？

n(n-1) = 28*2 n=8,8+1

无向图边数的2倍等于各顶点度数的总和。4*3 + 3*4 + 2x = 2e。

有向图：

强连通有向图的任何顶点到其他所有顶点都有路径，但不一定有弧。

有向完全图一定是强连通有向图

具有n个顶点的图是一个环，则它有几棵生成树？

找最小连通子图：边尽可能少，且连通则无环，所以n随便去掉一条边就是一棵生成树，共有n中情况

图与树的区别是逻辑上的区别，不是边数上的区别。

图的遍历就是从某一顶点出发，访问图中其余顶点的过程，要求每个顶点只能被访问一次，允许若图非连通，五法访问到顶点。

在图中涉及到树，一定会用的等式：e + 1 = n。

图的存储

邻接矩阵法：

邻接矩阵的实现：
二维数组，存储图中边的信息。（各顶点之间的邻接关系）
一维数组，存储图中顶点信息。

无向图：1表两个顶点相互邻接，0表两个顶点相互不邻接。一条边对应两个1
有向图：1表单向存在，1对1，一条边对应一个1。

在邻接矩阵中求取度、入度、出度：

无向图：邻接矩阵第i行 / 第j列非零元素个数。

有向图：【列入行出】
邻接矩阵第i行非零元素个数表出度OD(vi)
邻接矩阵第j列非零元素个数表入度ID(vi)

特点：

邻接矩阵存储属于 顺序存储。

适合存储稠密图（边数较多的图）。

邻接矩阵顶点边一旦确定，对应的邻接矩阵便已确定唯一。

邻接矩阵的顶点数等于整个矩阵的行数(或列数)

无向图：

无向图邻接矩阵必然是 对称矩阵，存储只用存一半，存上/下三角元素。

的边数等于矩阵中非零元素的个数的1/2。边数一定是偶数。

无向图的度 等于第i行或第j列的非零元素之和。

各顶点的度是矩阵中此结点(对角线的每个点) 对应的行或列的非零元素之和。

有向图：

有向图邻接矩阵可以是非对称矩阵，存储只用存一半，存上/下三角元素。

的 弧等于矩阵中非零元素的个数。

边数可以为奇数。

有向图的度 等于列入行出，列入度 + 行出度 = 第i行和第j列的非零元素个数之和。

各顶点的度 是矩阵中此结点(对角线的每个点) 对应的行和列的非零元素之和。

空间复杂度：O(n2) n为图中顶点个数|v|。

在不考虑压缩存储的情况下，存储空间大小为O(n2)。

找到顶点邻接边的时间复杂度：遍历行列O(n)。

判断两个顶点是否存在边时间复杂度：O(1)。直接看表即可。

计算：

An[i][j] 表示从顶点 i-j 的长度为 n 的路径数目。

无向图：含n个顶点e条边的无向邻接矩阵中，零元素个数是：矩阵大小n2，边条数2e，所以零元素个数n2 - 2e。【有向图中零元素n2-e】

邻接矩阵对角线以上(或以下)，的元素全为0，则图中必然不存在环，即拓扑排序必定存在，但不唯一。

邻接表法：

邻接表的实现：

顶点表：顶点数据域 data ➕ 边表头指针域 firstarc（指向第一条边度边表结点）
边表结点：邻接点域与该顶点邻接的顶点 ➕ 指针域 nextarc（指向下一条边的边表结点）

存储无向图：将每条边视为两条方向相反的有向边，因此需要存储两次。

存储有向图：一条边表示一个方向的有向边，存储一次。

在邻接表中求取度、入度、出度：

无向图：度：遍历邻接链表的边表结点个数。

有向图：出度：邻接表边表结点的个数。

入度：难求，遍历所有邻接表，看谁指向x。

邻接表法特点：

邻接表法属于 顺序存储 + 链式存储。

适合存储稀疏图（边数较少的边）。

一个图的邻接表表示法不唯一，因为在每个顶点的边表中，边的顺序不唯一。

空间复杂度：

无向图：O(|v|+2|E|)

因为每条边在邻接表中出现了2次。

有向图：O(|v|+|E|)

找到顶点邻接边的时间复杂度O(1)。直接读取邻接表即可。邻接表中很容易找到顶点所有邻边。

判断两个顶点是否存在边比较慢，因为需要再找到另一个顶点，再查看其对应边表中的边结点。

比如此时执行删除操作，效率低。

基本操作应用：

判断图是否有边：O(1)

题型：

无向图：

n个顶点的无向图的邻接表最多有几个边表结点：

想，因为是最多，所以一个点向另外n-1个结点相连，第2个，n-2，所以(1+n-1)*n-1 / 2 这么多条边。

因为求边结点，无向图邻接表中每条边存储两次，所以*2。

无向图的邻接表中，第 i 个顶点的度 = 第 i 个链表中结点数。

有向图：

有向图的邻接表存储中，顶点v在边表中出现的次数是：顶点v的入度。

因为任何顶点表对应的边表中存放的都是以顶点u为起点的边所对应的另一个顶点v。

从而v在边表中出现的次数也就是v的入度。

删除有向图邻接表中与边结点v相关的所有边：

删出边，遍历v的顶点结点对应的单链表，边数最多n-1，O(n)。

删入边，需要遍历整个图边，包括顶点表与边表，找谁指向它，O(n+e)

十字链表法：

定位：

十字链表法是有向图的链式存储结构：——>解决邻边表法入度不好找的问题

十字链表的组成：

十字链表中，有向图的顶点，每条弧都用一个结点来表示。一个是弧结点，一个是顶点结点。

顶点结点：（3个域）
data数据域，存放该顶点的数据信息。
firstin域，指向以该顶点为弧头的第一个弧结点。【可以找到所有指向本顶点时的弧】
firstout域，指向以该顶点为弧尾的第一个弧结点。【一直向后找可以找到从该点发射的所有弧】

弧结点：（5个域）
tailvex弧尾顶点，headvex弧头顶点；hlink头链域指向弧头相同的下一个弧结点；tlink尾链域指向弧尾相同的下一个弧结点；info域存放该弧的相关信息。
(如此排布，弧头相同的弧在同一个链表上，弧尾相同的弧也在一个链表上)

十字链表法特点：

顶点结点是顺序存储的。

十字链表中，既容易找到以vi为尾的弧，又容易找到以vi为头的弧。所以顶点的入度和出度极为好找。

图的十字链表表示法 不唯一。但一个十字链表唯一的确定一张图。

十字链表时间复杂度：O(|V|+|E|)

只存储有向图。

基本操作应用：

判断图是否有边：O(1)～O(|v|)

邻接多重表：

定位：

无向图的链式存储结构：——>解决邻接矩阵空间度太高以及每条边对应两份冗余信息，删除顶点或边等操作复杂度高

邻接多重表的组成：

邻接多重表中，每条边用一个边结点表示，还有顶点结点：

顶点结点：（2个域）
data数据域，存放该顶点的相关信息。
firstedge域，指向第一条依附于该顶点的边。

边结点：（5个域）
ivex，jxex域指向与该边相连的两个顶点；
ilink域指向下一条与ivex顶点相连的边，jlink域指向与jvex顶点相连的边；
info域存放该边的相关信息。

最后可以增加一个mark标志域：标记该条边是否被搜索过。

邻接多重表的特点：

邻接多重表中，所有依附于同一结点的边串联在同一个链表中。

因为每条边依附于两个顶点，所以每个边结点同时出现在两个链表之中。

邻接多重表与邻接表的差别：
同一条边在邻接表中用两个结点表示，而在邻接多重表中，只用一个边结点表示。

找与某一顶点相连的边上非常方便的，且一条边只用一个边结点表示

所以删除边，删除结点等操作非常方便。

邻接多重表的表示方式也是不唯一。

邻接多重表的空间复杂度：O(|v|+|E|)

只存储无向图。

图的基本操作

图的遍历

深度优先算法：DFS

类似于树的先序遍历，优先访问当前结点，随后访问其相邻结点，并对该邻居结点继续执行DFS。在整个图的遍历过程中，使用visited[]数组记录结点是否被访问过（因为图不像树能一直往下走而不重复，图这样任意走就可能会走重复）所以需要数组记录。true/1表已经访问过，false/0表没有。

访问步骤：

1️⃣从起始结点开始，将其标记为已访问。

2️⃣检查当前结点的所有未访问邻居结点，选择一个并将该结点作为一个起始结点，继续执行深搜。

3️⃣如果当前结点没有未访问过的邻居结点，则回溯至上一个结点——从哪里调用的回哪里。

重复执行123，直到所有可达到的结点都已经访问。

选择的时候往深去选。由访问步骤可知，DFS是一种递归的算法，需要借助函数递归栈。

若对一个非连通图，则需要从多个顶点开始深度搜索。

算法分析：

时间复杂度：

邻接矩阵：O(n2)

邻接表：O(n+e)

空间复杂度：

邻接矩阵：O(n) —— 借助递归工作栈+visited[]数组=2O(n)

DFS算法的应用：

判断图的连通性。

判断图中是否存在回路。（包括无向图与有向图）

对于无向图来说，若DFS过程中遇到了回边，则一定存在环。

对于有向图来说，在DFS过程中遇到的回边不一定是射回本源点，可能是指向深度优先森林中另一棵生成树

上的顶点的弧。若在DFS(v)结束之前，出现一条从u- v的回边，且u在生成树上是v的子孙，则此时，有向图

必定存在包含顶点v和u的环。

欧拉回路求解。

广度优先算法：BFS

类似于树的层序遍历，即访问完当前结点后，优先把其 所有的 相邻结点全部访问完。

实现广度优先搜索需要借助一个队列Q，Q用来暂存邻接点信息。

访问步骤：

1️⃣访问起始顶点V，输出V，标记V为已访问，将V加入至队列Q。（输出v，标记v，入队v）

2️⃣若队列Q不为空，则出队队首顶点v，依次访问v未被访问过的邻接结点，并将这些顶点入队。

3️⃣重复步骤2，直至队列为空。

算法分析：

时间复杂度：

邻接矩阵：O(n2)

邻接表：O(n+e)

空间复杂度：O(n) ——>包括辅助队列Q && visited[]数组。

会发现BFS算法的时空复杂度其实与DFS的相同。而不同之处仅仅在于对顶点的访问顺序不同。

DFS是一次尽可能挖的深，BFS是一次尽可能把该顶点所有的邻接点访问了。

BFS算法的应用：

找单源最短路径。

BFS判无向图是否有环。

BFS无法判有向图是否有环。

注意⚠️：

1️⃣广搜BFS，以起始点为中心，一层层向外扩展遍历图的顶点。因此无法考虑到边权值。
只适合求边权值相等的图的单源最短路径。

2️⃣DFS，BFS可以用来计算图的连通分量数。——因为一次遍历必然会把一个连通图的所有顶点访问到，已访问过的则不调用DFS。故连通分量数正好是DFS被调用次数。

3️⃣广搜是起点到其他顶点的路径是图中的最短路径，即所有生成树树高最小。

深搜是尽可能深地搜索地图，因此其路径也尽可能的长。所以深搜的树高总是≥ 广搜的树高y汉尼拔

图的应用

求最小生成树：（最小代价树MST）

普里姆挑点 —— 挑代价最小的点，收归自己。

克鲁斯卡尔挑边 —— 优先连通代价最小的两边的顶点。

求最短路径：

查找

树形查找

二叉排序树 BST树：

目的：构造二叉树的目的，不止于排序；而是为了提高查找、插入和删除关键字的速度。

定义：二叉排序树又称二叉查找树，（可以为空），特点是：

若左子树非空，左子树上所有结点值均小于根结点值。

左右子树递归的成为新二叉排序树。

总：左子树结点值 < 根结点值 < 右子树结点值。

所以对二叉排序树进行中序遍历 可得到一个递增的有序序列。

插入：

二叉树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字 = 给定值的结点时再插入的。

插入规则：

if（二叉排序树 = NULL）

直接插入；

插入关键字k

if（k<根结点值）

插入到左子树；

else 插入到右子树

构造：从一棵空树出发，依次输入元素，将他们插入二叉排序树中的合适位置的过程。

删除：

在二叉排序树中删除一个结点。⚠️

删除规则：

if（待删除结点为叶子结点）

直接删除，且不会破坏二叉排序树性质；

else if（待删除结点a只有一个左子树或右子树）

让a结点的子树成为a夫结点

else if（待删除结点有左右两子树）

令a的直接后继（或直接前驱）替代a

1️⃣以该结点 左子树的 最右(大)侧结点（直接前驱）替代。
2️⃣以该结点 右子树的 最左(小)侧结点（直接后继）替代。

二叉树的查找效率分析：

BST查找效率主要取决于树的高度。

递归次数——时间复杂度——查找长度——一定不会超过树的高度（最差=树高）

平均查找长度：O(log2n)

最坏单支树：O(n)

ASL计算：

ASL成功：层数 * 层数上结点个数 / 总结点数n⭕️

ASL失败：每层 * 空链域 / 方块个数♦️

查找评价：二叉排序树与二分查找区别与联系：

二分查找的判定树唯一。
二叉排序树的查找不唯一，即相同的关键字，其插入顺序不同，可能会产生不同二叉排序树。

插入和删除的时间复杂度：

二分查找针对的是有序顺序表，插入删除O(n)。

二叉排序树无须移动指针，只需修改指针即可完成插入删除删除：O(log2n)。

选用方法：

当有序表是静态查找表时，宜采用顺序表作为存储结构，采用二分查找。

当有序表是动态查找表，宜选择二叉排序树作为其逻辑结构。

平衡二叉树 AVL树：

目的：避免树的高度增长过快，降低二叉排序树的性能。

定义：规定在插入和删除结点时，要保证任意结点的左右子树高度差的绝对值不超过1，那我们把这样的二叉树称为平衡二叉树（Balanced Binary Tree）。

并定义结点左右子树的高度差为该结点的平衡因子。所以平衡二叉树的平衡因子只可能是-1 (左低右高)，0，1。结点中的数字表示该结点的平衡因子。

插入：⚠️学会插入调整

平衡二叉树的插入过程前半部分与二叉排序树插入相同，只是在新结点插入后，若造成查找路径上某个结点不再平衡，则需做出微调调整。

调整的规律包括4种情况。每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值>1的结点作为根的子树。

调整规律：

LL平衡旋转：【右单旋转】

是指在一棵树的左孩子的左子树上插入新结点，这样对于根A来说左孩子过长，A平衡因子变为2，所以A需要降幂右移，原A左孩子升幂继承王位，成为新的根结点；此时B的右孩子多了，就给了A当孩子，相当于把B的后继给了A当前驱，这样能保证有序

RR平衡旋转：【左单旋转】

是指在一棵树的右孩子的右子树上插入新结点，这样对于根A来说右孩子过长，平衡因子变为-2，所以A需要降幂左移，原A右孩子升幂继承王位，成为新的根结点；此时B的左孩子多了，就给A当右孩子，即相当于把B的前驱给了A当后继，保持有序。

LR平衡旋转：【先左后右双旋转】

是指在一棵树的左孩子的右子树上插入新结点，这样对于根A来说左孩子过长，A平衡因子变为2，所以A需要降幂右移，刺头孙子先升幂父亲丞相之位，再升幂继承爷爷王位；此时刺头孙子只能自己继承王位，其左孩子让父亲B管，右孩子让爷爷A管，即相当于把C的前驱给了B当后继，把C得后继给了A当前驱，来保持有序。

RL平衡旋转：【先右后左双旋转】

是指在一棵树的右孩子的左子树上插入新结点，这样对于根A来说右孩子过长，A的平衡因子变为-2，所以A需要降幂左移，刺头孙子先升幂父亲丞相之位，再升幂继承爷爷王位；此时刺头孙子只能自己继承王位，其左孩子让爷爷A管，右孩子让父亲B管，即相当于把C的前驱给了A当后继，把C的后继给了B当前驱，来保持有序。

注意：⚠️

LR 和 RL旋转时，新结点是插入C得左子树还是右子树不影响旋转过程。

LR 和 RL旋转时，AB接收C孩子后，总是右面比左面高1。

构造：

一般是给定关键字序列{2，3，4，5}，来构造一棵平衡二叉树。

删除：

删除操作，先对以z为根的子树进行平衡调整，若调整后子树高度-1，则可能需要对z的祖先结点进行平衡调整，甚至回溯到根结点（最终导致树高-1）。

查找：

平衡二叉树的查找过程与二叉排序树的相同，因此，查找过程中关键字的比较次数不超过树的深度。

构造平衡二叉树的最大深度为O(log2n)，因此平均查找效率为O(log2n)。

红黑树：

目的：为了保持AVL树的平衡性，会非常频繁地调整全树整体拓扑结构，代价相对比较大。所以在AVL树平衡标准上进一步放宽条件，引入红黑树结构。

B树：

B+树：

排序

定义：重新排列序列中的元素，使之按照关键字递增或递减有序排列。

特性：

排序算法的 稳定性：在排序过程后，关键字相等的元素次序保持不变。
一般来说，交换色两个紧挨着的元素交换，则为稳定的。
稳定性只是排序算法的一个特性，排序算法的评价指标依然是：时间与空间复杂度。

插入排序：

排序类型：

直接插入排序：

一个一个从前往后比，直到去了合适位置。

适用于顺序存储 + 链式存储。

稳定

哨兵💂插入排序：

0号位，放置待排元素。

适用于顺序存储 + 链式存储。

稳定

折半插入排序：

⚠️：折半排序只是减少了比较次数，而元素的移动次数还是和直接插入一样“埋坑法”，所以最好是O(n*log2n)，最坏是（On2）,平均一下就又是O(n2)。

仅仅适用于顺序存储。

稳定

希尔插入排序：🚩【会手算】

希尔排序思想：增量构成的序列形成子列（一般下设3个增量d1=5、d2=3、d3=1），在子列内进行直接插入排序。

直接插入排序算法的改进。

仅仅适用于顺序存储。

不稳定

排序评价：四个排序算法的时、空复杂度都一样

对任意具有n个关键字的序列，至少要进行几次关键字之间的两两比较。

log2(n!)

交换排序：

冒泡排序：

算法思想：从前往后（或从后往前），两两比较相邻元素，每一趟排序会把序列中 最小元素交换至序列最前方形成有序序列，且不参与之后的排序过程。

算法评价：

空间复杂度：O(1)。

时间复杂度：O(n2)。

稳定

快速排序：

算法思想：基于分治法，选表头元素作为枢轴(基准)元素，通过一趟排序将排序表划分为两个独立的部分，然后再对两个独立的部分继续递归快排，直至每个部分只有一个元素或为空为止。

注意⚠️：

划分的过程就是重新排列组合元素的过程，使得形成“左中右”比枢轴元素小的放枢轴元素之前，比枢轴元素大的放枢轴元素之后。——此过程可以用“填坑法”来描述；也可用二叉树描述快排的递归调用过程。

一趟快速排序，指的是将数组中所有元素全部访问一遍。

每一趟排序完，至少能确定一个元素的最终位置。

一趟排序一定能确定一个元素最终位置。两趟排序一定要确定三个元素位置，除非第一趟排序分的得两个子表之一为空——在边缘。

算法评价：

空间复杂度：O(log2n)。—— 递归调用栈 = 递归二叉树树高h = 快排所需趟数。

时间复杂度：O(n*log2n)。

不稳定

快排冒泡排序的改进，是所有内部排序算法中，平均性能最优的排序算法

选择排序：

简单选择排序；

算法思想：每趟排序从待排序列中选择“最小/最大”的元素，放入有序序列的末端。

特点：

元素间比较次数与序列的初始状态无关，始终是n(n-1)/2次。

算法评价：

空间复杂度：O(1)。

常数个辅助单元。

时间复杂度：O(n2)。

不稳定

简单选择排序可适用于顺序存储 与 链式存储 的线性表。

适用于 关键字较少 的情况。

堆排序：

算法思想：

先建堆，大根堆/小根堆；再根据大小根堆进行堆排序。

思路：把所有 非终端结点 都检查一遍，看是否满足大根堆的要求（即根≥左、右），若不满足，则需要进行堆调整。

所以在顺序存储的完全二叉树中，从后往前检查非终端结点编号为 i≤」n/2」的结点 。
堆调整：
若分支结点不满足大根堆特性，则将当前结点与更大的一个孩子互换。

简称：小元素不断下坠的过程。

其中，顺序存储结构：

建立堆后，如何基于堆实现堆排序呢

根据选择排序算法思想：
堆排序：是指每一趟将堆顶元素加入到有序子序列中。（将堆顶元素与带排序序列中的最后一个元素交换）
相当于将堆顶元素放置末尾，不参与后续排序，形成有序序列。

相当于，一边扫描是否满足堆排序规范，一边对堆进行调整。

第一趟处理包括，把最大的元素移到末尾，然后把剩余的元素恢复成大根堆的规范。

第二趟继续将堆顶元素与待排序序列中最后一个元素交换，移动至末尾，继续将剩余元素恢复成大根堆。

同样，n个元素，需要n-1趟处理。

特点：

大根堆：根≥左、右

小根堆：根≤左、右

基于大根堆的堆排序可以得到“递增序列”。将堆顶最大值放至末尾。

基于小根堆的堆排序可以得到“递减序列”。将堆顶最小值放至末尾。

堆调整时，若左右两个孩子一样大，则优先与左孩子交换。

建堆时间复杂度：O(n)。

调整堆时间复杂度：每调整一层最多需要比较2次【看成常熟级了】，一共1～h-1层需要调整。

堆排序时间复杂度 = 建堆*堆调整 = n*h=n*log2n 的时间复杂度。

考频超高的排序算法。

因为这个堆算法内容包含十分丰富。

算法评价：

空间复杂度：O(1)。

时间复杂度：O( n*log2n )。

不稳定

堆排序仅适用于 顺序存储 的线性表。

适用于 关键字较多/超多 的情形。

归并排序：

多路归并排序：

排序思想：将两个或两个以上的有序表合并成一个新的有序表。

算法评价：

空间复杂度：O(n)。

时间复杂度：O( n*log2n )。

稳定

归并排序可适用于顺序存储 与 链式存储 的线性表。

基数排序：

排序思想：基数排序不基于比较和移动进行排序，而基于关键字各位的大小进行排序；是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

特点：

元素间比较次数与序列的初始状态无关。

算法评价：

空间复杂度：O(r)。

一趟排序需要 r 个辅助队列存储空间。

时间复杂度：O( d(n+r) )。

d趟分配和收集操作。

稳定

基数排序可适用于顺序存储与链式存储的线性表。

计数排序：

外：

刷题总结：

在排序过程中，每趟都能确定一个元素的最终位置的是：

冒泡排序，简单选择排序，堆排序 + 快速排序。

直接插入排序特征：局部有序（前几个或后几个）。

其中能形成全局有序的子序列，而快排确定的中间枢轴元素的最终位置。

在最后一趟排序开始之前，所有元素都不在最终位置的的情况举例：

最后一个元素对应插在第一个元素位置。

初态：

与序列初始状态无关的是：

折半插入排序，简单选择排序。

受序列初始状态影响的是：直接插入排序，冒泡排序，快速排序。

稳定性：

一般简单算法都稳定（除了简单选择排序），改进优化算法不稳定“选艾希，堆攻速”“希望选择快速的这一堆”。

小点总结：

已知直接排序，问比较次数多少：首先看序列是接近顺序还是逆序；然后观察比较次数。

已知希尔排序结果，问选取的d的情况：数第一次排序后序列，按告知的d走一遍都是顺序即可。

已知快速排序结果，问最快的序列和最慢的序列。

最慢的序列是已经顺序或者逆序的序列，这样会形成单支树。最快的序列是，每次枢轴元素能把表分成长度相近的两个子表时。