本書是為全國高等院校計算機及相關(guān)專業(yè)開設(shè)數(shù)據(jù)結(jié)構(gòu)課程而精心組織和編著的一本實用教材。它從1999年出版以來，一直深受廣大讀者和專家的好評，相繼被許多高校選定為教科書和考研參考書，并被列選為國家級“十一五”規(guī)劃教材。這次對本書進(jìn)行了認(rèn)真和全面的修訂，形成第2版，相信會得到更廣泛的認(rèn)可，對數(shù)據(jù)結(jié)構(gòu)學(xué)科的教學(xué)和發(fā)展產(chǎn)生積極的影響。
本書從計算機學(xué)科發(fā)展和應(yīng)用的實際需要出發(fā)，對各種常用的數(shù)據(jù)結(jié)構(gòu)，從邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算種類、運算方法和算法等各個方面進(jìn)行了深入細(xì)致的解剖和分析，使讀者更容易理解基本概念和知識，能夠輕松地進(jìn)行算法設(shè)計和上機操作的訓(xùn)練，大大提高軟件開發(fā)與設(shè)計的專業(yè)能力。
另外，與本書配套的習(xí)題參考解答也一并被修訂和出版，為廣大自學(xué)讀者提供方便。

序 言
時光更迭、歷史嬗遞。中國經(jīng)濟以她足以令世人驚嘆的持續(xù)高速發(fā)展駛?cè)肓艘粋�新的世紀(jì)，一個新的千年。世紀(jì)之初，以微電子、計算機、軟件和通信技術(shù)為主導(dǎo)的信息技術(shù)革命給我們生存的社會所帶來的變化令人目不暇接。軟件是優(yōu)化我國產(chǎn)業(yè)結(jié)構(gòu)、加速傳統(tǒng)產(chǎn)業(yè)改造和用信息化帶動工業(yè)化的基礎(chǔ)產(chǎn)業(yè)，是體現(xiàn)國家競爭力的戰(zhàn)略性產(chǎn)業(yè)，是從事知識的提煉、總結(jié)、深化和應(yīng)用的高智型產(chǎn)業(yè)；軟件關(guān)系到國家的安全，是保證我國政治獨立、文化不受侵蝕的重要因素；軟件也是促進(jìn)其他學(xué)科發(fā)展和提升的基礎(chǔ)學(xué)科；軟件作為20世紀(jì)人類文明進(jìn)步的最偉大成果之一，代表了先進(jìn)文化的前進(jìn)方向。美國政府早在1992年“國家關(guān)鍵技術(shù)”一文中提出“美國在軟件開發(fā)和應(yīng)用上所處的傳統(tǒng)領(lǐng)先地位是信息技術(shù)及其他重要領(lǐng)域競爭能力的一個關(guān)鍵因素”，“一個成熟的軟件制造工業(yè)的發(fā)展是滿足商業(yè)與國防對復(fù)雜程序日益增長的要求所必需的”，“在很多國家關(guān)鍵技術(shù)中，軟件是關(guān)鍵的、起推動作用（或阻礙作用）的因素”。在1999年1月美國總統(tǒng)信息技術(shù)顧問委員會的報告“21世紀(jì)的信息技術(shù)”中指出“從臺式計算機、電話系統(tǒng)到股市，我們的經(jīng)濟與社會越來越依賴于軟件”，“軟件研究為基礎(chǔ)研究方面最優(yōu)先發(fā)展的領(lǐng)域�！倍�軟件人才的缺乏和激烈競爭是當(dāng)前國際的共性問題。各國、各企業(yè)都對培養(yǎng)、引進(jìn)軟件人才采取了特殊政策與措施。
為了滿足社會對軟件人才的需要，為了讓更多的人可以更快地學(xué)到實用的軟件理論、技術(shù)與方法，我們編著了《普通高等院校計算機專業(yè)（本科）實用教程系列》。本套叢書面向普通高等院校學(xué)生，以培養(yǎng)面向21世紀(jì)計算機專業(yè)應(yīng)用人才（以軟件工程師為主）為 目標(biāo)，以簡明實用、便于自學(xué)、反映計算機技術(shù)最新發(fā)展和應(yīng)用為特色，具體歸納為以下幾點：
1．進(jìn)透基本理論、基本原理、方法和技術(shù)，在寫法上力求敘述詳細(xì)，算法具體，通俗易懂，便于自學(xué)。
2．理論結(jié)合實際。計算機是一門實踐性很強的科學(xué)，叢書貫徹從實踐中來到實踐中去的原則，許多技術(shù)理論結(jié)合實例講解，以便于學(xué)習(xí)理解。
3．本叢書形成完整的體系，每本教材既有相對獨立性，又有相互銜接和呼應(yīng)，為總的培養(yǎng)目標(biāo)服務(wù)。
4．每本教材都配以習(xí)題和實驗，在各教學(xué)階段安排課程設(shè)計或大作業(yè)，培養(yǎng)學(xué)生的實戰(zhàn)能力與創(chuàng)新精神。習(xí)題和實驗可以制作成光盤。
為了適應(yīng)計算機科學(xué)技術(shù)的發(fā)展，本系列教材將本著與時俱進(jìn)的精神不斷修訂更新，及時推出第二版、第三版……
新世紀(jì)曙光激人向上，催人奮進(jìn)。江澤民同志在十五屆五中全會上的講話：“大力推進(jìn)國民經(jīng)濟和社會信息化，是覆蓋現(xiàn)代化建設(shè)全局的戰(zhàn)略舉措。以信息化帶動工業(yè)化，發(fā)揮后發(fā)優(yōu)勢，實現(xiàn)社會生產(chǎn)力的跨越式發(fā)展”，指明了我國信息界前進(jìn)的方向。21世紀(jì)日趨開放的國策與更加迅速發(fā)展的科技會托起祖國更加輝煌燦爛的明天。

孫家廣
2004年1月
第二版前言
本書第一版出版至今已近7年，隨著計算機數(shù)據(jù)結(jié)構(gòu)學(xué)科的不斷發(fā)展和教學(xué)的改革需要，在第一版的基礎(chǔ)上，整理和加工形成了第二版。
第一版教材深受讀者的喜愛，連續(xù)14次印刷，發(fā)行7萬余冊，被許多高校選定為教材和考研參考書。有許多讀者在網(wǎng)站上發(fā)表評論，贊揚本書的風(fēng)格和特色。
第二版對第一版的內(nèi)容進(jìn)行了優(yōu)化和適當(dāng)增刪，并對一些章節(jié)進(jìn)行了調(diào)整，由第1版中的8章修訂為10章。原來的第5章“樹”，改為第5章的“樹和二叉樹”和第6章的“特殊二叉樹”兩章，原來的第6章“圖”，改為第7章“圖”和第8章“圖的應(yīng)用”兩章。
在第二版教材中，增加了“堆”結(jié)構(gòu)的內(nèi)容、集合結(jié)構(gòu)的內(nèi)容、線性表應(yīng)用的內(nèi)容、棧與隊列應(yīng)用的內(nèi)容等；擴充了棧與遞歸應(yīng)用的實例、二叉樹和樹查找運算的算法、生成哈夫曼樹的算法、對B_樹的插入算法等；修改了從二叉搜索樹中刪除結(jié)點的算法、對外存文件進(jìn)行排序的算法等。當(dāng)然還對許多內(nèi)容進(jìn)行了修改，力爭反映該學(xué)科的先進(jìn)性和科學(xué)性，反映作為教材的系統(tǒng)性、實用性和可讀性。
第2版的內(nèi)容較豐富，在目錄、例題或習(xí)題中帶星號“*”的內(nèi)容可以不作為講授內(nèi)容和教學(xué)要求，留給學(xué)生自學(xué)。
書中所有算法和程序都在Visual C++ 6.0開發(fā)環(huán)境下調(diào)試運行通過，使得其正確性和有效性得到了進(jìn)一步驗證。
數(shù)據(jù)結(jié)構(gòu)教材的內(nèi)容包括兩個層面：邏輯層面和實現(xiàn)層面。在邏輯層面上，介紹的是各種數(shù)據(jù)結(jié)構(gòu)的特點，在每種數(shù)據(jù)結(jié)構(gòu)上進(jìn)行插入、刪除、查找、遍歷等相應(yīng)運算的方 法，不涉及在計算機上實現(xiàn)運算的算法；在實現(xiàn)層面上，討論的是如何把對數(shù)據(jù)結(jié)構(gòu)進(jìn)行運算的方法和步驟轉(zhuǎn)換為用一種計算機程序設(shè)計語言描述的算法，并能夠?qū)嶋H運行和得到驗證。邏輯層面的學(xué)習(xí)是基本的和必需的，實現(xiàn)層面的學(xué)習(xí)是進(jìn)一步的，對于計算機及信息類專業(yè)的學(xué)生，這兩步都要學(xué)，而且都要學(xué)好，對于經(jīng)管農(nóng)林等類的學(xué)生，則應(yīng)側(cè)重 第1步。
數(shù)據(jù)結(jié)構(gòu)課程是一門理論性和實踐性都很強的課程，只有通過親自編寫算法、上機運行和調(diào)試程序，才能夠加深理解和掌握所學(xué)的知識，提高程序設(shè)計和軟件研發(fā)能力。
使用此教材，最好具有C++語言的基礎(chǔ)，因為書中描述的數(shù)據(jù)類型和算法都是按照C++語言的規(guī)則編寫的。當(dāng)然，若是只具有其他計算機語言的基礎(chǔ)，則使用該書時應(yīng)同時自學(xué)C++語言。對于一般讀者來說，只要有任一種計算機語言的基礎(chǔ)，再自學(xué)任何其他計算機語言都是不困難的。
與本書配套的《數(shù)據(jù)結(jié)構(gòu)實用教程習(xí)題參考解答》也同時改版，將同此主教材一并出版發(fā)行。與本書配套的《數(shù)據(jù)結(jié)構(gòu)課程實驗》一書暫時不需改版，仍可繼續(xù)與這本第二版主教材配套使用。
在由清華大學(xué)出版社組織的此套系列教材中，本人還編著了《C++語言基礎(chǔ)教程》一書，該書已重印十多次，便于自學(xué)，讀者反映較好，并被列選為國家“十一五”規(guī)劃教材，不妨推薦給讀者參考。
衷心希望通過這次改版，使《數(shù)據(jù)結(jié)構(gòu)實用教程》一書更加受到讀者的愛戴和好評，也同時希望讀者繼續(xù)給予批評指正，本人深表謝意！
作者電子郵箱：xuxk@crtvu.edu.cn，聯(lián)系電話：010-64910302。


徐孝凱
2006年8月


第一版前言
數(shù)據(jù)結(jié)構(gòu)是普通高校計算機專業(yè)和信息管理專業(yè)一門必修的核心課程。它的主要任務(wù)是討論現(xiàn)實世界中數(shù)據(jù)（即事物的抽象描述）的各種邏輯結(jié)構(gòu)、在計算機中的存儲結(jié)構(gòu)以及進(jìn)行各種非數(shù)值運算的算法，目的是使學(xué)生掌握數(shù)據(jù)組織、存儲和處理的常用方法，為以后進(jìn)行軟件開發(fā)和學(xué)習(xí)后續(xù)專業(yè)課程打下基礎(chǔ)。
數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)4種。數(shù)據(jù)的存儲結(jié)構(gòu)分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)4種。對數(shù)據(jù)進(jìn)行的非數(shù)值運算主要包括插
入、刪除、查找、排序、輸入和輸出等。需要特別指出：數(shù)據(jù)的存儲結(jié)構(gòu)既適用于內(nèi)存，
也適用于外存，不僅要學(xué)會對內(nèi)存數(shù)據(jù)操作的算法，而且要學(xué)會對外存數(shù)據(jù)（文件）操作的算法，這樣才能夠解決實際軟件開發(fā)的問題，達(dá)到學(xué)以致用的目的。
在已經(jīng)出版的眾多數(shù)據(jù)結(jié)構(gòu)教材中，對每一種數(shù)據(jù)結(jié)構(gòu)類型進(jìn)行相應(yīng)運算的算法描述通常是粗略的，離真正用一種計算機語言上機實現(xiàn)還有相當(dāng)?shù)木嚯x，特別在外存文件的操作上更是如此。本套教材在這方面做了徹底的改變，所給出的每一算法都利用C/C++語言給出了具體的實現(xiàn)，算法的正確性和有效性得到了實際的檢驗，這樣就突出了實用性，使教材更便于教學(xué)，特別是自學(xué)，克服了以往同類教材只重視理論而輕視算法具體實現(xiàn)的 缺陷。
本套教材包含3本，第一本為主教材《數(shù)據(jù)結(jié)構(gòu)實用教程》，第二本為實驗教材《數(shù)據(jù)結(jié)構(gòu)課程實驗》，第三本為輔助教材《數(shù)據(jù)結(jié)構(gòu)實用教程習(xí)題參考解答》。主教材共分為8章，依次為緒論、線性表、稀疏矩陣和廣義表、棧和隊列、樹、圖、查找和排序。在第1章的緒論中，1.2節(jié)為算法描述，對于C++語言比較熟悉的教學(xué)班和讀者，此內(nèi)容可作為自學(xué)閱讀內(nèi)容。主教材沒有專門給出文件一章，這是因為，可把文件（這里只討論磁盤文件）看作存儲在外存上的數(shù)組，通過文件流操作函數(shù)既可順序存取文件內(nèi)容，也可隨機存取文件中任何位置上的信息塊，如何使用文件已經(jīng)在C/C++語言中學(xué)習(xí)過，在數(shù)據(jù)結(jié)構(gòu)課程中只是應(yīng)用問題，所以不必單列一章介紹。實驗教材給出了10個數(shù)據(jù)結(jié)構(gòu)應(yīng)用的典型例題，并給出了相應(yīng)的參考程序。輔助教材給出了主教材中每章習(xí)題的大部分參考解答，最后附加了兩個綜合題，它們是針對不同文件的插入、刪除和查找操作的，目的是培養(yǎng)學(xué)生對所學(xué)知識的實際應(yīng)用能力。
本人一直從事數(shù)據(jù)結(jié)構(gòu)的教學(xué)和研究工作，編著過多本教材，清華大學(xué)出版社已經(jīng)出版的《數(shù)據(jù)結(jié)構(gòu)簡明教程》一書就是其代表作�，F(xiàn)在這套教材是本人多年教學(xué)經(jīng)驗的結(jié)晶，是對以往教材的繼承、豐富和發(fā)展，希望能夠?qū)��?shù)據(jù)結(jié)構(gòu)課程的教學(xué)起到良好的作用，使讀者能夠得到滿意的收獲。
本套教材是根據(jù)計算機專業(yè)和信息管理專業(yè)本科培養(yǎng)目標(biāo)，對數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的要求編寫的。由于內(nèi)容敘述細(xì)致，算法描述具體，便于自學(xué)，所以刪除部分內(nèi)容后可作為相應(yīng)�？茖W(xué)生的教材。具體如何刪減，應(yīng)由辦學(xué)單位和任課教師定奪。
學(xué)習(xí)本套教材應(yīng)具有C語言或C++語言的基礎(chǔ)。若只學(xué)習(xí)過C語言，則應(yīng)在學(xué)習(xí)本課程的過程中補充C++語言的輸入/輸出操作、文件流操作、運算符重載等有關(guān)內(nèi)容。
本課程總學(xué)時應(yīng)安排在80～100學(xué)時之間，其中講授與上機學(xué)時之比應(yīng)為2∶1左右，有條件的學(xué)生要盡量多上機。
承蒙北京大學(xué)計算機系許卓群教授和北京石油大學(xué)計算機系陳明教授認(rèn)真審閱了本套教材的全部書稿，提出了寶貴的意見，在此謹(jǐn)向他們表示衷心感謝。
盡管本人做了很大的努力，但由于水平有限，加之時間倉促，錯誤和不足之處在所難免，敬請授課教師和廣大讀者批評指正。
電子郵箱地址：xuxk@crtvu.edu.cn，聯(lián)系電話：010-64910302。

徐孝凱
1999年10月

目 錄
第1章 緒論1
1.1 常用術(shù)語1
1.2 算法描述11
1.3 算法評價13
*1.4 與算法描述有關(guān)的C++知識19
1.4.1 包含文件語句20
1.4.2 數(shù)據(jù)類型28
1.4.3 函數(shù)36
1.4.4 運算符重載41
習(xí)題143
第2章 線性表48
2.1 線性表的定義和抽象數(shù)據(jù)類型48
2.1.1 線性表的定義48
2.1.2 線性表的抽象數(shù)據(jù)類型49
2.1.3 操作舉例50
2.2 線性表的順序存儲和操作實現(xiàn)51
2.2.1 線性表的順序存儲結(jié)構(gòu)51
2.2.2 順序存儲下的線性表操作的實現(xiàn)53
*2.3 線性表應(yīng)用舉例62
2.4 線性表的鏈接存儲結(jié)構(gòu)67
2.5 線性表操作在單鏈表上的實現(xiàn)75
*2.6 多項式計算83
2.6.1 多項式表示與求值83
2.6.2 兩個多項式相加88
習(xí)題291
第3章 集合、稀疏矩陣和廣義表94
3.1 集合的定義和抽象數(shù)據(jù)類型94
3.1.1 集合定義94
3.1.2 集合的抽象數(shù)據(jù)類型94
3.2 集合的順序存儲結(jié)構(gòu)和操作實現(xiàn)95
3.3 集合的鏈接存儲結(jié)構(gòu)和操作實現(xiàn)102
3.4 稀疏矩陣108
3.4.1 稀疏矩陣的定義108
3.4.2 稀疏矩陣的存儲結(jié)構(gòu)110
*3.4.3 稀疏矩陣的運算113
3.5 廣義表120
3.5.1 廣義表的定義120
3.5.2 廣義表的存儲結(jié)構(gòu)122
3.5.3 廣義表的運算123
3.5.4 簡單程序舉例127
習(xí)題3128
第4章 棧和隊列131
4.1 棧131
4.1.1 棧的定義131
4.1.2 棧的抽象數(shù)據(jù)類型131
4.2 棧的順序存儲結(jié)構(gòu)和操作實現(xiàn)132
4.3 棧的鏈接存儲結(jié)構(gòu)和操作實現(xiàn)136
4.4 棧的簡單應(yīng)用舉例138
4.5 算術(shù)表達(dá)式的計算142
4.5.1 算術(shù)表達(dá)式的兩種表示142
4.5.2 后綴表達(dá)式求值的算法144
4.5.3 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法146
4.6 棧與遞歸150
4.7 隊列160
4.7.1 隊列的定義160
4.7.2 隊列的抽象數(shù)據(jù)類型161
4.7.3 隊列的順序存儲結(jié)構(gòu)和操作實現(xiàn)162
4.7.4 隊列的鏈接存儲結(jié)構(gòu)和操作實現(xiàn)165
*4.8 隊列應(yīng)用舉例169
習(xí)題4173
第5章 樹178
5.1 樹的概念178
5.1.1 樹的定義178
5.1.2 樹的表示180
5.1.3 樹的基本術(shù)語181
5.1.4 樹的性質(zhì)182
5.2 二叉樹183
5.2.1 二叉樹的定義183
5.2.2 二叉樹的性質(zhì)184
5.2.3 二叉樹的抽象數(shù)據(jù)類型186
5.2.4 二叉樹的存儲結(jié)構(gòu)187
5.3 二叉樹遍歷189
5.4 二叉樹其他運算193
5.5 樹的存儲結(jié)構(gòu)和運算198
5.5.1 樹的抽象數(shù)據(jù)類型198
5.5.2 樹的存儲結(jié)構(gòu)199
5.5.3 樹的運算201
習(xí)題5207
第6章 特殊二叉樹212
6.1 二叉搜索樹212
6.1.1 二叉搜索樹的定義212
6.1.2 二叉搜索樹的抽象數(shù)據(jù)類型212
6.1.3 二叉搜索樹的運算213
6.2 堆220
6.2.1 堆的定義220
6.2.2 堆的抽象數(shù)據(jù)類型221
6.2.3 堆的存儲結(jié)構(gòu)221
6.2.4 堆的運算222
6.3 哈夫曼樹227
6.3.1 基本術(shù)語227
6.3.2 構(gòu)造哈夫曼樹228
*6.3.3 哈夫曼編碼231
*6.4 線索二叉樹234
6.4.1 二叉樹的線索化234
6.4.2 利用線索進(jìn)行遍歷238
*6.5 平衡二叉樹241
6.5.1 平衡二叉樹的定義241
6.5.2 平衡二叉樹的調(diào)整242
習(xí)題6247
第7章 圖249
7.1 圖的概念249
7.1.1 圖的定義249
7.1.2 圖的基本術(shù)語250
7.1.3 圖的抽象數(shù)據(jù)類型253
7.2 圖的存儲結(jié)構(gòu)254
7.2.1 鄰接矩陣254
7.2.2 鄰接表257
7.2.3 邊集數(shù)組262
7.3 圖的遍歷264
7.3.1 深度優(yōu)先搜索遍歷264
7.3.2 廣度優(yōu)先搜索遍歷267
7.3.3 非連通圖的遍歷269
習(xí)題7271
第8章 圖的應(yīng)用273
8.1 圖的生成樹和最小生成樹273
8.1.1 生成樹和最小生成樹的概念273
8.1.2 普里姆算法275
8.1.3 克魯斯卡爾算法278
8.2 最短路徑281
8.2.1 最短路徑的概念281
8.2.2 從一頂點到其余各頂點的最短路徑282
*8.2.3 每對頂點之間的最短路徑286
8.3 拓?fù)渑判?90
8.3.1 拓?fù)渑判虻母拍?90
8.3.2 拓?fù)渑判蛩惴?93
*8.4 關(guān)鍵路徑296
8.4.1 頂點事件的發(fā)生時間296
8.4.2 計算關(guān)鍵路徑的方法和算法299
習(xí)題8302
第9章 查找305
9.1 查找的概念305
9.2 順序表查找306
9.2.1 順序查找306
9.2.2 二分查找307
9.3 索引查找311
9.3.1 索引的概念311
9.3.2 索引查找算法314
*9.3.3 分塊查找316
9.4 散列查找317
9.4.1 散列的概念317
9.4.2 散列函數(shù)319
9.4.3 處理沖突的方法321
9.4.4 散列表的運算324
9.5 B樹查找328
9.5.1 B_樹定義328
9.5.2 B_樹查找330
9.5.3 B_樹插入332
9.5.4 B_樹刪除335
*9.5.5 對B_樹的其他運算337
*9.5.6 B+樹簡介340
習(xí)題9341
第10章 排序343
10.1 排序的基本概念343
10.2 插入排序344
10.2.1 直接插入排序345
*10.2.2 希爾排序346
10.3 選擇排序347
10.3.1 直接選擇排序347
10.3.2 堆排序348
10.4 交換排序352
10.4.1 氣泡排序352
10.4.2 快速排序354
10.5 歸并排序357
*10.6 各種內(nèi)排序方法的比較360
*10.7 外排序362
10.7.1 外排序的概念362
10.7.2 外排序算法364
習(xí)題10371