数据结构入门学习

---

前言

---

本文主要内容是对《2020年数据结构考研复习指导》一书的关键点提炼。作为IT从业者，数据结构是必须夯实的基础，该书虽为考研复习指导，但也可作为入门数据结构的选择。

---

思维导图

---

• 《2020年数据结构考研复习指导》
  • 第1章 绪论
    • 基本概念
      • 数据结构三要素
        • 逻辑结构
          • 线性结构
            • 线性表
            • 栈
            • 队列
          • 非线性结构
            • 集合
            • 树
            • 图
        • 存储结构
          • 顺序存储
          • 链式存储
          • 索引存储
          • 散列存储
        • 运算
    • 算法
      • 五个特性
        • 有穷性
        • 确定性
        • 可行性
        • 输入
        • 输出
      • 效率度量
        • 时间复杂度
        • 空间复杂度
  • 第2章 线性表
    • 基本概念
      • 相同数据类型
      • 有限序列
    • 基本操作
      • InitList(&L)
      • Length(L)
      • LocateElem(L,e)
      • GetElem(L,i)
      • ListInsert(&L,i,e)
      • ListDelete(&L,i,&e)
      • PrintList(L)
      • Empty(L)
      • DestoryList(&L)
    • 表示方式
      • 顺序表示
        • 特点
          • 逻辑上相连物理位置也相连
          • 可以静态分配也可以动态分配
          • 随机存取
          • 存储密度高
        • 基本操作
          • 插入、删除、按值查找
      • 链式表示
        • 特点
          • 物理位置不要求连续
          • 通过指针链接数据单元
          • 非随机存取
        • 类型
          • 单链表
          • 双链表
          • 循环链表
            • 循环单链表
            • 循环双链表
          • 静态链表
  • 第3章 栈和队列
    • 栈
      • 定义
        • 只能在一端插入或删除的线性表
      • 基本操作
        • InitStack(&S)
        • StackEmpty(S)
        • Push(&S,x)
        • Pop(&S,&x)
        • GetTop(S,&x)
        • ClearStack(&S)
      • 存储
        • 顺序栈
          • 共享栈
        • 链栈
    • 队列
      • 定义
        • 在一端插入，在另一端删除的线性表
      • 基本操作
        • InitQueue(&Q)
        • QueueEmpty(Q)
        • EnQueue(&Q,x)
        • DeQueue(&Q,&x)
        • GetHead(Q,&x)
      • 存储
        • 顺序存储结构
          • 顺序队列
          • 循环队列
        • 链式存储结构
          • 链式队列
      • 特殊
        • 双端队列
        • 输出受限的双端队列
        • 输入受限的双端队列
    • 栈和队列的应用
      • 栈
        • 括号匹配
        • 表达式求值
        • 递归
      • 队列
        • 层次遍历
        • 计算机系统中的资源竞争
    • 特殊矩阵(数组)
      • 顺序存储
      • 压缩
        • 对称矩阵
        • 三角矩阵
        • 三对角矩阵
        • 稀疏矩阵
  • 第4章 树与二叉树
    • 树
      • 定义
        • 1.有且只有一个根结点
        • 2.其余结点可分为互不相交的有限集合
        • 3.这些集合本身又是一棵树
        • 4.除根结点外，其余结点有且只有一个前驱结点
      • 基本术语
        • 度
        • 深度、高度、层次
        • 有序树、无序树
        • 路径、路径长度
        • 权、带权路径长度
      • 性质
        • 1.树的结点数=所有结点的度数+1
        • 2.度为m的树中第i层至多有m^(i-1)个结点
        • 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
        • 4.具有n个结点的m叉树最小高度为㏒m(n(m-1)+1)
      • 存储结构
        • 双亲表示法
        • 孩子表示法
        • 孩子兄弟表示法
      • 操作
        • 先根遍历
        • 后根遍历
        • 层次遍历
    • 二叉树
      • 定义
        • 1.每个结点至多只有两颗子树
        • 2.子树有左右之分
        • 3.子树也为二叉树
      • 特殊的二叉树
        • 满二叉树
        • 完全二叉树
        • 二叉排序树
        • 平衡二叉树
      • 性质
        • 1.叶子结点数=度为2的结点数+1
        • 2.第k层至多有2^(k-1)个结点
        • 3.高度为h至多有2^h-1个结点
        • 4.n个结点的完全二叉树高度为log2(n+1)或(log2n)+1
      • 存储结构
        • 顺序存储
        • 链式存储
      • 操作
        • 遍历
          • 先序遍历/PreOrder
          • 中序遍历/InOrder
          • 后序遍历/PostOrder
          • 层次遍历
        • 构造
        • 线索化
    • 森林
      • 定义
        • 树的集合
    • 树、二叉树、森林的转换
    • 树与二叉树的应用
      • 并查集
      • 二叉排序树/BST
        • 查找
        • 插入
        • 删除
        • 构造
      • 平衡二叉树/AVL
        • 查找
        • 插入
          • LL平衡旋转
          • LR平衡旋转
          • RL平衡旋转
          • RR平衡旋转
      • 哈夫曼树
        • 定义
          • 带权路径长度(WPL)最小的二叉树
        • 构造
        • 哈夫曼编码
  • 第5章 图
    • 基本概念
      • 有向图、无向图
      • 简单图、多重图
      • 完全图
      • 子图
      • (无向图)连通、连通图、连通分量
      • (有向图)强连通图、强连通分量
      • 生成树、生成森林
      • 结点的度、入度、出度
      • 边的权、网
      • 稠密图、稀疏图
      • 路径、路径长度、回路
      • 简单路径、简单回路
      • 距离
      • 有向树
    • 存储
      • 邻接矩阵法
      • 邻接表法
      • 邻接多重表(无向图)
      • 十字链表(有向图)
    • 操作
      • Adjacent(G,x,y)
        • 判断图G是否存在边\<x,y>或(x,y)。
      • Neighbors(G,x)
        • 列出图G中与结点x邻接的边。
      • InsertVertex(G,x)
        • 插入结点x。
      • DeleteVertex(G,x)
        • 删除结点x。
      • AddEdge(G,x,y)
        • 添加边(x,y)或\<x,y>。
      • RemoveEdge(G,x,y)
        • 删除边(x,y)或\<x,y>。
      • FirstNeighbor(G,x)
        • 求结点x的第一个邻接点。
      • NextNeighbor(G,x,y)
        • 返回除y之外的下一个邻接点。
      • Get_edge_value(G,x,y)
        • 获取边(x,y)或\<x,y>对应的权值。
      • Set_edge_value(G,x,y)
        • 设置边(x,y)或\<x,y>的权值。
    • 遍历
      • 广度优先搜索(BFS)
      • 深度优先搜索(DFS)
    • 应用
      • 最小生成树(MST)
        • Prim算法
        • Kruskal算法
      • 最短路径
        • Dijkstra算法
        • Floyd-Warshall算法
      • 拓扑排序
        • 有向无环图(DAG)
      • 关键路径
        • AOE网
  • 第6章 查找
    • 基本概念
      • 查找
      • 查找表/查找结构
      • 基本操作
        • 查找元素是否存在(找)
        • 检索满足条件的元素的属性(读)
        • 插入元素(增)
        • 删除元素(删)
      • 静态查找表、动态查找表
      • 关键字
      • 平均查找长度
    • 查找方法
      • 顺序查找
        • 一般线性表
        • 有序表
      • 折半查找
      • 分块查找
    • B树、B+树
    • 散列表
      • 散列函数
        • 直接定址法
        • 除留余数法
        • 平方取中法
        • 折叠法
      • 散列表
      • 处理冲突
        • 开放定址法
        • 拉链法(链接法)
    • 串(字符串)
      • 定义
      • 存储结构
        • 定长顺序表示
        • 堆分配存储表示
        • 块链存储表示
      • 基本操作
        • StrAssign(&T,chars)
        • StrCopy(&T,S)
        • StrEmpty(S)
        • StrCompare(S,T)
        • StrLength(S)
        • SubString(&Sub,S,pos,len)
        • Concat(&T,S1,S2)
        • Index(S,T,pos)
        • Replace(&S,pos,T,V)
        • StrInsert(&S,pos,T)
        • StrDelete(&S,pos,len)
        • ClearString(&S)
        • DestoryString(&S)
      • 模式匹配
        • KMP算法
  • 第7章 排序
    • 基本概念
      • 定义
      • 稳定性
    • 内部排序
      • 插入排序
        • 直接插入排序
        • 折半插入排序
        • 希尔排序
      • 交换排序
        • 冒泡排序
        • 快速排序
      • 选择排序
        • 简单选择排序
        • 堆排序
          • 小根堆/小顶堆
          • 大根堆/大顶堆
      • 归并排序
      • 基数排序
    • 外部排序
      • 多路归并排序
      • 多路平衡归并、败者树

---

正文

---

第1章 绪论

基本概念

• 数据结构三要素

  • 逻辑结构

    • 线性结构

      • 线性表
      • 栈
      • 队列

    • 非线性结构

      • 集合
      • 树
      • 图

  • 存储结构

    • 顺序存储
    • 链式存储
    • 索引存储
    • 散列存储

  • 运算

算法

• 五个特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

• 效率度量

  • 时间复杂度
  • 空间复杂度

第2章 线性表

基本概念

• 相同数据类型
• 有限序列

基本操作

• InitList(&L)
• Length(L)
• LocateElem(L,e)
• GetElem(L,i)
• ListInsert(&L,i,e)
• ListDelete(&L,i,&e)
• PrintList(L)
• Empty(L)
• DestoryList(&L)

表示方式

• 顺序表示

  • 特点

    • 逻辑上相连物理位置也相连
    • 可以静态分配也可以动态分配
    • 随机存取
    • 存储密度高

  • 基本操作

    • 插入、删除、按值查找

• 链式表示

  • 特点

    • 物理位置不要求连续
    • 通过指针链接数据单元
    • 非随机存取

  • 类型

    • 单链表
    • 双链表

    • 循环链表

      • 循环单链表
      • 循环双链表

    • 静态链表

第3章 栈和队列

栈

• 定义

  • 只能在一端插入或删除的线性表

• 基本操作

  • InitStack(&S)
  • StackEmpty(S)
  • Push(&S,x)
  • Pop(&S,&x)
  • GetTop(S,&x)
  • ClearStack(&S)

• 存储

  • 顺序栈

    • 共享栈

  • 链栈

队列

• 定义

  • 在一端插入，在另一端删除的线性表

• 基本操作

  • InitQueue(&Q)
  • QueueEmpty(Q)
  • EnQueue(&Q,x)
  • DeQueue(&Q,&x)
  • GetHead(Q,&x)

• 存储

  • 顺序存储结构

    • 顺序队列
    • 循环队列

  • 链式存储结构

    • 链式队列

• 特殊

  • 双端队列
  • 输出受限的双端队列
  • 输入受限的双端队列

栈和队列的应用

• 栈

  • 括号匹配
  • 表达式求值
  • 递归

• 队列

  • 层次遍历
  • 计算机系统中的资源竞争

特殊矩阵(数组)

• 顺序存储

• 压缩

  • 对称矩阵
  • 三角矩阵
  • 三对角矩阵
  • 稀疏矩阵

第4章 树与二叉树

树

• 定义

  • 1.有且只有一个根结点
  • 2.其余结点可分为互不相交的有限集合
  • 3.这些集合本身又是一棵树
  • 4.除根结点外，其余结点有且只有一个前驱结点

• 基本术语

  • 度
  • 深度、高度、层次
  • 有序树、无序树
  • 路径、路径长度
  • 权、带权路径长度

• 性质

  • 1.树的结点数=所有结点的度数+1
  • 2.度为m的树中第i层至多有m^(i-1)个结点
  • 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
  • 4.具有n个结点的m叉树最小高度为㏒m(n(m-1)+1)

• 存储结构

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

• 操作

  • 先根遍历
  • 后根遍历
  • 层次遍历

二叉树

• 定义

  • 1.每个结点至多只有两颗子树
  • 2.子树有左右之分
  • 3.子树也为二叉树

• 特殊的二叉树

  • 满二叉树
  • 完全二叉树
  • 二叉排序树
  • 平衡二叉树

• 性质

  • 1.叶子结点数=度为2的结点数+1
  • 2.第k层至多有2^(k-1)个结点
  • 3.高度为h至多有2^h-1个结点
  • 4.n个结点的完全二叉树高度为log2(n+1)或(log2n)+1

• 存储结构

  • 顺序存储
  • 链式存储

• 操作

  • 遍历

    • 先序遍历/PreOrder
    • 中序遍历/InOrder
    • 后序遍历/PostOrder
    • 层次遍历

  • 构造

  • 线索化

森林

• 定义

  • 树的集合

树、二叉树、森林的转换

树与二叉树的应用

• 并查集

• 二叉排序树/BST

  • 查找
  • 插入
  • 删除
  • 构造

• 平衡二叉树/AVL

  • 查找

  • 插入

    • LL平衡旋转
    • LR平衡旋转
    • RL平衡旋转
    • RR平衡旋转

• 哈夫曼树

  • 定义

    • 带权路径长度(WPL)最小的二叉树

  • 构造

  • 哈夫曼编码

第5章 图

基本概念

• 有向图、无向图
• 简单图、多重图
• 完全图
• 子图
• (无向图)连通、连通图、连通分量
• (有向图)强连通图、强连通分量
• 生成树、生成森林
• 结点的度、入度、出度
• 边的权、网
• 稠密图、稀疏图
• 路径、路径长度、回路
• 简单路径、简单回路
• 距离
• 有向树

存储

• 邻接矩阵法
• 邻接表法
• 邻接多重表(无向图)
• 十字链表(有向图)

操作

• Adjacent(G,x,y)

  作用：

判断图G是否存在边<x,y>或(x,y)。

• Neighbors(G,x)

  作用：

列出图G中与结点x邻接的边。

• InsertVertex(G,x)

  作用：

插入结点x。

• DeleteVertex(G,x)

  作用：

删除结点x。

• AddEdge(G,x,y)

  作用：

添加边(x,y)或<x,y>。

• RemoveEdge(G,x,y)

  作用：

删除边(x,y)或<x,y>。

• FirstNeighbor(G,x)

  作用：

求结点x的第一个邻接点。

• NextNeighbor(G,x,y)

  作用：

返回除y之外的下一个邻接点。

• Get_edge_value(G,x,y)

  作用：

获取边(x,y)或<x,y>对应的权值。

• Set_edge_value(G,x,y)

  作用：

设置边(x,y)或<x,y>的权值。

遍历

• 广度优先搜索(BFS)
• 深度优先搜索(DFS)

应用

• 最小生成树(MST)

  • Prim算法
  • Kruskal算法

• 最短路径

  • Dijkstra算法
  • Floyd-Warshall算法

• 拓扑排序

  • 有向无环图(DAG)

• 关键路径

  • AOE网

第6章 查找

基本概念

• 查找
• 查找表/查找结构

• 基本操作

  • 查找元素是否存在(找)
  • 检索满足条件的元素的属性(读)
  • 插入元素(增)
  • 删除元素(删)

• 静态查找表、动态查找表

• 关键字
• 平均查找长度

查找方法

• 顺序查找

  • 一般线性表
  • 有序表

• 折半查找

• 分块查找

B树、B+树

散列表

• 散列函数

  • 直接定址法
  • 除留余数法
  • 平方取中法
  • 折叠法

• 散列表

• 处理冲突

  • 开放定址法
  • 拉链法(链接法)

串(字符串)

• 定义

• 存储结构

  • 定长顺序表示
  • 堆分配存储表示
  • 块链存储表示

• 基本操作

  • StrAssign(&T,chars)
  • StrCopy(&T,S)
  • StrEmpty(S)
  • StrCompare(S,T)
  • StrLength(S)
  • SubString(&Sub,S,pos,len)
  • Concat(&T,S1,S2)
  • Index(S,T,pos)
  • Replace(&S,pos,T,V)
  • StrInsert(&S,pos,T)
  • StrDelete(&S,pos,len)
  • ClearString(&S)
  • DestoryString(&S)

• 模式匹配

  • KMP算法

第7章 排序

基本概念

• 定义
• 稳定性

内部排序

• 插入排序

  • 直接插入排序
  • 折半插入排序
  • 希尔排序

• 交换排序

  • 冒泡排序
  • 快速排序

• 选择排序

  • 简单选择排序

  • 堆排序

    • 小根堆/小顶堆
    • 大根堆/大顶堆

• 归并排序

• 基数排序

外部排序

• 多路归并排序
• 多路平衡归并、败者树