数据结构基础(C语言版)(第2版)

第1章 基本概念1.1 概观：系统生命周期1.2 指针和动态存储分配1.2.1 指针1.2.2 动态存储分配1.2.3 指针隐患1.3 算法形式规范1.3.1 综论1.3.2 递归算法1.4 数据抽象1.5 性能分析1.5.1 空间复杂度1.5.2 时间复杂度1.5.3 渐近记号(O，Q，)1.5.4 实际复杂度1.6 性能度量1.6.1 定时1.6.2 生成测试数据1.7 参考文献和选读材料第2章 数组和结构2.1 数组2.1.1 数组的抽象数据类型2.1.2 c语言的数组2.2 数组的动态存储分配2.2.1 一维数组2.2.2 二维数组2.3 结构体和联合体2.3.1 结构体2.3.2 联合体2.3.3 结构的内部实现2.3.4 自引用结构2.4 多项式2.4.1 多项式的抽象数据类型2.4.2 多项式的表示2.4.3 多项式加法2.5 稀疏矩阵2.5.1 稀疏矩阵的抽象数据类型2.5.2 稀疏矩阵的表示2.5.3 矩阵转置2.5.4 矩阵相乘2.6 多维数组的表示2.7 字符串2.7.1 字符串的抽象数据类型2.7.2 C语言的字符串2.7.3 模式匹配2.8 参考文献和选读材料2.9 补充习题第3章 栈与队列3.1 栈3.2 动态栈3.3 队列3.4 动态循环队列3.5 迷宫问题3.6 表达式求值3.6.1 表达式3.6.2 后缀表达式求值3.6.3 中缀表达式转换成后缀表达式3.7 多重栈与多重队列3.8 补充习题第4章 链表4.1 单向链表4.2 用C语言表示单向链表4.3 链式栈与链式队列4.4 多项式4.4.1 多项式表示4.4.2 多项式加法4.4.3 销毁多项式4.4.4 循环链表与多项式4.4.5 小结4.5 其它链表操作4.5.1 单向链表操作4.5.2 循环链表操作4.6 等价类4.7 稀疏矩阵4.7.1 稀疏矩阵表示4.7.2 输入稀疏矩阵4.7.3 输出稀疏矩阵4.7.4 销毁稀疏矩阵4.8 双向链表第5章 树5.1 引论5.1.1 术语5.1.2 树的表示5.2 二叉树5.2.1 二叉树的抽象数据类型5.2.2 二叉树的性质5.2.3 二叉树的表示5.3 遍历二叉树5.3.1 中序遍历5.3.2 先序遍历5.3.3 后序遍历5.3.4 非递归(循环)中序遍历5.3.5 层序遍历5.3.6 不设栈遍历二叉树5.4 其它二叉树操作5.4.1 复制二叉树5.4.2 判断两个二叉树全等5.4.3 可满足性问题5.5 线索二叉树5.5.1 线索5.5.2 中序遍历线索二叉树5.5.3 线索二叉树插入结点5.6 堆5.6.1 优先级队列5.6.2 大根堆定义5.6.3 大根堆插入操作5.6.4 大根堆删除操作5.7 二叉查找树5.7.1 定义5.7.2 二叉查找树的查找5.7.3 二叉查找树的插入5.7.4 二叉查找树的删除5.7.5 二叉查找树的合并与分裂5.7.6 二叉查找树的高度5.8 选拔树5.8.1 引子5.8.2 优胜树5.8.3 淘汰树5.9 森林5.9.1 森林转换为二叉树5.9.2 遍历森林5.10 不相交集合的表示5.10.1 引子5.10.2 合并与查找操作5.10.3 划分等价类5.11 二叉树的计数5.11.1 不同态二叉树5.11.2 栈置换5.11.3 矩阵乘法5.11.4 不同二叉树的数目5.12 参考文献和选读材料第6章 图6.1 图的抽象数据类型6.1.1 引子6.1.2 图的定义和术语6.1.3 图的表示6.2 图的基本操作6.2.1 深度优先搜索6.2.2 广度优先搜索6.2.3 连通分量6.2.4 生成树6.2.5 重连通分量6.3 *小代价生成树6.3.1 Kruskal算法6.3.2 Prim算法6.3.3 SoUin算法6.4 *短路径和迁移闭包6.4.1 单源点至所有其它节点：边权值非负6.4.2 单源点至所有其它节点：边权值正负无限制