001、数据结构

```mindmap
# 数据结构
- 线性表
    - 线性表
      - 概念
        - 由相同类型的结点组成的有限序列
        - 线性表中的结点之间的关系可由结点在线性表中的位置确定
        - 线性表的结点可由若干成分组成，其中能唯一标识该结点的成分称为关键字，或简称键
      - 基本运算
        - 查找运算
        - 插入运算
        - 删除运算
        - 其他运算：统计线性表中结点的个数、输出线性表各结点的值、复制线性表、线性表合并、线性表排序、按某种规律整理线性表
      - 存储
        - 顺序存储
          - 从数组的第一个元素开始、将线性表的结点依次存储在数组中：第i个结点存储在数组的第i(0<=i<=n-1)个元素中
          - 优点：随机存取线性表中任何一个结点
          - 缺点：一、数组大小通常是固定的，不利于任意增加或减少线性表的结点数；
                      二、插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂
        - 链接存储
          - 链接存储时用链表存储线性表
          - 单向链表：从链表的第一个结点开始，将线性表的结点依次存储在链表的各结点中，
          - 链表的每个结点不但要存储线性表结点信息，还要用一个域存储其后继结点的指针
          - 优点：每个结点的实际存储位置是任意的，给线性表的插入和删除操作带来了方便
          - 缺点：一、每个结点增加了一个后继指针成分，要花费更多存储空间；二、不便随机访问线性表的任一结点
      - 查找
        - 线性表的查找运算是指在线性表中找某个键值的结点
        - 查找算法：顺序查找、二分查找、分块查找、散列查找
      - 插入新的结点
        - 顺序存储
          - 把原来的第n-1个结点至第i个结点依次往后移一个数组元素位置
            把新结点放在第i个位置上
            修正线性表的结点个数
          - 在具有n个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上，
            若插入任一位置的概率相等，则在顺序存储线性表中插入一个新的结点，平均移动次数为n/2
        - 链接存储
          - 在某指针P所指结点之后插入；
            插在首结点之前，使待插入结点成为新的首结点；
            接在线性表的末尾；
            在有序链表中插入，使新的线性表仍然有序
      - 删除结点
        - 顺序存储
          - 在有n个结点的线性表中，删除第i个结点，删除时应将第i+1个结点至第n+1个结点依次向前移一个数组元素位置，共移动n-i-1个结点，步骤：
            检查删除要求的有关参数的合理性
            把原来第i+1个表元至第n-1个结点依次向前移一个数组元素位置
            修正线性表表元个数
          - 在具有n个结点的线性表上删除结点，其时间主要花费在移动表元的循环上，若删除任一表元的概率相等，则在序列存储线性表中删除一个结点，平均移动次数为（n-1）/2
        - 链接存储
          - 空链表：不执行删除操作
          - 要删除的结点恰为链表的首结点：将链表头指针改为指向原首结点的后继指电
          - 其他情况：先在链表中寻找要删除的结点，从链表首结点开始顺序寻找，
            若找到，执行删除操作，若直至链表末尾没有指定值的结点，则不执行删除操作
    - 栈
      - 栈
        - 栈只允许在同一端进行插入和删除运算，
        - 允许插入和删除的一端称为栈顶，另一端称为栈底，称栈的结点插入为进栈，结点删除为出栈
        - 因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征
      - 顺序存储
        - 可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标
      - 链接存储栈
        - 栈页可以用链表实现，用链表实现栈称为链表栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top，top为null的链表为空栈
    - 队列
      - 队列
        - 只允许在一端进行插入，另一端进行删除运算
        - 允许删除运算的那一端称为队首，允许插入运算的一端称为队尾，结点删除称为出队
        - 因最先进入队列的结点将最先出队，所以队列具有先进先出的特征
      - 顺序存储
        - 用顺序存储线性表来表示队列：
          为了指明当前执行出队运算的首位置，需要一个指针变量head(头指针)，
          为了指明当前执行进队运算的队尾位置，也需要一个指针变量taill（尾指针）
        - 用有N个元素的数组表示队列：
          随着出队和进队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而出队空间已用完的情况，
          一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组前端，修改头指针和尾指针，
         另一种更好的解决办法时采用循环队列
        -循环列表就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N-1]连接起来，
          队空的初态为 head=tail=0，
          在循环队列中，当tail赶上head时，队列满，反之，当head赶上tail时，队列变为空。
          这样对空和队满的条件都同为head=tail，这会给程序判别队空和队满带来不方便，
          因此，可采用当队只剩下一个空闲结点的空间时，就认为队列已满的简单办法，以区别队空和队满，
          即队空的判别条件时head=tail，队满的判别条件时head=tail+1 
      - 链接存储
        - 用链表实现队列称为链接队列
        - 链表的第一个结点时队列首结点，链表的末尾结点时队列的尾结点
          队尾结点的链接指针值为NULL，队列的头指针head指向链表的首结点，队列的尾指针tail指向链表的尾结点
          当队列的头指针head值为NULL时，队列为空
    - 稀疏矩阵
      - 稀疏矩阵
        - 在计算机中存储一个矩阵时，可使用二维数组。例如，M×N阶矩阵可用一个数组a[M][N]来存储
        - 如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵
        - 若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。
          因此，通常采用三元组数组或十字链表两种方法来存储稀疏矩阵
      - 三元组数组
        - 稀疏矩阵的每个非零元素用一个三元组来表示，即非零元素的行号、列号和它的值
        - 然后按某种顺序将全部非零元素的三元组存于一个数组中
        - 如果只对稀疏矩阵的某些单个元素进行处理，则宜用三元组表示。
      - 十字链表
        - 在十字链表中，矩阵的非零元素是一个结点，同一行的结点和同一列的结点分别顺序循环链接，
            每个结点既在它所在行的循环链表中，又在它所在列的循环链表中
        - 每个结点含5个域，分别为结点对应的矩阵元素的行号、列号、值，
            以及该结点所在行链表后继结点指针、所在列链表后继结点指针
        - 如果对稀疏矩阵某行或某列整体做某种处理，可能会使原来为零的元素变为非零，
          而原来非零的元素变成零。对于这种场合，稀疏矩阵宜用十字链表来表示。
    - 字符串
      - 字符串
        - 字符串是由某字符集上的字符所组成的任何有限字符序列
        - 当一个字符串不包含任何字符时，称它为空字符串
        - 一个字符串所包含的有效字符个数称为这个字符串的长度
        - 一个字符串中任一连续的子序列称为该字符串的子串
        - 字符串存在字符数组中，字符串最后一个有效字符之后的结束标记，记为 \0 ,由系统提供的库函数自动在末尾添加 \0
      - 对字符串的操作 
        - 统计有效字符串个数
        - 内容赋值到另一个字符串中
        - 将内容连接到另一个足够大的字符串的末尾
        - 在字符串中查找另一个字符串或字符
        - 按字典顺序比较两个字符串的大小
- 树
  - 树
    - 基本概念
      - 树是由一个或多个结点组成的有限集合T；
        有一个特定的结点，称为根结点
        其余的结点分成互不相交的有限集合，每个集合又都是一棵树
        Tm-1是根结点的子树
      - 一棵树至少有一个结点（根结点）
      - 一个结点的子树数目称为该节点的度（次数；结点的下一层子树，不含子子树），树中各结点的度的最大值称为树的度（树的次数；即理解为树中出现子树数目最多的度）
      - 度为0的结点称为叶子结点（树叶），除叶子结点外的所有结点称为分支结点，根以为的分支结点称为内部结点
      - 定义一棵树的根结点所在的层次为1，其余结点所在的层次等于它的父结点所在的层次加1，树中各结点的层次的最大值称为树的层次
    - 树的关系 
      - 位于上端的结点时位于下端的结点的父结点或双亲结点
      - 位于下端的结点时位于上端的结点的子结点
      - 同一父结点的多个子结点称为兄弟结点
      - 处于同一层上，不同父结点的子结点为堂兄弟结点
    - 常用的存储结构
      - 标准存储结构
        - 树的内容可分为成两部分，分别为结点的数据和指向子结点的指针数组
        -  例如：
              typedef struct tnode{
                char data;  # 树结点的数据信息
                struct tnode *child[N]; #树结点的子结点指针
            }TNODE;  #树结点的数据类型
      -  带逆存储结构
        -  在标准存储结构的基础上，增加一个指向其父结点的指针
        -  例子：
              typedef struct tnode{
                char data;  # 树结点的数据信息
                struct tnode *child[N]; #树结点的子结点指针
                struct tnode *parent;  # 父结点指针
            }TNODE;  #树结点的数据类型            
    - 树的遍历
      - 前序遍历：首先从左到右按前序遍历根结点的各棵子树（先最左边一棵树从上到下，先左后右的顺序遍历一遍后，再左边第二棵树）
      - 后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点（先最左边一棵树从下到上，先左后右的顺序遍历；先左边最底层，然后上一层，上一层的右边有树，则遍历右边最底层，然后右边层，同理依次遍历）
      - 层次遍历：首先访问处于0层上的根结点，然后从左到右依次访问处于1层上的结点，
        然后从左到右访问2层上的结点，即自上而下，从左到右逐层访问树中的各层上的结点
  - 二叉树
    - 基本概念
      - 是一个有限的结点集合（可以为空），由一个根结点及其两颗互不相交的左右二叉子树所组成
      - 二叉树的结点中有两颗子二叉树，分别称为左子树和右子树
      - 二叉树共有五种形态：空二叉树、二叉树中的结点没有子结点、结点只有一个左结点、结点只有一个右结点、结点有左右两个子结点
      - 二叉树的标准存储结构：
        typedef struct Btnode{
          char data; # 数据
          strucrt Btnode *lchild; # 左孩子
          strucrt Btnode *rchild; # 右孩子
        } BTNODE;
    - 六大性质
      - 三个重要性质
        - 在二叉树的第i层上至多有 2的(i-1)次方 个结点（i≥1）
        - 深度为k的二叉树至多有  2的k次方减1 个结点（k≥1）
        - 对任何一颗二叉树，如果其叶子结点数为 n₀，度为2的结点数为 n₂ ，则 n₀ =n₂+1
      - 满二叉树： 一棵深度为k且有  2的k次方减1  个结点的二叉树称为满二叉树（即全部结点都有左右子节点）
      - 完全二叉树：如果深度为k、有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树
      - 完全二叉与非完全二叉：
            完全二叉树（按从左到右的顺序编号，左边不能缺失结点，右边可以缺失结点）
            非完全二叉树（按从左到右的顺序编号，左边缺失结点）
      - 性质四：具有n个结点的完全二叉树的深度为 ∟㏒₂n 」+1。（注：∟ 」符号为向下取整运算符，
        ┍ ┐是向上取整运算符；∟ m 」表示不大于m的最大整数，反之┍ m ┐表示不小于m的最小整数）
      - 性质五：  如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第∟log2n」+1层，每层从左到右），则对任一结点i（1≤i≤n），有：
        -  如果i=1，则结点i无双亲，是二叉树的根；如果i>1,则其双亲是结点 ∟ i/2」。
        -  如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i
        -  如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1
      - 性质六：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树
    - 二叉树的遍历
  - 二叉排序树
  - 平衡二叉树
  - 线索树
  - 最优二叉树
- 图
  - 图
  - 最小生成树
  - 最短路径
  - 拓扑排序
  - 关键路径
- 排序
  - 排序
  - 插入排序
  - 选择排序
  - 交换排序
  - 归并排序
  - 基数排序
  - 算法复杂性比较
- 查找
  - 查找
  - 顺序查找
  - 二分法查找
  - 散列表
```