數(shù)據(jù)結(jié)構(gòu)與算法分析-C語言描述

1、叢醐結(jié)構(gòu)與難分析C語言撤述（X） Mark Allen Weiss 衿 ？!舜屯 #（X） Mark Allen Weiss 衿 ？!舜屯 #Mark Allen WeissData Structures and Algorithm Analysis in CData Structures anAnalysis hi CSemnci EditionO機(jī)械工業(yè)版_社 China Machine Press本書是Data Structures and Algorithm Analysis in C % 書第2版的簡體中譯本。原書曾 被評(píng)為20世紀(jì)頂尖的30部計(jì)算機(jī)著作之一 作者M(jìn)ark Allen

2、 Weiss在數(shù)據(jù)結(jié)構(gòu)和算法分析方面 卓有建樹 他的數(shù)據(jù)結(jié)構(gòu)和算法分析的著作尤其暢銷.并受到廣泛好評(píng).己被世界500余所大 學(xué)用作教材、在本書中，作者更加精煉并強(qiáng)化了他對(duì)算法和數(shù)據(jù)結(jié)構(gòu)方面創(chuàng)新的處理方法。通過C程序的 實(shí)現(xiàn).著重闡述了抽象數(shù)據(jù)類型的概念.并對(duì)算法的效率.性能和運(yùn)行時(shí)間進(jìn)行了分析。全書特點(diǎn)如下r專用一章來討論算法設(shè)計(jì)技巧.包括貪婪算法.分治算法.動(dòng)態(tài)規(guī)劃.隨機(jī)化算法以及回溯算法 介紹了當(dāng)前流行的論題和新的數(shù)據(jù)結(jié)構(gòu)，如斐波那契堆.斜堆.二項(xiàng)隊(duì)列.跳躍表和伸展樹 安排一章專門討論攤還分析.考查書中介紹的一些高級(jí)數(shù)據(jù)結(jié)構(gòu)新開辟一章討論高級(jí)數(shù)據(jù)結(jié)構(gòu)以及它們的實(shí)現(xiàn).其中包括紅黑樹.自頂向下

3、伸展樹.treap樹.k-d 樹.配對(duì)堆以及其他相關(guān)內(nèi)容Mark Allen Weiss關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法方面的知名教材還有合并了堆排序平均情況分析的一些新結(jié)果Mark Allen Weiss關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法方面的知名教材還有作者簡介是怫羅里達(dá)國際大學(xué)計(jì)算機(jī)學(xué)院教授.普林斯 頓大學(xué)計(jì)算機(jī)科學(xué)傅士。除本書外.他編寫的 Data Structures and Algorithm Analysis: in作者簡介Java. Data Structures and Algorithm Analysis: in O+以及Structures and Problem Solving: Using Jav

4、a、Data Structures and Problem Solving. Using C什等,.他目前是AP (Advanced Placement)考試計(jì)算機(jī)學(xué)科委員會(huì)的主席.，9787111127482J 網(wǎng) 上購書： HYPERLINK 9787111127482北京市西城區(qū)百萬莊南街1號(hào)100037 讀者服務(wù)熱線：(010)68995259. 68995264 讀者服務(wù)信箱 hzedu http:/www, hzbook .com ISBN 7-111-12748-X/TP 2851定價(jià)：35.00元C語言描述（I） Mark Allen Weiss 矜K舜絎 ifrData St

5、ructures and Algorithm Analysis in C|Second Edition機(jī)械工業(yè)出版社 China Machine tress本書是國外數(shù)據(jù)結(jié)構(gòu)與算法分析方面的標(biāo)準(zhǔn)教材，介紹了數(shù)據(jù)結(jié)構(gòu)（大量數(shù)據(jù)的組織方法） 以及算法分析（算法運(yùn)行時(shí)間的估算）。本書的編寫目標(biāo)是同時(shí)講授好的程序設(shè)計(jì)和算法分析 技巧，使讀者可以開發(fā)出具有最離效率的程序。本書可作為離級(jí)數(shù)據(jù)結(jié)構(gòu)課程或研究生一年級(jí)算法分析課程的教材，使用本書需具有-些 中級(jí)程序設(shè)計(jì)知識(shí)，還需要離敢數(shù)學(xué)的一些背景知識(shí)。Authorized translatic frcan the English language editi

6、on entitled Data Structures and Algorithm Analysis in C，Second Edition by Mark Allen Weiss, （1SBN0-201-49840-5） published by Pearson Education ,Inc, publishing as Addison Wesley 1 jngnumCyright 1997 by Addison Wesley Izmgman. Inc.Alt rights reserved. No part of this book may be reproduced or transmi

7、tted in any form or by any means,electronic or mechanic，including photoccying，recording，or by any information storage retrieval system, without permission of Pearson Education, Itk.Chinese simplified language edition published by China Machine Press. Ccjyright 2003 by China Machine Press,本書中文簡體字版由美國

8、Person教育出鈑集團(tuán)授權(quán)機(jī)械丄業(yè)出版社獨(dú)家出版。未經(jīng)出版者書面許可，不得以任何方式復(fù)制或抄襲本書內(nèi)容。版權(quán)所有，侵權(quán)必究。本書版權(quán)S記號(hào)宇=01-2001-2200圖書在版編目（CIP）數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述（原書第2版7/（美）維斯著;瑪舜璽譯.-北京:機(jī)械工業(yè) 出版社,2004.1（計(jì)算機(jī)科學(xué)叢書）書名原文：Data Structures and Algorithm Analysis in C： Second Edaion ISBN 7-111-12748-XT.數(shù)H.維馮HI.數(shù)據(jù)結(jié)構(gòu)算法分析C語言-程序設(shè)計(jì) N.TP311.12中國版本圖書館CIP數(shù)據(jù)核字（2003）第

9、068447號(hào)機(jī)械：E業(yè)出版社（北京市西城區(qū)百萬莊大街22號(hào)郵政編碼100037）責(zé)任纗輯：蔣祎北京牛山世興印刷廠印刷新華書店北京發(fā)行所發(fā)行2004年1月第1版第1次印刷 787mmX 1092mm 1/16 - 25.5 印張 印數(shù)：0 001-5000冊(cè)定價(jià)：35.00元凡購本書，如有缺頁、倒頁、脫頁，由本社發(fā)行部調(diào)換本社購書熱線電話:（010）68326294出版者的話文藝復(fù)興以降，源遠(yuǎn)流長的科學(xué)精神和逐步形成的學(xué)術(shù)規(guī)范.使西方國家在自然科學(xué)的 各個(gè)領(lǐng)域取得了莘斷性的優(yōu)勢(shì)；也正是這樣的傳統(tǒng)，使芡國在位息技術(shù)發(fā)嵌的六h多年間名 家輩出、獨(dú)領(lǐng)風(fēng)騷。在商業(yè)化的迸程中，美國的產(chǎn)業(yè)界與教育界越來越

10、緊密地結(jié)合，計(jì)算機(jī) 學(xué)科中的許多泰山北斗冋時(shí)身處科研和教學(xué)的最前線，由此而產(chǎn)牛的經(jīng)典科學(xué)著作，不僅擘 別了研究的范疇，還揭橥了學(xué)術(shù)的源變，既遵循學(xué)術(shù)規(guī)范，又自有學(xué)者個(gè)性，其價(jià)值并不會(huì) 丙年月的流逝而減退：近年，在全球倍息化大潮的推動(dòng)下，我國的計(jì)算機(jī)產(chǎn)收發(fā)展迅猛，對(duì)專業(yè)人才的需求日 益迫切。這對(duì)計(jì)算機(jī)教育界和出版界都既是機(jī)遇、也是挑戰(zhàn)；而專業(yè)教材的建S在教育戰(zhàn)略 !:顯得舉足輕審。在我國信息技術(shù)發(fā)展時(shí)間較短、從業(yè)人員較少的現(xiàn)狀下，美國等發(fā)達(dá)國家 在其計(jì)箅機(jī)科學(xué)發(fā)展的幾十年間積淀的經(jīng)典教材仍有許多值得借鑒之處。因此，引進(jìn)一批國 外優(yōu)秀計(jì)算機(jī)教材將對(duì)我國計(jì)算機(jī)教胄事業(yè)的發(fā)展起積極的推動(dòng)作用，也是與位

11、界接軌、建 MjF的世界一流大學(xué)的必由之路=機(jī)械工業(yè)出版社華章圖文信息有限公司較意識(shí)到“出版要為教育服務(wù)”e自1998年開始， 華章公司就將工作重點(diǎn)放在了遴選、移譯國外優(yōu)秀教材上。經(jīng)過幾年的不懈努力，我們與 Prentice Hall, Addison-Wesley, McGraw-Hill, Morgan Kaufmann等世界著名出版公司建立了 良好的介作關(guān)系：從它們現(xiàn)有的數(shù)百種教材中甄選出Tanenbaum, Stroustrup，Kernighan, Jim Gray等大師名家的一批經(jīng)典作品.以計(jì)算機(jī)科學(xué)叢書”為總稱出版，供讀者學(xué)習(xí)、研 究及庋藏。大理石紋理的封面，也正體現(xiàn)了這套叢書的

12、品位和格調(diào)。“if算機(jī)科學(xué)叢書”的出版工作得到了國內(nèi)外學(xué)者的鼎力襄助，國內(nèi)的專家不僅提供了中 肯的選題指導(dǎo)，還不辭勞苦地?fù)?dān)任了翻譯和審校的工作；而原書的作者也相當(dāng)關(guān)注其作品在 中M的傳播，有的還專誠為其書的中譯本作序、.迄今，“計(jì)算機(jī)科學(xué)叢書”已經(jīng)出版了近百個(gè) 品種.這些書籍在讀者中樹立了良好的U碑，并被許多高校采用為正式教材和參考書籍，為 進(jìn)-步推廣與發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。隨看學(xué)科建設(shè)的初步完善和教材改革的逐漸深化，教育界對(duì)國外計(jì)算機(jī)教材的需求和應(yīng) 用都步入一個(gè)新的階段。為此，華章公司將加人引進(jìn)教材的力度，在“華章教育”的總規(guī)劃 之下出版三個(gè)系列的汁算機(jī)教材：除“計(jì)算機(jī)科學(xué)叢書”之外.對(duì)影印

13、版的教材.則單獨(dú)開 辟出“經(jīng)典原版書庫“；同時(shí)，引進(jìn)全美通行的教學(xué)輔導(dǎo)書“Schaums Outlines”系列組成 “全笑經(jīng)典學(xué)習(xí)指導(dǎo)系列”（為了保證這二套叢書的權(quán)威性，同時(shí)也為了更好地為學(xué)校和老師 們服務(wù)，華章公司聘請(qǐng)了中國科學(xué)院、北京大學(xué)、清華大學(xué)、國防科技大學(xué).復(fù)旦大學(xué)、上 海交通大學(xué)、南京大學(xué)、浙江大學(xué)、中國科技大學(xué)、哈爾濱工業(yè)大學(xué)、西安交通大學(xué)、中國 人民大學(xué)，北京航空航天大學(xué).北W郵電大學(xué)、中山大學(xué)、解放軍理工大學(xué)、鄭州大學(xué)、湖 北I學(xué)院、中國國家信息安全測(cè)評(píng)認(rèn)證中心等國內(nèi)重點(diǎn)大學(xué)和科研機(jī)構(gòu)在卟算機(jī)的各個(gè)領(lǐng)域 的著名學(xué)者組成“專家指涉委員會(huì)”，為我們提供選題意見和出版監(jiān)督。這二套

14、叢書是響應(yīng)教育部提出的使用外版教材的號(hào)召，為國內(nèi)髙校的計(jì)算機(jī)及相關(guān)專業(yè)的教學(xué)度身訂造的。其中許多教材均已為M. I. T. Stanford, U.C. Berkeley，C. M. U.等世界 名牌大？所采用。不僅涵蓋了程序設(shè)汁、數(shù)據(jù)結(jié)構(gòu).操作系統(tǒng).計(jì)算機(jī)體系結(jié)構(gòu).數(shù)據(jù)庫、 編譯原理、軟件工程、圖形學(xué)、通倍與網(wǎng)絡(luò)、離散數(shù)學(xué)等H內(nèi)大學(xué)計(jì)算機(jī)專業(yè)普遍開沒的核 心凍程，而且各具特色有的出自語R沒計(jì)者之手、有的歷經(jīng)三十年而不衰、有的己被全 世界的幾百所髙校采用。在這些圓熟通博的名師大作的指引之下，讀者必將在i!算機(jī)科學(xué)的 宮殿屮由登堂而人室C權(quán)威的作者，經(jīng)典的教材、一流的譯者、嚴(yán)格的審校.精細(xì)的編輯

15、.這些因素使我們的 圖書有了質(zhì)量的保證，但我們的目標(biāo)是盡善盡美，而反饋的意見正是我們達(dá)到這一終極目標(biāo) 的重要幫助。教材的出版只是我們的后續(xù)服務(wù)的起點(diǎn)。華章公司歡迎老師和讀者對(duì)我們的工 作提出建議或給予指正，我們的聯(lián)系方法如下：電子郵件： HYPERLINK mailto:hzedu hzedu聯(lián)系電話：（010） 68995264聯(lián)系地址：北京市西城區(qū)百萬莊南街13郵政編碼：10Q037專家指導(dǎo)委員會(huì)（按姓氏筆畫順序）尤晉元王珊馮博琴史忠植史美林石教英呂建孫玉芳吳世忠吳時(shí)霖張立昂李偉琴李師賢李建中楊冬青邵維忠陸麗娜陸鑫達(dá)陳向群周伯生周克定周傲英孟小峰岳麗華范明鄭國梁施伯樂鐘玉琢唐世渭袁崇義高傳

16、善梅宏程旭程時(shí)端謝希仁裘宗燕戴葵譯者序隨著速度的不斷提髙和存儲(chǔ)容量的持續(xù)増長，計(jì)算機(jī)的功能日益強(qiáng)大，從而處理數(shù)據(jù)和解 決問題的規(guī)模和復(fù)雜程度與日俱増。這不僅帶來了需要認(rèn)真研究的新課題，而且突出了原有 數(shù)據(jù)結(jié)構(gòu)和算法效率低下的缺點(diǎn)。程序的效率問題不是由于計(jì)算機(jī)功能的強(qiáng)大而受到冷落， 相反地，倒是被人們提到前所未有的重視程度，因?yàn)榇笮蛦栴}的解決所涉及到的大容量存儲(chǔ)和 髙速度運(yùn)算容不得我們對(duì)效率有絲毫的忽視。本書正是在闡述數(shù)據(jù)結(jié)構(gòu)基本概念的同時(shí)深人 地分析了算法的效率。書中詳細(xì)介紹了當(dāng)前流行的論題和新的變化，討論了算法設(shè)計(jì)技巧，并 在研究算法的性能、效率以及對(duì)運(yùn)行時(shí)間分析的基礎(chǔ)上考査了一些髙級(jí)數(shù)據(jù)結(jié)

17、構(gòu)，從歷史的角 度和近年的進(jìn)展對(duì)數(shù)據(jù)結(jié)構(gòu)的活躍領(lǐng)域進(jìn)行了簡要的槪括。由于本書選材新穎，方法實(shí)用，題 例豐富，取舍得當(dāng)，因此，自從出版以來受到廣泛歡迎,已被世界許多知名大學(xué)用作教材。本書的目的是培養(yǎng)學(xué)生良好的程序設(shè)計(jì)技巧和熟練的算法分析能力，使得他們能夠開發(fā) 出髙效率的程序。從服務(wù)于實(shí)踐又鍛煉學(xué)生實(shí)際能力出發(fā)，書中提供了大部分算法的C程序 和偽碼例程，但并不是全部。一些程序可從互聯(lián)網(wǎng)上獲得。承蒙盧開澄教授、陳賢舜先生、溫麗芳女士的鼓勵(lì)，譯者有幸將國外幾部優(yōu)秀原著介紹給 我國的讀者;蔣祎先生認(rèn)真的工作使本書譯文免除不少疏漏和錯(cuò)誤;楊海玲女士的監(jiān)督使翻譯 工作比預(yù)想的順利。譯者在此表示衷心的感謝。譯

18、者還愿意借此機(jī)會(huì)感謝摯友孫華先生，他 對(duì)本書的翻譯工作自始至終給予熱心的關(guān)懷和無私的幫助。由于時(shí)間及水平所限，書中譯文不當(dāng)之處，統(tǒng)析學(xué)術(shù)界同仁及廣大讀者賜正。譯者2003年9月目的/目標(biāo)本書討論數(shù)據(jù)結(jié)構(gòu)和算法分析。數(shù)據(jù)結(jié)構(gòu)主要研究組織大量數(shù)據(jù)的方法，而算法分析則 是對(duì)算法運(yùn)行時(shí)間的評(píng)估。隨著計(jì)算機(jī)的速度越來越快，對(duì)于能夠處理大量輸人數(shù)據(jù)的程序 的需求變得日益急切。可是，由于在輸人量很大的時(shí)候，程序的低效率現(xiàn)象變得非常明顯，因 此這又要求對(duì)效率問題給予更仔細(xì)的關(guān)注。通過在實(shí)際編程之前對(duì)算法的分析，學(xué)生可以決 定一個(gè)特定的解法是否可行。例如，學(xué)生在本書中將讀到一些特定的問題并看到精心的實(shí)現(xiàn) 方法是

19、如何把對(duì)大量數(shù)據(jù)的時(shí)間限制從16年減至不到1秒的。因此，若無運(yùn)行時(shí)間的闡釋， 就不會(huì)有算法和數(shù)據(jù)結(jié)構(gòu)的提出。在某些情況下，對(duì)于影響算法實(shí)現(xiàn)的運(yùn)行時(shí)間的一些微小 細(xì)節(jié)都需要認(rèn)真地探究。一旦解法被確定，程序還是必須要編寫的。隨著計(jì)算機(jī)的日益強(qiáng)大,它們必須解決的問題 就變得更加巨大和復(fù)雜，這就要求開發(fā)更加復(fù)雜的程序。本書的目的是同時(shí)教授學(xué)生良好的 程序設(shè)計(jì)技巧和算法分析能力，使得他們能夠開發(fā)這樣的具有最髙效率的程序。本書適合作為髙級(jí)數(shù)據(jù)結(jié)構(gòu)(CS7)課程或是研究生第一年算法分析課程的教材。學(xué)生應(yīng) 該具有中等程度的程序設(shè)計(jì)知識(shí)，包括像指針和遞歸這樣一些內(nèi)容，還要具有離散數(shù)學(xué)的某些 知識(shí)。方法我相信，對(duì)

20、于學(xué)生重要的是學(xué)習(xí)如何自己動(dòng)手編寫程序，而不是從書上拷貝程序。但另一 方面，討論現(xiàn)實(shí)程序設(shè)計(jì)問題而不套用樣本程序?qū)嶋H上是不可能的。由于這個(gè)原因，本書通常 提供實(shí)現(xiàn)方法的大約一半到四分之三的內(nèi)容并鼓勵(lì)學(xué)生補(bǔ)足其余的部分。第12章是這一版 新加的-章，討論主要側(cè)重于實(shí)現(xiàn)細(xì)節(jié)的一些附加的數(shù)據(jù)結(jié)構(gòu)。本書中的算法均以ANSI C表示，盡管有些欠缺，但它仍然是最流行的系統(tǒng)程序設(shè)計(jì)語 言。C代替Pascal的使用使得動(dòng)態(tài)分配數(shù)組成為可能(可見第5章中的“再散列”)。它還在幾 處地方將代碼簡化，這通常是因?yàn)榕c(&)操作走捷徑的緣故。對(duì)C的大多數(shù)批評(píng)集中在用它寫出的程序代碼可讀性差的事實(shí)上。僅僅少*幾次鍵，卻

21、犧牲了程序清晰性，而程序的速度又沒有増加。因此，諸如同時(shí)賦值以及通過 if ( x = y ) 測(cè)試是否為0等技巧一般不在本書中使用。相信本書將證明只要細(xì)心練習(xí)是可以避免那些難 以讀懂的代碼的。內(nèi)容提要第1章包含離散數(shù)學(xué)和遞歸的一些復(fù)習(xí)材料。我相信對(duì)遞歸做到泰然處之的惟一辦法是反復(fù)不斷地看一些好的用法。因此，除第5章外，遞歸遍及本書每一章的例子之中。第2章處理算法分析。這一章闡述漸進(jìn)分析和它的主要弱點(diǎn)。這里提供了許多例子，包 括對(duì)對(duì)數(shù)運(yùn)行時(shí)間的深人解釋。通過直觀地把一些簡單遞歸程序轉(zhuǎn)變成迭代程序而對(duì)它們進(jìn) 行分析。介紹了更為復(fù)雜的分治程序，不過有些分析（求解遞歸關(guān)系）要推遲到第7章再詳細(xì) 討論

22、。第3章包括表、棧和隊(duì)列。重點(diǎn)放在使用ADT對(duì)這些數(shù)據(jù)結(jié)構(gòu)編程，這些數(shù)據(jù)結(jié)構(gòu)的快 速實(shí)現(xiàn)，以及介紹它們的某些用途上。課文中幾乎沒有什么程序（只有些例程），而程序設(shè)計(jì)作 業(yè)的許多思想基本上體現(xiàn)在練習(xí)之中。第4章討論樹，重點(diǎn)在查找樹，包括外部查找樹（&樹）。UNIX文件系統(tǒng)和表達(dá)式樹是作 為例子來介紹的。AVL樹和伸展樹只作了介紹而沒有分析。程序?qū)懗?5%，其余部分留給 學(xué)生完成。查找樹的實(shí)現(xiàn)細(xì)節(jié)見第12章=樹的另外一些內(nèi)容，如文件壓縮和博弈樹，延遲到 第10章討論。外部媒體上的數(shù)據(jù)結(jié)構(gòu)作為幾章中的最后論題來討論。第5章是相對(duì)較短的一章，主要討論散列表。這里進(jìn)行了某些分析，本章末尾討論了可擴(kuò) 散列

23、。第6章是關(guān)于優(yōu)先隊(duì)列的。二叉堆也在這里講授，還有些附加的材料論述優(yōu)先隊(duì)列某些 理淪上有趣的實(shí)現(xiàn)方法。斐波那契堆在第11章討論，配對(duì)堆在第12章討論。第7章討論排序。它特別關(guān)注編程細(xì)節(jié)和分析。討論并比較所有通用的排序算法。對(duì)以 下四種算法詳細(xì)地進(jìn)行了分析:插人排序、希爾排序、堆排序以及快速排序。堆排序平均情形 運(yùn)行時(shí)間的分析對(duì)子這一版來說是新的內(nèi)容。本章末尾討論了外部排序。第8章討論不相交集算法并證明其運(yùn)行時(shí)間。這是短且特殊的一章，如果不討論Kruskal 算法則該章可跳過。第9章講授圖論算法。圖論算法的重要性不僅因?yàn)樗鼈冊(cè)趯?shí)踐中經(jīng)常用到，而且還因?yàn)?它們的運(yùn)行時(shí)間強(qiáng)烈地依賴于數(shù)據(jù)結(jié)構(gòu)的恰當(dāng)使

24、用。實(shí)際t，所有標(biāo)準(zhǔn)算法都是和相應(yīng)的數(shù) 據(jù)結(jié)構(gòu).偽代碼以及運(yùn)行時(shí)間的分析一起介紹的。為把這些問題放進(jìn)一本適當(dāng)?shù)慕滩腻覀?對(duì)復(fù)雜性理論（包括NP-完全性和不可判定性）進(jìn)行了簡短的討論。第10章通過考査一般的問題求解技巧討論算法設(shè)計(jì)。這一章添加了大量的實(shí)例。這里 及后面各章使用的偽代碼使得學(xué)生更好地理解例子，而避免被實(shí)現(xiàn)的細(xì)節(jié)所困擾。第11章處理攤還分析。對(duì)來自第4章到第6章的三種數(shù)據(jù)結(jié)構(gòu)以及本章介紹的斐波那 契堆進(jìn)行了分桁。第12章是這一版新加的一章，討論查找樹算法、k-d樹和配對(duì)堆。不同于其他各章，本章 給出了查找樹和配對(duì)堆完全的仔細(xì)的實(shí)現(xiàn)。材料的安排使得教師可以把一些內(nèi)容納入到其他 各章

25、的討論之中。例如，第12章中的自頂向下紅黑樹可以在（第4章的）AVL樹下討論。第1章到第9章為大多數(shù)的一學(xué)期數(shù)據(jù)結(jié)構(gòu)深程提供了足夠的材料。如果時(shí)間允許，那 么第10章也可以包括進(jìn)來。研究生的算法分析課程可以使用第7章到第11章的內(nèi)容。第 11章所分析的高級(jí)數(shù)據(jù)結(jié)構(gòu)可以容易地在前面各章中査到。第9章中對(duì)NP-完全性的討論 對(duì)于這門課來說太過簡要，Garey和Johnson的論？JP完全性的書（有張立昂等翻譯的中文譯 本:計(jì)算機(jī)和難解性，科學(xué)出版社，1987譯者注可以補(bǔ)充本書的不足。KKKK練習(xí)在每章末尾提供的練4與書中講授的內(nèi)容順序相匹配。最后的一些練習(xí)是針對(duì)整個(gè)一章 而不是特定的某一節(jié)。難做的

26、練習(xí)標(biāo)以一個(gè)星號(hào),更難的練習(xí)標(biāo)有兩個(gè)星號(hào)。教師可從Addison-Wesley出版公司得到包含幾乎所有練習(xí)答案的解題指南。 參考文獻(xiàn)參考文獻(xiàn)位于每章的最后。一般說來，這些參考文獻(xiàn)或者是歷史性的，代表著書中材料的 原始來源，或者闡述對(duì)書中給出的結(jié)果的擴(kuò)展和改進(jìn)。有些文獻(xiàn)論述了一些練的解法。 代碼的獲得本書中的程序代碼通過匿名ftp可在aw. com網(wǎng)站得到。這個(gè)網(wǎng)站也可以通過World Wide Web來訪問;其URL為http: /www. aw. com/cseng/（從此處繼續(xù)鏈接）。該資料的準(zhǔn) 確位置可能變化。致謝在本叢書幾部著作的準(zhǔn)備過程中，本人得到許多朋友的幫助。有呰人在本書的其他版

27、本 中提到過;謝謝諸位。對(duì)于這一版，我要感謝 Addison-Wesley 的編輯 Carter Shanklin 和 Susan Hartman。Teri Hyde對(duì)此書做出了完美的工作，而Matthew Harris和他在Publication Services的同事出色地 完成了本書最后的定稿任務(wù)。M.A.W.Miami, Florida 1996年7月出版者的話專家指導(dǎo)委員會(huì)譯者序前B第1章引論 TOC o 1-5 h z 1-1本書討論的內(nèi)容11.2數(shù)學(xué)知識(shí)復(fù)習(xí)2指數(shù)2對(duì)數(shù)2級(jí)數(shù)31.2.4模運(yùn)算4V2.5證明方法41,3遞歸簡論6 HYPERLINK l bookmark57 o

28、Current Document 總結(jié)9 HYPERLINK l bookmark99 o Current Document 練習(xí)9 HYPERLINK l bookmark115 o Current Document 參考文獻(xiàn)10 HYPERLINK l bookmark8 o Current Document 第2章算法分析112.1數(shù)學(xué)基礎(chǔ) 11模型 132.3要分析的問題132.4運(yùn)行時(shí)間計(jì)算15一個(gè)簡單的例子15一般法則162.4.3最大子序列和問題的解i72.4.4運(yùn)行時(shí)間中的對(duì)數(shù) 212.4.5檢驗(yàn)?zāi)愕姆治?42.4.6分析結(jié)果的準(zhǔn)確性25,維26練習(xí)26參考文獻(xiàn)29 HYPER

29、LINK l bookmark9 o Current Document 第3章表、棧和隊(duì)列313.1抽象數(shù)據(jù)類型(AU1) 31表 ADT 313.2.1表的簡單數(shù)組劣現(xiàn)32鏈表323.2.3程序設(shè)計(jì)細(xì)節(jié)333.2.4常見的錯(cuò)誤 373.2.5雙鏈表 383.2.6循環(huán)鏈表383.2.7例子393-2.8鏈表的游標(biāo)實(shí)現(xiàn)4233 棧 ADT 463.3.1棧模型 463.3.2棧的實(shí)現(xiàn)46應(yīng)用52隊(duì)列 ADT 583.4-1隊(duì)列模型583.4.2隊(duì)列的敷組實(shí)現(xiàn)583.4.3隊(duì)列的應(yīng)用61錄62 62 HYPERLINK l bookmark25 o Current Document 第4章樹65

30、4、1預(yù)備知識(shí)65樹的實(shí)現(xiàn)664.1.2樹的週歷及應(yīng)用67二叉樹70實(shí)現(xiàn)704.2.2表達(dá)式樹704.3査找樹ADT二叉査找樹 73MakeEmpty 732Find 743FindMin 和 FindMnx 744Insert 75Delete 764.3.6平均情形分析 77AVI.樹804-4.1單旋轉(zhuǎn) 824.4.2雙旋轉(zhuǎn) 844,5伸展樹89一個(gè)簡單的想法 90展開914.6樹的遍歷 964.7 B樹97 HYPERLINK l bookmark104 o Current Document 總結(jié)101練習(xí)102參考文獻(xiàn)!07 HYPERLINK l bookmark29 o Curr

31、ent Document 第5章散列111般想法m5.2散列函數(shù)in5,3分離鏈接法 1135.4開放定址法 1175.4.1線性探測(cè)法1175.4.2平方探測(cè)法1185.43雙散列1225.5再散列123 HYPERLINK l bookmark30 o Current Document 5.6可擴(kuò)散列124 HYPERLINK l bookmark31 o Current Document 總結(jié)126練習(xí)127 HYPERLINK l bookmark32 o Current Document 參考文獻(xiàn)129 HYPERLINK l bookmark34 o Current Documen

32、t 第6章優(yōu)先隊(duì)列（推）133模型133 HYPERLINK l bookmark35 o Current Document 一些簡單的實(shí)現(xiàn) 134 HYPERLINK l bookmark36 o Current Document 二叉堆1341結(jié)構(gòu)性質(zhì)1346.3.2堆序性質(zhì)1353基本的堆操作 I允6.3.4其他的堆操作 139 HYPERLINK l bookmark38 o Current Document 6.4優(yōu)先隊(duì)列的應(yīng)用1426.4.1選擇問題1426-4.2事件楔擬1431-堆144左式堆6.6.1左式堆的性質(zhì)1456.6.2左式堆的操作 1466.7斜堆6.8二項(xiàng)隊(duì)列15

33、2二項(xiàng)隊(duì)列結(jié)構(gòu) 1526.8.2二項(xiàng)隊(duì)列操作1536.83二項(xiàng)隊(duì)列的實(shí)現(xiàn)155 HYPERLINK l bookmark43 o Current Document 總結(jié)158練習(xí)159 HYPERLINK l bookmark44 o Current Document 參考文獻(xiàn)162第7章排序 HYPERLINK l bookmark47 o Current Document 7.1預(yù)備知識(shí)165 HYPERLINK l bookmark48 o Current Document 7.2插人排序165算法1651.2.2插人排序的分析166一些簡單排序算法的下界 1667.4希爾排序1677.

34、4.1希爾排序的最壞情形分析 1687.5堆排序1707.5.1堆排序的分析172 HYPERLINK l bookmark50 o Current Document 7.6歸并排序J737.6.1歸并排序的分析 175 HYPERLINK l bookmark51 o Current Document 7.7快速排序1777.7.1選取樞紐元1797.7.2分割策略1797.7.3小數(shù)組1817.7.4實(shí)際的快速排序例程181 HYPERLINK l bookmark52 o Current Document 7.7.5快速排序的分析1837.7.6選擇的線性期望時(shí)間算法 川5 7.8大型結(jié)

35、構(gòu)的排序 1867.9排序的一般下界 1877.9,1決策樹1877.10 桶式排序 1897.11外部排序1897.11.1為什么霈要新的算法1S97.11.2外部排序模型1907.11.3筒單算法1907.1V4 多 _ 并1907.11.5多相合并1927.11.6替換選擇192總結(jié) HYPERLINK l bookmark58 o Current Document 練習(xí)194 HYPERLINK l bookmark59 o Current Document 參考文獻(xiàn)197 HYPERLINK l bookmark60 o Current Document 第8章不相交集ADT 199

36、 HYPERLINK l bookmark61 o Current Document 8.1等價(jià)關(guān)系199 HYPERLINK l bookmark62 o Current Document 8-2動(dòng)態(tài)等價(jià)性問題199 HYPERLINK l bookmark63 o Current Document 8.3基本數(shù)據(jù)結(jié)構(gòu) 201 HYPERLINK l bookmark64 o Current Document 8-4靈巧求并算法 203 HYPERLINK l bookmark65 o Current Document S.5路徑壓縮2058.6按秩求并和路徑壓縮的最壞情形 207Union

37、/Find 算法分析 207 HYPERLINK l bookmark68 o Current Document 一個(gè)應(yīng)用211 HYPERLINK l bookmark69 o Current Document 總結(jié)211 HYPERLINK l bookmark70 o Current Document 練習(xí)212 HYPERLINK l bookmark71 o Current Document 參考文獻(xiàn)213 HYPERLINK l bookmark72 o Current Document 第9章圖論算法2159,1若干定義2159.1.1圖的表示216 HYPERLINK l bo

38、okmark73 o Current Document 9.2拓?fù)渑判?17 HYPERLINK l bookmark74 o Current Document 9.3最短路徑算法2199.3.1無權(quán)最短路徑 220Dijkstra算法 2249.3-3具有負(fù)邊值的圖2299.3.4無圈圖2309.3.5所有點(diǎn)對(duì)最短路徑 232 HYPERLINK l bookmark77 o Current Document 9.4網(wǎng)絡(luò)流問題232一個(gè)簡單的最大流算法 233 HYPERLINK l bookmark78 o Current Document 9.5最小生成樹236Prim算法237Krus

39、kal算法 239 HYPERLINK l bookmark80 o Current Document 9.6深度優(yōu)先搜素的應(yīng)用 2409.6.1無向圖2419.6.2雙連通性2429.6J歐拉回路2459.6.4 有向圖2489.6.5査找強(qiáng)分支 249NP-完全性介紹2509.7.】難與易251NP類252NP-完全間題 252 HYPERLINK l bookmark81 o Current Document 總結(jié)254 HYPERLINK l bookmark82 o Current Document 練習(xí)254 HYPERLINK l bookmark83 o Current Doc

40、ument 參考文獻(xiàn)258 HYPERLINK l bookmark84 o Current Document 第10章算法設(shè)計(jì)技巧263 HYPERLINK l bookmark85 o Current Document 10.1貪婪算法263個(gè)簡單的調(diào)度問題263Huffman編碼 26610.1.3近似裝箱問題 270 HYPERLINK l bookmark88 o Current Document 10.2分治算法 27610.2.1分治算法的運(yùn)行時(shí)間 27710-2.2 最近點(diǎn)問題 27910.2.3選擇問題28110.2.4 些運(yùn)算問題的理論改進(jìn)284 HYPERLINK l b

41、ookmark92 o Current Document 103 動(dòng)態(tài)規(guī)劃28710.3.1用一個(gè)表代替遞歸28710.3.2矩陣乘法的順序安排28910.3.3最優(yōu)二叉査找樹 29110.3.4所有點(diǎn)對(duì)最短路徑 294 HYPERLINK l bookmark93 o Current Document 10.4隨機(jī)化算法29610.4.1隨機(jī)數(shù)發(fā)生器 297跳躍表30010.4.3素性測(cè)試30210.5回溯算法 30410.5.1收費(fèi)公路重建問題 304博弈308 HYPERLINK l bookmark98 o Current Document 總結(jié)313練習(xí) HYPERLINK l bo

42、okmark100 o Current Document 參考文獻(xiàn)320 HYPERLINK l bookmark102 o Current Document 第11章攤還分祈325 HYPERLINK l bookmark103 o Current Document 11.1 一個(gè)無關(guān)的智力問題 32511.2二項(xiàng)隊(duì)列32611,3 斜堆32911.4斐波那契堆33111.4.1切除左式堆中的節(jié)點(diǎn) 33211.4.2二項(xiàng)隊(duì)列的懶惰合并 33411.4.3斐波那契堆操作33611.4.4時(shí)間界的證明33711.5伸展樹339總結(jié) HYPERLINK l bookmark105 o Curren

43、t Document 練習(xí)342aaaa HYPERLINK l bookmark106 o Current Document 參考文獻(xiàn)343第12章高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)345 12.1自頂向下伸展樹34512.2紅黑樹 35112.2.1自底向上插人35212.2.2自頂向下紅黑樹 35312.2.3自頂向下刪除354 HYPERLINK l bookmark108 o Current Document 12.3確定性跳躍表 357AA樹362tTeap樹367k-d樹36912.7配對(duì)堆 372 HYPERLINK l bookmark114 o Current Document 總結(jié)37

44、6練習(xí)376參考文獻(xiàn)索引381第1章引 論在這一章，我們闡述本書的目的和目標(biāo)并簡要復(fù)習(xí)離散數(shù)學(xué)以及程序設(shè)計(jì)的一些槪念。 我們將要：看到程序在較大輸入情況下的運(yùn)行性能與在適量輸入情況下的運(yùn)行性能具有同等重 要性。總結(jié)本書其余部分所需要的基本的數(shù)學(xué)基礎(chǔ)。簡要復(fù)習(xí)遞歸。1.1本書討論的內(nèi)容設(shè)有一組N個(gè)數(shù)而要確定其中第務(wù)個(gè)最大者。我們稱之為選擇問題（selection problem）。 大多數(shù)學(xué)習(xí)過一兩門程序設(shè)計(jì)課程的學(xué)生寫一個(gè)解決這種問題的程序不會(huì)有什么困難。“顯 而易見的”解決方法有很多。該問題的一種解法就是將這/V個(gè)數(shù)讀進(jìn)一個(gè)數(shù)組中，再通過某種簡單的算法，比如冒泡 排序法，以遞減順序?qū)?shù)組排序

45、，然后返回位置i上的元素。稍微好一點(diǎn)的算法可以先把前個(gè)元素讀人數(shù)組并以遞減的順序）對(duì)其排序。接著，將 剩下的元素再逐個(gè)讀人。當(dāng)新元素被讀到時(shí)，如果它小于數(shù)組中的第k個(gè)元素則忽略，否則 就將其放到數(shù)組中正確的位置上，同時(shí)將數(shù)組中的一個(gè)元素?cái)D出數(shù)組。當(dāng)算法終止時(shí).位于 第k個(gè)位置上的元素作為答案返回。這兩種算法編碼都很簡單，建議讀者試一試。此時(shí)我們自然要問:哪個(gè)算法更好？哪個(gè)算 法更重要？還是兩個(gè)算法都足夠好？使用含有一百萬個(gè)元素的隨機(jī)文件，在* = 500 000的條 件下進(jìn)行模擬發(fā)現(xiàn)，兩個(gè)算法在合理的時(shí)間量內(nèi)均不能結(jié)束；每種算法都需要計(jì)算機(jī)處理若E 干天才能算完（雖然最后還是給出了正確的答案）

46、。在第7章將討論另一種算法，該算法將在 一秒鐘左右給出問題的解。因此，雖然我們提出的兩個(gè)箅法都能算出結(jié)果，但是它們不能被 認(rèn)為是好的算法，因?yàn)閷?duì)于第三種算法在合理的時(shí)間內(nèi)能夠處理的輸人數(shù)據(jù)量而言，這兩種 算法是完全不切實(shí)際的。12341Ch11Wats3Oah%4fgd0證明：令X = logcB，Y=logcA,以及Z=logAB.此時(shí)由對(duì)數(shù)的定義得：CX = B, CY = A以及 Az = Bo聯(lián)合這三個(gè)等式則產(chǎn)生(CY)Z=C = B。因此，X= YZ.這意味著Z-X/Y, 定理得證。定理1.2 lcAB = logA + logB 證明：令X = logA，Y-logB,以及Z =

47、logAB。此時(shí)由于假設(shè)默認(rèn)的底為2, 2X-A, 2y-B 及2Z = AB。聯(lián)合最后的三個(gè)等式則有2x2y=2z-ABo因此X+Y=Z，這就證明了該 定理。T其他一些有用的公式如下，它們都能夠用類似的方法推導(dǎo)。logA /B - logA - logBlog(AB) = H log AlogX X(對(duì)聽有的 X0 成、)log 1 二 0，log 2 = 1，log I 024 = 10, log I 048 576 -201.2.3級(jí)數(shù)最容易記憶的公式足亡 2,二 2、+1 - 1 j -n: Ci1在第二個(gè)公式屮，如果0A1，則-n丨3 X趨于時(shí)該和趨向干1/U-A),這些公式是“幾何

48、級(jí)數(shù)”公式，我們對(duì)以用下面的方法推導(dǎo)關(guān)于Eq-Aj(0 A 1)的公式.令S衷不和，此吋S =】+ .4 + A2 + A3 本 A4 + A5AS = A + A2 + ,43 + A4 * A5 f如果我們將這兩個(gè)等式相減(這種運(yùn)算只能對(duì)收斂級(jí)數(shù)進(jìn)行)，等號(hào)右邊所有的項(xiàng)相消，只留 下1:S - AS = 1這就是說可以用相同的方法計(jì)算W，它是一個(gè)經(jīng)常出現(xiàn)的和=我們寫成用2乘之得到5_62425將這兩個(gè)方程相減得到1+女+參因此，5 = 2:分析中另一種常用類甩的級(jí)數(shù)是算術(shù)級(jí)數(shù)。任何這樣的級(jí)數(shù)都可以通過基本公式計(jì)算其值,、 V . - N(N 1)N2么 22例如，為求出和2 + 5 + 8

49、 1十(3-1)，將其改寫為3(1 + 2-1 3 i-(丨十1 + I 如+ 1)，顯然，它就是3H + l)/2-另一種記憶的方法則是將第項(xiàng)與最后一項(xiàng)相加(和為3 + 1),第二項(xiàng)與倒數(shù)第二項(xiàng)相加(和也是3 + 1),等等。由于有1/2個(gè)這樣的數(shù)對(duì)， 因此總和就是kGk + 1)/2,這與前面的答案相同。現(xiàn)在介紹下面兩個(gè)公式，它們就沒有那么常見T。V ；2 _ .N(N_n(2N.ilN33卜63ONk+-,.1 &7TTT7 以-1當(dāng)=-1時(shí)，后一個(gè)的公式不成立：此時(shí)我們需要下面的公式，這個(gè)公式在計(jì)算機(jī)科學(xué) 中的使用要遠(yuǎn)比在數(shù)學(xué)其他科目中使用得多。數(shù)hn叫做調(diào)和數(shù)，其和叫做調(diào)和和。下面近

50、 似式中的誤差趨向于y&O.57721566,這個(gè)值稱為歐拉常數(shù)(Eu】er s constant)c A. Hv S 7以下兩個(gè)公式只不過是一般的代數(shù)運(yùn)算.，V S /(N) = Nf(N)1 = 1S = S - S /r-J-叼1.2.4模運(yùn)算 如果N整除A-B,那么我們就說A與B模N同余(congruent)，記為A-B(mod N)o宣 觀地看，這意味著無論4還是被N去除，所得余數(shù)都是相同的。于是，816ll(nxxl)。 如同等號(hào)的情形一樣，若 A=B(nYxlN),則 AC=B+C(hkx1 N)以及 AD=RD(rmd .)(， 有許多的定理適用模運(yùn)算，其中有一些特別要用到數(shù)論來證明。我們將謹(jǐn)慎地使用模運(yùn) U 算，這樣，前面的一些定理也就足夠1.2.5證明方法證明數(shù)據(jù)結(jié)構(gòu)分析中的結(jié)論的兩個(gè)最常用的方法是歸納法和反證法(偶爾也被迫用到只 有教授們才使用的證明方法)。證明一個(gè)定理不成立的最好的方法是舉出一個(gè)反例。 歸納法證明 由歸納法進(jìn)行的證明有兩個(gè)標(biāo)準(zhǔn)的部分。第一步是證明基準(zhǔn)情形(ba