数据结构线性表栈队列知识点笔记

数据结构线性表栈队列知识点笔记：查找：顺序查找、折半查找、B-树和B+树；排序：简单选择排序、二路归并排序、基数排序。

数据结构线性表栈队列知识点笔记

• 线性表
  • 定义
  • 基本操作
    • 初始化
    • 随机访问
    • 定位查找
    • 插入
    • 删除
    • 求表长
    • 倒序
  • 实现
    • 顺序存储
    • 链式存储
      • 单向链表
      • 循环链表
      • 双向链表
    • 应用
      • 用链表表示多项式
• 栈
  • 基本概念
    • 定义
    • 基本操作
      • 初始化
      • 栈满判断
      • 入栈
      • 栈空判断
      • 出栈
  • 顺序存储结构
  • 链式存储结构
  • 应用
    • 表达式求值
    • 迷宫问题
• 队列
  • 基本概念
    • 定义
    • 初始化
    • 满判断
    • 入队列
    • 空判断
    • 出队列
  • 顺序存储结构
  • 链式存储结构
  • 对角矩阵的压缩存储
  • 对称矩阵的压缩存储
• 图
  • 基本概念
  • 存储
    • 邻接矩阵法
    • 邻接表法
  • 遍历
    • 深度优先
    • 广度优先
  • 应用
    • 最小生成树
      • Kruskal算法
      • Prim算法
    • 最短路径
      • Dijkstra算法
      • Floyd算法
    • 拓扑排序
    • 关键路径
• 树与二叉树
  • 基本概念
  • 二叉树
    • 二叉树的顺序存储结构
    • 二叉树的链式存储结构
    • 二叉树的遍历
      • 前序
      • 中序
      • 后序
      • 非递归
    • 线索二叉树
      • 结构
      • 遍历
  • 树和森林
    • 树的存储结构
      • 双亲表示法
      • 孩子链表表示法
      • 孩子兄弟表示法
    • 森林与二叉树的转换
    • 树和森林的遍历
  • 树的应用
    • 二叉排序树
      • 查找
      • 插入
      • 删除
    • 平衡二叉树
    • 哈弗曼树
• 排序
  • 插入排序
    • 直接插入排序
    • 折半插入排序
  • 气泡排序
  • 简单选择排序
  • 希尔排序
  • 快速排序
  • 二路归并排序
  • 堆排序
  • 基数排序
  • 应用
• 查找
  • 顺序查找
  • 折半查找
  • B-树和B+树
    • 基本概念
    • 基本操作
      • 查找
      • 插入
      • 删除
  • 哈希
    • 函数设计
      • 除留余数法
      • 平方取中法
      • 数字分析法
      • 折叠法
    • 冲突解决
      • 链式存储法
      • 开放地址法
        • 线性探测法
        • 平方探测法
    • 装填因子
    • 平均查找长度
    • 平均成功/不成功查找次数