代码拉取完成，页面将自动刷新
同步操作将从 Shapper/C Data Structure 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
“程序（Program）=数据结构（Data Structure）+算法（Algorithm）”
数据结构的发展经历三个阶段：无结构阶段，结构化阶段和面向对象阶段
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
在理解了时间复杂度的概念后，就可以根据实际的代码进行度量了，以下举例了几个常用的时间复杂度的表示，对于如何度量其最重要的是观察程序中的循环结构，每一个循环结构代表执行循环中的指令n次，而其余指令一般而言一行代码代表执行一次，对于一个程序而言，执行的次数相差较小其实没有什么区别，都是一瞬间执行完毕。
#include<stdio.h>
int main(){
printf("Hello World"); //执行一次
return 0; //执行一次
}
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //执行n次
ans+=i; //执行一次
}
return 0; //执行一次
}
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //执行n次
for(int j=0;j<n;j++){ //执行n次
ans+=j;
}
}
return 0; //执行一次
}
#include<stdio.h>
int main(){
int i=1,n=10000; //执行一次
while(i<=n){ //执行logn次
i*=2;
}
return 0; //执行一次
}
#include<stdio.h>
int main(){
int n=10000,ans=0; //执行一次
for(int i=0;i<n;i++){ //执行n次
int j=0; //执行1次
while(j<=n){ //执行log(n)次
j*=2;
}
}
return 0; //执行一次
}
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
每一段的内存中的数据，都有一个地址与之相对应，也真是因为有地址的存在，我们计算机中才可以轻易的去访问到其中数据，拿一个数组来说，数组在C语言中是顺序存储的，因此，如上图的数据直接用代码找到其数据以及地址的话可以这样写
#include<stdio.h>
int main(){
int i;
char array[10]="ACDEQSFVCK";
for(i=0;i<10;i++){
printf("The %c Address is %x \n",array[i],&array[i]);
//%x可以换成%p都是十六进制表示，只不过%p会把所有的位数显示出来
}
return 0;
}
其数据的输出结果如下（注意，不同的电脑可能地址不一样）：
The A Address is 62fe40
The C Address is 62fe41
The D Address is 62fe42
The E Address is 62fe43
The Q Address is 62fe44
The S Address is 62fe45
The F Address is 62fe46
The V Address is 62fe47
The C Address is 62fe48
The K Address is 62fe49
可以看到这是一段连续的地址，当你把char类型换成int型之后可能又不太一样，因为char是1字节的，而int占4字节，所以int的地址会变成4个一跳的方式往上增长。
malloc()函数(stdlib.h)在堆中申请分配一个大小为size个字节的连续内存空间，若成功分配，则返回一个指向所分配空间起始地址的指针，否则返回空指针（NULL）。
free()函数(stdlib.h)用来释放已分配的内存空间，参数p是待释放的内存空间的首指针。 一般而言，常规的内存分配，使用再到释放的过程如下：
#include<stdio.h>
#include<stdlib.h>
int main(){
int *p; //定义一个指向整形的指针变量
p=(int*)malloc(5*sizeof(int)); //申请5个整形大小的内存空间并返回起始地址给p
if(p==NULL){ //申请失败
//执行申请失败的代码，一般print一个报错
exit(1); //退出
}
p[0]=1000; //为空间中添加数据
printf("%d",p[0]); //打印这个数据
free(p); //释放p的内存空间，此时p依旧存在，只不过失去了指向的对象，成了野指针
p=NULL; //为其赋NULL，此时它不再是一个野指针
return 0;
}
我们设计一个数据结构程序的过程是先定义所需要的变量与指针变量---->进行内存分配---->判断是否分配成功(分配不成功就报错或者退出程序)---->对指针空间中的数据进行操作(如赋值，修改，查询，删除) ---->完成操作后释放指针
除上文提到的两个函数外，在C++中引入的对象思维，有一个极其类似于malloc函数的方法，就是new方法，但他们还是有一些区别的：
new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。
| 类型 | 存储大小（字节） | 值范围 |
|---|---|---|
| char | 1 | -128 ~ 127 或 0 ~ 255 |
| unsigned char | 1 | 0 ~ 255 |
| signed char | 1 | -128 ~ 127 |
| int | 2 或 4 | -32,768 ~ 32,767 或 -2,147,483,648 ~ 2,147,483,647 |
| unsigned int | 2 或 4 | 0 ~ 65,535 或 0 ~ 4,294,967,295 |
| short | 2 | -32,768 ~ 32,767 |
| unsigned short | 2 | 0 ~ 65,535 |
| long | 4 | -2,147,483,648 ~ 2,147,483,647 |
| unsigned long | 4 | 0 ~ 4,294,967,295 |
| 类型 | 存储大小（字节） | 值范围 | 精度 |
|---|---|---|---|
| float | 4 | 1.2E-38 到 3.4E+38 | 6 位有效位 |
| double | 8 | 2.3E-308 到 1.7E+308 | 15 位有效位 |
| long double | 16 | 3.4E-4932 到 1.1E+4932 | 19 位有效位 |
| 类型 | 描述 |
|---|---|
| 函数返回为空 | C 中有各种函数都不返回值，或者您可以说它们返回空。不返回值的函数的返回类型为空。例如 void exit (int status); |
| 函数参数为空 | C 中有各种函数不接受任何参数。不带参数的函数可以接受一个 void。例如 int rand(void); |
| 指针指向 void | 类型为 void * 的指针代表对象的地址，而不是类型。例如，内存分配函数 void *malloc( size_t size ); 返回指向 void 的指针，可以转换为任何数据类型。 |
第一个枚举成员的默认值为整型的 0，后续枚举成员的值在前一个成员上加 1。
在C 语言中，枚举类型是被当做 int 或者 unsigned int 类型来处理的，所以按照 C 语言规范是没有办法遍历枚举类型的。
枚举有符号，枚举变量的大小是 1<=sizeof(enum)<=sizeof(int) 字节 （1-4字节），根据最大数值大小分配内存。
// 不定义枚举类型，不定义枚举变量
enum
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
};
// 先定义枚举类型，再定义枚举变量
enum DAY
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
};
enum DAY day;
// 定义枚举类型的同时定义枚举变量
enum DAY
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;
// 省略枚举名称，直接定义枚举变量
enum
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;
// 定义枚举类型别名
typedef enum
{
MON=1, TUE, WED, THU, FRI, SAT, SUN
}Day;
Day day;
枚举的作用：
[]优先级高于单目*运算符
*a[i]//先结合[]，取数组索引i，再结合*取值，可判断a为指针数组。
(*a)[i]//先取值，再取索引i，可判断a为数组指针。
.：访问结构体成员 ->：访问结构体指针成员 位域
int main(){
struct bs{
unsigned m: 6;
unsigned n: 12;
unsigned p: 4;
}; //sizeof(bs)为4
struct bs{
unsigned m: 12;
unsigned char ch: 4;
unsigned p: 4;
};
struct bs{
unsigned m: 12;
unsigned ch;
unsigned p: 4;
};
struct bs{
int m: 12;
int : 20; //该位域成员不能使用
int n: 4;
};
大小端
大小端存储由 CPU架构 决定。
大端模式（ big endian ）：低地址存在高位，高地址存在低位。
小端模式（ Little Endian ）：低地址存在低位；高地址高位。
使用大端模式的有：TCP/IP网络数据流；使用小端模式的有：x86；ARM可以是大端模式，也可以是小端模式；
共用体的作用：
如下代码利用重叠技术实现用UINT型对数组数据进行接收，然后再将其组合成浮点型（32位）数据进行赋值。
static union
{
uint8_t data[24];
float ActVal[6];
}posture;
if(USART_GetITStatus(USART1, USART_IT_RXNE)==SET)
{
USART_ClearITPendingBit( USART1,USART_IT_RXNE);
ch=USART_ReceiveData(USART1);
posture.data[i] = ch;
i++;
if(i >= 24)
{
i = 0;
break;
}
}
SetPositionX(posture.ActVal[3]);
SetPositionY(posture.ActVal[4]);
SetAngle(posture.ActVal[0]);
int **res;//二维动态数组初始化与访问
res=(int**)malloc(size*sizeof(int*));
for (int i = 0; i < size; i++) {
res[i] = (int *) calloc(colsize, sizeof(int));
}
res[0][0] = 1;
注意： memset()只能用于char类型（字符串），它写入的尺度是1字节，如果类型为int（4字节），会导致错误。
注意：
strlen是string.h中的函数，以'\0'结束。
sizeof是运算操作符。
| 函数 | 目的 |
|---|---|
| strcpy(s1, s2); | 复制字符串 s2 到字符串 s1。 |
| strcat(s1, s2); | 连接字符串 s2 到字符串 s1 的末尾。 |
| strlen(s1); | 返回字符串 s1 的长度。 |
| strcmp(s1, s2); | 如果 s1 和 s2 是相同的，则返回 0；如果 s1<s2 则返回小于 0；如果 s1>s2 则返回大于 0。 |
| strchr(s1, ch); | 返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置。 |
| strstr(s1, s2); | 返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置。 |
auto
auto 存储类是所有局部变量默认的存储类。
register
register 存储类用于定义存储在寄存器中而不是 RAM 中的局部变量。这意味着变量的最大尺寸等于寄存器的大小（通常是一个字），且不能对它应用一元的 '&' 运算符（因为它没有内存位置）。
定义 'register' 并不意味着变量将被存储在寄存器中，它意味着变量可能存储在寄存器中，这取决于硬件和实现的限制。
static
static 存储类指示编译器在程序的生命周期内保持局部变量的存在，而不需要在每次它进入和离开作用域时进行创建和销毁。因此，使用 static 修饰局部变量可以在函数调用之间保持局部变量的值。
static 修饰符也可以应用于全局变量。当 static 修饰全局变量时，会使变量的作用域限制在声明它的文件内。
全局声明的一个 static 变量或方法可以被任何函数或方法调用，只要这些方法出现在跟 static 变量或方法同一个文件中。
extern
extern 存储类用于提供一个全局变量的引用，全局变量对所有的程序文件都是可见的。当您使用 extern 时，对于无法初始化的变量，会把变量名指向一个之前定义过的存储位置。
当您有多个文件且定义了一个可以在其他文件中使用的全局变量或函数时，可以在其他文件中使用 extern 来得到已定义的变量或函数的引用。可以这么理解，extern 是用来在另一个文件中声明一个全局变量或函数。
extern int a; // 声明一个全局变量 a
int a; // 定义一个全局变量 a
extern int a =0 ; // 定义一个全局变量 a 并给初值。
int a =0; // 定义一个全局变量 a, 并给初值，
头文件中只存放“声明”，而不存放“定义”。
不提倡使用全局变量，尽量不要在头文件中出现现象 extern int value 这类声明，用访问器（函数）替代全局变量。
线性表是n(n>=0)个数据元素的有限序列。在表中，元素存在线性的逻辑关系：表中有且仅有一个开始结点;有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点(predecessor);除终端结点外，表中的每个结点均只有一个后继结点(successor)。根据它们之间的关系可以排成一个线性序列,记作（a1,a2,…,an）
| N | 方法 | 描述 |
|---|---|---|
| 1. | InitList(L) | 线性表初始化,构造一个空的线性表L |
| 2. | ListLength(L) | 求线性表的长度,返回线性表L中数据元素的个数 |
| 3. | GetElem(L,i,x) | 用x返回线性表中的第i个数据元素的值 |
| 4. | locaionElem(L,x) | 按值查找,确定数据元素x在表中的位置 |
| 5. | ListInsert(L,i,x) | 插入操作,在线性表L中第i个位置之前插入一个新元素。L的长度加1 |
| 6. | ListDelete(L,i) | 删除操作,删除线性表L中的第i个元素,L的长度减1 |
| 7. | ListEmpty(L) | 判断线性表L是否为空,空表返回TRUE,非空表返回FALSE |
| 8. | ClearList(L) | 将已知的线性表L置为空表 |
| 9. | DestroyList(L) | 销毁线性表L |
其他操作：合并、分拆、复制、排序等等。
顺序存储是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。
采用顺序存储结构的线性表称为“顺序表”，顺序表中逻辑上相邻的数据元素在物理存储位置上也是相邻的。
物理结构上由数组来实现。
typedef struct {
int data[InitList];
int length;
}SqlList;
typedef struct {
int *data;
int length; //当前长度
int MaxSize; //最大长度
} SqlList;
链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存储的结构。
typedef struct Node {
int data; //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
struct Node *next; //单链表的指针域
} Node,*LinkedList; //Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型
在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, * DLinkList;
循环链表的尾指针指向的是链表的开头。
通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）。
typedef struct LNode {
int data;
struct LNode* next;
}LNode, * LinkList;
只允许在一端进行插入或删除操作的线性表。
栈是一种后进先出（LIFO）的数据结构。
术语：栈顶、栈底、空栈。
| N | 方法 | 描述 |
|---|---|---|
| 1. | InitStack(&S) | 初始化栈。构造一个空栈 S，分配内存空间 |
| 2. | DestroyStack(&S) | 销毁栈。销毁并释放栈 S 所占用的内存空间 |
| 3. | Push(&S,x) | 入栈，若栈S未满，则将x加入使之成为新栈顶 |
| 4. | Pop(&S,&x) | 出栈，若栈S非空，则弹出栈顶元素，并用x返回 |
| 5. | GetTop(S, &x) | 读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素 |
数组实现 代码示例
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int top;
} SqStack;
链表实现 代码示例
优点: 便于多个栈共享储存空间,提高其效率,不会栈满上溢
特点：所有操作在表头进行,通常没有头结点,将头指针作为栈顶指针,便于结点插入/删除
bool Push(LiStack &S, ElemType x) {
auto p = (LinkNode *) malloc(sizeof(LinkNode));
if (p == nullptr) return false;
p->data = x;
p->next = S;
S = p;
return true;
}
定义: 将两个栈的栈底设置在共享空间的两端,两个栈顶向中间延伸
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int top0;
int top1;
} ShStack;
只允许在一端进行插入（入队），在另一端删除（出队）的线性表。
队列是一种先进先出（FIFO）的数据结构。
术语：队头、队尾、空队列。
| N | 方法 | 描述 |
|---|---|---|
| 1. | InitQueue(&Q) | 初始化队列，构造一个空队列Q |
| 2. | DestroyQueue(&Q) | 销毁队列。销毁并释放队列Q所占用的内存空间 |
| 3. | EnQueue(&Q,x) | 入队，若队列Q未满，将x加入，使之成为新的队尾 |
| 4. | DeQueue(&Q,&x) | 出队，若队列Q非空，删除队头元素，并用x返回 |
| 5. | GetHead(Q,&x) | 读队头元素，若队列Q非空，则将队头元素赋值给x |
一般采用链表实现，长度不固定。
数组实现
代码示例
无法正常使用，当rear到达数组末端，未采用循环机制进行将导致空间用尽。
链表实现 代码示例
链表长度不固定可以动态申请，避免数组空间用尽的问题。
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode *next;
} LinkNode;
typedef struct {
LinkNode *front, *rear;
} LinkQueue;
长度固定，只能存入有限数量元素。
数组实现 代码示例
front、rear到达数组末端时，移动到数组头部进行循环，缺点在于：front=rear时，队列可能为空可能为满。 解决front=rear的多状态问题，可以采用的方法：
typedef int ElemType;
typedef struct {
int front, rear;
int size;
ElemType data[MaxSize];
} CQueue;
链表实现 代码示例
使用循环链表模拟循环队列固定长度的情景。
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode *next;
} LinkNode;
typedef struct {
LinkNode *front, *rear;
int size;
} ClQueue;
双端队列即在两端都可以执行入队和出队操作的数据结构。
bool EnQueue_Head(DeQue &Q, ElemType x) {
if (QueueFull(Q)) return false;
Q.front = (Q.front - 1 + MaxSize) % MaxSize;
Q.data[Q.front] = x;
Q.size++;
return true;
}
bool DeQueue_Rear(DeQue &Q, ElemType &x) {
if (QueueEmpty(Q)) return false;
Q.rear = (Q.rear - 1 + MaxSize) % MaxSize;
x = Q.data[Q.rear];
Q.size--;
return true;
}
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
树的基本术语
节点的度：树中某个节点的子树的个数。
树的度：树中各节点的度的最大值。
分支节点：度不为零的节点。
叶子节点：度为零的节点。
路径长度：路径上经过的边的个数。
孩子节点：某节点的后继节点；双亲节点：该节点为其孩子节点的双亲节点（父母节点）；兄弟节点：同一双亲的孩子节点；子孙节点：某节点所有子树中的节点；祖先节点：从树节点到该节点的路径上的节点。
树的高度(深度)：树中结点的最大层数。结点的深度：从根结点开始自顶向下逐层累加。结点的高度：从叶结点开始自底向上逐层累加。
有序树：树中节点子树按次序从左向右安排，次序不能改变；无序树：与之相反
森林：互不相交的树的集合。
有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
度为m的树: 度最大的节点的度为m，必须是非空树；m叉树：节点的最大度为m，度最大的节点的度可以小于等于m，允许是空树。
树的性值
结点数=总度数+1（加根节点）。
度为m的树中第i层最多有$m^{i-1}$个节点。
高度为h的m次树至多$\frac{m^h-1}{m-1}$个节点。
具有n个节点的m次树的最小高度为$log_m( n(m-1) + 1 )$向上取整。
二叉树的特点
每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
左子树和右子树是有顺序的，次序不能任意颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树的性质
特殊二叉树
斜树
所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
满二叉树
在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
特点有：
叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树
对一棵具有n个结点的二叉树按层编号，如果编号为$i(1<=i<=n)$的结点与同样深度的满二叉树中编号为 $i$ 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
特点有：
叶子只能出现在最后两层。
最多只能有一个度为1的节点。
二叉排序树
左子树上所有结点的关键字小于根结点
右子树上所有结点的关键字大于根结点
左右子树又各是一棵二叉排序树
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1（搜索效率高）
二叉树的存储结构
线性存储
二叉树的顺序存储结构，只适合存储完全二叉树，因为最坏情况下高度为h的右斜树，也至少需要$2^h-1$个存储单元
若完全二叉树中共有n个结点，则
链式存储
结点元素，data域，用来存储数据，其可以是int，char等基本的类型，同时也可以是struct等这些复杂的复合数据类型。
左孩子结点，left指针，总是用来指向当前结点的下一层的左边结点，其属于一种指针。
右孩子结点，right指针，总是用来指向当前结点的下一层的右边结点，其属于一种指针。
父结点（可选），parent指针，总是指向当前结点的前一个结点，简称父亲结点，其不属于必须结点设计，省略掉可以打扰节省内存的效果，而使用则可以更方便进行定向搜索，本案例中不使用父节点。
我们使用一棵树的时候需要建立一棵树根，由这个“根”，来进行逐步的向下构建。
//树的结点
typedef struct node{
int data;
struct node* left;
struct node* right;
} BiTNode，*BiTree;
二叉树的遍历
//树的先序遍历 Pre-order traversal
void preorder(Node* node){
if (node != NULL)
{
printf("%d ",node->data);
preorder(node->left);
preorder(node->right);
}
}
//树的中序遍历 In-order traversal
void inorder(Node* node){
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
//树的后序遍历 Post-order traversal
void postorder(Node* node){
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d ",node->data);
}
}
初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
重复3直至队列为空
由双遍历序列逆向构造二叉树
若只给出一棵二叉树的前、中、后、层序遍历序列中的一种，不能唯一确定一棵二叉树。
仅仅由前序、后序、层序序列两两组合也无法唯一确定一棵二叉树，必须有一个中序序列才能逆向构造。
对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树。
目的: 知道了“前驱”和“后继”信息，就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。
如何线索化：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //增加了左右标识域
}ThreadNode,*ThreadTree;
标识域： 如果ltag=0，表示指向节点的左孩子。如果ltag=1，则表示lchild为线索，指向节点的直接前驱 如果rtag=0，表示指向节点的右孩子。如果rtag=1，则表示rchild为线索，指向节点的直接后继
| 方法 | 中序线索二叉树 | 先序线索二叉树 | 后序线索二叉树 |
|---|---|---|---|
| 找前驱 | √ | × | √ |
| 找后继 | √ | √ | × |
除非采用暴力或者三叉树才能实现表中打叉的部分,所以一般中序线索二叉树最常用。
树的存储结构
树、森林和二叉树的转换
树和森林的遍历
又名：最优二叉树
其标准含义是：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
基本术语
构建哈夫曼树 构建哈夫曼树时，只需要遵循一个原则，那就是权重越大的结点距离树根越近，权重小的节点远离根节点。由于性值，需要利用parent访问双亲节点。
//哈夫曼树结点结构
typedef struct {
int weight; //结点权重
int parent, left, right; //父结点、左孩子、右孩子在数组中的位置下标
} HTNode, *HuffmanTree;
将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新 结点的权值置为左、右子树上根结点的权值之和。
从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
重复步骤2和3，直至F中只剩下一棵树为止。
如图这颗哈夫曼树的WPL值为：\[WPL=(1+4)\times3+(6+7+8)\times2 = 57\]
哈夫曼树的特点
哈夫曼编码（Huffman Coding）
又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。主要目的是根据使用频率来最大化节省字符（编码）的存储空间。
性质
霍夫曼编码是一种前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是 “前缀无歧义编码”(prefix-free code)简称PFC编码 。
构造哈夫曼编码
并查集是一种树型的数据结构，它是逻辑结构集合的一种具体实现，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
基本操作
并查集的存储结构
用一个数组即可表示集合关系，使用双亲表示法（顺序存储），即数组存储双亲节点的数组下标，根节点的值为-1。
优化操作
二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：
二叉搜索树的性能分析
对于有n个结点的二叉搜索树：
在插入和删除后，二叉搜索树性质＆平衡性破坏。
为了防止BST出现性能下降，为 BST 引入了平衡的概念，来有效的控制树高，以追求更低的树。
理想平衡
适度平衡
等价变换
对于 BST ，拓扑结构不尽相同，但中序遍历序列如果相同，则称之为 等价 BST。
等价BST规律：
基本操作
自平衡二叉搜索树（AVL tree）[^1]
[^1]:由G. M. Adelson-Velsky和E. M. Landis不1962年证明
任一节点v的平衡因子(balance factor) 定义为“其左、右子树的高度差”,即
$balFac(v)=height(lc(v)) - height(rc(v))$
所谓AVL树,即平衡因子受限的二叉搜索树其中各节点平衡因子的绝对值均不超过1。
红黑树
伸展树
替罪羊树
图$G$由顶点集$V$和边集$E$组成，记为$G = (V, E)$，其中$V(G)$表示图$G$中顶点的 ==有限非空集==；$E(G)$ 表示图$G$中顶点之间的关系（边）集合。若$V = \{v1, v2, … , vn\}$，则用 ==$|V|$表示图$G$中顶点的个数==，也称图$G$的阶，$E = \{(u, v) | uÎV, vÎV\}$，用 ==$|E|$表示图G中边的条数==。
注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集 ，E可以是空集。
有向图： 若E是有向边（也称弧）的有限集合时，则图G为有向图。 弧是顶点的有序对，记为==<v,w>，其中v、w是顶点，v称为 弧尾，w称为弧头==，称为从顶点v到顶点w的弧，也称 v邻接到w，或w邻接自v。 <v,w> ≠<w,v>
无向图： 若E是无向边（简称边）的有限集合时，则图G为无向图。边 是顶点的无序对，记为(v, w)或(w, v)，因为==(v, w) = (w, v)，其 中v、w是顶点==。可以说顶点w和顶点v互为邻接点。边(v, w) 依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。
简单图： 1. 不存在重复边； 2. 不存在顶点到自身的边。
多重图：图G中某两个结点之间的边数多于 一条，又允许顶点通过同一条边和自己关联， 则G为多重图。
顶点的度、入度、出度
无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。无向图的全部顶点的度的和等于边数的2倍。
有向图： 入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目，记为OD(v)。==顶点v的度==等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
顶点-顶点的关系描述
边的权、带权图/网
特殊形态的图
邻接矩阵法（Adjacency Matrix）
邻接矩阵法的性质： 设图G的邻接矩阵为A（矩阵元素为0/1），则An 的元素An [i] [j]等于由顶点i到顶点j的长度为n的路径的数目。
特点：邻接矩阵存在以下缺点
邻接表法（Adjacency List）（顺序+链式存储）
通过链表或者利用数组模拟链表的方式将图的相连接关系表示的一种方法，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。空间复杂度：无向图O(|V|+2|E|)，有向图O(|V|+|E|)
邻接表的链表表示的是单向边关系，如果连接到空结点的那一条边不算，那么双向图的边正好就是单向图的两倍。
邻接表就相当于是一种改良，对于稀疏图能够很好的适应，使用较少的空间和时间就能表达。
邻接多重表（Adjacency Multilists）（顺序+链式存储）
顺序表存储顶点编号以及与顶点相连的第一条边的指针。链表用来表示边，存储边的两个顶点编号、权值以及对应顶点的下一条边的指针，删除边，删除节点等操作方便。但只适合用来存储无向图，因为不包含方向的信息。空间复杂度O(|V|+|E|)
十字链表（Orthogonal List）（顺序+链式存储）
顺序表存储顶点编号以及与顶点相连的该顶点作为弧头的第一条弧、该顶点作为弧尾的第一条弧的指针。链表用来表示边，存储弧头弧尾编号、权值以及弧头相同的下一条弧、弧尾相同的下一条弧的指针，删除边，删除节点等操作方便。但只适合用来存储有向图，空间复杂度O(|V|+|E|)
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlogn)$，因此也称为非线性时间比较类排序。 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张表格概括：
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | In-place | 稳定 |
| 快速排序 | $O(n log n)$ | $O(n log n)$ | $O(n^2)$ | $O(log n)$ | In-place | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | In- place | 稳定 |
| 希尔排序 | $O(n log n)$ | $O(n log^2 n)$ | $O(n log^2n)$ | $O(1)$ | In- place | 不稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | In-place | 不稳定 |
| 堆排序 | $O(n log n)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | In-place | 不稳定 |
| 归并排序 | $O(n log n)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | In-Out-place | 稳定 |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | Out-place | 稳定 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | Out- -place | 稳定 |
| 基数排序 | $O(nk)$ | $O(nk)$ | $O(nk)$ | $O(n + k)$ | Out-place | 稳定 |
算法思想
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
算法步骤
注：原始的冒泡是从后往前的
算法思想
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
算法步骤
算法思想
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。就像我们斗地主时，抽牌阶段会把抽到的牌插入到相应的位置中去，使手上的牌有序。
插入排序有个小优化叫做折半插入，就是往前寻找插入位置时，因为前面的数组全部有序，因此我们用二分查找法来寻找插入位置。
算法步骤
算法思想
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
算法步骤
算法思想 选择排序是一种简单直观的排序算法，无论什么数据进去都是 $O(n^2)$ 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
算法步骤
算法思想
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，堆排序的本质是建立在堆上的选择排序。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
堆排序的平均时间复杂度为 Ο(nlogn)，利用堆的特性，其实我们可以很方便的得到一个未排序数组中的Top K元素。
算法步骤
算法思想
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代（双指针的思想）；
算法步骤
二路归并排序：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
基数排序：根据键值的每位数字来分配桶；
算法思想
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 $O(n + k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
算法步骤
算法思想
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快 当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢 当输入的数据被分配到了同一个桶中。
算法步骤
算法思想
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，基数排序将待排序的元素拆分为 k 个关键字，所以基数排序也不是只能使用于整数。
如果对自然数进行比较，将自然数按个位对齐后往高位补齐 0，则一个数字从左往右数第 i 位数就可以作为第 i 关键字；
如果对字符串基于字典序进行比较，一个字符串从左往右数第 i 个字符就可以作为第 i 关键字；
如果是从第 1 关键字到第 k 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；
如果是从第 k 关键字到第 1 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。
查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表按照操作方式可分为：
平均查找长度（Average Search Length，ASL）： 在所有的查找过程中进行关键字的比较次数的平均值。 对于含有n个数据元素的查找表，查找成功的平均查找长度计算公式如下： \[ASL = \sum_{i=1}^{n}P_{i}C_{i}\] $P_iP$：查找表中第i个数据元素的概率,一般等概率为$\frac{1}{n}$ $C_i$：找到第i个数据元素时已经比较过的次数。
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。时间复杂度$O(n)$。
基本思路
从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。
优缺点
缺点：当n 很大时，平均查找长度较大，效率低； 优点：对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。
二分查找（Binary Search），也称折半查找，是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种查找算法每一次比较都使查找范围缩小一半。时间复杂度为$O(log_2^n)$。
基本思路 给予一个包含 $n$个带值元素的数组A 1、 令$L$为$0$， $R$为$n-1$； 2、 如果$L>R$，则搜索以失败告终 ； 3、 令$m$(中间值元素)为$(L+R)/2$(向下取整)； 4、 如果$A_m<T$, 令$L$为$m + 1$并回到步骤二； 5、 如果$A_m>T$，令$R$为$m - 1$并回到步骤二；
注意： 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手