计算机系列教材数据结构与算法(第2版)/汪沁

目录 第1章绪论 1 1.1数据结构的概念 2 1.1.1引言 2 1.1.2数据结构的有关概念与术语 5 1.2抽象数据类型 7 1.3算法描述与分析 11 1.3.1什么是算法 11 1.3.2算法分析技术初步 13 1.4基本的算法策略 17 1.4.1穷举法 17 1.4.2递推法与迭代法 18 1.4.3分治法 20 1.4.4贪心算法 22 1.4.5动态规划 22 1.5案例分析 25 1.6小结 26 讨论小课堂1 27 习题1 28第2章线性表 30 2.1线性表的定义及其运算 30 2.1.1线性表的定义 30 2.1.2线性表的抽象数据类型 31 2.2线性表的顺序存储结构及实现 32 2.2.1顺序存储结构 32 2.2.2线性表在向量中基本运算的实现 34 2.3线性表的链表存储结构 39 2.3.1单链表 39 2.3.2线性链表基本运算的实现 42 2.4循环链表和双向链表 49 2.4.1循环链表 49 2.4.2双向链表 50 2.4.3顺序存储结构与链表存储结构的综合分析与比较 51 2.5单链表的应用 52 2.5.1多项式相加的链表存储结点 52 2.5.2多项式相加的算法实现 53 2.6小结 54 讨论小课堂2 55 习题2 55第3章栈和队列 57 3.1栈 57 3.1.1栈的定义 57 3.1.2栈的抽象数据类型 58 3.2栈的顺序存储结构及实现 59 3.2.1栈的顺序存储结构 59 3.2.2顺序栈的定义 60 3.3栈的链表存储结构及实现 62 3.4栈的应用 65 3.4.1表达式的计算 65 3.4.2子程序的嵌套调用 67 3.4.3递归调用 68 3.5队列 69 3.5.1队列的定义及运算 69 3.5.2队列的抽象数据类型 70 3.6队列的顺序存储结构及实现 70 3.7队列的链表存储结构及实现 74 3.8队列的应用 77 3.9算法实例——Hanoi塔问题 78 3.10小结 79 讨论小课堂3 80 习题3 81第4章串 83 4.1串的基本概念 83 4.1.1串的定义 83 4.1.2串的抽象数据类型 84 4.2串的存储与基本操作的实现 85 4.2.1定长顺序串 86 4.2.2堆串 86 4.2.3块链串 87 4.2.4串操作的实现 88 4.3串的模式匹配 91 4.3.1朴素模式匹配算法 92 4.3.2模式匹配的KMP算法 92 4.4串的应用举例： 文本编辑 97 4.5小结 99 讨论小课堂4 99 习题4 100第5章数组和广义表 101 5.1数组 102 5.1.1数组的基本概念 102 5.1.2二维数组 102 5.1.3数组的顺序存储方式 103 5.2矩阵的压缩存储 104 5.2.1特殊矩阵 104 5.2.2稀疏矩阵 107 5.3广义表 112 5.3.1广义表的定义 112 5.3.2广义表的存储结构 113 5.4案例分析 116 5.4.1概述和方法 116 5.4.2算法和程序 118 5.5小结 120 讨论小课堂5 120 习题5 120第6章树与二叉树 122 6.1树的概念及术语 123 6.1.1树的定义 123 6.1.2树的抽象数据类型 124 6.1.3树的表示方式 125 6.2二叉树 125 6.2.1二叉树的定义 125 6.2.2二叉树的抽象数据类型 126 6.2.3二叉树的重要性质 127 6.2.4二叉树的存储结构 128 6.3二叉树的遍历 130 6.3.1先序遍历 131 6.3.2中序遍历 131 6.3.3后根遍历 132 6.3.4按层遍历 133 6.3.5非递归遍历算法 133 6.3.6二叉树的建立 136 6.3.7二叉树遍历的应用举例 137 6.4二叉树与树、森林的转换 139 6.4.1树与二叉树的转换 139 6.4.2森林与二叉树的转换 140 6.5树的存储结构 141 6.5.1树的双亲表示法 142 6.5.2孩子表示法 142 6.5.3孩子兄弟表示法 143 6.6树的遍历 144 6.6.1一般树的遍历 144 6.6.2森林的遍历 145 6.7二叉树的应用 146 6.7.1哈夫曼树 146 6.7.2哈夫曼树的构造 146 6.7.3哈夫曼树的实现算法 148 6.7.4哈夫曼编码 149 6.8小结 150 讨论小课堂6 150 习题6 150第7章图 153 7.1图的基本概念 153 7.1.1图的定义 153 7.1.2图的术语 155 7.1.3图的抽象数据类型 156 7.2图的存储结构 157 7.2.1图的邻接矩阵 157 7.2.2邻接矩阵表示法的描述 159 7.2.3邻接矩阵表示下的基本操作的实现 160 7.2.4图的邻接链表 161 7.2.5图的邻接表表示法的描述 162 7.2.6邻接表表示下基本操作的实现 163 7.3图的遍历与图的连通性 165 7.3.1图的深度优先遍历 166 7.3.2图的广度优先遍历 168 7.3.3非连通图和连通分量 170 7.4图的*小生成树 170 7.4.1*小生成树的基本概念 170 7.4.2普里姆(Prim)算法 171 7.4.3克鲁斯卡尔（Kruskal）算法 174 7.5*短路径 175 7.5.1从某顶点到其余各顶点的*短路径 175 7.5.2每对顶点之间的*短路径 178 7.6拓扑排序与关键路径 180 7.6.1拓扑排序 180 7.6.2关键路径 183 7.7图的应用 189 7.7.1图在路由器寻径中的应用 189 7.7.2图在物流信息系统中应用 190 7.8小结 190 讨论题7 191 习题7 191第8章查找 193 8.1查找的基本概念 194 8.2静态查找表 195 8.2.1顺序表的查找 195 8.2.2有序表的折半查找 196 8.2.3索引顺序表查找 200 8.3动态查找表 201 8.3.1二叉排序树 201 8.3.2平衡二叉树 210 8.4案例分析 214 8.4.1直方图问题 214 8.4.2箱子装载问题 216 8.5小结 218 讨论小课堂8 218 习题8 219第9章排序 220 9.1排序的基本概念 220 9.2插入排序 221 9.2.1直接插入排序 221 9.2.2折半插入排序 222 9.2.3希尔排序 222 9.3交换排序 224 9.3.1冒泡排序 224 9.3.2快速排序 225 9.4选择排序 229 9.4.1简单选择排序 229 9.4.2堆排序 230 9.5归并排序 233 9.6基数排序 235 9.7小结 239 讨论小课堂9 240 习题9 240第10章索引结构与哈希 242 10.1静态索引结构 242 10.1.1索引表 242 10.1.2索引表查找 242 10.2动态索引结构（B-树和B 树） 245 10.2.1B-树的定义 245 10.2.2B-树的运算 246 10.2.3B 树 249 10.3键树及Trie树 250 10.3.1键树的定义 250 10.3.2双链树 251 10.3.3Trie树 252 10.4哈希表及其查找 253 10.4.1哈希表与哈希函数 253 10.4.2构造哈希函数的常用方法 254 10.4.3解决冲突的主要方法 256 10.4.4哈希查找的性能分析 260 10.5小结 261 讨论小课堂10 262 习题10 262参考文献 265