《趣学数据结构》大纲

谁践踏了优雅 2023-09-26 20:51 57阅读 0赞

### 文章目录 ###

*  趣学数据结构
 *   *  一、数据结构入门
     *   *  （一）数据结构的基础知识
         *   *  1、基本概念
             *   *  （1）数据
                 *  （2）数据元素
                 *  （3）数据项
                 *  （4）数据对象
                 *  （5）数据结构
             *  2、逻辑结构
             *   *  （1）集合
                 *  （2）线性结构
                 *  （3）树形结构
                 *  （4）图形结构
             *  3、存储结构
             *   *  （1）顺序存储
                 *  （2）链式存储
                 *  （3）散列存储
                 *  （4）索引存储
         *  （二）算法复杂度
         *  （三）一盘棋麦子
         *  （四）神奇的魔鬼序列
     *  二、数据结构的分类
     *   *  （一）线性表
         *   *  1、线性表的分类
             *   *  （1）顺序表
                 *   *  ① 静态分配
                     *  ② 动态分配
                     *  ③ 顺序表的基本操作
                 *  （2）单链表
                 *   *  ① 单链表的存储方式
                     *  ② 单链表的基本操作
                 *  （3）双向链表
                 *   *  ① 双向链表的基本操作
                     *  ② 双向链表的存储方式
                 *  （4）循环链表
             *  2、线性表的应用
             *   *  （1）合并有序顺序表
                 *  （2）合并顺序链表
                 *  （3）就地逆置单链表
                 *  （4）查找链表的中间节点
                 *  （5）删除链表的重复元素
         *  （二）栈和队列
         *   *  1、栈的分类
             *   *  （1）顺序栈
                 *  （2）链栈
             *  2、队列的分类
             *   *  （1）顺序队列
                 *   *  ① 顺序队列的定义
                     *  ② 循环队列的定义
                     *  ③ 循环队列的基本操作
                 *  （2）链队列
             *  3、栈和队列的应用
             *   *  （1）数制的转换
                 *  （2）回文判定
                 *  （3）双端队列
         *  （三）字符串
         *   *  1、字符串
             *  2、字符串相关的算法
             *   *  （1）模式匹配BF算法
                 *  （2）模式匹配KMP算法
                 *  （3）改进的KMP算法
             *  3、字符串的应用——病毒检测
         *  （四）数组和广义表
         *   *  1、数组的顺序存储
             *  2、特殊矩阵的压缩存储
             *   *  （1）对称矩阵
                 *  （2）三角矩阵
                 *  （3）对角矩阵
                 *  （4）稀疏矩阵
             *  3、广义表
             *  4、好玩贪吃蛇——数字矩阵
         *  （五）树
         *   *  1、树
             *   *  （1）树的定义
                 *  （2）树的存储结构
                 *  （3）树、森林与二叉树的转换
             *  2、二叉树
             *   *  （1）二叉树的性质
                 *  （2）二叉树的存储结构
                 *  （3）二叉树的创建
                 *  （4）二叉树的遍历
                 *   *  ① 先序遍历
                     *  ② 中序遍历
                     *  ③ 后序遍历
                     *  ④ 层次遍历
             *  3、线索二叉树
             *   *  （1）线索二叉树的存储结构
                 *  （2）线索二叉树的构造
                 *  （3）线索二叉树的遍历
             *  4、树和森林的遍历
             *   *  （1）树的遍历
                 *  （2）森林的遍历
             *  5、树的应用
             *   *  （1）二叉树的深度
                 *  （2）二叉树的叶子树
                 *  （3）三元组创建二叉树
                 *  （4）遍历序列还原树
                 *  （5）哈夫曼树
         *  （六）图
         *   *  1、图的存储结构
             *   *  （1）邻接矩阵
                 *  （2）邻接表
                 *  （3）十字链表
                 *  （4）邻接多重表
             *  2、图的遍历
             *   *  （1）广度优先搜索
                 *  （2）深度优先搜索
             *  3、图的应用
             *   *  （1）单源第一短路径——Dijkstra
                 *  （2）各项点之间第一短路径——Floyd
                 *  （3）第一小生成树——prim
                 *  （4）第一小生成树——kruskal
                 *  （5）头拓扑排序
                 *  （6）关键路径
         *  （七）查找
         *   *  1、线性表的查找
             *   *  （1）顺序查找
                 *  （2）折半查找
             *  2、树表的查找
             *   *  （1）二叉查找树
                 *  （2）平衡二叉查找树
             *  3、散列表的查找
             *   *  （1）散列函数
                 *  （2）处理冲突的方法
                 *  （3）散列查找及性能分析
         *  （八）排序
         *   *  1、插入排序
             *   *  （1）直接插入排序
                 *  （2）希尔排序
             *  2、交换排序
             *   *  （1）冒泡排序
                 *  （2）快速排序
             *  3、选择排序
             *   *  （1）简单选择排序
                 *  （2）堆排序
             *  4、合并排序
             *  5、分配排序
             *   *  （1）桶排序
                 *  （2）基数排序
         *  （九）高级数据结构
         *   *  1、并查集
             *  2、优先队列
             *   *  （1）出队
                 *  （2）入队
             *  3、B-树
             *   *  （1）树高与性能
                 *  （2）查找
                 *  （3）插入
                 *  （4）删除
             *  4、B+树
             *  5、B\*树
             *  6、红黑树
             *   *  （1）红黑树的定义
                 *  （2）树高与性能
                 *  （3）红黑树与4阶B树
                 *  （4）查找
                 *  （5）插入
                 *  （6）删除

![请添加图片描述][46890bfaa39d4d499794210a9b0d6bee.png]

> # 趣学数据结构 #
> 
> ## 一、数据结构入门 ##
> 
> ### （一）数据结构的基础知识 ###
> 
> #### 1、基本概念 ####
> 
> ##### （1）数据 #####
> 
> ##### （2）数据元素 #####
> 
> ##### （3）数据项 #####
> 
> ##### （4）数据对象 #####
> 
> ##### （5）数据结构 #####
> 
> #### 2、逻辑结构 ####
> 
> ##### （1）集合 #####
> 
> ##### （2）线性结构 #####
> 
> ##### （3）树形结构 #####
> 
> ##### （4）图形结构 #####
> 
> #### 3、存储结构 ####
> 
> ##### （1）顺序存储 #####
> 
> ##### （2）链式存储 #####
> 
> ##### （3）散列存储 #####
> 
> ##### （4）索引存储 #####
> 
> ### （二）算法复杂度 ###
> 
> ### （三）一盘棋麦子 ###
> 
> ### （四）神奇的魔鬼序列 ###
> 
>   
> 
> 
> ## 二、数据结构的分类 ##
> 
> ### （一）线性表 ###
> 
> #### 1、线性表的分类 ####
> 
> ##### （1）顺序表 #####
> 
> ###### ① 静态分配 ######
> 
> ###### ② 动态分配 ######
> 
> ###### ③ 顺序表的基本操作 ######
> 
> ##### （2）单链表 #####
> 
> ###### ① 单链表的存储方式 ######
> 
> ###### ② 单链表的基本操作 ######
> 
> ##### （3）双向链表 #####
> 
> ###### ① 双向链表的基本操作 ######
> 
> ###### ② 双向链表的存储方式 ######
> 
> ##### （4）循环链表 #####
> 
> #### 2、线性表的应用 ####
> 
> ##### （1）合并有序顺序表 #####
> 
> ##### （2）合并顺序链表 #####
> 
> ##### （3）就地逆置单链表 #####
> 
> ##### （4）查找链表的中间节点 #####
> 
> ##### （5）删除链表的重复元素 #####
> 
> ### （二）栈和队列 ###
> 
> #### 1、栈的分类 ####
> 
> ##### （1）顺序栈 #####
> 
> ##### （2）链栈 #####
> 
> #### 2、队列的分类 ####
> 
> ##### （1）顺序队列 #####
> 
> ###### ① 顺序队列的定义 ######
> 
> ###### ② 循环队列的定义 ######
> 
> ###### ③ 循环队列的基本操作 ######
> 
> ##### （2）链队列 #####
> 
> #### 3、栈和队列的应用 ####
> 
> ##### （1）数制的转换 #####
> 
> ##### （2）回文判定 #####
> 
> ##### （3）双端队列 #####
> 
> ### （三）字符串 ###
> 
> #### 1、字符串 ####
> 
> #### 2、字符串相关的算法 ####
> 
> ##### （1）模式匹配BF算法 #####
> 
> ##### （2）模式匹配KMP算法 #####
> 
> ##### （3）改进的KMP算法 #####
> 
> #### 3、字符串的应用——病毒检测 ####
> 
> ### （四）数组和广义表 ###
> 
> #### 1、数组的顺序存储 ####
> 
> #### 2、特殊矩阵的压缩存储 ####
> 
> ##### （1）对称矩阵 #####
> 
> ##### （2）三角矩阵 #####
> 
> ##### （3）对角矩阵 #####
> 
> ##### （4）稀疏矩阵 #####
> 
> #### 3、广义表 ####
> 
> #### 4、好玩贪吃蛇——数字矩阵 ####
> 
> ### （五）树 ###
> 
> #### 1、树 ####
> 
> ##### （1）树的定义 #####
> 
> ##### （2）树的存储结构 #####
> 
> ##### （3）树、森林与二叉树的转换 #####
> 
> #### 2、二叉树 ####
> 
> ##### （1）二叉树的性质 #####
> 
> ##### （2）二叉树的存储结构 #####
> 
> ##### （3）二叉树的创建 #####
> 
> ##### （4）二叉树的遍历 #####
> 
> ###### ① 先序遍历 ######
> 
> ###### ② 中序遍历 ######
> 
> ###### ③ 后序遍历 ######
> 
> ###### ④ 层次遍历 ######
> 
> #### 3、线索二叉树 ####
> 
> ##### （1）线索二叉树的存储结构 #####
> 
> ##### （2）线索二叉树的构造 #####
> 
> ##### （3）线索二叉树的遍历 #####
> 
> #### 4、树和森林的遍历 ####
> 
> ##### （1）树的遍历 #####
> 
> ##### （2）森林的遍历 #####
> 
> #### 5、树的应用 ####
> 
> ##### （1）二叉树的深度 #####
> 
> ##### （2）二叉树的叶子树 #####
> 
> ##### （3）三元组创建二叉树 #####
> 
> ##### （4）遍历序列还原树 #####
> 
> ##### （5）哈夫曼树 #####
> 
> ### （六）图 ###
> 
> #### 1、图的存储结构 ####
> 
> ##### （1）邻接矩阵 #####
> 
> ##### （2）邻接表 #####
> 
> ##### （3）十字链表 #####
> 
> ##### （4）邻接多重表 #####
> 
> #### 2、图的遍历 ####
> 
> ##### （1）广度优先搜索 #####
> 
> ##### （2）深度优先搜索 #####
> 
> #### 3、图的应用 ####
> 
> ##### （1）单源第一短路径——Dijkstra #####
> 
> ##### （2）各项点之间第一短路径——Floyd #####
> 
> ##### （3）第一小生成树——prim #####
> 
> ##### （4）第一小生成树——kruskal #####
> 
> ##### （5）头拓扑排序 #####
> 
> ##### （6）关键路径 #####
> 
> ### （七）查找 ###
> 
> #### 1、线性表的查找 ####
> 
> ##### （1）顺序查找 #####
> 
> ##### （2）折半查找 #####
> 
> #### 2、树表的查找 ####
> 
> ##### （1）二叉查找树 #####
> 
> ##### （2）平衡二叉查找树 #####
> 
> #### 3、散列表的查找 ####
> 
> ##### （1）散列函数 #####
> 
> ##### （2）处理冲突的方法 #####
> 
> ##### （3）散列查找及性能分析 #####
> 
> ### （八）排序 ###
> 
> #### 1、插入排序 ####
> 
> ##### （1）直接插入排序 #####
> 
> ##### （2）希尔排序 #####
> 
> #### 2、交换排序 ####
> 
> ##### （1）冒泡排序 #####
> 
> ##### （2）快速排序 #####
> 
> #### 3、选择排序 ####
> 
> ##### （1）简单选择排序 #####
> 
> ##### （2）堆排序 #####
> 
> #### 4、合并排序 ####
> 
> #### 5、分配排序 ####
> 
> ##### （1）桶排序 #####
> 
> ##### （2）基数排序 #####
> 
> ### （九）高级数据结构 ###
> 
> #### 1、并查集 ####
> 
> #### 2、优先队列 ####
> 
> ##### （1）出队 #####
> 
> ##### （2）入队 #####
> 
> #### 3、B-树 ####
> 
> ##### （1）树高与性能 #####
> 
> ##### （2）查找 #####
> 
> ##### （3）插入 #####
> 
> ##### （4）删除 #####
> 
> #### 4、B+树 ####
> 
> #### 5、B\*树 ####
> 
> #### 6、红黑树 ####
> 
> ##### （1）红黑树的定义 #####
> 
> ##### （2）树高与性能 #####
> 
> ##### （3）红黑树与4阶B树 #####
> 
> ##### （4）查找 #####
> 
> ##### （5）插入 #####
> 
> ##### （6）删除 #####

[46890bfaa39d4d499794210a9b0d6bee.png]: https://img-blog.csdnimg.cn/46890bfaa39d4d499794210a9b0d6bee.png