數(shù)據(jù)結(jié)構(gòu)與算法分析

出版時間:2005-8  出版社:人民郵電出版社  作者:維斯  頁數(shù):501  
Tag標簽:無  

內(nèi)容概要

  《數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)是數(shù)據(jù)結(jié)構(gòu)和算法分析方面的經(jīng)典教材。第2版更加精煉并強化了《數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)創(chuàng)新的對算法和數(shù)據(jù)結(jié)構(gòu)的講授方法。通過C程序的實現(xiàn),著重闡述了抽象數(shù)據(jù)類型(ADT)的概念,并對算法的效率、性能和運行時間進行了分析?!稊?shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)適合作為本科數(shù)據(jù)結(jié)構(gòu)課程或研究生第一年算法分析課程的教材。第1~9章為大多數(shù)本科一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程提供了足夠的材料。多學(xué)時課程可講授第10章。研究生的算法分析課程可以使用第6~12章的內(nèi)容。

作者簡介

  Mark Allen Weiss,美國佛羅里達國際大學(xué)計算機學(xué)院教授,普林斯頓大學(xué)汁算機科學(xué)博士,他目前是AP(Advanced Placemenl)考試汁算機學(xué)科委員會的主席。除本書外,他還撰寫了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在數(shù)據(jù)結(jié)構(gòu)與算法分析方面卓有建樹,他在此方面的著作尤其暢銷,并受到廣泛好評。他的Data Structures and Algorithm Analysis曾被評為20世紀最佳的30療計算機著作之一,本書是此書的C語言版。他在數(shù)據(jù)結(jié)構(gòu)與算法分析方面的系列著作已被國際上500余所大學(xué)用做教材?! ”緯鶕?jù)國內(nèi)的教學(xué)實際對原版部分章節(jié)的內(nèi)容做了調(diào)整和改編,使之更加緊湊,改編工作得到了原書作者的首肯和支持。

圖書封面

圖書標簽Tags

評論、評分、閱讀與下載


    數(shù)據(jù)結(jié)構(gòu)與算法分析 PDF格式下載


用戶評論 (總計62條)

 
 

  •     書寫的相當精彩,對于經(jīng)典的數(shù)據(jù)結(jié)構(gòu)都做了非常詳細的講解,同時還手把手的教著編寫代碼。書不厚,對于讀者來說,英文版比中文版要好理解一些。但是有一點不足就是第10章回溯算法那里的例子個人覺得不是太好,不是很好理解。
  •     我看的是中文版的,hash table那一章,第114頁。我就直奔主題了啊。
      中文版里是這樣說的:
      
      我們程序的一個低效之處在於第12行上的malloc執(zhí)行了H->TableSize次。這可以通過循環(huán)出現(xiàn)之前調(diào)用一次malloc操作。
      
      H->TheLists = malloc(H->TableSize * sizeof(struct ListNode));
      
      注意了,這裡的類型定義是這樣的:
      
      struct ListNode;
      typedef ListNode *List;
      
      List * TheLists;
      
      也就是說TheLists是指向List的指針,也就是List的數(shù)組;它在之前被賦值過一次:
      
      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必須進行一次提領(lǐng)才能賦值給它ListNode類型的地址。
      
      請大家?guī)兔Υ_認一下,謝謝。
      
  •      首先,并不存在從所給定義出發(fā)在表的前面插入元素的真正顯性的方法。 原文 Firstof all, there is no really obvious way to insert at the front of thelist from the definitions given。翻譯啊 你tm用的谷歌在線翻譯吧?
  •     沒有人吐槽一下翻譯嗎?翻譯的看不下去了。
      
      舉個例子,p84最下面一段“我們繼續(xù)在前面例子的基礎(chǔ)上以倒序插入關(guān)鍵字10到16,接著插入8......”,但圖(p85圖4-36下面的那幅)里面當前的順序是插入16和15.根本沒有10. 后來對照英文版發(fā)現(xiàn),翻譯的文字和圖都對不上,英文版是插入15,14......。.我死活想不明白為什么會出現(xiàn)個“倒序”這個詞。
      
      《c語言參考手冊》的翻譯版也給那么高的分,我都懷疑打分的人你們看過書了嗎?
      接觸了這么多翻譯的書唯獨帶著“娛樂”精神來翻譯的《unix編程藝術(shù)》翻譯的較為不錯,其它的沒有一本可以少吐槽的。唉,還是直接上英文版吧。
  •      想學(xué)C++的,而上面寫的是C語言版,是否是一樣的呢,有的書寫C++有的寫C有什么差別呀
  •     這種程度的書確實很少能見到了。
      
      它不在簡單的地方無謂的浪費筆墨,恰到好處的把初學(xué)者帶入算法和數(shù)據(jù)結(jié)構(gòu)的世界。
      
      它基本上涉及了數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的“方方面面”。很難想象這書的厚度,居然能講這么多內(nèi)容(你看看算法導(dǎo)論有多厚就知道我在說什么了)。
      
      它在內(nèi)容上并不乏深度。高級數(shù)據(jù)結(jié)構(gòu)部分并不容易,如果你第一次就全部耐心看完,我也不得不懷疑那是不是真的。因為那些數(shù)據(jù)結(jié)構(gòu)的額繁瑣程度非同一般,如果你能隨手碼出其中的大半,就足以說明你的代碼能力已經(jīng)差不多出神入化了。
      
      最重要的是,你真的就感覺作者在你眼前給你說教一般,個人覺得,這本書真的算是一本有靈魂的書吧。甚至同一個問題在書中的不同位置出現(xiàn),不斷的被優(yōu)化。
      
      此書很多高級部分,真的不得不佩服作者的編排,層層深入,尤其是二叉堆,斜堆,二項堆,F(xiàn)ibonacci堆那段。然后伸展樹和Fibonacci堆又給聯(lián)系起來了。均攤復(fù)雜度分析。。。。做到這種程度上,也就不難理解,為什么這個厚度的書,可以把這么多東西都講這么詳細~
      
      ~~~~~
      這本書主要還是講數(shù)據(jù)結(jié)構(gòu)的,算法方面除非和所介紹的數(shù)據(jù)結(jié)構(gòu)有很強的關(guān)系,否則一般都只是簡單的介紹一下而已。這本書的算法部分確實只能說是入門,僅僅只看這本書,算法部分應(yīng)該是不夠的(尤其是圖論,動態(tài)規(guī)劃部分,篇幅太短)。
  •     這本書買了很多年,搬了這么多次工位,一直在辦公室常備的書(雖然已經(jīng)很少翻看).
      
      里面使用的代碼,不是所謂的偽代碼,而是正經(jīng)可以運行的C代碼,所以新人如果能照著做一遍下來,收獲應(yīng)該不小.
      
      我的一個朋友,很多年前也是讀這本書寫了一些筆記:
      http://www.luocong.com/dsaanotes/
      
      另外,選題也比較適中.不偏不倚,都是一些比較常用的數(shù)據(jù)結(jié)構(gòu)/算法.
      
      還需提一點的是,侯捷在寫<<STL源碼剖析>>一書時參考的數(shù)據(jù)結(jié)構(gòu)書就是這本書.
      
      翻譯質(zhì)量不差,基本看起來沒有帶來阻礙.
      
      我對數(shù)據(jù)結(jié)構(gòu)算法基本上也是持的和本書差不多的觀點:常用的,基本的數(shù)據(jù)結(jié)構(gòu),算法能清楚原理,無阻礙的正確寫出來即可.深究下去是個無底洞,而且各領(lǐng)域有各自特定的算法,真等研究某一個方向時再細致研究下去就行.
      
  •      此書最大的優(yōu)點是,講解一個算法時,不會像《算法導(dǎo)論》那樣,每次都來一個毫無生氣的術(shù)語定義,包括解釋里邊涉及的名詞,都是同樣的方式,而本書更多的,是用通俗語言描述一個算法,對于初學(xué)者,比較好理解,另外,還包含代碼風格一致的C語言實現(xiàn),比《算法導(dǎo)論》平易很多。
      
       印象最深的是散列一章,講解詳細,表格闡述,曲線說明,非常透徹,附帶代碼實現(xiàn),很贊;還有講快速排序時,用直觀曲線來對比各種排序算法的效率,然后得出優(yōu)化結(jié)論,最后優(yōu)化過的快排,效率非常好,另外這種探索研究的方法,也值得學(xué)習(xí)。
      
       書中涉及的算法,都是比較基礎(chǔ)經(jīng)典的,都是應(yīng)該掌握的,但是缺點也是,只有經(jīng)典的算法,沒有進一步深入或者擴展,但對于普通的算法學(xué)習(xí)者已經(jīng)足夠,如果算法進階,去看《算法導(dǎo)論》,再進階,去看《計算機程序設(shè)計藝術(shù)》。
      
      
       PS:木有貶低《算法導(dǎo)論》的意思,《算法導(dǎo)論》術(shù)語描述有其嚴謹?shù)囊幻?,看?xí)慣了,理解更透徹,當然它的 illustrate 和 Pseudocode 講解的方式也非常棒,適合有一定基礎(chǔ)的人看。
  •     在學(xué)校圖書館借了這本書,
      粗略看了一些,發(fā)現(xiàn)感覺很多句子不通順。。。
      感覺像《 c primer plus》那本書的翻譯風格才是好的。
      希望翻譯者以后在翻譯相關(guān)書籍時注意語言的通順和典雅,不要
      太生硬。
      
  •     翻譯第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(不太明白)。求高手解釋。
  •     這段時間又繼續(xù)深入的學(xué)習(xí)了下,覺得主要收獲有兩個:
      收獲一:真正的理解了折半查找和插入查找,以前買過一本105元的書,可看了很久,就是不知道作者講的什么,但是這本書不同,這本書的作者用形象的文字和圖片的說明讓人的理解入木三分。我自已也動手寫了一個demo的查找:查找10000以內(nèi)的一個任意一個數(shù)字,比喻6665,如果是普通的,可能要查找6666次,可是用折半頂多才10+次,也就是10余次,沒有到20次,用插入查找最多才一次。當然我承認,我自己的demo的例子很理想化,可是它讓我意識到了用算法查找的美妙(后面還有一種算法,暫時沒看,它跟前面有些因果關(guān)系,因為我是跳躍著看的,-_-)。
      收獲二:我學(xué)會了用棧來處理四則混合運算了,網(wǎng)上也有很多地方講這個方面的,但是個人感覺還是這本書的作者寫的好,因為他讓我真正的理解了它的過程,這個地方我真的很感激作者,覺得學(xué)會了這個太值了,因為我現(xiàn)在的工作是做一個全動態(tài)的報表平臺,報表是一個二維的數(shù)據(jù)架構(gòu),有合并列,動態(tài)產(chǎn)生列,因此許多單元格的數(shù)據(jù)都不是直接能夠從數(shù)據(jù)庫得到的,而是要用表達式來處理才能夠得到想要的結(jié)果的。學(xué)會了這個它完滿的解決了我的需求。
      當然還有一些沒有深入理解,只是概念記住了但是理解只到了一半的:串的查找,還有樹。
      但是我覺得如果是以前,要我記概念都好難了,現(xiàn)在居然能夠記住概念,呵呵。我相信如果堅持反復(fù)多用心看幾次定能夠理解它們的。
      程老師,謝謝您。加油!
      
  •     正在閱讀中,如果有什么紕漏會在評論&筆記中給出。
      
      以下是一些感受,不定時完善:
      
      和CLRS相比,簡單的多,沒有太多的各種復(fù)雜分析,適合入門。
      
      英文原版,不用擔心渣翻譯
      
      不過采用的似乎不是真正的C代碼,有時候有點別扭
      
      另外,字體太小了,看久了傷眼睛
      
      
  •     斷斷續(xù)續(xù)看了兩個月,沒有完全看完。
      
      所有的算法都能看懂,而且可以編程實現(xiàn),但還是不會做習(xí)題。
      離散數(shù)學(xué)的功底不行,先看看離散數(shù)學(xué)再看這本書。
  •     薄薄的小書,tex排版,圓圓的字體排代碼,c語言代碼并不是全的,是c偽代碼。
      - - 我很菜的,所以專業(yè)的東西說不出來。感覺在解說上沒有算法導(dǎo)論那樣詳細(其實我覺得算法導(dǎo)論啰嗦)。
  •     我買的低價版.今天剛剛買到手.
      
      這本感覺上也是基礎(chǔ)吧.不像算法導(dǎo)論上那么全.
      
      從明天起開始看.
  •     現(xiàn)在的程序員總是用著別人封裝好的函數(shù)、類、庫、API,滿滿的,我們就會覺得編程不過是這么回事,搭積木而已,別人都把材料提供好了,至于材料是怎么做的,不用理會。
      真的是這樣嗎?說數(shù)據(jù)結(jié)構(gòu)和算法沒用的人,那是因為他用不到。為什么用不到?他的層次決定了他不會接觸到編程最關(guān)鍵最核心的部分——算法。
      先不說那些反應(yīng)算法的力量的似乎變態(tài)的問題,也不說2006年第4期《程序員》的專題,只說,當我們遇到一個問題時,如何搭建數(shù)學(xué)模型?當我們在有限的硬件條件下要完成高速的數(shù)據(jù)處理,如何設(shè)計?當我們?yōu)榭蛻糸_發(fā)完一套軟件后,能不能保證未來幾年內(nèi)數(shù)據(jù)猛增不會帶來計算量的指數(shù)級增長?當我們需要升級服務(wù)器內(nèi)存和硬盤是,能不能修改幾個函數(shù)就避免硬件的投資?
      這些問題的答案,請在這本書中尋找。
      表、棧、隊列、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)作者并未花大力氣描述,而是重在后面的對這些數(shù)據(jù)結(jié)構(gòu)的應(yīng)用上,每一個結(jié)論都給出了詳盡的數(shù)學(xué)證明,閱讀過程中,我們可以感受到蘊含在其中的匠心獨運的邏輯思維之美。借用GOOGLE黑板報的一個專題,算法體現(xiàn)了——“數(shù)學(xué)之美”。
      并不是說本書就很完美了,有些章節(jié)講得太過籠統(tǒng),讀起來跳躍感太強,比如第九章的網(wǎng)絡(luò)流問題,介紹的太過簡單,推導(dǎo)過程中省略了不少步驟,對增廣路徑算法講的太粗,至于預(yù)流推進算法(Push-Relabel)則根本未提,不能不說是一個小小缺憾。
  •     本書適合作為高級數(shù)據(jù)結(jié)構(gòu)(CS7)課程或是研究生第一年算法課程的教材。學(xué)生應(yīng)該具有中等程度的程學(xué)設(shè)計知識,還要具有離散數(shù)學(xué)的某些知識。
  •     這本書真是非常好!個人感覺很適合給初學(xué)者入門看,里面的分析數(shù)學(xué)公式恰到好處,沒有算法導(dǎo)論的令人望而生畏,也沒有國內(nèi)圖書的草草了事,既學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)又有剛剛好的算法分析,很容易使人產(chǎn)生共鳴。
      給我印象深刻的就是快速排序那一段,真是精彩!
  •     開篇第一章引論的第一節(jié)提出一個問題:
      
      “設(shè)有一組N個數(shù)而要確定其中第K個最大者”
      
      并給出兩種解法
      
       全排序后返回K位置上的元素。平均復(fù)雜度O(NLogN)
      
       再建立一個臨時數(shù)組,從N中讀取K個數(shù),全排序,然后依次讀入其余N - K個數(shù)進來和第K名比較,大于K的值則插入到合適位置,只待循環(huán)完畢返回K位置元素。平均復(fù)雜度O(KLogK + (N - K))
      
      這兩種方法在N=100萬,K=50萬時速度都尤其“漫長“,往往讓人抓耳撓腮,作者講敘到還有一種算法1秒鐘就可以得出答案。該算法原理和快速排序一致,但只有一個方向的遞歸。平均復(fù)雜度O(N)。
      
      先選取一個中值元素(該中值是否合理將影響到算法效率),然后將大于等于該數(shù)的元素放到其左側(cè),小于該數(shù)的放到右側(cè),如7 4 6 8 0 -1 選取6作為中值元素,則結(jié)果應(yīng)該為4 0 -1 6 8 7,接下來比較K值和現(xiàn)在的中值元素6所在索引(3),如何小于3,則只需在索引0~2間再進行遞歸操作繼續(xù)選取第K名,大于3則在4~5中遞歸選取第K - 3名即可。還有一關(guān)鍵是該為遞歸中的數(shù)組長度選取一臨界點,小于該臨界則進行選擇排序,插入排序即可,比如20以內(nèi)。
      
      算法真是精妙,趕緊學(xué)習(xí)。
  •   前言就有說這是 研究生教材或者本科生高級數(shù)據(jù)結(jié)構(gòu)的教材,不知道為什么有人說初學(xué)者能看這個……
  •   哪本書適合初學(xué)者入門數(shù)據(jù)結(jié)構(gòu),求推薦
  •   @空空 Weiss老師Sedgewick的Algorithm,可以說是最適合初學(xué)者自學(xué)的數(shù)據(jù)結(jié)構(gòu)教材
  •   英文版的內(nèi)容本質(zhì)上相同(手上的是電子版,函數(shù)名不同,malloc返回的指針用了顯示類型轉(zhuǎn)換)
    這里應(yīng)該是原作者的錯
  •   你改的對,循環(huán)之前加上tmp=malloc之后應(yīng)該把12行替換成H->TheLists[i]=tmp+i;
    其實這樣申請連續(xù)空間的話根本不需要TheLists數(shù)組,直接用tmp+i代替TheLists[i]使用就可以,但這樣的話數(shù)據(jù)結(jié)構(gòu)的定義和接口實現(xiàn)方式都要做變動。
  •   翻譯錯誤很多,不過這里沒錯。。??碢86,確實是插入了從16到10這7個數(shù),然后是8和9。
    C++ Primer貌似翻得還可以。。。
  •   很久不看技術(shù)書籍了,容我有空再細細品讀,如有錯誤回來改正。謝謝樓上提醒。
  •   我高中花了一年時間讀了本書的英文版,是我讀的最早的英文書。注意標題是數(shù)據(jù)結(jié)構(gòu)與算法分析,講的是算法分析,而不是算法。
  •   這本書的作者還寫了一本C++的實現(xiàn)
  •   感激!
  •   前輩點評很好,這本書的C++版本怎么樣?
  •   呃,這和我看的真的是同一本書?
    書里面不能直接拿去編譯的代碼并不少見,例如4.1.2的ls;
    而且書里也描述了不少比較“偏”(準確來說一般數(shù)據(jù)結(jié)構(gòu)/算法書籍里面只提個名字)的數(shù)據(jù)結(jié)構(gòu),例如splay tree, fib heap etc.
    而且這個翻譯質(zhì)量……我摘錄一段:
    無論何時只要你確定一個指向,那么你就必須保證該指針不是NULL
  •   你好,我想問一下這本書有答案嗎?
  •   博客寫的很贊~關(guān)注
  •   的確翻譯很生硬
  •   如果hash(x)位置被占用,那么以這個位置為基礎(chǔ),向后間隔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的感覺確實不一樣
    在我看來,反正值得一讀
  •   唔,其實我的意思是,這本書非常適合一個沒有基礎(chǔ)的人開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法。比嚴蔚敏的那本書好太多了。
  •   LZ真的看完了么?后面的高級數(shù)據(jù)結(jié)構(gòu)以及對應(yīng)的時間復(fù)雜度分析,真能叫入門程度么?
    嚴格來說,此書深入淺出,很多部分即便是初學(xué)者看都沒有問題。但這絕對不代表這書就是入門書,因為它同樣涉及很多復(fù)雜的高級內(nèi)容,而且作者一點都不草率,完全沒偷工減料的意思。
  •   @Earthson 這本書的分析相對其他書不太嚴謹,更多在直觀上。而且后半部分的牽涉到的advanced data structure更多也只是停留在introduction的程度。要說非入門的部分,就是他的習(xí)題了,難度不小而且題量大。
  •   如果你說此書基礎(chǔ),那還能理解。但是僅僅是入門的話,個人覺得也未免太低看它了。
    這書的數(shù)據(jù)結(jié)構(gòu)講得已經(jīng)非常完整了(在教材的意義上),至少個人覺得重要的思想應(yīng)該都涉及了(當然,也不排除我還有什么遺漏)。
    算法的話,這書倒確實是入門了點。講得一般是和數(shù)據(jù)結(jié)構(gòu)涉及的一些簡單算法(不過此書重點原本就在數(shù)據(jù)結(jié)構(gòu))。獨立出來的完整的也就兩章而已。
    此外,后面的高級數(shù)據(jù)結(jié)構(gòu)真的只是停留在介紹的程度么?
    首先,看它的說明,給出一個實現(xiàn)是沒有問題的。其次,這個部分和前面的部分是承接的關(guān)系。倒數(shù)第二章的癱瘓分析是從樹和優(yōu)先隊列的基礎(chǔ)章節(jié)衍生出來的。而最后一章,作者也說得很清楚,是之前介紹的數(shù)據(jù)結(jié)構(gòu)的實用變種(這句話的潛臺詞是你根據(jù)之前學(xué)到的思想,理解它們并不會太困難,雖然它們實現(xiàn)起來也許非常復(fù)雜)
  •   @Earthson 首先對于我說的入門,請參考我在2#的回復(fù)。用詞不當請見諒,中文不好。至于你的幾個觀點邏輯性,其實是有偏頗/漏洞的。
    首先教材所講內(nèi)容的完整性和深度間既不必要也不充分。還有就是introduction的深度每個人的理解不同。這本書相對其他同類型的,在advanced data structures方面的確只能算是introduction級別。
    最后de個bug,那個你說的癱瘓分析應(yīng)該是amortized analysis,一般翻譯成攤銷分析或者均攤分析,而不是癱瘓分析。
  •   抱歉,之前有點激動了??赡苤饕菢祟}的原因。主要是"入門級別"這個詞。lz在2樓的解釋其實只是解釋了lz說的入門是什么意思。標題的沖擊力確實有那么點大,不免讓人“誤會”。lz把級別兩字去掉就不會導(dǎo)致這種問題了。
    至于lz所說的完整性和深度什么的,我也沒有說兩者直接存在什么強的關(guān)系。我無非是說了它的深度和廣度都有比較好的表現(xiàn),所以覺得如果作為基礎(chǔ)和深入都是不錯的選擇。實際上,個人覺得這本書兼顧了入門,廣度和深度。就書的厚度上來說,能做到這種程度,它確實非常出眾。
    表達上的話,鄙人也不是很好,也請見諒了。
    ~~~~
    最后那個錯別字抱歉,原本想打成“攤還分析”的(中文版的翻譯便是)。
  •   我跟你一樣,這本書我早都翻爛了;還是要加強數(shù)學(xué),一輩子都需要數(shù)學(xué)。
  •   沒看就評論?
  •   本書下載和分章討論地址http://bbs.theithome.com/thread-htm-fid-67.html
  •   雖然你說的很好,但你的頭像太爛了
  •   感覺有點難..等待深究
  •   對于我這個一歲的程序員來說,現(xiàn)在才體會到,希望別太晚~
  •   沒有這些底層的高效算法設(shè)計,那些封裝好的函數(shù)、類、庫、API都是浮云
  •   以前無感,到現(xiàn)在了才深有體會,唉
  •   書中的內(nèi)容簡單易懂,對于初學(xué)者非常好用,而后面的參考文獻又給了你深入的方向,這個是我最喜歡的書之一。
  •   薄是最大的優(yōu)點
  •   本書的代碼,你有嗎?
    到官網(wǎng)上找不到啊!
  •   俺也沒有呢 也許找不著更好咯 自己一點點地敲 理解更深
  •   才看了開頭就 嘆為觀止? 看完再說吧。
  •   mark!
  •   聽起來不錯!這可是面試時經(jīng)常會被問到的題目啊
  •   作者的個人主頁上就有源代碼,課后題答案csdn也下的到。
  •   第二個算法果然高超!
    www.h2w1.com/i/kauu
  •   到 其實就是快排的第一步啊,很多書上都有講
  •   不就是快排嗎···你可以再試試歸并排序和這個原理差不多···
  •   作者的說的是用簡單的算法排序排序,例如冒泡法,所以復(fù)雜度是O(N^2)。如果用O(nlogn)的排序算法,在N=1000000的時候和O(N)的算法差距是大約20倍,體現(xiàn)不出優(yōu)越性來。
    第二種算法也沒有O(klogk+N-k)那么快的。第二階段如果排序好的序列用數(shù)組實現(xiàn),那么最壞情況是(N-k)(logk + k) (二分法查找插入位置,每次都插入在最前,一共N-k次),如果用鏈表實現(xiàn),那么最壞情況是(N-k)(k+C)。然后再加上排序的O(k^2)。
 

250萬本中文圖書簡介、評論、評分,PDF格式免費下載。 第一圖書網(wǎng) 手機版

京ICP備13047387號-7