数据结构提纲

线性表

线性表的概念

• 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列

线性表的操作

主要操作：

初始化 Initlist()
销毁 droplist()
插入 insertlist()
删除 deletelist()
按值查找 findbyvalue()
按位查找  findbylocat()

其他操作：

求表长
输出
判空（isempty）

顺序表

存储结构

逻辑相邻+地址相邻

实现方法

静态表： 数组实现
动态表： 指针实现（malloc或者new分配空间）

特点

随机访问，按位查找复杂度O(1)
存储密度高
扩展不方便
插入、删除不方便
代码

链表

链表的概念

链表：用链式存储实现的存储结构
单链表：有尾结点
代码
双链表：有头节点、尾结点
循环链表：有头节点、尾结点，且最后一个结构的尾结点指向第一个结构
静态链表：用数据进行实现的结构

顺序表与链表的比较

1. 顺序表的优点：
   支持随机存取、存储密度高
2. 顺序表的缺点：
   大片连续空间分配不方便，改变容量不方便
3. 链表的优点：
   离散的小空间分配方便，改变容量方便
4. 链表的缺点：
   不可随机存取，存储密度低
   顺序表和链表的逻辑结构都是线性结构，都属于线性表。但是二者的存储结构不同，顺序表采用顺序存储(特点，带来的优点缺点)；链表采用链式存储（特点、导致的优缺点）。由于采用不同的存储方式实现，因此基本操作的实现效率也不同。

栈和队列

基础概念与基本操作

栈的概念（stack）

• 栈是只允许在一端进行插入或删除操作的线性表
  特性：

  后进先出

重要词汇：

栈顶:允许插入和删除的一端
栈顶元素：栈顶位置的元素
栈底:不允许插入和删除的一端
空栈:没有元素的栈

栈的基本操作

初始化栈：initstack()
销毁栈：dropstack()
进栈：push()
出栈：pop()
返回栈顶元素：gettop()//与出栈相比不消除栈顶元素——栈大小不变

队列的概念（stack）

• 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表

特性：

先进先出
重要词汇：
队头:允许删除的一端
队头元素：队头位置的元素
队尾:允许插入的一端
队尾元素：队尾位置的元素
空队列:没有元素的队列

队列的基本操作

初始化队列：initqueue()
销毁队列：dropqueue()
进队：enqueue()
出队：outqueue()
返回队头元素：gettop()//与出队相比不消除对头元素——队列大小不变

顺序存储结构与链式存储结构

栈的顺序存储结构与链式存储结构

代码

队列的顺序存储结构与链式存储结构

代码

栈和队列的应用

栈的应用一——括号匹配

• 用栈实现括号匹配：
  依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检否匹配。
• 匹配失败情况：
  ①左括号单身
  ②右括号单身
  ③左右括号不匹配

  栈的应用二——算式求值

• 逆波兰表达式=后缀表达式
  正常的表达式：运算符在操作数之后

  操作数1 操作数2 运算符
  1+1 =》1 1 +  1+23=》123\+

• 波兰表达式=前缀表达式
  正常的表达式：运算符在操作数之前

  运算符 操作数1 操作数2
  1+1=》+11  1+23=》+1\23

• 中缀表达式：
  正常的表达式：运算符在操作数之间

  操作数1 运算符 操作数2
  1+1  1+2*3

1. 用栈实现后缀表达式的计算：
   ①从左往右扫描下一个元素，直到处理完所有元素
   ②若扫描到操作数则压入栈，并回到①；否则执行③
   ③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

2. 用栈实现前缀表达式的计算：
   ①从右往左扫描下一个元素，直到处理完所有元素
   ②若扫描到操作数则压入栈，并回到①；否则执行③
   ③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

3. 用栈实现中缀转后缀：
   初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
   从左到右处理各个元素，直到末尾。可能遇到三种情况：
   ① 遇到操作数。直接加入后缀表达式。
   ② 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到
   弹出“(”为止。注意：“(”不加入后缀表达式。
   ③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，
   若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
   按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

   栈的应用三——递归

   队列的应用

4. 树的层次遍历
5. 图的广度优先搜索
6. 操作系统的先来先去服务FCFS

串

串的概率和操作

串的基本概念

• 串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S = ‘a₁a₂······a_n‘ （n ≥0）
• 其中，S是串名，单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；
• 串中字符的个数n称为串的长度。
• n = 0时的串称为空串（用?表示）。

子串：串中任意个连续的字符组成的子序列。
主串：包含子串的串。
字符在主串中的位置：字符在串中的序号。
子串在主串中的位置：子串的第一个字符在主串中的位置

串的基本操作

串的匹配

pat: 用于匹配的字符串 对应子字符位置j
txt： 被匹配的字符串 对应子字符位置i

朴素匹配

暴力匹配
每个i都从头开始一次关于pat的匹配

KMP

1. 主要思路：
   求解一个用于字符串pat信息的数据——next
   如果p[j]位置与t[i]位置匹配失败，next会告诉我们pat字符串应该前进多少位置（当前位置在下一步应该用pat哪一个位置的来比较）
   匹配成功或者首字符就不匹配都会使两个串的位置均前进
2. 主要表示：
   表示被匹配的字符串的位置i不会回退
   j==0 是表示当前字符与第一个字符不匹配，因此ij++
3. next数据求解
   假设pat = ABCDABD
   3.1 常规方法
   找前缀子串和后缀子串的最大公共元素长度
   
   next为最大公共元素长度的后移且每项+1
   首字符置零
   3.2 状态机
   

   KMP优化

4. 需要优化的地方：
   以自动机为例，在上面例子中，状态6匹配字符若为other，则跳转状态2，此时字符会与2的状态在进行一次检测，这两次检测可以简化为单次检测
5. 优化方式

代码：

字符串

树

树

树的基本概念

• 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
  1）有且仅有一个特定的称为根的结点。
  2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

  节点之间的关系

• 父节点（双亲节点),孩子节点
• 祖先节点，子孙节点
• 兄弟节点，堂兄弟节点
• 节点之间的路径
• 路径长度

graph TD
    A --> B
    B --> C
    C --> E
    C --> D

节点、树的属性

• 节点的深度（层次）：从1开始，从上往下数
• 节点的高度：从1开始，从下往上数
• 树的深度：最大的层数
• 节点的度：子女的分支数
• 树的度：各节点中最大的度

树的性质

1. 总节点数 = 总度数 + 1
2. 度为m的树
   • 至少有一个节点度为m
   • 一定是非空树
3. m叉树
   • 所有节点的度小于m
   • 可以是空树
4. 节点数：
   • 度为m的树第i层最多有m^i-1个节点
   • 高度为h的m叉树最多有 $\frac{m^h-1}{m-1}$
   • 高度为h的m叉树最少有h个节点
   • 高度为h，度为m的树最少有h+m-1个节点
5. 具有n个结点的m叉树的最小高度为$\log_m(n(m-1)+1)$

二叉树

二叉树的基本概念

• 二叉树是n（n≥0）个结点的有限集合：
  ① 或者为空二叉树，即n = 0。
  ② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。
  左子树和右子树又分别是一棵二叉树。
  特点：
  ①每个结点至多只有两棵子树
  ②左右子树不能颠倒（二叉树是有序树）

特殊二叉树

1. 满二叉树:高度为h，节点数为2^h-1的二叉树
2. 完全二叉树：在满二叉树中最下一层，连续删除若干个节点得到完全二叉树。
3. 二叉排序树：左子树关键值 < 根节点关键值 < 右子树关键值
4. 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。

• 满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。

二叉树的性质

1. 设非空二叉树中度为0、1和2的结点个数分别为n₀、n₁和n₂，总节点为n
   • n = n₀ + n₁ + n₂ —- ①
   • n = n₁ + 2*n₂ + 1 (节点数 = 总度数 + 1 ) —-②
   • n₀ = n₂ + 1 —-由①②推出
2. 节点数：
   • 二叉树第i层最多有2^i-1个节点 满二叉树
   • 高度为h的二叉树至多有2? ? 1个结点 满二叉树
3. 具有n个（n > 0）结点的完全二叉树的高度h为$\log_2(n+1)$

二叉树的存储结构

1. 线性存储

   定义一个长度为 MaxSize 的数组 t ，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
   对于第i个节点

   i的左孩子——2i
   i的右孩子——2i+1
   i的父节点——$\frac{i}{2}$
   i所在层数——$\log_2(n+1)$

   缺陷：非完全二叉树会有许多空节点，造成空间浪费

2. 链式存储

   struct treenode{
      ELemtype data;
      treenode *rchild, * lchild;
      //可选头节点
      treenode *parent;
   };
   typedef struct treenode *treenodes;

二叉树的遍历

 1-3实现过程：递归

1. 先序遍历：根左右
2. 中序遍历：左根右

3. 后序遍历：左右根

4. 层次遍历:
   算法思想：
   ①. 初始化一个辅助队列
   ②. 根结点入队
   ③. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
   ④. 重复③直至队列为空
   

线索二叉树的基本概念和构造

• 前驱：
  在二叉树中，有（左子树为空）节点，遍历过程中，在该节点之前遍历的一个节点为前驱（若该节点为遍历的第一个节点，则前驱为NULL）
• 后继：
  在二叉树中，有（右子树为空）节点，遍历过程中，在该节点之后遍历的一个节点为后继（若该节点为遍历的最后一个节点，则后继为NULL）
• 线索二叉树：
  一个二叉树，在最底层的节点中他的左子树节点指向他的前驱，右子树节点指向后继，最后形成的数据结构（依据先/中/后序遍历的不同，生成的线索二叉树不同）

树、森林

树的存储结构

以此树为例

1. 双亲表示法（顺序存储）

数组序号	data	parent
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1

1. 孩子表示法（链式+顺序）
   
2. 兄弟表示法（链式存储）

   struct tnode{
      elemtype data; //数据
      tnode *firstchild, *nextbrother; //指向第一个孩子，和右兄弟
   };
   typedef tnode *tnodeds;

树、森林、二叉树的转换

https://www.cnblogs.com/zhuyf87/archive/2012/11/04/2753950.html

哈夫曼数

给定n个权值分别为w,w2…wn的结点,构造哈夫曼树的算法描述如下

1. 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F
2. 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和
3. 从F中删除刚才选出的两棵树,同时将新得到的树加入F中。
4. 重复步骤2和3,直至F中只剩下一棵树为止

• 已知有n个节点，最后的哈夫曼树有2*n+1个节点

图

图的基本概念

• 概念：图是顶点集和边集组成的二元组G=,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。

• 顶点V的度 = 与V相关联的边的数目

• 在有向图中：
  • 顶点V的出度 = 以V为起点有向边数
  • 顶点V的入度 = 以V为终点有向边数
  • 顶点V的度 = V的出度+V的入度
• 设图G的顶点数为n，边数为e
  • 图的所有顶点的度数之和 = 2*e

图的存储结构

邻接矩阵

1. 无向图的邻接矩阵是对称矩阵，同一条边表示了两次；
2. 顶点v的度：等于二维数组对应行（或列）中值为1的元素个数；
3. 判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；
4. 顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；
5. 设图的顶点数为 n ,用有n个元素的一维数组存储图的顶点,用邻接矩阵表示边,则G占用的存储空间为：$n+n2$；图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图；

?

typedef struct{
    char *ves;//记录顶点信息，A.B...
    int **arc;//边表
    int numberV,nueberE;
}MGraph;

邻接表

1. 邻接表表示不唯一。
2. 对于有n个顶点和e条边的无向图,其邻接表有n个头结点和2e个表结点。
3. 对于无向图,邻接表的顶点vi对应的第i个链表的表结点数目正好是顶点vi的度。
4. 对于有向图,邻接表的顶点vi对应的第i个链表的表结点数目仅仅是vi的出度。其入度为邻接表中所有adjvex域值为i的表结点数目。

typedef struct EdgeNode{  //边表结点
   int adjvex; //邻接点域，存储该顶点对应的下标
   EdgeType weight;  //存储权值，非网图不需要
   struct EdgeNode *next;
}EdgeNode;

struct VertexNode{  //顶点表结点
   VertexType data; //顶点信息
   EdgeNode *firstedge;  //边表头指针
};
typedef VertexNode AdjList;

typedef struct{
   AdjList adjList[100];  
   int numVertexes,numEdges; //图中当前顶点数和边数
}GraphAdjList;

十字链表

• 用于有向图，方便计算入度与出度

邻接多重表

• 用于无向图

图的遍历

深度优先遍历-DFS

1. 对树状结构：
   • 类似于二叉树的左右根（后序遍历）
2. 对邻接表结构：
   • 将节点顺序，依次遍历当前节点和他的所有边表信息

广度优先遍历-BFS

1. 对树状结构：
   • 类似于二叉树的根左右（先序遍历）
2. 对邻接表结构：
   • 先把所有节点依次入栈
   • 顶点出栈，顶点中有边表信息，将边表信息入栈
   • 重复上一步至栈空

图的应用

最小生成树

• 生成树：一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。

  • 深度优先生成树: 由深度优先遍历得到的生成树；
  • 广度优先生成树: 由广度优先遍历得到的生成树。
  • 遍历时访问过的n个顶点和遍历时经历的n-1条边组成。
  • 生成森林: 对于非连通图, 各个连通分量的生成树组成非连通图的。

• 最小生成树：在一个连通网的所有生成树中， 各边的代价之和最小的那棵生成树。简称为最小生成树(MST)。

1. 普里姆算法 (Prim算法)
   • 从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。
2. 克鲁斯卡尔算法（ Kruskal 算法）
   • 所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
   • 树的归并操作

   • 拓扑排序

• 用顶点表示活动， 用有向弧表示活动间的优先关系， 即上节所讨论的AOV-网。
• 用顶点表示事件， 用弧表示活动， 弧的权值表示活动所需要的时间。带权的有向无环图叫做边表示活动的网（Activity On Edge Network）, 简称AOE-网。

方法一：（从图中顶点的入度考虑）
从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。
从有向图中删去该顶点和所有以它为尾的弧；
重复上述两步,直到图全部顶点输出；或当前图中不再存在没有前驱的顶点。

关键路径

最短路径

1. Dijkstra O($N^2$)
   • 引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。一个记录节点是否有最短路径的D,一个P用来记录当前最短路径节点的前驱节点，
   • 步骤一：指定开始节点start，初始化S（到自己为0，其他记录为INF——最大值），初始化U（从start开始能到达的节点）
   • 步骤二：从U中找到start能到的节点k（此路径最小），将该节点加入到S
   • 步骤三：更新U中的节点路径（对于一个未记录的节点i，如果start->k->i的路径小于start->i的路径，就更新U）
   • 重复步骤二、三

     for (int count = 1; count < n; count++) { // 要加入n-1个顶点
                 int k = -1; // 选出一个距离初始顶点start最近的未标记顶点
                 int dmin = Integer.MAX_VALUE; //dim为记录当前路径中的最小值
                 for (int i = 0; i < n; i++) {
                     if (visited[i] == 0 && weight[start][i] < dmin) {
                        //visit表示该节点是否被记录 = D
                         dmin = weight[start][i];//wight = U
                         k = i;
                     }
                 }
     
                 // 将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
                 shortPath[k] = dmin;
                 visited[k] = 1;
     
                 // 以k为中间点，修正从start到未访问各点的距离
                 for (int i = 0; i < n; i++) {
                     //如果 '起始点到当前点距离' + '当前点到某点距离' < '起始点到某点距离', 则更新
                     if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
                         weight[start][i] = weight[start][k] + weight[k][i];
                         path[i] = path[k] + "-->" + i; //P
                     }
                 }
             }

2. Floyd O($N^3$)
   • 指定一个开始节点，从他能到达的第一个节点开始，不断试图增加中间节点，

查找

查找的基本概念

概念：给定一个值key，在含有n个记录的表中找出关键字等于key的记录。若找到,则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。
主关键字：能唯一标识一个记录的关键字。
次关键字：能标识多个记录的关键字。
平均查找长度ASL(Average Search Length) ：为确定数据元素在查找表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
$ASL = \sum_1^n P_i*C_i$
Pi为查找表中第i个记录的概率，Ci为找到第i个记录时，和给定值已经进行过比较的关键字个数。

静态查找表——基于线性表的查找法

概念：查询某个特定的元素是否在表中；检索某个特定的元素的各种属性。

1. 顺序查找
2. 折半查找（二分查找）：要求待查找的表必须是按关键字大小有序排列的顺序表。
   • $ASL_{折半查找} = [\log_2n]+1$
     
3. 索引查找（分块查找）：索引表是一个递增有序表。
   • 性能介于顺序查找和折半查找之间的查找方法。
   • $ASL_{索引} = L_B+L_W(L_B为索引表序列、L_W块内序列)$

动态查找表——基于树表的查找法

概念：表结构本身在查找过程中动态生成，即对于给定值key，若表中存在关键字等于key的记录，则查找成功，否则插入关键字等于key的记录。

1. 二叉排序树BST (Binary Sort Tree)
   • 中序遍历得到顺序关键字
   • https://www.cnblogs.com/sench/p/7783331.html
2. 平衡二叉树(AVL)
   • 平衡因子BF(Balance Factor) ：二叉树中每个结点的平衡因子是该结点左子树的高度减去右子树的高度。
     
   • 左旋和右旋
   • https://blog.csdn.net/isunbin/article/details/81707606
3. B-树

   哈希表——计算式查找法

• 哈希法又称散列法、杂凑法或关键字地址计算法等，相应的表称为哈希表或散列表；
• 方法的基本思想：在元素的关键字Key和元素的存储位置p之间建立一个对应关系H，使得p=H(Key)，H称为哈希函数(散列函数)，是一个压缩映象；
• 当查找关键字为key的元素时，利用哈希函数计算出该元素的存储位置p=H(key)，从而达到按关键字直接存取元素的目的；
• H(Key)也称为哈希地址(又称散列地址)。把如此构造的表存储结构称为哈希表。
• 装填因子α(Load Factor):
  $α= \frac nm$ n: 表中关键字数；m: 表长。

1. 构造方法：

   • 直接定址：
     $H(key) = key$ 或 $H(key) = a*key+b$
   • 数字分析：提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。
     $H(key)=H(d1d2d3…d7d8)=d4d7$
     
   • 除留余数法：假设哈希表长为m, 则哈希函数为:
     $H(key) =key\%p— (p为小于等于m的最大素数)$
     
   • 伪随机数法
   • 平方取中法
   • 折叠法（关键字分割成位数相同的几部分，然后取这几部分的叠加和）

2. 解决冲突：

   • 开放定址法：
     $H_i = ( H(Key)+d_i )\%m$
     di: 称为增量序列
     
   • 再造哈希法
   • 建立公共溢出区
   • ASL计算 https://blog.csdn.net/txd751466382/article/details/80851543
     

• 哈希表的装填因子 ? 表明了表中的装满程度。越大，说明表越满，再插入新元素时发生冲突的可能性就越大。
• 哈希的查找性能，即平均查找长度依赖于哈希表的装填因子，不直接依赖于 n 或 m。
• 不论表的长度有多大，总能选择一个合适的装填因子，以把平均查找长度限制在一定范围内。