数据结构 C语言 微课版——从概念到算法

目录 第 1章 绪论 1 1.1 程序设计的问题背景 1 1.2 程序设计的一般过程 2 1.3 数据结构概述 3 1.4 数据结构基本概念 6 1.5 算法设计的一般步骤 9 1.5.1 算法定义及性质 9 1.5.2 算法设计步骤 12 1.6 算法复杂度分析 12 1.6.1 算法时间复杂度分析 12 1.6.2 算法空间复杂度分析 15 1.7 算法分析实例 17 1.8 本章小结 22 计算机领域名人堂 23 本章习题 23 第 2章 线性表 27 2.1 线性表的基本概念 27 2.1.1 线性表定义 28 2.2.2 抽象数据类型定义 29 2.2 线性表顺序存储结构定义及实现 32 2.2.1 顺序表存储结构定义 32 2.2.2 顺序表的基本操作实现 35 2.3 线性表链式存储结构定义及实现 39 2.3.1 单链表存储结构定义 40 2.3.2 单链表的实现 40 2.3.3 循环单链表 44 2.3.4 双向链表 46 2.4 顺序表与链表的比较 48 2.5 线性表应用实例 49 2.5.1 递增有序单链表生成算法 49 2.5.2 单链表插入删除算法 53 2.5.3 单链表合并算法 55 2.5.4 单链表的逆置 57 2.6 本章小结 60 计算机领域名人堂 61 本章习题 62 第3章 栈与队列 66 3.1 栈 67 3.1.1 栈的基本概念 67 3.1.2 栈的抽象数据类型 68 3.1.3 栈的操作特性 68 3.1.4 栈的顺序存储结构 70 3.1.5 栈的链式存储结构 76 3.1.6 栈的应用 78 3.2 队列 86 3.2.1 队列的基本概念 87 3.2.2 队列的抽象数据类型 87 3.2.3 链式队列的基本运算及实现 88 3.2.4 顺序队列的基本运算及实现 91 3.3 应用实例 96 3.3.1 栈的应用实例 96 3.3.2 队列的应用实例 99 3.4 本章小结 102 计算机领域名人堂 103 本章习题 103 第4章 字符串、多维数组与广义表 108 4.1 字符串 108 4.1.1 字符串的定义 109 4.1.2 字符串的存储结构及其基本运算的实现 111 4.1.3 字符串的模式匹配算法 116 4.2 多维数组 122 4.2.1 多维数组概念的引入 122 4.2.2 多维数组的顺序存储 124 4.2.3 矩阵的压缩存储 128 4.3 广义表 137 4.3.1 广义表的定义 137 4.3.2 广义表的存储 139 4.4 应用实例 143 4.4.1*大匹配分词算法 143 4.4.2正数值三角形的*优路径 147 4.5 本章小结 149 计算机领域名人堂 149 本章习题 150 第5章 树与二叉树 153 5.1 实际应用中的树 153 5.2树的逻辑结构 155 5.2.1 树的定义与基本术语 155 5.2.2 树的抽象数据类型定义 157 5.3 树的存储结构 158 5.3.1 双亲表示法 159 5.3.2 孩子表示法 159 5.3.3 孩子兄弟表示法 161 5.4 二叉树的逻辑结构 162 5.4.1 二叉树的定义 163 5.4.2 二叉树的性质 163 5.4.3 二叉树的操作与抽象数据类型定义 166 5.5 二叉树的存储结构 168 5.5.1 二叉树的顺序存储结构 168 5.5.2 二叉树的链式存储结构 169 5.5.3 基于二叉链表的二叉树遍历 170 5.5.4 线索链表与线索二叉树 179 5.6 树、森林与二叉树的转换 185 5.6.1 树与二叉树的转换 185 5.6.2 森林与二叉树的转换 186 5.6.3 树与森林的遍历 187 5.7 哈夫曼树 189 5.7.1 哈夫曼树与哈夫曼算法 189 5.7.2 哈夫曼编码 192 5.8 应用实例：表达式二叉树 193 5.8.1 表达式二叉树的概念 194 5.8.2 表达式二叉树的实现 194 5.9本章小结 197 计算机领域名人堂 197 本章习题 198 第6章 图 203 6.1 实际应用中的图 203 6.2 图的基本概念 204 6.2.1 图的定义和基本术语 204 6.2.2 图的操作定义 207 6.3 图的存储结构 208 6.3.1 邻接矩阵 208 6.3.2 邻接表 211 6.3.3 十字链表 213 6.3.4 邻接多重表 214 6.4 图的遍历 215 6.4.1 图的深度优先搜索遍历 215 6.4.2 图的广度优先搜索遍历 217 6.4.3 图的连通性 218 6.5 图的生成树问题 219 6.5.1 生成树与*小生成树 219 6.5.2 *小生成树Prim算法 220 6.5.3 *小生成树Kruskal算法 223 6.6 图的*短路径问题 226 6.6.1 单源*短路径Dijkstra算法 226 6.6.2 各顶点间*短路径Floyd算法 230 6.7 有向无环图的应用 233 6.7.1 拓扑排序 233 6.7.2 关键路径 236 6.8 应用实例 241 6.8.1 并查集 241 6.8.2 地铁换乘问题 245 6.9 本章小结 258 计算机领域名人堂 258 本章习题 259 第7章 排序 263 7.1 实际应用中的排序 263 7.2 排序的概述 264 7.2.1 排序算法的稳定性 265 7.2.2 排序算法的分类 266 7.2.3 排序算法的性能 266 7.3 插入排序 266 7.3.1 直接插入排序 266 7.3.2 折半插入排序 269 7.3.3 希尔排序 271 7.4 交换排序 274 7.4.1 冒泡排序 274 7.4.2 快速排序 277 7.5 选择排序 281 7.5.1 简单选择排序 281 7.5.2 树形选择排序 284 7.6 归并排序 291 7.7 分配排序 295 7.7.1 桶排序 295 7.7.2 基数排序 296 7.8 各种排序技术比较 299 7.9 本章小结 300 计算机领域名人堂 301 本章习题 302 第8章 查找 308 8.1 查找概述 308 8.1.1 查找基本概念 308 8.1.2 查找操作性能分析 309 8.2 线性表的查找技术 309 8.2.1 顺序查找 309 8.2.2 折半查找 312 8.2.3 索引查找 315 8.3 树表的查找技术 316 8.3.1 二叉排序树 316 8.3.2 平衡二叉树 325 8.3.3 红黑树 331 8.3.4 B树 346 8.4 散列表的查找技术 350 8.4.1 散列表概述 350 8.4.2 散列函数设计 351 8.4.3 处理冲突的方法 352 8.4.4 散列查找性能分析 355 8.5 本章小结 357 计算机领域名人堂 358 本章习题 359 第9章 大数据存储与检索 364 9.1 大数据的定义与特征 364 9.1.1 大数据定义 365 9.1.2 大数据特征 365 9.1.3 大数据的行业发展趋势 367 9.2 大数据存储 367 9.2.1 数据存储管理 368 9.2.2 分布式文件系统 368 9.2.3 NoSQL数据库 371 9.2.4 HBase数据库 372 9.3 大数据检索 375 9.3.1 大数据索引 375 9.3.2 大数据高效检索 377 9.4 应用实例 378 9.5 本章小结 382 计算机领域名人堂 383 本章习题 383