数据结构

大学数据结构笔记，内容包含线性表、栈和队列、串、数组和广义表、树和二叉树、文件、外部排序、内部排序、查找、动态存储管理、图。

数据结构

• 线性表
  • 类型定义
  • 顺序表示和实现
  • 链式表示和实现
    • 线性链表
    • 循环链表
    • 双向链表
• 栈和队列
  • 栈
    • 抽象数据类型栈的定义
    • 表示和实现
  • 应用举例
    • 数制转换
    • 括号匹配的检验
    • 行编辑程序
    • 迷宫求解
    • 表达式求值
• 串
  • 定义
  • 表示和实现
    • 定长顺序存储表示
    • 堆分配存储表示
    • 串的块链存储表示
  • 应用举例
    • 文本编辑
• 数组和广义表
  • 数组的定义
  • 数组的顺序表示和实现
  • 矩阵的压缩存储
    • 特殊矩阵
    • 稀疏矩阵
  • 广义表的定义
  • 广义表的存储结构
• 树和二叉树
  • 树的定义和基础术语
  • 二叉树
    • 定义
    • 性质
    • 存储结构
  • 遍历二叉树和线索二叉树
    • 遍历二叉树
    • 线索二叉树
  • 树和森林
    • 树的存储结构
    • 森林与二叉树的转换
    • 树和森林的遍历
  • 赫夫曼树及其应用
    • 最优二叉树（赫夫曼树）
    • 赫夫曼编码
• 文件
• 外部排序
  • 外存信息的存取
  • 外部排序的方法
• 内部排序
  • 插入排序
  • 快速排序
  • 选择排序
  • 归并排序
  • 基数排序
  • 各种内部排序方法的比较和讨论
• 查找
  • 静态查找
    • 顺序表的查找
    • 有序表的查找
    • 索引顺序表的查找
  • 动态查找表
    • 二叉顺序树和平衡二叉树
    • B_树和B+树
  • 哈希表
    • 定义
    • 哈希函数的构造方法
    • 处理冲突的方法
    • 哈希表的查找及其方法
• 动态存储管理
  • 可利用空间表及分配方法
  • 边界标识法
    • 可利用空间表的结构
    • 分配算法
    • 回收算法
• 图
  • 图的定义和术语
  • 图的存储结构
    • 数组的表示法
    • 邻接表
    • 十字链表
    • 邻接多重表
  • 图的遍历
    • 深度优先搜索
    • 广度优先搜索
  • 图的连通性问题
    • 无向图的连通分量和生成树
    • 最小生成树
  • 有向无环图及其应用
    • 拓扑排序
    • 关键路径
  • 最短路径
    • 从某个源点到其余各顶点的最短路径
    • 每一对顶点之间的最短路径