文章目录

• 趣学数据结构
• • 一、数据结构入门
  • • （一）数据结构的基础知识
    • • 1、基本概念
      • • （1）数据
        • （2）数据元素
        • （3）数据项
        • （4）数据对象
        • （5）数据结构
      • 2、逻辑结构
      • • （1）集合
        • （2）线性结构
        • （3）树形结构
        • （4）图形结构
      • 3、存储结构
      • • （1）顺序存储
        • （2）链式存储
        • （3）散列存储
        • （4）索引存储
    • （二）算法复杂度
    • （三）一盘棋麦子
    • （四）神奇的魔鬼序列
  • 二、数据结构的分类
  • • （一）线性表
    • • 1、线性表的分类
      • • （1）顺序表
        • • ① 静态分配
          • ② 动态分配
          • ③ 顺序表的基本操作
        • （2）单链表
        • • ① 单链表的存储方式
          • ② 单链表的基本操作
        • （3）双向链表
        • • ① 双向链表的基本操作
          • ② 双向链表的存储方式
        • （4）循环链表
      • 2、线性表的应用
      • • （1）合并有序顺序表
        • （2）合并顺序链表
        • （3）就地逆置单链表
        • （4）查找链表的中间节点
        • （5）删除链表的重复元素
    • （二）栈和队列
    • • 1、栈的分类
      • • （1）顺序栈
        • （2）链栈
      • 2、队列的分类
      • • （1）顺序队列
        • • ① 顺序队列的定义
          • ② 循环队列的定义
          • ③ 循环队列的基本操作
        • （2）链队列
      • 3、栈和队列的应用
      • • （1）数制的转换
        • （2）回文判定
        • （3）双端队列
    • （三）字符串
    • • 1、字符串
      • 2、字符串相关的算法
      • • （1）模式匹配BF算法
        • （2）模式匹配KMP算法
        • （3）改进的KMP算法
      • 3、字符串的应用——病毒检测
    • （四）数组和广义表
    • • 1、数组的顺序存储
      • 2、特殊矩阵的压缩存储
      • • （1）对称矩阵
        • （2）三角矩阵
        • （3）对角矩阵
        • （4）稀疏矩阵
      • 3、广义表
      • 4、好玩贪吃蛇——数字矩阵
    • （五）树
    • • 1、树
      • • （1）树的定义
        • （2）树的存储结构
        • （3）树、森林与二叉树的转换
      • 2、二叉树
      • • （1）二叉树的性质
        • （2）二叉树的存储结构
        • （3）二叉树的创建
        • （4）二叉树的遍历
        • • ① 先序遍历
          • ② 中序遍历
          • ③ 后序遍历
          • ④ 层次遍历
      • 3、线索二叉树
      • • （1）线索二叉树的存储结构
        • （2）线索二叉树的构造
        • （3）线索二叉树的遍历
      • 4、树和森林的遍历
      • • （1）树的遍历
        • （2）森林的遍历
      • 5、树的应用
      • • （1）二叉树的深度
        • （2）二叉树的叶子树
        • （3）三元组创建二叉树
        • （4）遍历序列还原树
        • （5）哈夫曼树
    • （六）图
    • • 1、图的存储结构
      • • （1）邻接矩阵
        • （2）邻接表
        • （3）十字链表
        • （4）邻接多重表
      • 2、图的遍历
      • • （1）广度优先搜索
        • （2）深度优先搜索
      • 3、图的应用
      • • （1）单源第一短路径——Dijkstra
        • （2）各项点之间第一短路径——Floyd
        • （3）第一小生成树——prim
        • （4）第一小生成树——kruskal
        • （5）头拓扑排序
        • （6）关键路径
    • （七）查找
    • • 1、线性表的查找
      • • （1）顺序查找
        • （2）折半查找
      • 2、树表的查找
      • • （1）二叉查找树
        • （2）平衡二叉查找树
      • 3、散列表的查找
      • • （1）散列函数
        • （2）处理冲突的方法
        • （3）散列查找及性能分析
    • （八）排序
    • • 1、插入排序
      • • （1）直接插入排序
        • （2）希尔排序
      • 2、交换排序
      • • （1）冒泡排序
        • （2）快速排序
      • 3、选择排序
      • • （1）简单选择排序
        • （2）堆排序
      • 4、合并排序
      • 5、分配排序
      • • （1）桶排序
        • （2）基数排序
    • （九）高级数据结构
    • • 1、并查集
      • 2、优先队列
      • • （1）出队
        • （2）入队
      • 3、B-树
      • • （1）树高与性能
        • （2）查找
        • （3）插入
        • （4）删除
      • 4、B+树
      • 5、B*树
      • 6、红黑树
      • • （1）红黑树的定义
        • （2）树高与性能
        • （3）红黑树与4阶B树
        • （4）查找
        • （5）插入
        • （6）删除