数据结构与算法分析 C语言描述 原书第2版

本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有*高效率的程序。 本书可作为高级数据结构课程或研究生一年级算法分析课程的教材,使用本书需具有一些中级程序设计知识,还需要离散数学的一些背景知识。

译者序  
前言  
第1章　引论┊1  
1.1　本书讨论的内容┊2  
1.2　数学知识复习┊3  
1.2.1　指数┊3  
1.2.2　对数┊3  
1.2.3　级数┊4  
1.2.4　模运算┊5  
1.2.5　证明方法┊5  
1.3　递归简论┊7  
总结┊10  
练习┊10  
参考文献┊11  
第2章　算法分析┊13  
2.1　数学基础┊14  
2.2　模型┊16  
2.3　要分析的问题┊16  
2.4　运行时间计算┊18  
2.4.1　一个简单的例子┊18  
2.4.2　一般法则┊19  
2.4.3　最大子序列和┊20  
2.4.4　运行时间中的对数┊24  
2.4.5　检验你的分析┊27  
2.4.6　分析结果的准确性┊28  
总结┊28  
练习┊29  
参考文献┊32  
第3章　表、栈和队列┊35  
3.1　抽象数据类型┊36  
3.2　表ADT┊36  
3.2.1　表的简单数组实现┊37  
3.2.2　链表┊37  
3.2.3　程序设计细节┊38  
3.2.4　常见的错误┊42  
3.2.5　双链表┊43  
3.2.6　循环链表┊43  
3.2.7　例子┊43  
3.2.8　链表的游标实现┊47  
3.3　栈ADT┊50  
3.3.1　栈模型┊50  
3.3.2　栈的实现┊51  
3.3.3　应用┊56  
3.4　队列ADT┊62  
3.4.1　队列模型┊62  
3.4.2　队列的数组实现┊62  
3.4.3　队列的应用┊65  
总结┊66  
练习┊66  
第4章　树┊71  
4.1　预备知识┊72  
4.1.1　树的实现┊73  
4.1.2　树的遍历及应用┊74  
4.2　二叉树┊76  
4.2.1　实现┊77  
4.2.2　表达式树┊77  
4.3　查找树ADT——二叉查找树┊80  
4.3.1　MakeEmpty┊80  
4.3.2　Find┊81  
4.3.3　FindMin和FindMax┊81  
4.3.4　Insert┊81  
4.3.5　Delete┊83  
4.3.6　平均情形分析┊84  
4.4　AVL树┊86  
4.4.1　单旋转┊88  
4.4.2　双旋转┊90  
4.5　伸展树┊95  
4.5.1　一个简单的想法┊96  
4.5.2　展开┊97  
4.6　树的遍历┊102  
4.7　B树┊103  
总结┊107  
练习┊108  
参考文献┊113  
第5章　散列┊117  
5.1　一般想法┊118  
5.2　散列函数┊118  
5.3　分离链接法┊120  
5.4　开放定址法┊123  
5.4.1　线性探测法┊124  
5.4.2　平方探测法┊125  
5.4.3　双散列┊129  
5.5　再散列┊130  
5.6　可扩散列┊132  
总结┊133  
练习┊134  
参考文献┊137  
第6章　优先队列（堆）┊139  
6.1　模型┊140  
6.2　一些简单的实现┊141  
6.3　二叉堆┊141  
6.3.1　结构性质┊141  
6.3.2　堆序性质┊142  
6.3.3　基本的堆操作┊143  
6.3.4　其他的堆操作┊146  
6.4　优先队列的应用┊149  
6.4.1　选择问题┊149  
6.4.2　事件模拟┊150  
6.5　d-堆┊151  
6.6　左式堆┊152  
6.6.1　左式堆的性质┊152  
6.6.2　左式堆的操作┊153  
6.7　斜堆┊158  
6.8　二项队列┊159  
6.8.1　二项队列结构┊159  
6.8.2　二项队列操作┊160  
6.8.3　二项队列的实现┊162  
总结┊165  
练习┊166  
参考文献┊169  
第7章　排序┊173  
7.1　预备知识┊174  
7.2　插入排序┊174  
7.2.1　算法┊174  
7.2.2　插入排序的分析┊175  
7.3　一些简单排序算法的下界┊175  
7.4　希尔排序┊176  
7.5　堆排序┊179  
7.6　归并排序┊182  
7.7　快速排序┊186  
7.7.1　选取枢纽元┊187  
7.7.2　分割策略┊188  
7.7.3　小数组┊190  
7.7.4　实际的快速排序例程┊190  
7.7.5　快速排序的分析┊192  
7.7.6　选择的线性期望时间算法┊194  
7.8　大型结构的排序┊195  
7.9　排序的一般下界┊196  
7.10　桶式排序┊198  
7.11　外部排序┊198  
7.11.1　为什么需要新的算法┊198  
7.11.2　外部排序模型┊199  
7.11.3　简单算法┊199  
7.11.4　多路合并┊200  
7.11.5　多相合并┊201  
7.11.6　替换选择┊202  
总结┊203  
练习┊204  
参考文献┊207  
第8章　不相交集ADT┊209  
8.1　等价关系┊210  
8.2　动态等价性问题┊210  
8.3　基本数据结构┊212  
8.4　灵巧求并算法┊214  
8.5　路径压缩┊216  
8.6　按秩求并和路径压缩的最坏情形┊217  
8.7　一个应用┊221  
总结┊222  
练习┊222  
参考文献┊223  
第9章　图论算法┊225  
9.1　若干定义┊226  
9.2　拓扑排序┊228  
9.3　最短路径算法┊230  
9.3.1　无权最短路径┊232  
9.3.2　Dijkstra算法┊235  
9.3.3　具有负边值的图┊240  
9.3.4　无圈图┊241  
9.3.5　所有点对最短路径┊243  
9.4　网络流问题┊243  
9.5　最小生成树┊247  
9.5.1　Prim算法┊248  
9.5.2　Kruskal算法┊250  
9.6　深度优先搜索的应用┊251  
9.6.1　无向图┊252  
9.6.2　双连通性┊253  
9.6.3　欧拉回路┊256  
9.6.4　有向图┊259  
9.6.5　查找强分支┊260  
9.7　NP-完全性介绍┊262  
9.7.1　难与易┊262  
9.7.2　NP类┊263  
9.7.3　NP-完全问题┊264  
总结┊266  
练习┊266  
参考文献┊270  
第10章　算法设计技巧┊273  
10.1　贪婪算法┊274  
10.1.1　一个简单的调度问题┊274  
10.1.2　Huffman编码┊276  
10.1.3　近似装箱问题┊280  
10.2　分治算法┊286  
10.2.1　分治算法的运行时间┊287  
10.2.2　最近点问题┊289  
10.2.3　选择问题┊291  
10.2.4　一些运算问题的理论改进┊294  
10.3　动态规划┊297  
10.3.1　用一个表代替递归┊298  
10.3.2　矩阵乘法的顺序安排┊300  
10.3.3　最优二叉查找树┊301  
10.3.4　所有点对最短路径┊304  
10.4　随机化算法┊306  
10.4.1　随机数发生器┊307  
10.4.2　跳跃表┊310  
10.4.3　素性测试┊312  
10.5　回溯算法┊314  
10.5.1　收费公路重建问题┊314  
10.5.2　博弈┊318  
总结┊323  
练习┊323  
参考文献┊329  
第11章　摊还分析┊333  
11.1　一个无关的智力问题┊334  
11.2　二项队列┊335  
11.3　斜堆┊339  
11.4　斐波那契堆┊341  
11.4.1　切除左式堆中的节点┊341  
11.4.2　二项队列的懒惰合并┊343  
11.4.3　斐波那契堆操作┊346  
11.4.4　时间界的证明┊346  
11.5　伸展树┊348  
总结┊351  
练习┊351  
参考文献┊353  
第12章　高级数据结构及其实现┊355  
12.1　自顶向下伸展树┊356  
12.2　红黑树┊361  
12.2.1　自底向上插入┊362  
12.2.2　自顶向下红黑树┊363  
12.2.3　自顶向下删除┊367  
12.3　确定性跳跃表┊368  
12.4　AA树┊373  
12.5　treap树┊378  
12.6　k-d树┊379  
12.7　配对堆┊383  
总结┊387  
练习┊387  
参考文献┊389  
索引┊391 显示全部信息