数据结构学习笔记

顺序表的动态实现：
typedef struct
{
ElemType *data;//存储顺序表中元素的首地址
unsigned int maxsize;//顺序表最大长度
unsigned int length;//顺序表元素个数
}SeqList，*PSeqList;

归并算法：有两个顺序表AB，两个顺序表首元素比较，符合条件的(假如是A表的首元素)那个放到新建表里，然后B表的首元素继续和A表的第二个比，直到一个表全部比完，剩下的归并到新表

单链表：
typedef struct LNode
{
ElemType data;//存放节点数据元素
struct LNode* next;//指向下一个节点的指针
}LNode,*Linklist;
Linklist LL;//强调声明一个链表

递归实现：递归是层的概念，自己调用自己，递去归来，如果符合return的条件，就退出当前的层，回到上一层执行完剩下的内容

顺序栈：
typedef struct
{
int data[max];//用数组存放元素
int top;//“栈顶指针”
}SeqStack,*PSeqStack;

链栈：
1.初试化：分配头结点
2.入栈：每次在头结点后插入
3.出栈：在头节点后删除

循环队列：移动头指针和尾指针，因为数组大小是固定的，队底进满了就在头进，然后尾指针移到上面
队尾位置：if(rear>maxsize)rear = rear - maxsize;/rear = rear%(maxsize)+1
队长length = (rear - front + 1 +maxsize)%maxsize
链式队列：尾部入队，头部出队（比单链表多一个尾指针）
1.初始化：生成一个头节点，然后让front指针和rear指针都指向头结点
2.入队：直接在尾指针后加
3.出队：直接让头指针的next指向取出元素的next，如果是出队的是最后一个节点的话，将头指针赋给尾指针

串：
typedef struct
{
char* data;//存放首元素地址
unsigned int maxsize;//字符串最大长度
unsigned int length;//实际长度
}string;

字符串匹配算法
BF算法：目标串A和模式串B，都有一个指针，逐个对比，不符合就将B串的指针下移一位，将A串的指针重新回溯到第一位
KMP算法：如果一次比较没符合，目标串指针每次移到到下一位，模式串可以不回溯到第一位，回溯的位置由比较失败后前面字符串的前缀和后缀决定
目标串ababddgghr
模式串ababc
比较到ababc最后一个c时，目标串是d，不符合，然后看目标串的abab，前缀有a、ab、aba，后缀有b、ab、bab，相同的最大长度的是ab，则回溯到（最大长度+1）2+1=3的位置，即回到第二个a的位置继续比
根据模式串算nextval数组：例如模式串ababc:
含失败的对比串 除去失败 回溯的位置
a 空 0（固定）
ab a 1（固定）
aba ab（a b） 0+1=1
abab aba(a、ab和a、ba) 1+1=2
ababc abab(a、ab、aba和b、ab、bab) 2+1=3
对应的next数组（减1）：-1 0 0 1 2
KMP算法优化（优化next数组）
如 a a a a a a
-1 0 1 2 3 4
-1 -1 -1 -1 -1 -1(第一位固定一样，第二个a回到的位置是第一个，然后对比两个字符，一样就用相同的nextval值)
又如b a a b a a
-1 0 0 0 1 2

• -1 0 0 -1 0 0

顶点的度：与顶点相关联的边的条数
入度：以该定点为终点的边的条数（出度是起点）
路径（顶点序列）、回路（第一个顶点和最后一个顶点相同的路径）、连通（无向图）、强连通（有向图）
连通图（任意两个顶点都是连通的，顶点为n最后n-1条边）
强连通图（顶点为n—n条边）

图的数组表示法（邻接矩阵）
typedef struct{
char vexs[maxsize];//顶点的最大数值
int edges[maxsize][maxsize];//二维数组表示边表（邻接矩阵）
int vexnum,arcnum;//图的顶点数[V]和边数[E]
}MGraph;
在无向图的邻接矩阵，顶点的度为该点所在的行或列中非0个数
在有向图的邻接矩阵，顶点的出度为所在行的非0个数，入度为所在列的非0个数
带权的直接将权值写入邻接矩阵就好
空间复杂度是O(|V|^2),求度的时间复杂度O(|V|)【遍历某行/列】

图的邻接表（有数据冗余）：
typedef struct VNode{
VertType data;//顶点的信息
ArcNode first;//顶点的第一条边
}VNode;//顶点的结构体
typedef struct ArcNode{
int adjvex;//边指向的顶点的数组下标（伪指针）
InfoType info;//边的相关信息（权值）
struct ArcNode next;//指向下一条边的指针
}ArcNode;//边链表的结构体
typedef struct{
VNode vexs[maxsize];//顶点的数组
int vexnum,arcnum;//图的顶点数和边数
}ALGraph;//图的结构体
无向图中，边链表的节点数是2|E|，空间复杂度是O(|V|+2|E|)，求顶点度的时间复杂度是O（1)【遍历待求顶点的链表就行】

有向图中，边链表的节点数是|E|，空间复杂度是O(|V|+|E|)，求顶点的出度的时间复杂度是O(1)，入度是O(|E|)

图的十字链表[适用有向图]（就是原有的连接表再加上一个入度的链接表）：
边链表的节点总数是|E|，空间复杂度是O(|V|+|E|)，顶点的入度和出度的时间复杂度O(1)~O（|E|）

图的邻接多重表[适用无向图]：
边链表的节点总个数是|E|,空间复杂度是O(|V|+|E|)，删除边和顶点的 *** 作很方便

图的基本 *** 作—>
1.判断图中是否存在顶点a到b的边：无向图的邻接表直接找a顶点的边链表，邻接矩阵直接数组下标，邻接矩阵最好的时间复杂度是O(1)，邻接表的最好O(1)【没有边】最坏复杂度是O(|V|)（连接了其他所有节点，遍历整条边链表来找）
有向图的差不多
2.列出顶点a和b邻接的边：无向图的邻接矩阵直接找a行/b行，邻接矩阵直接找，邻接矩阵最好的时间复杂度是O(|V|)(扫描一整行/列)，邻接表最好是O(1)最坏O(|V|)
有向图的邻接矩阵时间复杂度是O(|V|)+O(|V|)，邻接表的出度最好O(1),最坏O(|V|)，入边O(|E|)
3.插入顶点：都是O(1)
4.删除顶点：
5.插入一条边：O(1)

图的遍历：
广度：利用辅助数组和队列，先入队一个元素，然后出队，再将与其相关联的元素入队（入队就是标记为已访问元素，将辅助数组对应的位置置为true）
深度：利用辅助数组、栈和邻接表（进栈的顺序按照边链表的来）先进栈一个元素A，然后找与A相关联的元素入栈（一直有没访问过的相关联就一直进栈），直到某个元素B和它相关联的元素全部访问过，元素B出栈，然后继续查找上一个元素没访问的元素

最小生成树：
普里姆算法：从任意顶点开始生成树，依次将代价最小的其他顶点纳入生成树（O(n^2)）
克鲁什卡尔算法：纵观全图，每次选择权值最小的边，让这条边的两个顶点连通，如果两个顶点已有另外的路径实现了连通，则不选O(|E|log|E|)

链表：非连续的地址（数据域+指针域）
随机访问一般是下标

时间复杂度计算：1.只要没有循环等复杂结构，那就是O(1)
2.单一for循环O(n) 3.嵌套循环：O(n^…) 4.斐波那契数列的递归：O(2^n)
5.while循环里i每次乘2，越来越接近n 😮(logn) 6.上述结合

空间复杂度：1.已分配的临时空间不随变量值大小变化而变化O(1)
2.new一个数组int[n]，O(n)

线性表的存储方式又顺序存储和链式存储，查找的时间复杂度是O(1)

树形结构是非线性结构，是由分支关系定义的层次结构
节点的度（叉）：节点下一层有几个节点
节点深度：在第几层
节点高度：当前节点到其最远叶节点的长度
树的遍历方式：层次遍历和三大遍历
层次遍历是先上到下，先左后右（相当于每一层从左到右），实现方法用队列：先将根节点入队，进入循环—出队一个元素以及其子节点入队（没有子节点就继续出队一个元素）
遍历递归方案void PreOrder(BiTree TT){
if(TT == NULL) return;//先序放第一句，中序第二，后序第三句
visit(TT);PreOrder(TT->lchild);PreOrder(TT->rchild);
}
求二叉树高度：int TreeDepth(BiTree TT){ if(TT == NULL) return 0;
int ll = TreeDepth(TT->lchild);
int rr = TreeDepth(TT->rchild);
return ll }
非递归方案(栈实现)：1.从根节点出发，沿左节点依次入栈，直到左节点为空；
2.栈顶元素出栈
3.如果出栈元素有右节点，把右节点当成开始回到步骤1，若出栈元素没有右节点，回到步骤2
4.栈空即完成
（先序是在节点入栈前访问，中序是出栈后访问）

二叉树线索化：一棵二叉树，写出二叉链表，然后二叉树画图时用虚线补充，按 节点没有左子节点，就连前驱节点，节点没有右子节点，就连后继节点
线索二叉树求前驱后继：
1.先序求后继节点：如果当前节点的右指针存线索，则指向的是后继，若右指针存节点，取左节点为后继，没左节点就取右节点
2.后序求前驱节点：左指针左指针*******，取右节点******************
3.中序求后继：如果当前节点的右指针是线索，则指向的节点是后继；如果当前节点指向的右指针是节点，右子树的最左边节点为后继节点
中序求前驱：左*******************；左左右**
二叉排序树（BST）—>删除 *** 作：1.删除根/删除叶节点，释放内存即可；2.删除只有单子树的节点，子树代替自己；3.删除有双子树的节点，找自己左子树最右侧的节点代替自己（即当前位置节点值小但又是最大的那个值），然后删除那个节点/或者找右子树最左侧的节点（比自己大又是最小的那个）
树的遍历：先根遍历等于对应二叉树的先序遍历，后根遍历是对应二叉树的中序遍历
森林的遍历：先序遍历对应二叉树的先序遍历，中序遍历对应二叉树的中序遍历
【树/森林对应的二叉树是根据儿子节点放左下，兄弟节点接右下（很多兄弟就一直右下的右下，儿子也是）】
平均查找长度ASL—>成功：每个节点要比较的平均次数（第一层比较一次，第二层比较两次，因为是从第一层走向第二层），（每层数*每层节点数）的累加除于总结点数
失败：叶节点的虚空子节点比较平均次数（叶节点的两个虚空子节点比较次数/总虚空节点）

平衡二叉树（AVL）—>平衡节点：自己左子树的高度-右子树的高度
找最小不平衡子树调整：情况一外侧子树更高，只要旋转一次；内侧转两次（先找最小不平衡树，然后退一步看有问题的那边的子树按情况1转，转完后又是情况一），哪边子树高就转哪边，先搞小的再搞大的
旋转可以理解为收儿子，A原来是B的儿子，旋转后A收B当儿子，B站了一个儿子位，那如果A的那个儿子位有人，就要送给B当另一边的儿子作为补偿
平衡二叉树的最小节点数：An = A(n-1) + A(n-2) + 1; —> 1 2 4 7 12 … [类似斐波那契数列:1 1 2 3 5 8 13 …]
哈夫曼树（左走0，右走1）
带权路径长度：用节点的权值乘路径长度，而所有节点带权路径之和WPL最小，就是最优哈夫曼树
哈夫曼树构造：每次选两个出来相加得到新节点
红黑树规则：1.根节点为黑；2.叶节点为NULL且为黑；3.每个节点到叶子节点的所有路径，都包括相同数目的黑色节点；4.红色的孩子不能是黑的，黑的孩子节点可以黑

红黑树的插入 *** 作：
1.只有一个根节点（红色）时直接插入，然后根节点变黑
2.父节点是黑色时，新插红色不影响
3.新节点D的父节点B和叔叔节点C都红以及根A黑时，父节点B变黑，然后根节点A变红，叔叔节点C变黑
4.新节点D的父节点B红，叔叔黑或没叔叔，且新节点D是父节点B的右孩子，父节点B是根节点A的左孩子(即不直)，以B为轴左旋转，使D上升【或者D是B的右孩子，B是A的左孩子，以B为轴右旋转】，进入情况5
5.新节点D的父B红，叔叔黑或没叔叔，且D是B的左孩子，B是A的左孩子，以A为轴右旋转使B上升， *** 作和之前的旋转描述一样【B右D右同理】
红黑树的删除 *** 作
1.删除红叶节点
2.待删除的叶节点D为黑，D的兄弟节点E也黑，没有侄子节点—>删除D，父变黑，E变红
3.D黑，父节点P未知，兄弟E黑，有单侄子F红—>删除D，E颜色变P颜色，P和F变黑，旋转使E上升
4.D黑，父节点P未知，兄弟E黑，有双侄子FG红—>删除D，旋转使E上升，E变P色，P和同级的那个节点变黑
5.D黑，E红，P必黑，双侄子FG黑—>删除D，旋转使E上升，E变黑，P和同级变黑
6.删除节点只有左孩子/右孩子—>待删除节点颜色不变，用孩子的值代替原值，删孩子节点
7.删除节点有双孩子—>待删除节点值换成前驱的值，然后删除前驱节点，然后按上面的情况分析

单链表：
1.按节点的前插 *** 作（p节点前插入元素e）：先判p空？分配一个新的节点内存s，将s的后继指向p的后继，再将p的后继指向s，将p的元素数据赋给s的数据区，再把元素e赋给p的数据区；
按位序的插入：先判插入位置i是否合法？然后定义节点指针p从头节点（第0个节点，不存数据）移到待插位置i的前一个，判断i-1位置的是否空？分配一个链表类型的节点指针s，元素e赋给s的数据，，s的后继指向p的后继，p的后继给s

2.查找：找值，遍历比较；找第i个
3.反转：原地翻转（翻转某个节点p之后的所有值），新建节点ss和ssnext，用ss指向p的next，然后将p的next指向空，然后在ss非空的条件下将ss插到p的后面（ssnext是存放ss的下一位地址的，用来实现递增的效果）