导图社区 数据结构思维导图整理
- 27
- 0
- 0
- 举报
数据结构思维导图整理
数据结构，整理了宋代文学概述、宋词、宋诗、宋代散文、C11语法、排序、图、树、935考纲对比的内容，欢迎大家学习。
编辑于2023-03-05 23:09:15 江苏省
- 相似推荐
- 大纲
数据结构
10/17新增 935(东南大学)考纲.考研 408也同样可以使用【参考王道的讲义】增加 C11 模块，主要针对部分C语言语法内容补充
绪论
算法
算法定义
问题求解步骤描述
五个特性
有穷性
确定性
可行性
输入
输出
复杂度计算
复杂度主要是以当 n->∞ 时的等阶无穷大来进行判断而阶大小的主部，主要是根据时间渐近复杂度作为比较依据
时间复杂度
主要是取主阶
加法规则
乘法规则
常见渐进时间复杂度
等差等比公式
利用等差等比公式，计算具体的次数公式
空间复杂度
定义辅助空间大小与原数据量之间的关系
原地工作
求解问题
递归算法
递推公式
递归调用
递归公出口
列方程法
数据
数据是一种信息载体数据对象 / 数据元素 / 数据项区别】```例如: 人有许有器官（假设器官为最小单位），那么鼻子就是一个数据项.，一个人就是一个数据元素。而对于整个人类整体（所有人类）则被称为数据对象```数据结构 与 数据对象区别】```虽然有了整个人类对象，但是人与人是有关系的，所以要记录其数据关系，同时人也是有行为的，还要记录其操作行为，才算完整数据结构 = 数据对象 + 数据关系 + 数据操作```
数据对象
具有相同性质的数据元素集合
数据元素
数据的基本单位
(个体)基本单位
数据项
构成数据元素的最小单位
(个体)属性
数据类型
值的**集合**与**操作**的总称例如 整数能够增加减少操作
原子类型
结构类型
抽象数据类型(ADT)
(数据对象，数据关系，基本操作集）
数据结构
多种特点关系的数据元素的集合；元素的关系被称为结构
三要素
逻辑结构
线性结构
一般线性表
受限线性表
操作或者数据元素受限制
栈
队列
串
线性表推广
数组
非线性结构
树
二叉树
多叉树
森林
图/网
有向图
无向图
集合
存储结构
OS中文件的存储结构便包括 顺序，链式，索引存储
顺序存储
链式存储
索引存储
利用类似B+树的数据结构存储索引
散列存储/哈希存储
利用哈希函数去计算具体存储地址
数据运算(操作)
Linear List线性表
定义/概念
有限个数据元素，相同数据类型，且有序
与其他结构区别】例如：集合就是有限，相同，但无序
存储空间大小相同
表头元素；表尾元素；位序； 前驱；后继
操作
创建/销毁
静态分配
动态分配
C/C++malloc , new[]
增删改查
属性获取
存储结构
sequential mapping顺序存储
SqList顺序表
除了逻辑结构具有线性上连续外，还在**物理存储结构上**具有**相邻连续**的特点关于下标】数组默认存储从 0 开始，所以插入第 i 位时要进行相对地址转换(i-1)长度为n 顺序表，可插入位置为 [1,n+1]代码】这部分代码不用管 ,最好不要用指针```#define SIZE 100 //大小#define INC 10 //增量typedef struct SqList{ Elem *elem; //首地址 int len;//长度 int size;//存储容量}SqList;```
特性
随机存取[物理顺序和逻辑顺序相同]
删除和插入时间复杂度高
分配方式
静态
C语言数组方式分配
动态
C语言指针方式分配
分配一个Elem的指针，且指针所指的地址空间大小为 length * sizeof(Elem)
操作
初始化
1.分配内存地址2.检测(健壮性)3.修改属性4.返回操作状态```bool init(SqList &L){ L.elem = (Elem *)malloc)(SIZE*sizeof(Elem)); if(! L.elem) return false; L.len = 0; L.size = INIT_SIZE; return true;}```
插入
1.判断插入区间合法性(铭记健壮性)2.内存大小是否足够3.移位并插入```bool insert(SqList &L,int i,Elem e){ if(i L.len + 1) return false; if(L.len >= L.size){ tmp = (Elem *)realloc(L.elem,(L.size+INC)*sizeof(Elem)); if(!tmp) return false; L.size += INC; } q = &(L.elem[i-1]); for(p = &(L.elem[L.len-1]); p >= q; --p) *(p+1)=*p; * q = e; ++ L.len; return true;}```
实现逻辑
健壮性判断
插入范围，存储空间大小
移动
从后往前，将第i位元素后移，在第i位写入数据，线性表长度加1
属性修改
顺序表长度
返回函数状态
返回函数是否成功执行或者异常的状态
时间复杂度
最好O(1)
最坏O(n)
平均 = 概率 移动次数 = 期望
删除
1.判断合法域2.移动3.修改属性```bool delete(SqList &L, int i, Elem e){ if( iL.len ) return false; p = &(L.elemp[i-1]); e = *p; q = L.elem + L.len - 1; for(int j=i; j
实现逻辑
健壮性
移动
属性修改
返回函数状态
时间复杂度
最好O(1)
最坏O(n)
平均
按值查找
实现逻辑
顺序寻找
返回位序
时间复杂度
最好O(1)
最坏O(n)
平均
合并
真题
2010】408整数数组循环左移
2011】408找出两个等长升序序列的中位数
2013】408找出序列中的主元素主元素：个数 > 序列总个数/2
2018】408求最小未出现整数
2020】408求三元组最小距离
链式存储
单链表
定义
C语言实现【语法如有疑问，参考本思维导图 C11(标准)章节】```typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域}LNode , *LinkList```
操作
插入
头插法
1.直接插入法关于指针顺序不需要记，写完之后推以下有没有问题就行了【在修改 L->next=s之后,s->next=L->next=s就成自指了】```//假设s为要插入的结点,L为插入位置的前一个位置结点p=GetElem(L,i-1);s->next=L->next;L->next=s;```评价：操作简单，但存储顺序为逆序2.后插交换法```//s结点插入p结点之后s->next=p->next;p->next=s;//数据交换swap(p->data,s->data);```
尾插法
增加尾指针```r->next=s;r=s;```
时间复杂度O(n)
删除
1.找前驱位置 i-12. i-1 位置先连到 i+1 位置上，再把 i 直接删掉即可【注：由于是单链表的单向性，已知 i-1 位置只能得到 i-1 之后位置的指针，而不能找到其前面的指针.】```p=GetElem(L,i-1);q=p->next;p->next=q->next;delete q;```
按值查找
判空
双链表
即双向链表
定义
```typdef struct DNode{ Elem data; struct DNode *prior,*next;}DNode, *DLink```
操作
注意插入删除顺序插入第k位则遍历至第k-1位结点进行操作
插入
实现逻辑
时间复杂度
删除
循环链表
其末尾元素尾指针指向头结点在操作系统中用于CLOCK置换算法
单向循环链表
双向循环链表
方阵
静态链表
数组存储下表跳转信息，建立链接逻辑【数组模拟的链式结构】
跳跃表
跳跃表基于有序单链表，在链表的基础上，每个结点不只包含⼀个指针，还可能包含多个指向后继结点的指针，这样就可以跳过⼀些不必要的结点，从⽽加快查找、删除等操作。 查询，删除，插⼊都是logn
相关概念
头结点
概念】假设头结点为 L 则其值为 空值，L->next 指向第一个元素地址优点】1.插入删除代码逻辑上操作一致2.空表和非空表处理一致
头指针
始终指向链表中第一个结点的指针，通常用其来标识一个链表地址。单链表】```含有头结点时，指针值为头结点地址不含头结点时，指针值为NULL,否则为第一个元素的地址```
链表头
第一个存有数据内容(值)的结点头指针是指向头结点的指针，头结点是指向链表头的结点
首元结点
是指链表中用来存储数据元素的结点中的第一个结点
尾指针
尾指针所指向的结点的下一个节点即是头结点
真题
2009】408查找只含头结点的单链表中倒数第k位置的结点值
2012】408求出某两个链表共同后缀起始位置
2015】408单链表中保留所有绝对值相等节点中, 第一个出现位置的结点
2019】408对单链表进行重排
优缺点
顺序
随机访问，链式则只能顺序访问
链式
分配灵活，无需占用连续空间，插入删除时间复杂度低
逻辑结构
栈(Stack)
栈的判空判满都根据实际情况进行分析主要掌握逻辑【数据结构其实可以视为某种物理/逻辑模型(在现实中都能找到)】只要选择好类比的逻辑，就好自己理解这个部分
定义
栈顶(top)
栈低(Bottom)
空栈(Empty)
特性LIFO 后进先出
数学性质 [ 卡特兰数 ]n 个不同元素进栈，出栈元素不同的排列个数为
操作
初始化Init (&S)
销毁Destroy(&S)
进栈(Push)Push(&S,&e)
出栈Pop(&S,&e)
读取栈顶GetTop(S,&e)
判空IsEmpty
```栈顶指针默认指向下一个插入元素位置作为栈顶的下标top,则默认指向栈顶元素位置```
存储结构
顺序
顺序栈
利用数据进行顺序存储```C++#define MaxSize 50typedef struct{ int top; ElemType data[maxsize];}Stack;```栈顶指针初始值可为 -1 或 0这里以栈顶指针指向元素值的逻辑进行初始化栈空】```S.top == -1 // (-1相当于空指针)```栈满】栈上溢```S.top == MaxSize - 1 // (从0开始存储)```栈长】```S.top + 1```进栈】```S.top++; S.data[S.top] = a;```出栈】```return S.data[S.top]; S.top--;```
共享栈
共享栈：```两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间；两个栈的栈底在这片存储空间的 两端 ，当元素入栈时，两个栈的栈顶指针相向而行。优点：节约存储空间，减少发生上溢可能```
链式
链栈默认插入删除操作【头插法】头插法插入头结点的后面，而对于栈，插入段即是栈顶，所以头为栈顶，尾为栈底
链栈
```typedef struct Linknode{ Elem data; struct Linknode *next;}*LiStack;```
操作
含有头结点```取头指针为 *LinkHead;*LinkHead = &StackHead;```插入 / 删除```LinkHead->
属性
表头结点
操作在头结点进行的话，表头即栈顶链接的方向是从表头向表尾链接
表尾结点
应用题型
括号匹配
括号匹配的原则就像小时候玩过的"祖玛宝石消除"小游戏，如果某串中间的元素被消除后，消除位置的左右两侧就会聚拢，然后按照规则继续消除，形成连锁反应。不过由于栈的性质，只能从栈顶进入，所以就当 宝石消除只能发射宝石到队头进行消除。原理是一样的。算法思想：1.设置一个空栈，顺序读括号2.右括号，能和栈顶消除，就立刻消除3.左括号，直接压入栈中
表达式求值
表达式中的 X缀，表示的是操作符相对于操作数的位置在三种不同的表达式类型中，操作数的相对位置始终没有改变。唯一变化的是操作符的位置。
前缀/波兰表达式
运算符在操作数前（从右往左扫描）例如E/F的整体结果要看作一个操作数前缀表达式:- + A * B - C D / E F
中缀
运算符在两数中间中缀表达式也是人一般书写的格式正常顺序：A + B * ( C - D ) - E / F
后缀/逆波兰表达式
运算符在操作数后（从左往右扫描）后缀表达式的符号序列顺序，即为实际的运算顺序。后缀表达式：A B C D - * + E F / -后缀求值】存操作数栈，出现运算符，就进行运算然后将结果压入操作数栈中
转换方法
逆波兰：括号>乘除>加减，左>右；数值直接输出，符号不同级，新来级别更高先输出，同级符号先左后右转换：a/b+(c\*d-e\*f)/g1.加括号 ((a/b)+(((c\*d)-(e\*f))/g))2.运算符号后移 ((ab)/(((cd)\*(ef)\*-)g)/)+或前移+(/(ab)-/\*(cd)*(ef))g3.去括号 ab/cd\*ef\*-g/++/ab-/\*cd\*efg
计算方法
由于中缀表达式运算顺序的不定项（同级别运算可交换）所以，对应生成的前后缀表达式也不唯一。后缀：存储操作数栈，遇运算符则弹出栈顶两个元素再将计算结构放入栈中。采用从左往右扫描计算前缀：同理，不过采用从右往左扫描计算
表达式树
递归调用
时间复杂度计算
1.转化为递推表达式2.画出对应的递归树
dfs广搜
出栈序列
不可能序列
通俗点理解，即某元素出列后，栈中余下元素的出栈序列，应为入站时的逆向子序列.```例如 cabdef在 c先出之后，ab 的输出序列只能为 ba 顺序的子序列。所以 cab序列就不可能出现```
序列种类数
卡特兰数:
可能序列
对于abcd...顺序，如果 d 先出，那么d之前的 abc 在后面则只能逆向子序列. 而 d 之后进栈值可以插入在 cba形成的子序列中
数值转换
栈的最小深度
利用入栈和出战顺序求解
函数局部变量存储
队列/Queue
基本操作
FIFO
初始化
销毁
判空
入队
出队
读取队头元素
概念
队头指针
队头指针指向队头结点，队尾指向队尾结点而队尾用于入队所以 链式的入队操作为 ```rear -> next = x; x->next = NULL;rear = x;```而顺序的入队操作```Q.data[++Q.rear] = x;```
队尾指针
头结点
对于不带头结点的队列```判空时因为没有任何元素所以Q.rear = NULL, Q.front = NULL;第一个元素为：Q.front = p; Q.rear = p; p->next = NULL;```带头结点的链式队列```//初始化Q.rear = Q.front = (LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;//判空(Q.rear == Q.front) return true;```
存储结构
顺序
循环队列
【初始操作】```front == rear == 0rear 指向将要分配位置，front 指向队首元素```【判空操作】```1）**空出一个单元**区分队空队满 — 队头指针在对位指针下一位置队满：(rear+1)%size == front队空：front == rear2)增加记录元素**个数属性** size队满：size == n队空：size == 03）增加 **tag 标记**， 用于区分是队空是相等还是队满是相等队满：tag == 1, rear == front队空：tag == 0, rear == front```
顺序存储
```#define MaxSize 50typedef struct{ Elem data[MaxSize] int front,rear;}SqQueue;```操作和栈一致都是以队尾/栈顶指针指向最后一个元素】初始状态 Q.front == Q.rear == 0;队空状态 Q.front == Q,rear进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1出队操作：队不空时，先取队头元素值，再将队头指针加 1
链式
双端队列
输入/输出受限模型
链式存储
定义】```typedef struct LinkNode{Elem data;struct LinkNode *next;}LinkNode;typedef struct{LinkNode *front,*rear;}LinkQueue;```带头结点和不带头结点的判空```不带：front == NULL, rear == NULL带： front == rear入队出队操作：队尾（链尾）入头出（链头）```操作】```front-> node1->..->rear// 插入rear->next = ```
定义
定义】```typedef struct LinkNode{Elem data;struct LinkNode *next;}LinkNode;typedef struct{LinkNode *front,*rear;}LinkQueue;```带头结点和不带头结点的判空```不带：front == NULL, rear == NULL带： front == rear入队出队操作：队尾（链尾）入头出（链头）```
操作
操作】```front-> node1->..->rear// 插入rear->next = temp; temp->next=null; rear = temp;```
逻辑结构
应用
二叉树层次遍历
出队序列计算
1.双端队列2.有限制出入的队列
做题时可标注左右进入的序列
FIFO性质
OS缓冲区
CPU资源分配
页面替换算法
数组矩阵
数组
定义
线性表推广，多维=数组矩阵C语言存储默认下标为0
存储结构
行优先
先行后列行号 i = x // col(列数);列号 j = x % col;
列优先
先列后行列号 j = x // row(行数);行号 i = x % row;
特殊矩阵
特殊矩阵的压缩存储压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。**注：所有矩阵存入对应的一维数组中，下表均默认从 0 开始**计算方法: 利用等差数列公式进行计算
对称矩阵
和线性代数的矩阵概念定义一致 n阶方阵的元素沿对角线对称相等 a(i,j)=a(j,i)则将这个二维矩阵存储于一维数组中为 B[n(n+1)/2]**对称矩阵，下三角按行优先存储 = 上三角按列优先存储**
下标转换公式
三角矩阵
即只有上/下三角具有元素，其余位置元素值均为 c(常数)
下标转换
下标从0开始的矩阵
三对角矩阵
除第一行和最后一行以外，有对角线及左右三个元素。假设以行优先对于第i行，前i-1行已满:(i-1)*3-1对于第j列，如果j在对角线下方说明,j-i=-1,此时改行有一个元素，即个数为 (j-i)+2所以求和得：3i-3-1+j-i+2=2i+j-2但是由于下标从0开始，所以最终还得减去一个一即：2i+j-3
下标转换
稀疏矩阵
三元组
十字链表
疏密矩阵
邻接矩阵
真题
矩阵元素下表与一位数组下标换算
特殊值法，带入(1,1)下标进去
地址求行长
已知 A[i][j] 和 B[x][y] 的地址个数 = A地址 - B地址 = (i-x) * n【行长】+ j-y-1 (由于是从 B[x][y+1]开始计数)
串
基本概念
与线性表区别在于只存储子串(字符)类型
子串
主串
位置
存储结构
C默认串默认增加'\0'以表示结尾
定长顺序存储
堆分配存储
块链存储
相关运算
模式匹配
求出字符串首次出现的位置
暴力匹配
KMP算法
代码】```/* 返回结果 -1 表示没有匹配位置，否则返回开始匹配的起始下标(默认从0) */int kmp(string s,string t){ int i = 0, j = 0;get_next(s);int slen = s.length(), tlen = t.length(); while(i
next数组
next数组定义```next数组的第i+1位的值是前i位**最长前后缀长度(不包括子串本身)**；即PM[i+1]的值 = next[i]next数组和next数组值之间关系为,数组元素+1=数组值```next数组算法```const int maxnum = 100;int next[maxnum]; // next下标从1开始string t;// 模式串t,下标从0开始//对模式串进行处理void get_next(string t){int i=0,j=-1; // 下标初始化，防止出现越界情况next[i] = j;int len = t.length();while(i
next手工算法
注意】在考试题中，字符串下标默认从1开始```例如: ababaaababaanext下标默认从0开始,next[0],next[1]默认为 0,1next[0] = 0a -> next[1] = 1 (失配回到原点下标 1)ab -> next[2] = 1 (最长前后缀为0,失配回到原点下标1)aba -> next[3] = 2 （最长前后缀为1,所以失配后，至少有1位是已经可以匹配，下标跳转到下一位:1+1=2）abab -> next[4] = 3 (同理)ababa -> next[5] = 4ababaa -> next[6] = 2 (此处最大前后缀为1,所以1+1=2)由上可以得知:next[0]=0,next[1]=1 固定之后第i位结果为，模式串前i位最大公共前后缀长度+1```
相等判断
C语言函数```int strcmp(char* S,char* T);若S > T，返回结果大于零；若S
求子串
连接
C语言函数```strcat(str,str2);将str2连接到str后面，但是注意段错误(地址越界)```C++函数```str = str1 + str2;'+' 符号重载```
长度
C语言```int strlen(char *); // 函数```C++语言```int str.length(); // 类方法```
查找
效率指标
平均查找长度
查找成功
进行一次比较便计数1；如果第一次就查找成功则查找次数为1；所以查找成功AVL即对所有元素比较次数求和并最后除以其个数【等同概率】
查找失败
对于某种探测法，查找失败意味着，假设通过除留取余得到初始位置失配，则需要进一步进行一次比较判断。同时下一次比较位置也是由探测法来决定，如果是线性探测，则在其失配位置进行+1。直到没有元素为止【失配要包括和空位置进行比较】对于除留取余而言，初始位置就只有0~(m-1),所以对每个位置一次进行计算即可
概念
查找表/查找结构
用于查找的数据结构
操作
查找特定元素
检查满足条件元素属性
插入元素
删除元素
静态查找表
顺序
折半
散列
动态查找表
用于查找的数据结构
二叉排序树
AVL平衡二叉树
B树
平均查找长度
P为查找概率，C为比较次数【期望公式】
冲突/碰撞
同义词之间冲突
不可能避免
聚集/堆积
同义词与非同义词发生冲突
主要与冲突探测方法有关
散列结构
散列函数
**散列函数**把查找表中的关键字映射成对应的地址的函数；【反映关键字与地址之间的直接联系】**散列表**根据关键字进行直接访问的数据结构
直接定址法
顺序存储结构，随机存储便是直接定址法
除留余数法
数字分析法
选择数字中的某些数位
平方取中法
冲突处理
**冲突：**奖两个或者两个以上的不同关键字映射到同一个地址注：王道408和严书上内容归类有些不一致，最好还是以严书本为主
开放定址法
注：在严书数据结构中，为线性探测再散列；平方探测【二次探测再散列】；伪随机探测再散列
线性探测再散列
冲突位置顺序查找
二次探测再散列
冲突位置进行探测,d=0,+-1^2,+-2^2，...
伪随机探测再散列
链地址法/拉链法
又称拉链法【邻接表结构】
再哈希(散列)法
又称双散列法，使用两个散列函数
平均查找长度
查找成功
计算每一个再散列表中的元素，所需要的查找次数，然后求平均值在查找过程中要按照对应的探测方法进行搜索。
查找失败
查找失败表示的是，对于余数在 0~n-1 范围内的所有数，且均不在散列表中出现，所需要的次数。其中，在对比完最后一个有效位之后，由于还要比较一次没有存放元素位置，所以每次要多比较一次空位置。
装填因子
a= 表中记录数/散列表长度
线性结构
顺序查找(链式限制)
一般顺序表查找
有序表顺序查找
由于序列关键字有序，如果是递增序列，当要比较的值x小于当前比较值，则可以判断查找失败【可不用查找至末尾】
折半(二分)查找
适用于有序顺序存储结构
折半查找判定树
折半查找的过程可以使用二叉树进行描述：称为判定树
类型：平衡二叉树
n 个元素时的树高 h
除了判定成功结点外，还有判定失败结点
判定树是否复合规则判断
1.折半查找判定树构造可以向下取整，也可以向上取整或者向下取整【但是不能 即向上，又向下(判断依据)】2.中序遍历得到的是有序序列
最多查找次数
最少查找次数
分块(索引顺序)查找
将长度为n的查找表均匀的分为b块，每块s个记录，在等概率下，若块内和所应表中均采用顺序查找ASL =(b+1)/2+(s+1)/2=(s^2+2s+n)/2s如果 s=(根号)n, 且索引表按照折半查找，则平均查找长度为：log(b+1)+(s+1)/2
理想块长
顺序分块查找
最优优化
索引结构/树表
B树
/多路平衡查找树【设计思路演进】理解数据结构的定义，一定先理解发明人的意图.为什么我们不用二分查找树来做索引? 这是因为查找结点的时候, 我们需要访问磁盘, 二分查找树的深度比较深, 往往需要比较多次的磁盘IO, 时间开销较大.基于这个考虑, 工程师设计了B-tree, 其的核心特征是实现**平衡**, **多路** **查找树**平衡意味着, 树的所有路径高度都要一致, 多路意味着结点的出度>=2(实际上往往是成百上千的)查找树意味着结点之间, 结点内部是有序的(类似二分查找树)通过增加查找树的度数，就能够大大降低树的高度。同时还要考虑到平衡性，防止退化。
属性
B树的阶
所有结点的孩子数目最大的个数，常用m表示
非叶结点结构
K为关键字【值】，且满足有序P为指针，指向子树根节点指针。且指针 Pi 所有制的所有结点关键字都大于 Ki
所有结点平衡因子为 0 【高度平衡】
高度
由于B为m阶树，则每个结点最多m棵子树，m-1个关键字
最高
除每个非终端结点至少有 m/2(向上整除)子树保证其最小分裂数，防止退化为 二叉树第一层最少 1 个，第二层至少 2 个，第三层则为 2[m/2](上整除)所以 对于最高则为 n+1=2[m/2]^{h-1}所以
最低
对于最低的高度，则是该树所有结点的阶数等于树的阶数[使得度最大化]由于 n = m^h-1 [度为m的满m叉树个数]所以 h = log_{m^h}^{n+1} [最小高度]
关键字数
高度为 h的 m 阶B数;关键字数的计算刚好和高度相反
最多
最少
即结点数一定时，最高可能的高度的反命题要使得层数最高且结点数最少，则树高为h，其h-1层位满，h层多一个作为结点
性质
非根结点关键字个数
每个非根结点有[M/2-1,M-1)个关键字，且以升序排列.上限容易理解：由于为m阶树，所以指针个数最多为 m，关键字比指针个数少 1, 为 m-1下限：由于建立B树的目的就是通过增加度数从而降低查找树高度，如果小于m/2,意味着还不如用AVL查找方便。
非根结点子树个数
刚好是其关键字个数范围 +1结点子节点数=该结点关键字数+1因为根存在，则其关键字数 >= 1所以，根节点为非终端结点时，至少有两个孩子.
根节点为非终端结点时，至少有两个孩子.
严格平衡查找树，所有节点子树高度一致叶子处于同一层且用NULL表示
4).对于一个关键字来说它的左孩子的下标一定和它一样，它的右孩子的下标一定比它多一个.5).所有的叶子结点都在同一层
非叶结点的结构
操作
B树通过分裂和合并从而保持平衡AVL则是通过旋转保持平衡
查找
插入
不同于二叉树，找到其左右孩子位置插入；由于每个结点最多能够容纳 m-1 个 关键字，所以从首节点开始，要将每个填满后再分裂。例如 4阶B树，5、9、13、15 ，首先前三个在第根结点处[填满根结点]，然后由于插入15使得不平衡，所以采取分裂。
分裂
**分裂**B树再插入后如果不满足平衡状态，则会进行分裂当插入部分的关键字数超过了m-1时，不满足m阶B树定义，就需要将其分裂从而减小。每次分类分成两棵，由于子树个数增加，所以将中间位置【m/2向上整除】插入到父节点位置中。如果父节点叶超过上限，则继续分裂，直到根节点为止。
删除
插入后要满足结点度数下限
合并
注：这里[]表示向上取整1）**直接删除关键字**删除后结点所在关键字数 >= [m/2]，则直接删除2）**兄弟够借**当删除为结点关键字=[m/2]-1【结点下限个数，删了就不够了，得补】则需要调整该结点左右兄弟及其双亲结点位置3）**兄弟不够借**就把父节点的关键字数减少，把其中一个关键字向下合并到该子树中，若父节点关键字不够，则像向上重复。
图示
计算
已知阶、层数、某层关键字数，求最多结点数
阶限定了至少有一个结点，使得其关键字为 阶数-1.同时如果要使得结点数最多，就尽可能让当个结点的关键字减少，从而分裂的更多。层数一定，叉越少结点数越少结点数一定，叉越多，层数越小
B+树
B树的设计思想还是保留了二叉排序树结点存储内容的想法，因此作为一个索引而言还不够轻量。为了通过索引查找，由于索引和值存放在一起（只能放在外存），因此由于内存有限，就必须要反复的在内外存中进行调度，导致IO的开销增大。那能不能把索引和值分开呢，答案当然是可以，B+树就是为了解决这个问题。
图示
B与B+树区别
1）结构上：对于B树而言，关键字本身就是值，而关键字左右两侧才是孩子结点值指针而B+树则是关键字作为索引(内结点不存具体值)，在非叶子结点出现的关键字也会出现在叶子节点中，B+树叶子结点包含了全部关键字。最后在使用指针链接，从而能够顺序查找。根节点关键字数n>=22）查找上：B+树查找，即使找到也要顺着结点查到底B+数适合数据库查找的原因】B+树更适合外部存储。由于内结点不存放真正的数据（只是存放其子树的最大或最小的关键字，作为索引），一个结点可以存储更多的关键字，每个结点能索引的范围更大更精确，也意味着B+树单次磁盘IO的信息量大于B树，I/O的次数相对减少。MySQL是一种关系型数据库，区间访问是常见的一种情况，B+树叶结点增加的链指针，加强了区间访问性，可使用在区间查询的场景；而使用B树则无法进行区间查找
红黑树
定义
红黑树是在AVL树的基础上提出来的。红黑树(R-B Tree)是一种二叉树，但在每个节点增加一个存储为表示节点的颜色（非红即黑）。通过对任何一条从根到叶子的路径上各个着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍。因此，红黑树是一种**弱平衡二叉树**，相对于要求严格的AVL树来说，它的旋转次数少，所以对于**搜索，插入，删除操作较多**的情况下，通常使用红黑树。以下是红黑树的定义，或者可以说是规则```1. 节点是红色或黑色2. 根是黑色3. 所有叶子都是黑色(NULL 节点）4. 任何相邻结点不能同时为红5. **从任一节点到每个叶子的所有简单路径都包含相同数目的黑色节点。（维持一种黑色平衡）**，这点证明了它并非是平衡二叉搜索树。```
性质
**性质**```- 每个节点非红即黑- 根节点是黑的- 每个叶结点（叶结点即树尾端NULL指针或NULL节点）都是黑的- 如果一个节点是红色的，则它的子节点必须是黑色的- 对于任意节点而言，其他叶子点树NULL指针的每条路径都包含**相同数目的黑节点**``````1) 树高度最大为 2(log(n+1))如果把红色删除，则可以得到一个全黑的四叉树，因此此时作为最低高度为 log(n+1) , 1 是底层叶子结点部分。由于不能连续为红，因此红后必有黑. 因此二倍的最低高度，为其最大高度。2) 旋转不会改变树的中序遍历顺序```
应用
常见应用场景```- epoll 内核实现，红黑树管理时间块- linux进程调度 CFS(Completely Fair Scheduler)```
基本操作
变色
变色即 红黑色之间的变换.
旋转
旋转即 二叉树最基本的旋转操作
插入
基本的插入删除操作和平衡二叉树一致.其中插入的结点必为红色，不过如果失衡，则会进行调整
插入调整
我们设定将**要插入的节点标为 N**， N 的**父节点标为 P**， N 的**祖父节点为 G**， N 的**叔父节点为 U**```cppnode *grandparent(node *n) { return n->parent->parent;}node *uncle(node *n) { if(n->parent == grandparent(n)->left) return grandparent(n)->right; else return grandparent(n)->left;}```**情形 1**： 新节点 N **位于树的根上**，没有父节点，在这种情况下，我们将其绘制成黑色节点以满足性质2， 因为它在每个路径上对黑节点数目增加 1， 性质 5 也是符合的。```cppvoid insert_case1(node *n) { if(n->parent == NULL) n->color = BLACK; else insert_case2(n)}```**情形2**： 新节点的父节点 P 是黑色， 所以性质 4 没有失效（新节点的确是红色的），这种情况下红黑树是有效的，性质 5 也没有受到威胁，尽管新节点 N 有两个黑色叶子子节点， 但由于新节点 N 是红色， 通过它的每个子节点的路径就都有通过它所取代的黑色的叶子的路径同样数目的黑色节点，所有依然满足这个性质。```cppvoid insert_case2(node *n) { if(n->parent->color == BLACK) return; else insert_case3(n);}```**情形3**： 父节点 P 和 叔父节点 U 都是红色（此时新插入节点N 作为P 的左子节点或右子节点都属于情形三这里我们演示 N 作为 P 左子节点的情形）则我们可以将它们两个重新绘制为黑色并重绘祖父节点 G 为红色（用来保持性质 5）.现在我们的新节点 N 有了一个黑色的父节点P, 因为通过父节点P或叔父节点 U 的任何路径都必定通过祖父节点 G，在这些路径上的黑节点数目没有改变。注意： 红色的祖父节点 G 的父节点也有可能是红色的， 这就违反了性质 4， 为了解决这个问题，我们**在祖父节点 G 上递归地进行情形 1 的整个过程**。（把 G 当成是新加入的节点进行各自情况的检查。）```cppvoid insert_case3(node *n) { if(uncle(n) != NULL && uncle(n)->color == RED) { n->parent->color = BLACK; uncle(n)->color = BLACK; grandparent(n)->color = RED; insert_case1(grandparent(n)); } else insert_case4(n); }```**情形4：**父节点 P 是红色而叔父U是黑色或没有， 并且新节点 N 是其父节点 P 的右子节点而父节点 P 又是其父节点的左子节点，在这种情形下，我们进行一次左旋转调换新节点， 在这种情况下我们进行一次左旋转调换新节点和其父节点的角色，接着， 我们按情形 5 处理以前的 父节点 P 以解决性质 4 失效的问题， 注意这个改变会导致某些路径通过它们以前不通过的新节点 N ，或不通过节点 P，但由于这两个节点都是红色，所以性质 5 仍然有效。```cppvoid insert_case4(node *n) { if(n == n->parent->right && n->parent == grandparent(n)->left) { rotate_left(n->parent): n = n->left; // 方便 insert_case 5 操作 } else if(n == n->parent->left && n->parent == grandparent(n)->right) { rotate_right(n->parent); n = n->right; } insert_case5(n); }```情形 5 ： 父节点 P 是红色而叔父节点 U 是黑色或缺少，而父节点 P 是其父 G 的左子节点，在这种情况下，我们进行针对 祖父节点G 的一次右旋转； 在旋转产生的树中，以前的父节点 P 现在是新节点 N 和 以前的祖父节点 G 的父节点，我们知道以前的祖父节点 G 是黑色，否则父节点 P 就不可能是红色， （P 和 G 都是红色违反了性质4）， 我们切换以前的父节点 P 和祖父节点 G 的颜色，结果的树满足性质 4， 性质 5 也满足， 因为通过这三个节点中任何一个的 所有路径以前都通过祖父节点 G， 现在它们都通过以前的父节点 P。```cppvoid insert_case5(node *5) { n->parent->color = BLACK; grandparent(n)->color = RED; if(n == n->parent->left && n->parent == grandparent(n)->left) rotate_right(grandparent(n)); else rotate_left(grandparent(n));}```
删除
删除调整
935考纲对比
【考查目标】 1. 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异以及各种基本操作的实现。 2. 掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3. 能够选择合适的数据结构和方法进行问题求解；具备采用c或c++语言设计与实现算法的能力【题型分布】12选择（24分）2综合题（21分）【新增内容】并查集 、分块查找、外部排序
2022】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 【多维数组的存储】和特殊矩阵的压缩存储 三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉搜索树 2. 平衡二叉树3. 哈夫曼(Huffman)树和哈夫曼编码4. 【并查集】 三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 四、查找 (一) 查找的基本概念 (二) 顺序查找法(三) 【分块查找法】(四) 折半查找法 (五) B-树及其基本操作、B+树的基本概念(六) 散列(Hash)表 (七) 查找算法的分析及应用 五、排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort)(九) 基数排序(十) 【外部排序】 (十一) 各种排序算法的比较 (十二) 排序算法的应用
2021】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储 三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉排序树 2. 平衡二叉树 3. 哈夫曼(Huffman)树和哈夫曼编码 三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 四、查找 (一) 查找的基本概念 (二) 顺序查找法 (三) 折半查找法 (四) B-树及其基本操作、B+树的基本概念(五) 散列(Hash)表 (六) 查找算法的分析及应用 五、内部排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort) (九) 基数排序 (十) 各种内部排序算法的比较 (十一) 内部排序算法的应用
树
该思维导图就是一个树形结构
基本概念
高度
结点高度
从叶子结点开始自底向上逐层累加
树的高度
树中结点的最大高数
层数/深度
注意题目中从第0层开始计算还是第1层开始计算，默认第一层开始
结点深度
从叶子结点开始自顶向下逐层累加
树的深度
树中结点的最大深度
祖先、子孙、兄弟、双亲；堂兄弟
和家族族谱图的关系一致
度
注意树的度和图的度之间的区别；结点度为结点**孩子个数** = 除连接父节点以外的边个数
结点的度
该结点孩子个数
树的度
树中结点的最大度数
结点
除根结点以外各结点只有唯一前驱
分支结点
叶子结点
有序树与无序树
路径和路径长度
默认有向树，从父结点指向子结点
路径
两个结点之间所经过的结点序列构成
路径长度
路径上所有经过的边的个数之和
森林
m(m>=0)棵互不相交的树的集合。例如把树根结点删除变形成一个森林
性质
结点与度数
结点数(m)=非叶子结点数+叶子节点数
结点数 = Σ 度 x 个数 + 1【根】
结点总数等于度从1到n的所有结点个数之和+1(根)
除了根结点以外都是一边对一个结点
结点个数
任何树的第一层默认为根
高度为 h 的 m 叉树至(最)多结点数
等比数列求和：1+m+..+m^h-1 = a1 * (1-q^n)/(1-q)= (1-m^h)/(1-m)
sp: 高 h 的二叉树结点至多为
偶数个结点的二叉树，其 度数为1 的结点个数必然为奇数
最小高度
n 个结点的 m阶树/m叉树/完全 m 叉树 的高度 【必背】
由于 n个结点 m 叉树的结点数最多为假设n个结点高度为k+1，则 (m^k-1)/(m-1)
最大高度
n个结点，度为m的树最大高度
类型
二叉树
定义
如果某结点只有一个子结点，则必为左孩子
结点个数 ,含有左右子树的有序树
性质
一般计算题会给出完全二叉树用于计算
个数相关
叶子结点个数
```n=n0+n1+n2 ; // n为总结点数,n0度为0的结点n=m+1 ; //m为边数m=n1+2*n2 + 1n0+n1+n2 = n1+2*n2+1n0=n2+1```
第k层最多结点数
高度为h至多结点个数
下标相关
左右孩子
i 结点的左孩子编号 = 2i
i 结点的右孩子编号 = 2i+1
深度相关
结点所在深度
完全二叉树】深度
严格二叉树的最大深度
只含有度为0和2节点的二叉树
(n+1)/2
指针个数
n个节点的二叉链存储节点空指针个数为 n+1
N 个结点的二叉树，有 N+1 个空指针
遍历访问序
次序合法性
遍历顺序合法性使用 中序(必须) + 前/后序 确定具体二叉树，再检验其他
访问序确定二叉树形状
必要条件```中序 + 前/后序```
左必在右的前面被访问
前中后序的访问序列，叶子结点序列不变
高度等于其结点数时，先序和后序遍历序列相反
类型
满二叉树
定义
完全二叉树
定义
层都是满的，同时第 层按照从左往右顺序填结点
每个结点都与高为 的满二叉树编号为 的结点位置一一对应
性质
若一个结点没有左孩子，则其必然是叶结点
叶子结点的双亲的左兄弟（若存在）则必然不是叶子结点
父节点左兄弟不为叶子结点
高度为 h 的完全二叉树，节点个数最小为
最后一个分支 (非叶) 结点序号为
若某完全二叉树有 个结点，则其叶子节点个数为
计算
第 x 层有 k 个叶子结点，求结点个数max/min情况
结点个数最少为：结点个数最多为：
存储结构
顺序存储
主要利用左右孩子结点下表关系存储
链式存储
n个结点的二叉链表中右 n+1 个空链域```typedef struct BiTNode{Elem data; //数据域struct BiTNode *lchild,*rchild; // 左右孩子指针}BiTNode,*BiTree;```
遍历
先、中、后主要指的是，**根**在访问时的相对次序，左右子树次序相对不变遍历空间复杂度主要指 栈的深度类似的，前、中、后缀表达式，指的是符号相对数字的相对位置定序的核心方法在于，通过 根左右的相对顺序，先把根求出，再划分子树位置。
先/前序(NLR)
1) 子树遍历```中序遍历最后一个结点在它的左子树中(当最右子树没有只有左孩子时，会按照 根->左进行访问，此时右子树左孩子次序>最右子树次序)```2.1）最后访问为叶子结点```如果某叶子结点为前序最后访问，则必为中序最后访问```2.2) 叶子结点相对次序```前中后相对访问次序相同```
中序(LNR)
1) 子树遍历```前序遍历最后一个结点在它右子女指针走到底```2）叶子结点```如果某叶子结点为前序最后访问，则必为中序最后访问```
后序(LRN)
1）先后次序```n,m为两个结点，n在m次序前条件为:n在m左方/n为m子孙```2) 路径查找```n为m的祖先，则利用后序查找能够找到n到m的路径```
树和森林
定义
度为m的树 m叉树
度为m的树：该树结点的最大度数为mm叉树:有许多类型```严格m叉树:只有度数为0和为m的结点完全m叉树```
森林
森林(forest)是m(m≥0)棵互不相交的树的集合。任何一棵树,删除了根结点就变成了森林
存储结构
双亲表示法
```#define MAX 100typedef struct{ ElemType data; int parent;}PTNode;typedef struct{ PTNode nodes[MAX]; int n;}PTree;```
顺序存储；存储地址=逻辑地址
孩子表示法
邻接表存储；有向图存储结构
孩子兄弟/二叉树表示法
左子树孩子，右子树兄弟```typedef struct CSNode{ Elem data; struct CSNode *fchild,*nsible;}CSNode,*CSTree;```
森林结点数
已知森林边和结点数，求森林中包含的树的个数
森林和二叉树关系
右孩子指针为空的结点个数
设F是一个森林,B是由F转换过来的二叉树.若F有n个非终端结点，则B中右指针域为空的结点有n+1个。```无右指针，即无右兄弟结点。转化后，森林最后一棵树的根结点无右结点每个非终端结点的最后一个孩子，也无右结点```
森林左子树结点数=森林第一棵树结点树
遍历以及有序树
主要是讨论有序树T转化为二叉树T1后，两棵树之间访问序的对应关系1) 树 / 森林1.1) 先根 / 先序```先遍历树根，再依次遍历其子结点；根 -> 孩子 -> 兄弟```1.2) 后根 / 后序```孩子 -> 兄弟 -> 根```2）二叉树2.1) 先序```在转换为二叉树后，孩子在左结点，兄弟在右结点。所以先序， 根 -> 孩子 -> 兄弟```2.2) 中序```由左根右可得：孩子 -> 根 -> 兄弟而转化后的孩子在最左位置，所以与森林后序遍历相同```理解】 兄弟最后访问，所以只需要考虑根和孩子的先后顺序即可可以想一想森林对应存储方式一个结点，以及连接其子结点的边。```PreRootSearch(int u){info(u);//先处理根的信息for(auto e:E()){PreRootSearch(e.v);//按照其边的存储顺序，顺序遍历下一个子结点位置}```那么对应二叉树的处理，必然是前序遍历，即根左右而森林后序即后根遍历，则是先访问子结点后访问根结点。由于森林的二叉树形式是兄弟为右子树，所以这个中序遍历即，先子后兄弟再双亲
树：先根
森林：先序
二叉树：先序
树：后根
森林：后序
二叉树：中序
树、森林和二叉树转换
左子为第一个孩子，右子结点为层次遍历的兄弟结点反向转换规则同理所以转换结果的二叉树，根没有右子树【根无兄弟】
森林由多棵树组成，每个树的根互为兄弟。先将每棵树转化为二叉树，再将根节点作为兄弟相连。反向转换规则同理
遍历
BFS广度优先搜索
复杂度分析
生成树与生成森林
DFS深度优先搜索
遍历与连通性
递归与非递规转换
```void XOrder(){【初始化栈】【初始化遍历指针】 while(p||IsEmpty(S)){ if(p){ vis(p);//【先序访问位】 push(S,p); p = p->lchild; }else{ Pop(S,p); 【中序访问位】 p=p->rchild; }}```
递归 = 栈
层次遍历
辅助队列
遍历序列构造二叉树
中序(必须)+先序/后续
中序遍历:(左(根)右)根(左(根)右)先序：根((根)左右)((根)左右)后续：(左右(根))(左右(根))根由 先序/后续 确定树根，然后利用中序，划分主根左右子树，之后再依次递归判断顺序
线索树遍历需要栈
后序遍历
求祖先到子孙的路径可以使用先/中序遍历
要求祖先到子孙的路径，只能先子孙后祖先所以只能采取后续遍历的方法
已知次序求二叉树异构个数
主要利用栈序列计算来求解（卡特兰数）```已知先序，求异构数:即已知先序入栈序，求不同中序出站顺序可能数```
应用
2022/4/12AVL内容调整
哈夫曼树
带权路径长度
定义
带权路径长度(WPL)最小的二叉树；也称最优二叉树
度为 m 的哈夫曼树，为严格的 m 叉树
构造
贪心，每次取两个权值最小的结点作为新结点的左右子树新结点权值为左右子树和，并放入到可选择的结点集合中
性质
初始结点均为叶子结点
权值越小到根节点路径越长
新建了n-1个结点，结点 总数 为 2n-1
度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为
注意，度为m的哈夫曼树为严格的m叉树
叶子结点个数即为不同符号的编码数
哈夫曼编码
固定长度编码
每个字符用相等长度二进制位表示
前缀编码
没有一个编码是另一个编码的前缀
线索二叉树
1) 引入目的```为了加快结点查找的前驱或者后继速度```2) () 结构```是对二叉树(逻辑结构)下通过物理结构进行扩充信息。是一种物理结构```
物理/存储结构
引入标签```(lchild,ltag,data,rtag,rchild)```
标志域含义
前驱后继与具体使用的搜索次序有关
概念
线索
由于N个结点的二叉树有N+1个空指针。为了加快查找结点前驱和后继的速度，利用这些空链域记录直接前驱后继的指针，称为线索。
线索化
对二叉树以某种次序的遍历使其成为线索二叉树的过程被称为线索化。
相关问题
线索化后的空链个数
无前驱和后继位置结点的空链域不能线索化```1) 先序左子树为空的二叉树先序线索化后，空链域个数为 2根 + 最后访问叶子2) 中序3) 后序```
仍需要栈支持的遍历为 后序线索树
由于某结点的右子树存在，且后继一定不为 右子节点，导致后继线索缺失。而前序和中序，则是要么线索存在，要么就是其右节点为后继
不是每个结点都能通过线索查找其前驱后继
已知后序线索二叉树，求后序后继仍不能完全求解
由于某结点的右子结点为其前驱，而其右子结点占用其右指针，所以该结点的后继指针不一定存在。
二叉搜索树 BST
二叉查找树（Binary Search Tree）**（又称：二叉搜索树，二叉排序树）**【注意别称，之前被坑过一次，和二叉判定树名字较类似】左子树上所有关键字小于根节电关键字，而右结点则均大于。
定义
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树
操作
插入
所以插入的新结点均作为叶子节点
查找
递归实现
非递归实现
删除
叶结点直接删除
x 只有一个左/右子树子结点接上其父节点
x 有左右两棵子树补前驱后继
中序遍历前驱后继，也是关键字大小的前后继
构造
性质
删除某节点后将其插入，则前后排序树有可能不同
题目计算
ASL(平均查找长度）
成功查找长度
失败查找长度
递增序列遍历=中序遍历
非法查找路径序列
由于 每次从根会往左右子树(小，大)区间搜索，如果在小区间序列查找经过比根的值还大，则不合法。即左子树路径不存在比根更大的值，右子树路径不存在比根更小的值
平衡二叉树AVL
AVL 二叉平衡树，本质上是为了解决二叉搜索树退化情况而增加平衡机制得到的新数据结构.优点是保证查找时的稳定 **O(logn)**复杂度。但是坏处也明显，对于反复插入删除操作，由于需要不断的平衡操作，因此会照成大量的耗时。
平衡机制
平衡的核心就是根结点的左右子树高度差绝 ≤ 1 , 因此对于因为插入或者删除操作而导致失去平衡时就要进行调整。左右子树的高度差在该数据结构中被称为**平衡因子**平衡因子 = 左子树 - 右子树
平衡因子
双亲结点因子=左子树高度 - 右子树高度
操作原理
插入/删除
插入(删除)结束后，检查其插入路径上的结点平衡因子的绝对值是否大于1，如果有，则找到**插入路径上**离插入位置**最近的**不平衡结点 进行调节。
旋转
LL,LR指的是相对**插入路径上**离插入位置**最近的**不平衡结点为根的位置。LL即左子树的左节点引起
旋转要点
调整最小不平衡子树
LL,RR 旋一次，LR,RL 旋两次（先内后外）
左重顺旋减轻左深，右重逆旋减轻右深
LL，RR旋转最小不平衡字数，减少一层，其父节点全部减少一个因子，达到平衡
根连前驱后继【按照数值大小比较连接】
旋转方式
LL(左孩子左子树)
左子树右旋(顺)，左子替换根[根失去左孩子]左子就把自己的右子树给了根当左孩子[根前驱替代为新左子树]【记忆】左左失衡，左旋转，降低一层就平衡）【操作】(A为离根结点最远的的不平衡结点)以 A 的 左孩子 固定为新的根 右旋一次并将 A 连接为其右子结点原本右节点按照前驱后继关系连接[比大小]
左子树旋转，降低一层就平衡
RR(右孩子右子树)
LL, RR 为单次旋转。操作同理
LR(左孩子右子树)
两次旋转；记A为根，B为根(A)的左孩子,C为B的右孩子第一次旋转：由于B的右孩子重了，所以先将C左旋替换B这样A的左孩子又重了，进行第二次旋转第二次旋转：将C右旋，替换掉根，这下B作为C的左孩子，A作为C的右孩子，从而平衡
RL(右孩子左子树)
计算
原理：前三层好理解，0,1,2. 第 n 层时，由于左右子树层差小于1，所以需要选择一个层数为 n-1 平衡且构成个数最小的子树，以及一棵高位 n-2 的平衡且个数最小的子树。将这两棵作为左右子树，连接在一个新结点上，层数即为 n. 所以再利用递归的思想，可以得到递归写法。再由递归转递推的方法，写除递推程序【类似求 斐波那契数】 递归、递推进行计算```\\递归写法int RNum(int k){ if(k == 0) return 0; if(k == 1) return 1; return RNum(k-1)+RNum(k-2)+1;}\\递推写法int ans = 0,b = 1,c = 2;for(int i=1;i
构造一棵高为 h 的 AVL 所需要的最少结点数
已知共有 n 个结点的 AVL，求其最大深度
已知AVL的高度为 n,且所有非叶子结点的平衡因子为 1,求结点总数
并查集
操作
原理其实很简单，就是把一个集合逐渐与其他集合合并，同时呢，集合以树的形式表示，即某节点 x以及其所有子树构成的结点为一个集合，集合的名字也以 x命名。在合并集合时，就把其中一个父节点指向另一个集合即可。在合并操作中有按秩合并和路径压缩两种优化方式，不过这个一般不会考察深入，了解即可
合并 Union
```void union(int S[],int r1,int r2){int f1 = Find(r1),f2 = Find(r2);//找到祖先if(f1 != f2) s[r2] = r1; // 表示 r2 集合合并到 r1的集合中，且以 r1为父节点}```
寻找祖先 Find(S,x)
```int Find(int S[],int x){return x == S[x]? x : S[X] = Find(S[X]);//路径压缩}```
初始化 Init(S)
```void init(int S[],int size){for(int i=0;i
图
相关概念
有向图
弧头(顶点)
弧尾(顶点)
无向图
简单图、多重图
简单图：无自环，无重复边
多重图：有自环，重复边
完全图
简单图的边数达到上限
子图
边和顶点均为子集且能够形成一张图
连通、连通图和连通分量
连通：u,v之间存在路径
连通图：图中任意两点均连通
连通分量：无向图中极大连通子图
总共n个点，由于边是随意连接的要让前n-1个点连通，而第n个点不连通，则是不连通时候的最大边数，将第n个点连接入前n-1形成完全图中，则多增加一条边即可【注:随意连接可以理解为最小最大问题】
强连通、强连通分量
强连通:有向图中的u,v互相可达
强连通图：有向图中任意两点互相可达
强连通分量：有向图中极大墙连通子图
生成树、生成森林
生成树：包含图中全部顶点的一个极小连通子图
生成森林：非连通图中连通分量的生成树构成了生成森林
极小连通子图：保持图的联通性，又使得边数尽可能少
顶点度，入度和出度
顶点度：无向图中顶点所连边数
边的权和网
网：带权图
稠密图、稀疏图
路径、路径长度和回路
路径：顶点序列【由顶点和相邻顶点序偶构成的边所形成的序列】
回路/环：路径中第一个和最后一个顶点相同
简单路径、简单回路
距离
有向树
无向图森林
n个顶点，e条边的无向图森林树的个数
存储结构
稀疏矩阵
十字链表
弧(tailvec，headvex，hlink，tlink,info)tailvex: u【弧头结点】headvex: v【弧尾结点】hlink: 指向相同弧头的下一条弧tlink: 指向弧尾相同的下一条弧相当于对邻接表存储和操作进行了一定的扩展[按照**稀疏矩阵**的想法实现}【可以理解为：十字链表=邻接表+逆邻接表】有向图存储结构
邻接表法
利于稀疏图的存储【有向图】寻找是否存在 u->v的边时需要遍历，复杂度为O(n), 而邻接矩阵为O(1)```#define Max 100typedef struct ArcNode{ int adjvex; // 弧头顶点 struct ArcNode* next; // 下一条弧指针 //边权}MGraph; typedef struct VNode{ Vertex data; //顶点信息 ArcNode *first; //第一条弧的指针}VNode,AdjList[Max];typedef struct{ AdjList vertices; // 邻接表 int vnum,arcnum; // 顶点数，弧边数}ALGraph;```
邻接多重表
【无向图】存储结构
稠密矩阵
邻接矩阵
```#define Max 100typedef struct{ Vertex V[Max]; // 顶点表 Edge E[Max][Max]; // 邻接矩阵； 边表 int vnum,arcnum; // 顶点数，弧数}MGraph; ```
有向图
有向图有向边，行下标(弧尾) -> 列下标(弧头)
无向图
对称矩阵存储，下三角和上三角存储效果相等
性质
遍历
广搜bfs
性能分析：空间复杂度：O(V)[ 队列Q ]时间复杂度：邻接表 —— O(V+E)邻接矩阵 —— O(V^2)
深搜dfs
性能分析：空间复杂度：O(V)[ 队列Q ]时间复杂度：邻接表 —— O(V+E)邻接矩阵 —— O(V^2)
应用
最小生成树
包含图中所有顶点，并且只含尽可能少的边，所形成的树(特殊的图)
Prim算法
更新点集合，每次寻找点集所相连且未放入边集的最小长度边，并将其点更新到集合中时间复杂度：O(n^2) -> 堆优化 O(nlogn)【注：Prim在稠密图中比Kruskal优,在稀疏图中比Kruskal劣Prim堆优化效果最好，但是空间花费大，代码复杂】
Kruskal算法
维护边集，每次寻找长度最小的边，且两边端点不全在点集中，则更新长度可以通过排序维护，时间复杂度可降至O(|E|log|E|)
最短路径
Dijkstra
贪心，维护点集合，类似Prim算法缺点：不能求解负权图
Floyd
算法思想：对于图(邻接矩阵)而言，选择起点i,终点j,遍历寻找是否有中间结点k能够使得 (i->k->j) j)的长度，这样就可以更短 缺点：时间复杂度高
有向无环图表达式
拓扑排序
拓扑排序1）找到没有前驱结点/入度为0结点输出2）删除其相关联的有向边3）重复 1）、2）逆拓扑排序1）找到没有后继结点/出度为0结点输出2）删除其相关联的有向边3）重复 1）、2）
AOV网
有序序列个数
关键路径
**源点：**唯一一个入度为0的点**汇点：**唯一一个出度为0的点**关键路径：**从源点到汇点的所有路径中，路径长度最长为关键路径**关键活动：**关键路径上的活动【关键路径上的活动事件最早和最迟发生时间相同】**e/边:**活动**v/结点:**事件【理解】把整张图想象成一个蚂蚁巢穴，巢穴有很多洞[顶点]以及通往洞的路径[边]，很多蚂蚁同时从源点出发，且速度相同。只有当通完该洞的所有路径均被蚂蚁走完，到达此洞的蚂蚁才能够再次同时出发，否则要等待还未到的蚂蚁。**事件最早时间**：即走通往该洞的最长路径蚂蚁在出发前没有摸鱼，因为他最后到达，所以他所有摸鱼的时间，都会增加先到达蚂蚁的等待时间。**事件最晚时间**：先到的蚂蚁表示不公平，为什么要等待最后到的蚂蚁，所以他们可以摸会鱼再出发，只要最后和本应该最晚到的蚂蚁一起到即可。**活动最早时间**：活动最早 = 事件最早**活动最晚时间**：活动最迟 = 时间最晚-经过路径[即：最迟出发时间 = 最迟必须到洞的时间 - 要走路的时间/路径时间]
AOE网
事件最早发生时间
拓扑序求最早事件发生时:即前驱任务最晚完成后立刻开始max(ve(j)+W(vj,vk))；**即到该顶点 j 的最长路径**
事件最迟发生时间
逆拓扑序求最晚事件发生时即后继时间固定，前驱时间最迟开始时间；**用最长路径值-当前路径值**;
活动最早开始事件
活动和事件的区别在于：事件为定点，而活动为边；活动早开始 = 事件最早开始
活动最晚开始时间
活动早开始 =
时间余量
时间余量为0的边，则为关键活动
排序
基本概念
关键字有序过程
稳定性
关键字相同元素再排序后仍然保持排序前相同顺序【稳定】，否则称之为不稳定；**常见稳定排序：**直接插入排序折半插入排序冒泡排序归并排序基数排序**常见不稳定排序**希尔排序【插入排序的一种，但是增量会发生改变，所以划分组的不同，可能会产生影响】快速排序选择排序堆排序
具体元素未知，至少比较次数
未知具体元素至少比较次数按照**最坏情况下**的最少比价【最优比较】即logn复杂度的快排
趟
排序过程中，对尚未确定最终位置的所有元素进行一遍处理
相当于完成一个内循环
内部排序
内存中进行的排序（称为内部排序）
常见类型
插入排序
直接插入
**算法思想**假设顺序进行到第i位置；那么前i-1位已经排好序，后n-i位还处于无序状态【可能】则此时，将第i位元素按照有序规则，插入到前i-1位中，形成前i位有序；对于插入位置的寻找，如果是顺序遍历则为直接插入，如果使用折半搜索，则是折半插入顺序遍历一般是从第i个位置往前，逆着找插入排序由于涉及大量插入操作，所以链表结构比顺序结构效率更好
时间复杂度
稳定排序
特点
每一次排序完后，前i位有序，i位以后也可能存在使得原i位发生改变的值
折半插入
对已排好序列查找部分使用折半搜索
顺序存储
即使在前i位查找时间位 nlogn,但是由于只能用顺序存储实现，所以加上移动原因也许要n^2
时间复杂度
稳定排序
希尔排序
又称【缩小增量排序】有点分治思想的味道；假设增量为d,则每次比较位置为 x,x+d,...
算法描述选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序
时间复杂度
空间复杂度
不稳定排序【分组原因】
交换排序
冒泡排序
算法描述【最大泡泡冒起来】每一次排序将最小/最大的元素，通过依次遍历比较交换，放到序列末尾/队首最终位置
时间复杂度
空间复杂度
稳定排序
特点
前i位或者后i位(根据顺序或逆序)为最终有序排序
快速排序
基于分治思想【二分】
时间复杂度【与递归栈的深度有关】
空间复杂度【栈深】
特点
某个值的左边均为小于它的值，右边均为大于它的值
当序列基本有序或者逆序情况下，效率最低：受不平衡划分影响
真题
2014) 对 15 个元素进行快排，则比较元素次数最少是
错因】直接利用了 nlogn 平均时间复杂度计算；其次，此题是不考虑最坏最优情况，而是绝对最有情况解析】当15个元素完全有序时 7 1 7 3 1 3 3 1 31 1 1 1 1 1 1 1 1 1 1 1总计： 7*2+3*4+8*1=34
选择排序
简单选择
选择排序和插入排序比较：**相同**当前遍历到第i位时，前i-1位均为有序；而对于选择排序而言，前i-1位即是最终前i-1位的位置，而对于插入排序则是最终子序列状态；**不同**选择排序是找到后 n-i位的最小值从而交换到相应位置，而插入排序则是将第i位插入到前i位有序位置
算法描述每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换
时间复杂度
空间复杂度
不稳定排序【多个最小取最后遍历位置】
特点
前i位或者后i位(根据顺序或逆序)为最终有序排序
堆排序
操作描述：基于二叉堆[数组]【建堆】二叉树的顺序存储方式从i=[n/2]-1【只需要调节一半的原因是，二叉堆是一棵完全二叉树，叶子结点占到一半个数，同时按照层次建立的想法，从倒数第二层开始建立堆的有序】序号减小方向逐个进行排序。每个向下或者向上进行排序```//大根堆 void HeadAdjust(int A[],int k,int len){ A[0]=A[k];//存储遍历根值 for(int i=2*k;i0;i--){ HeadAdjust(A,i,len); }}```【插入】新结点防至堆末端，在对这个新结点向上执行调整操作
算法描述二叉堆：完全二叉树，左右子树均小于/大于根结点【小/大顶堆】
时间复杂度
空间复杂度
建堆时间【计算补充】
特点
最后一个非叶子结点位置为len/2【根结点下标为1】
不稳定排序【调整时可能调节后面位置到根】
归并排序
算法描述二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列
时间复杂度 【与序列初始状态无关】
空间复杂度
稳定排序
特点
当有足够大到内存装不下的文件进行排序时，采用分治的归并排序
基数排序
算法描述基于关键字位上数字大小进行逐一排序
时间复杂度
空间复杂度
常见关键字排序
最高位优先 MSD
最低位优先 LSD
稳定排序
排序比较
时间复杂度
有序情况下
直接插入、冒泡排序
快排
无序情况下【平均】
简单选择、直接插入、冒泡排序
堆排，快排、归并
空间复杂度
简单选择、插入、冒泡、希尔、堆排
快排
归并
算法稳定性
关键字相同元素再排序后仍然保持排序前相同顺序【稳定】，否则称之为不稳定；
稳定排序
直接插入排序折半插入排序冒泡排序归并排序基数排序
不稳定排序
希尔排序【插入排序的一种】快速排序选择排序堆排序
存储结构影响
顺序存储
受存储结构影响的排序依赖于顺序存储随机存储性:常见顺序存储排序】希尔排序堆排序折半插入
链式存储
插入排序
算法过程特征
【每趟排序能够得到至少一个最终有序序】
堆排序，快速排序、简单选择、冒泡排序
【比较次数与初始序列】
无关二路归并排序、简单选择排序、基数排序
有关快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
【排序趟数与初始序列】
无关直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
有关冒泡排序、快速排序
【冒泡排序】趟数与数据有关，优化冒泡排序的最优复杂度为O(n)，其主要优化就是记录了前一趟是否冒泡，如果没有产生冒泡就说明数组已经有序，直接return。如果产生了冒泡，才继续执行。【快速排序】的排序趟数就是它的递归深度。当 快排 的数据是有序时候，会退化为冒泡，所以快排趟数也与初始序列顺序有关了
外部排序
文件通常按快存储在磁盘上，OS也按照块对磁盘信息进行读写。由于文件中记录信息很多，所以无法将整个文件复制进入内存中进行排序。因此要将待排序的记录存储在外存上，排序时再把数据一部分地调入内存中进行排序。排序过程中需要多次进行内存和外存之间的交换。因为磁盘I/O的时间远超于内存运算时间，所以外部排序主要考虑的是访问内存次数。
基本概念
一般方法归并排序法
外部排序总时间 = 内存排序时间 + 外存信息读写时间 + 内部归并所需时间
归并躺数 = 树的高度 =
归并总比较次数 ==
外部排序的时间复杂度主要由：归并路数初始归并段归并比较次数
I/O 操作次数读入归并段，写入归并段（以块为单位）
图解
初始序列为12个无序数据
把内存数据划分为多个块，首先对块内进行排序，形成有序字串
将两个已经排序好的子块进行归并成一个更大的块【二路归并】
继续将小的归并段合并为更大的归并段
多路平衡归并与败者树
利用败者树增加归并路数
k 路平衡归并
最多只能有 k 个段归并为一个
每一趟中，若有m个块进行归并，则一趟处理得到个块
胜者树/败者树
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。【注：胜利或者失败规则要具体根据题目要求来确定】胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到【败者树很像求min/max值的线段树】
胜者树
胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果
败者树
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程【注：败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关
利用败者树加快排序
```外部排序最耗时间的操作时磁盘读写，对于有m个初始归并段，k路平衡的归并排序，磁盘读写次数为|logkm|，可见增大k的值可以减少磁盘读写的次数，但增大k的值也会带来负面效应，即进行k路合并的时候会增加算法复杂度，来看一个例子。把n个整数分成k组，每组整数都已排序好，现在要把k组数据合并成1组排好序的整数，求算法复杂度u1: xxxxxxxxu2: xxxxxxxxu3: xxxxxxxx.......uk: xxxxxxxx算法的步骤是：每次从k个组中的首元素中选一个最小的数，加入到新组，这样每次都要比较k-1次，故算法复杂度为O((n-1)*(k-1))，而如果使用败者树，可以在O(logk)的复杂度下得到最小的数，算法复杂度将为O((n-1)*logk)， 对于外部排序这种数据量超大的排序来说，这是一个不小的提高```
置换-选择排序
增加归并段长度减少归并段个数
原理
由于多路归并的初始段建立采用，将文件划分n组[每组的大小尽可能装满单内存空间]然后再利用内存进行内部排序，从而形成初始归并段，但是也意味着，必须将其划分为n组置换-选择排序则是将初始归并段减小的一种排序法
初始段建立图解
```1.首先从初始文件中输入 6 个记录到内存工作区中；2.从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；3.然后将 MINIMAX 记录输出到归并段文件中；4.此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；5.从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；6.重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；7.重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。```
每组划分6个元素，则初始组数至少划分4组
选择出第一个 MINIMAX 29
选择比初始段中更大的 MINIMAX 38
同理
直到无 MINIMAX 选出，此时认为初始段已经完成
败者树利用
同上一节所用到的败者树不同的是，在不断选择新的 MINIMAX 记录时，为了防止新加入的关键字值小的的影响，每个叶子结点附加一个序号位，当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。在初期创建败者树时也可以通过不断调整败者树的方式，其中所有记录的序号均设为 0 ，然后从初始文件中逐个输入记录到内存工作区中，自下而上调整败者树。
最佳归并树
由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树
原理
通过以构建赫夫曼树的方式构建归并树，使其对读写外存的次数降至最低（k-路平衡归并，需要选取合适的 k 值，构建赫夫曼树作为归并树）。所以称此归并树为
附加虚短的最佳归并树
在一般情况下，对于 k–路平衡归并来说，若 (m-1)MOD(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)MOD(k-1)-1 个虚段
额外补充虚断数
C11语法
实际上数据结构部分只需要熟悉C语言中struct部分的语法即可.当然由于408参考书目中使用的是C语言代码，所以结构体中还是使用的指针作为连接方式，没有使用C++的STL。指针，也是必须熟悉的部分---其他详细内容参考 我的另一篇思维导图[C++(Cpp)笔记](https://www.processon.com/view/61dc27837d9c0806a89c324c)
typedef 关键字
typedef 与 "#define""#define" 即宏定义，是存粹的文本替换。在正式编译前的**预处理**中，预处理器会根据代码中的 "#define" 宏定义进行杨哥替换，直到文件结束或者对应的 #undef 指令位置【也就是说，"#define" 生效于 编译器把文本翻译为文本阶段(预处理)】typedef 用来为复杂的声明定义简单的别名例如 typedef long long ll;这个处理在**编译阶段**由编译器进行处理
struct 结构体
语法
不带 typedef 标签
不带 typedef 标签
定义】```struct T(结构体名称){ ElemType(元素类型) elem(元素名)； ...};```定义结构体的同时定义结构体变量】```struct T(结构体名称){ ElemType(元素类型) elem(元素名)； ...}t1,t2;// t1,t2在后续就可以直接使用```初始化】```struct T t = {elem,...}; //含初始值struct T *t = NULL; //结构体指针```赋值】```t = {elem,...}; ```
带 typedef 标签
带 typedef 标签【相当于把struct T的名字取了个别名叫 T(少写struct)】但是在实际开发中一般少这样定义结构体，不然别人不知道这是什么类型，结构体或者单独的变量? [linux内核不采用typedef](http://lkml.iu.edu/hypermail/linux/kernel/0206.1/0402.html)```typedef struct{ ElemType elem; struct T* next;}T,*TLink; //['*Tlink'表示声明结构体指针'*T'别名为TLink]// 初始化T t = {elem,...};TLink tlink = NULL;```
错误语法
常见错误缺少结构体名称】```typedef struct{}LNode;struct LNode L;//会报错LNode L;//不会报错```使用typedef又不加别名】```typedef struct T {};T t;```
结构体嵌套
自引用
结构体的自引用(self reference)，就是在结构体内部，包含指向自身类型结构体的指针。1.1 不使用typedef时```错误的方式：struct T{ struct T A; int value;};这种声明是错误的，因为这种声明实际上是一个无限循环，成员A是一个结构体，A的内部还会有成员是结构体，依次下去，无线循环。在分配内存的时候，由于无限嵌套，也无法确定这个结构体的长度，所以这种方式是非法的。正确的方式： （使用指针）struct T{ struct T *A; int value;};由于指针的长度是确定的（在32位机器上指针长度为4），所以编译器能够确定该结构体的长度。```1.2 使用typedef 时```错误的方式：typedef struct { int value; NODE *link; } NODE;这里的目的是使用typedef为结构体创建一个别名NODEP。但是这里是错误的，因为类型名的作用域是从语句的结尾开始，而在结构体内部是不能使用的，因为还没定义。正确的方式：有三种，差别不大，使用哪种都可以。复制代码1)typedef struct T1{ int value; struct T1 *next; } NODE;2)struct T2;typedef struct T2 NODE;struct T2{ int value; NODE *next; };3)struct T3{ int value; struct T3 *next; };typedef struct T3 NODE;```建议使用第三种，逻辑更清晰；定义结构体T3，在对T3进行别名.
相互引用
结构体的相互引用（mutual reference），就是说在多个结构体中，都包含指向其他结构体的指针``````
C与C++中 struct 区别
C++中的struct是对C中的struct进行了扩充，所以增加了很多功能1. 声明时的区别 | | C | C++ | | -------- | ---------------------- | ------------------ | | 成员函数 | 不能 | 可以 | | 静态成员 | 不能 | 可以 | | 防控属性 | 默认public，不能修改 | 有三种，默认public | | 继承关系 | 不可以继承 | 可从其他结构体继承 | | 初始化 | 不能直接初始化数据成员 | 可以 |2. 使用过程中的区别 **在C中使用结构体时需要加上struct，或者对结构体使用typedef取别名，而C++可直接使用**，例如： ```c++ 结构体声明，C和C++使用同一个 struct Student{ int iAgeNum; string strName; } typedef struct Student Student2；//C中取别名 struct Student stu1; //C中正常使用 Student2 stu2; //C中通过取别名的使用 Student stu3; //C++使用 ```3. 模板中的使用 class这个关键字还可用于定义模板参数，就像typename。但是strcut不用与定义模板参数，例如： ```c++ template //可以把typename 换成 class int Func( const T& t, const Y& y ){ //TODO } ```
指针 T *t
地址与值
```//赋值 int * 变量，表示变量所存储的信息为地址值int *p = NULL;int a = 10;p = &a;//输出 printf("指针地址:%d,指针所指值(变量地址,变量的值:%d):%d",&p,p,*p);```
& 取地址/引用(别名)
注意 & 在 取地址和引用之间功能的区别```//取址【把变量的地址拿出来】int a = 0;int *p; // 指针变量 pp = &a;//引用【取某个变量的别名】int & x1 = x; //x1和x的地址一样，值也一样[都是同一个东西，叫法不同，编译器会进行解释]//把某变量传入func中，且别名为 avoid func(int &a){};```