数据结构与算法分析

出版时间：2005-8  出版社：人民邮电出版社  作者：维斯  页数：501  
Tag标签：无  

内容概要

　　《数据结构与算法分析：C语言描述》(英文版第2版)是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了《数据结构与算法分析：C语言描述》(英文版第2版)创新的对算法和数据结构的讲授方法。通过C程序的实现，着重阐述了抽象数据类型（ADT）的概念，并对算法的效率、性能和运行时间进行了分析。《数据结构与算法分析：C语言描述》(英文版第2版)适合作为本科数据结构课程或研究生第一年算法分析课程的教材。第1~9章为大多数本科一学期数据结构课程提供了足够的材料。多学时课程可讲授第10章。研究生的算法分析课程可以使用第6~12章的内容。

作者简介

　　Mark Allen Weiss，美国佛罗里达国际大学计算机学院教授，普林斯顿大学汁算机科学博士，他目前是AP（Advanced Placemenl）考试汁算机学科委员会的主席。除本书外，他还撰写了Data Structures and Problem Solving Using Java（中文版第3版即将山人民邮电出版社出版）等著作。

书籍目录

Adapters ForewordPreface1　Introduction　　11.1.　Whats the Book About?　　11.2.　A Brief Introduction to Recursion　　3Summary7Exercises7References82　Algorithm Analysis　　92.1.　Mathematical Background　　92.2.　Model　　122.3.　What to Analyze　　122.4.　Running Time Calculations　　142.4.1.　A Simple Example　　152.4.2.　General Rules　　152.4.3.　Solutions for the Maximum Subsequence Sum Problem182.4.4.　Logarithms in the Running Time222.4.5.　Checking Your Analysis272.4.6.　A Grain of Salt27Summary28Exercises29References333　Lists, Stacks, and Queues353.1.　Abstract Data Types (ADTs)　　353.2.　The List AnT　　363.2.1.　Simple Array Implementation of Lists　　373.2.2.　Linked Lists　　373.2.3.　Programming Details　　383.2.4.　Common Errors　　433.2.5.　Doubly Linked Lists　　453.2.6.　Circularly Linked Lists　　463.2.7.　Examples　　463.2.8.　Cursor Implementation of Linked Lists　　503.3.　The Stack ADT　　563.3.1.　Stack Model　　563.3.2.　Implementation of Stacks　 573.3.3.　Applications　653.4.　The Queue AnT　　　　　733.4.1.　Queue Model　733.4.2.　Array Implementation of Queues　　733.4.3.　Applications of Queues78Summary　　79Exercises　　794　Trees　　834.1.　Preliminaries　　834.1.1.　Terminology　　　834.1.2.　Tree Traversals with an Application　　844.2.　Binary Trees　　　　　　854.2.1.　Implementation864.2.2.　Expression Trees　　874.2.3.　Tree Traversals904.3.　The Search Tree ADT　Binary Search Trees　　974.3.1. MakeEmpty　 974.3.2. Find　　974.3.3.　FindMin and FindMax　　994.3.4.　Insert　　1004.3.5.　Delete　 1014.3.6.　Average-Case Analysis		1034.4.　AVL Trees　　						1064.4.1.　Single Rotation1084.4.2.　Double Rotation　　1114.5.　Splay Trees　　1194.5.1.　A Simple Idea (That Does Not Work)　　12 04.5.2. Splaying　 12 24.6.　B-Trees　　　　　　128Summary133Exercises134References1415　Priority Queues (Heaps)　　1455.1.　Model　　1455.2.　Simple Implementations　　1465.3.　Binary Heap　　1475.3.1.　Structure Property　1475.3.2.　Heap Order Property1485.3.3.　Basic Heap Operations　　1505.3.4.　Other Heap Operations　　1545.4.　Applications of Priority Queues1575.4.1.　The Selection Problem　　1575.4.2.　Event Simulation　　1595.5.　d-Heaps　　1605.6.　Leftist Heaps　　1615.6.1.　Leftist Heap Property　　1615.6.2.　Leftist Heap Operations　 1625.7.　Skew Heaps　　1685.8.　Binomial Queues　　1705.8.1.　Binomial Queue Structure　　1705.8.2.　Binomial Queue Operations　　1725.8.3.　Implementation of Binomial Queues　　173Summary　　180Exercises　　180References　 1846　Sorting　 1876.1.　Preliminaries　　1876.2.　Insertion Sort　　1886.2.1.　The Algorithm　　1886.2.2.　Analysis of Insertion Sort　　1896.3.　A Lower Bound for Simple Sorting Algorithms　　1896.4.　Shellsort　　1906.4.1.　Worst-Case Analysis of Shellsort　　1926.5.　Heapsort　　1946.5.1.　Analysis of Heapsort　　1966.6.　Mergesort　　1986.6.1.　Analysis of Mergesort　　2006.7.　Quicksort　　2036.7.1.　Picking the Pivot　　2046.7.2.　Partitioning Strategy　 2056.7.3.　Small Arrays　　20 86.7.4.　Actual Quicksort Routines　　2086.7.5. Analysis of Quicksort　 2096.7.6.　A Linear-Expected-Time Algorithm for Selection　　2136.8.　Sorting Large Structures　　2156.9.　A General Lower Bound for Sorting　　2166.9.1.　Decision Trees　　2176.10.　Bucket Sort and Radix Sort　　2196.11.　External Sorting　　2226.11.1.　Why We Need New Algorithms　　2226.11.2.　Model for External Sorting　　2226.11.3.　The Simple Algorithm　　2226.11.4.　Multiway Merge　　2246.11.5.　Polyphase Merge2256.11.6.　Replacement Selection　　226Summary　　227Exercises　　2297　Hashing　　2357.1.　General Idea　　2357.2.　Hash Function　　2377.3.　Separate Chaining　　2397.4.　Open Addressing　　　2447.4.1.　Linear Probing2447.4.2.　Quadratic Probing　2477.4.3.　Double Hashing　　2517.5.　Rehashing　　2527.6.　Extendible Hashing　　255Summary　　258Exercises　　259References　　2628　The Disjoint Set AnT　　2658.1.　Equivalence Relations　　2658.2.　The Dynamic Equivalence Problem　　2668.3.　Basic Data Structure　　2678.4.　Smart Union Algorithms　　2718.5.　Path Compression　　2738.6.　Worst Case for Union-by-Rank and Path Compression　　2758.6.1.　Analysis of the Union/Find Algorithm　　2758.7.　An Application　　281Summary　　281Exercises　　282References　　2839　Graph Algorithms　　2859.1.　Definitions　　2859.1.1.　Representation of Graphs　　2869.2.　Topological Sort　　2889.3.　Shortest-Path Algorithms　　2929.3.1.　Unweighted Shortest Paths　　2939.3.2.　Dijkstras Algorithm　　2979.3.3.　Graphs with Negative Edge Costs　　3069.3.4.　Acyclic Graphs　 3079.3.5. All-Pairs Shortest Path　　3109.4.　Network Flow Problems　 3109.4.1.　A Simple Maximum-Flow Algorithm　　3119.5.　Minimum Spanning Tree　　3159.5.1.　Prims Algorithm　　3169.5.2.　Kruskals Algorithm　　3189.6.　Applications of Depth-First Search　　3:219.6.1.　Undirected Graphs　　3229.6.2.　Biconnectivity　　3249.6.3.　Euler Circuits　　3289.6.4.　Directed Graphs　　3319.6.5.　Finding Strong Components　　3339.7.　Introduction to NP-Completeness　　3349.7.2.　The Class NP　　3369.7.3.　NP-Complete Problems　　337Summary　　339Exercises　　339References　　34510　Algorithm Design Techniques　　34910.1.　Greedy Algorithms　　34910.1.1.　A Simple Scheduling Problem　　35010.1.2.　Huffman Codes　　35310.1.3.　Approximate Bin Packing　　35910.2.　Divide and Conquer　　36710.2.1.　Running Time of Divide and Conquer Algorithms　　36810.2.2.　Closest-Points Problem　　37010.2.3.　The Selection Problem　　37510.2.4.　Theoretical Improvements for Arithmetic Problems　　37810.3.　Dynamic Programming　　38210.3.1.　Using a Table Instead of Recursion　　38210.3.2.　Ordering Matrix Multiplications　　38510.3.3.　Optimal Binary Search Tree　　38910.3.4.　All-Pairs Shortest Path　　39210.4.　Randomized Algorithms　　39410.4.1.　Random Number Generators　　39610.4.2. Skip Lists　 39910.4.3.　Primality Testing　　40110.5.　Backtracking Algorithms　　40310.5.1.　The Turnpike Reconstruction Problem　　40510.5.2.　Games　　407Summary　　415Exercises　　417References424ll　Amortized Analysis　　42911.1.　An Unrelated Puzzle　　43011.2.　Binomial Queues　　43011.3.　Skew Heaps　　43511.4.　Fibonacci Heaps　　43711.4.1.　Cutting Nodes in Leftist Heaps　　43011.4.2.　Lazy Merging for Binomial Queues　　44111.4.3.　The Fibonacci Heap Operations　　44411.4.4.　Proof of the Time Bound　　44511.5.　Splay Trees　　447Summary　　451Exercises　　452References　 45312　Advanced Data Structures and Implementation　　45512.1.　Top-Down Splay Trees　　45512.2.　Red Black Trees　　45912.2.1.　Bottom-Up Insertion　　46412.2.2.　Top-Down Red Black Trees　　46512.2.3.　Top-Down Deletion　　46712.3.　Deterministic Skip Lists　　47112.4.　&A-Trees　　47812.5.　Treaps　　48412.6.　k-d Trees　　48712.7.　Pairing Heaps　　490Summary　　496Exercises　　497References　　499

编辑推荐

　　作者Mark Allen Weiss在数据结构与算法分析方面卓有建树，他在此方面的著作尤其畅销，并受到广泛好评。他的Data Structures and Algorithm Analysis曾被评为20世纪最佳的30疗计算机著作之一，本书是此书的C语言版。他在数据结构与算法分析方面的系列著作已被国际上500余所大学用做教材。　　本书根据国内的教学实际对原版部分章节的内容做了调整和改编，使之更加紧凑，改编工作得到了原书作者的首肯和支持。

用户评论 (总计62条)

•   　　书写的相当精彩，对于经典的数据结构都做了非常详细的讲解，同时还手把手的教着编写代码。书不厚，对于读者来说，英文版比中文版要好理解一些。但是有一点不足就是第10章回溯算法那里的例子个人觉得不是太好，不是很好理解。
•   　　我看的是中文版的，hash table那一章，第114頁。我就直奔主題了啊。
  　　中文版里是這樣說的：
  　　
  　　我們程序的一個低效之處在於第12行上的malloc執行了H->TableSize次。這可以通過循環出現之前調用一次malloc操作。
  　　
  　　H->TheLists = malloc(H->TableSize * sizeof(struct ListNode));
  　　
  　　注意了，這裡的類型定義是這樣的：
  　　
  　　struct ListNode;
  　　typedef ListNode *List;
  　　
  　　List * TheLists;
  　　
  　　也就是說TheLists是指向List的指針，也就是List的數組；它在之前被賦值過一次：
  　　
  　　H->TheLists = malloc(sizeof(List) * H->TableSize);
  　　
  　　可以很明顯地看出來，這兩次malloc的大小、指針類型都不同，所以我認為中文版114頁的這句話是錯的。
  　　
  　　同時我寫了段代碼測試了一下，果然按照它這樣的說法會有運行時錯誤。然後我按照我的想法修改了一下就通過了：
  　　
  　　ListNode *tmp;
  　　tmp = malloc(H->TableSize * sizeof(struct ListNode));
  　　
  　　H->TheLists[0] = tmp;
  　　H->TheLists[1] = tmp + 1;
  　　
  　　這樣就沒問題。
  　　
  　　也就是說，H->TheLists必須進行一次提領才能賦值給它ListNode類型的地址。
  　　
  　　請大家幫忙確認一下，謝謝。
  　　
•   　　 首先，并不存在从所给定义出发在表的前面插入元素的真正显性的方法。 原文 Firstof all, there is no really obvious way to insert at the front of thelist from the definitions given。翻译啊 你tm用的谷歌在线翻译吧？
•   　　没有人吐槽一下翻译吗？翻译的看不下去了。
  　　
  　　举个例子，p84最下面一段“我们继续在前面例子的基础上以倒序插入关键字10到16，接着插入8......”，但图（p85图4-36下面的那幅）里面当前的顺序是插入16和15.根本没有10. 后来对照英文版发现，翻译的文字和图都对不上，英文版是插入15，14......。.我死活想不明白为什么会出现个“倒序”这个词。
  　　
  　　《c语言参考手册》的翻译版也给那么高的分，我都怀疑打分的人你们看过书了吗？
  　　接触了这么多翻译的书唯独带着“娱乐”精神来翻译的《unix编程艺术》翻译的较为不错，其它的没有一本可以少吐槽的。唉，还是直接上英文版吧。
•   　　 想学C++的，而上面写的是C语言版，是否是一样的呢，有的书写C++有的写C有什么差别呀
•   　　这种程度的书确实很少能见到了。
  　　
  　　它不在简单的地方无谓的浪费笔墨，恰到好处的把初学者带入算法和数据结构的世界。
  　　
  　　它基本上涉及了数据结构基础的“方方面面”。很难想象这书的厚度，居然能讲这么多内容（你看看算法导论有多厚就知道我在说什么了）。
  　　
  　　它在内容上并不乏深度。高级数据结构部分并不容易，如果你第一次就全部耐心看完，我也不得不怀疑那是不是真的。因为那些数据结构的额繁琐程度非同一般，如果你能随手码出其中的大半，就足以说明你的代码能力已经差不多出神入化了。
  　　
  　　最重要的是，你真的就感觉作者在你眼前给你说教一般，个人觉得，这本书真的算是一本有灵魂的书吧。甚至同一个问题在书中的不同位置出现，不断的被优化。
  　　
  　　此书很多高级部分，真的不得不佩服作者的编排，层层深入，尤其是二叉堆，斜堆，二项堆，Fibonacci堆那段。然后伸展树和Fibonacci堆又给联系起来了。均摊复杂度分析。。。。做到这种程度上，也就不难理解，为什么这个厚度的书，可以把这么多东西都讲这么详细～
  　　
  　　~~~~~
  　　这本书主要还是讲数据结构的，算法方面除非和所介绍的数据结构有很强的关系，否则一般都只是简单的介绍一下而已。这本书的算法部分确实只能说是入门，仅仅只看这本书，算法部分应该是不够的（尤其是图论，动态规划部分，篇幅太短）。
•   　　这本书买了很多年,搬了这么多次工位,一直在办公室常备的书(虽然已经很少翻看).
  　　
  　　里面使用的代码,不是所谓的伪代码,而是正经可以运行的C代码,所以新人如果能照着做一遍下来,收获应该不小.
  　　
  　　我的一个朋友,很多年前也是读这本书写了一些笔记:
  　　http://www.luocong.com/dsaanotes/
  　　
  　　另外,选题也比较适中.不偏不倚,都是一些比较常用的数据结构/算法.
  　　
  　　还需提一点的是,侯捷在写<<STL源码剖析>>一书时参考的数据结构书就是这本书.
  　　
  　　翻译质量不差,基本看起来没有带来阻碍.
  　　
  　　我对数据结构算法基本上也是持的和本书差不多的观点:常用的,基本的数据结构,算法能清楚原理,无阻碍的正确写出来即可.深究下去是个无底洞,而且各领域有各自特定的算法,真等研究某一个方向时再细致研究下去就行.
  　　
•   　　 此书最大的优点是，讲解一个算法时，不会像《算法导论》那样，每次都来一个毫无生气的术语定义，包括解释里边涉及的名词，都是同样的方式，而本书更多的，是用通俗语言描述一个算法，对于初学者，比较好理解，另外，还包含代码风格一致的C语言实现，比《算法导论》平易很多。
  　　
  　　 印象最深的是散列一章，讲解详细，表格阐述，曲线说明，非常透彻，附带代码实现，很赞；还有讲快速排序时，用直观曲线来对比各种排序算法的效率，然后得出优化结论，最后优化过的快排，效率非常好，另外这种探索研究的方法，也值得学习。
  　　
  　　 书中涉及的算法，都是比较基础经典的，都是应该掌握的，但是缺点也是，只有经典的算法，没有进一步深入或者扩展，但对于普通的算法学习者已经足够，如果算法进阶，去看《算法导论》，再进阶，去看《计算机程序设计艺术》。
  　　
  　　
  　　 PS：木有贬低《算法导论》的意思，《算法导论》术语描述有其严谨的一面，看习惯了，理解更透彻，当然它的 illustrate 和 Pseudocode 讲解的方式也非常棒，适合有一定基础的人看。
•   　　在学校图书馆借了这本书，
  　　粗略看了一些，发现感觉很多句子不通顺。。。
  　　感觉像《 c primer plus》那本书的翻译风格才是好的。
  　　希望翻译者以后在翻译相关书籍时注意语言的通顺和典雅，不要
  　　太生硬。
  　　
•   　　翻译第122页双散列这
  　　提到hash2(49)=7-0=7，所以49被插到位置6。
  　　hash2(58)=7-2=5,所以被插到位置3（不能理解）。
  　　再接着，hash2(69)=7-6=1，所以被插到位置0
  　　hash2(60)=7-4=3，因此我们尝试位置3，6，9，然后是2（不太明白）。求高手解释。
•   　　这段时间又继续深入的学习了下，觉得主要收获有两个：
  　　收获一：真正的理解了折半查找和插入查找，以前买过一本105元的书，可看了很久，就是不知道作者讲的什么，但是这本书不同，这本书的作者用形象的文字和图片的说明让人的理解入木三分。我自已也动手写了一个demo的查找：查找10000以内的一个任意一个数字，比喻6665，如果是普通的,可能要查找6666次，可是用折半顶多才10+次，也就是10余次，没有到20次，用插入查找最多才一次。当然我承认，我自己的demo的例子很理想化，可是它让我意识到了用算法查找的美妙（后面还有一种算法，暂时没看，它跟前面有些因果关系，因为我是跳跃着看的，-_-）。
  　　收获二：我学会了用栈来处理四则混合运算了，网上也有很多地方讲这个方面的，但是个人感觉还是这本书的作者写的好，因为他让我真正的理解了它的过程，这个地方我真的很感激作者，觉得学会了这个太值了，因为我现在的工作是做一个全动态的报表平台，报表是一个二维的数据架构，有合并列，动态产生列，因此许多单元格的数据都不是直接能够从数据库得到的，而是要用表达式来处理才能够得到想要的结果的。学会了这个它完满的解决了我的需求。
  　　当然还有一些没有深入理解，只是概念记住了但是理解只到了一半的：串的查找，还有树。
  　　但是我觉得如果是以前，要我记概念都好难了，现在居然能够记住概念，呵呵。我相信如果坚持反复多用心看几次定能够理解它们的。
  　　程老师，谢谢您。加油！
  　　
•   　　正在阅读中，如果有什么纰漏会在评论&笔记中给出。
  　　
  　　以下是一些感受，不定时完善：
  　　
  　　和CLRS相比，简单的多，没有太多的各种复杂分析，适合入门。
  　　
  　　英文原版，不用担心渣翻译
  　　
  　　不过采用的似乎不是真正的C代码，有时候有点别扭
  　　
  　　另外，字体太小了，看久了伤眼睛
  　　
  　　
•   　　断断续续看了两个月，没有完全看完。
  　　
  　　所有的算法都能看懂，而且可以编程实现，但还是不会做习题。
  　　离散数学的功底不行，先看看离散数学再看这本书。
•   　　薄薄的小书，tex排版，圆圆的字体排代码，c语言代码并不是全的，是c伪代码。
  　　- - 我很菜的，所以专业的东西说不出来。感觉在解说上没有算法导论那样详细（其实我觉得算法导论啰嗦）。
•   　　我买的低价版.今天刚刚买到手.
  　　
  　　这本感觉上也是基础吧.不像算法导论上那么全.
  　　
  　　从明天起开始看.
•   　　现在的程序员总是用着别人封装好的函数、类、库、API，满满的，我们就会觉得编程不过是这么回事，搭积木而已，别人都把材料提供好了，至于材料是怎么做的，不用理会。
  　　真的是这样吗？说数据结构和算法没用的人，那是因为他用不到。为什么用不到？他的层次决定了他不会接触到编程最关键最核心的部分——算法。
  　　先不说那些反应算法的力量的似乎变态的问题，也不说2006年第4期《程序员》的专题，只说，当我们遇到一个问题时，如何搭建数学模型？当我们在有限的硬件条件下要完成高速的数据处理，如何设计？当我们为客户开发完一套软件后，能不能保证未来几年内数据猛增不会带来计算量的指数级增长？当我们需要升级服务器内存和硬盘是，能不能修改几个函数就避免硬件的投资？
  　　这些问题的答案，请在这本书中寻找。
  　　表、栈、队列、树、图等基本数据结构作者并未花大力气描述，而是重在后面的对这些数据结构的应用上，每一个结论都给出了详尽的数学证明，阅读过程中，我们可以感受到蕴含在其中的匠心独运的逻辑思维之美。借用GOOGLE黑板报的一个专题，算法体现了——“数学之美”。
  　　并不是说本书就很完美了，有些章节讲得太过笼统，读起来跳跃感太强，比如第九章的网络流问题，介绍的太过简单，推导过程中省略了不少步骤，对增广路径算法讲的太粗，至于预流推进算法（Push-Relabel）则根本未提，不能不说是一个小小缺憾。
•   　　本书适合作为高级数据结构(CS7)课程或是研究生第一年算法课程的教材。学生应该具有中等程度的程学设计知识，还要具有离散数学的某些知识。
•   　　这本书真是非常好！个人感觉很适合给初学者入门看，里面的分析数学公式恰到好处，没有算法导论的令人望而生畏，也没有国内图书的草草了事，既学习了数据结构又有刚刚好的算法分析，很容易使人产生共鸣。
  　　给我印象深刻的就是快速排序那一段，真是精彩！
•   　　开篇第一章引论的第一节提出一个问题：
  　　
  　　“设有一组N个数而要确定其中第K个最大者”
  　　
  　　并给出两种解法
  　　
  　　 全排序后返回K位置上的元素。平均复杂度O(NLogN)
  　　
  　　 再建立一个临时数组，从N中读取K个数，全排序，然后依次读入其余N - K个数进来和第K名比较，大于K的值则插入到合适位置，只待循环完毕返回K位置元素。平均复杂度O(KLogK + (N - K))
  　　
  　　这两种方法在N=100万，K=50万时速度都尤其“漫长“，往往让人抓耳挠腮，作者讲叙到还有一种算法1秒钟就可以得出答案。该算法原理和快速排序一致，但只有一个方向的递归。平均复杂度O(N)。
  　　
  　　先选取一个中值元素（该中值是否合理将影响到算法效率），然后将大于等于该数的元素放到其左侧，小于该数的放到右侧，如7 4 6 8 0 -1 选取6作为中值元素，则结果应该为4 0 -1 6 8 7，接下来比较K值和现在的中值元素6所在索引(3)，如何小于3，则只需在索引0~2间再进行递归操作继续选取第K名，大于3则在4~5中递归选取第K - 3名即可。还有一关键是该为递归中的数组长度选取一临界点，小于该临界则进行选择排序，插入排序即可，比如20以内。
  　　
  　　算法真是精妙，赶紧学习。
•   前言就有说这是 研究生教材或者本科生高级数据结构的教材，不知道为什么有人说初学者能看这个……
•   哪本书适合初学者入门数据结构，求推荐
•   @空空 Weiss老师Sedgewick的Algorithm，可以说是最适合初学者自学的数据结构教材
•   英文版的内容本质上相同（手上的是电子版，函数名不同，malloc返回的指针用了显示类型转换）
  这里应该是原作者的错
•   你改的对，循环之前加上tmp=malloc之后应该把12行替换成H->TheLists[i]=tmp+i;
  其实这样申请连续空间的话根本不需要TheLists数组，直接用tmp+i代替TheLists[i]使用就可以，但这样的话数据结构的定义和接口实现方式都要做变动。
•   翻译错误很多，不过这里没错。。。看P86，确实是插入了从16到10这7个数，然后是8和9。
  C++ Primer貌似翻得还可以。。。
•   很久不看技術書籍了，容我有空再細細品讀，如有錯誤回來改正。謝謝樓上提醒。
•   我高中花了一年时间读了本书的英文版，是我读的最早的英文书。注意标题是数据结构与算法分析，讲的是算法分析，而不是算法。
•   这本书的作者还写了一本C++的实现
•   感激！
•   前辈点评很好，这本书的C++版本怎么样？
•   呃，这和我看的真的是同一本书？
  书里面不能直接拿去编译的代码并不少见，例如4.1.2的ls；
  而且书里也描述了不少比较“偏”（准确来说一般数据结构/算法书籍里面只提个名字）的数据结构，例如splay tree, fib heap etc.
  而且这个翻译质量……我摘录一段：
  无论何时只要你确定一个指向，那么你就必须保证该指针不是NULL
•   你好，我想问一下这本书有答案吗？
•   博客写的很赞~关注
•   的确翻译很生硬
•   如果hash(x)位置被占用，那么以这个位置为基础，向后间隔hash2(x)尝试插入。hash(49)=9，hash2(49)=7，所以尝试插入到位置9+7=6。58插入到8+5=3，69插入到9+1=0，60依次尝试插入到0+3，0+3+3，0+3+3+3，直到找到能插入的位置。
•   入门倒不至于吧
  这本书更CLRS的感觉确实不一样
  在我看来，反正值得一读
•   唔，其实我的意思是，这本书非常适合一个没有基础的人开始学习数据结构和算法。比严蔚敏的那本书好太多了。
•   LZ真的看完了么？后面的高级数据结构以及对应的时间复杂度分析，真能叫入门程度么？
  严格来说，此书深入浅出，很多部分即便是初学者看都没有问题。但这绝对不代表这书就是入门书，因为它同样涉及很多复杂的高级内容，而且作者一点都不草率，完全没偷工减料的意思。
•   @Earthson 这本书的分析相对其他书不太严谨，更多在直观上。而且后半部分的牵涉到的advanced data structure更多也只是停留在introduction的程度。要说非入门的部分，就是他的习题了，难度不小而且题量大。
•   如果你说此书基础，那还能理解。但是仅仅是入门的话，个人觉得也未免太低看它了。
  这书的数据结构讲得已经非常完整了（在教材的意义上），至少个人觉得重要的思想应该都涉及了（当然，也不排除我还有什么遗漏）。
  算法的话，这书倒确实是入门了点。讲得一般是和数据结构涉及的一些简单算法（不过此书重点原本就在数据结构）。独立出来的完整的也就两章而已。
  此外，后面的高级数据结构真的只是停留在介绍的程度么？
  首先，看它的说明，给出一个实现是没有问题的。其次，这个部分和前面的部分是承接的关系。倒数第二章的瘫痪分析是从树和优先队列的基础章节衍生出来的。而最后一章，作者也说得很清楚，是之前介绍的数据结构的实用变种（这句话的潜台词是你根据之前学到的思想，理解它们并不会太困难，虽然它们实现起来也许非常复杂）
•   @Earthson 首先对于我说的入门，请参考我在2#的回复。用词不当请见谅，中文不好。至于你的几个观点逻辑性，其实是有偏颇/漏洞的。
  首先教材所讲内容的完整性和深度间既不必要也不充分。还有就是introduction的深度每个人的理解不同。这本书相对其他同类型的，在advanced data structures方面的确只能算是introduction级别。
  最后de个bug，那个你说的瘫痪分析应该是amortized analysis，一般翻译成摊销分析或者均摊分析，而不是瘫痪分析。
•   抱歉，之前有点激动了。可能主要是标题的原因。主要是"入门级别"这个词。lz在2楼的解释其实只是解释了lz说的入门是什么意思。标题的冲击力确实有那么点大，不免让人“误会”。lz把级别两字去掉就不会导致这种问题了。
  至于lz所说的完整性和深度什么的，我也没有说两者直接存在什么强的关系。我无非是说了它的深度和广度都有比较好的表现，所以觉得如果作为基础和深入都是不错的选择。实际上，个人觉得这本书兼顾了入门，广度和深度。就书的厚度上来说，能做到这种程度，它确实非常出众。
  表达上的话，鄙人也不是很好，也请见谅了。
  ～～～～
  最后那个错别字抱歉，原本想打成“摊还分析”的（中文版的翻译便是）。
•   我跟你一样，这本书我早都翻烂了；还是要加强数学，一辈子都需要数学。
•   没看就评论？
•   本书下载和分章讨论地址http://bbs.theithome.com/thread-htm-fid-67.html
•   虽然你说的很好，但你的头像太烂了
•   感觉有点难..等待深究
•   对于我这个一岁的程序员来说，现在才体会到，希望别太晚～
•   没有这些底层的高效算法设计，那些封装好的函数、类、库、API都是浮云
•   以前无感，到现在了才深有体会，唉
•   书中的内容简单易懂，对于初学者非常好用，而后面的参考文献又给了你深入的方向，这个是我最喜欢的书之一。
•   薄是最大的优点
•   本书的代码，你有吗？
  到官网上找不到啊！
•   俺也没有呢 也许找不着更好咯 自己一点点地敲 理解更深
•   才看了开头就 叹为观止？ 看完再说吧。
•   mark！
•   听起来不错！这可是面试时经常会被问到的题目啊
•   作者的个人主页上就有源代码，课后题答案csdn也下的到。
•   第二个算法果然高超！
  www.h2w1.com/i/kauu
•   到 其实就是快排的第一步啊，很多书上都有讲
•   不就是快排吗···你可以再试试归并排序和这个原理差不多···
•   作者的说的是用简单的算法排序排序，例如冒泡法，所以复杂度是O(N^2)。如果用O(nlogn)的排序算法，在N=1000000的时候和O(N)的算法差距是大约20倍，体现不出优越性来。
  第二种算法也没有O(klogk+N-k)那么快的。第二阶段如果排序好的序列用数组实现，那么最坏情况是(N-k)(logk + k) (二分法查找插入位置，每次都插入在最前，一共N-k次)，如果用链表实现，那么最坏情况是(N-k)(k+C)。然后再加上排序的O(k^2)。