My logo
Published on

书籍-数据结构

概论

数据结构的作用，意义，基本概念和术语

逻辑结构 （分为线性结构和非线性结构两大类）

  1. 集合结构
  2. 线性结构
  3. 树形结构-非线形
  4. 图形结构-飞线形

物理结构

  1. 顺序结构
  2. 链式结构
  3. 索引存储机构
  4. 散列存储结构

算法的描述和分析

算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有序序列，并且没跳指令表示一个或多个操作。

算法的特性

  1. 输入
  2. 输出
  3. 有穷性
  4. 确定性
  5. 可行性

算法的复杂度

  • 时间复杂度

    • 推导大O阶方法：常数阶，线形阶，对数阶，平方阶

  • 空间复杂度

一，线性表

1.1 线形表的逻辑结构

  1. 线形表的逻辑定义和性质

  2. 线性表上定义的基本运算

1.2 线形表的顺序存储结构和基本运算

  1. 顺序表的定义和特点
  2. 顺序表上进行插入和删除操作的实现以及时间性能分析
  3. 理解求顺序表逆置和极值及定位两种算法的实现过程
  4. 优缺点：读数据的时候，时间复杂度是O(1)；而插入或删除，时间复杂度都是O(n)。

1.3 线性表链式存储结构的不同形式及基本运算

  1. 单链表，循环链表，双向链表的定义及特点
  2. 单链表上实现建表，查找，插入和删除等基本算法，并分析其时间复杂度
  3. 用尾指针表示单循环链表的意义
  4. 双向链表上的插入和删除操作

需要理解的实现

  1. 头插入法和尾插入法
  2. 循环链表
  3. 双向链表
  4. 静态链表（暂时不深入）
  5. 概念（Node）：数据域，指针域，节点

二，栈和队列

2.1 栈的逻辑结构，存储结构以及相关算法

  1. 栈的逻辑定义，特点及运算
  2. 顺序栈和链栈上实现进栈，退栈等基本运算
  3. 顺序栈的上溢和下溢问题，如何防止溢出

2.2 队列的逻辑结构，存储结构以及相关算法

  1. 队列的逻辑定义，特点以及运算
  2. 顺序循环队列的表述：队空和队满的判定；顺序循环队列上入队，出队等基本算法
  3. 链队列的表述：带头节点和不带头节点两种情况下链队列上的基本算法

2.3 栈和队列的应用

  1. 圆括号匹配的检验问题
  2. 字符串回文的判断问题
  3. 数制转换
  4. 利用栈实现程序的递归
  5. 表达式求值（重点）

三，多维数组和广义表

3.1 多维数组及其运算

  1. 多维数组的逻辑结构表达以及特征
  2. 多维数组的顺序存储结构及地址计算方法
  3. 多维数组的常用运算

3.2 矩阵的压缩存储

  1. 特殊矩阵的类型和性质，稀疏矩阵的概念
  2. 用一维数组压缩存储特殊矩阵时，存储地址的计算
  3. 稀疏矩阵的三元组表表示方法及其常用算法

3.3 广义表

  1. 什么是广义表
  2. 广义表的定义及特性
  3. 求广义表的深度，表长，表头和表尾运算

四，树和二叉树

4.1 树的概念

  1. 树的定义和表示方法
  2. 树的常用术语及其含义

4.2 二叉树的概念

  1. 二叉树的递归定义
  2. 二叉树的性质及其证明，两种特殊形式的二叉树
  3. 二叉树的顺序存储和链式存储

4.3 二叉树的运算

  1. 二叉链表的生成
  2. 二叉树的应用

4.4 线索二叉树

  1. 二叉树线索化的含义，线索二叉树结点的表示方法
  2. 对给定二叉树进行线索化的思想和实现
  3. 二叉线索链表上的运算：查找某节点的后继节点和线索二叉树的遍历

4.5 树和森林

  1. 树的三种存储结构表示方法
  2. 树和森林的遍历

4.6 哈夫曼树及其应用

  1. 最优二叉树的概念，哈夫曼算法的思想
  2. 哈夫曼算法的实现
  3. 编码，前缀编码，哈夫曼编码的概念；根据最优二叉树构造对应的哈夫曼编码

五，图

5.1 图的概念

  1. 图的定义和表示方法
  2. 图的常用术语及其含义
  3. 图的分类
  • 方向
  • 无向图 ：【顶点(度)-边-生成树】
  • 有向图 ：【顶点(人度｜出度)-弧-有向树-生成森林】
  1. 边分类
  • 稀疏图
  • 稠密图
  1. 完全图-有向完全图
  2. 简单图
  3. 顶点
  • 邻接点
  • 依附
  1. 网-权
  2. 路径
  • 连通
    • 连通图-强连通图
    • 连通分量-强连通分量
  • 环
    • 简单路径

5.2 图的存储结构

  1. 图的邻接矩阵表示法
  2. 图的邻接表表示法

5.3 图的遍历算法

  1. 深度优先搜索遍历的算法思想：以邻接矩阵和邻接表分别作为图的存储结构；其深度优先搜索遍历的算法实现及其时间复杂度
  2. 广度优先搜索遍历的算法思想：以邻接矩阵和邻接表分别作为图的存储结构，其广度优先搜索遍历的算法实现及其时间复杂度
  3. 深度优先搜索遍历算法中递归的应用和广度优先搜索遍历算法中队列的应用

5.4 图的生成树和最小生成树

  1. 生成树的概念
  2. 对遍历给定的图，求其深度优先和广度优先生成树
  3. 最小生成树的概念及其性质
  4. Prim算法和Kruskal算法的基本思想及其实现

5.5 最短路径

  1. 最短路径问题的描述
  2. Dijkstra 算法的基本思想及其实现过程

5.6 拓扑排序

  1. 拓扑排序的实际意义
  2. 对有向图构造其顶点的拓扑序列，判断有向图中是否有环
  3. 拓扑排序的基本思想及其算法

六，串

  1. 串的定义
  2. 串的比较
  3. 串的抽象数据类型和串的存储结构
  4. 朴素的模式匹配算法
  5. KMP模式匹配算法

七，排序

7.1 排序的基本概念

7.2 插入排序

7.3 交换排序

7.4 选择排序

7.5 归并排序的基本思想及算法实现

7.6 分配排序

7.7 各种内部排序算法的分析比较

八，查找

8.1 查找的基本概念

8.2 顺序表的查找

8.3 树表的查找

8.4 散列表查找

8.5 有序表的查找（效率由低到高）

  1. 顺序查找（有哨兵和没有哨兵）
  2. 折半查找
  3. 插值查找
  4. 斐波那契查找

8.6 线形索引查找（效率由低到高）

  1. 稠密索引
  2. 分块索引-普遍被用于数据库表查找等技术
  3. 倒排索引-ES 搜索使用到这个算法
  4. 二叉排序树（又叫二叉查找树）
  5. 平衡二叉树（AVL树）