26数据结构王道书知识点梳理

专为计算机考研学子设计！本导图严格依据王道考研教材体系化梳理，通过树状逻辑与高频考点标注，帮助考生快速掌握数据结构核心脉络，建立清晰的知识体系。原创内容经深度提炼，涵盖线性表、树、图等全模块精华，直击408统考重点。助你省时省力突破复习瓶颈！

数据结构

• 第一章 绪论
  • 数据结构的基本概念
    • 基本概念和术语
      • 数据
      • 数据元素
      • 数据对象
      • 数据类型
        • 原子类型
        • 结构类型
        • 抽象数据类型
    • 数据结构三要素
      • 数据的逻辑结构
      • 数据的存储结构
        • 顺序存储
        • 链式存储
        • 索引存储
        • 散列存储
      • 数据的运算
  • 算法和算法评价
    • 算法的基本概念
    • 算法效率的度量
      • 时间复杂度
        • 算法中基本运算的执行次数的数量级作为该算法的时间复杂度
        • 时间复杂度的计算
          • while循环
          • 一层for循环
          • 两层for循环
          • 概要
      • 空间复杂度
• 第二章 线性表
  • 线性表的定义和基本操作
    • 线性表的定义
      • 具有相同数据类型的n(n>0)个数据元素的有限序列
    • 线性表的基本操作
  • 线性表的顺序表示
    • 顺序表的定义
      • 线性表的顺序存储也称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
    • 顺序表上基本操作的实现
      • 顺序表的初始化
      • 插入操作
      • 删除操作
      • 按值查找(顺序查找)
  • 线性表的链式表示
    • 单链表的定义
    • 单链表上基本操作的实现
      • 单链表的初始化
      • 求表长操作
      • 按序号查找结点
      • 按值查找表结点
      • 插入结点操作
      • 删除结点操作
      • 采用头插法建立单链表
      • 采用尾插法建立单链表
    • 双链表
    • 循环链表
      • 循环单链表
      • 循环双链表
        • 头结点的前驱和后继都指向自己则循环双链表为空
    • 静态链表
    • 顺序表和链表的比较
• 第八章 排序
  • 排序的基本概念
  • 插入排序
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序、基数排序和计数排序
  • 各种内部排序算法的比较
  • 外部排序
• 第七章 查找
  • 查找的基本概念
  • 顺序查找和折半查找
    • 顺序查找
    • 折半查找
    • 分块查找
  • 树形查找
    • 二叉排序树(BST)
      • 查找
        • 每次找一半，key大于节点值的去其右子树继续找，key小于节点值的去其左子树继续找，以 此类推，直到等于或者为空，分别代表找到和未找到
      • 插入
        • 二叉排序树是一个查找表，插入一个关键字首先要找到插入位置。对于一个不存在于二叉排序树 中的关键字，其查找不成功的位置即为该关键字的插入位置  在插入过程中如果待插入关键字已经存在，则返回 0，代表插入不成功  如果待插入关键字不存在，则插入，并返回 1,代表插入成功  每次插入操作，插入位置都是叶子节点
      • 删除
        •  p结点为叶子结点。直接删除即可，不会破坏二叉排序树的特性  p结点只有一课左子树或右子树。删除后让其子树替代即可。  p结点有左、右两棵子树，则令p节点左子树的最右下节点或右子树的最左下节点替代p，
    • 平衡二叉树
      • 建立
        • 建立平衡二叉树的过程和建立二叉排序树的过程基本一样，都是将关键字逐个插入空树 中的过程。所不同的是，如果失去平衡则需要进行平衡调整，即树中出现平衡因子绝对值大于 1 的结点。
      • 调整
      • 删除
    • 红黑树
  • B树和B＋树
    • B树及其基本操作
      • 特点
      • 查找
        • 与二叉查找树相似，只是每个结点都是多个关键字的有序表，在B树上查找到某个结点 后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查 找。若查找到叶子节点，则说明查找失败。 ①在B树中找结点:在磁盘上进行。②在结点内找关键字:在内存中进行。
      • 插入
      • 删除
    • B＋树的基本概念
  • 散列表（Hash）
    • 散列表的基本概念
      • ●思想:根据给定的关键字计算出关键字在表中的地址。 ●散列函数:把表中关键字映射成该关键字对应的地址的函数，记为Hash(key) =Address ●散列表:建立关键字和存储地址之间的一种直接映射关系。 ●冲突:散列函数可能会把两个或两个以上的不同关键字映射到同一地址。
    • 散列函数的构造方法
    • 处理冲突的方法
    • 散列查找及性能分析的应用
• 第六章 图
  • 图的基本概念
    • 图的定义
      • 定点的度、入度、出度：无向图的顶点的度之和等于边数的两倍。有向图的出度之和=入度之和=边数。
  • 图的存储及基本操作
    • 邻接矩阵法
    • 邻接表法
    • 十字链表
    • 邻接多重表
    • 图的基本操作
  • 图的遍历
    • 广度优先搜索
    • 深度优先搜索
    • 图的遍历与图的连通性
  • 图的应用
    • 最小生成树
      • Prim（普里姆）
        • 每次都选择相邻的权值最小的边
      • Kruskal（克鲁斯卡尔）
        • 每次都选择权值最小的边
    • 最短路径
      • 单源最短路径
        • BFS算法（无权图）
        • Dijkstra算法（带权图、无权图）
      • 各顶点间的最短路径
        • Floyd算法（带权图、无权图）
    • 有向无环图描述表达式
    • 拓扑排序
    • 关键路径
• 第五章 树与二叉树
  • 树的基本概念
    • 树的定义
    • 基本术语
    • 树的性质
      • n个结点的树有n-1条边
  • 二叉树的概念
    • 二叉树的定义及其主要特性
      • 二叉树的定义
        • 二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意倒。
      • 几种特殊的二叉树
        • 满二叉树
        • 完全二叉树
        • 二叉排序树
          • 左子树上所有结点的关键字均小于根结点的关键字;右子树上所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。
        • 平衡二叉树
          • 左右的高度之差的绝对值不超过1
        • 正则二叉树
          • 树中只有度为0或2的结点
      • 二叉树的性质
        • n0 = n2 + 1
        • 完全二叉树
    • 二叉树的存储结构
      • 顺序存储结构
      • 链式存储结构
  • 二叉树的遍历和线索二叉树
    • 二叉树的遍历
      • 线序遍历
        • 根左右
      • 中序遍历
        • 左根右
      • 后序遍历
        • 左右根
      • 层次遍历
      • 由遍历序列构造的二叉树
        • 由先序序列和中序序列构造二叉树
        • 由后序序列和中序序列构造二叉树
        • 由层次序列和中序序列构造二叉树
        • 先序序列、后序序列、层序序列两两组合，无法唯一确定一棵二叉树
    • 线索二叉树
      • 线索二叉树的基本概念
      • 中序线索二叉树的构造
        • 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
  • 树、森林
    • 树的存储结构
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟表示法（左孩子右兄弟）
    • 树、森林与二叉树的转换
      • 树转换为二叉树
      • 森林转换为二叉树
        • 将森林中的每棵树转换为二叉树，将下一棵二叉树作为前一棵二叉树的右子树
      • 二叉树转换为森林
        • 先把右子树全部拆下，再把各个二叉树转为树
    • 树和森林的遍历
      • 树的遍历
        • 先根遍历
        • 后根遍历
      • 森林的遍历
        • 先序遍历森林
        • 中序遍历森林
  • 树与二叉树的应用
    • 哈夫曼树和哈夫曼编码
      • 哈夫曼树
        • 定义
        • 哈夫曼树的构造
      • 哈夫曼编码
    • 并查集
• 第四章 串
  • 串的定义和实现
    • 串的定义
    • 串的基本操作
    • 串的存储结构
  • 串的模式匹配
    • 简单的模式匹配算法
    • 串的模式匹配算法-KMP
    • KMP算法的进一步优化
• 第三章 栈、队列和数组
  • 栈
    • 栈的基本概念
      • 栈(Stack)是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
      • 当n个不同元素入栈时，出栈元素不同排列的个数为
    • 栈的顺序存储结构
      • 顺序栈的实现
      • 顺序栈的基本操作
      • 共享栈
    • 栈的链式存储结构
  • 队列
    • 队列的基本概念
      • 队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。其操作的特性是先进先出(First In First Out, FIFO)。
    • 队列的顺序存储结构
      • 队列的顺序存储
        • 不可用Q.rear=MaxSize作为队列满的条件，（d）中队列只有一个元素，但仍满足该条件。这时入队出现“上溢出”，这是一种“假溢出”。
      • 循环队列
        • 判断队空/队满
        • 循环队列的操作
    • 队列的链式存储结构
      • 链式队列的基本操作
    • 双端队列
      • 输出受限的双端队列
      • 输入受限的双端队列
  • 栈和队列的应用
    • 栈在括号匹配中的应用
    • 栈在表达式求值中的应用
    • 栈在递归中的应用
    • 队列在层次遍历中的应用
    • 队列在计算机系统中的应用
  • 数组和特殊矩阵
    • 数组的定义
      • 数组是由 n(n>1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
    • 数组的存储结构
      • 一维数组
      • 二维数组
        • 行优先存储
        • 列优先存储
    • 特殊矩阵的压缩存储
      • 对称矩阵
      • 三角矩阵
      • 三对角矩阵
    • 稀疏矩阵