上面这首曲子是“All That We Are”
学习本笔记三个建议
1.无需做笔记
2.短阅读，长做题，多周期
3.唯一真神：重复的力量
主页
线性代数
高等数学重难点

数据结构的三要素

逻辑结构

            
集合：元素之间没有特定关系
线性结构：一对一    栈
树形结构：一对多    树
图形结构：多对多    图

存储结构

顺序存储：数据元素按顺序存储在连续的存储空间中，例如数组，队列。
链式存储：数据元素通过指针链接，例如链表。
索引存储：为数据元素建立附加的索引表，例如数据库的索引。
散列存储：通过散列函数将数据映射到散列表，例如哈希表。
---------------------------------------------
很多人有个误区在这里
索引存储是顺序存储+索引
散列存储是顺序存储+散列

数据的操作

数据的操作包括对数据的增、删、改、查等基本操作。这些操作基于数据的逻辑结构和存储结构实现。

总结

这部分的内容来说，就题目判断一个东西是否为逻辑结构和存储结构
很大一部分不好判断，并且你写的莫名其妙的，答案也是莫名其妙的，总感觉无论选什么，答案总是能够圆谎一样
没办法，只能积累，目前栈 树 图是地地道道的逻辑结构
中间有个万金油，就是链表 它既可以是两种中的任意一种
剩下的几乎全是存储，反正你只要不在最后一场考试选错，其他的一切都是积累

算法和算法的度量

算法的基本概念

            
算法是对特定问题求解步骤的一种描述
五个特性：
1.有穷性
2.确定性
3.可行性
4.输入
5.输出

时间复杂度

            
n：问题规模
T(n)：时间开销
O(n)：时间复杂度
推导大O阶：
    1.用常数1取代运行时间中所有的加法常数
    2.在修改后的运行次数函数中只保留最高阶项
    3.将最高阶项系数变为1
必须牢记的：
⬯(1)<⬯(log₂n)<⬯(n)<⬯(nlog₂n)<⬯(n²)<⬯(n³)<⬯(2^n)<⬯(n!)<⬯(n^n)
常       对       线      线对      方      立    指      全排   牛牛

空间复杂度

            
空间复杂度只需要观察与n有关变量即可
递归调用空间复杂度就是递归的深度
有一些是每一层都少去一点是就是n²
也是大O表示法
空间复杂度其实算的就是除去你输入的，以及程序本身的内存以外
当你执行程序的时候，使用的变量会占有内存，这些内存就是空间复杂度的组成

总结

空间复杂度不会怎么考
时间复杂度考的多，这一类题目，纯粹就是数学题
这里给出两个用的巨多的公式（等比数列求和，等差数列求和）
 $等差： S_{n} = \frac{n}{2} \times (a + a_{n})$ 
 $等比数列： \begin{aligned} S_{n} = n a_{1}, (q = 1) \\ S_{n} = \frac{a_{1} \times (1 - q^{n})}{1 - q} = \frac{a_{1} - a_{n} q}{1 - q} = \frac{a_{n} q - a_{1}}{q - 1}, (q \neq 1) \end{aligned}$

例题一：n为正整数，程序的最坏情况下的时间复杂度
            
for (i = n - 1; i > 1; i--)
{
	for (j = 1; j < i; j++)
	{
		if (...)
			.....
	}
}
            
答案：O(n²)
解析：我之前由于学过一点数据结构，但是囫囵吞枣，我一看到这种双层循环，就意识到
循环次数，那不就是外层循环×内层循环嘛，于是我算

外层循环：从n-1到1，但是不包括1,也就是执行了n-2次循环   为什么？不是哥们
说实话我有时候也坎坷 似乎这是凭感觉得出这个次数的好像
那我们代数看看，假如n-1=10，从10 到 1 你掰手指头看看有几次？
别忘了，一定是包括10的，这没问题吧？😨
但是是不包括1的，因为到1的时候循环是不执行的，也就是最后一次循环是2
10 9 8 7 6 5 4 3 2
1  2 3 4 5 6 7 8 9 次
那不就是比初始值少一次嘛，那外层循环是n-1-1=n-2就说得通了

再看内层循环
当i=n-1的时候，j从1开始，直到j < i  也就是j < n-1
1到n-2 有几次？不知道？可去你的吧，n-2次啊😥
同理，当i=n-3的时候，执行 n-3次
i一直会到2，也就是内层最后一次是
j<2，j从1开始，也就是执行1次
好，我们捋一下
n-2
n-3
...
1
是不是等差数列？
所以我们算一下：
 $S_{n} = \frac{[1 + (n - 2)] \cdot (n - 2)}{2} = \frac{(n - 1) (n - 2)}{2} = \frac{n^{2} - 3 n + 2}{2}$ 

好了，内外层我们都算完了，以我的想法就是将内层次数X外层次数
当然是错的，为什么？为什么？我当时最大的问号就是为什么？我明明接触过的训练就是相乘
其实我忽略了一个细节，那就是内层循环的次数不直接是n有关，是和外层有关
这就导致，其实这两个for循环，其实就是一个整体，语句的次数其实就是整体执行的次数
不知道你能不能理解，反正我稍微有点感觉了
所以我们的整体循环次数就是内层循环的次数
也就是
 $\frac{n^{2} - 3 n + 2}{2}$ 
当然加上大O
 $O (\frac{n^{2} - 3 n + 2}{2}) = O (n^{2})$ 
别问我，怎么突然间只剩下n方了，回上面看大O阶的推导，你啊你😡😡😡😡

例题二：m++语句的执行次数
            
int m = 0, i, j;
for (i = 1; i <= n; i++)
{
	for (j = 1; j <= 2 * i; j++)
	{
		m++;
	}
}
            
答案：n(n+1)
分析：
外层：i从1到n，也就是n次
内层：
第一次：1到2，包括2，也就是2次
第二次：1到4，4次
第三次：6
8
10
12
...
第n次：2n
等差数列是吧？
 $S_{n} = \frac{(2 + 2 n) n}{2} = (1 + n) n$ 
结束了，又不是问时间复杂度，单纯问次数，如果是时间复杂度那就是O(n^2)

例题三：n为描述问题规模的非负整数，求时间复杂度
            
x = 2;
while (x < n / 2)
	x = 2 * x;
            
答案：n(n+1)
分析：这类问题怎么办？懵了？先别哭
有套路！
别高兴，骗你的
一般设循环次数为t，解出t=多少，不就ok了？
来，我们试一试
设次数为t
注意看循环停止的条件x < n/2
每次的迭代量为*2，而x是从2开始
也就是说2的某某次方为n/2的时候停止
是这意思吧？但是注意从2开也就是一开始就是2的1次方
所以
 $2^{t - 1} = \frac{n}{2}$ 
 $2^{t} = n$ 
 $\log_{2} 2^{t} = \log_{2} n$ 
 $t = \log_{2} n$ 
 $那么时间复杂度： O (\log_{2} n)$

难点：递归函数的时间复杂度
            
int fact(int n)
{
	if (n <= 1)
		return 1;
	return n * fact(n - 1);
}
            
答案：O(n)
分析：
递归函数的时间复杂度可以说和前面不是一个量级的
理解上就很难迈过去
最好理解的一种方法就是公式递推法：
	if (n <= 1)
        return 1;   O(1)
	return n * fact(n - 1); O(1)
我们使用T(n)来表示时间的程度
我们观察，当n<=1的时候只会执行return 1，也就是程序的时间复杂度就是O(1)
当n>1的时候
T(n) = O(1)+T(n-1)   这个O(1)是return n * fact(n - 1);的复杂度，因为乘法只会执行一次
T(n-1)是指，进入下一个函数的时间的程度
那么总的时间程度就是
不断的累加
T(n) = O(1) + T(n-1)
T(n-1) = O(1) + T(n-2)
...
总的时间复杂度就是
1×O(1) + T(n-1)第一次
2xO(1) + T (n-2)到第二个函数时
3xO(1) + T (n-3)到第三个函数时
...
有没有发现规律
yes
O(1)的系数，就是后面T(n-系数)
程序什么时候停止？就是当T(1)的时候
我们要让T(n-1)、T(n-2)、、、、变为T(1)
那不就是T(n-(n-1))      n-1就是系数
于是
(n-1)O(1) + T(n-(n-1))
(n-1)O(1) + T(1)
就是
O(n-1)
O(n)
于是答案就出来了
这个方法，对于简单的递归来说还行，但是复杂的递归需要很大的毅力，分析能力
但是总之，这个方法稍微掌握一下还是挺不错的

线性表

线性表基本概念

线性表是具有相同数据类型的n个数据元素的有限序列，n=0时为空表

 $线性表 {\begin{matrix} 顺序存储 — — 顺序表 \\ 链式存储 {\begin{matrix} 单链表 \\ 双链表 \\ 循环链表 \\ 静态链表 (数组实现) \end{matrix} \end{matrix}$ 
不要急好哥们，有时候就是大道至简，这个图我放这不是用来凑字数的
线性表是一种假想的东西，它是一个逻辑上的东西
而线性表的实现也就是分为两种顺序和链式，这是两个存储结构
别一眼带过，这是很重要的构思。
顺序存储对应的就是顺序表，所以顺序表是一种存储结构
链式存储对应的单链表，双链表，循环链表，静态链表都是一种存储结构

顺序表

用顺序存储的方式实现线性表
 $顺序表 {\begin{matrix} 静态分配（数组） \\ 动态分配（指针分配内存） \end{matrix}$ 
这里我讲解一下，动态分配，你是不是又没有思考？
一定要有敏锐的察觉，动态分配，分为两种，就是，每存入一个数就分配一个数的地址将前面和后面链接起来
这似乎是链表的思想
那顺序表的动态是指在程序执行的时候才知道数组要存多少个
这个时候我们动态分配一个数组
存入，当过了一段时间，哦豁，又来新活了，怎么办？
再分配一个新数组，注意是整体，是一个比原来大的数组，足以容纳新的数
然后怎么办？整体搬迁，类似扶贫，整个危房村的人，统一搬迁到政府新建的集体房子
顺序表的增删平均
1. 新增元素： O(N) （尾插是O(1),不考虑扩容的情况）
2. 查找元素： O(N)
3. 根据下标获取/修改元素：O(1)
4. 删除元素：O(N)
5. 清除所有元素：O(1)
存取方式
读写的方式，顺序表是支持随机存取的存储结构，也就是可以访问任意一个元素

单链表

讲单链表之前我们先来说两个东西头指针和头结点
头指针是指向链表第一个节点的指针
头结点是放在第一个元素之前的一个特殊结点，不存储任何数据
是的，当头结点存在，头指针就是指向头结点的
很好
接下来我们看看怎么建立链表，我们初步建立了一个思想，就是每当需要增加一个元素，采用分配的方法，指针指向的链接形成一个不连续内存的存储结构
单链表有两种实现方法
1.头插法
听着很熟悉吧，我们来看，如果这个链表带有头结点，那么每次新增的元素
放到头节点之后，也就是说，每次新增的元素的下一指向先被赋为头结点的下一指向
然后再将头结点的下一指向赋为这个元素
等等，是不是把你搞晕了哈哈哈🤣🤣🤣🫵🏿，你傻吗？头结点->1，现在加入2
你肯定让2->1,然后再让头结点->2啊
L->next=NULL;
p->next=L->next;
L->next=p;
那没有头结点的呢？
L=NULL;
p->next=L;
L=p;
咦，啊啊啊啊啊脑子要爆炸啦
这里讲一个很混乱的东西，头结点和没有头结点怎么都是L啊
头结点在哪呢？
其实头结点就是实例化的一个头指针，我这么说可能有点歧义
我们看下面两段代码
    
Lnode *head,*p;
head=(Lnode*)malloc(sizeof(Lnode));
head->next=NULL;
--------------------------------------------
Lnode *head,*p;
head=NULL;
    
第一段代码，我们看到head是头指针，头指针被分配了指向
    这不是给head分配空间，是让head指向了一个地方，分配空间Lnode *head这句已经自动分配了
    好，头指针现在已经指向了一个地方，head->next是说头指针指向的这个地方的指针域指向下一个的地方赋为空
    |头指针|->|头结点|->|NULL|//通过这个你应该明白了，头结点是分配的地址
第二段代码，我们看到head头指针直接被定义以后赋为NULL说明没有任何指向，也就是没有头结点。
-------------------------
然后我们讲讲头插法
    
        带头结点
p=(Lnode*)malloc(sizeof(Lnode));
p->data=i;
p->next=head->next;
head->next=p;
-----------------------------------------------
        不带头结点
p=(Lnode*)malloc(sizeof(Lnode));
p->data=i;
p->next=head;
head=p;
    
我们看第一段代码，p是要新增的一个节点，p=(Lnode*)malloc(sizeof(Lnode));分配空间
p->data=i;给数据域赋值
p->next=head->next;这是带头结点的，所以head指向的地方是头结点而head->next是头结点指向的下一节点
这句话就是将头结点指向的下一节点赋为新节点的下一节点
head->next=p;将头指针指向的头结点的指针域指向p
总体一套连招下来，打的你是晕头转向啊
    没事我会魔法，看🪄
    |head|->|头结点|->|NULL|
    |p|->|NULL|
    |head|->|头结点|->|p|->|NULL|
    这样看不够清晰我们现在要是再增加一个节点M
    |head|->|头结点|->|p|->|NULL|
    |M|->|P|
    |head|->|头结点|->|M|->|P|->|NULL|
我们看第二段代码
    p->next=head;直接将p的下一个赋值为head指向的NULL
    head=p;再将head头指针指向新增的p
    慢慢体会吧
2.尾插法
    尾插法就是每此新增的元素是增加到结尾
    所以我们要增加一个尾指针，辅助我们在末尾增加新元素
    头指针是不动的，尾指针每次结束是指向最后一个元素，再将最后一个元素的指针域赋为NULL
    
    LinkList TailInster(LinkList &L,int n){
	int x=1;
	L= (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	while(x!=n){
   		s=(LNode*) malloc(sizeof(LNode));
   		s->data=x;
  	 	r->next=s;
   		r=s;
   		x++;
	}
	r->next=NULL;
	return L;
}
    
因为有了尾指针，所以头插法和尾插法创建单链表的时间复杂度一样都是O(n)

单链表的时间复杂度总结

头插法-尾插法:都是O(n)
按值按序查:O(n)
增:O(n)，给定节点:O(1)
删:O(n)
求表长:O(n)
时间主要花在查找上

双链表

双链表有前驱和后继，两个指针域，单链表只有一个指针域，只能指向后继节点
双链表的增删时间复杂度都是O(1)

循环单链表

比起单链表来讲，循环单链表最后一个元素节点的指针域，也就是指向下一个的指针，指向的不是NULL
而是改为指向头结点，如果没有头结点就是头一个元素也就是头指针
这里我要提个醒，链表不是数组，循环单链表的最后一个元素指向的是链表第一个元素
是完整的，不存在任何一个节点的指针域是NULL，所以判断循环单链表的条件不是判空
是判断头结点是不是等于头指针，这样一样来就是说没有元素存在，因为
|head|->|头结点|->|head|
我们也知道，单链表是存在头指针和尾指针
循环链表的话，可以只存在其中一个
如果只存在头指针，那么尾插法需要O(n)
如果只存在尾指针,那么尾插，头插都是O(1)
头指针因为要遍历到最后一个
而尾指针尾插O(1)不需要解释
头插为什么也是？因为头指针可以通过尾指针+1得到
因为是循环链表嘛

循环双链表

循环双链表就不多说了，一样的思想，头结点两个指针域的指前指针是要指向链表末尾的节点
判断的话，头结点是两个指针域都等于头指针

静态链表

静态链表采用数组的方式
不同于其他，这是个结构体数组，就是说数组的每一个元素都是结构体
结构体包含一个数据和一个整形表示位置
这个整形的数字表示的就是这个元素的下一个元素指向的位置是数组中的第几个元素
给代码自己看

 typedef struct
    {
        ElemType data;
        int next;
    }SLinkList[MaxSize];

栈、队列和数组

栈

栈是一种线性表，只不过它的操作受到限制
只能是一端进行增加和删除
既然是线性表那么就有两种存储方式，也就是顺序栈和链栈
 $卡特兰数： n 个不同元素入栈，出栈元素不同排列的个数为 \frac{1}{n + 1} C_{2 n}^{n}$

顺序栈

顺序栈的实现

typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

栈空条件top=-1
栈的实现其实就是一个数组以及记录栈顶(数组下标)的东西
            你不能纯粹把数组形象化为一个栈，因为栈顶不是数组的开头而是指针向后移动
            也就是说，下标越大的就是栈顶
            |1|-|2|-|3|-|4|-|5|-|6|-|7|-|空|
            7是栈顶，top指向的就是这个，top的值是6，因为数组是从0开始计数

共享栈

就是一个数组被两个栈共同占用，挺那啥的是吧，但是节省空间啊
只会发生上溢
我们来考虑一下，共享栈，也就是农村包围城市，两头包围
|1|-|2|-|3|-|空|-|空|-|空|-|空|-|空|-|2|-|1|
看到没有前一个栈是存了三个，栈顶元素是3，top是2是递加的
后面一个栈是存了二个，栈顶元素是2，top是n-2=8是递减的
溢满的情况是怎么样的？
 |1|-|2|-|3|-|4|-|5|-|5|-|4|-|3|-|2|-|1|
A->                                   <-B
现在已经存满了
如果A或者B此时再执行存入一个数，那么势必是造成A或B的一个数被覆盖
造成数据混乱，叫上溢
很多人不理解，为什么叫上溢不叫下溢？
这里的上溢是指
栈的增长方向通常被视为“向上”增长。因此，当栈满时，进一步的增长操作导致数据“溢出”预设的界限，这就是“上溢”。
如果栈已经没有元素了，即栈顶指针已经指向栈底或更下的位置，继续执行弹出操作就会导致下溢错误。

链栈

链栈的实现

typedef struct LinkNode{
    ElemType data;
    int top;
}*LiStack;

栈空条件top=MaxSize

队列

队列简称队，与栈一样是一种受到限制的线性表，只不过只能在一端插入，一端删除。
队列的顺序存储，很简单与线性表顺序存储无异，我们给定两个指针
            
 #define MaxSize 50;
 typedef struct{
     ElemType data[MaxSize];
     int front,rear;
 }SqQueue;
            
front 是指向队头，rear是指向队尾。
一开始front和rear都是指向第一个元素，也就是空队
当不断增加元素以后，rear不断后移。
当我们有元素出队列的时候，front要后移
这个时候问题就是出来了，就是说数组的前几个是空的
而rear回不到前面，也就是说，一个冰箱上下都装满了物品
当上面的物品被清空的时候，你还要放物品，你只知道去下面放
下面是满的，你就说你要重新买个冰箱，因为现有的冰箱不能放了
这不是蠢吗，不是，有钱我也这么干，买两杯咖啡，一个倒一个扔，反正不爱喝

顺序循环队列

所以我们就有循环队列
初始：Q.front = Q.rear =0;
队首指针进1:Q.front = (Q.front + 1) % MaxSize;
队尾指针进1:Q.rear = (Q.rear + 1) % MaxSize;
队列长度:(Q.rear - Q.front + MaxSize) % MaxSize;
队满条件:(Q.rear +1) % MaxSize ==Q.front;//这里是约定空出一个不存储，也就是队尾+1就是队头的时候就是满,注意队尾指向的不是最后一个元素而是最后一个元素的下一个空位置
队空条件:Q.front == Q.rear;
当然了，你也可以这样想，我们额外定义一个Size来记录列表存储个数，当Size=0并且头尾指针相等就是空
如果Size=MixSize并且头尾指针相等就是队满
同样，你也可以这样，出队的时候才会导致队空
入队才会导致队满，定义一个参数tag，=0是删除操作，此时头尾相等是队空，=1是增加，头尾相等是队满
MaxSize是指存储的个数，不是下标，其次A[21]，MaxSize是21，A[0...n]，MaxSize是n+1,因为有n+1个元素
双端队列:允许两端都可以进行入队和出队操作的队列
输入受限的双端队列:允许一端进行输入和删除，另一端只能删除
输出受限的双端队列:允许一端进行输入和删除，另一端只能输入
双端列表是数组形式的，也就是说先全部进入，再依次输出。
即便是双端可进可出，那也是队列，是队列你就给我先进先出
也就是全部进入以后再谈输出

队列的链式存储

链队列,尾指针是指向最后一个元素，这一点和顺序存储不同
            
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front ,*rear;
}*LinkQueue;
            
当Q.front==NULL并且Q.rear==NULL表示队列为空;//认真记住链表和数组的不同的判断方法，不然你会栽跟头的

栈和队列的应用

后缀表达式的求值与转换(栈)
    四则运算表达式转化为后缀表达式的规则：
    
        1.数字直接写
        2.运算符号如果级别高于栈顶的，直接入栈写上，如果等于或者低于栈顶的让栈顶先出，自己再进去
        3.左括号不管入，遇到右括号，将左括号上面的所有出栈
        //如果前面加入了 （*  ，此时来了个+，也是需要让*先出来，而不是以为有（就不动了， （ 只是用来碰到 ） 打包的
    
    我们来举个例子：9+（3-1）×3+10
    数字直接写：9
    然后就是+号，符号入栈
	
    然后就是（入
    	
    9+（3-1）×3+10，然后就是3，直接写
    93
    然后就是-入
     	
    9+（3-1）×3+10，然后就是1，数字直接写
     931
    然后就是）右括号，你瞧，直接打包出来，其实也没有就一个-号，收获不大啊，竹篮打水一场空
     931-
       	
    然后就是x，和此时的栈顶+比较，谁牛逼，显然x牛点，所以入栈
           	
    9+（3-1）×3+10，然后就是3，数字直接写
    931-3
    然后就是+，比较栈顶的x，哦豁，没有它厉害，乖乖让x出来
    就是
    931-3x
    此时栈：
          	
    还没有完，还要继续比较现在的栈顶，是+和即将入的+是相等的，让栈顶出来
    931-3x+
           	
    这个时候，我们的+再入栈
      931-3x+
           	
    9+（3-1）×3+10，然后就是10，数字直接写
    931-3x+10
    然后没了，栈里面的给我滚出来吧
    931-3x+10+
    
    以上就是中转后缀表达式，下面讲讲如何模拟计算机一样，直接计算后缀表达式
    
    1.当是数字的时候直接入栈

    2.当是运算符号的时候

    3.就将栈的最上面两个数拿出进行运算 后 再将结果进栈 记住（栈顶元素永远在运算符号的右边）
    
    看9 3 1 - 3 * + 10 2 / +
    9 3 1依次入栈，没有异议

    
    接下来是-，取出栈顶的两个元素，分别是1 3，1是栈顶，放-号的右边
    就是3-1=2
    将2入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是 3 入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是*，取出来运算
    2*3=6，即便是*这种不在意次序的，你也务必养成习惯将栈顶放右边
    6入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是+，取出运算
    9+6=15，15入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是10，数字入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是
    2入栈
    
    9 3 1 - 3 * + 10 2 / +接下来是/，取出两个运算
    10/2=5入栈
    
9 3 1 - 3 * + 10 2 / +接下来是+，取出来运算
15 + 5 = 20
好了，这就是最后结果了，不信你自己算嘛，给你9+（3-1）x 3+10/2
栈在递归中的应用
对同一个问题递归比非递归好看，但是非递归的效率比递归高
队列在层次遍历中应用
信息的逐层处理
队列在计算机系统中的应用
第一方面解决主机与外部设备之间速度不匹配的问题
第二方面解决由多个用户引起的资源竞争问题
数组和特殊矩阵
两种映射方法：行优先/列优先，行优先：先行后列，存储在一维数组中
压缩存储多个相同的值只分配一个存储空间，节省空间
特殊矩阵线性代数中的对称，上/下三角，对角阵，稀疏矩阵

串

串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串
长度为0的才是空串，空格是空格串不是空串
串中字符位置是从1开始数
串也算一种特殊的线性表

串的顺序存储

没什么好说的，就是用数组来存

串的链式存储

也没什么好说的，块链存储的意思就是，每一个节点呐不单单是存一个字符，而是一串字符，如果存不满，用#填充

串的模式匹配

子串的定位操作就是串的模式匹配
Next数组求解
            
首先我们需要知道KMP是干嘛的，通俗易懂的来讲是查找相同字符串的一种捷径
我们人的本能的趋简避繁，例如aababcbdaabacbbbd这样的字符串，我们需要在其中找到子串aabacb我们怎么操作？
为什么会将子串第一个字符依次对比字符串的每一个字符来判断：
=----------1---------=
aababcbdaabacbbbd
aabacb
=----------2---------=
aababcbdaabacbbbd
 aabacb
=----------3---------=
aababcbdaabacbbbd
  aabacb
=----------4---------=
aababcbdaabacbbbd
   abacb
=----------5---------=
aababcbdaabacbbbd
    abacb
=----------6---------=
aababcbdaabacbbbd
     abacb
=----------7---------=
aababcbdaabacbbbd
      abacb
=----------8---------=
aababcbdaabacbbbd
       abacb
=----------9---------=
aababcbdaabacbbbd
        abacb
=----------10---------=
aababcbdaabacbbbd
         abacb
=----------end完结撒花---------=
怎么样是不是很麻烦吧？//麻烦个嘚，我就喜欢
不是，既然计算机大拿说了麻烦咱就认行吗？
于是开头字母分别为KMP的三个人设计了一个算法叫KMP算法（具体思路自己百度，以下只解释最重要也是最难理解的Next数组该怎么求）
Next数组说白了就是求子串中每一个最长相等前后缀（听不懂没关系，往下看）
//别傻不愣登的去求主串的，那么长求到地老天荒啊，别问我怎么知道，因为我傻
这里声明一个规则：
前缀：不包含未元素的串
后缀：不包含首元素的串
我们来举个例子这是子串|a|a|b|a|a|f|
（1）|a|
前缀以及后缀都为0  导致最长相等前后缀为0
（2）|a|a|
前缀为|a|
后缀为|a|相等
最长相等前后缀为1
（3）|a|a|b|
前缀为|a|a|
后缀为|a|b|不相等
在这有两个元素的前后缀的基础上再下一次比较
前缀|a|
后缀|b|依然不相等//注意这里的|a|和|b|不是后缀中的|a|b|拆分的，是前缀|a|a|的第一个|a|以及后缀|a|b|最后的那个|b|
最长相等前后缀为0
（4）|a|a|b|a|
前缀为|a|a|b|
后缀为|a|b|a|当然不相等
在这有三个元素的两个前后缀的基础上再下一次比较
前缀|a|a|
后缀|b|a|依然不相等
同理再比较
前缀|a|
后缀|a|相等
所以最长相等前后缀为1
（5）|a|a|b|a|a|
前缀|a|a|b|a|
后缀|a|b|a|a|不等
再前缀|a|a|b|
后缀|b|a|a|不等
再|a|a|
后缀|a|a|相等长度为2
最长相等前后缀为2
（6）|a|a|b|a|a|f|
前缀|a|a|b|a|a|
后缀|a|b|a|a|f|不等
前缀|a|a|b|a|
后缀|b|a|a|f|不等
前缀|a|a|b|
后缀|a|a|f|不等
前缀|a|a|
后缀|a|f|不等
前缀|a|
后缀|f|不等
所以最长相等前后缀为0
所以前缀表的值就是，这6个算出来的数值
即|0|1|0|1|2|0|
重点这还不是Next数组
我们需要将-1发放到最前面，然后去掉最后一个数，整体右移
|-1|0|1|0|1|2|
以上为理论部分（聪明的人会看到这里的）

以下是代码实现部分（C++）
#include < stdio.h >
#include < iostream >//c++的头文件
#include< string >
using namespace std;//c++的命名空间，如果没有这句话，很多地方会这样写std::cout等等
class solution {//定义类，c++语法
public://公共方法（好像java才说方法）以及属性
    void getnext(int* next, const string& s) {//传入next数组以及字串
        int j = 0;//j初始化为0
        next[0] = 0;//首元素设置为0
        for (int i = 1; i < s.size(); i++) {//我们假设i指向后缀的末尾，j指向前缀的末尾
            while (j > 0 && s[i] != s[j]) {//while是用来处理前后缀不相同的情况
                j = next[j - 1];//这句代码的意思是回退，回退到前一个数组元素的值为数组下标处
            }
            if (s[i] == s[j]) {//if用来处理前后缀相同的情况
                j++;//如果想相同，则会将j++，让j来表示最长相等前后缀的情况
            }
            next[i] = j;//让此处的最长相等前后缀为j的值
        }
    }
};
int main()
{
    int next[8];
    string s = "abcabcab";
    solution*a = new solution();
    a->getnext(next,s);
    for(int i=0;i<8;i++)
    printf("%d",next[i]);
}
        //放心，代码你十有八九看不懂，不过没关系，毕竟你要是自己研究出来了
        //你就是KMP的发明者了，今天看几遍，过几天再来，慢慢的就理解了
            
我就知道你肯定不会认真的看，所以我必须拿出点手段来
Next数组求解
前缀：不包含未元素的串
后缀：不包含首元素的串
我们来举个例子这是子串|a|a|b|a|a|f|
（1）|a|
前缀以及后缀都为0  导致最长相等前后缀为0
（2）|a|a|
前缀为|a|
后缀为|a|相等
最长相等前后缀为1
（3）|a|a|b|
前缀为|a|a|
后缀为|a|b|不相等
在这有两个元素的前后缀的基础上再下一次比较
前缀|a|
后缀|b|依然不相等//注意这里的|a|和|b|不是后缀中的|a|b|拆分的，是前缀|a|a|的第一个|a|以及后缀|a|b|最后的那个|b|
最长相等前后缀为0
（4）|a|a|b|a|
前缀为|a|a|b|
后缀为|a|b|a|当然不相等
在这有三个元素的两个前后缀的基础上再下一次比较
前缀|a|a|
后缀|b|a|依然不相等
同理再比较
前缀|a|
后缀|a|相等
所以最长相等前后缀为1
（5）|a|a|b|a|a|
前缀|a|a|b|a|
后缀|a|b|a|a|不等
再前缀|a|a|b|
后缀|b|a|a|不等
再|a|a|
后缀|a|a|相等长度为2
最长相等前后缀为2
（6）|a|a|b|a|a|f|
前缀|a|a|b|a|a|
后缀|a|b|a|a|f|不等
前缀|a|a|b|a|
后缀|b|a|a|f|不等
前缀|a|a|b|
后缀|a|a|f|不等
前缀|a|a|
后缀|a|f|不等
前缀|a|
后缀|f|不等
所以最长相等前后缀为0
所以前缀表的值就是，这6个算出来的数值
即|0|1|0|1|2|0|
重点这还不是Next数组
我们需要将-1发放到最前面，然后去掉最后一个数，整体右移
|-1|0|1|0|1|2|
上面这个是下标从0开始的Next数组，如果是从1开始的就是整体+1
|0|1|2|1|2|3|
什么是从0从1开始？我真的要敲爆你的脑子🧠
abcde中c是第三个就是从1开始
abcde中c是第二个就是从0开始
好啦，Next数组求法已经完结，但是有些人真的太聪明了，搞出了一个NextVal数组(我真他妈的🤬)
也简单看下面
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
因为下标从1开始，所以我们写的Next就是整体+1了
我们的NextVal数组第一个统一是0
|0|_|_|_|_|_|
然后我们看
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
这个Next是1，对应的下标1所对应的字符是第一个a和此时的字符是一样的，其次第一个字符a对应的Next是0
一样的字符的话就引用前面的Next值就是0
|0|0|_|_|_|_|
然后我们看
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
2对应的是a，与b不同，我们直接把b的下标拿下来
|0|0|2|_|_|_|
然后我们看
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
1对应的是a，与a相同，使用第一个next
|0|0|2|0|_|_|
然后我们看
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
2对应的是a，与a相同，使用第一个next
|0|0|2|0|0|_|
然后我们看
下标: |1|2|3|4|5|6|
字符: |a|a|b|a|a|f|
Next: |0|1|2|1|2|3|
3对应的是b，与f不同，则使用自己的
|0|0|2|0|0|3|
给你一个例题：串“ababaaababaa”的next数组和nextval数组分别是什么？
答案：
-1,0,0,1,2,3,1,1,2,3,4,5
0,1,0,1,0,4,2,1,0,1,0,4
设有字符串S='aabaabaabaac',P='aabaac'
1.求出P的next数组。
2.若S作主串，P作模式串，给出KMP算法的匹配过程。
            
            第一个答案好说|0|1|2|1|2|3|
            第二个
            第一趟匹配
            S；|a|a|b|a|a|b|a|a|b|a|a|c|
            P：|a|a|b|a|a|c|
            在S[6]与P[6]的时候失效
            注意到失效的P串的第六个字符的next数值是3，也就是下次比较的时候，直接跳到P串的第3个字符开始比较
            P的第三个对应S的第六个
            也就是第二趟
            S；|a|a|b|a|a|b|a|a|b|a|a|c|
            P：      |a|a|b|a|a|c|
            失效的时候就是S[9]，P[6]，P的第六个对应的next是3
            也就是下一次从S[9],P[3]开始
            也就是第三趟
            S；|a|a|b|a|a|b|a|a|b|a|a|c|
            P：            |a|a|b|a|a|c|
            匹配成功。
                
一个主串长度是n，子串长度是m,简单的匹配算法时间复杂度是O(nm),KMP是O(n+m)

树和二叉树

树的基本概念

            
    
祖先:比它高的唯一路径上的都是
子孙：比它低的唯一路径上的都是
双亲：它的前驱节点
孩子：它的后继节点
兄弟：有共同的双亲
堂兄弟：双亲不同，但是双亲有共同的双亲
------------------------------
结点的度
树的度
分支结点
叶子结点
树的高度：从下往上，就是最大层数
树的深度：从上往下，也是最大层数
路径：从A到B经过了《哪些》结点
路径长度：从A到B经过了《几》条边
树的路径长度：根结点到各个结点的路径长度总和
森林：互不相交的树
m叉数：所有结点的度小于等于m
------------------------------
树的性质
结点数=所有结点度数+1
 $度为 m 的树中第 i 层至多有 m^{i - 1} 个结点$ 
 $高度为 h 的 m 叉树至多有 \frac{m^{h} - 1}{m - 1} 个结点$ 
 $具有 n 个结点的 m 叉树的最小高度 l o g_{m} (n (m - 1) + 1)$ 
 $高度为 h ，度为 m 的树至少有 h + m - 1 个结点$ 
            
我来解释一下，
第一个你随便画一个二叉树满的，是不是2的比层数低一次方的数（等比数列第n项公式）
第二个它说了至多，也就是每个结点的度是m，每次都是上一次的m倍，也就是等比求和公式
第三个因为至少，所以我们把每一个结点满填m，因为是m叉树嘛，然后我们设高度为h
 $n = \frac{m^{h} - 1}{m - 1}$ 
 $m^{h} = n (m - 1) + 1$ 
 $h = l o g_{m} (n (m - 1) + 1)$ 
            
这些公式包你恶心的哥哥姐姐，并且你就算记住了也做不了题
you know what
这些公式其实是自己做题做到很多以后，自己靠着不主动的记忆，记忆主动去回忆一丝丝的的东西
然后发现记忆好像就只有零星一点，就算了，然后自己分析题目，自己推，长此以往，竟然觉得所有题好像就这么回事
公式反正不顶用，我记个屁，还不如现场推，反正题目也不会套公式

二叉树

二叉树，刚学就忘了？之前说的m叉树，当m=2的时候不就是二叉树
二叉树是指所有结点的度小于等于2
二叉树的左右子树是有序的
几个特殊的二叉树
满二叉树除了叶子结点每一个结点度都是2
完全二叉树与满二叉树是编号必须一一对应
二叉排序树左子树上所有结点的关键字都小于其根，右子树的所有结点关键字都大于其根
平衡二叉树左子树和右子树的深度之差不超过一
想让我画图给你看是吧，不给🤣🤣🤣🤣
            ------------------------------------------
二叉树的性质
1.非空二叉树的叶节点数量是度为2的结点数+1
            因为你看结点总数=度为1+度为2+度为0，换另一种思路总数=度为1×1+度为2×2+1(根),所以等式结合就是度为0的数=度为2的数+1
 $2. 非空二叉树第 k 层上至多有 2^{k - 1} 个结点$ 
 $3. 高度为 h 的二叉树至多有 2^{h} - 1 个结点$ 
 $4. 对于完全二叉树：结点 i 的双亲编号是 [\frac{i}{2}] （向下取整），结点 i 所在层次是 [l o g_{2} i + 1]$ 
 $5. 具有 n 个结点的完全二叉树的高度为 [l o g_{2} (n + 1)] 或 [l o g_{2} n] + 1$ 
不知道你怎么想，反正我快红温了😁😀🙂🤨😐😑😶😥😫🤑😩😰😱🥵😡🤬🐒
还是那句话，我不想背，数学已经让我头疼了
什么？我不想背的，有的是人背，我做不到的总是有人做得到？
我去不了的学校他们就替我去了？
我可去你的吧

二叉树的存储结构

1.顺序存储
只适合存储完全二叉树和满二叉树
用人话就是数组，下标就是数的关键字，什么叫关键字？
我日，看上面我摆出的那个树的图像，每一个圆圈就是结点，圆圈里面的A，B这些就是关键字
你问，ABC....怎么用下标对应？
你啊你，别那么死板啊，把ABC...换成123...不就行了。🫢
2.链式存储
左右指针域以及数据域
我知道，你肯定会问双亲怎么找？
从头开始，如果频繁的找的话，你就多设置一个双亲指针域嘛，有什么大不了的
在含有n个结点的二叉链表中，含有n+1个空链域
是不是很无厘头，我老是这样摆出一个公式，然后解释，但是唯独没有解释为什么要学习这个公式
考试要考？只能说虚伪
没办法，想要站在巨人的肩膀上，只能这样
解释一下，n个结点空链域，也就是说,想想看，一个结点如果是叶子结点是不是它就有两个空链域
如果一个结点只有左右其中一个结点是不是就有一个空链域
然后，空链域是不是=总链域-使用的链域
总链域就是结点×2
使用的链域是不是就是n,是你个大头鬼，根结点是被谁使用的链域形成的，你说说看？
所以使用的链域就是n-1
所以空链域=2n-(n-1)=n+1

二叉树的遍历和线索二叉树

树学了这么久，你就没有想过，代码是如何实现，在每一个结点之间横跳的吗？
             
    
如同以上这棵树，我们如果以先序遍历来遍历这棵树该怎么办？
以我们的理论来说，先序就是根左右，也就是ABEFGDHIC
没问题吧，这都是很简单的(不明白的点开右上角的目录《二叉树的遍历》)
            //哈哈哈，我发现就是这一节啊，行吧，我把它(动物它☝🏻)放到这一节的最后部分了
好，二叉树的实现是利用链表，也就是它有两个指针域
指向左孩子和右孩子，我们从A开始
A可以找到B和C，我们怎样实现先把B以及B的子孙都访问完再访问C？
没错，递归
看下面代码
            
void preOrder(BiTree T)
{
    if(T!=NULL)
        {
            visit(T);
            PreOrder(T->lchild);
            PreOrder(T->rchild);
        }
}
            
中序和后序怎么办？就是Visit放的位置不一样罢了
中
void preOrder(BiTree T)
{
    if(T!=NULL)
        {
            PreOrder(T->lchild);
            visit(T);
            PreOrder(T->rchild);
        }
}
            
后
void preOrder(BiTree T)
{
    if(T!=NULL)
        {
            PreOrder(T->lchild);
            PreOrder(T->rchild);
            visit(T);
        }
}
            
三种算法的时间、空间复杂度都是O(n)
层序遍历
要实现层序遍历，我们要借助一个队列
具体实现如图


    
这是我们的树，我们要层序遍历就是ABCEDFGHI
我们先让根结点进栈A

如果此时的A结点有左孩子就入队，再如果有右孩子再把右孩子入队也就是BC依次入

这个时候A的左右都入了，于是把A出栈

轮到B了，看B的左右子树依次入栈也就是ED

好，B的左右孩子都入了，B可以放心滚蛋了

轮到C了，因为C是单身，无牵无挂，直接拜拜

再到E，E是有FG两个左右孩子的，所以入栈

E滚蛋，如果就是D，D也有左右孩子，也就E滚，D左右孩子入，D滚

接下来4个都是叶子，没有孩子，所以依次出栈

完结，撒花❀，等等，还没有说代码，算了，反正你也不看，哦对了，那不是个栈，笑死我了哈哈哈哈哈
其实是队列啦☝🏻☝🏿🫰🏿

    void  LevelOrder(BiTree T) {
	InitQueue(Q);
	BiTree p;
	EnQueue(Q, T);//将根结点入队
	while (!IsEmpty(Q)) {
		DeQueue(Q, p);//出队
		visit(p);//访问树
		if(p->lchild!=NULL)
			EnQueue(Q, T);//将左结点入队
		if(p->rchild!=NULL)
			EnQueue(Q, T);//将右结点入队
	}

}

线索二叉树
            好，everybody 全体目光向我看齐


这是一个二叉树，我们把它转化一下

看我们的图，是不是最后的叶子结点的左右子树也就是指针域都是空的
这样是不是很浪费？传统来讲
我们树是没有前驱结点的，也就是说如果你正在某个结点
你想要知道这个结点的前面一个结点，你做不到
怎么办？你只能重新遍历
记录当前结点，并设置一个pre，p两个指针
当p移动，pre总是落后一个，当遍历P=你记录的结点
pre就是你想找的
好啦，说了这么多废话，线索二叉树是什么
就是说把空链域指向它的前驱后继，保证利益最大化
也就是说左孩子空的话就指向它的前面一个结点
右孩子空的话就指向它的后一个结点
都涉及前后了，那肯定是前中后序肯定是不一样的
我们就拿这幅图的前序来讲

先序就是根左右嘛，拿这副图来讲，它的前一个就是它的双亲
它的后一个就是它的双亲的右结点，也就是它的兄弟结点
然后我们继续

有人就说了，怎么最后一个叶子结点不画了，是不是懒啊
不是，是因为它的前驱是左结点，而左节点是空，所以它的左空链域是指向空
右空链域原本指向后继，但是后继没了，所以也是指向空
所以，不是你写了不过50个字用了这么多所以？
🫰🏿🫰🏿🫰🏿🫰🏿

 二叉树的前中后序遍历
这类题目一般给前中/后中，来确定后/前序遍历，因为只有前中/后中才能确定唯一的二叉树，而前后序不能确定
    
    （1）给定前序ABDGHCEFI与中序GDHBAECIF，写出后序遍历。
    什么？我前中后序遍历都不知道是什么？
    接下来我们来学习，前中后，简单来说，前中后描述的是根所在的位置
    前（根左右）中（左根右）后（左右根）
   
    
    上图中，前序遍历，也就是根左右，我们一步步来看
    首先根：A
    其次左：B //很好，接下来并不是右C，而是E，因为B也是一棵子树二叉树的根
    也就是根B的左：E //接下开E又是一棵子树的根
    也就是根E的左：F //因为F不再是任何树的根，这时候就可以到右
    也就是根E的右：G //完成以后，我们回退到E？不，因为E的左右都写完了，于是我们再回退B，根B写了左但还没写右
    也就是根B的右：D //此时D又是根，于是再写D的左
    也就是根D的左：H //此时H不是根了，就可以写右
    也就是根D的右：I //这时候，根D左右写完，回退B，B的左右也写完了，回退A，A只写完了左，右还没有写，于是
    也就是根A的右：C //到此为止，我们的前序遍历就算写完了
    前序：ABEFGDHIC

本来我想图省事，直接说，中后序同理的😏😏😏
   
    
    上图中，中序（左根右）一步步来
    左：F //这个左是整个树的左
    根：E //这应该能理解吧？不能理解？废了，重开吧
    右：G //此时，一棵子树以及遍历完了，按理说是返回到B，但是B是根，把B看成根，也就是E子树为左，D子树为右
    也就是根：B 现在你肯定想说，接下来不就是D了吗？no、no、no，时刻谨记D是根，我们优先左再根再右，也就是根D树的左H
    左：H
    根：D
    右：I 现在D树完成，回退到B，B树的左右也完成了，回退到A，A左完成，根据左根右，也就是左完成，现在是根，于是
    根：A
    右：C 这还用我说？🤏🤏🤏
        中序：FEGBHDIAC
    
   
    
    上图中，后序（左右根），一步步来说
    左：F 
    右：G
    根：E //现在B的左树已经写完，根据左右根规则，我们看B的右边的树，也就是以D为根的树，但是我们肯定不是先写D，要先左
    左：H
    右：I
    根：D //好了，左右子树都写完，就写根了
    根：B 现在总体看，A树的左子树写完了，再看A的右树
    右：C
    根：A 完结撒花😃😃😃😃😃
    后序：FGEHIDBCA
    
我了个天，扫盲结束。

已知前/后和中序遍历构造二叉树

 （1）给定前序ABDGHCEFI与中序GDHBAECIF，写出后序遍历。
    你肯定有点思路，但我知道并不多，我们来用一种流氓的思路来解决他
    画以下的类似二维坐标系的图

怎么样，画出上面的图，我们肯定知道A是根节点，别问为什么，因为前序遍历第一个肯定是总树的根节点啊😡😡😡😡
接下来我们画线
    
画这些点和线真的累死我啦🤨😥😭
看起来是不是很简单，但是如果你现在直接把我题目抄在草稿纸上，自己去画，绝对会有地方卡住
这就是为什么你有时候学习，以为学的很好了，看起来很简单，但是自己一动手就废了
注意看我画的图，你怎么知道A必须连接B？为什么不左连接D，右连B？等等问题
在这里我们遵循几个原则
1.这是二叉树，最多只有两个子树，也就是最多只能有两个孩子
2.左孩子的x不会大于根的x
3.根一定在孩子上方
4.与最近的结合
行了，以上是我瞎总结的，这些就是经验，教科书又臭又长，但是学懂了，根本不需要记住那么多东西
就是自然而然的。
然后就是喜闻乐见的，答题环节
后序遍历：GHDBEIFCA //你可能还是困惑为什么E在C前面，I在F前面，真的想一巴掌拍晕你，左右根，A的右树开始是C，但是C是A右子树的根啊，所以开始E，然后C的右，右F也是一棵子树，F也是根所以先I再F啊，你得牢记，计算机是靠递归，而不是忍者神龟
  （2）给定后序ACDBGIHFE与中序ABCDEFGHI求前序遍历
在解答这道题前别着急写，别以为学了点东西就以为天下无敌了，乱拳打不死老师傅
仔细想想中序遍历不管他，我们前一题给的是前序遍历，在y轴上当然A最在最上面，因为A是全部的根
但是后序呢？最后一个字母E才是根，如果还按之前的y轴排，E在最下面，那成啥了？
    
    按照同样的思路连线，你可以自己尝试一下，再来看我画的
    
我知道你如果自己试了的话，有可能在C为什么不连A，而是B连A，这个问题在于，B作为一个根，你将其从上到下看成一个金箍棒
如果C连的左子树为A，那么A大概率在B这根金箍棒的右边而不是左边
下面是题目的答案
 前序遍历：EBADCFHGI
 一开始学习的时候我问过一个问题：
    第三中，给定前后序，怎么求中序啊？（不知道你会不会有这种想法）
还记得我们一开始说的吗？只有前中以及后中才能确定一棵树，而前后并不能确定唯一的一棵树

树、森林

树的存储方式
1.双亲表示法


  
        
             
            data
            parent
        
        
             0
            A
            -1
        
        
             1
            B
            0
        
        
             2
            C
            0
        
        
             3
            D
            0
        
        
             4
            E
            1
        
        
             5
            F
            1
        
        
             6
            G
            2
        
        
             7
            H
            3
        
        
             8
            I
            3
        
        
             9
            J
            3
        
        
             10
            K
            4
        
              
                   11
            L
            4
        
              
                   12
            M
            7
        
    
不难看出，就是用数组存储它的双亲的下标
2.孩子表示法
孩子表示法就是每个结点与其孩子是链表关系，链表存储的数据域是孩子结点在数组中的下标
//树的孩子表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType;   //树结点的数据类型，目前暂定整形
typedef struct CTNode{      //孩子结点
	int child;
	struct CTNode * next;
}*ChildPtr;
typedef struct{              //表头结构
	TElemType data;
	ChildPtr firstchild;
}CTBox;
typedef struct{              //树结构
	CTBox nodes[MAX_TREE_SIZE];    //结点数组
	int  r,n;                     //根节点的位置和结点数
}
3.孩子兄弟表示法
二叉树表示法，就是两个左右指针域，记住四个字《左孩右兄》

	data	parent
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1
5	F	1
6	G	2
7	H	3
8	I	3
9	J	3
10	K	4
11	L	4
12	M	7

树、森林与二叉树的转换

树和二叉树的转换就是《左孩右兄》
森林和二叉树的转换也是《左孩右兄》，但是森林到树的时候
每一棵树化为二叉树，第一棵树为根，其次其他树的根是它的兄弟
二叉树到森林就是不断拆分它的右子树，每次只拆一个，右子树的左子树保留下来就是它的每一棵树
-----------------------------------------
树的遍历和森林的遍历
树
先根和后根
树的先根=对应二叉树的先序
树的后根=对应二叉树的中序
森林
森林的先序=依次对各个树进行先根
森林的中序=依次对各个树进行后根
森林的中序也可以称为后序

定长编码，哈夫曼，并查集

定长编码就是固定长度来表示字符，在同一棵树中，使用定长编码的符合一定在同一层哈夫曼树

已知

A	B	C	D	E
0.15	0.16	0.07	0.21	0.41

(1)画出相对应的哈夫曼(Huffman)树 (2)计算带权路径长度WPL (3)求A、B、C、D、E的哈夫曼(Huffman)编码

（1）取最小的两者不断重构(结合以后的生成的数再放到整个比较) 以下是详细步骤 1>ABCDE中A与C的数值最小于是乎先画出A C

2>把A和C的合并数值0.22当成AC再去和剩下的B、D、E比较大小，选出最小两个(也就是B和D)，这个时候刚才画的就别动，在旁边重新画一棵树

3>思想同上(别告诉我你现在还没有看明白😒😒😒)

以上就是对应的完整的哈夫曼树了 (2)计算WPL（看带字母的节点，然后看这个节点到顶点经过了几条边，经过几条就数值*几就行）例如A，从顶点到A经过了4条边(幼儿园的都知道怎么数🤣🤣🤣) 也就是0.15*4，总之把所有字母的边*数加起来就是WPL ∴WPL=1*0.41+3*0.15+3*0.07+3*0.06+3*0.21//*是乘号✖，我靠这样看起来很头疼吗？？这不就是程序员必备的？ ∴WPL=1✖0.41+3✖0.15+3✖0.07+3✖0.06+3✖0.21//满足你 (3)求哈夫曼编码（将哈夫曼树的左边画0，右边画1，你就知道了）

然后就是从顶点开始往字母走，假如我们选D，D的编码就是011(简单吧🫵) 答案就是： A:000 B:010 C:001 D:011 E:1 别觉得哈夫曼编码就是固定长度(🤣🫵) 其次呢，构造过程中产生了n-1个点，那么总数就是n+n-1=2n-1个点哈夫曼树是没有度为1的结点的并且所有的编辑点都是叶子结点，其余的都是生成的 --------------------------------------------- 并查集并查集说白了就是两个操作 1.查：查找是否属于同一集合 2.并：如果不属于同一集合就合并，后来放到前面根的孩子里面例如长度为10的并查集，1-2，3-4，5-6，7-8，8-9，1-8，0-5，1-9的顺序进行查找和合并操作最终有几个集合？ 1-2.1和2是不同的集合所以2合并到1中{1，2} 3-4，3和4是不同的集合所以4合并到3中{3，4} 5-6，同理{5，6} 7-8，{7，8} 8-9，9和并到8所属集合{7，8}中{7，8，9} 1-8，将8所属集合合并到1所属集合中{1，2，7，8，9} 0-5，将5所属集合合并到0中{0，5，6} 1-9，将9所属集合合并到1所属集合中{1，2，7，8，9} 所以总结下来就是 {3，4} {5，6} {1，2，7，8，9} ----------------------------------------------------- 前缀编码：没有一个编码是另一个编码的前缀

图

基本概念

G=(V,E)//V是顶点，E是边，G是图，说白了都是英文单词首字母
---------------------------------------------
图不能是空图，就是至少得有一个点，即便一条边都没有
---------------------------------------------
<1,2>这种是有向边，就是只能从1到2，有向边叫弧
(1,2)这种是无向边，1到2，2到1，无所谓，no care
---------------------------------------------
完全图
    有向完全图：任意两点都存在来往的弧
    无向完全图：任意两点都存在边
---------------------------------------------
子图
    点是子集，边是子集，并且边所对应的点都是点子集里面的，才叫子图
    怎么着，是不是对上面的话不以为意？这句话很重要，很重要，很重要
    给你解释一下，假如点是城市，边是道路，全中国的点子集就是天津，北京，上海
    但是现在边子集里面有一条是湖北到北京的，但是湖北不是点子集里面的
    那这个子图就不是它的子图。
---------------------------------------------
生成子图
    顶点完全一样，但是边是子集
---------------------------------------------
连通、连通图、连通分量
两个点之间有路径就是连通的
图中任意两个点之间都有路径的话就是连通图
连通图至少有n-1条边
无向图中的极大连通子图称为连通分量
我知道最后一个有点，无语，学数学的时候也学过极大值这个概念
不知道你还记不记得，极大值是的前提是在一段区域内，最值才是全部作比较
也就说极大连通子图，第一个确保连通，第二个确保尽可能的多的点
---------------------------------------------
强连通图、强连通分量
无他，就是任意两点都有路径，但是这个是有向图，也就说一定是，嗯懂吧，就是说一定是沿着箭头有路径
极大强连通子图是有向图的强连通分量
强连通图至少有n条边
---------------------------------------------
生成树、生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图
第一个是全部顶点，第二个是极小也就是边数最小，但是始终保存连通
对生成树来说，减去一条边就是非连通，加上一条边就是回路

非连通图的连通分量的生成树构成了非连通图的生成森林
这句话很绕，但是你想想，非连通，但是我们的每一个连通分量是连通的
连通的连通分量的生成树，也就是包含连通分量全部顶点，极小边
这些生成树不是一棵，所以就是森林
---------------------------------------------
度
对于无向图来讲，度=边数*2//这是因为一个边是两个顶点共享
对于有向图来讲，入度=出度=边数//因为一个点
---------------------------------------------
简单路径、简单回路
在路径中，顶点不重复出现
除第一个和最后一个，环路中没有重复的顶点
---------------------------------------------
有向树
一个顶点的入度为0，其余顶点的入度为1的有向图，是有向树

有向图的强连通分量的求法

1.找入度为0/出度为0的顶点（满足一个为0就行）
2.依次删除这些顶点以及相连的弧，直到不存在入度/出度为0的顶点（为什么说依次呢，以为当你删除第一个顶点以后可能会造成别的顶点就为0了）
3.删掉的顶点以及剩下的有向图就是强连通分量(每一个被你删掉的顶点就是一个单独的强连通分量)

邻接矩阵


    
 $[\begin{matrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{matrix}]$ 
我们首先不考虑边上的权值，当然存储权值也简单把有边权值替换1，无边的还是0即可，当然可能会有权值为0
无妨，我们定义一个无穷大来表示无边就是很大的数
观察以上矩阵，发现，是对称的，是因为无向图，1-2，那么就是2-1
并且矩阵中的1数是整个图的度
并且每一个点的度只用看行或者列即可


 $[\begin{matrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}]$ 
观察以上矩阵是不对称的
每一个顶点的度是行列的加和，例如1的度是第一行+第一列，因为它的度=入度+出度
整个图的度=矩阵*2(别想多了，就是1的个数*2)

邻接矩阵的空间复杂度是O(n²)

邻接表


    
  
        
            
                1
                ->
                5
                ->
                4
                ->
                2
                ^
            
            
                2
                ->
                 1
                ->
                4
                ^
            
            
                3
                ->
                 4
                 ->
                 5
                 ^
            
            
                4
               ->
                 1
                 ->
                 2
                ->
                 3
                 ^
            
            
                5
                ->
                   1
                ->
                   3
                ^
            
        
        
这个是无向图的邻接表，有向图大致同理，只不过是有指向，也就是1->2，只能是1到2，2到1没有
其次邻接表你也看出来了，1连接的是5，4，2那么4，2，5/2，4，5行不行，当然可以，都是无所谓的

无向图的空间复杂度O(|V|+2|E|)
有向图的空间复杂度O(|V|+|E|)

十字链表、邻接多重表

十字链表是有向图的一种链式存储结构
邻接多重表是无向图的一种链式存储结构
            《不以为意？》
            我看你碰见题目出现了这两个词语的时候懵不懵
            十字链表和邻接多重表
            很像邻接表，我真不想画了，网上随便找两个看看就行
            很简单，甚至比要你画一个喜羊羊还简单

十字链表的空间复杂度O(|V|+|E|)
邻接多重表的空间复杂度O(|V|+|E|)

图的深度优先与广度优先

 
        
            
                1
                ->
                3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                3
                ->
                 4
                 ->
                 5
                 ^
            
            
                4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
我们来分析一下深度优先
    第一步    我们给1标上了①，接下来给3表上了②，于是这时候跳到了
                
        
            
                ①1
                ->
                ②3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                3
                ->
                 4
                 ->
                 5
                 ^
            
            
                4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
跳到了3处，往后给4表上③，这时候跳到
                    
        
            
                ①1
                ->
                ②3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                ②3
                ->
                 ③4
                 ->
                 5
                 ^
            
            
                4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
这时候跳到了
                     
        
            
                ①1
                ->
                ②3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                ②3
                ->
                 ③4
                 ->
                 5
                 ^
            
            
                ③4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
    注意这时候，4后面没有任何东西，于是回退到上一个的最后继续标
                         
        
            
                ①1
                ->
                ②3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                ②3
                ->
                 ③4
                 ->
                 ④5
                 ^
            
            
                ③4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
    标了于是跳到5处，给5的下一个2标上
                            
        
            
                ①1
                ->
                ②3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                ②3
                ->
                 ③4
                 ->
                 ④5
                 ^
            
            
                ③4
                ^
            
            
                ④5
                ->
                   ⑤2
                ->
                   4
                ^
            
        
        
    到此为止全部的数都标完了
    于是 深度优先遍历就是：1、3、4、5、2


接下来我们讨论一下广度优先遍历(简单的一批，就是从上到下，从左到右)
     
        
            
                1
                ->
                3
                ->
                2
                ->
                4
                ^
            
            
                2
                 ^
            
            
                3
                ->
                 4
                 ->
                 5
                 ^
            
            
                4
                ^
            
            
                5
                ->
                   2
                ->
                   4
                ^
            
        
        
    就是1、3、2、4、5
    

当然这是表，如果是树型的呢？

    
很好，其实广度优先就是层次遍历，想我们的树的层序遍历，是不是借助过栈来实现
很好，如果你能想起来的话，如果不能，你g了，如果你觉得是的话也g了，因为是用的队列
就拿这个图来讲，A入队列，A接着准备出，但是先把与A相邻的BC入，A再出
|A|
然后B出，但是先把与B相邻的ED入，B出
|A|B|
然后C出，C是孤独老人
|A|B|C|
以此类推
|A|B|C|E|D|F|G|H|I|
这就是广度优先
以上的东西，不要跳，理解以后做题会很爽，爽的一塌糊涂
深度优先的树也好弄，就是一条道走黑，走不动了再依次回退，直到回退的点有别的路再走黑，这样不断循环直到走完

最小生成树

给定图，利用Kruskal算法（克鲁斯卡算法）生成最小生成树

    
    
(1) 找出最小的边
    即
       
        
(2) 继续找出最小的边
    即
       
        
(3) 继续找出最小的边
    即
       
        
(4) 继续找出最小的边(注意：这里之所以是选40而不是15的边是因为C和D已经有了通路)
    即

        
    

    

    


给定图，利用Prim算法（普里姆算法）生成最小生成树，给定A为初始点

    
(1) 选出与A相连的最小权值的边
    即

    
(2) 选出与AD相连的最小权值的边
    即

    
(3) 选出与ADE相连的最小权值的边
    即

    
(4) 选出与ADEC相连的最小权值的边(注意：不能选择已经用通路的两点的边)
    即

    
总结两种算法的结果是相同的，但是其过程是不同的，解答这类题目的答案就是需要步骤的
克鲁斯卡尔针对边数少挺好，普里姆针对边数多挺好

最短路径

迪杰斯特拉(Dijkstra)【每次选最短，基于前次来组成最短路径】


    第一步，画表格
    
    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        
        
        
    
    
        d
        ∞
        
    
    
        e
        ∞
    
    
        f
        ∞
        
        
    
    
        终点集
        {a,b}
    

a->b有路且权为2，a->c有路且权为5，其他都是没有的写无穷，比较a->b与a->c的权大小，选小的，标红

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        
        
        
    
    
        d
        ∞
        
    
    
        e
        ∞
    
    
        f
        ∞
        
        
    
    
        终点集
        {a,b}
    


然后以ab为整体去看

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        3 (a,b,c)
        
        
        
    
    
        d
        ∞
        5 (a,b,d)
        
        
        
    
    
        e
        ∞
        ∞
        
        
        
    
    
        f
        ∞
        ∞
        
        
        
    
    
        终点集
        {a,b}
        {a,b,c}
        
        
        
    

ab->c=2+1=3因为a->b是2啊，然后b->c是1，a->b->c不就是3
你不会还真的信我说的，以ab为整体，从a到c是5了吧？不会吧🤣不会吧
这就相对于一个1岁的小孩子长到了5岁，我叫你整体看以后发展，你说可以到0岁和6岁，牛逼
还有ab->d=2+3=5，其他都没有了
选最小的标红
    最新更新，我的问题，其实每次的路径，只要后面的点例如此时到5以5看
去其他有没有路径，假如没有到2的路径，反而之前有到2的路径，但是没有选择，那么就平移，而不是说5没有到2的路径就写无穷
然后比较大小的时候，需要和之前到2的这个路径比较，如果这个到2的短，那就选
那你说，5也到不了2啊，但是就是这样的，5的接下来就是2
    

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        3 (a,b,c)
        
        
        
    
    
        d
        ∞
        5 (a,b,d)
        
        
        
    
    
        e
        ∞
        ∞
        
        
        
    
    
        f
        ∞
        ∞
        
        
        
    
    
        终点集
        {a,b}
        {a,b,c}
        
        
        
    


再以abc为整体去看，c可以到def，注意了，整体也是以最后一个元素c作起始点，b是不行的

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        3 (a,b,c)
        
        
        
    
    
        d
        ∞
        5 (a,b,d)
        5 (a,b,d)
        
        
    
    
        e
        ∞
        ∞
        7 (a,b,c,e)
        
        
    
    
        f
        ∞
        ∞
        4 (a,b,c,f)
        
        
    
    
        终点集
        {a,b}
        {a,b,c}
        {a,b,c,f}
        
        
    

重复的话我就不说了，还是选择最小的，标红

然后再选，然后你就傻眼了，f都是终点了，怎么选，嘿嘿，表格不动，把前面一次未标的平移

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        3 (a,b,c)
        
        
        
    
    
        d
        ∞
        5 (a,b,d)
        5 (a,b,d)
        5 (a,b,d)
        
    
    
        e
        ∞
        ∞
        7 (a,b,c,e)
        7 (a,b,c,e)
        
    
    
        f
        ∞
        ∞
        4 (a,b,c,f)
        
        
    
    
        终点集
        {a,b}
        {a,b,c}
        {a,b,c,f}
        {a,b,c, f,d}
        
    

标出最小的，也就是下一个f直接到d

然后d可以到f也可以到e，但是f已经有了，只能去e了

    
        
        第1次
        第2次
        第3次
        第4次
        第5次
    
    
        b
        2 (a,b)
        
        
        
        
    
    
        C
        5 (a,c)
        3 (a,b,c)
        
        
        
    
    
        d
        ∞
        5 (a,b,d)
        5 (a,b,d)
        5 (a,b,d)
        
    
    
        e
        ∞
        ∞
        7 (a,b,c,e)
        7 (a,b,c,e)
        6 (a,b,d,e)
    
    
        f
        ∞
        ∞
        4 (a,b,c,f)
        
        
    
    
        终点集
        {a,b}
        {a,b,c}
        {a,b,c,f}
        {a,b,c, f,d}
        {a,b,c, f,d,e}
    

最终答案就是终点集abcfde
弗洛伊德(Floyd)【基于上一个表，依次将每个点作为中间点去更新】


    我们首先画两个表格
    
    
        D(-1)
        0
        1
        2
    
    
        0
        
        
        
    
    
        1
        
        
        
    
    
        2
        
        
        
    

        
    
        Path(-1)
        0
        1
        2
    
    
        0
        
        
        
    
    
        1
        
        
        
    
    
        2
        
        
        
    

    我们是初始化第一个表为点到点之间的权，如果没有就写无穷
    第二个表，有直接路径就写前一个点的标值，例如0->1有路径，写0.没有路径写-1
    自己到自己的权值是0
    
    
        D(-1)
        0
        1
        2
    
    
        0
        0
        10
        13
    
    
        1
        6
        0
        4
    
    
        2
        5
        ∞
        0
    

        
    
        Path(-1)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        -1
        -1
    

以上就是初始的表，我们接下来分别以每一个点作为中间点更新两个表格

    
    
        D(0)
        0
        1
        2
    
    
        0
        0
        10
        13
    
    
        1
        6
        0
        4
    
    
        2
        5
        ∞
        0
    

        
    
        Path(0)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        -1
        -1
    

有没有发现我把-1变成了0，对0是第一个中间点来更新，至于为什么是0，随你的便
怎么更新？第一个表格，我们是计算x通过0到y，有没有原来的小，有就更新
第二个表格怎么更新呢？就是看上一个path表格的数的后半段
例如现在2通过0到1，2->0->1，0是中间点，path记录的是1前面的一个点
这里的图简单，所以是0，复杂点的图，可能就不是中间点
也就是说2->....->0->.....->1
我们要求的就是.....最右边的一个点，靠近1的
怎么看，看上一个path表格，0到1的路径是写的0，那么就是0
好，依据这些，我们去更新表格
    
    
        D(0)
        0
        1
        2
    
    
        0
        0
        10
        13
    
    
        1
        6
        0
        4
    
    
        2
        5
        15
        0
    

        
    
        Path(0)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        0
        -1
    

这里值得注意的是，1通过0到2，是指1到0，0到2，看上一个表就是6+13是>原本的4的所以不更新
D表不更新，那么P表也对应不更新
你也看到了，以谁作为中间点，谁的那一行与列不用动，好接下来再更新

    
        D(1)
        0
        1
        2
    
    
        0
        0
        10
        
    
    
        1
        6
        0
        4
    
    
        2
        
        15
        0
    

        
    
        Path(1)
        0
        1
        2
    
    
        0
        -1
        0
        
    
    
        1
        1
        -1
        1
    
    
        2
        
        0
        -1
    

    因为对角线不动，并且呢中间点所在行列不变，所以，直接照搬
    然后就剩下两个
    0通过1到2就是10+4=14是大于之前的13的，所以不动
    2通过1到0就是，你是不是回去看图了，你会发现，2->1没有路径，傻眼了
    其实所有的计算都是基于上面一个表，2->1是15，然后1到0是6，就是15+6=21是大于原来的5的，所以不更新

    
        D(1)
        0
        1
        2
    
    
        0
        0
        10
        13
    
    
        1
        6
        0
        4
    
    
        2
        5
        15
        0
    

        
    
        Path(1)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        0
        -1
    

接下来再以2为中间点

    
        D(2)
        0
        1
        2
    
    
        0
        0
        
        13
    
    
        1
        
        0
        4
    
    
        2
        5
        15
        0
    

        
    
        Path(2)
        0
        1
        2
    
    
        0
        -1
        
        0
    
    
        1
        
        -1
        1
    
    
        2
        2
        0
        -1
    

没什么好解释的吧？
    然后看0通过2到1，0->2->1=13+5=18>10不更新
    1通过2到0就是1->2->0=4+5=9>6不更新
    所以

    
        D(2)
        0
        1
        2
    
    
        0
        0
        10
        13
    
    
        1
        6
        0
        4
    
    
        2
        5
        15
        0
    

        
    
        Path(2)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        0
        -1
    

    以上就是最短路径了，第一个表很好看
    第二个表怎么看最短路径呢？
    
    
    
        Path(2)
        0
        1
        2
    
    
        0
        -1
        0
        0
    
    
        1
        1
        -1
        1
    
    
        2
        2
        0
        -1
    

    假如我们看1到0的最短路径，path表中记录的是终点的前一个点
    也就是表格中的1
    所以就是1->1->0=1->0是最短的

	第1次	第2次	第3次	第4次	第5次
b	2 (a,b)
C	5 (a,c)
d	∞
e	∞
f	∞
终点集	{a,b}

	第1次	第2次	第3次	第4次	第5次
b	2 (a,b)
C	5 (a,c)
d	∞
e	∞
f	∞
终点集	{a,b}

	第1次	第2次	第3次
b	2 (a,b)
C	5 (a,c)	3 (a,b,c)
d	∞	5 (a,b,d)	5 (a,b,d)
e	∞	∞	7 (a,b,c,e)
f	∞	∞	4 (a,b,c,f)
终点集	{a,b}	{a,b,c}	{a,b,c,f}

	第1次	第2次	第3次	第4次
b	2 (a,b)
C	5 (a,c)	3 (a,b,c)
d	∞	5 (a,b,d)	5 (a,b,d)	5 (a,b,d)
e	∞	∞	7 (a,b,c,e)	7 (a,b,c,e)
f	∞	∞	4 (a,b,c,f)
终点集	{a,b}	{a,b,c}	{a,b,c,f}	{a,b,c, f,d}

	第1次	第2次	第3次	第4次	第5次
b	2 (a,b)
C	5 (a,c)	3 (a,b,c)
d	∞	5 (a,b,d)	5 (a,b,d)	5 (a,b,d)
e	∞	∞	7 (a,b,c,e)	7 (a,b,c,e)	6 (a,b,d,e)
f	∞	∞	4 (a,b,c,f)
终点集	{a,b}	{a,b,c}	{a,b,c,f}	{a,b,c, f,d}	{a,b,c, f,d,e}

D(-1)	0	1	2
0	0	10	13
1	6	0	4
2	5	∞	0

Path(-1)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	-1	-1

D(0)	0	1	2
0	0	10	13
1	6	0	4
2	5	∞	0

Path(0)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	-1	-1

D(0)	0	1	2
0	0	10	13
1	6	0	4
2	5	15	0

Path(0)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	0	-1

D(1)	0	1	2
0	0	10
1	6	0	4
2		15	0

Path(1)	0	1	2
0	-1	0
1	1	-1	1
2		0	-1

D(1)	0	1	2
0	0	10	13
1	6	0	4
2	5	15	0

Path(1)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	0	-1

D(2)	0	1	2
0	0		13
1		0	4
2	5	15	0

Path(2)	0	1	2
0	-1		0
1		-1	1
2	2	0	-1

D(2)	0	1	2
0	0	10	13
1	6	0	4
2	5	15	0

Path(2)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	0	-1

Path(2)	0	1	2
0	-1	0	0
1	1	-1	1
2	2	0	-1

拓扑排序

拓扑【每次选入度为0的点，删除这个点和他的边】
注意是删除以后有些点就从入度为1变了0了，而且拓扑排序不唯一


我们看这个图，从a入度为0开始，删除a以及它的边


现在发现b和e都是入度为0，也就是你从b或者e都行，我们从b入手


现在e和c都是入度为0的，都可以选我们选c


不用多说了吧，只有e了
所以我们的拓扑序列就是abced
当然，不止这一个

关键路径/AOE网

拓扑求Ve（点的最早开始时间）


    我们把每个点的Ve（最早开始时间设置为0），先不管Vl
    
    
        
        V1
        V2
        V3
        V4
    
    
        Ve
        0
        0
        0
        0
    
    
        Vl
        
        
        
        
    

然后我们从a入度为0，开始它连接V2和V3，到V2是2，到V3是5
2和5都比0大所以更新，并且删除V1以及它的边
    
    
        
        V1
        V2
        V3
        V4
    
    
        Ve
        0
        2
        5
        0
    
    
        Vl
        
        
        
        
    

    

    现在从V2走，因为只有V2是入度为0，V2连接V3和V4
    V2本身是2，V2再到V3就是2+1=3
    V2本身是2，V2再到V4就是2+3=5
    但是V3是5比3大所以不更新
    V4是0比5小更新
    
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        5
        0
        0
    
    
        Vl
        
        
        
        
        
        
    

别奇怪了，之前的表格画少了，我不想改，太麻烦，就这样
然后我们删除V2和它的边


入度为0的就是V3，看V3连接着V4，V6，V5
    V3本身是5，V3到V4就是5+3=8，比原来的V4的5大，更新
    V3本身是5，V3到V6就是5+1=6比原来V6的0大，更新
    V3本身是5，V3到V5就是5+4=9比原来V5的0大，更新
    
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        6
    
    
        Vl
        
        
        
        
        
        
    

再删除V3和它的边


    现在入度为0的就是V4
    V4连接V5和V6
    V4本身是8，V4到V5就是8+1=9，原来的V5是9，不更新
    V4本身是8，V4到V6就是8+4=12，原来的V6是6比12小，更新为更大的12
    
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        12
    
    
        Vl
        
        
        
        
        
        
    

再删除V4


V5到V6，V5本身是9，到V6就是9+1=10，没有12大，不更新
最终的表就是
    
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        12
    
    
        Vl
        
        
        
        
        
        
    


接下来我们求最晚开始时间Vl
就是逆拓扑排序：每次选 出度为0的，从最后一个点开始
也就是从V6开始，最后一个点的最晚和最早都是一样的
把所有点的最晚时间初始化为最后一个点的最晚时间


    
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        12
    
    
        Vl
        12
        12
        12
        12
        12
        12
    

V6连接着V5，V4，V3，我们用12分别减去，然后比大小，更新小的那个数
     
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        12
    
    
        Vl
        12
        12
        11
        8
        11
        12
    

    然后删除V6以及它的边


接下来不多讲了，以此类推最终的表就是
        
    
        
        V1
        V2
        V3
        V4
         V5
         V6
    
    
        Ve
        0
        2
        5
        8
        9
        12
    
    
        Vl
        0
        4
        5
        8
        11
        12
    

求出来这个表格是活动的最早最晚开始时间，我们要求事件，的最早和最晚，再画一个表格
      
    
        
        最早
        最晚
    
    
        a
        
        
    
    
        b
        
        
    
              
        c
        
        
    
              
        d
        
        
    
              
        e
        
        
    
              
        f
        
        
    
              
        j
        
        
    
              
        h
        
        
    
              
        i
        
        
    
              
        j
        
        
    

事件是边，事件的最早时间就是前面一个点的最早开始时间
      
    
        
        最早
        最晚
    
    
        a
        0
        
    
    
        b
        0
        
    
              
        c
        2
        
    
              
        d
        2
        
    
              
        e
        5
        
    
              
        f
        5
        
    
              
        j
        5
        
    
              
        h
        8
        
    
              
        i
        8
        
    
              
        j
        9
        
    

    那最晚怎么算，用点的最晚开始时间减去前面边(事件)的时间
    
    
        
        最早
        最晚
    
    
        a
        0
        2
    
    
        b
        0
        0
    
              
        c
        2
        4
    
              
        d
        2
        5
    
              
        e
        5
        5
    
              
        f
        5
        7
    
              
        j
        5
        11
    
              
        h
        8
        10
    
              
        i
        8
        8
    
              
        j
        9
        11
    

每个事件的时间余量就是最晚-最早，拿f来讲7-5=2，也就是2天

    
        
        最早
        最晚
    
    
        a
        0
        2
    
    
        b
        0
        0
    
              
        c
        2
        4
    
              
        d
        2
        5
    
              
        e
        5
        5
    
              
        f
        5
        7
    
              
        j
        5
        11
    
              
        h
        8
        10
    
              
        i
        8
        8
    
              
        j
        9
        11
    

    看我标红的，最晚和最早时间是一样的，也就是关键路径，一天都不能少

	V1	V2	V3	V4
Ve	0	0	0	0
Vl

	V1	V2	V3	V4
Ve	0	2	5	0
Vl

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	5	0	0
Vl

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	6
Vl

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	12
Vl

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	12
Vl

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	12
Vl	12	12	12	12	12	12

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	12
Vl	12	12	11	8	11	12

	V1	V2	V3	V4	V5	V6
Ve	0	2	5	8	9	12
Vl	0	4	5	8	11	12

	最早	最晚
a	0
b	0
c	2
d	2
e	5
f	5
j	5
h	8
i	8
j	9

	最早	最晚
a	0	2
b	0	0
c	2	4
d	2	5
e	5	5
f	5	7
j	5	11
h	8	10
i	8	8
j	9	11

	最早	最晚
a	0	2
b	0	0
c	2	4
d	2	5
e	5	5
f	5	7
j	5	11
h	8	10
i	8	8
j	9	11

查找

顺序查找、折半查找、分块查找

顺序查找对顺序表和链表适用
一般线性表的顺序查找
等概率：ASL(成功)=(n+1)/2
不等概率：概率*该点的查找长度---------举例子：长度为3，1的概率是2，2的概率是1，3的概率是9，ASL=1*2+2*1+3*9
等概率：ASL(不成功)=n+1
有序线性表的顺序查找
ASL成功与一般无异
ASL不成功=n/2+n/(n+1)
折半查找(二分查找)只适用有序的顺序表，不适合链表
具体过程如下，挺简单的，值得注意的是，指针的移动是多一位或者，少一位的，因为你看1到6没有，那肯定把指针移到比1小如0，或者比6大如7，而不是1和6这边界
为什么不是？给你10个有序摆放的屎找出是你拉的
你一开始找的是第1个到第5个
没找到，结果第二次找，是第5个到第10个
你说滑稽吗？明明你也很爱我，我也很爱你，没结果~
🙂明明第一轮已经看过了第5个了，干嘛第二轮还要看，你说呢

对{5,13,17,29,37,41,61,79,89}利用折半查找值为29的元素

我们规定了首尾都有一个指针，其次mid的指针由下面式子给出
     $m i d = \frac{l o w + h i g h}{2} = \frac{0 + 8}{2} = 4$ 
是的，折半的想法，此时mid指向的值为37比我们要找的值29大
这就是说明我们的中间的指针是比这个大的(😏废话)
所以我们把高指针的指向重新定义为mid(中间指针)的前一个
如果你对为什么是前一个没有疑虑，那么你很聪明
因为我们比较的就是中间指针肯定是要么大要么小，如果相同的就结束了啊
所以这个相当于不属于我们下一次查找的范围了



     $m i d = \frac{l o w + h i g h}{2} = \frac{0 + 3}{2} = 1$ (向下取整)
mid指向的是13，比29小，我们把low(小)指针改为mid(中间指针)的后面一个


     $m i d = \frac{l o w + h i g h}{2} = \frac{2 + 3}{2} = 2$ (向下取整)
此时mid指向的是17还是比29小，于是把low指针指向mid的下一个

     $m i d = \frac{l o w + h i g h}{2} = \frac{3 + 3}{2} = 3$ 
bingo！mid指向29，刚好是我们要找的，好吧，麻烦是麻烦了点
但是编程实现起来比其他简单啊🤨

思考一个问题，折半查找的过程能不能用一棵树来表示
给你一个序列：7  10  13  16  19  29  32  33  37  41  43

    
看到这个图，注意没有，每一个根结点就我们每次的中间指针
并且，这个树的中序遍历是一个升序的，是一棵平衡二叉树
平均查找长度ASL=log₂(n+1)-1
树高h=[log₂(n+1)]//向上取整
折半查找的时间复杂度=O(log₂n)
在如图中的查找成功的ASL=（1*1+2*2+3*4+4*4）/10=3
查找不成功的ASL=（3*4+4*8）/12=11/3
为什么？看第一层1个，第二层两个，每一层代表查找几次
即第一层1个并且查找一次=1*1
第二层2个并且查找两次=2*2
....
看不成功的
第三层有4个不成功=3*4
第四层有8个不成功=4*8
为什么它看起来失败的在第四层，而我说第三层呢？
你是不是傻瓜，失败那个点需要找吗？你找到7，还比7小，往左子树走，没有东西了，不需要比较了，可不就是3层
分块查找
它结合了顺序查找和折半查找的优点
什么意思？
看下面给定序列
88 24 72 61 21 6 32 11 8 31 22 83 78 54
我们建立一个索引表
|24|54|78|88|
|1 |7 |10|13|    这是当前数在查找表中的位置
我们把序列简单构成查找表
|24|21|6|11|8|22|32|31|54|72|61|78|88|83|
  ↑             ↑       ↑       ↑
  24             54       78       88
为什么？难道你不奇怪吗？凭什么，四个索引是怎么来的？
你凭什么这么分，当我是傻子吗？
很好，我们分的依据第一个是根号（总数）
也就是对总个数求开方，对14求开方就是，就是不知道🤣
3到4之间，我们分4块，我知道你想问为什么不分3块，考试的时候脑袋一抽分3块怎么办？
不怎么办，你取3块就取3块呗，怎么地，厕所五个坑，想去哪里去哪里，我选第一个就是社牛，第5个就是社恐了？
分为4块以后，选择合适的数作为分块的边界，54指向32是因为32是22后面第一个比24大的
你可以简单的看到，就算索引表是有序的，但是查找表的分块是无序的
分块查找的ASL=L(索引表查找长度)+L(查找表的查找长度)=(b+1)/2+(s+1)/2
为什么是(b+1)/2首先这是顺序查找，顺序查找的等概率是长度除上个数[(b+1)×n]/2 × 1/n = (b+1)/2
例如我们找6，首先在索引表中找，4个，（4+1）/2=2.5
然后在24-54这个查找表分块中找
有6个，（6+1）/2=3.5
所以ASL=2.5+3.5=6
假如一个序列有n个值，我们索引表分多少块比较好？
√n次（啊呀，就是根号n啊）

二叉排序树、二叉平衡树、红黑树(头疼，不讲)

二叉排序树（二叉查找树）
左子树 < 根 < 右子树
这里重点介绍构建和删除，会构建就会插入，查找
构建给你一个序列：100 80 90 60 120 110 130

    
再放入80，80比100小，进入左子树

    
再看90，比100小进入左子树，再比较80，比80大，进入80的右子树

    
再看60，比100小，进左子树，比80小进入80的左子树

    
再看120比100大进入右子树

    
再看110，比100大进入右子树，比120小，进入120的左子树

    
再看130，比100大进入右子树，比120还大进入120的右子树

    
结束

我们来看删除
叶子结点直接pass无所谓，如果我们删除120这个结点怎么办？
两种，让直接后继代替，或者直接前驱代替

    
或者

    
平衡二叉树（AVL树）
任意结点的左右子树高度差的绝对值不超过1
定义左子树和右子树高度差为该结点的平衡因子
并且平衡因子的值只能为-1，0，1
---------------------------------
LL型：失衡结点在左子树左孩子上
    办法：以平衡因子结点右旋//注意区别失衡结点和平衡因子结点
---------------------------------
RR型：失衡在右子树的右孩子上
    办法：以平衡因子结点左旋
---------------------------------
LR：失衡在左子树的右孩子上
    办法：左旋平衡因子结点的左孩子，在右旋平衡因子结点
---------------------------------
RL：失衡在右子树的左孩子上
    办法：右旋右孩子再左旋
---------------------------------
现在到了喜闻乐见的举例子环节，什么？不喜欢，拉到🤣
给定关键字序列{15,3,7,10,9,8}构造一棵平衡二叉树

    
一开始是一棵空树，然后我们加入15

    
然后加入3，因为3比15小，加入15的左子树

    
再加入7，比15小加入左子树，比3大，加入3的右子树

    
现在我们看三个结点的平衡因子，15的，左右子树高度差是不是2-0=2.为什么是2，你要把左子树当成整体看
然后3的左右子树高度差是0-1=-1
然后7的左右子树高度差是0-0=0
失衡结点是（7），因为是（7）造成的，然后失衡因子是2也就是结点（15）
失衡节点是在左子树的右孩子，也就是LR
先左旋左孩子，再右旋
我们看看左旋左孩子怎么做

    
我们再右旋平衡因子结点

    
然后连线

    
然后再插入我们的10，因为10比7大，进入右子树，然后比15小，进入15的左子树

    
这个时候也没有失衡，我们就继续插入9，因为9比7大，进入右子树，比15小进入15的左，比10小，进入10的左

    
好，开始失衡了，因为（7）的左右子树高度差=1-3=-2
但是你看15的平衡因子=2-0=2，我们找的是最小的树的不平衡因子
9是在15树的左子树的孩子上
即LL，以15为核心，右旋

    
再连线

    
我们再插入8，因为8比7大，进入右子树，8比10小进入10的左子树，8比9小再进入9的左子树

    
此时，（7）的平衡因子是1-3=-2，（10）的平衡因子是2-1=1
只有（7）是不平衡的，而（8）在（7）的右子树的左孩子上
即RL型，先右旋右孩子，再左旋

    
这个时候，（7）的左旋是指将（7）作为9的左孩子，但是9已经有了怎么办？就将9的孩子抢过来当成自己的右孩子

    
完结撒花
二叉平衡树的删除怎么办？

    
假如我们删除32这个结点，删除节点方法和排序二叉树一样，然后才是使用平衡二叉树的方法整合为平衡二叉树
32是叶子结点直接删除

    
删除和插入构建很大的不同就是你不能通过肉眼简单的看出来是什么型
只能通过编程的思想，程序是如何判断的呢？就是靠平衡因子
（44）的平衡因子是-2，（78）的平衡因子是1，所以就是RL型
为什么？-2是因为左减右，为负，所以右大于左，所以不平衡一定在右中
1是正数，所以左大于右，所以不平衡在左中
合起来就是右左RL
好，用我教你的方法以（44）为基础，执行RL变换

    
然后（44）再左旋，因为（50）有左孩子了，所以抢过来当右孩子，（44）再自己当（50）左孩子

    
 $\begin{aligned} n_{h} 表示深度为 h 的平衡二叉树中含有最少结点数 \\ n_{0} = 0, n_{1} = 1, n_{2} = 2 \\ n_{h} = n_{h - 1} + n_{h - 2} + 1 \end{aligned}$ 
咋地，以上公式不以为意是吧，反正我突然摆出来，莫名其妙的，懒得看就是说
那我问你：具有5层结点的AVL至少有多少个结点？12个
AVL不是AV，是平衡二叉树😡

B、B+树

m阶B树是所有结点平衡因子均为0的m路平衡查找树
重要性质
m阶B树最多m个分支，m-1个元素
m阶B树最少[m/2]个分支，[m/2]-1个元素，向上取整。注意根例外，根最少2个分支，1个元素
三个特性
平衡：所有叶子都在同一层
有序：结点内有序排列，结点外呢，按照排序树一样，左小右大
多路

    
呼~~~累死我了，网页画图真的是一个个坐标点自己尝试出来的
以上就是一棵五阶B树
注意看我的箭头，可不是随便指的，例如我们找16
首先比22小，去（5  11）里面
比最大的11都大，所以走（5  11）的第三个箭头
去（13  15）里面，结果比里面最大15还大，去（13  15）的第三个箭头，也就是失败，查找失败
如果说我们找10，那就是22到（5  11）然后因为比5大，比11小，所以走（5  11）的第二个箭头，还是失败
也不是说全失败啊，我们找11，可不就是11了
------------------------------------------------
B树的插入和删除
插入一定是插入到叶子结点
插入以后如果满足元素个数要求就直接插
插入以后如果比要求的多了，那么就分裂，这中情况是叫溢出
怎么分裂：
在插入以后的结点，从中间位置[m/2]向上取整，分成两半，左半部分不动，此点上移，右半部分分裂一个新结点
太懒了，不想画图了，我贴个图又可能加载不出来咋办呢，头疼啊
删除
1.如果不是叶子结点，那么删除以后用它的直接前驱或者后继上来顶替就行
如果是叶子结点三种情况：
    直接删，还是满足
    兄弟够借，左右兄弟随便一个上去，父亲下来顶替被删元素
    兄弟不够借，合并：
            左合并：此点左父下移，此点右并过来
            右合并：此点右父下移，此点左并过去
B+
其他和B一样，只是结点子树的个数与此结点里面关键字个数相同
B+树，除了叶子结点，都是索引，也就是说，还没有到叶子结点就找到一样的时候，并不是找到了
还要继续向下，找到叶子结点以后，还要找，找到对应的以后，叶子结点本身也是一个对应的关键字，如同
我们之前那个B树图，下面都是失败，而这个则是成功对应的记录

散列表(哈希表)

设散列表长为11，记录关键字集合为{15，17，28，41，37，31，56，23，45，51，73}，散列函数：H(Key) = key MOD 11，冲突处理采用线性探测法，请给出散列表的构造过程，再求平均查找程度ASL (1)先看散列函数，H(Key) = Key MOD 11.(对每个数都取余，与11相除，取余)

余数	4	6	6	8	4	9	1	1	1	7	7
原数	15	17	28	41	37	31	56	23	45	51	73

(2)我们先写出一个0-10（11个）

0	1	2	3	4	5	6	7	8	9	10

我们规定，按照余数，放进这个表格中，如果冲突线性探测就是往后顺延一位（如果一位不行就再继续顺）我们一步步来，把余数4对应的15放到4处

0	1	2	3	4	5	6	7	8	9	10
				15

此时记录15到位4处动了（1）次，接着把17放到6处

0	1	2	3	4	5	6	7	8	9	10
				15		17

记录17动了（1）次，接着放28，因为28是6，和之前的17冲突了，采用线性探测就是往后顺延一位

0	1	2	3	4	5	6	7	8	9	10
				15		17	28

记录28动了（2）次，接着41放8处

0	1	2	3	4	5	6	7	8	9	10
				15		17	28	41

记录41动了（1）次，接着37，与15冲突了往后顺延1位

0	1	2	3	4	5	6	7	8	9	10
				15	37	17	28	41

记录37动了（2）次，接着31，放9处

0	1	2	3	4	5	6	7	8	9	10
				15	37	17	28	41	31

记录31动了（1）次，接着56放1处

0	1	2	3	4	5	6	7	8	9	10
56				15	37	17	28	41	31

记录56动了（1）次，接着23放1处冲突顺延到2处

0	1	2	3	4	5	6	7	8	9	10
	56	23		15	37	17	28	41	31

记录23动了（2）次，接着45放1处冲突顺延到2处再冲突再顺延3处

0	1	2	3	4	5	6	7	8	9	10
	56	23	45	15	37	17	28	41	31

记录了45动了（3）次，接着把51放7处与28冲突顺延到8冲突到9冲突于是放到10

0	1	2	3	4	5	6	7	8	9	10
	56	23	45	15	37	17	28	41	31	51

记录51动力4次，接着73放7处冲突，再8冲突，再9冲突，再10冲突，再0放

0	1	2	3	4	5	6	7	8	9	10
73	56	23	45	15	37	17	28	41	31	51

以上就是表的构造过程了 15：1次 17：1次 28：2次 41：1次 37：2次 31：1次 56：1次 23：2次 45：3次 51：4次 73：5次求ASL(平均查找程度就是将以上数加起来再除他们的总个数)

ASL= $\frac{1 + 1 + 2 + 1 + 2 + 1 + 1 + 2 + 3 + 4 + 5}{10} = 2.3$

还有一种题目是冲突采用链地址表示法前面求余数的步骤一样就是构造的时候采用链表的思想

余数	4	6	6	8	4	9	1	1	1	7	7
原数	15	17	28	41	37	31	56	23	45	51	73

就是构造以下基表竖着的

0	^
1	->	56	->	23	->	45	^
2	^
3	^
4	->	15	->	37	^
5	^
6	->	17	->	28	^
7	->	51	->	73	^
8	->	41	^
9	->	31	^
10	^

求ASL，就是1*第一列的个数+2*第二列的个数+3*第三列的个数... 此题就是ASL=1*6+2*4+3*1

散列表查找效率取决三个因素：散列函数、处理冲突、装填因子α

α = \frac{表中记录数 n}{散列表长度 m}

α越大，说明装填记录越满，发生冲突可能性越大这里补充一个，查找失败的ASL怎么算，什么时候算查找失败？当然是碰到空地址就是查找失败了

排序

排序的基本概念

除去我写的外部排序，本节所有排序都是属于内部排序，注意区别二路归并和多路归并
算法的稳定性
    待排序表中两个元素如果对应关键字一样，在使用某一种排序方法后，相对位置不变，则算法稳定
算法的稳定性不代表算法的好坏
    
        
            
                呵呵，背吧哥们🤣🐒🫵🏿
                最好时间复杂度
                最坏时间复杂度
                 平均复杂度
                辅助空间复杂度
                稳定性
            
            
                直接插入排序
                O(n)
                O(n²)
                O(n²)
                O(1)
                稳定
            
            
                折半插入排序
                O(n)
                O(n²)
                O(n²)
                O(1)
                稳定
            
          
                希尔
                O(n)
                O(n²)
                O(n的1.3次方)
                O(1)
                不稳定
            
         
                冒泡
                O(n)
                O(n²)
                O(n²)
                O(1)
                稳定
            
                 
                快排
                O(nlog₂n)
                O(n²)
                O(nlog₂n)
                O(log₂n)
                不稳定
            
                         
                简单选择排序
                O(n²)
                O(n²)
                O(n²)
                O(1)
                不稳定
            
        
                堆排序
                O(nlog₂n)
                O(nlog₂n)
                O(nlog₂n)
                O(1)
                不稳定
            
        
                2路归并排序
                O(nlog₂n)
                O(nlog₂n)
                O(nlog₂n)
                O(n)
                稳定
            
        
                基数排序
                O(d(n+r))
                O(d(n+r))
                O(d(n+r))
                O(r)
                稳定

插入排序(直接插入、折半插入、希尔)


直插
直插听起来简单，实际上确实简单
给你一个序列
{49，38，65，97，76，13，27，49}
我们会每次选一个作为比较值，例如一开始我们选择第一个49作为已经排好的数字
{（49），38，65，97，76，13，27，49}给它做上标记
然后我们选38对比我们的49，发现38比49小，直接把49往后移动一位
{，（49），65，97，76，13，27，49}因为我们是把38存放在temp临时变量中，即便49替代了原本的38也无所谓
现在继续比较发现已经没有元素了，所以把38放入，并且标记排好的序列
{（38，49），65，97，76，13，27，49}
接下来我们把65放到临时变量temp中，依次从后比较已经排好的序列
比49大，也就是比排好的序列最大都大，所以不动，将排好序列标记覆盖到65
{（38，49，65），97，76，13，27，49}
同样拿出97，比所有都大
{（38，49，65，97），76，13，27，49}
现在拿出76，发现比97小，97，往后退一位，占了76位置
{（38，49，65，，97），13，27，49}
然后比较76和65，发现比65大，所以放到65的位置+1处，也就是原本97的位置
{（38，49，65，76，97），13，27，49}
再比较13，比97小，97后退，76后退，65、49、38依次后退
{（13，38，49，65，76，97），27，49}
后面我就不说了，都是一样的，但是注意这最后一次
{（13，27，38，49，65，76，97），49}
到这里的时候，49按照以往的一样进行排序
比97、76、65都小，他们都后退，但是到49的时候，两个相等怎么办？
比它小的才后退，不然不动，也就是
{（13，27，38，49，65，76，97），49}
{（13，27，38，49，49，65，76，97）}
相信你也看出来了，算法稳定性是指关键字一样的元素使用排序后相对位置是否改变，这里49和49的相对位置没有改变
所以直插排序是稳定算法

折半
对{5,13,17,29,37,41,61,79,89}利用折半查找值为29的元素

我们规定了首尾都有一个指针，其次mid的指针由下面式子给出
     $m i d = \frac{l o w + h i g h}{2} = \frac{0 + 8}{2} = 4$ 
是的，折半的想法，此时mid指向的值为37比我们要找的值29大
这就是说明我们的中间的指针是比这个大的(😏废话)
所以我们把高指针的指向重新定义为mid(中间指针)的前一个
如果你对为什么是前一个没有疑虑，那么你很聪明
因为我们比较的就是中间指针肯定是要么大要么小，如果相同的就结束了啊
所以这个相当于不属于我们下一次查找的范围了



     $m i d = \frac{l o w + h i g h}{2} = \frac{0 + 3}{2} = 1$ (向下取整)
mid指向的是13，比29小，我们把low(小)指针改为mid(中间指针)的后面一个


     $m i d = \frac{l o w + h i g h}{2} = \frac{2 + 3}{2} = 2$ (向下取整)
此时mid指向的是17还是比29小，于是把low指针指向mid的下一个

     $m i d = \frac{l o w + h i g h}{2} = \frac{3 + 3}{2} = 3$ 
bingo！mid指向29，刚好是我们要找的
以上就是我们折半查找的思想
可是我们说的是折半排序啊，对没错，和直接插入排序一样，每次都会构建一个部分有序序列
但是每次往后拿新的元素比较的时候，不再是从后往前一个个比，而且是采取折半查找方法定位元素位置
定位以后，该元素+1位置直到我们新的元素位置的所有元素都后移一位
然后把新的元素插入到该元素+1位置，是不是很抽象，我有时候挺无奈的
因为我确实觉得这样说，是很清晰的，但是这是基于我本身是十分了解的前提下
但是很多人是没有我这样的基础的，也就说，这是一种自我陶醉
所以说这是一个稳定的算法，因为只有比它小的才会往前面放
注意折半查找用在已经排好序的里面，从后面依次选一个进行查找，然后查找位置插入

希尔
利用希尔排序对关键字系列{40，24，80，39，43，18，20，10，90，70}从小到大排序(增量5，3，1)
    增量的意思就是每个x个为一个组比较大小
    当增量为5时
    40，24，80，39，43，18，20，10，90，70
    40，24，80，39，43，18，20，10，90，70
    40，24，80，39，43，18，20，10，90，70
    40，24，80， 39，43，18，20，10，90，70
    40，24，80， 39，43，18，20，10，90，70
    最终我们得出增量为5的分组（颜色不同来区分）
    40，24，80， 39，43，18，20，10，90，70
    （把小的放前，大的放后就行）
    18，20，10， 39，43，40，24，80，90，70
    就是以上的第一次增量，当增量为3的时候
    18，20, 39，43，40，24，80，90，70
    18，20, 24，43，40，39，80，90，70
    完成，以下是增量为1的
    18，20, 24，43，40，39，80，90，70
    18，20，24，39，40，43，70，80，90
    完成
咋，我说完成就完成了？这就是你完全把自己托付给别人了
算法稳定性呢？怎么看？这是一个不稳定的算法，因为你选取的比较有可能导致呢，两个相同元素的相对位置发生变换
因为不是依次比较的，反正你知道大概原理就行

交换排序(冒泡排序、快速排序)


冒泡
每轮从前往后依次比较相邻两个元素大小，小放前大放后，相等不动，每轮可以选出一个最大的放在最后一个位置
{36，27，20，60，55，7，28，36，52，44，16}
比较36和27，27放前，36放后
{27，36，20，60，55，7，28，36，52，44，16}
比较36和20，20放前，36放后
{27，20，36，60，55，7，28，36，52，44，16}
比较36和60，60比36大，不动
{27，20，36，60，55，7，28，36，52，44，16}
比较60和55，55放前
{27，20，36，55，60，7，28，36，52，44，16}
然后不说了
{27，20，36，55，7，60，28，36，52，44，16}
{27，20，36，55，7，28，60，36，52，44，16}
{27，20，36，55，7，28，36，60，52，44，16}
{27，20，36，55，7，28，36，52，60，44，16}
{27，20，36，55，7，28，36，52，44，60，16}
{27，20，36，55，7，28，36，52，44，16，60}
以上就是第一轮比较次数 ，后面的几轮以此类推

快排
对{46，58，15，45，90，18，10，62}进行快速排序
    以第一个数为基准提出来
        ___  58  15  45  90  18  10  62
        ___  58  15  45  90  18  10  62<--
    这时候比较最后一个数与第一个数46的大小，62>46(不动)
        ___  58  15  45  90  18  10<--  62
    这时候比较向前移动一位比较10和46大小，10<46(将10移动到46原本在的第一位)
        10  58  15  45  90  18  ___  62
    这个时候比较的指向是从前面也就是10的后面开始
        10  58<--  15  45  90  18  ___  62
    58>46(将58移动到10原本的位置)
        10  ___  15  45  90  18  58  62
    这时候再从后面也就是58的前面
        10  ___  15  45  90  18<--  58  62
    18<46(移动到58原本所在的前面)
        10  18  15  45  90  ___  58  62
    再从18的后面开始比较
        10  18  15<--  45  90  ___  58  62
    15<46(不动)
        10  18  15  45<--  90  ___  58  62
    45<46(不动)
        10  18  15  45  90<--  ___  58  62
    90>46(移动到后面的空位去)
        10  18  15  45  ___  90  58  62
    到此为止全部元素都和46比较过了，于是把46放到空位处
        10  18  15  45  46  90  58  62
    此时46的位置已经确定了，46所在的位置就是这里，你可能也感觉出来了，这一轮比较就是把比46小的一股脑丢46前面，比46大的一股脑丢到后面去
    既然46确定了，只需要比较两块内容就行了，也就是46前面的，和46后面的就行，还是按照之前的方法
        ___  18  15  45<--  46  ___  58   62<--
    哈哈哈，开启双开模式，前面提10，后面提90
    45>10(不动);62<90(动)
        10  18  15<--  45  46  62  58<--  ___
        10  18<--  15  45  46  62  58  90
    我会把比较完成的数标红
        10  18  15 45  46  62  58  90
        10  ___  15 45<--  46  ___  58<--  90
        10  ___  15<-- 45  46  58  ___  90
        10  15  18  45  46   58  62  90
注意如果碰到相同的是不动的
快速排序是内部排序中平均性能最好的
快排最大递归深度是n，最小是log₂n
怎样快速判断，快排第几趟是不可能的结果
将序列完整排好，对比选项，看看是否至少有2个位置是对应上的

选择排序(简单选择、堆排序)


简单选择
如同名字一样，简单
{60，27，20，36，55，77，28，36，52，44，16}
每轮都在剩下的数中选最小的换到前面
用一个temp临时变量存储数组中元素最小的下标，依次比较数组，找出最小的，然后和数组从前到后交换
例如第一个
我们记录假设最小就是数组开头k=0，然后我们比较第二个
{60，27，20，36，55，7，28，36，52，44，16}
发现27更小，更新k=1，一定是数组下标，而不是本身数值，因为我们要交换
{60，27，20，36，55，7，28，36，52，44，16}
20比存储的k=1（27）更小，再更新k=2
以此类推
{60，27，20，36，55，7，28，36，52，44，16}
k最终的值是5，也就是元素7
让数组[0]与数组[k]交换
{7，27，20，36，55，60，28，36，52，44，16}
第一个我们就确定了，第二趟我们让k假设第二个元素，也就是k=1最大，也就是让k=1，然后依次比较记录
后面就不说了
唯一需要注意的是，这个简单选择排序是不稳定的，因为假如有两个一样的，一个在前一个后
由于最小的数在最后面，让第一个和最小的交换位置，所以第一个就跑第二个后面了

堆排
对{5,1,6,9,2}如何构造大/小根堆
    怎么说呢，就是大小根堆简单就是根是最大/小的就是
    我们操作的步骤第一步就是将给出的数列按完全二叉树排列(完全二叉树不知道的话那，废了)
    
    
我们这样5个数，我们取一半（向下取整）
     $\frac{5}{2} = 2$ 
我们从第二个数开始即1【2】开始比较它与它的左右孩子们的大小，大的放根上就行
    
    
    然后再第1个数即5【1】比较它与它的左右孩子大小
    
    
以上就是大根堆的构造过程，小根堆同理但是这只是简单数字比较少的时候的情况
一旦数字过多就会出现，一些没讲过的情况例如
    {9,43,-54,4,-13,10,36}(初步一看就不是最大根堆/最小根堆，因为第一个数既不是最大也不是最小)

    
我们构造大根堆，第一步还是总个数/2
     $\frac{7}{2} = 3$ (向下取整)
比较第三个与它的左右孩子的大小，大的放根上

    
接着比较第二个数与它的左右孩子的大小，大的放根上

    
接着比较第一个数与它的左右孩子的大小大的放根上

    
OK，此时就是最大根堆了，哎呀呀，我想说的那种情况没有发生，
    就是那种像最后一步的时候，9和43不是换了嘛，9到新位置以后如果它的左右孩子有比它大的，也要再调换

然后就是仅仅这样不算是堆排序，这一步只是把最大值选出来了
我们可以通过移除最大值，来继续排但这样多此一举
不如直接让这个根（最大值）和我们的第七个数（大概率最小值）调换
调换以后，我们可以忽略它，然后重新排序
    按照我们说的，继续

    
    嘿嘿
     $\frac{6}{2} = 3$ 
    还是比较第三个数和它的左右孩子，但是这次，它只有左孩子了
    然后就是第二个数和它的左右孩子，9还是最大的，然后我们比较
    第一个数，发现36是最大的调上去

    
    到这里并没有结束，我之前说的情况发生了
    就是第六个数10比第三个数（掉下来的）-54大，此时同样需要换
    最终就是

    
然后就是再把根36和最后位第六位调换，然后重新排，以此往复
直到排完就是一个以完全二叉树的从小到大的排序了
小根堆是同理的。（暂时更到这里，累死我了😭😣🤤😬😰😨🥶🥵🥴😵‍💫🤧🤮🤢🫵😗）

归并排序

归并的含义是将两个或者两个以上的有序表合并成一个新的有序表
对{40，24，80，39，43，18，20，10，90，70} 进行从小到大排序过程(两两分组比较)
    
    这应该看得懂吧？一目了然了都😏😏
趟数与元素以及归并路数之间关系
 $m = [l o g_{k} N] / / m 趟， k 路， N 元素$

基数排序

对{457,131,481,219,392,674,350,815,315}进行基数排序
    
接下来就是收集（从上到下，从左到右）：{350,481,392,674,475,815,315,137,219}
    
接下来就是收集（从上到下，从左到右）：{815,315,219,137,350,674,475,481,392}
    
接下来就是收集（从上到下，从左到右）：{137，219，315，350，392，475，481，674，815}
至此你也看出来了，它到底是怎么运作来实现排序的
也不难，先个位数，再十位数，再百位数，一步步确保
切记：基数排序不能对浮点以及双精度类型进行排序

内部排序总结

以上的各种排序都是内部排序
========================================
n较小，采用直接插入排序/简单排序，并且当记录本身信息量大的时候使用简单排序
========================================
n较大，采用快速排序、堆排序、归并排序，其中快速排序被认为是平均最好，快排、堆排不稳定，但是归并稳定
========================================
文件基本有序的时候，选择直接插入或冒泡
========================================
n巨大，关键字位数少的前提下，使用基数排序
========================================
当记录本身信息量巨大，采用链表，避免耗费大量时间移动记录

外部排序

排序算法

算法

觉得页面太小点击下面链接
算法

算法判断题

觉得页面太小点击下面链接
算法判断题

算法易混淆点

============================================
时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。
============================================
一个算法应该具有以下5个特性：有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。 因此一个算法可以没有输入
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================
============================================

递归和分治

二分查找(基于递归分治)

        
/*问题：给定一个长度为n的有序数组nums，其中所有元素都是唯一，查找元素target*/
#include< stdio.h >//基于分治递归的二分查找
int dfs(int[], int, int, int);
void main() {
	int a[] = {1, 2, 3, 4, 5, 6, 7, 8};//定义一个数组
	int b = dfs(a, 2, 0, sizeof(a)/sizeof(a[0])-1);
	//第四个参数是计算数组大小，因为sizeof返回的是存储大小，所以总大小/一个大小就是个数
	printf("这个元素是数组中的第%d个\n",b+1);
	return 0;
}
int dfs(int a[], int target, int i, int j)
{
	if (i > j)
		return -1;//如果左指针大于右指针说明查找失败，因为二分都分劈叉了，你说呢
	int m = (i + j) / 2;//依据我们理论来讲，m中间指针是指向首尾/2，也就是一半，向下取整
	if (target > a[m])//如果目标比中间大，我们将目光看向大的那一半
		return dfs(a, target, m + 1, j);//进入大的一半
	else if (target < a[m])//如果目标比中间小，将目光看向小的那一半
		return dfs(a, target, i, m - 1);//进入小的一半
	else
		return m;//如果此时首尾指针指向一个元素，那么就是我们要找的
}
/*分治的体现，使用递归，每次割分，不断将问题化为一个个小问题，小问题之间无联系*/

动态规划

代码示例


/*动态规划*/
/*
-----------------------------------------
背包问题
打家劫舍
股票问题
子序列问题
-----------------------------------------
dp[i][j]
1.dp数组以及下标含义
2.递推公式
3.dp数组如何初始化
4.遍历顺序
5.打印数组
-----------------------------------------
*/
/*--------------------------------------------*/
/*--------------------------------------------*/
/*斐波那契数列*/
//1 1 2 3 5 8 13 ...
//1.确定dp数组，dp[i]，代表第i个斐波那契数
//2.确定递推公式，dp[i] = dp[i-1]+dp[i-2]
//3.初始化，dp[0]=1,dp[1]=1
//4.遍历顺序，从前向后遍历
//5.打印dp数组
int dp[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n; i++)
{
	dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
/*--------------------------------------------*/
/*--------------------------------------------*/
/*爬楼梯*/
//1.确定dp数组，dp[i],代表达到第i阶有dp[i]中方法
//2.确定递归公式，dp[i] = dp[i-1]+dp[i-2]
//3.初始化，dp[0]从含义上是没营养的，到达第0阶有1种方法。所以直接dp[1]=1,dp[2]=2
//4.遍历，从前向后
//5.打印dp
/*--------------------------------------------*/
/*--------------------------------------------*/
/*使用最小花费爬楼梯*/
/*
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。
-------------------------------------
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
--------------------------------------
1.花费的力气是当前所在的台阶
2.顶楼是数组大小+1，也就是最后一个力气再后一个
*/
//1.确定dp数组，dp[i]代表到达i位置所需要最小花费为dp[i]
//2.确定递推公式，dp[i]是由dp[i-1]或者dp[i-2]得到
//		dp[i] = dp[i-1]+cost[i-1]到i处需要i-1处需要i-1处的力气
//		dp[i] = dp[i-2]+cost[i-2]到i处需要i-2处需要i-2处的力气
//		两个都能去第i处，但是要求最小花费，所以选择两者中较小者
//		所以就是dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
//3.初始化，dp[2]由dp[1]和dp[0]决定，所以只需要初始化dp[1]和dp[0]
//		我们站在1和0处是不需要花费的，只有跳上去才需要
//		所以dp[0] = 0;dp[1] = 0;
//4.遍历，从前向后
//5.打印dp
int minCostClimbingStairs(int* cost, int costSize) {
	int dp[costSize + 1];//初始化数组
	dp[0] = dp[1] = 0;//初始化，第一个和第二个
	for (int i = 2; i <= costSize; i++) {
		dp[i] = fmin(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);//选每一步最小的跳
	}
	return dp[costSize];//返回dp数组，最后一个就是最小花费的总力气
}
/*--------------------------------------------*/
/*--------------------------------------------*/

贪心算法

代码示例


/*贪心算法*/
/*
本质：找到每个阶段的局部最优
局部最优推出全局最优
*/
//贪心没有套路，基本思路就是局部最优、
/*饼干问题*/
//孩子需要的饼干：1，2，7，10
//饼干：1，3，5，9
//思路，局部：每次用最大的饼干匹配胃口最大的孩子
//1.选最大饼干9，匹配尽量胃口大的7
//2.再选最大饼干5，匹配胃口大的2
//3.再选最大饼干3，匹配胃口大的1
sort(胃口);//对胃口排序
sort(饼干);//对饼干排序
int 成功投喂小孩数 = 0;
int index = 饼干.size-1;
for (int i = 胃口.size-1; i >= 0; i--)//胃口从大到小进行遍历
{
	while (index >= 0 && 饼干[index] >= 胃口[i])//饼干从大到小进行遍历匹配
	{
		成功投喂小孩数++;
		index--;
	}
}

回溯和其他算法

基本认知


/*回溯算法*/
/*
有递归就会有回溯
回溯算法：纯暴力搜索
可以解决：
1.组合问题：从一堆东西中找出数量为n的组合（无序）
2.切割问题：给一个字符串，问如何切割保证子串都是回文字串
3.子集问题：给一堆东西，列出所有的子集
4.排列问题：从一堆东西中找出数量为n的排列，排序不同顺序即便相同东西也是不同排列
5.棋盘问题：N皇后，解数独
-----------------------------------------------------
回溯法针对任何问题，都可以抽象为一个树形问题
一般来说回溯法的递归函数无返回值
函数取名为（模板）
*/
void backtracking(参数)
{
	if (停止条件)
	{
		收集结果;//叶子节点来收集结果
		return ;
	}
	for (集合元素)
	{
		处理节点;
		递归函数;
		回溯操作;
	}
}
/*
举个例子，集合1234
组合问题
取1 取2
12
此时回溯，也就是回溯到2还没有进来
1
然后加入3
13
再回溯，也就是回溯到3还没有加进来
1
然后加入4
14
以此类推
*/
-----------------------------------------
/*组合问题*/
/*
给定两个整数n和k，返回范围[1,n]中所有可能的k个数的组合
*/
int** combine(int n, int k, int* returnSize, int** returnColumnSizes)
{
	for (int i = 0; i < size; i++)
	{
		for (int j = i + 1; j < size; j++)
		{
			for (int a1 = j + 1; a1 < size; a1++)
			{
				for (int a2 = a1 + 1; a2 < size; a2++)
				{
					for (int a3 = a2 + 1; a3 < size; a3++)
					{
						for (int a4 = a3 + 1; a4 < size; a4++)
						{
							for (int a5 = a4 + 1; a5 < size; a5++)
							{
								for (int a6 = a5 + 1; a6 < size; a6++)
								{
									for (int a7 = a6 + 1; a7 < size; a7++)
									{
										.......
											直到
											for (int ak = a(k - 1) - 1; ak < size; ak++)
											{
												return k个数的组合
											}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}
/*
是的，没看错，这种用for循环死磕，还能加工资，毕竟代码行就是工资
今天你给我从0-10000000000000000找出999999999999个
你就得写999999999999for循环，牛逼
所以回溯法就来了，它可以控制递归来达到控制for循环的次数
*/
class Solution {
private:
	vector< vector< int>> result; // 存放符合条件结果的集合
	vector< int> path; // 用来存放符合条件结果
	void backtracking(int n, int k, int startIndex) {
		if (path.size() == k) {//如果到叶子，也就是存了k个以后结束
			result.push_back(path);//将结果存储到二维数组中
			return;
		}
		for (int i = startIndex; i <= n; i++) {
			path.push_back(i); // 处理节点，也就是加入节点
			backtracking(n, k, i + 1); // 递归
			path.pop_back(); // 回溯，撤销处理的节点
		}
	}
public:
	vector< vector < int>> combine(int n, int k) {
		result.clear(); // 可以不写
		path.clear();   // 可以不写
		backtracking(n, k, 1);
		return result;
	}
};
/*
for循环  保证 从左到右  单向遍历
递归  保证 从上到下
结束条件 保证 从上到下有尽头
撤销操作  保证 能回溯，也就是保证了能从下到上
*/
--------------------------------------------------------------------------
--------------------------------------------------------------------------
--------------------------------------------------------------------------
--------------------------------------------------------------------------

复原IP地址

数据结构经典题

代码示例

1.以下属于逻辑结构的是:
A. 顺序表
B. 哈希表
C. 有序表
D. 单链表
答案: C                  
其实很不好理解，毕竟你的脑子不够聪明。顺序表顺序存储。哈希表散列存储。单链表链式存储。
怎么？有序表，有序存储是吧，有序是指元素之间有序，不是说地址有序，所以只要涉及元素的关系就是逻辑

2.以下关于数据结构的说法中正确的是:
A.数据的逻辑结构独立于其存储结构
B.数据的存储结构独立于其逻辑结构
C.数据的逻辑结构唯一决定其存储结构
D.数据结构仅由其逻辑结构和存储结构决定
答案: A         &n

    bsp;        
这道题主要的任务就是说，逻辑结构其实是人先想出来，然后用计算机实现
所以说逻辑结构独立存储结构
但是存储结构是要靠逻辑结构作为支撑的
数据结构的三要素：逻辑、存储、操作

3.若长度为n的非控股线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，则i的合法值是:
A.1≤i≤n
B.1≤i≤n+1
C.0≤i≤n-1
D.0≤i≤n
答案: B                  
我知道你可能会选C，第i个位置插入元素，你给我在第0个位置插入试试看？又不是数组下标，哦，喝杯咖啡就是程序员了？
线性表的顺序存储，就是数组，动态分配，可以在最后追加一个元素的啊，反正重新创建数据，重新整体搬迁完事了

4.栈和队列具有相同的:
A.抽象数据类型
B.逻辑结构
C.存储结构
D.运算
答案: B                  
栈和队列都是线性结构，是逻辑结构，是元素之间是有关系的，你前我后

5.若一个栈的输入序列为1，2，3...n,输出序列的第一个元素是n，则第i个输出元素是:
A.不确定
B.n-i
C.n-i-1
D.n-i+1
答案: D                  
这题我选过B，以为第一个输出n，那第二个就是n-1,第i个不就是n-i了？
哦哦哦，不对是我太蠢了，第i个应该是n-i+1,害，老了

5.最适合用作链队的链表是:
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
答案: B                  
队列是要一头进行删除一头进行增加的，C、D不合适，因为只有队首，队尾进行操作是要遍历的
A为什么不行？A和B差距就是循环两个字，看队列的性质，循环不循环是无所谓的，因为我们只通过两个指针的跳变
完成我们首末的工作，还不清楚去看队列的相关知识

6.已知循环队列存储在一维数组A[0...n-1]中，且队列非空时，front和rear分别指向队头元素和队尾元素。
    若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是:
A.0，0
B.0，n-1
C.n-1,0
D.n-1,n-1
答案: B                  
这道题的文本本身就是一个坎，进队操作就是rear=(rear+1)%MAXSIZE
好，现在rear尾指针指向哪里？包是0啊
我们在队列讲解中说的《约定空出一个不存储，也就是队尾+1就是队头的时候就是满,注意队尾指向的不是最后一个元素而是最后一个元素的下一个空位置》
是指一种特殊的情况
n%n=0,也就是(n-1+1)%n=0
所以rear就是n-1，front不动，那就是0

7.设二叉树有2n个结点，且m < n,则不可能存在的结点是:
A.n个度为0
B.2m个度为0
C.2m个度为1
D.2m个度为2
答案: C                  
这道题最好的办法就是判断奇偶性，我们知道n0=n2+1
而且2n=n0+n1+n2，代入结合一下
2n=2n2+n1+1
n1=2n-2n2-1
n1=2(n-n2)-1
说明n1是奇数，所以C不对


8.高度为h的完全二叉树最少有多少个结点:
A. $2^{h}$ 
B. $2^{h} + 1$ 
C. $2^{h - 1}$ 
D. $2^{h} - 1$ 
答案: C                  
想象一下，如果我们的第h层只有一个结点，是不是就是最少的情况
那前面的h-1层就是满的，我们用等比数列算 $\frac{1 - 2^{h - 1}}{1 - 2} = 2^{h - 1} - 1$ 
然后我们第h层有一个，加上这一个
 $2^{h - 1} - 1 + 1 = 2^{h - 1}$ 

9.已知一棵完全二叉树的第6层(根为第一层)有8个叶结点，则该完全二叉树的结点个数最多是:
A.39
B.52
C.111
D.119
答案: C                  
想象一下完全二叉树第6层如果有叶结点，那么就是第七层没有满，也有可能是第六层就是这几个叶子结点了
我们要算最多，那不就是存在第七层的嘛
我们前6层都满，算一下 $\frac{1 - 2^{6}}{1 - 2} = 63$ 
我们第七层什么情况？我们第6层有8个叶子，也就是第7层少了16个结点，我们把第七层算一下减去16就行
第七层的结点用等比第n项公式
 $2^{6} = 64, 64 - 16 = 48, 48 + 63 = 111$ 

10.在二叉树中有两个结点m和n，若m是n的祖先，则使用什么可以找到从m到n的路径:
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
答案: C                  
二叉树的代码实现中，是递归的，递归就是说先深入再回退，那么就是左右根可以不断的输入从n到m的路径
相当于可以找到从m到n的路径

11.线索二叉树是一种什么结构:
A.逻辑
B.逻辑和存储
C.物理
D.线性
答案: C                  
烦死了，这种题目

12.二叉树在线索化后，仍不能有效求解的问题是:
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前驱
D.后序线索二叉树中求后序后继
答案: D                  
根左右，右的线索前驱是左，要找右的前驱根，显然不太行

13.在有n个叶结点的哈夫曼树中，非叶结点的总数是:
A.n-1
B.n
C.2n-1
D.2n
答案: A                  
哈夫曼树中只有度为0和2的结点，根据度为0和度为2的公式
n0=n2+1
n2=n0-1

14.对n个互不相同的符号进行哈夫曼编码，若生成的哈夫曼树共有115个结点，则n的值是:
A.56
B.57
C.58
D.60
答案: C                  
n个符号共新建了n-1个结点，2n-1=115
2n=116
n=58

15.若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是:
A.强连通图
B.连通图
C.有回路
D.一棵树
答案: B                  
A是有向图的东西
B对
C有回路不一定是连通图，因为可能是单独一个顶点，其他剩下的有回路
D一棵树是不可能有环的，而这个连通图是可能有的

16.一个28条边的非连通无向图至少有多少个顶点:
A.7
B.8
C.9
D.10
答案: C
                             
我们知道边数和顶点的关系，也就是 $e = \frac{n (n - 1)}{2}$ 
以上的完全图的边对应点的关系，我们如果再增加一个点，这个点就是单独的点，也就是构成非连通图
 $28 = \frac{n (n - 1)}{2}$ 
算出n=8，此时再加一个顶点就是非连通
所有就是9

17.无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有多少个顶点:
A.11
B.12
C.15
D.16
答案: D
                             
分析题目，只有度4度3度2，也就是总度=n4+n3+n2
我们又知道无向图度与边的关系，就是总度数=边数*2
23*2=n4+n3+n2
46=20+12+n2
n2=14
那度为2的顶点个数就是12/2=7
所有总的顶点个数=7+4+5=16

18.在有n个顶点的有向图中，顶点的度最大可达:
A.n
B.n-1
C.2n
D.2n-2
答案: D
                             
有向图的度=入度+出度
我们看题目，问的是一个顶点的度
这个顶点可以与n-1个有来往
来是n-1
往是n-1
总是2n-2

19.具有6个顶点的无向图，当有多少条边时能确保是一个连通图:
A.8
B.9
C.10
D.11
答案: D
                             
考虑我们的知识点，n个顶点的完全图对应有多少条边？
 $e = \frac{n (n - 1)}{2}$ 
假如5个顶点组成是一个完全图，现在加入一个顶点就是非连通，但是再加入一条边就是连通的了，因为完全图里面加不了边了
 $10 = \frac{5 (5 - 1)}{2}$ 
5个顶点完全图需要10条边，再加入一条不就是让6个顶点连通的了，所以就是11

20.若具有n个顶点的图是一个环，则它有多少棵生成树:
A.n方
B.n
C.n-1
D.1
答案: B
                             
n个顶点是一个环，环去掉任意一条边都是一个生成树
所以可以有n种

21.若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有多少棵树:
A.n
B.e
C.n-e
D.1
答案: C
                             
对于任意一棵树而言，e=n-1 ,就是边数等于顶点数-1
假设有x棵数
那么就是e=(n1-1)+(n2-1)+...+(nx-1)
e=n-x
x=n-e

22.n个顶点的无向图的邻接表最多有多少个边表结点:
A.n方
B.n(n-1)
C.n(n+1)
D.[n(n-1)]/2
答案: B
                             
对于一个具有n 个顶点的无向图：
每个顶点都至少有一个边表节点，即使它不与任何其他顶点相连（这种情况下，该顶点的链表只有一个节点，代表一个孤立顶点）。
在无向图中，每条边在邻接表中会出现两次，因为无向图的边是双向的。因此，如果顶点
A与顶点B相连，那么在顶点A的链表中会有一个边表节点指向B，在顶点B的链表中也会有一个边表节点指向A。
因此，对于一个具有n个顶点的无向图：最多有n个顶点，每个顶点都与其他个顶点相连(n-1)（除了它自己）。
因此，最多有n×(n−1) 个边表节点，因为每条边贡献了两个边表节点（每个顶点的链表中各一个）。
但是，由于每条边被计算了两次（一次在每个顶点的链表中），实际的边数是边表节点数的一半，即边数=[n×(n−1)]/2

23.在有向图的邻接表存储结构中，顶点v在边表中出现的次数是:
A.顶点v的度
B.顶点v的出度
C.顶点v的入度
D.依附于顶点v的边数
答案: C
                             
邻接表有向图，连接的一定是向有路径的方向，这个点被上一个点过来，一定是入度

24.设有向图G=(V，E)，顶点集V={V0,V1,V2,V3},边集={< V0 , V1>,< V0,V2 >,< V0,V3 >,< V1,V3 >}若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是:
A.2
B.3
C.4
D.5
答案: D
                             
嗯，我知道你可能会有疑问，我想告诉你的是，你设想到的所有可能是存在的，分岔路口是包括的。

只有缩短所有关键路径上的至少一个关键活动可以缩短整个工程工期

25.用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树:
A.相同
B.不相同
C.可能相同、可能不同
D.无法比较
答案: C
当权值有一样的时候，普利姆和克鲁斯卡尔是有可能构造出不同的最小生成树
为什么我突然想到权力的游戏，还有戒指

26.为提高查找效率，对65025个元素的有序顺序表建立索引结构，在最好情况下查找到表中已有元素最多需要执行多少次2关键字比较:
A.10
B.14
C.16
D.21
答案: C
                             
首先最好是建立的索引表求开方 $\sqrt{65025} = 255$ 
也就是说索引表有255个，索引块中也有255，分别采用折半查找
 $2 l o g_{2} (255 + 1) = 16$ 

27.含有n个非叶结点的m阶B树中至少包含多少个关键字:
A.n(m+1)
B.n
C.n([m/2]-1)
D.(n-1)([m/2]-1)+1
答案: D
                             
至少，根至少一个关键字
其他结点至少[m/2]-1个关键字
所以就是(n-1)([m/2]-1)+1个

28.已知一棵五阶B树中共有53个关键字，则树的最大高度为，最小高度为:
A.2
B.3
C.4
D.5
答案: C B
                             
树的高度要最高，也就是分支最少，每一个结点的关键字最少
套用等比数列求和公式 $\frac{1 - 3^{h}}{1 - 3} = \frac{53}{2}$ 
树的高度要求最低，也就是每一个结点关键字最多，分支最多
套用等比数列公式就是 $\frac{1 - 5^{h}}{1 - 5} = \frac{53}{4}$ 
分别得出4和3

29.依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根结点中包含的关键字是:
A.8
B.6，9
C.8，13
D.9，12
答案: B
                             
我们插入
            5 6 9 13
这个时候超过了元素可以容忍的最大个数，我们从m/2也就是4/2第二个分开，第二个成根，其他分为左右
            6
       5         9 13
8入
            6
       5         8 9 13
2入
              | 6 |
     |2  5|           |8 9 13|
12入
              | 6 |
     |2  5|           |8 9 12 13|
超了，我们还是以9为分割
               |6 9|
     |2  5|     |8|     |12 13|
再加入15
               |6 9|
     |2  5|     |8|     |12 13 15|
所以根结点就是6 9

30.现有长度为11且初始为空的散列表HT，散列函数是H(Key)=Key%7,采用线性探测法解决冲突，将关键字序列87，40，30，6，11，22，98，20依次插入HT后，HT查找失败的平均查找长度为:
A.4
B.5.25
C.6
D.6.29
答案: C
                             
我们把数装进去
散列地址    |0 | 1 |2 | 3 | 4 | 5 | 6 | 7 | 8 ||||
关键字     |98 |22 |30|87| 11 |40 | 6 |20|
我们查找第一个失败肯定是从0到7然后再到8然后失败，也就是9次
第二个从1到7再到8然后失败，也就是8次
以此类推
注意什么时候停止，肯定是到6，3次的时候
因为%7是不可能出现余数为7的
(9+8+7+6+5+4+3)/7=6

31.对n个关键字进行快速排序，最大递归深度为，最小递归深度为:
A.1
B.n
C.log2n
D.nlog2n
答案: B C
                             
最大深度就是一条路到黑，那就是n，最小如果递归化为一棵树，那就是树高

32.设数组a[1...50,1...80]的基地址是2000，每个元素占两个存储单元，若以行序为主序顺序存储，则元素a[45][68]的存储地址为多少？若以列序为主序顺序存储，则元素a[45][68]的地址是多少:
答案: 9174  8788
这里我讲第一个概念，行序为主就是先把第一行存完再到下一行
列序为主就是先把第一列存完，再存第二列
还有一点就是，这里的数组是从1开始，区别于0开始的是，存储大小一样，但是a[5]在1看来是第4个，在0看来是第5个
这里a[45][68]是从1开始，也就是行有44行存满，第45行有67个
44行×每一行的个数80=3520
3520+67=3587
数组的总个数为3587
然后×上每一个元素的大小3587×2=7174
再加上首地址2000=9174
--------------------------------------
以列序为主
也就是a[45][68]中，67列是满的，为什么是67，因为在1看来它是，如果在0开来就是68了
67列满了，第68列只存到第44行，也就是第68列从上往下只有44个元素
67×50=3350，为什么是乘50？因为数组行数大小是1...50，也就是最大50行，那不就是一列从上到下的个数
3350+44=3394
3394×2=6788
再加上首地址2000=8788
==================================================
好，我们总结一下，这里比较误导的区域
从0开始，和从1开始
从0开始的a[5][5]
你自己读读，a[5][5]是第几行第几列
当然是第6行第6列啊，难不成a[0][3]是第0行吗？
这里是从0开始
从1开始呢？a[5][5]。当然是第5行第5列啊
它没有a[0][x],或者a[x][0]这种，更不用说a[0][0]
我们上面计算的时候，假设行优先，为什么a[45][68]，是计算44行完整大小，再加上67
因为a[45][68]是指第45行第68列的元素，也就是前面44行地址都要计算，45行的67列地址也要算
如果是从0开始a[45][68]是指第46行第69个元素，所以要计算前45行地址，再加上46行的68个元素地址
还是不了解的话是我的错，请记住数组下标只能到比定义-1
比如a[5][5]，你在调用的时候最多调用a[4][4],a[5][5]是越界的
所以从1开始和从0开始当然少一个

最大深度就是一条路到黑，那就是n，最小如果递归化为一棵树，那就是树高

33.具有n个关键字的m阶b-树，有多少个叶子节点（查找不成功的节点）
n+1个
b-树就是b树，如果不清楚b树概念，点击目录，或者翻上去，找到b树复习
我也挺迷的，我甚至第一次做这题的时候一点思路都没
我还乱套公式，比如什么n(n-1)/2这种
给你讲个东西
下面是
            A
       B         C
   D       E   F      G
请问有几个查找不成功的节点
其实你把这个隆起的树，看成平的就好了，你不会想到胸了吧？
D  B  E  A  F  C   G
你看，这样虽然反人类，但是b树的本意就是如此
  D     B    E    A    F   C     G
1    2    3    4    5    6    7     8
你看7个节点一共有8个查找不成功的
还不明白？
2      4      6      8       10
让你找一个数，你可能会经历哪些失败？
1.比2小
2.比2大比4小
3.比4大比6小
4.比6大比8小
5.比5大比10小
6.比10大
你看5个点，6个可能结果，也就是叶子节点
注意在b树中叶子节点是指外部节点也就是内部叶子节点的下一层虚空的，满的
            
34.若平衡二叉树的高度为6，且所有非叶子节点的平衡因子均为1，则该平衡二叉树的节点总数为
这题很有意思，看似很难，其实对于你来讲确实难，因为你如果忘记了平衡二叉树是什么
也不知道平衡因子怎么算的话，建议你去上边，查看平衡二叉树定义，以及平衡因子计算方法
不需要看多，就看这两个，别看着看着，点开blbl，结果看美女去了☝🏻🤣
言归正传，不是阿甘正传
假设你知道平衡因子计算，就是这个点的左子树和右子树高度差，哈哈哈哈哈
其实你不上去看，继续看我也会告诉你，哎，我老是忍不住啊啊啊啊啊啊啊
       A
   B       C
D
这样的二叉树中的A的平衡因子是多少？是1，怎么来的，2-1=1（你不会看不懂个吧？🐒🫤）
看不懂，我告诉你，A的左子树是B和D，两个，A的右子树是C一个，二个减去一个就是一个，2-1=1，别问我为什么2-1=1，这涉及到哲学
♂，别想多了，不是那个哲学，是正经哲学
好，然后我们构造层次为6的并且非叶子的平衡因子为1的二叉树
一步步来
                                           A
                                       B
这样满足条件吗？满足，但是高度为2，还差
                                           A
                                       B
                                    C
这样呢？不行啦，哪里不行？不是那里，是A，A没有右孩子，但是左孩子2个，2-0=2，多了，怎么办？
补呗
                                           A
                                       B       D
                                    C
好，现在满足了，当也才3层啊，继续，我知道你看的不耐烦了（你他妈一股脑搞到6层会死吗？傻逼），好好好，我搞😭😭
                                           A
                                       B       D
                                    C
                                 E
                              F
                          G
现在是有6层了，但是平衡因子严重多处不符，没事，考研嘛，总是把那些耐不住性子的人剔除，咱耐心，穿针引线一步步来
我们看A肯定是最严重的，左5-右1=4，也就是右边要加3个
怎么加是关键
                                           A
                                       B       D
                                    C        H
                                 E
                              F
                          G
我现在加了H，刚好让D成为平衡因子为1的节点，因为此时D不是叶子了，那我们下一个加哪里？既然我们想要的是右子树的层数，肯定是接着H下面
                                           A
                                       B       D
                                    C        H
                                 E         I
                              F
                          G
好，现在I放进去，但是D的平衡因子变成2了啊，怎么办？补呗，你还想不劳而获？我也想
                                           A
                                       B       D
                                    C        H   J
                                 E         I
                              F
                          G
ok，现在D的平衡因子变1了，接着我们的补层数
                                           A
                                       B       D
                                    C        H   J
                                 E         I
                              F         K
                          G
皆大欢喜，A的右子树层数为4了，刚好让A的平衡因子为1，但是有人喜就有人忧
是谁在哭泣啊？当然是我们的D公主啦，D的左树比右树多2个，怎么办？补啊
                                           A
                                       B       D
                                    C        H   J
                                 E         I    L
                              F         K
                          G
补的是J的左子树L，现在H哭了，竟然没人关心他，他也是左2右0啊啊啊啊
                                           A
                                       B       D
                                    C        H   J
                                 E         I  M L
                              F         K
                          G
至此右子树施工完毕，按照上面的方法补全左子树
                                               A
                                       B                D
                                    C     N         H       J
                                 E   R   O   P    I   M   L
                              F    S  U T       K
                          G
大功告成！数下来刚好20个，over
没事，我知道自己画了一团屎🫤🫤
            
35.下面给出的排序中，不稳定的排序算法是
A.插入排序
B.冒泡排序
C.二路归并
D.堆
答案：D
别急，别骂街，这麽简单的题目，我拿出来自然是为了水字数
A的插入排序，回想一下，插入有直接插入和希尔以及折半插入
直接插入就是假定第一个是排好的，然后依次从后面取一个放到已经排好的序列中，从排好的序列中从后往前比较大小，实现插入正确位置
也就是说，这种排序是稳定的，两个关键字相同的，一个前一个后，不会说经过排序后面跑前面去
折半，和直接插入的区别在于每次也是从后面选一个加入已经排好的序列，但是不是傻瓜一样从后往前依次比较
采用折半查找的方式，找到自己的为然后直接插进去，讲究快(还行🫤)准(不准就不学你了😐)狠(这个字不是狼)
希尔就是增量的方式，比如每5个进行一组排序然后交换(这里不属于交换排序是因为，这个是夸几个进行交换，交换是连着的两个交换是交换排序)
希尔每5个进行排，就可能导致相同的被打乱（还不清楚去看上面的希尔排序介绍）
冒泡排序就是交换排序，因为从第一个开始每次比较相邻两个大小，一趟可以选出一个最大或者最小的
冒泡是因为连续比较所以稳定（不是连续所以稳定，是因为相同关键字在排序过后前后位置不变才稳定）
二路归并，重要在于归并两个字，不知道你听说过分治法没，没有算了，如果听过，其实就是分-治哈哈哈哈，我没有说废话！
归并的意思就是两个合并成一个（这里是指二路），具体点
{1，5}和{2，9}怎么合并？
分别比较两个数组的第一个，始终是第一个
1和2比，1小放进我们的新数组中，新数组开辟的大小由两个数组大小的和觉得
{1，}
现在变成了{，5}和{2，9}
比较5和2，2小，2放进去
{1，2，}
比较{，5}和{，9}的5和9
5小，5放
{1，2，5，}，由于第一个数组没有数字了，依次把第二个数组放进去就行，因为两个数组，自己本身内部是有序的
{1，2，5，9}，归并思路就是如此，所以归并也不会改变相同关键字前后位置。
            
36.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列是否存在？
答案是：存在
拓扑是每次选择入度为0的点，删除它以及它的边
邻接矩阵主对角线下全为0意味着什么？
 $[\begin{matrix} 1 & 1 & 1 & 2 & 3 & 1 \\ 0 & 1 & 2 & 3 & 4 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]$ 
意味着高节点到底节点没有入度，低到高可能有，还不止一个
我们本来就是从低到高，依次选入度为0，并且删除的，刚好符合拓扑的想法

37.设H(x)是一个哈希函数，有K个不同关键字,满足H(x1)=H(x2)=...=H(xk)若采用线性探测法将这k个关键字存入哈希表中，至少要探测多少次？
答案：k(k-1)/2
这个问题，值得深思，初看，你可能会觉得，啊，最少，那不就是第一次放入就行了？
都没有冲突，就是K次嘛
注意审题，H(x1)=H(x2)=...=H(xk)说明，每一个关键字的哈希值都一样
也就是说，都是冲突的
第一个放，需要0次探测，以为直接放嘛
第二个放，需要1次，第三次需要2次
第k个放，需要k-1次
S=项数（首项+末项）/2
项数k
首项0
末尾k-1
S=k(k-1)/2
你是不是好奇第一个为什么是0，以为线性探测是在冲突发生的时候使用的哟，怎么还没有捡芝麻就丢了西瓜
也就是第二个才冲突，所以第二个是1
 
38.(多选)将森林转换成对应的二叉树，若在二叉树中，节点u是节点v的父节点的父节点，则在原来的森林中，u和v可能具有的关系是
A.父子关系
B.兄弟关系
C.u的父节点与v的父节点是兄弟关系
答案：AB
还记得左孩右兄吗？森林、树，二叉树的转换规则
题目说u是v的双亲的双亲
一共的可能性就是
                u
             X
               V
            -------
                 u
              x
           v
            -------
            u
               x
                  v
            --------
            u
               x
            v
            --------
一共就这四种
第一个就是左孩然后右兄，也就是v是u的孩子节点，v与x是兄弟节点
第二个是左孩然后再左孩，也就是v是x的孩子，u是x的孩子，u就是v的双亲的双亲了
第三个u和x和v之间是兄弟关系
第四个v是u的兄弟x的孩子，也就是v的双亲x的兄弟是u
所以就选A和B
            
39.设顺序存储的某线性表共有123个元素，按分块查找的要求分为3块。(想吃蛋糕了😰)索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序存储查找方法，则在等概率的情况下，分块查找的平均查找长度为
A.21
B.23
C.41
D.62
答案：B
分块，索引这些关键词没有触发你吗？
123分3块，一块就是41，也就是我们一开始就要从3个选一个
这可是顺序查找，什么意思？【A】【B】【C】【D】【E】【F】
第一次查找，走到A，需要查1次
第二次查找，走到B，需要查找2次
第三次查找，走到C，需要查找3次
。。。
是的，顺序查找就是这样
好，我们第一轮分3块，也就是说
 $\frac{3 (3 + 1)}{2} \times \frac{1}{3}$ 
因为等分3块，每一块不就是还要除以3嘛
好，第一轮我们算出来了，第二轮就是在41个里面选，为什么是41？因为第一轮已经确定了，你的数在三块中的哪一块了
还是顺序查找
 $\frac{41 (41 + 1)}{2} \times \frac{1}{41} = 21$ 
所以我们两轮的平均查找都算完了，我们加起来就行
21+2=23
            
40. $\begin{aligned} 40. 将一个 A [1. . .100, 1. . .100] 的三对角矩阵，按行优先存入一维数组 B [1. . .298] 中， \\ A 中元素 A_{66, 65} (下标 66, 65) 在数组 B 中的位置 K 为 \end{aligned}$ 
A.198
B.195
C.197
答案：B
三对角矩阵，你学过线性代数啦？就是三线行列式
这里用一个公式就行
 $3 (i - 1) - 1 \leq K < 3 i - 1$ 
如果是以行优先，i就是行数，如果是列优先，i就是列数
这里是行，i就是行数66
 $3 (66 - 1) \leq K < 3 \times 66 - 1$ 
 $194 \leq K < 197$ 
然后对比选项，就是195了
            
算法原地工作是需要少量的辅助空间的，不是不需要。同一个算法，实现语言越高不一定效率越低。
            
AOE网（Activity On Edge Network）用边表示活动，用顶点表示事件（活动的完成）。边是带权的，表示活动需要的时间。
             
41.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0 右孩子的平衡因子为1，则应作（  ）型调整以使其平衡。
A、LL    B、LR    C、RL    D、RR
答案是C
说实话我在拿到这道题的实话信心满满，因为我已经通过上面34题，把平衡二叉树弄的死去活来的，清清爽爽的
我就不信有什么平衡二叉树难题，于是我分析题目，找啊找
切，不就A的左是0，右是1，不对啊，卧槽，我大概能够猜到是_R，至于前面的
是什么呢？我甚至还想知道A是整个树中的左还是右
唉，还是榆木脑袋，A的左平衡是0，右平衡是1，说明A的平衡因子就是0-1=-1啊
然后右子树上平衡因子是1，也就是右子树的左-右=1，也就是右子树的左子树比右子树高一棵
然后总结就是-1，1，也就是右左=RL
为什么-1是右，正数1是左？
我真的要骂你，你比我还傻瓜，平衡因子是左子树高度-右子树高度
是负数不就是右子树多

42.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（   ）。
A. 13
B. 33
C. 18
D. 40
答案是：B
你不会第一步就琢磨半天，觉得，啊，这四个选项怎么都这么小啊，啊呀，算我求你了
别自己屁股坐在凳子上，一拍脑袋就叽里呱啦的想
看看题目行不行？不是求整个数组的地址了啊，是对称矩阵，对称矩阵是怎么存的，你心里面没有数吗？
压缩啊啊啊
上下三角啊，行优先啊，想想线性代数啊
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
存下三角，你告诉我a85是谁？啊呀，同学们啊，我都给你标、标、标出来啦，这你要再不知道，就是逼我跳楼啊
我恨你，我恨你啊啊啊，以上是颉斌斌老师的话语
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
1  2  3  4  5  6  7  8  9  10
存的就是这个，行优先就说1 12 123 1234这样啊啊啊啊
你就数啊
33个啊
不是你还真的一个个数啊，要是1000×1000的你怎么数啊
没看到每行都是一个等差数列吗
a85就说前面7行都是满的，再加上第8行的5个就行了啊
S = ((1+7)*7)/2 +5= 28 + 5 = 33
什么？看不懂？等差数列求和公式不会？你他喵的
    

43.在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（   ）邻接点。
A. 入边 B. 出边 C. 入边和出边    D. 不是出边也不是入边
答案是A
我真的懵了，拿到题目的时候，我就知道个邻接表，虽然我不知道怎么想的，我对逆邻接表有了解
但是我真的不知道怎么思考了
甚至邻接表都是迷迷糊糊的
看了答案才知道，存储图的方式啊，邻接矩阵和邻接表
啊啊 等等，我现在才恍然大悟，邻接矩阵就是顺序存储啊
邻接表是链式存储，一切都离不开链式和顺序存储啊
卧槽，get it。
邻接表每一个节点后面连接的是它的出边
逆邻接表不就是入边了

44.设对n(n>1)个元素的线性表的运算只有四种：（1）删除第一个元素；（2）删除最后一个元素；（3）在第一个元素之前插入新元素；（4）在最后一个元素之后插入新元素，则最好使用（ ）。
A、只有尾结点指针没有头结点指针的循环单链表
B、只有尾结点指针没有头结点指针的非循环双链表
C、只有头结点指针没有尾结点指针的循环双链表
D、既有头结点指针又有尾结点指针的循环单链表
答案是C
这种题目是不是一眼看上去很讨厌，甚至厌恶🤢
其实就是将4个操作的时间复杂度摆一起比较谁的最优就行
看A，只有尾指针，没有头结点的循环单链表
（1）删除第一个元素 因为循环嘛，尾指针的下一个就是首元素，所以o(1)
（2）删除最后一个元素；你不会因为尾指针就是指向最后一个所以直接删除就是O（1）吧？
nononono，想想看，这是个循环的链表，最后一个删除了，尾指针指到哪里？
倒数第二个了，但是是单链表啊，没有指向前的，所以你只能先遍历到倒是第二个
通过让倒数第二个的next指向尾指针的next（第一个节点），变相的把最后一个节点删除
所以时间复杂度是O（n）
（3）在第一个元素之前插入新元素：这很好办，因为是循环所以尾指针的下一个就是第一个节点
直接让新节点next=尾的next，再把尾的next=新节点，所以是O（1）
（4）在最后一个元素之后插入新元素，O（1）
A：O(1) O(n) O(1) O(1)
依次排出A B C D 然后选最优
剩下的选项我就不讲了
            
45.有 ABCDEF 六个城市，每一个城市都和其他所有城市直接相连，问从 A——B 有多少种连接方式，路径不允许经过某个城市两次
A. 78
B. 65
C. 43
D. 以上都错
答案：B
是不是懵了，我也是，我还挣扎了一下，还想用乱炖公式，什么求和公式
什么的
其实是这样的，6个城市，A-B，也就是说中间城市最多4个
不断增加中间城市的排列就是答案了
 $A_{4}^{0} + A_{4}^{1} + A_{4}^{2} + A_{4}^{3} + A_{4}^{4}$ 
不知道排列怎么算？其实就是看下标和上标，下标决定从几开始乘，上表决定乘几个数，有特例就是上标为0的时候是1
 $1 + 4 + 4 \times 3 + 4 \times 3 \times 2 + 4 \times 3 \times 2 \times 1 = 1 + 4 + 12 + 24 + 24 = 65$ 

46.设二叉排序树中有 n 个结点，则在等概率下二叉排序树的平均成功查找长度为（ ）。
(A) O(1)
(B) O(log2n)
(C) O(n)
(D) O(n^2)
答案：B
 $等概率下成功查找的概率； \sum (本层深度 \times 本层元素) / 节点个数$ 
 $等概率下不成功查找的概率； \sum (本层深度 \times 本层补上的叶子个数) / 补上的叶子总数$ 
 $当元素个数为 n 的时候，树高度为 h = l o g_{2} (n + 1)$ 
上面不知道怎么求树高，请扇自己一巴掌，告诉自己，别放过自己，恶补二叉树有关知识
 $\frac{\sum_{1}^{n} (h \cdot 2^{h - 1})}{n}$ 
再将h替换为n的式子
 $\frac{\sum_{1}^{n} (l o g_{2} (k + 1) \cdot 2^{l o g_{2} (k + 1) - 1})}{n}$ 
 $\frac{\sum_{1}^{n} ((k + 1) l o g_{2} (k + 1))}{2 n}$             说实话我一度觉得题目有问题，确实是这样，这还是我修改以后的
我还想用定积分定义，结果没有极限，这种求和公式怎么求出来具体的啊啊啊
所以我们就让k就是n
 $\frac{((n + 1) l o g_{2} (n + 1))}{2 n} = \frac{n l o g_{2} (n + 1) + l o g_{2} (n + 1)}{2 n} = 2 l o g_{2} (n + 1) = l o g_{2} (n + 1)$ 
顺便提一句，我真的不是为了凑答案才这样写的
            
47.n个不同的元素依次进栈，能得到（ ）种不同的出栈序列。
 $卡特兰数 \frac{1}{n + 1} C_{2 n}^{n}$ 

48,下述有关hash冲突时候的解决方法的说法，错误的有？
A. 通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。
B. 开放定址更适合于造表前无法确定表长的情况
C. 在用拉链法构造的散列表中，删除结点的操作易于实现
D. 拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间
答案是B
开放定址法和拉链法，类比数组和链表
所以你就知道为什么选B了，你见过数组可以未卜先知吗？

49.对10TB的数据文件进行排序，应使用的方法是（）
A. 希尔排序
B. 堆排序
C. 快速排序
D. 归并排序
答案：D
内部排序不适合数据较大的排序
使用外部排序，注意区别二路归并和多路归并，一个是内部一个是外部

50.先序序列为 a,b,c,d 的不同二叉树的个数是（）。
A．13    B．14    C．15    D．16
答案：B
我是蛮讨厌的，你选项要是最大6，7个我还可能自己画画
10几个，我画鸡毛啊
但是我也不知道咋办，突然间我想到了一个东西，但是
我不敢用，因为挺虚的，我就知道卡特兰数是求什么什么来着
嗯，上面就是求出栈次序，啊呀我想啊想，是不是呢
出栈为先序abcd的次数，哎呀呀呀呀呀，好像有点道理
不对，先序和中序确定一棵二叉树
先序为入栈，然后出栈次序为中序
出栈次序有多少个就有多少棵树
但是问题来了，出栈为后序怎么办？
按我目前的水平来讲，这有点自己绕自己了
先序是确定的，中序和后序，是我自己规定的
又不是题目说的，你管呢？
我说中序就是中序，就是每一个不同出栈次序就是一棵不同的树

51.已知一个长度为16的有序顺序表R[1..16]，采用折半查找方法查找一个存在的元素，则比较的次数最多
答案是5次
我一开始一直以为是四次
1-16 -》（1+16）/2=8，第一次
1-7-》 （1+7）/2=4 第二次
1-3-》 （1+3）/2=2第三次
1-1-》（1+1）/2 = 1 第四次
后面我发现不是这样
16个元素，以中构建二叉排序树
其实就是树的深度就是比较次数
利用公式
 $2^{h} - 1 = 16$ 
 $h = l o g_{2} 17$ 
 $h = 5$ 

52.若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。
A. 0
B. 1
C. 2
D. 3
答案是：D
这道题可以回顾一下平衡二叉树构造过程
以及我认为最难的是题目的分支节点这个词语
天天玩这种，直接给我们背名词定义算了呗
分支节点是指除叶子节点外的所有节点

53.若无向图 G=（V, E）中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（）。
A. 6     B. 15     C. 16     D. 21
答案：C
公式秒了
 $| E | = \frac{(| V | - 1) (| V | - 2)}{2} + 1$ 

54.由一个关键字序列建立一棵二叉排序树，该二叉排序树的形状取决于______。
A. 该序列的存储结构
B. 序列中的关键字的取值范围
C. 关键字的输入次序
D. 使用的计算机的软、硬件条件
选C
不明白。排序树不是自动左大右小吗？哦原来是左大右小啊，第一个大的说不定就是第一个根节点然后右子树就没有了，最后一个大的就指不定了

55.含有20个结点的AVL树的最大高度是______。
A.4
B.5
C.6
D.7
答案：C
写不出来，纯粹没有背公式
平衡二叉树深度为h所需的最小节点数:
N(h)=N(h-1)+N(h-2)+1
N(0)=0,N(1)=1;
N(6)=20;

56.若一棵有n个结点的二叉树，其中所有分支结点的度均为k，该树中的叶子结点个数是______。
A. n(k-1)/k
B. n-k
C. (n+1)/k
D. (nk-n+1)/k
答案：D
第一次我就写出来了
做数学题了
设x为叶子个数
分支节点有多少个？
总个数减去叶子就是n-x
所以总个数就是k(n-x)+1
为什么+1？因为还有根节点
等式就是
n=k(n-x)+1
解出x=(nk-n+1)/k

57.已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是
A. 27
B. 46
C. 54
D. 56
答案：B
给出方法吧，节点是奇数就直接按哈夫曼来构造
节点是偶数就补一个0，然后按哈夫曼构造，然后计算

58.下面程序段的时间复杂度是()
i=s=0;
while(s< n){
i++;s+=i;
}
A. O(sqrt(n))      B. O(n2)      C. O(log2n)   D. O(n3)
答案：A
时间复杂度当数学题来写，很快乐
总的来说就是s>=n就停止
i=1 s=1
i=2 s=3
i=3 s=6
i=4 s=10
i=5 s=15
....
找到规律没有？别给自己下套
什么i加，s也在加，根本用不了等差公式是吧？
你个大傻瓜
第一个s是不是第一个i
第二个s是不是前两个i的加和
第三个s是不是前三个i的加和
第n个s不就是前n个i的加和嘛
怎么说，套公式啊
我们设执行了x次
 $\frac{(1 + x) x}{2} = x^{2} = n$ 
 $x = \sqrt{n}$ 
            
59.一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是______。
A. n*h
B. n+h
C. n-1
D. h-1
答案：C
分支数，不是分支节点，除去根节点，有几个节点就有几个分支数
            
60.
小端存储：和常用习惯一样——低地址存低位
大端存储：高地址存低位
0x11223344
44是低位，存储在小端中的地位也就是最上面
在大端中是低放高也就是最下面
但是读取都是从上往下
            
61.对8个元素的顺序表进行快速排序，在最好情况下，元素之间的比较次数为______ 次。
A. 7
B. 8
C. 12
D. 13
答案：D
最好的情况，还记得我们怎么分吗？当然是二分
也就是一个长度3，一个长度4
怎么不是44分？你傻啊，分的那点肯定不算啊
也就是用了7次找到中间那个点
左边长度3，至少比较2次就一个排好了
右边长度4至少比较3次再分成长度1和长度2
长度2的比较一次，长度1的比较你大爷，和鬼比吗
7+2+3+1=13
            
62.设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2 个子结点。若 T有 k个叶结点，则T的结点总数是（）。
A. 2k-1    B. 2k    C. k^2    D. 2^k-1
答案：A
 $n = 0 \times n_{0} + 2 \times n_{2}$ 
 $n_{0} = n_{2} + 1$ 
 $n = 2 k - 2$ 
对我一直怀疑题目是不是错了，后来才知道，第一层的根节点，我们没有算，度为2的×2只是把除根节点外的所有节点加和了
于是n=2k-1

63.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）
A．257
B．258
C．384
D．385
答案：C
首先我知道你肯定能够强算，反正就推嘛，倒数第一层到底是第几层，然后这一层没有满，用满的减去现有的
然后倒数第二层绝对有叶子节点，这些叶子节点也是通过计算倒是第一层有多少个，然后除2，得出倒数第二层有多少个是有子节点的剩下的就是叶子
但是有一个更简单的方法
 $n_{0} + n_{1} + n_{2} = 768$ 
 $n_{2} = n_{0} - 1$ 
并且度为1的节点只能是1个或者0个，因为是完全二叉树
 $2 n_{0} + n_{1} = 769$ 
假如度为0的节点个数是0个，那么怎么可能一个偶数=奇数
所以度为0的个数为1，于是
 $n_{0} = 384$ 
            
路径是由顶点组成的序列，而不是由边组成的序列。
            
64.在线索二叉树中，t所指结点没有左子树的充要条件是（   ）。
A. t->left==NULL B. t->ltag==1 C. t->ltag==1&&t->left==NULL D. 以上都不对
答案：B
线索二叉树中，如果左或者右子树为空，可以让其指向前驱和后继节点
ltag==1说明左边有线索，也就是左子树为空。
            

65.设F是一个森林，B是由F变换得的二叉树，若F中有n个非终端节点，则B中右指针域为空的结点有：
            
66.在二维数组中，每个数组元素同时处于（ ）个向量中。
2个，行和列向量的交点
            
非同义词之间的冲突是引起堆积现象的主要原因。
同义词：同义词是指不相同的键值却得到相同哈希值的元素。
非同义词：非同义词是指不相同的键值得到不同哈希值的元素。
            
线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
这句话是正确的，我想你可能会说，不对啊，没有顺序，那我的指针怎么指向的下一个呢？
这里犯了一个错，就是说，这里的顺序是逻辑上的顺序，也就是我们逻辑上的前后，指针的特性给出的
而不是存储顺序
            
二叉树的创建，以及前中后序

/*二叉树的创建和遍历*/
#include< stdio.h>
#include< stdlib.h>
//二叉树的创建
typedef struct TreeNode {
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
}TreeNode;
void creatTree(TreeNode**T)
{
	char ch;
	scanf_s("%c\n", &ch);
	//这里为什么放一个换行符？
	//因为你喜欢回车，回车也是字符被读入，所以会导致一直进行下去
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		creatTree(&((*T)->lchild));
		creatTree(&((*T)->rchild));
	}
}
void pre(TreeNode *T)
{
	if (T == NULL)
	{
		return;
	}
	else{
		if(T!=NULL)
		printf("%c", T->data);
		pre(T->lchild);
		pre(T->rchild);
	}

}
void in(TreeNode* T)
{
	if (T == NULL)
	{
		return;
	}
	else {

		in(T->lchild);
		printf("%c", T->data);
		in(T->rchild);
	}

}
void le(TreeNode* T)
{
	if (T == NULL)
	{
		return;
	}
	else {

		le(T->lchild);
		le(T->rchild);
		printf("%c", T->data);
	}
}
int main()
{
	printf("这是树的创建\n");
	TreeNode *T;
	creatTree(&T);//测试使用ABD##E##CF##G###，多出来的一个#是C的缺陷
	//之所以有#是因为二叉树空后代都要标出来
	//这是使用前序遍历创建二叉树
	printf("\n前序遍历为：\n");
	pre(T);
	printf("\n中序遍历为：\n");
	in(T);
	printf("\n后序遍历为：\n");
	le(T);
	return 0;
}


二叉树的层序遍历

/*二叉树的层序遍历*/
#include< stdio.h>
#include< stdlib.h>
//二叉树的创建
typedef struct TreeNode {
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
}TreeNode;
typedef struct Queue
{
	TreeNode* data;
	struct Queue* pre;
	struct Queue* next;
}Queuel;
void creatTree(TreeNode**T,char*str,int*index)
{
	char ch;
	ch = str[*index];
	(*index)++;
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		creatTree(&((*T)->lchild),str,index);
		creatTree(&((*T)->rchild),str,index);
	}
}
void pre(TreeNode *T)//前序遍历
{
	if (T == NULL)
	{
		return;
	}
	else{
		if(T!=NULL)
		printf("%c", T->data);
		pre(T->lchild);
		pre(T->rchild);
	}

}
void in(TreeNode* T)//中序遍历
{
	if (T == NULL)
	{
		return;
	}
	else {

		in(T->lchild);
		printf("%c", T->data);
		in(T->rchild);
	}

}
void le(TreeNode* T)//后序遍历
{
	if (T == NULL)
	{
		return;
	}
	else {

		le(T->lchild);
		le(T->rchild);
		printf("%c", T->data);
	}
}
Queuel* initQueue()//初始化队列
{
	Queuel* Qnead = (Queuel*)malloc(sizeof(Queuel));
	Qnead->data = NULL;
	Qnead->next = Qnead;
	Qnead->pre = Qnead;
	return Qnead;
}
void addQueue(TreeNode* T,Queuel*Qhead)//队尾增加元素
{
	Queuel *node = (Queuel*)malloc(sizeof(Queuel));
	node->data = T;//将树结点存储结点
	node->pre = Qhead;//让新结点的前驱指向头
	node->next = Qhead;//让新结点的后继指向头
	Qhead->pre->next = node;//让最后一个结点指向新结点
	Qhead->pre = node;//让头的前一个指向新结点
}
Queuel* deleteQueue(Queuel* Qhead)//队头删除元素
{
	if (isEmpty(Qhead))//如果链表为空则删除失败
	{
		return NULL;
	}
	else {
		Queuel * Qnode = Qhead->next;//建立一个结点存储我们要删除的
		Qhead->next->next->pre = Qhead;//让头结点的后继的后继的前驱指向头
		Qhead->next = Qhead->next->next;//让头的后继指向后继的后继
		return Qnode;//返回删除的结点
	}
}
int isEmpty(Queuel* Q)
{
	if (Q->next==Q)//队列判空
	{
		return 1;
	}
	else {
		return 0;
	}
}
void level(TreeNode* T,Queuel *Qhead)//层序遍历
{

		addQueue(T, Qhead);//进入第一个结点
		while (!isEmpty(Qhead))//判断队列是否为空
		{
			Queuel* outnode = deleteQueue(Qhead);//建立一个结点存储出队列的结点
			printf("%c", outnode->data->data);//打印这个结点
			if (outnode->data->lchild)//如果结点有左子树
			{
				addQueue(outnode->data->lchild, Qhead); //就让左子树进入
			}
			if (outnode->data->rchild)//如果结点有右子树
			{
				addQueue(outnode->data->rchild, Qhead);//就让右子树进入
			}

	}

}
int main()
{
	printf("这是树的创建\n");
	TreeNode *T;
	char * str = "ABD##E##CF##G###";
	int index = 0;
	creatTree(&T,str,&index);
	printf("\n前序遍历为：\n");
	pre(T);
	printf("\n中序遍历为：\n");
	in(T);
	printf("\n后序遍历为：\n");
	le(T);
	printf("\n层序遍历为：\n");
	Queuel * Qhead = initQueue();
	level(T, Qhead);
	return 0;
}

           
二叉树的前中后序遍历(非递归)
这里主要使用了，栈来模拟前序遍历，根进根出，右先进左再进
为什么右先进呢，因为是栈，所以后进才能先出
左退，左的右孩先进左孩子再进...

后序遍历：我们前序是：根左右，后序是：左右根
假如现在我们让左孩子先进，右孩子后进，也就是右孩子先出，左孩子后出
是不是就是中右左
我们把中右左存入数组，如何整体翻转一下
那不就是左右中了！

以上前序和后序   判断停止条件就是栈不为空
-----------------------------------------
中序遍历：左中右
还是借助栈来实现
一路向左，接连入栈，直到有人左孩子是空
此时弹出栈顶元素
此时判断栈顶元素的右孩子是否为空
如果不为空，右孩子入栈，判断右孩子的左孩子是否为空，如果不为空一路向左入栈
假如栈顶元素的右孩子也空，那么继续输出栈顶元素
什么时候停止呢？就是栈为空的时候，别想多了，第一次入栈是放到判空的外面的、
值得注意的是，需要一个指针来遍历节点，用栈来存储遍历过的节点

    /*二叉树的前中后序遍历的非递归
1.入栈根节点
2.循环，直到左孩子为空
3.出栈，访问节点，入栈右孩子
*/
#include< stdio.h>
#include< stdlib.h>

//二叉树的创建
typedef struct TreeNode {
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
}TreeNode;
typedef struct StackNode {//栈
	TreeNode* data;
	struct StackNode* next;
}StackNode;
void creatTree(TreeNode**T,char*str,int*index)
{
	char ch;
	ch = str[*index];
	(*index)++;
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		creatTree(&((*T)->lchild),str,index);
		creatTree(&((*T)->rchild),str,index);
	}
}
StackNode* initStack()
{
	StackNode* S = (StackNode*)malloc(sizeof(StackNode));
	S->data = NULL;
	S->next = NULL;
	return S;
}
void StackPush(TreeNode* T, StackNode* S)
{
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = T;
	node->next = S->next;
	S->next = node;
}
int isEmptyStack(StackNode* node)
{
	if (node->next == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
StackNode* StackPop(StackNode* S)
{
	if (isEmptyStack(S))
	{
		return NULL;
	}
	else
	{
		StackNode* node = S->next;
		S->next = node->next;
		return node;
	}
}
void pre(TreeNode *T)//前序遍历
{
	TreeNode* node = T;
	StackNode* S = initStack();//初始化一个栈
	while (node||!isEmptyStack(S))//当树节点不为空或者栈不为空
	{
		if (node)//当节点非空
		{
			printf("%c",node->data);//打印这个节点
			StackPush(node,S);//将这个节点入栈
			node = node->lchild;//进入这个节点的左孩子
		}
		else//当节点为空
		{
			node = (StackPop(S))->data;//将父节点出栈并赋予当前节点
			node = node->rchild;//进入父节点的右孩子，进入右孩子如果还为空
			//还会进入这个父节点的父节点，然后再进入右孩子，以此类推
		}
	}

}
void in(TreeNode* T)//中序遍历
{
	TreeNode* node = T;
	StackNode* S = initStack();//初始化一个栈
	while (node || !isEmptyStack(S))//当树节点不为空或者栈不为空
	{
		if (node)//当节点非空
		{
			StackPush(node, S);//将这个节点入栈
			node = node->lchild;//进入这个节点的左孩子
		}
		else//当节点为空
		{
			node = (StackPop(S))->data;//将父节点出栈并赋予当前节点
			printf("%c", node->data);//打印这个空节点的父节点
			node = node->rchild;//进入父节点的右孩子，进入右孩子如果还为空
			//还会进入这个父节点的父节点，然后再进入右孩子，以此类推
		}
	}

}
StackNode* getTop(StackNode* S)
{
	if (isEmptyStack(S))
	{
		return NULL;
	}
	else
	{
		StackNode* node = S->next;
		return node;
	}
}
void le(TreeNode* T)//后序遍历
{
	StackNode *S=  initStack();//初始化栈
	TreeNode* node = T, * r = NULL;//r标记最近访问过的节点
	while (node || !isEmptyStack(S))//当节点不为空或者栈不为空的时候
	{
		if (node)//如果节点不为空
		{
			StackPush(node,S);//将节点入栈
			node = node->lchild;//将节点进入它的左子树
		}
		else  //当节点为空
		{
			TreeNode* top = getTop(S)->data;//取得它的父节点

			if (top->rchild && top->rchild != r)//如果栈顶节点的右孩子不为空，并且没有访问过
			{
				top = top->rchild;//右孩子进入栈顶
				StackPush(top, S);//将右孩子加入栈顶
				node = top->lchild;//加入右孩子的左孩子节点
			}
			else//栈顶没有右孩子或者右孩子被访问过
			{
				top = StackPop(S)->data;//取出栈顶元素
				printf("%c",top->data);//打印栈顶元素
				r = top;//将当前栈顶标记为被访问
			}
		}
	}

}
int main1()
{
	printf("这是树的创建\n");
	TreeNode *T;
	char * str = "ABD##E##CF##G###";
	int index = 0;
	creatTree(&T,str,&index);
	printf("\n前序遍历为：\n");
	pre(T);
	printf("\n中序遍历为：\n");
	in(T);
	printf("\n后序遍历为：\n");
	le(T);
	return 0;
}

翻转链表

            
/*双指针实现翻转链表*/
/*
| a | -> | b | -> | c | -> | d | -> | e |
| a | <- | b | <- | c | <- | d | <- | e |
*/
/*
  pre      cue
  ↓       ↓
  NULL    | a | -> | b | -> | c | -> | d | -> | e |
*/
/*
           pre      cue
            ↓       ↓
  NULL  <-| a | -> | b | -> | c | -> | d | -> | e |
*/
/*
                     pre      cue
                     ↓       ↓
  NULL  <-| a | <- | b | -> | c | -> | d | -> | e |
*/
//没错，正常人看不懂我的鬼画符
/*通俗来讲，就是借助两个指针,让pre指向空，cue指向第一个*/
/*
然后再让cue指向的第一个指向pre也就是第一个节点反转
然后pre和cue整体后移，pre指向第一个，cue指向第二个
再让cue指向的东西指向pre，就是反转第二个
那什么时候结束呢？
                                               pre    cue
                                                ↓    ↓
  NULL  <-| a | <- | b | -> | c | -> | d | -> | e |->NULL
  没错，当cue指向null的时候就不需要翻转了
  简单！🫵🏿🤣
*/
/*
很好，我们看这一步
  pre      cue
  ↓       ↓
  NULL  <-| a |    | b | -> | c | -> | d | -> | e |
           pre      cue
            ↓       ↓
  NULL  <-| a | -> | b | -> | c | -> | d | -> | e |
是不是第一个的下一个，已经翻转了，我的下一个都没了，我的pre和cue如何后移？
很好，我们需要一个零食指针，不对，是临时指针
保存temp = a->next，如何将cue = temp
*/
 turn()
{
     cue = Node->head;//让cue指向链表第一个节点
     pre = NULL;//pre设置为空，目的是模拟链表最后一个就是指向空
     while (cue)//当cue为空的时候停止
     {
         temp = cue->next;//使用临时变量保存节点的下一个
         cue->next = pre;//让当前节点指向前面一个
         pre = cue;//整体后移
         cue = temp;//整体后移
     }//完成翻转
     return pre;//返回翻转后的头结点,cue指向的是null啊，蠢猪
}

两两交换链表


/*两两交换链表中的节点*/
/*
| a | -> | b | -> | c | -> | d | -> | e | -> | f | -> | g |->NULL
| b | -> | a | -> | d | -> | c | -> | f | -> | e | -> | g |->NULL
怎么变？

               ↗→→→→→→→→→→
             ↗    ↓  ←   ↰       ↓
   head      ⇦   | a | -> | b | -> | c | -> | d | -> | e | -> | f | -> | g |->NULL
    ↑ ↘
    ↑    ↘→→→→→→ →↗
   cue
   如果你想象这都是绳子，一拉直，就是变换好了
*/
/*
               | b | -> | a | -> | c | -> | d | -> | e | -> | f | -> | g |->NULL
                         ↑
                         cue
cue指向的后面两个进行变换
*/
/*什么时候为停止？*/
/*
当cue指向的后一个为空的时候，或者cue指向的下一个的下一个为空，因为不足两个
也停止
这里是或的条件
当然了
if(cue->next!=NULL&&cue->next->next!=NULL)
这两个条件是不能写反的，因为如果cue的下一个是空，你还能对空取它的下一个吗？
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {

    struct ListNode* pre = head->next;
    struct ListNode* cue = pre;
    while (cue->next != NULL && cue->next->next != NULL)
    {
        struct ListNode* temp1 = cue->next;
        struct ListNode* temp2 = cue->next->next->next;
        cue->next = cue->next->next;
        cue->next->next = temp1;
        temp1->next = temp2;
    }
    return pre->next;
}

翻转二叉树


/*翻转二叉树*/
/*你画个二叉树，然后将整个树盖到纸上*/
/*类似镜像*/
/*注意嗷，不是交换左右孩子的数值，是左右孩子的指针*/
/*用前序和后序是比较好的*/
TreeNode* invertTree(root)//前序实现
{
	if (root == NULL)//如果树为空，就返回空
		return root;
	swap(root->left, root->right);//交换左右子树
	invertTree(root->left);
	inverTree(root->rright);
}

TreeNode* invertTree(root)//后序实现
{
	if (root == NULL)//如果树为空，就返回空
		return root;
	invertTree(root->left);
	inverTree(root->rright);
	swap(root->left, root->right);//交换左右子树
}

对称二叉树

            
/*判断对称二叉树*/
/*
判断一个树是否为对称二叉树
具体思路就是，判断左-右孩子是否一样
注意这里的左右孩子不是一个根的左右
而是靠左侧最外侧的左孩子
以及右侧最外侧的右孩子
以及内部的左边的右孩子
和内部的右边的左孩子
递归三要数：开始停止过程
什么时候停止呢？
当左右子树都空停止？nonono
当左右子树只要有一个为空就停止返回失败
如果这里想不明白，那你还是没有区别我说的左右子树
这里的左右子树是最左边，以及最右边的树
你都有一个为空了，还对称个毛线
当然了，左右子树都不为空，但是值不等的时候也返回失败
使用后序遍历现实《递归》
*/
bool compare(TreeNode* left,TreeNode *right)//比较的实现
{
	if (left = NULL && right != NULL)//但凡有一边为空就失败
		return false;
	else if (left != NULL && right == NULL)//但凡有一边为空失败
		return false;
	else if (left->val != right->val)//数值不相等也为空
		return false;
	else if (left == NULL && right == NULL)//当都为空的时候，也是对称，返回成功
		return true;//除以上几种情况外的，到最后都会到两边都为空的，所以不用判断
	bool ouside = compare(left->left, right->right);//相对于判断你的两个胳膊是不是对称
	bool inside = compare(left->right, right->left);//相对于判断你的两条腿是不是对称
	bool result = outside && inside;//如果胳膊和腿同时对称才是对称
	return result;//返回比较的结果
}

二叉树最大深度

            
/*求解二叉树的最大深度*/
/*
-----------------------------------
深度：任意节点到根节点的距离，本身和根节点都算进去，用先序遍历
根左右

高度：任意一个节点到叶子节点的距离，本身和叶子节点都算进去，用后序遍历
左右根

也就是说求高度就是需要从下往上遍历
后序遍历刚好就是左右（下），然后根（上）
通过返回当前节点高度给根，然后根+1就是，根节点的高度

也就是说求深度就是需要从上往下遍历
后序遍历刚好就是根（上），然后左右（下）
通过返回当前根节点高度给孩子，然后孩子+1就是，孩子节点的深度


重点：最大深度就是根节点的高度

-----------------------------------
*/
int gethight(TreeNode* node)
{
	if (node == NULL)
	{
		return 0;
	}//终止条件
	//单层递归过程如下
	int lefthight = gethight(node->left);//进入左
	int righthight = gethight(node->right);//进入右
	int heigh = 1 + Max(lefthight, righthight);// 取左右孩子最大值，然后+1，因为自己也算一个
	//就是左右根，后序遍历求根高度，就是最大深度
	return heigh;
}

二叉树的最小深度

            
/*二叉树最小深度*/
//根节点到最近叶子节点的距离
//后序遍历
int gethight(TreeNode* node)
{
	if (node == NULL)//明确递归终止条件
	{
		return 0;//空节点的高度是0
	}
	int left_height = gethight(node->left);//遍历左子树
	int right_hight = gethight(node->right);//遍历右子树
	if (node->left == NULL && node->right != NULL)//当左为空，右不为空，取右边，因为深度不包括空节点
	{
		return 1 + right_hight;
	}
	if (node->right == NULL && node->left != NULL)//当右为空，左不为空，取边
	{
		return 1 + left_height;
	}
	//还有就是都不为空的时候，取左右子树最小高度即可
	int result = 1 + min(left_hight, right_hight);
	return result;
}

完全二叉树节点数量

            
/*完全二叉树的节点数量*/
//后序遍历
//
//普通二叉树
int getNum(TreeNode* node)
{
	if (node == NULL)
		return 0;
	leftNum = getNum(node->left);//左
	rightNum = getNum(node->right);//右
	int result = leftNum + rightNum + 1;//中
	return result;
}

//完全二叉树
//计算思路，借助满二叉树的节点计算辅助计算完全二叉树
//例如深度为3的满二叉树就是2的3次方-1
//通过拆分左右子树，来形成满二叉树计算的式子
//判断子树是否为满二叉树，只需要向左走到底，和向右走到底
//左右深度一样就是满二叉树，单独的叶子节点一定是满二叉树

int getNum(TreeNode* node)
{
	if (node == NULL)//递归终止条件
	{
		return 0;
	}
		TreeNode* Left = node->left;
		TreeNode* Right = node->right;
		int leftpath = 0;//计量左侧深度
		int rightpath = 0;//计量右侧深度
		while(Left)//去遍历左侧
		{
			Left = Left->left;
			leftpath++;
		}
		while (Right)//遍历右侧，统计右侧深度
		{
			Right = Right->right;
			rightpath++;
		}
		if (leftpath == rightpath)//如果两边相等，就是满二叉树
		{
			return (2<< leftpath)-1 //计算子树节点数量,左移一位就是平方，以此类推
		}
		//以下是单层递归的逻辑
		int leftnum = getNum(node->left);//去计算左树
		int rightnum = getNum(node->right);//去计算右树
		int result = leftnum + rightnum;
		return result;

}

合并二叉树

            
/*合并二叉树*/
//现在有两棵二叉树
//如果有对应节点，则节点相加
//如果一棵有，一棵没有就是把有的放上去，连带其子树
//使用前序，根左右

TreeNode* margeTree(TreeNode* t1, TreeNode* t2)
{
	if (t1 == NULL)//终止条件
	{
		return t2;//如果t1此处没有点，就把t2此处点返回
		//反正不管t2也没有，就当它现在有，至少得让它证明自己
	}
	if (t2 == NULL)
	{
		return t1;
	}
	//以下是单层递归逻辑
	t1->value += t2->value;//都不为空就是相加(中)
	t1->left = margeTree(t1->left, t2->left);//让合并的树就在t1上表现，左子树就是t1，t2的合并（左）
	t1->right = margeTree(t1->right,t2->right);//让合并的树就在t1上表现，右子树就是t1，t2的合并（右）
	return t1;//返回被覆盖的t1

}


    快来看这有个美女摔倒啦！🫵🏿🤣
                      _ _-^^"-,---,
              _-""./  ||//_  /
            _< _../    <-"__)'
    _..--'''         _.-"  \
  .'         _..--""' `  ` \
  `,    _..-" ' /      `   |
    \  ' \   ' |  //||\    \
     \  /"|      // -- |   /
      \/ \|   |""   G>/  ,/`.
     ,'   `   '. -  .;-""    |
    <'     \""\ \_"  /  _.-_"
     `\      _ "//-.'.-" --."\
       \    (c`//// /  /"   \ |
        "-___/| U |  ,/      \|
             "|  /  ,'        \
              / /   | |  .     ,
             (  (   ) J /      |
              \  \   \."   .   /
               '  "-_/   /'   /
                `.   \==.    """-._
                  \      `+-'./~   ".
              ,.   "-_   /  //'   .- \
         _.--"  ""--_-"-/       /"    `,
       /"        \           |-<--""-  |
       |  -.__..--""""""'-->'`         |
       /  |      .-")/"  ,'   \        J
      |   \   .-"  ..-"""  _.-'        J
       \   \  ' <"/     ./"         ./'/
        \.  \_.-,'`\   /    _      ((  |
          \    /    \        \      '\/,
           \ ,'      \_       \      / _\
            /        _/--""""\_'(   ""' /
           /      _/'/        /\_    _-"
          /      <-"/       <'   "\ /
         /         /      ." "-"=-""     __.
         \,       /      /_   |   """-/""   `.
           `-----Y       " ""-_         \    |
                 (             ". __     +   |
                  `-___          `\.""-/\|   |
                       `--._       /  <.  \) `,
                            ""-._ /     "\    |
                                 "._       ""-\C.-.
                                    "-._      /ryt|
                                        "-   )    '
                                        < \_ /   /
                                         `\ ",  /
                                           )|,  |
                                           |    '
                                           '   /
                                          |   '
                                          \ ,'
                                           "

算法经典题

觉得页面太小点击下面链接算法

C语言总结

基本要点和易错点

函数是组成C程序的基本单位，语句是组成C程序的最小单位。
-------------------------------------------------------------
C程序总是从main开始，main结束
-------------------------------------------------------------
三种结构：顺序，选择，循环
-------------------------------------------------------------
开发C过程：编辑、编译(.obj)、连接(.exe)、执行。其中obj是在编译完后才有，exe同理
-------------------------------------------------------------
C的基本数据类型(5种)：整型、字符、单精度浮点、双精度浮点、枚举
-------------------------------------------------------------
变量定义以及变量声明：定义是创建，声明是告诉编译器别处存在，不需要重新创建，我要使用别处的。
-------------------------------------------------------------
空白字符不能出现在整数数字之间
-------------------------------------------------------------
字符常量(4种)：普通字符常量、字符串常量、转义字符、符号常量
-------------------------------------------------------------
实型常量：.前可以省略，e后必为整型
-------------------------------------------------------------
转义字符只能用小写
-------------------------------------------------------------
自增自减只能用于单个变量
-------------------------------------------------------------
sizeof是单目运算符，而不是函数
-------------------------------------------------------------
运算符优先级口诀：成单乘加移等位辑赋//成员、单目、乘法、加减、移位、判等、位运算符、逻辑、赋值
-------------------------------------------------------------
printf中，从右向左计算出表达式的值//printf(，i++,i--),i++显示的值是i进行自减以后的
-------------------------------------------------------------
else与其前面最靠近的if配对
-------------------------------------------------------------
case后只能是整型或者字符型的常量或常量表达式
-------------------------------------------------------------
对数组不赋初值，那么会分配随机内存数，如果是static声明的，会自动分配0
-------------------------------------------------------------
static是静态变量的意思，只随着程序的销毁而销毁
-------------------------------------------------------------
数组定义时，只能省略后面的元素初始值，不能隔山打牛：[10,,3]
-------------------------------------------------------------
char s[5]={'a','b','c'}|char s[5]="abc"//这两种区别在于后者会被自动末尾添加一个'\0'
-------------------------------------------------------------
指针变量就是一个变量，就是指向double和指向int的指针本身大小是一样的，保存的就是地址
-------------------------------------------------------------
int a[10];a是指数组的首元素的地址，即a==&a[0],而"整个数组"的首地址是 &a
-------------------------------------------------------------
字符数组不能整体赋值，但是字符指针可以
-------------------------------------------------------------
void类型的函数，是可以使用return的。函数内部不能定义其他函数
-------------------------------------------------------------
函数定义出现在函数使用之前不会报错，也不需要函数声明，这个时候就是函数原型
-------------------------------------------------------------
函数参数的计算顺序是从右向左
-------------------------------------------------------------
auto是自动分配自动销毁，函数外部直接定义是全局，static是静态，与全局不同的是，它只能被本编译单位使用，extern使用的是直接声明，而不是static
-------------------------------------------------------------
编译预处理都以‘#’开头，每个预处理语句必须单独占一行
-------------------------------------------------------------
宏是在程序执行之前完成
-------------------------------------------------------------
文件中位置编号从1开始，第一个字节编号为1
-------------------------------------------------------------
输入数据的时候不能规定精度
-------------------------------------------------------------
\b是让光标位置回退一格，而不是向前删除一个字符
-------------------------------------------------------------
两指针相加没有意义
-------------------------------------------------------------
在二维数组中a[3][3],a[2]是一个地址，而不是a[2][0]这个值，但是a和a[0]指向的地址是一样的
-------------------------------------------------------------
一个文件中不一定必须要有main函数
-------------------------------------------------------------
头文件不一定以.h结束，.c也是一样的，头文件的h只是方便区分
-------------------------------------------------------------
e前e后必有数，e后必定为整数，小数点两边有一个是0，可省略
-------------------------------------------------------------
共用体的大小由共用体中所占最大的那个决定
-------------------------------------------------------------
#include< stdio.h>
int main()
{
	float a = 1.5;
	printf("%f", ++a);
}
//2.500000
没想到吧，浮点数也可以进行自加自减
-------------------------------------------------------------
~（取反）不能用于浮点数
-------------------------------------------------------------
右移操作有两种情况，一种是不管符号位是不是0，空缺位都补0，即逻辑移位；一种是符号位是什么，空缺位就补什么，即算术移位。
-------------------------------------------------------------
指针用惯了，但是结构体指针时，你想去下一个，可不兴指针++的方式
-------------------------------------------------------------
-：左对齐。
+：输出符号（正数前面加上“+”）。
#：八进制前缀（0）、十六进制前缀（0x 或 0X）或浮点数小数点（.）。
0：用 0 在左侧填充数据输出的空白，而不是默认的空格字符。
m.n：m 是指定的最小宽度，n 是指定的精度。
*：用来接收动态传入的宽度和精度。例如，%*.*f 表示输出浮点数，宽度和精度由后面带两个 int 类型的参数动态传入。
-------------------------------------------------------------
逗号表达式的值
表达式1，表达式2，表达式3....表达式n
从左到右，依次计算各个表达式，表达式n是整个逗号表达式的值
-------------------------------------------------------------
#include < stdio.h>
main()
{
    int a = 10;
    while (a)
    {
        int b = 10;
        a--;
        printf("%d", b);//可以
    }
    printf("%d", b);//不行，b显示未定义
}
-------------------------------------------------------------
void func(int *p){
	static int num = 4;
	p = & num;
	(*p)--;
}
int main(){
	int i = 5;
	int *p = & i;
	func(p);
	printf("%d", *p);
	return 0;
    }

这道题有意思的，平常习惯了一种概念，就是传入指针就是地址，修改以后就是改变了外部值
一不小心就掉坑咯
这题答案是5
p传进去以后，p的指向就变了，修改的确实是num
然而形参永远是形参，main中的p还是指向i的
-------------------------------------------------------------
算术运算符和圆括号有不同的运算优先级，对于表达式：
a+b+c*(d+e)，关于执行顺序，以下说法正确的是
A)先执行 a+b 得 r1，再执行(d+e)得 r2，再执行 cr2 得 r3，最后执行 r1+r3 得表达式最后结果
B)先执行(d+e)得 r2，再执行 cr2 得 r3，再执行 a+b 得 r1，最后执行 r1+r3 得表达式最后结果
C)先执行(d+e)得 r2，再执行 cr2 得 r3，再执行 b+r3 得 r4，最后执行 a+r4 得表达式最后结果
D)先执行 a+b 得 r1，再执行 r1+c 得 r5，再执行(d+e)得 r2，最后执行 r5r2 得表达式最后结果
答案是A，我选的是B，因为我犯了个错误，计算机是从左向右计算的
贪心法收取符号，碰到括号确实是直到右括号，然后计算括号包裹
但是没有括号之前是能算就算的
-------------------------------------------------------------
32位系统，函数void Func(char str[100]){}中sizeof(str)的大小为（）
A. 4    B. 6    C. 8    D. 100
答案是A
你不会选了D吧？自以为学了点东西，str代表的是整个数组大小
然后乐乐呵呵的选了D
正好，掉陷阱了，这是函数的参数，是形参
数组传入是自动退化为指针，指针在64位中是8
在32位中就是4了
-------------------------------------------------------------
void*可以转化为任何类型指针，当任何类型指针也可以转化为void*
-------------------------------------------------------------
类似于*和++这样的一元运算符遵循从右至左的结合顺序
-------------------------------------------------------------
有以下程序
#include < stdio.h >
main( ) { int a,b;
for (a=0; a<3; a++)
{ scanf("%d", &b);
switch(b)
{
default: printf("%d,", b++);
case 1: printf("%d,", b++);
case 2: printf("%d,", b++);
} } }
程序运行时输入：1 2 3< 回车 >，则输出结果是
答案是：1,2,2,3,4,5,
switch...case的三个规则：
（1）既无成功匹配，又无default子句，那么swtich语句块什么也不做；
（2）无成功匹配，但有default，那么swtich语句块做default语句块的事；
（3）有成功匹配，没有break，那么成功匹配后，一直执行，直到遇到break。
通俗一点说，就是：
我只找我想要的case，其他的都不管（直接注释掉这个case前面的所有语句）。
找到我想要的case后，我就不再看其他case了（直接注释掉这个case后面的其他"case"关键字）。
找到我想要的case后，我只管执行后面代码，直到遇到break后跳出switch语句块。
-------------------------------------------------------------
以下程序中c的二进制值是（  ）。
char a=3,b=6,c;
c=a^b<<2;
A. 00011011       B. 00010100     C. 00011100       D. 00011000
答案：A
选B的请别放过自己
<< 优先级比^高
把看函数先看定义域和看表达式结果先看符号优先级抄100遍
-------------------------------------------------------------
求输出结果
#include< stdio.h >
int a[2][2][3] = {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9}, {10, 11, 12}}};
int *ptr = (int *)(&a + 1);
int main(){
printf("%d %d", *(int*)(a + 1), *(ptr - 1));
}
a是三级指针，代表整个数组首地址，a+1=>{{7, 8, 9}, {10, 11, 12}}的首地址
*(int*)(a + 1)。首先(int*)强制为一维数组，然后解引用，也就是7
&a是四级指针，&a+1，代表的是{{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9}, {10, 11, 12}}}  ->{{{ }}}
跳出去了
(int *)(&a + 1)就是跳出去以后的数组强制到一维,ptr此时就是一维
ptr - 1,只能移动1维数组的移动量，也就是指向了a数组的最后一个元素
*(ptr - 1)解引用就是12
所以就是7和12
-------------------------------------------------------------
四舍五入或直接取整
1.强制转化成int，直接取整
2.保留精度(四舍五入)
printf("%.2f",3.1475926)//输出的是3.15,保留二位，只看第三位，四舍五入
3.round()函数，四舍五入，并且round是将小数部分全部取到整数部分
4.浮点除法运算
-------------------------------------------------------------
strlen()函数用于计算字符串的长度，但不包括末尾的空字符'\0'。因此，对于字符串"hello!"，其长度为6个字符，不包括末尾的空字符'\0'。
-------------------------------------------------------------
scanf()读取字符串，遇到空格停止读入
-------------------------------------------------------------
double x = 5.1012;
printf("x=%d\n",x);
没错，它不是5，而是一个负数
其行为是未定义的
-------------------------------------------------------------
printf("%2d\n",2010);
程序运行时输出 2010
这是因为 %2d 表示输出的整数将占用至少2位的宽度，如果整数不足2位，则在前面补空格。如果整数超过2位，则按实际位数输出。
-------------------------------------------------------------
C语言标识符的分类：关键字、预定义标识符、用户定义标识符
-------------------------------------------------------------
非线性结构是数据元素之间存在一种（  ）
A）一对多关系        B）多对多关系      C）多对一关系     D）一对一关系
答案B，多对多包含一对多
-------------------------------------------------------------
数组名作为实参传给被调用的函数时，形参获得的是该数组第一个元素的首地址
-------------------------------------------------------------
全局变量将作用于整个程序文件，所以不能在 main() 函数中定义该变量。（X）
这句话是错的，区分声明和定义，声明在外面就行了，定义在哪里都可以
-------------------------------------------------------------
continue在switch里面使用，一定是外部有while或者for包含
并且continue是作用于外部的循环，而不是switch。
-------------------------------------------------------------
sscanf 或 fscanf 的格式字符串
普通字符匹配：
%c：读取一个字符。
%s：读取一个字符串，直到遇到空白字符（空格、制表符、换行符等）。
数字匹配：
%d：读取一个整数。
%u：读取一个无符号整数。
%f：读取一个浮点数。
%e 或 %E：读取一个科学计数法表示的浮点数。
%x 或 %X：读取一个十六进制数。
字符范围匹配：
%[abc]：读取一个字符，该字符必须是 a、b 或 c 之一。
%[^abc]：读取一个字符，该字符不能是 a、b 或 c 之一。
字符串范围匹配：
%[a-z]：读取一系列小写字母。
%[A-Z]：读取一系列大写字母。
%[0-9]：读取一系列数字。
忽略字符：
%*c：忽略下一个字符。
%*s：忽略接下来的字符串。
宽度限定：
%9s：读取最多9个字符的字符串。
%*9c：忽略接下来的9个字符。
长度修饰符：
%hhd：读取一个有符号的8位整数（char）。
%hu：读取一个无符号的8位整数（unsigned char）。
%hd：读取一个有符号的16位整数（short）。
%ld：读取一个有符号的32位整数（long）。
%lld：读取一个有符号的64位整数（long long）。
%lf：读取一个 double 类型的浮点数。
%lf：读取一个 long double 类型的浮点数。
位置指定：
%2$d：读取第二个字段的整数。
-------------------------------------------------------------
int a[5]={}; 全部数组元素使用默认值,当然默认值一般是0;
int a[5]={0}; 第一个元素初始化为0,其他使用默认值(默认值也是0)
-------------------------------------------------------------
C语言中浮点类型数据不包括小数
-------------------------------------------------------------
判断题：由float x=3e-6,y=3e-6;不能得到x==y的逻辑值为假。
是错的，==运算不能使用浮点,会有精度损失
-------------------------------------------------------------
int a[]={0,1,2,3,4,5,6,};
这个数组只有7个元素，不是8个，最后的逗号也可有可无
a[7]确确实实会输出0，但是越界行为是不能保证的
-------------------------------------------------------------
优先级只是决定了表达式的结合次序，而不是运算顺序
-------------------------------------------------------------
--p++
看这个式子，先不说错误
你觉得是先后++还是前--
肯定是先后++，单目运算符是从右向左结合
编译器会报错误，--需要左值
为什么，即便我p++先执行，但是我p依旧是指针不是吗？
好，即便这样不是，那我这样--(p++)可以吗
不可以，因为--对的是一个表达式p++而言，表达式不能进行
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------

字符串处理函数(#include< string.h >)
puts(p);//其中p是字符指针，可以带有转义字符，并且puts会自动在末尾增加一个换行符


char a[30] = {'\0'};//定义一个字符数组
char* str = a;//初始化字符指针指向字符数组，必须初始化，一定要初始化
gets(str);//从标准输入中读取整行，直到遇见换行符然后丢掉换行，然后在末尾加入一个空字符形成C字符串,它是有缺点是，因为不知道str可以存多少个，所以会造成越界
puts(str);//打印一行，然后加上换行符。
fgets(str,10,stdin)//它接受三个参数，第一个是str，第二个是读入的字符最大量，第三个是指明读取的源头，这里是标准输入(键盘)，当读到换行(回车),或者第9个字符停止，如果是换行，那么会将换行保存
fputs(str,stdout)//接受两个参数，第二个是需要输出的地方，这里是标准输出，也就是屏幕，并且与pust不同的是，它不在末尾添加换行
strlen(str)//计算字符长长度
strcat(str1,str2)//拼接字符串,将第二个字符串拼接到第一个字符串后，形成的新串为第一个字符串，没错，可能会越界
strncat(str1,str2,最大添加字符数)//是的，这不就改良版来了，为什么上面那个没有像gets一样被官方废除，因为gets是用户输入，这个函数只有程序员的操作
strcmp(str1,str2)//比较两个字符串//相同返回0
strcpy(str1,str2)//把str2复制到str1中
strlwr(str)//大写变小写
strupr(str)//小写变大写
========================================================
double acos(double x)//反余弦
double asin(double x)
double atan(double x)
double atan2(double x,double y)
...重点关注库函数的参数是什么类型
接下来没讲是几乎都是double
double frexp(double x,int *exponent)//分解浮点数，将指数存到exponent中
double ldexp(double x,int exponent)//返回x乘以2的exponent次幂
========================================================

文件

文件操作

    
        文件使用模式
        处理方式
        指定文件不存在
        指定文件存在
    
    
        r
        读取（文本文件）
        出错
        正常
    
    
        w
        写入（文本文件）
        建立新文件
        原有内容丢失
    
        
        a
        添加（文本文件）
        建立新文件
        原有内容后添加
    
        
        rb
        读取（二进制文件）
        出错
        正常
    
        
        wb
        写入（二进制文件）
        建立新文件
        原有内容丢失
    
        
        ab
        添加（二进制文件）
        建立新文件
        在原有内容后添加
    
        
        r+
        可读取，又可写入
        出错
        打开文件时，文件指针位于文件开头，无论是读取内容还是写入内容，都可在文件中任意位置进行，且进行写入操作时，会覆盖原有位置的内容。
    
    
        w+
        写/读
        建立新文件
        打开文件时，文件指针位于文件开头，文件原有内容丢失，无论是读取内容还是写入内容，都可在文件中任意位置进行
    
        
        a+
        读/添加
        建立新文件
        打开文件时指针位于文件末尾，在文件原有末尾添加，读取内容时，可以在任意位置进行，但写入内容时，只会追加在文件尾部。
    
        
        rb+
        读写
        出错
        正常
    
        
        wb+
        写读
        建立新文件
        原有内容清除
    
        
        ab+
        读添加
        建立新文件
        文件末尾添加
    




FILE *p;//定义文件指针
p=fopen(文件名，文件使用模式);打开文件
fclose(文件指针)//关闭文件
feof(文件指针)//判断文件结束，是末尾返回非0值
ch = getc(p);//从文件流中读取一个字符赋给ch
ch = fgetc(p);//从文件流中读取一个字符赋给ch
putc(ch,p);//将ch写入到文件中
fputc(ch,p);//将ch写入到文件中
fgets(字符变量,n,p);//从p(文件流)中提取n-1个字符给字符变量
fputs(字符变量,p);//将字符变量中字符写入到p(文件)中
fprintf(p,格式串,输出项表);//写入，本质用法和printf一样例如fprintf(p,"这个是%d",10);
fscanf(p,格式串,输入项表);//读取，本质和scanf一样
fwrite(buf,size,count,p);//写入从buf提取count个size字节大小的数据到文件中
fread(buf,size,count,p);//读取count个size字节大小的数据到buf中
ftell(p);//获取指针当前位于文件的位置，返回相对于文件开头的位移量
fseek(p,位移量,0);//0(SEEK_SET)文件开头、1(SEEK_CUR)当前、2(SEEK_END)文件结尾，让指针从文件开头位移《位移量》个位移量，《位移量》为负就是向文件头，为正就是向文件尾，0就是到第三个参数位置
rewind(p);//重置指针位于文件开头

语义“贪心”法

请看这个代码a---b
恶心吧🤣🫵🏿，我们如果碰到怎么办？我们当然是问问更加头疼的编译器，看看它怎么做
它说：该死的程序员
好，正话不多说，我们开始废话：
C语言中使用这个规则：从左到右一个字符一个字符读入，如果该字符可以组成一个符号，那么就读入下一个字符，然后判断是否能够组成一个符号
如果可以并且这两个字符可能是另外符号的组成就再继续读入，直到读入的字符不可能组成有意义的符号。
上面的代码a---b
读入a，接着-
-可以组成自减--，所以继续读入
a--，此时--已经不可能和别的组成有意义的符号了，于是
保持再读入-，再读入b
也就是(a--)-b//这段代码执行是a-b，然后a自减，为什么？因为这是a--,使用a然后a才能自减

深度理解函数声明

请看这个代码(*(void(*)())0)()
爽吗？
要回答这个问题，真傻逼，不知道谁天天研究这些恶心的东西
行吧
float a;//就是定义一个浮点变量
float *g();//()优先级最高，所以g和()结合，也就是说g()，g是一个函数，然后才是float *，也就是返回类型为浮点指针的函数g
float (*g)();//现在*g表明g是一个指针，float表明返回类型为float,()表明是一个函数，结合起来，g是一个指向返回类型为浮点的函数，也就说g是一个函数指针
接下来一步步分析
(
*//此时*与后面最近的()形成一个解引用的目的
(void(*)())//首先是*表明指针,是匿名指针，然后和()结合就是匿名指针函数，指向没有返回值的函数,加上括号表明是一个强制转换
注意*不是和(void(*)())先结合，因为这样没有意义，应该是(void(*)())和0结合
(void(*)())0表示，将0强制转换为指针函数，指向无返回值的函数
然后才是与*结合*(void(*)())0，表示解引用0，解出来就是0指向的函数本身可以想象成f
然后(f)()
也就是调用f这个函数
(*(void(*)())0)()//也就是调用一个函数，这个函数是被强制转的0，0指向的是一个无返回值的函数

C语言编程有关问题

如果页面太小，请点击下面链接 C

C++总结

基础


/*-------------------------------------------------------------*/
/*命名空间*/
namespace N1
{
	int a;//1.命名空间可以定义变量
	int aplus(){}//2.也可以定义函数
	namespace N2//3.命名空间也可以嵌套定义
	{
		int b;
	}
}
namespace N1//4.编译器允许多个相同的命名空间，编译器会自动合成一个
{
	int a;//5.这是错误的，因为这同一个命名空间，重复定义了
}
/*6.命名空间使用*/
//"::"在C++中是作用域限定符
//命名空间名称::命名空间成员
int test_1()
{
	N1::a = 10;//将命名空间中的成员a赋值为10
}
/*7.使用using 命名空间名称::命名空间成员*/
using N1::a;
int test_2()
{
	a = 10;//这样就可以直接使用
}
/*8.使用using 命名空间名称 将所有成员导入*/
using namespace N1;
int test_3()
{
	a = 10;//将命名空间中N1所有成员都引入
}
/*-------------------------------------------------------------*/
/*函数重载*/
int add(int x,int y)
{
	return x + y;
}
double add(double x, double y)
{
	return x + y;
}
//函数名相同，接受形参不同就是重载
//形参不同指参数个数、类型、顺序不同
//仅仅是函数返回类型不同不能说重载
/*-------------------------------------------------------------*/
/*引用*/
int main()
{
	int a = 10;
	int& b = a;
	//1.和指针不同的是，这里的b不是引用变量，是给a取别名
	//也就是说没有创建任何什么什么类型的变量，只是别名，不占空间
	//2.引用在定义时必须初始化，这一点和指针也不一样
	//3.一个变量可以有多个引用
	//4.一个引用只能引用一个实体，不能改变,看下面
	int c = 20;
	b = c;//这句话是指将c的值赋给a，b还是引用a
	//5.引用也分常引用和普通引用
	const int& d = a;//可以
	const int e = 10;
	int& f = e;//不行，因为普通引用不能引用常量
	//6.引用可以作为参数，效果和传入指针类似
	//7.引用作为函数返回值要小心，不能将局部变量作为返回引用
	//因为函数销毁，局部变量销毁，引用个蛋
	//8.没有多级引用
}

面向对象


/*-------------------------------------------------------------*/
/*类*/
//c中结构体只能定义变量，但是C++中结构体还能定义函数
struct N//用结构体来定义类，默认可见度是公共
{
	int a;//成员变量
	int b()//成员函数
	{
		return 0;
	}
};//别忘记分号
//C++中还喜欢用class来定义
class N//用class定义类默认是私有
{
	int a;//成员变量
	int b()//成员函数
	{
		return 0;
	}
	void Show();
};//别忘记分号
void N::Show()//在类体外定义类中成员需要使用::作用域解析符指明哪个作用域
{
	cout << "" << endl;
}
/*-------------------------------------------------------------*/
/*构造函数*/
//与类名相同，目的不是开辟空间，是初始化对象
//并且只能赋初值，而不是初始化变量，因为可以在构造函数中多次赋值
/*-------------------------------------------------------------*/
/*析构函数*/
//无参无返回值，是真的无返回值，而不是void
//一个类有且仅有一个析构函数，不显示定义的话就使用默认的
//先构造的后析构，后构造的先析构，是的，使用的栈
/*-------------------------------------------------------------*/
/*拷贝构造函数*/
Data d1(2024,9,22);//Data类对象d1，构造函数参数为2024,9,22
Data d2(d1);//使用拷贝d1对象的构造参数来构建构造函数
/*-------------------------------------------------------------*/
/*static成员*/
//静态成员为所有类对象共享，不属于某个具体对象
//非静态变量归属于对象，静态函数不是对象的一部分，无法用静态函数访问对象中的变量
//静态成员变量一定在类外进行初始化，定义还是在类里面定义
class Test
{
private:
	static int _n;
};
// 静态成员变量的定义初始化
int Test::_n = 0;//虽然是私有，但是静态变量初始化可以从外部访问
//静态成员函数可以访问静态成员变量
/*
* 绕了半天就两个问题
* 1、静态成员函数可以调用非静态成员函数吗？
 2、非静态成员函数可以调用静态成员函数吗？
1.不可以
2.可以
*/
/*-------------------------------------------------------------*/
/*友元类*/
//友元类的所有成员函数都可以是另一个类的友元函数
// 都可以访问另一个类中非公有成员
class A
{
	friend class B;
	A(int n=0)
		:_n(n)//构造函数初始化列表中的变量
	{}
private:
	int _n;
};
class B
{
	void T(A& a)
	{
		a._n;//可以调用友元类中的私有变量
	}
};
//重点！
// 1.友元类是单向的，不具有交换性
// 2.友元关系不能传递
/*-------------------------------------------------------------*/
/*内部类*/
//定义在一个类中的类就是内部类
//唉😔，很可怜
//1.内部类是独立类，不属于外部类，不能通过外部调用内部类
//2.外部类对内部类没有优越访问权限
//3.内部类是外部类的友元类，就是说内部类可以访问外部所有成员，但是外部类不行
//4.外部类的大小与内部类无关

内存管理


/*C++内存管理*/
             程序中内存区域划分
--------------------------------------------
|                内核空间
|
|
|	        栈(向下增长)
|		     ↓
|
|
|		*内存映射段*
|
|
|		    ↑
|		堆(向上增长)
|
|
|
|	    数据段(全局数据、静态数据)
|
|           代码段(可执行、常量)
|
--------------------------------------------
栈又叫堆栈，用于存储非静态局部变量/函数参数/返回值。

内存映射段是高效的I/O映射，进程之间通信

堆用于存储运行时动态内存分配

数据段也称：静态区，存储全局数据，以及静态数据

代码段也叫常量区，存放可执行的代码和只读常量

栈开辟空间是从地址高处向下开辟的，所以是向下

堆区开辟空间，是先开辟空间地址较低处开始

int a = 10;
int b = 20;
int* c = (int*)malloc(sizeof(int) * 10);
int* d = (int*)malloc(sizeof(int) * 10);
在上面的四个变量中，a和b是存储在栈区，先开辟的地址高
也就是a的地址高于b

c和d是存储在堆区，后开辟的地址高
也就是d的地址高于c
后开辟的也不一定高，因为如果前面的某个地址被释放了，就会放前面去

----------------------------C中的内存管理--------------------------------------
malloc  calloc   realloc   free
1.malloc
开辟指定大小空间，成功返回首地址，并且是void*, 需要强制转换，失败就是NULL

2.calloc
开辟指定大小空间，给明个数，以及每个大小，成功为首地址，失败NULL
开辟好以后将每一个字节初始化为0

3.realloc
可以调整已经开辟好的动态内存大小
二个参数：
第一个是需要调整的内存的首地址
第二个是调整后的新大小
调整大小三种情况
1.原地 后面有足够空间
2.异地 后面没有，重新找新地方，自动释放原来地方，并且拷贝数据到新地方
3.失败 后面和堆区都没有足够空间

4.free
释放空间
---------------------- - 面向对象中的内存管理--------------------------------------
1.动态申请某个类型的空间
int* p1 = new int;//申请
delete p1;//销毁
等价于
int* p1 = (int*)malloc(sizeof(int));
free(p1);

2.动态申请多个类型的空间
int* p1 = new int[10];
delete[] p1;
等价于
int* p1 = (int*)malloc(sizeof(int) * 10);
free(p1);

3.动态申请某个类型空间并且初始化
int* p1 = new int(10);
delete p1;
等价于
int* p1 = (int*)malloc(sizeof(int));
*p1 = 10;
free(p1);

4.动态申请多个类型的空间并初始化
int* p1 = new int[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
delete[] p1;
等价于
int* p1 = (int*)malloc(sizeof(int) * 10);
for (int i = 0; i < 10; i++)
{
	p1[i] = i;
}
free(p1);

总的来说，new会调用构造函数，而delete会调用析构函数

operator new 和 operator delete 函数与malloc和free用法完全一样
operator new 和 operator delete的底层就是malloc和free
只不过前者加了一个抛异常
new 和 delete 的底层是 operator new 和 operator delete
不过 new 和 delete 分别加了调用构造函数和析构函数

注意malloc和free是函数
而 new 和 delete 是操作符
并且malloc 和free不会初始化
并且malloc 和free要手动计算大小
并且malloc返回的是void*，需要强制转换
new和delete还会调用构造函数和析构函数
----------------------------------------------------------------
内存泄露
1.堆内存泄露
	就通过malloc、new、等等分配的内存，堆被用完了
2.系统资源泄露
	使用系统提供的资源，但是没有释放，就是无数个‘后台’，不用，还挂着

如何避免：
1.良好设计
2.智能指针
3.泄露检测工具

《模板》入门

            
/*函数模板和类模板*/
交换两数(整形或者浮点)
C的解决办法
void Swa(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
void Swb(double* p1, double* p2)
{
	double temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

C++:函数重载(函数名一样，根据传入参数自动选择)
void Swa(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
void Swa(double* p1, double* p2)
{
	double temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

看上去，貌似C++合理了点，但是代码量是一样的
所以：
             泛型编程
编写与类型无关的通用代码，实现代码复用，模板是泛型编程的基础

模板分为：函数模板和类模板

函数模板
	模板与类型无关
函数模板的形式

----------------------------------------------------
template < typename T1,typename T2,...,typename Tn>
返回类型 函数名(参数列表)
{
	//函数体
}
----------------------------------------------------
template< typename T>
void Swa(T & x, T & y)
{
	T temp = x;
	x = y;
	y = temp;
}

注意template、typename是关键字，可以使用class替代，但是不能用struct
在c++中可以使用class替代struct

函数模板就是个蓝图，本身不是函数，是编译器产生具体函数的模具
编译器根据传入的实际参数类型来推演生成对应类型的函数以供调用
当使用int类型调用函数模板时，会将T确定为int类

隐式实例化：让编译器来推演类型
template< typename T>
T Add(const T& x, const T& y)//int Add(const int& x,const int& y)
{
	return x + y;
}
int main()
{
	int a = 10, b = 20;
	int c = Add(a, b);//在c++中形参是引用，从而不必像C那样传入&a，和&b
	return 0;
}

值得注意的是
int a = 10;
double b = 1.1;
int c = Add(a, b);
//编译是失败的，因为不会进行类型转换
//具体就是编译器见到第一个a是int，将T定为int
//然后见到b是double，又推演为double
//并且模板参数只有一个T，无法确定是哪一个是T
//所以我们就会有显式实例化

显式实例化：指定模板参数的实际类型
template< typename T>
T Add(const T& x, const T& y)
{
	return x + y;
}
int main()
{
	int a = 10;
	int b = 5;
	int c = Add< int>(a, b);//指明类型
	return 0;
}
//指定以后，如果不符合int，编译器会转化，但是转化不成功，还是报错
----------------------------------------------------------------
函数模板的匹配原则

1.非模板函数和同名模板函数可以同时存在，优先调用非模板函数
int Add(const int& x, const int& y)
{
	return x + y;
}
template< typename T>
T Add(const T& x, const T& y)
{
	return x + y;
}
int main()
{
	int a = 10;
	int b = 5;
	int c = Add(a, b);//调用的是非模板函数
	int d = Add< int>(a, b);//调用的实例化的模板函数
	return 0;
}
2.非模板函数(普通函数)可以将实参自动类型转化，但是模板函数不允许
3.如果模板函数比起非模板有着更好的匹配，那么就选择模板
----------------------------------------------------------------
类模板
格式：
template< class T1,class T2,...,class Tn>
calss 类模板名
{
	//类成员声明
}
--------------------------------------------
例如：
template< class T>
class Score
{
public:
	void Print()
	{
		cout << "" << endl;
	}
private:
	T _Math;
	T _English;
};

//类模板中成员函数的定义若是放在类外定义，需要加模板参数列表
template< class T>
class Score
{
public:
	void Print();
private:
	T _Math;
	T _English;
};
template< class T>//需要加上参数列表
void Score< T>::Print()//命名空间的引用
{
	cout << "" << endl;
}
注意：模板不支持分离编译，声明在.h文件中，定义在.cpp文件中是不允许的
实例化：
Score< int> s1;
Score< double> s2;
类模板不是类，实例化后的才是类

《模板》进阶

           
非类型模板参数
模板的参数分为
	类型形参：class或者typename 后的
	非类型形参：使用一个常量作为参数，在模板中可以使用该参数作为一个常量

template< class T,size_t N>//size_t其实简单理解：无符号整型
class SA
{
public:
	size_t arraysize()
	{
		return N;
	}
private:
	T _arrayp[N];
};
使用非类型模板参数以后，就可以实例化对象的时候指定创建静态数组的大小
int main()
{
	SA< int, 10> a1;//在类成员中创建了大小为10的数组
	SA< int, 1000> a2;//创建了大小为1000的数组
}
重点：
1.非类型模板参数只允许使用整形家族(int,long int,unsigned int 等等)
2.浮点、类对象、字符串是不允许使用为非类型参数
3.非类型模板参数在编译时就要确定结果，编译器在编译阶段就要根据传入的非类型参数生成对应类或者函数

--------------------------------------------------------------------------------
模板的特化
步骤：
1.首先要有基础的函数模板
2.关键字template后面接一对空的尖括号<>
3.函数名后跟一对尖括号,尖括号指定需要特化的类型
4.函数形参表必须和模板函数的基础参数完全相同

template< class T>
bool IsEqual(T x, T y)
{
	return x == y;
}
cout << IsEqual(1, 1) << endl; //1
cout << IsEqual(1.1, 2.2) << endl; //0
这样使用是没有问题的，它的判断结果也是我们所预期的，但是我们也可能会这样去使用该函数模板
char a1[] = "2021dragon";
char a2[] = "2021dragon";
cout << IsEqual(a1, a2) << endl; //0
判断结果是这两个字符串不相等，这很好理解，因为我们希望的是该函数能够判断两个字符串的内容是否相等，而该函数实际上判断是确实这两个字符串所存储的地址是否相同，这是两个存在于栈区的字符串，其地址显然是不同的。
类似于上述实例，使用模板可以实现一些与类型无关的代码，但对于一些特殊的类型可能会得到一些错误的结果，此时就需要对模板进行特化，即在原模板的基础上，针对特殊类型进行特殊化的实现方式



//基础函数模板
template< class T>
bool IsEqual(T x, T y)
{
	return x == y;
}
//针对char*类型的特化
template<>
bool IsEqual< char*>(char* x, char* y)
{
	return strcmp(x, y) == 0;
}


全特化：将模板参数列表所有参数都确定化
偏特化：任何针对模板参数进一步进行条件限制设计的特化
偏特化包含部分特化以及参数进一步被限制
进一步被限制就是说，指明参数是全部引用，还是全部是指针的时候就调用

---------------------------------------------------------------------
模板的分离编译
//一个程序（项目）由若干个源文件共同实现，而每个源文件单独编译生成目标文件，最后将所有目标文件链接起来形成单一的可执行文件的过程称为分离编译模式。
在分离编译模式下，我们一般创建三个文件
一个头文件用于进行函数声明
一个源文件用于对头文件中声明的函数进行定义
最后一个源文件用于调用头文件当中的函数

程序运行经历的四个步骤：
1.预处理：头文件展开，去注释，宏替换，条件编译
2.编译检查代码，没有错误编译成汇编语言
3.汇编：把编译阶段生成的文件转成目标文件
4.链接：将生成的各个目标文件进行链接，生成可执行文件
模板分离编译失败的原因：
在函数模板定义的地方（Add.cpp）没有进行实例化，而在需要实例化函数的地方（main.cpp）没有模板函数的定义，无法进行实例化。
总的就是说，用的时候定义。不用就别定义。不要分离编译

继承和友元

            
/*继承*/
在保持原有特性的基础上进行扩展，增加功能，这样的新类，称为派生类
举例：
class Person//父类
{
public:
	void Print()
	{
		cout << "" << endl;
	}
protected:
	string _name = "";//名字
	int _age = 18;//年龄
};

class Student : public Person//子类(派生类)
{
protected:
	int _stuid;//学号
};

class Teacher : public Person//子类(派生类)
{
protected:
	int _jobid;//工号
};
子类是继承自父类的
继承以后，父类中的成员，包括成员函数和成员变量都是子类的一部分，自动复写
继承方式和访问限定符
1.public
2.protected
3.private
public继承:基类的private派生类中不可见，其他按父类的限定
protected继承:基类的private在派生类不可见,其他父类的一律在子类中变成protected
private继承:基类的private在派生类中不可见,其他父类的一律在子类中变成private

使用继承时也可以不指明继承方式，使用class时默认为private，使用struct默认是public
----------------------------------------------
//基类
class Person
{
public:
	string _name = "张三"; //姓名
};
//派生类
class Student : Person //默认为private继承
{
protected:
	int _stuid;   //学号
};
-----------------------------------------------
//基类
class Person
{
public:
	string _name = "张三"; //姓名
};
//派生类
struct Student : Person //默认为public继承
{
protected:
	int _stuid;   //学号
};
---------------------------------------------- -
基类和派生类对象赋值转换
class Person//基类
{
protected:
	string _name;//姓名
	string _sex;//性别
	int _age;//年龄
};
class Student : public Person//派生类
{
protected:
	int _stuid;//学号
};

Student s;//定义了一个派生类对象
Person p = s;//派生类对象赋值给基类对象
Person* ptr = & s ;//派生类对象赋值给基类指针
Person& ref = s;//派生类对象赋值给基类引用
//感觉与我们的观点有点不同，怎么儿子可以给老子赋值了？
//不应该是 老子的东西可以赋值给儿子吗，毕竟儿子拥有老子的一切特性
这个现象就是《切片/切割》，就只是把派生类中基类的部分赋值
派生类对象赋值给指针，也同样切片了，基类指针指向的派生对象也只剩下基类中有的成员
同理，派生类对象赋值给引用也是

注意：基类对象不能赋值给派生类对象
但是基类指针可以通过强制转换赋值给派生类的指针
此时基类指针必须指向派生类对象才是安全的
基类指针当然可以指向派生，前面都说了，儿子可以赋值给老子

---------------------------------------------------------------------------
继承的作用域
子类和父类中有同名成员，子类成员将屏蔽父类对同名成员的直接访问
这叫隐藏，也是重定义
class Person//父类
{
protected:
	int _num = 111;
};
class Student : public Person
{
protected:
	int _num = 999;
};

此时访问子类的_num成员是显示999

如果实在想要访问父类
加上作用域限定符
Person::_num
就是111了
-----------------------------------------------------
//父类
class Person
{
public:
	void fun(int x)
	{
		cout << x << endl;
	}
};
//子类
class Student : public Person
{
public:
	void fun(double x)
	{
		cout << x << endl;
	}
};
int main()
{
	Student s;
	s.fun(3.14);       //直接调用子类当中的成员函数fun
	s.Person::fun(20); //指定调用父类当中的成员函数fun
	return 0;
}
---------------------------------------------------- -
这不是函数重载，函数重载是在同一个作用域

-------------------------------------------------------
派生类的默认成员函数
//一共有6个
初始化和清理：构造函数和析构函数
拷贝和赋值：使用同类的对象去初始化一个新创建的对象，赋值是把一个对象赋值给另一个对象
取地址重载：普通对象和const对象的取地址
-------------------------------------------------------
class Person
{
public:
	Person(const string& name = "peter")//构造函数
		:_name(name)//初始化成员为构造函数中指定字符串
	{
		cout << "" << endl;
	}
	Person(const Person& p)//拷贝构造函数
		:_name(p.name)
	{
		cout << "" << endl;
	}
	Person& operator = (const Person& p)//赋值运算符重载函数
	{
		cout << "" << endl;
		if (this != &p)
		{
			_name = p.name;
		}
		return *this;
	}
	~Person()//析构函数
	{
		cout << "" << endl;
	}
private:
	string _name;//姓名
};

===========================================================================
//派生类
class Student : public Person
{
public:
	//构造函数
	Student(const string& name, int id)
		:Person(name) //调用基类的构造函数初始化基类的那一部分成员
		, _id(id) //初始化派生类的成员
	{
		cout << "Student()" << endl;
	}
	//拷贝构造函数
	Student(const Student& s)
		:Person(s) //调用基类的拷贝构造函数完成基类成员的拷贝构造
		, _id(s._id) //拷贝构造派生类的成员
	{
		cout << "Student(const Student& s)" << endl;
	}
	//赋值运算符重载函数
	Student& operator=(const Student& s)
	{
		cout << "Student& operator=(const Student& s)" << endl;
		if (this != &s)
		{
			Person::operator=(s); //调用基类的operator=完成基类成员的赋值
			_id = s._id; //完成派生类成员的赋值
		}
		return *this;
	}
	//析构函数
	~Student()
	{
		cout << "~Student()" << endl;
		//派生类的析构函数会在被调用完成后自动调用基类的析构函数
	}
private:
	int _id; //学号
};

===========================================================================
1.派生类的构造函数被调用时，会自动调用基类的构造函数初始化基类那一部分成员
如果基类没有默认的构造函数，则必须在派生类构造函数的初始化列表中显示调用基类的构造函数
2.派生类的拷贝构造函数必须调用基类的拷贝构造函数完成基类成员的拷贝构造
3.派生类的赋值运算符重载函数必须调用基类的赋值运算符重载函数完成基类成员的赋值
4.派生类的析构函数会在被调用完成后自动调用基类的析构函数清理基类成员
5.派生类对象初始化时，会先调用基类的构造函数再调用派生类的构造函数
6.派生类对象在析构时，会先调用派生类的析构函数再调用基类的析构函数
===========================================================================
1.派生类和基类的赋值运算符重载函数因为函数名相同构成隐藏，因此在派生类中调用
基类赋值运算符重载函数，需要使用作用限定符指定
2.派生类和基类的析构函数也会因为函数名相同构成隐藏，如果在派生类中调用，也需要指定

接下来该看继承和友元

C++难点、混淆点总结

1.一个类的静态数据成员所表示属性是类的属性或对象的属性？
错误的，只是类的属性，因为静态数据成员，不会成为对象消失的时候消失的大怨种
又不是古代了，陪葬的恶习早没了，人都是独立个体，静态说我也是
--------------------------------------------------------------
2.静态成员函数对类的数据成员访问可以是静态数据成员也可以是非静态数据成员？
错误的，静态成员函数不随着对象的消失而消失，什么意思？就是说静态成员函数不接受隐含的this指针
所以它不能访问自己类的非静态成员（包括函数和数据）
不过你也可以结合上一题，静态成员是类的的属性。就能够大致理解了
一定会骂街：你这说的是人话吗？能不能讲明白点，臭傻蛋
好吧☝🏿☝🏻（我可不会骂人，我只是模仿你的语气）
this指针就是区别于外部变量和内部变量的作用，外部变量与内部变量是一样的很难区别(只有程序区别不了，毕竟人工智障)
这个时候程序给你一个工具，让你用这个工具来帮它区别开
但是问题是静态成员，是不随对象毁灭的，也就是说你上一秒指的，下一秒就没了
和男人的嘴一样。所以静态对象是没有this指针的
看下面程序，你就知道this指针是什么了

class Box {
    int length;  // 定义私有的整型成员变量length
public:
    Box(int length) {
        this->length = length;  // 构造函数，初始化成员变量length
    }

    int getLength() {
        return this->length;  // 访问成员变量length
    }

    void display() {
        std::cout << "Length: " << this->getLength() << std::endl;  // 类的成员函数，访问成员变量length和其他函数
    }
};

发现没有，成员函数形参是len，结果类成员数据也有叫len的，然后还执行赋值
如果没有this指针就是length = length;
你说可怕不？this指的就是类成员而不是传入的参数
疑问来了，为什么不改参数的名称？换一个，不就不用this指针了吗？
唉，你应该明白，总有人喜欢挑战极限
还记得模板吗？泛型编程
所有类和函数全部用模板生成，几百个模板，模板到最后，给自己都干傻了
如果你不知道这种笑话，那你总知道宏定义吧？
类似所有的代码全部用宏定义写。宏定义都不知道？
算了，右上角有个X号，退出。
--------------------------------------------------------------
3.inline函数可以是虚函数
类中定义的函数默认都是内联函数
在类中说明，类体外如果不加inline说明的定义，均不是内联了
包含循环语句和分支语句的函数不能成为内联
--------------------------------------------------------------
4.静态成员函数不能是虚函数
静态成员函数没有this指针，无法访问虚表，虚表就是实现继承多态的关键
--------------------------------------------------------------
5.构造函数不能是虚函数
因为对象中的虚表指针是在构造函数初始化列表阶段才初始化
--------------------------------------------------------------
6.析构函数可以是虚函数
--------------------------------------------------------------
7.对象访问普通函数更快还是虚函数更快？
对象访问普通函数比虚函数快，因为访问虚函数的时候，需要找到虚表指针，指针在虚表中找到对应虚函数，才能调用
--------------------------------------------------------------
8.
函数模板的实例化是由编译程序在处理函数调用时自动完成的，而类模板的实例化必须由程序员在程序中显式地指定
--------------------------------------------------------------
9.traits
 traits是C++的自动类型判断。
  出发点：因为C++没有反射的机制。所以利用traits来完成。
  大量使用场景：STL（STL中大量使用traits来区分类别。注释POD标量类型和类类型的构造函数等）

  机制：

template < typename T>
//泛化
struct is_void
{ static const bool value = false; };
template <>
//特化
struct is_void< void>
{ static const bool value = true; };

int main(){
    std::cout<< is_void< int>::value;
    std::cout<< is_void< void>::value;
}

  根据模板的自动类型推导。在调用void的时候会使用特化版本。而其他类型呢？对，使用泛化版本。
  这样就巧妙的区分了不同的类型。这就是traits的基本原理。
--------------------------------------------------------------
10.类模板的成员函数都是函数模板
--------------------------------------------------------------
11.没使用过的成员函数（即函数模板）不会被实例化
--------------------------------------------------------------
12.free()对应的是malloc()，delete对应的是new
--------------------------------------------------------------
13.构造函数权限为protected，在类外除了继承的方式，无法实例化对象。 
--------------------------------------------------------------
用new创建对象时，要调用构造函数
new创建n个对象的对象数组，系统调用n次构造函数
delete必须用于由运算符new返回的指针，人话：打狗也得看主人
delete可以用于空指针
一个指针只能使用一次delete操作
delete[] ptr;无论ptr指向的是什么，是多少维，都是这样一个[]
delete删除对象的时候是需要调用析构函数的，对象数组有几个就调用几次
--------------------------------------------------------------
析构函数本身并不收回之前分配的内存空间
--------------------------------------------------------------
成员函数在类体内默认是内联函数，但是在类体外定义时不是内联函数
--------------------------------------------------------------
protected声明的数据，只能被类的成员函数访问，即创建对象，通过对象.变量是不允许的
--------------------------------------------------------------
析构函数不能有参数，以及返回值类型
构造函数不能有返回值类型
--------------------------------------------------------------
构造函数在声明时给出了默认值的话，定义时不能再设定默认值
--------------------------------------------------------------
函数在类中声明时指定了类型，那么在类外定义时也需要指定类型，如果不指定默认为int，并且C++不支持默认int
别想了，定义指定，声明不指定，也不行
除非你声明以及定义都不指定，不过这样有些地方不行，2022的vs就报错
--------------------------------------------------------------
引用
1.对void进行引用不允许
2.不能建立引用的数组
3.没有引用的引用
4.引用不能用类型初始化 int &a = int;不行
5.没有空引用
6.引用能够使用任何合法变量
7.引用不是变量，引用必须初始化，以后不能修改
8.引用不占内存，只有说明无定义，并且只有说明时带&
9.引用做函数形参的时候具有指针的效果
引用返回值
int &f(int x)
{
    ....
}
一个函数返回引用，此函数可以直接当做左值来运算
例如 f(3)+=10;//因为函数返回值是一个引用，引用是一个变量本身，其实就是一个变量在做运算
返回的时候一定要注意不是本函数的局部变量时可以返回一个引用
而且只有变量才能成为引用的返回
常引用
const int & n =x;
不能通过n来修改x的值
但是x自己是可以修改的
其次，只有常成员函数才能操作常数据成员
--------------------------------------------------------------
友元（函数和类）
需要类体内声明，friend为关键字,可以访问类的私有成员，但不是类的成员函数
友元的作用：提高程序的运行效率，但是破坏了类的封装性和隐蔽性
其次调用友元函数的时候不需要加上对象前缀
友元函数可以是多个类的友元
类的成员函数可以成为另一个类的友元函数，但是声明要加上前缀
class B
{
    friend void A::f();
}
友元类
一个类的友元类，其友元类的所有成员函数都是这个类的友元函数
友元函数如果重载，重载的也必须一个个声明，不可能声明一个，定义重载的时候好几个
--------------------------------------------------------------
(1)"."（类成员访问运算符）
(2)" .*"（类成员指针访问运算符）
(3) "::"（域运算符）
(4)"siezof"（长度运算符）
(5) " ?:"（条件运算符）
以上运算符不能重载
运算符的重载就是函数的重载
运算符的重载有4个不能改变
1.运算符操作个数
2.运算符原有优先级
3.运算符原有的结合性
4.运算符原有的语法结构
运算符重载有两种形式
1.成员函数
2.友元函数
利用成员函数对双目运算符重载，其左操作数为this指针，右操作数为成员函数参数
--------------------------------------------------------------
函数模板既可以与函数模板重载，也可以与非函数模板重载
--------------------------------------------------------------
在类模板中定义一个静态数据成员，有n个实例化的时候，也会有n个静态变量
--------------------------------------------------------------
有的情况下，派生类构造函数体为空，仅起到参数传递的作用，用来让基类带参构造函数得以初始化
--------------------------------------------------------------
派生类的构造函数的成员初始化列表中不能包含基类的子对象的初始化
因为基类构造函数不能够被继承。其对象的初始化由基类完成
--------------------------------------------------------------
指针引起的普通成员的调用，仅仅与指针类型有关，而与指针指向的对象无关
基类指针p，子类a，让p=&a,此时基类和子类中都定义了名who的函数
p.who();调用的是基类的who函数
--------------------------------------------------------------
只有同时满足三个条件，对虚函数的调用才是动态联编
1.类之间为基类和派生类关系
2.要有虚函数
3.调用虚函数操作的是指向对象的指针或者对象的引用，或者由成员函数调用虚函数
--------------------------------------------------------------
抽象类：带有纯虚函数的类
其派生类依然可以是抽象类
--------------------------------------------------------------
构造函数中不能调用纯虚函数，但是可以调用虚函数
--------------------------------------------------------------
是的，上面的那个who函数出现了与我们预期不符的，就是静态联编，可以使用虚函数来变成动态联编
--------------------------------------------------------------
编译时多态（静态）和运行时（动态）的多态
编译时多态是指一个类或一个函数中含有同名函数，根据参数列表(类型/个数)区别，通过静态联编实现
例如：一个类中不同参数的构造函数以及运算符重载函数
动态多态性指定义在一个类层次中不同类的重载函数，一般具有相同参数表，根据指针指向的对象所在类来区别语义，虚函数：正是在下。通过动态联编实现
--------------------------------------------------------------
C++种的异常由程序员控制引发，而不是计算机硬件或者程序运行环境控制
catch的捕获只能是类型而不是具体的值，捕获的东西是由throw抛出的
只要匹配到一个，后面的都异常处理都被忽略
展开栈：从try开始直到异常抛出这中间有多少个对象创建就有多少对象析构
--------------------------------------------------------------
--------------------------------------------------------------
--------------------------------------------------------------

C++全面讲解

觉得页面太小点击下面链接 C++

0	^
1	->	56	->	23	->	45	^
2	^
3	^
4	->	15	->	37	^
5	^
6	->	17	->	28	^
7	->	51	->	73	^
8	->	41	^
9	->	31	^
10	^

呵呵，背吧哥们🤣🐒🫵🏿	最好时间复杂度	最坏时间复杂度	平均复杂度	辅助空间复杂度	稳定性
直接插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
折半插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
希尔	O(n)	O(n²)	O(n的1.3次方)	O(1)	不稳定
冒泡	O(n)	O(n²)	O(n²)	O(1)	稳定
快排	O(nlog₂n)	O(n²)	O(nlog₂n)	O(log₂n)	不稳定
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
2路归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定

文件使用模式	处理方式	指定文件不存在	指定文件存在
r	读取（文本文件）	出错	正常
w	写入（文本文件）	建立新文件	原有内容丢失
a	添加（文本文件）	建立新文件	原有内容后添加
rb	读取（二进制文件）	出错	正常
wb	写入（二进制文件）	建立新文件	原有内容丢失
ab	添加（二进制文件）	建立新文件	在原有内容后添加
r+	可读取，又可写入	出错	打开文件时，文件指针位于文件开头，无论是读取内容还是写入内容，都可在文件中任意位置进行，且进行写入操作时，会覆盖原有位置的内容。
w+	写/读	建立新文件	打开文件时，文件指针位于文件开头，文件原有内容丢失，无论是读取内容还是写入内容，都可在文件中任意位置进行
a+	读/添加	建立新文件	打开文件时指针位于文件末尾，在文件原有末尾添加，读取内容时，可以在任意位置进行，但写入内容时，只会追加在文件尾部。
rb+	读写	出错	正常
wb+	写读	建立新文件	原有内容清除
ab+	读添加	建立新文件	文件末尾添加

0	^
1	->	56	->	23	->	45	^
2	^
3	^
4	->	15	->	37	^
5	^
6	->	17	->	28	^
7	->	51	->	73	^
8	->	41	^
9	->	31	^
10	^

0	^
1	->	56	->	23	->	45	^
2	^
3	^
4	->	15	->	37	^
5	^
6	->	17	->	28	^
7	->	51	->	73	^
8	->	41	^
9	->	31	^
10	^