数据结构

数据结构的简单知识点总结，包括数据结构、五个特征、线性表、栈和队列、树与二叉树、查找、排序等等。

数据结构

• 第一章 绪论
  • 数据结构
    • 逻辑结构
      • 线性结构：线性表、栈、队列
      • 非线性结构：树、图、集合
    • 存储结构（物理结构）
      • 子主题
    • 数据的运算
  • 五个特征
    • 算法定义
    • 五个特性：有穷性、确定性、可行性、输入、输出
    • 效率的衡量（时间、空间复杂度）
• 第二章 线性表
  • 顺序存储
    • 顺序表
  • 链式存储
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表（借助数组实现）
• 第三章 栈和队列
  • 栈
    • 顺序栈
    • 链栈
    • 共享栈
  • 队列
    • 循环队列
    • 链式队列
    • 双端队列
  • 数组
    • 一维数组
    • 多维数组：压缩数组、稀疏数组
• 第四章 串
  • 基本概念：主串、字串、串长
  • 存储结构
    • 定长顺序存储
    • 堆分配存储
    • 块链存储
  • 模式匹配算法
    • 暴力匹配法
    • KMP算法
      • 部分匹配值表
      • next数组
      • next函数的推理过程
    • KMP算法的进一步改进-->nextval数组
• 第五章 树与二叉树
  • 二叉树
    • 概念：定义、存储结构
    • 操作
      • 三种遍历
      • 线索二叉树
    • 应用
      • 排序二叉树-->平衡二叉树
      • 哈夫曼树
  • 树和森林
    • 概念：定义、存储结构
    • 操作
      • 与二叉树的转换
      • 遍历
    • 应用：并查集
• 第六章 图
  • 图的定义
  • 图结构的存储
    • 邻接矩阵法、邻接表法
    • 邻接多重表、十字链表
  • 图的遍历
    • 深度优先遍历
    • 广度优先遍历
  • 图的相关应用
    • 最小生成树：Prim算法、Kruskal算法
    • 最短路径：Dijkstra算法、Floyd算法
    • 拓扑算法：AOV网
    • 关键路径：AOE网
• 第七章 查找
  • 基本概念：静态查找、动态查找
  • 线性结构
    • 顺序查找
    • 折半查找
    • 分块查找
  • 树形结构
    • 二叉排序树
    • 二叉平衡树
    • B树、B+树
  • 散列结构 --> 散列表
    • 性能分析
    • 冲突处理
  • 效率指标 --> 平均查找长度
    • 查找成功
    • 查找失败
• 第八章 排序
  • 基本概念
    • 稳定性
    • 衡量标准：时、空复杂度
  • 内部排序
    • 插入排序
    • 交换排序
    • 选择排序
    • 归并排序
    • 基数排序
  • 外部排序 --- 多路归并排序