算法：C語(yǔ)言實(shí)現(xiàn)

前言

寫本書(shū)的目的是為了對(duì)當(dāng)今使用最為重要的計(jì)算機(jī)算法做一綜述，并為需要學(xué)習(xí)這方面知識(shí)的越來(lái)越多的讀者提供基礎(chǔ)的技術(shù)。本書(shū)可以在學(xué)生掌握了所需的基本程序設(shè)計(jì)技巧，熟悉了計(jì)算機(jī)系統(tǒng)，但還未學(xué)過(guò)計(jì)算機(jī)科學(xué)或計(jì)算機(jī)應(yīng)用高級(jí)領(lǐng)域的專業(yè)課程的時(shí)候，用作計(jì)算機(jī)科學(xué)的第二。第三或第四門課程的教科書(shū)。此外，由于本書(shū)包含了大量有用算法的實(shí)現(xiàn)，以及關(guān)于這些算法的性能特征的詳細(xì)信息，因而它還可用于自學(xué)，或者作為從事計(jì)算機(jī)系統(tǒng)或應(yīng)用程序開(kāi)發(fā)人員的參考手冊(cè)。寬廣的視角使得本書(shū)成為計(jì)算機(jī)算法領(lǐng)域最合適的入門讀物。對(duì)于新的一版，我不僅完全重寫了它的內(nèi)容，而且還添加了一千多個(gè)練習(xí)。一百多幅圖表和數(shù)十個(gè)新程序。我還給所有圖表和程序添加了詳細(xì)的注釋。新的素材不僅涵蓋了新的主題，而且還包含對(duì)經(jīng)典算法的更完整解釋。抽象數(shù)據(jù)類型是這本書(shū)的重點(diǎn)，這使得程序應(yīng)用更廣泛，并且與現(xiàn)代面向?qū)ο蟮某绦蛟O(shè)計(jì)環(huán)境更緊密。讀過(guò)本書(shū)舊版本的人一定會(huì)發(fā)現(xiàn)，新版本包含了更為豐富的新信息，所有讀者將發(fā)現(xiàn)大量的教學(xué)資料為掌握基本概念提供了有效途徑。由于新的素材數(shù)量過(guò)多，所以我們把新版本分為兩卷（每一卷的容量都大約為舊版本的大?。緯?shū)是第一卷。這卷書(shū)中包含了基本概念。數(shù)據(jù)結(jié)構(gòu)。排序算法和搜索算法，第二卷涵蓋的高級(jí)算法及應(yīng)用是以第一卷的基本抽象概念和方法為基礎(chǔ)的。這個(gè)新版中的關(guān)于基本原理和數(shù)據(jù)結(jié)構(gòu)的所有素材幾乎都是新的。這本書(shū)不僅適合于程序員和計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生，而且也適合于想利用計(jì)算機(jī)并想使它運(yùn)行更快或是想要解決更大問(wèn)題的人們。這本書(shū)中的算法代表了過(guò)去50年來(lái)所研究的知識(shí)主體。對(duì)于大量應(yīng)用問(wèn)題，這些知識(shí)主體已經(jīng)成為有效使用計(jì)算機(jī)的不可缺少的部分。從物理學(xué)中的N-體模擬問(wèn)題到分子生物學(xué)中的序列分析問(wèn)題，在此所描述的基本方法在科學(xué)研究中已日顯重要。另外，對(duì)于從數(shù)據(jù)庫(kù)系統(tǒng)到Internet搜索引擎，這些方法已經(jīng)成為現(xiàn)代軟件系統(tǒng)的重要組成部分。隨著計(jì)算機(jī)應(yīng)用的覆蓋面越來(lái)越廣，基本算法的影響也日益顯著。本書(shū)的目標(biāo)是要提供一種資源，使廣大學(xué)生以及專業(yè)人士可以了解并有效利用這些算法解決計(jì)算機(jī)應(yīng)用中出現(xiàn)的問(wèn)題。

內(nèi)容概要

本書(shū)細(xì)膩講解計(jì)算機(jī)算法的C語(yǔ)言實(shí)現(xiàn)。全書(shū)分為四部分，共16章。包括基本算法分析原理，基本數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)結(jié)構(gòu)、遞歸和樹(shù)等數(shù)據(jù)結(jié)構(gòu)知識(shí)，選擇排序、插入排序、冒泡排序、希爾排序、快速排序方法、歸并和歸并排序方法、優(yōu)先隊(duì)列與堆排序方法、基數(shù)排序方法以及特殊用途的排序方法，并比較了各種排序方法的性能特征，在進(jìn)一步講解符號(hào)表、樹(shù)等抽象數(shù)據(jù)類型的基礎(chǔ)上，重點(diǎn)討論散列方法、基數(shù)搜索以及外部搜索方法。書(shū)中提供了用C語(yǔ)言描述的完整算法源程序，并且配有豐富的插圖和練習(xí)，還包含大量簡(jiǎn)潔的實(shí)現(xiàn)將理論和實(shí)踐成功地相結(jié)合，這些實(shí)現(xiàn)均可用在真實(shí)應(yīng)用上。
本書(shū)內(nèi)容豐富，具有很強(qiáng)的實(shí)用價(jià)值，適合作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)本科生算法課程的教材，也是廣大研究人員的極佳參考讀物。

作者簡(jiǎn)介

塞奇威克（Robert Sedgewick），擁有斯坦福大學(xué)博士學(xué)位（導(dǎo)師為donald
E.Knuth），普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授，Adobe Systems公司董事，曾是Xerox
PARC的研究人員，還曾就職于美國(guó)國(guó)防防御分析研究所以及INRIA。除本書(shū)外，他還與Philippe
Flajolet合著了《算法分析導(dǎo)論》

書(shū)籍目錄

出版者的話
譯者序
前言
第一部分　基礎(chǔ)知識(shí)
　第1章　引言
　 1.1　算法
　 1.2　典型問(wèn)題——連通性
　 1.3　合并一查找算法
　 1.4　展望
　 1.5　主題概述
　第2章　算法分析的原理
　　2.1　實(shí)現(xiàn)和經(jīng)驗(yàn)分析
　　2.2　算法分析
　　2.3　函數(shù)的增長(zhǎng)
　　2.4　大O符號(hào)
　　2.5　基本遞歸方程
　　2.6　算法分析示例
　　2.7　保證、預(yù)測(cè)及局限性
第二部分　數(shù)據(jù)結(jié)構(gòu)
　第3章　基本數(shù)據(jù)結(jié)構(gòu)
　 3.1　構(gòu)建組件
　 3.2　數(shù)組
　 3.3　鏈表
　 3.4　鏈表的基本處理操作
　 3.5　鏈表的內(nèi)存分配
　 3.6　字符串
　 3.7　復(fù)合數(shù)據(jù)結(jié)構(gòu)
　第4章　抽象數(shù)據(jù)類型
　 4.1　抽象對(duì)象和對(duì)象集
　 4.2　下推棧ADT
　 4.3　棧ADT客戶示例
　 4.4　棧ADT的實(shí)現(xiàn)
　 4.5　創(chuàng)建一個(gè)新ADT
　 4.6　FIFO隊(duì)列和廣義隊(duì)列
　 4.7　復(fù)制和索引項(xiàng)
　 4.8　一級(jí)ADT
　 4.9　基于應(yīng)用的ADT示例
　 4.10　展望
　第5章　遞歸與樹(shù)
　 5.1　遞歸算法
　 5.2　分治法
　 5.3　動(dòng)態(tài)規(guī)劃
　 5.4　樹(shù)
　 5.5　樹(shù)的數(shù)學(xué)性質(zhì)
　 5.6　樹(shù)的遍歷
　 5.7　遞歸二叉樹(shù)算法
　 5.8　圖的遍歷
　 5.9　綜述
第三部分　排序
　第6章　基本排序方法
　　6.1　游戲規(guī)則
　　6.2　選擇排序
　　6.3　插入排序
　　6.4　冒泡排序
　　6.5　基本排序方法的性能特征
　　6.6　希爾排序
　　6.7　對(duì)其他類型的數(shù)據(jù)進(jìn)行排序
　　6.8　索引和指針排序
　　6.9　鏈表排序
　　6.10　關(guān)鍵字索引統(tǒng)計(jì)
　第7章　快速排序
　 7.1　基本算法
　 7.2　快速排序算法的性能特征
　 7.3　棧大小
　 7.4　小的子文件
　 7.5　三者取中劃分
　 7.6　重復(fù)關(guān)鍵字
　 7.7　字符串和向量
　　……
　第8章　歸并與歸并排序
　第9章　優(yōu)先隊(duì)列和堆排序
　第10章　基數(shù)排序
　第11章　特殊用途的排序方法
第四部分　搜索
　第12章　符號(hào)表和二叉搜索樹(shù)
　第13章　平衡樹(shù)
　第14章　散列
　第15章　基數(shù)搜索
　第16章　外部搜索

章節(jié)摘錄

插圖：還有一個(gè)例子出現(xiàn)在某種程序設(shè)計(jì)環(huán)境中，連通性可用來(lái)斷言兩個(gè)變量名是否等價(jià)。問(wèn)題是在經(jīng)過(guò)這樣的斷言序列之后，能夠確定兩個(gè)給定的名字是否等價(jià)。這個(gè)應(yīng)用激發(fā)了我們打算考慮的幾個(gè)算法的研制。它直接將我們的問(wèn)題與一種簡(jiǎn)單抽象關(guān)聯(lián)起來(lái)，為使算法具有廣泛應(yīng)用而提供了一種方法。我們即將看到這一點(diǎn)。像上一段描述的變量名等價(jià)問(wèn)題這樣的應(yīng)用程序要求我們把每個(gè)不同的變量名與一個(gè)整數(shù)關(guān)聯(lián)起來(lái)。這種關(guān)聯(lián)關(guān)系也隱含在前面描述的網(wǎng)絡(luò)連接和電路連接的應(yīng)用中。在第10章至第16章，我們將會(huì)以一種更高效的方法考慮提供這種連接關(guān)系的大量算法。因此，不失一般性，本章假設(shè)有N個(gè)對(duì)象，每個(gè)都與0一N一1之間的一個(gè)整數(shù)名對(duì)應(yīng)。我們正在尋求完成特定和良定義任務(wù)的程序，可能還想要解決其他許多相關(guān)的問(wèn)題。在研制算法時(shí)我們面對(duì)的首要任務(wù)之一是確信我們已經(jīng)以合理的方式指定了問(wèn)題。我們要求算法的越多，它完成任務(wù)所需要的時(shí)間和空間越多。不可能量化這個(gè)關(guān)系，并且我們?cè)诎l(fā)現(xiàn)一個(gè)問(wèn)題難以求解或是求解代價(jià)昂貴，或是在好的情況下，發(fā)現(xiàn)算法可以比原始說(shuō)明提供更多有用的信息時(shí)，我們常常修改這個(gè)問(wèn)題的說(shuō)明。例如，我們的連通問(wèn)題的說(shuō)明只要求我們的程序知道任意給定對(duì)p—q是否是連通的，并不能夠表明連接那個(gè)對(duì)的任何方式。添加這樣一個(gè)說(shuō)明的要求會(huì)使問(wèn)題更加困難，會(huì)涉及其他的算法，我們將在第5章簡(jiǎn)略討論，并在第7章詳細(xì)討論。前面這段提到的說(shuō)明要比原始說(shuō)明要求更多的信息，我們也可以要求更少的信息。例如，我們可能只想回答這樣的問(wèn)題：“M個(gè)連接足以把Ⅳ個(gè)對(duì)象都連接起來(lái)嗎？”這個(gè)問(wèn)題表明，要研制一個(gè)高效的算法，常常需要我們對(duì)正在處理的抽象對(duì)象進(jìn)行高級(jí)推理。在這種情況下，由圖論基本結(jié)果可以得出所有Ⅳ個(gè)對(duì)象是連通的，當(dāng)且僅當(dāng)連通算法輸出的對(duì)的個(gè)數(shù)恰好為N一1（見(jiàn)5．4節(jié)）。換句話說(shuō)，連通算法永遠(yuǎn)不會(huì)輸出多于N一1個(gè)對(duì)，這是因?yàn)橐坏┧敵鯪一1個(gè)對(duì)，則它從那個(gè)時(shí)刻遇見(jiàn)的任何對(duì)將會(huì)是連通的。因此，我們可以修改求解連通問(wèn)題的程序，增加一個(gè)計(jì)數(shù)器就可以得到一個(gè)回答yes-no問(wèn)題的程序，而不輸出那些前面不連通的每個(gè)對(duì)，當(dāng)計(jì)數(shù)器的值為N-1時(shí)，程序回答“yes”，否則回答“no”。這個(gè)問(wèn)題只是我們希望回答關(guān)于連通性的許多問(wèn)題中的一個(gè)例子。輸入對(duì)的集合稱為圖（graph），輸出對(duì)的集合稱為圖的生成樹(shù)，它連接了所有對(duì)象。我們?cè)诘谄卟糠挚疾靾D、生成樹(shù)以及所有相關(guān)算法的性質(zhì)。

媒體關(guān)注與評(píng)論

對(duì)于在數(shù)學(xué)分析方面不算熟練且需要留意理論算法的普通程序員來(lái)說(shuō)，本書(shū)是一本可讀性很強(qiáng)的優(yōu)秀讀本。他們應(yīng)該會(huì)從中獲益良多。　　——Steve Summit，《C Programming FAQs》的作者Sedgewick有一種真正的天賦，可以用易于理解的方式來(lái)解釋概念。書(shū)中采用了一些易懂的實(shí)戰(zhàn)程序，其篇幅僅有一頁(yè)左右，這更是錦上添花。而書(shū)中大量采用的圖、程序、表格也會(huì)極大幫助讀者的學(xué)習(xí)和理解，這使本書(shū)更顯得與眾不同。　　——William A. Ward，南亞拉巴馬大學(xué)

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法：C語(yǔ)言實(shí)現(xiàn) PDF格式下載

---