数据结构与算法分析 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

马克·艾伦·维斯（Mark Allen Weiss）佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Robert Sedgewick。 他曾经担任全美AP（Advanced Placement）考试计算机学科委员会的主席（2000-2004）。他的主要研究兴趣是数据结构、算法和教育学。他编写的关于数据结构与算法方面的教材还有《Data Structures and Algorithm Analysis : in Java》《Data Structures and Algorithm Analysis : in C++》《Data Structures and Problem Solving : Using Java》《Data Structures and Problem Solving : Using C++》。

暂无其它内容！

• 优点是习题、算法分析，数据结构讲解不够全面，算法部分是鸡肋，所以仅单本书严重不适合计专业学生完成数据结构或算法任一课程，需配合其它全面数据结构或算法教材，推荐 sedgewick 《算法》c/c++版

  来源：豆瓣 发布时间：2025-05-19 21:25:27

• 数据结构和算法分析的经典教材

  来源：豆瓣 发布时间：2025-05-19 21:25:27