出版者的话前言第1章引论11.1本书讨论的内容11.2数学知识复习21.2.1指数21.2.2对数21.2.3级数21.2.4模运算41.2.5证明的方法41.3递归简论51.4实现泛型构件pre-Java 571.4.1使用Object表示泛型81.4.2基本类型的包装91.4.3使用接口类型表示泛型91.4.4数组类型的兼容性101.5利用Java 5泛型特性实现泛型构件111.5.1简单的泛型类和接口111.5.2自动装箱/拆箱111.5.3菱形运算符121.5.4带有限制的通配符121.5.5泛型static方法141.5.6类型限界141.5.7类型擦除151.5.8对于泛型的限制151.6函数对象16小结18练习18参考文献19第2章算法分析202.1数学基础202.2模型222.3要分析的问题222.4运行时间计算242.4.1一个简单的例子242.4.2一般法则242.4.3较大子序列和问题的求解262.4.4运行时间中的对数312.4.5分析结果的性33小结33练习34参考文献37第3章表、栈和队列393.1抽象数据类型393.2表ADT393.2.1表的简单数组实现403.2.2简单链表403.3Java Collections API中的表413.3.1Collection接口413.3.2Iterator接口423.3.3List接口、ArrayList类和LinkedList类433.3.4例子：remove方法对LinkedList类的使用443.3.5关于ListIterator接口463.4ArrayList类的实现463.4.1基本类463.4.2迭代器、Java嵌套类和内部类493.5LinkedList类的实现523.6栈ADT583.6.1栈模型583.6.2栈的实现593.6.3应用593.7队列ADT653.7.1队列模型653.7.2队列的数组实现653.7.3队列的应用66小结67练习67第4章树714.1预备知识714.1.1树的实现724.1.2树的遍历及应用724.2二叉树754.2.1实现764.2.2例子：表达式树764.3查找树ADT——二叉查找树784.3.1contains方法794.3.2findMin方法和findMax方法804.3.3insert方法804.3.4remove方法824.3.5平均情况分析834.4AVL树864.4.1单旋转874.4.2双旋转894.5伸展树944.5.1一个简单的想法(不能直接使用)954.5.2展开964.6再探树的遍历1004.7B树1014.8标准库中的集合与映射1054.8.1关于Set接口1054.8.2关于Map接口1054.8.3TreeSet类和TreeMap类的实现1064.8.4使用多个映射的实例106小结111练习111参考文献115第5章散列1175.1一般想法1175.2散列函数1175.3分离链接法1195.4不用链表的散列表1235.4.1线性探测法1235.4.2平方探测法1245.4.3双散列1295.5再散列1305.6标准库中的散列表1325.7最坏情形下O(1)访问的散列表 1335.7.1散列1335.7.2布谷鸟散列1355.7.3跳房子散列1435.8通用散列法1465.9可扩散列148小结149练习150参考文献153第6章优先队列(堆)1566.1模型1566.2一些简单的实现1566.3二叉堆1576.3.1结构性质1576.3.2堆序性质1576.3.3基本的堆操作1586.3.4其他的堆操作1626.4优先队列的应用1646.4.1选择问题1646.4.2事件模拟1656.5d-堆1666.6左式堆1676.6.1左式堆性质1676.6.2左式堆操作1686.7斜堆1726.8二项队列1736.8.1二项队列结构1746.8.2二项队列操作1746.8.3二项队列的实现1766.9标准库中的优先队列180小结180练习181参考文献184第7章排序1867.1预备知识1867.2插入排序1867.2.1算法1867.2.2插入排序的分析1877.3一些简单排序算法的下界1877.4希尔排序1887.5堆排序1917.6归并排序1937.7快速排序1987.7.1选取枢纽元1997.7.2分割策略2007.7.3小数组2027.7.4实际的快速排序例程2027.7.5快速排序的分析2037.7.6选择问题的线性期望时间算法2067.8排序算法的一般下界2077.9选择问题的决策树下界2097.10对手下界2107.11线性时间的排序：桶排序和基数排序2127.12外部排序2167.12.1为什么需要一些新的算法2177.12.2外部排序模型2177.12.3简单算法2177.12.4多路合并2187.12.5多相合并2197.12.6替换选择219小结220练习221参考文献225第8章不相交集类2278.1等价关系2278.2动态等价性问题2278.3基本数据结构2298.4灵巧求并算法2318.5路径压缩2338.6路径压缩和按秩求并的最坏情形2348.6.1缓慢增长的函数2358.6.2利用递归分解的分析2358.6.3O(M logN)界2408.6.4O(Mα(M,N))界2408.7一个应用241小结243练习243参考文献244第9章图论算法2469.1若干定义2469.2拓扑排序2489.3最短路径算法2509.3.1无权最短路径2519.3.2Dijkstra算法2549.3.3具有负边值的图2589.3.4无圈图2599.3.5所有点对最短路径2619.3.6最短路径的例子2619.4网络流问题2629.5最小生成树2679.5.1Prim算法2679.5.2Kruskal算法2699.6深度优先搜索的应用2709.6.1无向图2709.6.2双连通性2719.6.3欧拉回路2739.6.4有向图2759.6.5查找强分支2769.7NP-性介绍2779.7.1难与易2789.7.2NP类2789.7.3NP-问题279小结280练习280参考文献284第10章算法设计技巧28810.1贪婪算法28810.1.1一个简单的调度问题28810.1.2哈夫曼编码29010.1.3近似装箱问题29310.2分治算法29810.2.1分治算法的运行时间29810.2.2最近点问题30010.2.3选择问题30210.2.4一些算术问题的理论改进30410.3动态规划30710.3.1用一个表代替递归30710.3.2矩阵乘法的顺序安排30910.3.3二叉查找树31110.3.4所有点对最短路径31210.4随机化算法31410.4.1随机数发生器31510.4.2跳跃表31910.4.3素性测试32010.5回溯算法32210.5.1收费公路重建问题32310.5.2博弈326小结331练习331参考文献336第11章摊还分析34011.1一个无关的智力问题34011.2二项队列34011.3斜堆34411.4斐波那契堆34511.4.1切除左式堆中的节点34611.4.2二项队列的懒惰合并34711.4.3斐波那契堆操作34911.4.4时间界的证明35011.5伸展树351小结354练习354参考文献355第12章高级数据结构及其实现35612.1自顶向下伸展树35612.2红黑树36212.2.1自底向上的插入36212.2.2自顶向下红黑树36312.2.3自顶向下的删除36712.3treap树36812.4后缀数组与后缀树37012.4.1后缀数组37112.4.2后缀树37312.4.3线性时间的后缀数组和后缀树的构建37512.5k-d树38512.6配对堆387小结392练习393参考文献396索引399