數據結構與算法分析

所属分类:計算機理論、基礎知識  
出版时间:2005-8   出版时间:人民郵電出版社   作者:維斯   页数:501  

内容概要

  《數據結構與算法分析︰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)。
 

計算機與互聯網 PDF免费下载,計算機理論、基礎知識PDF免费下载。 计算机教程网 

计算机教程网 @ 2018