数据结构笔记

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。下图为数据结构的笔记，粗略记录了不同章节的主要内容，仅做概览。

数据结构

• 绪论
  • 结构
    • 逻辑结构
      • 集合
      • 线性
      • 树形
      • 图状
    • 存储结构
      • 顺序存储
      • 链式存储
  • 算法评级
    • 基本标准
    • 时间复杂度
    • 空间复杂度
• 线性表
  • 定义和实现
  • 两种存储结构
    • 顺序存储
      • 掌握算法
        • 取值
        • 查找定位
        • 插入
        • 删除
    • 链式存储
      • 掌握的知识点
      • 算法操作
        • 单链表
          • 取值
          • 查找
          • 插入
          • 删除
          • 遍历等
          • 创建
            • 前插（栈）
            • 后插（队）
        • 循环链表
          • 插入
          • 删除
          • 遍历等
          • 实现线性表其他运算的算法
        • 双向链表
          • 插入
          • 删除
          • 遍历等
          • 实现线性表其他运算的算法
    • 应用对比
      • 比较
        • 存储密度
        • 时间性能
      • 线性表合并
        • 无序表
        • 有序表
      • 链式有序
  • 时间复杂度和空间复杂度的角度综合考虑线性表在顺序和链事存储结构下的特点及其各自使用的场合
• 栈和队列
  • 顺序栈
    • 进站
    • 出站
    • 取元素
    • 沾满和占空的特点
  • 链栈
    • 进站
    • 出站
    • 取元素
    • 沾满和占空的特点
  • 递归
  • 循环队列
    • 原理
    • 队满和空的条件
    • 进站
    • 出站
    • 取元素
  • 链队列
    • 入队
    • 出队
    • 取元素
  • 存取数据的特点
• 数组和广义表
  • 按行优先
  • 按列优先
  • 多维数组中的某个数组元素地址求解
  • 串
    • 存储结构
      • 顺序串
      • 链串
      • 堆串
    • BF算法
    • KMP算法
      • next值
      • 修正next值
  • 数组
    • 定义
    • 顺序存储
    • 压缩存储
      • 特殊矩阵
        • 对称矩阵
          • 压缩
          • 存储
        • 三角矩阵
          • 压缩
          • 存储
        • 对角矩阵
          • 压缩
          • 存储
      • 稀疏矩阵
        • 三元组
        • 行逻辑链接的顺序表
        • 十字链表存储
  • 广义表
    • 概念
    • 表头与表尾定义
    • 链式存储两种形式
      • 头尾链表
      • 扩展线性表存储
• 树和二叉树
  • 二叉树
    • 二叉树的定义
    • 特殊二叉树的定义
      • 完全二叉树
      • 满二叉树
      • 线索二叉树
        • 构造
        • 遍历
          • 先序列
          • 中序
          • 后序
    • 两种存储结构
      • 顺序存储
      • 链式存储
        • 二插链表
    • 遍历方式
      • 先序列
      • 中序
      • 后序
    • 二叉树的构造
      • 先序中序序列
      • 后序中序序列
    • 复制二叉树
    • 计算深度
    • 节点个数
    • 三种存储方法
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟表示法
  • 森林
    • 表示
    • 遍历
      • 先序
      • 后序
    • 转换
  • 哈夫曼树
    • 构造过程
    • 赫夫曼编码原理
• 图
  • 图的定义和相关术语
  • 三种存储结构
    • 数组表示法
    • 邻接表
    • 十字链表
  • 两种遍历方式
    • 深度优先搜索
    • 广度优先搜索
  • 图的相关应用
    • 最小生成树
      • 普里姆算法
      • 鲁克斯卡算法
    • 拓扑排序
    • 关键路径
    • 最短路径
      • 迪杰斯特拉算法
      • 弗洛伊德算法
  • 理解算法原理及解决的实际问题
• 查找
  • 两种存储表
    • 静态查找
      • 特点
      • 相关操作
        • 顺序表
        • 有序表的查找 折半查找
        • 索引顺序表的查找原理
        • 能够运用平均查找长度概念对查找性能进行分析
    • 动态查找表
      • 特点
      • 相关操作
        • 二叉排序树
          • 定义
          • 构造过程
          • 插入
          • 删除
          • 性能分析
        • 二叉平衡树
          • 定义
          • 构建
            • LL
            • LR
            • RR
            • RL
        • B-树
          • 定义
          • 插入
          • 删除
          • 性能分析
        • 哈希树
          • 定义
          • 构造方法
          • 处理冲突方法
          • 查找及性能分析
• 排序
  • 排序的定义
  • 稳定和不稳定的定义
  • 排序算法
    • 插入排序
      • 直接插入
      • 折半插入
    • 希尔排序
      • 原理
      • 应用
    • 交换排序
      • 冒泡排序
        • 原理
        • 应用
      • 快速排序
        • 原理
        • 应用
    • 选择排序
      • 简单选择排序
        • 原理
        • 应用
      • 堆排序
        • 原理
        • 应用
    • 归并排序
      • 原理
      • 应用
    • 基数排序
    • 外部排序