【数据结构】基础知识总结

系列综述：
💞目的：本系列是个人整理为了数据结构复习用的，由于牛客刷题发现数据结构方面和王道数据结构的题目非常像，甚至很多都是王道中的，所以将基础知识进行了整理，后续会将牛客刷题的错题一并整理到该文章中，可以考试复习或者找工作复习使用。
🥰来源：材料主要源于《王道数据结构考研复习指导》进行的，每个知识点再考研中及复习至少思考过三遍，比较可靠。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！

文章目录

- 数据结构
- - 一、绪论
  - - 基本概念
    - 数据结构三要素
    - 算法
  - 二、线性表
  - 三、栈和队列
  - - 栈
    - 队列
  - 四、串
  - - 串的定义和实现
    - 串的存储结构
  - 五、树与二叉树
  - - 树
    - 二叉树
    - 树与森林
    - 二叉排序树
    - 平衡二叉树
  - 六、图
  - - 基本概念
    - 图的存储
    - 图的遍历
    - 图的应用
  - 七、查找
  - - 基本概念
    - 静态查找
    - 动态查找
  - 八、排序
  - - 插入排序
    - 交换排序
    - 选择排序
    - 特殊排序
    - 内部排序算法比较
- 参考博客

😊点此到文末惊喜↩︎

相关思维导图：https://wwb.lanzouy.com/iAZyi0d3qbyd

数据结构

一、绪论

基本概念

$\supset 数据元素 \supset 数据项$
- 数据对象是具有相同性质的数据元素的集合
- 数据元素是数据的基本单位，由若干数据项组成
- 据项是构成数据元素不可分割最小单位
数据类型：是一个值的集合和定义在该集合上的一组操作
- 原子类型：值不可再分
- 结构类型：值可以再分
数据结构
- 定义：数据元素 + 相互关系
- 数据的运算实质就是算法的执行，由逻辑结构定义，由存储结构实现。不能过于考虑逻辑结构，而忽略存储结构是否容易实现，逻辑结构和存储结构都影响着算法的好坏。

数据结构三要素

逻辑结构
- 集合：数据元素同属于一个集合，其他无任何关系
- 线性结构：数据元素之间只存在一对一的关系，如栈、队列、串、数组、其他线性表
- 树状结构：数据元素间存在一对多的关系
- 图状结构：数据元素间存在多对多的关系
存储结构
- 顺序存储：逻辑相邻的数据元素存储在物理上相邻的位置。
  - 优点：可以实现随机存取，占用空间小
  - 缺点：可能产生空间碎片
- 链式存储：不同节点只要求逻辑上相邻，但是节点内要求物理连续
  - 优点：无碎片现象，元素的增删容易
  - 缺点：指针占用额外的空间，只能顺序存取
- 索引存储：存储元素的同时建立索引表
  - 优点：查找速度快
  - 缺点：索引表占用额外的空间，增删数据需要花费时间修改索引表
- 散列存储（哈希存储）：将数据元素的值映射成存储地址
  - 优点：增删改查都很快
  - 缺点：出现哈希冲突会增大时空开销

算法

算法的特性
- 输入：有零个或多个输入
- 有穷性：每一步均可在有穷时间内完成
- 确定性：相同的输入只能获得相同的输出
- 可行性：算法可以通过计算机基本指令实现
- 输出：至少一个输出
好的算法
- 正确性：正确解决问题
- 健壮性：及时处理非法数据
- 可读性：易于人们理解
- 时空开销小
算法效率的度量
- 时间复杂度：最深层嵌套语句运算次数的数量级
- 空间复杂度：算法耗费的存储空间，原地存储指O(1)
- $O(1)<O(log_{2}n)<O(n)<O(nlog_{2}n)<O(n^2)<O(2^n)<O(n!)<O(n^n)$

二、线性表

线性表：具有相同数据类型数据元素的有限序列
- 逻辑和物理的关系：是一种逻辑结构，表示数据元素一对一的相邻关系，即除表头元素其他元素只有一个直接前驱，除表尾元素其他元素只有一个直接后继
- 存储空间上：每个元素占用相同大小的存储空间
顺序表：线性表的顺序存储（逻辑结构和存储结构的结合）
- 逻辑和物理的关系：表中逻辑顺序和物理顺序相同
- 存储空间上：每个节点只存储数据元素，不需要浪费额外空间
- 增删改查：插入和删除需要移动大量元素，但是可以随机存取
- 静态分配，数组大小在编译阶段确定，执行时一旦超过可能发生溢出
- 动态分配，在程序执行时分配，一旦超过原空间，需要开辟更大的空间进行存储
单链表：线性表的链式存储
- 逻辑和物理的关系：表中逻辑顺序和物理顺序一般不相同
- 存储空间上：每个节点只存储数据元素，需要额外存储指针
- 增删改查：查找需要进行遍历，但是增删容易
- 头插法：链表元素的读入顺序和生成顺序时相反的
- 尾插法：链表元素的读入顺序和生成顺序时相同的
双链表：每个节点有两个指针prior和next，可以逆序遍历
循环单链表：尾指针指向头节点的链表，判空条件是头节点指针是否指向自己
循环双链表：判空条件是头节点的prior和next都等于头节点
静态链表：使用数组描述线性表的链式存储
- 节点具有数据域和指针域，指针域存放的是数组下标
- 结束标志是next == -1
- 静态链表的插入和删除只需要修改指针，不需要移动元素
- 可用于不支持指针的高级语言Basic

三、栈和队列

栈

栈的基本概念
- 栈：只允许在一端进行插入和删除操作的线性表，即后进先出
- 栈顶（Top）：线性表允许进行插入删除的那一端
- 栈底（Bottom）：线性表不允许插入和删除的那一端
- 空栈：不含任何元素的空线性表
- n个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n+1}C_{2n}^{n}$
```
- 最后一个元素第一个出栈，则输出序列一定是逆序
- 判断出栈顺序是否正确：按序进栈并在栈中相邻的元素出栈一定是逆序的
```
顺序栈：采用顺序存储的栈（逻辑和物理存储顺序一致）
```
//数组 + 栈顶指针top
#define MaxSize 50
typedef struct {
    Elemtype data[MaxSize];// 存放栈中元素，数组栈存在上溢的问题
    int top;// 栈顶指针
}SqStack;
```
- 栈顶指针：初始化时通常设置S.top = -1
- 栈顶元素：S.data[S.top]
- 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素
- 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1
- 栈空条件：S.top == -1
- 栈满条件：S.top == MaxSize-1
- 栈长：S.top+1
共享栈
- 定义：栈底在共享数组两端，栈顶向共享空间中间延伸
- 栈空条件：top0 = -1时0号栈为空，top1=MaxSize时1号栈为空
- 栈满条件：仅当两个栈顶指针相邻即top1 - top0 = 1
链栈
```
typedef struct Linknode{
    Elemtype data;
    struct Linknode *next;
}* LiStack;
```
- 定义：采用链式存储的栈
- 优点：不会栈满上溢，便于节点的插入和删除，但是需要前一个节点的辅助

队列

队列的基本概念
- 定义：只允许在线性表的一端进行插入，而在另一端进行删除的线性表，即先进先出
- 出队：在队头删除元素
- 入队：在队尾加入元素
- 空队列：不含任何元素的线性表
- 栈和队列都是操作受限的线性表，不可以随便读取栈或队列中间的某个数据
队列的顺序存储
```
#define MaxSize 50
typedef struct {
    Elemtype data[MaxSize];// 存放栈中元素，数组栈存在上溢的问题
    int front,rear;
}SqQueue;
```
- 定义：分配一块连续的存储单元存放队列中的元素，队头指针front指向对头元素，队尾指针rear指向队尾元素的下一个位置
- 队空条件：Q.front == Q.rear==0
- 进队操作：队不满时，先送至到队尾元素，再将队尾指针加1
- 出队操作：队不空时，先取队头元素值，再将队头指针加1
- 假溢出：存在连续出队导致分配使用的内存不足，使用循环队列进行解决
循环队列
- 定义：将存储队列元素的表在逻辑上视为一个环
- 出队：Q.front = Q.rear = 0
- 入队：Q.rear = (Q.rear+1) % MaxSize
- 队列长度：（Q.rear-Q.front+MaxSize）% MaxSize
- 将队尾指针指向队尾的下一个元素，牺牲了队尾指针指向的单元。将队头指针在队尾指针的下一位置作为队满的标志
- 队满条件：(Q.rear+1) % MaxSize == Q.front
- 队空条件：Q.front == Q.rear
链队列
```
typedef struct {
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
```
- 定义：队列的链式表示，头指针指向队头节点，尾指针指向队尾节点的单链表
- 判空条件：Q.front == NULL && Q.rear == NULL
- 设计：通常将链式队列设计成带头节点的单链表，统一插入和删除操作
- 优点：有利于元素数据变动，无溢出问题
双端队列
- 定义：允许前端和后端均可出入队操作的队列
- 输出受限的双端队列：允许在一端进行插入和删除，在另一端只允许插入的双端队列
- 输入受限的双端队列：允许在一段进行插入和删除，在另一端只允许删除的双端队列
特殊矩阵的压缩存储
- 压缩矩阵：为多个值相同的元素值分配一个存储空间，对零元素不分配存储空间
- 特殊矩阵：分布具有规律性的矩阵，例如上三角矩阵、对角矩阵、对称矩阵
- 稀疏矩阵：矩阵中非零元素相对于矩阵整体元素个数来说比较少，通常使用三元组存储

四、串

串的定义和实现

定义：由零个或多个字符组成有限序列
子串：串中任意个连续的字符组成的子序列
主串：包含子串的串，串的主要操作是以子串为对象进行的
空格串：由一个或多个空格组成的串
串相等：串的长度和每个位置对应的字符都相等

串的存储结构

定长顺序存储

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];// 字符串的最后一位是‘\0’
    int length;
}SString;

堆分配存储表示

typedef struct{
    char *ch;	// 按照串长分配存储区，ch指向串的基地址
    int length;
}HString;

串长的两种表示方式
- length变量存储
- 结束标记法

五、树与二叉树

树

定义：树是n个节点的有限集合，当n=0时，称为空树
树的定义是递归的，具有以下特点
- 树的根节点没有前驱，除根节点外的所有结点都有且只有一个前驱
- 树中所有节点可以有零个或多个后继
- 树适合表示有层次结构的数据
- 在n个节点的树中有n-1条边
基本概念
- 祖先：根A到节点K的唯一路径上的任何节点，称为节点K的祖先
- 子孙：如果节点B是节点K的祖先，则节点K是节点B的子孙
- 兄弟节点：具有相同的父节点，根A是树中唯一没有双亲的结点
- 节点的度：某个节点的孩子的个数
- 树的度：树中节点的最大度数
- 分支节点：度大于0的节点
- 叶子节点：度为0的节点
- 节点的深度：从根节点开始自顶向下逐层累加的
- 节点的高度：从该节点分支的叶节点开始自底向上逐层累加的
- 树的高度（深度）：树中节点的最大的层数
- 有序树：树中节点的各字数从左到右是有序的，不能互换
- 路径：自顶向下两个节点所经过的结点序列构成的
- 路径长度：路径上所经过的边的个数，同一个双亲之间的孩子不存在路径
- 森林：m棵互不相交的树的集合
一棵度为m的树
- $总节点数 = n_0 + n_1+n_2+···$
  $总度数/总分支数 = 1*n_1+2*n_2+3*n_3+···$
  $总节点数 = 总度数 + 1$
- 度为m的树中第i层上至多有 $m^{i-1}$ 个节点
- 高度为h个m叉树至多有 $m^h-1)/(m-1)$ 个节点

二叉树

特点
- 每个节点至多有两颗子树
- 二叉树是有序树，左右子树顺序不能颠倒
- 二叉树以递归形式定义
二叉树和度为2的有序树的区别
- 度为2的树至少有3个节点，而二叉树可以为空
- 度为2的树若某个节点只有一个孩子，则该孩子无须区分左右次序。有序树孩子左右次序是固定的
特殊的二叉树
- 满二叉树：一个高度为h，且含有 $2^h-1$ 个节点的二叉树称为满二叉树，即树中每层都含有最多的节点。
- 完全二叉树：最后一层自左向右排列不满，其余均满。即度为1的节点只有左孩子。
- 二叉排序树：左子树上所有节点的关键字均小于根节点的关键字，右子树上的所有结点均大于根节点。左子树和右子树又各是一颗二叉排序树
- 平衡二叉树：书上的任一结点的左子树和右子树的深度之差不超过1
二叉树的性质
- 非空二叉树的叶子结点等于度为2的结点数加1， $n_0 = n_2+1$
- 结点数量为n，则边的数量为n-1
- 非空二叉树的第k层至多有 $2^{k-1}$ 个结点
- 高度为h的树至多有 $2^h-1$ 个结点
- 完全二叉树和满二叉树可以自顶向下，自左向右进行顺序编号
顺序存储
- 定义：二叉树的顺序存储是指用一组地址连续的存储单元一次自上而下、自左向右存储完全二叉树上的结点
- 满二叉树和完全二叉树适合采用顺序存储，优点
  - 节省存储空间
  - 利用数组元素下标可以确定结点在二叉树中的位置
- 忽略数组第0个元素，从数组下标1开始存储的性质
  - 当i为偶数时，其双亲的编号为i/2，是左孩子。
    当i为奇数时，其双亲的编号为(i-1)/2，是右孩子。
  - 结点i的左孩子编号为2i，否则无左孩子
    结点i的右孩子编号为2i+1，否则无右孩子

链式存储结构

typedef struct BiNode{
    ElemType data;		// 数据域
    struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

在n个结点的二叉链表中，含有n+1个空链域

二叉树的遍历
- 定义：某条搜索路径访问树中的每个结点，使得每个结点均被访问一次
- 由遍历序列构造二叉树
  - 由二叉树的先序和中序序列可以唯一确定一颗二叉树
  - 由二叉树的中序和后序序列可以唯一确定一颗二叉树
- 有五种遍历方式，空间复杂度和时间复杂度均为O(n)

  // 先序遍历：根左右
  void preOrder(BiTree T){
      if(T != NULL) {
          visit(T);				// 遍历根结点
          preOrder(T->lchild);	// 遍历左子树
          preOrder(T->rchild);	// 遍历右子树
      }
  }
  
  // 中序遍历：左根右
  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);				// 遍历根结点
      }
  }
  
  // 层次遍历/广度优先遍历
  void levelOrder(BiTree T) {
      initQueue(Q);						// 初始化辅助队列
      BiTree p;
      EnQueue(Q, T);						// 将根节点入队
      while (!IsEmpty(Q)) {				// 队列不空则循环
          DeQueue(Q, p);					// 队头结点出队
          visit(p);						// 访问队头结点
          if (p->lchile  != NULL)			
              EnQueue(Q, p->lchild);		// 左子树不空，则左子树根节点入队
          if (p->rchild != NULL)
              EnQueue(Q, p->rchild);		// 右子树不空，则右子树根节点入队
      }
  }

线索二叉树

目的：充分利用空指针域，加快查找结点前驱和后继的速度
方式
- 若无左子树，令lchile指向其前驱结点
  若无右子树，令rchild指向其后继结点

typedef struct ThreadNode{
    ElemType data;							// 数据元素
    struct ThreadNode *lchildl, *rchild;	// 左右孩子指针
    int ltag, rtag;		// 左表示前驱，右表示后继，1表示前后，0表示孩子		
}ThreadNode, *TheadTree;

// 中序线索二叉树的建立
void InThread(ThreadTree T){
    if(T != NULL) {
        InThread(T->lchild);
        visit(T);
    	InThread(T->rchild);
    }
}
void visit(ThreadNode *q){
    if(q->lchild == NULL){
        q->lchild = pre;
        q->ltag = 1;
    }  
    if(pre != NULL && pre->rchild == NULL){
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;S
}

树与森林

树的存储结构

双亲优先法

#define MAX_TREE_SIZE 100   // 树中最多的结点数
typedef struct {
    ElemType data;	// 数据元素
    int parent;		// 双亲数组下标
}PTNode;
typedef struct {					// 树的类型定义
    PTNode nodes[MAX_TREE_SIZE];	// 双亲定义
    int n;							// 结点数
}PTree;

采用顺序存储，第一个是根节点，其双亲为-1
可很快得到双亲结点，但是求结点的孩子需要遍历整个结构

孩子优先法
```
typedef struct SNode{
    ElemType data;
   	SNode *child;
}SNode;

SNode T[MAX_SIZE];// 双亲结点数组
```
- 使用邻接链表，数组存储存储所有结点表示双亲，链表元素表示双亲节点的孩子
- 寻找孩子结点非常直接，寻找双亲需要完整遍历

孩子兄弟表示法

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild, *nextsibling; 
    // 左指针为第一个孩子，右指针为孩子的兄弟
}CSNode, * CSTree;

易于查找孩子，但是难以查找双亲

树转化为二叉树
- 每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟
树的遍历
- 先根遍历：先根后顺序遍历相应子树，遍历序列和对应二叉树的先序序列相同
- 后根遍历：先顺序遍历子树后访问根，遍历序列和该树对应二叉树的中序序列相同
- 层次遍历：按每层结点顺序访问

二叉排序树

BST的特性
- 左子树非空则左子树所有结点的值均小于根节点的值
- 右子树非空则右子树所有结点的值均大于根节点的值
- 左右子树分别各是一颗二叉排序树
重要：对二叉排序树结点中序遍历，可以得到一个递增的有序序列

BST的非递归查找算法

BSTNode *BST_Search(BiTree T, ElemType key){
    while (T != NULL && key != T->data){
        if(key < T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

BST的插入和构造

int BST_Insert(BiTree &T, KeyType k) {
    if (T == NULL){
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return l;
    }
    else if(k == T->key)
        return 0;
    else if(k < T->key)
        return BST_Insert(T->lchlde, k);
    else
        return BST_Insert(T->lchild, k);
}
// 二叉排序树的构造
void Creat_BST(BiTree &T, keyType str[], int n){
    T = NULL;
    int i = 0;
    while (i < n) {
        BST_Insert(T, str[i]);
        i++;
    }
}

二叉排序树的删除
- 若被删结点为叶结点，则直接删除
- 若被删结点只有一颗子树，则让该节点的子树成为其父亲结点的子树
- 若被删结点有左右子树，则从左子树中最大结点代替被删结点，从右子树中找最小结点代替被删结点
二叉排序树的查找效率
- 最好情况，二叉排序树是一个平衡二叉树，平均查找长度为 $O(log_2n)$
- 最坏情况，输入序列是有序的，则形成一颗单支树，平均查找长度为 $O(log_2n)$
二分查找的对象是有序顺序表
- 当有序表是静态查找表时，宜用顺序表作为存储结构
- 当有序表是动态查找表时，宜用二叉排序树作为逻辑结构

平衡二叉树

定义：任意结点的左右子树的高度差的绝对值不超过1
目的：为了避免树的高度增长过快，降低二叉排序树的性能
插入
- 调整对象：最小不平衡子树
- 四种平衡操作
平衡二叉最大深度和平均查找长度均为 $O(log_2n)$
哈夫曼树的基本概念
- 带权路径长度：根到任意结点的路径长度（经历的边的数量）与该节点权值的乘积
- 树的带权路径长度：所有叶结点的带权路径长度之和
- 哈夫曼树：带权路径长度最小的二叉树
哈夫曼树的构造
- 给定n个带权结点序列，每次取出两颗权值最小的结点构成一颗二叉树，树的根节点为左右子树的结点之和，并将根节点加入到序列中
哈夫曼树的特点
- 每个初始结点都最终成为叶结点，权值越小的结点到根节点的路径长度越大
- 初始结点数量为n个，则哈夫曼树的结点总数2n-1
- 哈夫曼树中不存在度为1的结点
- 相同的序列可能构造不同的哈夫曼树，但是带权路径长度WPL相同且为最优
哈夫曼编码
- 固定长度编码：对每个字符用相等长度的二进制位表示
- 可变长度编码：允许对不同字符使用不等长的二进制位表示
- 哈夫曼树通常使用可变长度编码，对频率高的字符赋予更短的编码，启到压缩数据的目的
- 前缀编码：没有一个编码是这个编码的前缀
由哈夫曼树构建哈夫曼编码
- 初始结点的权值为该节点的频率
- 在哈夫曼树中对每个结点进行左0右1的标记
- 每个叶子结点从根节点开始形成的01序列即为编码

六、图

基本概念

图：由顶点集和边集组成，顶点的个数称为图的阶
- 线性表可以是空表，树可以是空树，但是图不可以是空图，顶点咋集一定非空
有向图：由顶点集和有向边集（也称为弧）组成，有向边使用<v，u> 序列表示，可以双向
无向图：由顶点集和无向边集组成
简单图：不存在重复边和顶点到自身的边
多重图：允许两顶点间边数多于一条或顶点通过一条边和自己关联
完全图：顶点集合具有n个的无向图，具有n(n-1)/2条边
有向完全图：顶点集合具有n个的有向图，具有n(n-1)条边。在有向完全图中任意两个顶点之间都存在方向相反的两条弧
G’是G的子图：G =（V,E）和G’=（V’ ,E’），若V’是V的子集，且E是E’的子集，其中E’的顶点必须在V’内？
生成子图：与主图顶点集相同的子图
连通图：图中任意两个顶点都有路径存在，边数小于n-1的必是非连通图
- 极大连通子图：包含主图所有边的连通子图，再加入一个顶点都会使其不连通
- 极小连通子图：保持图连通并使边数最少的子图
- 连通图的生成树：包含图中所有顶点的一个极小连通子图，边数必为n-1
强连通图：图中的每一对顶点都有双向的路径
顶点的度
- 无向图：该顶点边的条数。无向图全部顶点的度的和等于边数的两倍
- 有向图
  - 入度：以顶点v为终点的有向边的数目
  - 出度：以顶点v为起点的有向边的数目
  - 有向图的全部顶点的入度之和与出度之和相等，且等于边数
带权图/网：边上带有权值的图
稀疏图、稠密图：使用边数的多少进行划分，一般 $∣ E ∣ < ∣ V ∣ l o g ∣ V ∣$ 认为是稀疏图
路径：由边关联的相邻顶点组成的序列
- 路径长度：路径上边的数目
- 回路/环：第一个顶点和最后一个顶点相同的路径
- 简单路径：顶点不重复出现的路径
- 简单回路：除了第一个顶点和最后一个顶点外其余顶点不重复出现的回路
- 距离：两个顶点之间最短的路径
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图

图的存储

邻接矩阵
- 定义：存储顶点之间邻接关系二维数组
- 带权图中邻接矩阵存放着该边对应的权值
- 有向图和无向图的矩阵：n个节点生成n×n的矩阵，某行某列不为零表示行序号的节点到列序号的节点有边，带权图某行某列为其权值
- 结构体
```
#define MaxVertexNum 100			// 顶点数目的最大值
typedef char VertexType;			// 顶点的数据类型
typedef int EdgeType;				// 带权图中边上给权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];	// 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];	// 邻接矩阵、边表
    int vexnum, arnum;				// 图的当前顶点数和弧数
}MGraph;
```
- 特点：
  - 无向图的邻接矩阵是对称矩阵，可以进行压缩操作，只存储半三角
  - 邻接矩阵表示法的空间复杂度为 $O(n^2)$ ，其中n为图的顶点数量|V|
  - 无向图的邻接矩阵的第i行（或第i列）非零元素（或非无穷元素）的个数正好是第i个顶点的度数
  - 有向图第i行全部的有值元素之和为顶点i的出度，第i列全部的有值元素之和为顶点i的入度
  - 邻接矩阵容易确定顶点之间是否有边相连，但确定边数花费时间比较大
  - 稠密图适合使用邻接矩阵存储
邻接表法
- 定义：顶点表使用顺序存储，边表使用链式存储
- 结构体
```
#define MaxVertexNum 100	// 图中顶点的最大数量
// 边表节点
typedef struct ArcNode{
    int adjvex;				// 该弧所指向的顶点位置
    struct ArcNode *next;	// 指向下一条弧的指针
    //InfoType info;		// 网的边权值
}ArcNode;
// 顶点表节点
typedef struct VNode{
    VertexType data;		// 顶点数据
    ArcNode *first;			// 指向第一条依附该顶点的弧线的指针
}VNode,AdjList[MaxVertexNum];
// 邻接表
typedef struct{
    AdjList vertices;		// 图的顶点数和弧数
    int vexnum, arcnum;		// AlGraph是邻接表存储的图
}ALGraph;
```
- 特点：
  - G为无向图，则所需的存储空间为 $O (∣ V ∣ + 2∣ E ∣)$ 。G为有向图，则所需的存储空间为 $O (∣ V ∣ + ∣ E ∣)$ 。
  - 邻接链表适合存储稀疏图
  - 给定顶点，通过邻接链表可以很容易的找到它的所有邻边和顶点
  - 有向图的邻接链表容易计算某个顶点的出度，但是不容易计算入度，需要遍历全部邻接链表
  - 图的邻接链表不是唯一的，各边节点的连接次序可以任意的
十字链表
- 定义：有向图的一种链式存储结构，由顶点结构体和边结构体组成
- 常用于存储稀疏图，容易求得顶点的出度和入度
邻接多重表
- 定义：无向图的一种链式存储，由顶点结构体和边结构体组成
- 相比于邻接表同一条边需要两个节点表示，在邻接多重表中只使用一个节点

图的遍历

定义：从图中某一个顶点出发，对图中所有顶点访问一次且仅访问一次，
广度优先搜索BFS
```
bool visited[MAX_VERTEX_NUM];
// 遍历所有节点
void BFSTraverse(Graph G){
    for（i = 0; i < G.vexnum; ++i）
        visited[i] = FALSE;
    InitQueue(Q);
    for(i=0; i<G.vexnum; ++i)
        if(!visited[i])
            BFS(G, i);
    
}
// 遍历输入节点的所有子节点
void BFS (Graph G, int v){
    visit(v);
    visited[v] = TRUE;
    Enqueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for (w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G, v, w))
            if(!visited[w]){
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
    }
}
```
- 算法时间复杂度
  - 邻接表存储为 $O (∣ V ∣ + ∣ E ∣)$
  - 邻接矩阵存储为 $O(|V^2|)$
- 广度优先遍历过程可以得到一颗广度优先生成树，广度优先生成树的唯一性和邻接矩阵存储表示的唯一性一致
深度优先搜索DFS
```
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    for(v=0; v<G.vexnum; ++v)
        visited[v]=FALSE;
    for(v=0; v<G.vexnum; ++v)
        if(!visited[v])
            DFS(G,v);
}


void DFS(Graph G, int v){
    visit(v);
    visited[v] = TRUE;
    for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G,v,w))
        if(!visited[w]){
            DFS(G,w);
        }
}
```
- DFS是一个递归算法，空间复杂度为 $O (∣ V ∣)$
- 时间复杂度
  - 邻接表存储为 $O (∣ V ∣ + ∣ E ∣)$
  - 邻接矩阵存储为 $O(|V^2|)$

图的应用

最小生成树
- 定义：包含连通图的所有顶点 && 只含尽可能少的边的生成树 && 边的权值之和最小
- 性质
  - 不一定唯一，图中的各边权互不相等时，G的最小生成树是唯一的
  - 无向连通图G的边数比顶点数小1，即G本身是一颗树时，则G的最小生成树就是它本身
  - 最小生成树的边的权值之和总是唯一的，且是最小的
  - 最小生成树的边数为顶点数减1
- 生成算法1: Prim算法
  - 过程：开始从图中任取一顶点，加入树T中，之后选择一个与当前T中顶点集合距离最近且加入后不生成环的顶点加入集合，再重复以上过程。
  - 特点：时间复杂度为 $O(|V|^2)$ ，适用于求解边稠密图的最小生成树
- 生成算法2: Kruskal算法
  - 过程：将边的权值由小到大进行排序，不断选取当前未被选取的权值最小的边且加入后不会构成环
  - 特点：主要由排序时间决定，适合顶点多的图
最短路径
- 定义：带权图中两顶点长度最短的那条路径
- 最短路径问题分类
  - Dijkstra算法：单源最短路径问题，即求图中某一个顶点到其他各顶点的最短路径
    特点：1.基于贪心策略的 2.时间复杂度均为 $O(|V|^2)$ 3.不适用边上有负权值的
  - Floyd算法：求顶点对之间的最短路径
    特点：1.时间复杂度为 $O(|V|^3)$ 2. 不允许带有负权值边组成的回路
有向无环图：不存在环的有向图，简称DAG图
- 用于描述含有公共子式的共享，从而节省存储空间
拓扑排序
- AOV网：使用顶点表示前后关系的有向无环图
- 定义：有一个有向无环图组成的序列，且满足以下关系
  - 每个顶点出现且只出现一次
  - 在序列中靠后的顶点不存在到前面顶点的路径
  - 每个AOV网中存在一个到多个拓扑排序序列
- 对AOV网进行拓扑排序
  - 从AOV网中选择入度为0的顶点并输出
  - 从网中删除该顶点和所有以它为起点的有向边
  - 重复前两步知道当前AOV网络为空或网中不存在无前驱的顶点
- 特点：
  - 时间复杂度为 $O (∣ V ∣ + ∣ E ∣)$
  - 有向无环图的拓扑序列唯一不能唯一确定该图
  - 若不存在拓扑序列则图中必有回路
关键路径
- AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示完成活动的开销
- 概念：
  - 开始顶点（源点）：AOE网中仅有的一个入度为0的顶点，表示整个工程的开始
  - 结束顶点（汇点）：网中仅有的一个出度为0的顶点，表示整个工程的结束
  - 关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径。这个路径决定了工程最短结束事件
- 性质
  - 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
  - 只有在进入某个顶点的各有向边所代表的活动都结束，该顶点所代表的事件才能发生
  - 网络中的关键路径可能不唯一，且关键路径上的所有活动都是关键活动
  - 缩短所有关键路径上共有的任意一个关键活动

七、查找

基本概念

查找：在数据集合（查找表）中寻找满足某种条件的数据元素
分类
- 静态查找：顺序查找、折半查找、散列查找
- 动态查找：散列查找、二叉平衡树查找、B树查找
关键字：数据元素中唯一表示该元素的某个数据项的值
平均查找长度：所有查找过程中进行关键字的比较次数的平均值
增加查找效率的数据结构都是对于查找表进行规则约束而形成的

静态查找

顺序查找
- 定义：在线性表中遍历查找
- 平均查找长度
  - $ASL_{成功} =(n+1)/2$
  - $ASL_{失败} =n+1$
- 特点
  - 当n平均查找长度较大，效率低
  - 对数据元素的存储和有序性没有要求
折半查找
- 适用范围：二分查找适用于有序顺序表（存储结构必须支持随机查找）
- 时间复杂度： $O(log_2n)$
分块查找
- 特点
  - 块内元素无序，块之间元素有序
  - 第一个块中的最大关键小于第二个块中的所有记录的关键字
  - 索引表中的每个元素中含有各块中的最大关键字和各块中的第一个元素的地址
- $\sqrt{查找表长度}$

动态查找

B树
- 定义：是一颗多路平衡查找树，m叉的B树有以下特性
  - 绝对平衡：任一层的所有子树均高度相同
  - 根节点：子树数量[2,m]，关键字数[1,m-1]
  - 其他节点子树：[m/2,m]，关键字数[(m/2)-1,m-1]
  - 每个节点内的关键字有序，左小右大
  - 叶子节点均在最后一层
  - 节点中孩子个数等于该节点中关键字个数加1
  - B树叶子节点中对应查找失败的情况，n个关键字中有n+1中失败的可能性
- B树的高度和磁盘存取顺序成正比，不包括没有信息的叶节点那层
- 基本操作
  - 在B树中找节点（通常存储在磁盘中）
  - 在节点内找关键字（通常存储在内存中）
- 插入操作
  - 插入后节点的关键字个数小于m，可以直接插入
  - 插入后检查被插入节点内的关键字个数，当插入后的节点关键字个数大于m-1时，必须对节点进行分裂，左部分放在原节点中，中间位置元素插入到原节点的父节点，右部分放到新节点中
- 删除操作
  - 直接删除：所在节点的关键字个数大于等于m/2
  - 兄弟够借：被删除节点由父顶点代替，父顶点由被借顶点代替
  - 兄弟不够借：父亲顶点下来与兄弟合并
- B+树
  - 具有n个关键字的节点只含有n棵子树，即每个关键字对应一颗子树
  - 内部节点关键字个数n的范围是 $m/2\le n \le m$ ，根节点为 $1\le n \le m$
  - 只有叶子节点包含信息（全部节点），非叶节点只是索引作用，存盘存储块小，读入内存快
  - 查找过程，无论成功与否，每次查找都是一条从根节点到叶子节点的路径
散列表（哈希表）
- 散列函数：将查找表中关键字映射成对应地址的函数，但是可能将多个关键字映射到同一个地址发生冲突
- 哈希表：建立关键字和存储地址直接的直接映射关系
- 常用散列函数
  - 直接定址法：简单算数运算进行映射，简单不会产生冲突，只适合关键字分布基本连续的情况，空位较多会造成存储空间的浪费
  - 除留余数法：选取小于等于元素个数的最大质数，进行取余运算。冲突主要取决于选取的余数
  - 数字分析法：选取数码分布较为均匀的其中几位作为散列地址（手机号）
  - 平方取中法：取关键字平方值的中间几位作为散列地址
- 开放定址法处理冲突的方式
  定义：存放新表项的空闲地址既向它的同义词表项开放，又向它的非同词表项开放
  缺点：开放定址法不能随便删除元素，可以给要删除的元素做一个标记，进行逻辑删除，防止中断查找路径
  - 线性探测法：冲突发生时，顺序查看下一个表中的单元直到找到一个空闲单元。但是可能造成相邻散列地址的堆积，导致查找效率下降
  - 平方探测法：每次查找的步数呈指数增长，不能探测所有单元，但是可以探测一半
  - 再散列法：使用两个散列函数，当通过第一个散列函数得到的地址发生冲突时，再利用第二个散列函数
  - 伪随机序列法：出现碰撞时使用生成的伪随机序列作为增量
- 拉链法
  顺序数组作为散列后的地址，数组中的每个数据元素指向发生冲突的同义词链表

八、排序

算法的稳定性：关键字相同的两个元素在排序后顺序不变

插入排序

直接插入排序
- 基本思想
  对于n个元素的序列，分为有序表和无序表，每次从后部的无序表中选择第一个元素和有序表中的元素从后向前进入比较，若有序表中选择元素比无序表中选择元素大，则有序表元素后移，直到找到无序表中选择元素要插入的位置
- 哨兵的作用：在进行大量数据进行比较时，在数据边界放置特别的元素标注，避免每次比较是否越界而浪费时间
- 空间复杂度：O(1) 时间复杂度： $O(n^2)$
折半插入排序
- 基本思想
  适合整体有序的顺序表，使用折半查找确定插入位置，从而统一移动元素
- 时间复杂度仍然为 $O(n^2)$ ，但是对于数据量不大的排序表往往可以表现出较好的性能
希尔排序（缩小增量排序）
- 基本思想
  取一个小于n的步长d，把表中的全部记录分成d组，将待排序表中d的倍数的数据元素放在同一组，在组内进行直接插入排序。再取更小的步长进行排序，直到所有记录放在同一组中。
- 空间复杂度：O(1) 时间复杂度： $O(n^{1.3})$ ，但仅适用顺序存储

交换排序

冒泡排序
基本思想：按逆序或顺序两两比较相邻的元素，按升序或降序进行交换
- 产生的子序列是全局有序的，即每一次排序会产生一个最终结果元素
- 空间复杂度：O(1) 时间复杂度： $O(n^2)$
快速排序
- 基本思想
  - 选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
  - 分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
  - 递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
- 特点
  - 不产生有序子序列，但每次排序后会将基准元素放到最终位置上
  - 每次排序划分子区间越相近越能发挥快排优势
- 空间复杂度： $O(log_2n)$ 时间复杂度： $O (n l o g n)$

选择排序

简单选择排序
- 基本思想：分成有序区和无序区，每次从无序区中找一个最小的放到有序区的最后一个
- 空间复杂度：O(1) 时间复杂度： $O(n^2)$
堆排序
- 堆分类
  - 大根堆：在完全二叉树中，所有根均大于左右子树的值
  - 小根堆：在完全二叉树中，所有根均小于左右子树的值
- 堆的建立
  - 检查所有非终端节点，顺序存储前i， $\le n/2$
  - 从最大分支节点第i个开始，与其顺序表中左孩子2i和右孩子2i+1进行比较，交换最大值，使该分支节点满足大根堆
  - 指针前移指向下一个分支节点，重复上述过程，时间复杂度为O(n)
- 堆的插入
  先将新节点放在堆末端，再对这个新节点执行调整操作，与父节点不断比较向上调整到最后位置
- 堆的删除
  用堆底部元素进行填充，然后该元素进行下坠比较
- 堆的应用
  - 可以用堆实现优先队列
- 算法性能
  - 空间复杂度： $O (1)$ 时间复杂度： $O(nlog_2n)$

特殊排序

归并排序
- 定义：将n个有序表组合在一起形成新的有序表，通常n为2称为2路归并算法
- 算法性能
  - 空间复杂度： $O (n)$ 时间复杂度： $O(nlog_2n)$
基数排序
- 不基于比较和移动，而是基于关键字各位的大小进行排序
- 算法性能
  - 空间复杂度： $O (r)$ ，r表示辅助队列个数
  - 时间复杂度： $O (d (n + r))$ ，共接进行d躺分配和收集，一趟分配需要O(n)，一趟收集需要O®

内部排序算法比较

直冒简希，快堆二基

算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入排序	$O (n)$	$O(n^2)$	$O(n^2)$	$O (1)$	是
冒泡排序	$O (n)$	$O(n^2)$	$O(n^2)$	$O (1)$	是
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	否
希尔排序	适合大规模数据	$O(n^{1.3})$	$O(n^2)$	$O (1)$	否
快速排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	否
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	O(1)	否
2路归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O (n)$	是
基数排序	$O (d (n + r))$	$O (d (n + r))$	$O (d (n + r))$	$O (r)$	是

当n比较小或关键字基本有序的时候，使用直接插入排序。
当n比较大，使用 $O(nlog_2n)$ 的排序算法
- 快速排序，排序关键字随机分布时，性能表现最好
- 堆排序，辅助空间少，不会出现最坏情况
- 归并排序，排序稳定，不交换相等数据元素
数据元素本身信息量比较大，可以使用简单选择排序，减少数据元素的移动次数。或者使用链表作为存储结构。
n很大且关键字位数少可以分解，可以采用基数排序