Data Structures and Algorithm Analysis in C, SecondEdition
數(shù)據(jù)結(jié)構(gòu)和算法分析C語言版（第二版）
by Mark Allen Weiss
作者: Mark Allen Weiss
PREFACE
卷首語
CHAPTER1:? INTRODUCTION
第一章： 簡介
CHAPTER2:? ALGORITHM ANALYSIS
第二章:? 算法分析
CHAPTER3:? LISTS,STACKS,AND QUEUE
第三章： 列表，棧，和隊列
CHAPTER4:? TREES
第四章： 樹
CHAPTER5:? HASHING
第五章： 哈希表
CHAPTER6:? PRIORITY QUEUES(HEAPS)
第六章： 優(yōu)先隊列(哈希表)
CHAPTER7:? SORTING
第七章： 排序
CHAPTER8:? THE DISJOINT SET ADT
第八章： 互斥集合，抽象數(shù)據(jù)類型
CHAPTER9:? GRAPH ALGORITHMS
第九章： 圖算法
CHAPTER10: ALGORITHM DESIGNTECHNIQUES
第十章： 算法設(shè)計技術(shù)
CHAPTER11: AMORTIZED ANALYSIS
第十一章： 分?jǐn)偡治?b>?
?
PREFACE
卷首語
Purpose/Goals
目的/目標(biāo)
?? This book describes data structures, methodsof organizing large amounts of data, and algorithm analysis, the estimation ofthe running time of algorithms. As computers become faster and faster, the needfor programs that can handle large amounts of input becomes more acute.Paradoxically, this requires more careful attention to efficiency, sinceinefficiencies in programs become most obvious when input sizes are large. Byanalyzing an algorithm before it is actually coded, students can decide if aparticular solution will be feasible. For example, in this text students lookat specific problems and see how careful implementations can reduce the timeconstraint for large amounts of data from 16 years to less than a second.Therefore, no algorithm or data structure is presented without an explanationof its running time. In some cases, minute details that affect the running time of the implementation are explored.
??? ?這本書描述了數(shù)據(jù)結(jié)構(gòu)（組織大量數(shù)據(jù)的方法）和算法分析（算法運(yùn)行時間的估計）。隨著電腦變得越來越快，就對程序可以處理大量輸入有更高的需求。矛盾的是，這就要求對效率更加注意，因?yàn)楫?dāng)輸入大量數(shù)據(jù)時，程序的低效率最為明顯。在算法被實(shí)際編碼前分析該算法，學(xué)生們就可以確定這個方案是否可行。例如，在本書中學(xué)生們會看到一些特殊的問題以及認(rèn)真仔細(xì)的實(shí)現(xiàn)是如何將大量數(shù)據(jù)的時間限制從16年變成不到一秒的。因此，沒有一個算法或數(shù)據(jù)結(jié)構(gòu)是與運(yùn)行時間的解釋無關(guān)的。在一些情況中，就要探究影響實(shí)現(xiàn)的運(yùn)行時間的微小細(xì)節(jié)。
?? Once a solution methodis determined, a program must still be written. As computers have become more powerful, the problems they solve have becomelarger and more complex, thus requiring development of more intricate programsto solve the problems. The goal of this text is to teach students goodprogramming and algorithm analysis skills simultaneously so that they candevelop such programs with the maximum amount of Efficiency.
???? ?一旦確定一個解決方案，就會寫出一個程序。隨著電腦的功能越來越強(qiáng)大，他們需要解決的問題就越來越大，越來越復(fù)雜，因此就需要更加復(fù)雜的程序去解決這些問題。本書的目的就是教學(xué)生同時掌握好的編程技能和算法分析技能，使他們可以開發(fā)出最高效的程序。
?? This book is suitable for either an advanceddata structures (CS7) course or a first-year graduate course in algorithmanalysis. Students should have some knowledge of intermediate programming,including such topics as pointers and recursion, and some background indiscrete math.
??? 這本書適合于任一高級數(shù)據(jù)結(jié)構(gòu)（CS7）課程或研究生一年級的算法分析課程。學(xué)生們應(yīng)該懂一些作為中介的編程知識（包括指針，遞歸等）和一些離散數(shù)學(xué)的知識。
?
Approach
方法
?
?? I believe it is important for students to learn how to program for themselves, not how to copyprograms from a book. On the other hand, it is virtually impossible to discussrealistic programming issues without including sample code. For this reason,the book usually provides about half to three-quarters of an implementation,and the student is encouraged to supply the rest.
??? 我認(rèn)為對于學(xué)生來說重要的是怎樣寫出自己的程序而不是怎樣從一本書里抄襲程序。另一方面，不用示例代碼討論實(shí)際編程問題幾乎是不可能的。出于這個原因，本書通常會提供實(shí)現(xiàn)的大約八分之三的內(nèi)容，剩下的部分就由學(xué)生補(bǔ)充。
?? The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the mostpopular systems programming language. The use of C instead of Pascal allows theuse of dynamically allocated arrays (see for instance rehashing in Ch. 5). Italso produces simplified code in several places, usually because the and(&&) operation is?shortcircuited.
??? 本書是用ANSI C描述的，盡管C語言有些不足，但是它大概是最流行的系統(tǒng)性的編程語言。使用C語言而不是使用Pascal語言，是因?yàn)镃語言允許動態(tài)分配數(shù)組（可以在第五章中的重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)部分找示例）。它也在幾個地方提供了簡化了的代碼，通常是因?yàn)?amp;&操作是短路（僅計算邏輯表達(dá)式中的一部分便能確定結(jié)果，而不對整個表達(dá)式進(jìn)行計算的現(xiàn)象）的。
Most criticisms of Ccenter on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as thesimultaneous assignment and testing against 0 via if (x=y) are generally not used in the text, since the loss of clarity iscompensated by only a few keystrokes and no increased speed. I believe that this bookdemonstrates that unreadable code can be avoided by exercising reasonable care.
大多數(shù)對C語言的批判都集中于使用C語言容易寫出幾乎不可讀的代碼。一些更好的技巧，例如同時分配和對0通過測試if（x=y）通常不會用在本書中，因?yàn)榍逦鹊膿p失只會增加鍵盤輸入次數(shù)而不會降低速度。我覺得這本書表明了不可讀的代碼可以通過適當(dāng)?shù)淖⒁鈦肀苊狻?/p>
Overview ?
綜述
?? Chapter 1 containsreview material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses overand over. Therefore, recursion is prevalent in this text, with examples inevery chapter except Chapter 5.
??? 第一章包含離散數(shù)學(xué)和遞歸的復(fù)習(xí)材料。我覺得使自己對遞歸感到舒服唯一的方式就是反復(fù)地去看遞歸好的用法。因此，遞歸在本書中是很普遍的，并且除了第五章，在每一章都有例子。
?? Chapter 2 deals withalgorithm analysis. This chapter explains asymptotic analysis and its majorweaknesses. Many examples are provided, including an in-depth explanation oflogarithmic running time. Simple recursive programs are analyzed by intuitivelyconverting them into iterative programs. More complicated divide-and-conquerprograms are introduced, but some of the analysis (solving recurrencerelations) is implicitly delayed until Chapter 7, where it is performed indetail.
?? 第二章研究了算法分析。這一章解釋了漸近分析法和它主要的缺點(diǎn)。本章中舉了很多例子，包括對于對數(shù)的運(yùn)行時間的深入的解釋。通過將遞歸程序轉(zhuǎn)化為迭代程序的方法分析簡單的遞歸程序。介紹了更復(fù)雜的分治法的程序，但是一些解決遞歸關(guān)系的分析被推遲到了第七章，在第七章進(jìn)行了對遞歸詳細(xì)的分析。
?? Chapter 3 covers lists,stacks, and queues. The emphasis here is on coding these data structures usingADTS, fast implementation of these data structures, and an exposition of someof their uses. There are almost no programs (just routines), but the exercisescontain plenty of ideas for programming assignments.
??? 第三章研究了鏈表，堆棧和隊列。這里的重點(diǎn)是將這些數(shù)據(jù)結(jié)構(gòu)使用抽象數(shù)據(jù)類型進(jìn)行編碼，以及這些數(shù)據(jù)結(jié)構(gòu)的快速實(shí)現(xiàn)和它們的某些應(yīng)用的闡述。幾乎沒有程序（只有慣例），但是這些練習(xí)包含了大量的編程工作的思想。
?? Chapter 4 covers trees,with an emphasis on search trees, including external search trees (B-trees).The UNIX file system and expression trees are used as examples. AVL trees andsplay trees are introduced but not analyzed. Seventy-five percent of the codeis written, leaving similar cases to be completed by the student.Additional coverage of trees, such as file compression andgame trees, is deferred until Chapter 10. Data structures for an externalmedium are considered as the final topic in several chapters.
??? 第四章研究了樹，重點(diǎn)是搜索樹，包括外部搜索樹（B-trees）。UNIX文件系統(tǒng)和表達(dá)樹被用作例子。本章介紹了平衡二叉樹和伸展樹但是沒有進(jìn)行分析。百分之七十五的代碼都提供給了讀者，留下了相似的部分讓學(xué)生來完善。樹額外覆蓋的范圍，例如文件的壓縮和對策樹推遲到第十章來介紹。對于一個外部存儲的數(shù)據(jù)結(jié)構(gòu)在最后幾章討論。
?? Chapter 5 is arelatively short chapter concerning hash tables. Some analysis is performed andextendible hashing is covered at the end of the chapter.
??? 第五章是一個關(guān)于哈希表的相對短的章節(jié)。本章的最后的部分進(jìn)行了一些關(guān)于哈希表的分析以及包括了一些可擴(kuò)散列的內(nèi)容。
?? Chapter 6 is aboutpriority queues. Binary heaps are covered, and there is additional material onsome of the theoretically interesting implementations of priority queues.
??? 第六章是關(guān)于優(yōu)先隊列的內(nèi)容。其中包括了二叉堆以及一些附加的關(guān)于優(yōu)先隊列的理論上來說很有趣的實(shí)現(xiàn)的材料。
?? Chapter 7 coverssorting. It is very specific with respect to coding details and analysis. All the important generalpurpose sorting algorithms are coveredand compared. Three algorithms are analyzed in detail: insertion sort,Shellsort, and quicksort. External sorting is covered at the end of thechapter.
??? 第七章研究了排序。它對編碼細(xì)節(jié)和分析來說都是特別的。所有重要的萬能排序算法都涉及到了并且進(jìn)行了相互的比較。針對插入排序，希爾排序和快速排序三種算法進(jìn)行了詳細(xì)的分析。外部排序在最后一章講到。
?? Chapter 8 discusses thedisjoint set algorithm with proof of the running time. This is a short andspecific chapter that can be skipped if Kruskal's algorithm is not discussed.
??? 第八章討論了不相交集合算法運(yùn)行時間的證明。它是一個很短也很特殊的章節(jié)，如果沒有學(xué)過克魯斯卡算法這一章可能會被跳過。
?? Chapter 9 covers graphalgorithms. Algorithms on graphs are interesting not only because theyfrequently occur in practice but also because their running time is so heavilydependent on the proper use of data structures. Virtually all of the standardalgorithms are presented along with appropriate data structures, pseudocode, andanalysis of running time. To place these problems in a proper context, a shortdiscussion on complexity theory (including NP-completeness and undecidability)is provided.
??? 第九章講了圖算法。圖算法是很有趣的，不只是因?yàn)樗l繁的在實(shí)踐中出現(xiàn)，也是因?yàn)樗倪\(yùn)行時間嚴(yán)重依賴于數(shù)據(jù)結(jié)構(gòu)的合理使用。實(shí)際上所有優(yōu)秀的算法都是連同恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，偽代碼和運(yùn)行時間的分析一起出現(xiàn)的。為了把這些問題放到一個合適的環(huán)境中，提供了一個關(guān)于復(fù)雜理論（包括完全性和不可判定型）的簡短的討論。
?? Chapter 10 coversalgorithm design by examining common problem-solving techniques. This chapteris heavily fortified with examples. Pseudocode is used in these later chaptersso that the student's appreciation of an example algorithm is not obscured byimplementation details.
??? 第十章講了通過測試普通的解決問題技術(shù)的算法設(shè)計。這一章提供了更多的例子。后面的章節(jié)使用了很多的偽代碼，是為了讓學(xué)生們?nèi)バ蕾p算法示例而不是去研究它的實(shí)現(xiàn)細(xì)節(jié)。
?? Chapter 11 deals withamortized analysis. Three data structures from Chapters 4 and 6 and theFibonacci heap, introduced in this chapter, are analyzed.
?? 第十一章研究了平攤分析。本章介紹并分析了來自于第四章和第六章的三個數(shù)據(jù)結(jié)構(gòu)以及斐波那契堆。
?? Chapters 1-9 provideenough material for most one-semester data structures courses. If time permits,then Chapter 10 can be covered. A graduate course on algorithm analysis couldcover Chapters 7-11. The advanced data structures analyzed in Chapter 11 caneasily be referred to in the earlier chapters. The discussion ofNP-completeness in Chapter 9 is far too brief to be used in such a course.Garey and Johnson's book on NP-completeness can be used to augment this text.
??? 第一到九章提供了一學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程的充足的資料。如果時間允許可以講第十章。對于研究生的算法分析課程，應(yīng)該講七到十一章。十一章的高級的數(shù)據(jù)結(jié)構(gòu)分析也會在前面的章節(jié)簡單的涉及到。第九章關(guān)于完全性在這種課程中的討論太短了。Garey和Johnson的關(guān)于完全性的書可以作為對本書的擴(kuò)展。
Exercises
練習(xí)
Exercises, providedat the end of each chapter, match the order in which material is presented. Thelast exercises may address the chapter as a whole rather than a specificsection. Difficult exercises are marked with an asterisk, and more challengingexercises have two asterisks.
??? 練習(xí)題，每章的最后都有，并且是按照文章順序排列的。最后的練習(xí)題或許是把整章內(nèi)容整合成一個整體而不是一個特殊的部分。比較難的習(xí)題都標(biāo)有星號，更具挑戰(zhàn)性的習(xí)題標(biāo)有兩個星號。
A solutions manualcontaining solutions to almost all the exercises is available separately fromThe Benjamin/Cummings Publishing Company.
Benjamin和Cummings的出版公司出版的解答手冊包含了幾乎所有習(xí)題的解決方法。
References
參考文獻(xiàn)
?? References are placedat the end of each chapter. Generally the references either are historical,representing the original source of the material, or they represent extensionsand improvements to the results given in the text. Some references representsolutions to exercises.
??? 參考文獻(xiàn)在每章末尾。一般每一個參考書都是有歷史性的，有的是材料的出處，有的是本文正文內(nèi)容的擴(kuò)展和提高。一些參考書是習(xí)題的解決方法。
?
Acknowledgments
鳴謝
???? I would like to thankthe many people who helped me in the preparation of this and previous versionsof the book. The professionals at Benjamin/Cummings made my book a considerablyless harrowing experience than I had been led to expect. I'd like to thank myprevious editors, Alan Apt and John Thompson, as well as Carter Shanklin, whohas edited this version, and Carter's assistant, Vivian McDougal, for answeringall my questions and putting up with my delays. Gail Carrigan atBenjamin/Cummings and Melissa G. Madsen and Laura Snyder at PublicationServices did a wonderful job with production. The C version was handled by JoeHeathward and his outstanding staff, who were able to meet the productionschedule despite the delays caused by Hurricane Andrew.
??? 非常感謝那些在準(zhǔn)備第一版和本版書的過程中幫助過我的人。Benjamin和Cummings的同行使我的書出版比我預(yù)期的要順利得多。感謝上一版的編輯Alan Apt和John Thompson，還有Carter Shanklin ，其中Carter Shanklin編輯了這一版，還有Carter的助理，Vivian McDougal，回答了我所有的問題還忍受了我的延期。在Benjamin/Cummings 的Gail Carrigan和Melissa G.Madsen 和出版服務(wù)部的Laura Snyder都為本書做了很大的貢獻(xiàn)。C版本的數(shù)據(jù)結(jié)構(gòu)是由Joe Heathward和他能夠看到產(chǎn)品計劃的優(yōu)秀的職員負(fù)責(zé)的，盡管Hurricane Andrew造成了延期。
???? I would like to thankthe reviewers, who provided valuable comments, many of which have beenincorporated into the text. Alphabetically, they are Vicki Allan (Utah StateUniversity), Henry Bauer (University of Wyoming), Alex Biliris (BostonUniversity), Jan Carroll (University of North Texas), Dan Hirschberg(University of California, Irvine), Julia Hodges (Mississippi StateUniversity), Bill Kraynek (Florida International University), Rayno D. Niemi(Rochester Institute of Technology), Robert O. Pettus (University of SouthCarolina), Robert Probasco (University of Idaho), Charles Williams (GeorgiaState University), and Chris Wilson (University of Oregon). I would particularlylike to thank Vicki Allan, who carefully read every draft and provided verydetailed suggestions for improvement.
??? 感謝審稿人，他們提供了非常有價值的注釋，這些注釋已經(jīng)被收錄到了文章當(dāng)中。照字母順序排列，他們是Vicki Allan,Henry Bauer,Alex Biliris,Jan Carroll.Dan
Hirschberg,Julia Hodges,Bill Kraynek,Rayno D.Niemi,Robert O.Pettus,Robert
Probasco,Charles Williams和Chris Wilson.特別感謝Vicki Allan，他認(rèn)真地閱讀了每一個手稿并且為本書的提高提供了非常詳細(xì)的建議。
???? At FIU, many peoplehelped with this project. Xinwei Cui and John Tso provided me with their classnotes. I'd like to thank Bill Kraynek, Wes Mackey, Jai Navlakha, and Wei Sunfor using drafts in their courses, and the many students who suffered throughthe sketchy early drafts. Maria Fiorenza, Eduardo Gonzalez, Ancin Peter, TimRiley, Jefre Riser, and Magaly Sotolongo reported several errors, and Mike Hallchecked through an early draft for programming errors. A special thanks goes toYuzheng Ding, who compiled and tested every program in the original book,including the conversion of pseudocode to Pascal. I'd be remiss to forget CarlosIbarra and Steve Luis, who kept the printers and the computer system workingand sent out tapes on a minute's notice.
在佛羅里達(dá)國際大學(xué)，許多人都給我提供了幫助。Xinwei
Cui和John Tso給我提他們的課堂筆記。我想感謝Bill
Kraynek，Wes Mackey，Jai Navlakha和Wei Sun，他們在他們的課堂上使用了我的手稿，使得許多學(xué)生試用了還算說得過去的初稿。Maria
Fiorenza, Eduardo Gonzalez, Ancin Peter, Tim Riley, Jefre Riser, 和 Magaly Sotolongo找出了幾個錯誤，Mike Hall在初稿中找出了錯誤的程序。特別感謝Yuzheng Ding，他編譯并測試了原版書中的每一個程序，包括偽代碼到Pascal的轉(zhuǎn)換。差點(diǎn)忘記了Carlos Ibarra 和Steve Luis，他們一刻不停地操作著打印機(jī)和電腦系統(tǒng)并且及時發(fā)放出磁帶。
???? This book is a product of a love for datastructures and algorithms that can be obtained only from top educators. I'dlike to take the time to thank Bob Hopkins, E. C. Horvath, and Rich Mendez, whotaught me at Cooper Union, and Bob Sedgewick, Ken Steiglitz, and Bob Tarjanfrom Princeton.
這本書是對數(shù)據(jù)結(jié)構(gòu)和算法的熱愛的產(chǎn)物，這完全來自于教過我的老師們。我想感謝在庫伯聯(lián)盟學(xué)院教過我的Bob Hopkins, E. C. Horvath, 和Rich Mendez，以及在普林斯頓大學(xué)教過我的Bob Sedgewick, Ken Steiglitz, 和Bob Tarjan。
???? Finally, I'd like tothank all my friends who provided encouragement during the project. Inparticular, I'd like to thank Michele Dorchak, Arvin Park, and Tim Snyder forlistening to my stories; Bill Kraynek, Alex Pelin, and Norman Pestaina forbeing civil next-door (office) neighbors, even when I wasn't; Lynn and TobyBerk for shelter during Andrew, and the HTMC for work relief.
???? 最后，我要感謝在整個過程中給我鼓勵的所有朋友們。尤其是要感謝傾聽我的故事的Michele Dorchak, Arvin Park,和Tim Snyder，還有一直包容我的好同事們。還要感謝在Andrew期間Lynn和Toby
Berk對我的幫助，以及HTMC對我的幫助。
???? Any mistakes in thisbook are, of course, my own. I would appreciate reports of any errors you find;my e-mail address is weiss@fiu.edu.
??? 當(dāng)然，書中的任何錯誤都是由于我個人的原因。我非常感激您能指出書中的錯誤，我的郵箱是weiss@fiu.edu。
M.A.W.
M.A.W.?
Miami , Florida
佛羅里達(dá)州邁阿密
September 1992
1992年九月
