本書主要講述了各種基本數(shù)據(jù)結(jié)構(gòu)的概念, 包括數(shù)據(jù)結(jié)構(gòu)的邏輯定義、物理實現(xiàn)及其相應(yīng)運算, 并運用大量經(jīng)典的算法舉例說明怎樣用這些抽象的概念來解決實際問題。全書共分9章, 分為: 緒論，線性表和串，堆棧和隊列，樹和二叉樹，圖，數(shù)組、矩陣和廣義表，排序，查找，文件。
本書是作者在三十多年數(shù)據(jù)結(jié)構(gòu)教學(xué)經(jīng)驗總結(jié)的基礎(chǔ)上編寫而成。全書共分為9章，內(nèi)容涵蓋數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表和串、棧和隊列、樹和二叉樹、圖、數(shù)組和矩陣、排序、查找、文件。
本書采用C++程序設(shè)計語言對算法進行描述。本書不僅介紹了數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，而運用大量的實際案例充實教材的內(nèi)容，力求既有理論深度，又有實用價值。在書中的附錄A中還給出了數(shù)據(jù)結(jié)構(gòu)課程實踐中，如采用VC++6.0作為軟件環(huán)境時，VC++系統(tǒng)實用操作的簡介。另外在附錄B中給出了本課程學(xué)習(xí)中應(yīng)該完成的基本實驗要求，在每章的后面都附有相關(guān)的習(xí)題和部分習(xí)題答案。
本書是按高等院校計算機專業(yè)及信息管理專業(yè)本科四年制教學(xué)計劃“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)大綱要求編寫的教材，還可以作為計算機科技工作者及其相關(guān)專業(yè)人員的參考書。在學(xué)習(xí)本書知識前，要求讀者具備C++程序設(shè)計的知識。
“數(shù)據(jù)結(jié)構(gòu)”已成為一門比較成熟的課程。它是計算機系統(tǒng)軟件和應(yīng)用軟件研制者的必修課程。數(shù)據(jù)結(jié)構(gòu)和算法是計算機基礎(chǔ)性研究內(nèi)容之一，掌握這個領(lǐng)域的知識對于利用計算機資源高效地開發(fā)計算機程序是非常必要的。
數(shù)據(jù)結(jié)構(gòu)理論的應(yīng)用范圍已經(jīng)深入到編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫、人工智能、信息科學(xué)、系統(tǒng)工程、計算機輔助設(shè)計及信息管理領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要解決非數(shù)值計算應(yīng)用問題。
從理論上講：數(shù)據(jù)結(jié)構(gòu)的概念嚴謹、抽象；每種數(shù)據(jù)結(jié)構(gòu)類型描述層次清晰可見——概念層、邏輯定義層、物理存儲層、運算實現(xiàn)層；每種數(shù)據(jù)結(jié)構(gòu)類型描述反映了實現(xiàn)問題的思想、實現(xiàn)的前提以及不同實現(xiàn)方式的特點和優(yōu)劣。
數(shù)據(jù)結(jié)構(gòu)描述的內(nèi)容看上去如同程序，但不是程序，它是程序設(shè)計思想的抽象化、一般化，它不依賴于某種物理設(shè)備甚至某種語言系統(tǒng)，學(xué)習(xí)者通過“數(shù)據(jù)結(jié)構(gòu)”課程不僅能獲得專業(yè)知識，而且能學(xué)到一種思維方式。
從實踐上講，數(shù)據(jù)結(jié)構(gòu)是建立在抽象化描述基礎(chǔ)之上的實踐性理論，這門學(xué)科只有賦予實踐的內(nèi)容才具有完備性，具體化是該學(xué)科的又一特點。在計算機系統(tǒng)中全面體現(xiàn)著數(shù)據(jù)結(jié)構(gòu)的作用，系統(tǒng)框架結(jié)構(gòu)的構(gòu)建、程序?qū)崿F(xiàn)的精巧化都融入了數(shù)據(jù)結(jié)構(gòu)的理論思想和技術(shù)。
本書敘述了各種基本數(shù)據(jù)結(jié)構(gòu)的概念，包括數(shù)據(jù)結(jié)構(gòu)的邏輯定義、物理實現(xiàn)及其相應(yīng)運算，并舉例說明怎樣用這些抽象的概念來解決實際問題。通過本書的學(xué)習(xí)不僅能正確地掌握數(shù)據(jù)結(jié)構(gòu)的基本理論，并能運用這些理論來解決實際問題。
本書是編者集多年從事計算機軟件設(shè)計實踐及講授“數(shù)據(jù)結(jié)構(gòu)”課程的體會，并參考分析了國內(nèi)外數(shù)據(jù)結(jié)構(gòu)書籍文獻編寫而成的。本書采用廣泛使用的C++語言描述算法，并進行了適當?shù)乃惴◤?fù)雜性分析。
“數(shù)據(jù)結(jié)構(gòu)”課程不但理論性很強，同時實踐性也很強。本書在每一章的最后都安排了適量的習(xí)題，供讀者練習(xí)。
本書共分9章，介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念及線性表和串、棧和隊列、樹和二叉樹、圖、數(shù)組和矩陣、排序、查找、文件的數(shù)據(jù)結(jié)構(gòu)、算法及其應(yīng)用案例。
本書由王少波、張志編著。王少波負責(zé)編寫第1、2、3、4、7章及附錄，張志負責(zé)編寫第5、6、8、9章，全書由王少波負責(zé)統(tǒng)稿。
在成書過程中，編者參考了有關(guān)書籍，在此向這些書籍的作者表示感謝。
由于編者水平有限，書中可能存在不妥與疏漏之處，懇請讀者不吝指教。
編者
2017年6月
第1章緒論
1.1什么是數(shù)據(jù)結(jié)構(gòu)
1.1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)事例
1.1.2數(shù)據(jù)結(jié)構(gòu)的定義
1.2數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念
1.2.1數(shù)據(jù)和信息
1.2.2數(shù)據(jù)元素
1.2.3結(jié)構(gòu)類型
1.2.4靜態(tài)存儲空間分配回收和動態(tài)存儲空間分配回收
1.3數(shù)據(jù)類型、抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)
1.3.1類和數(shù)據(jù)類型
1.3.2抽象數(shù)據(jù)類型
1.3.3數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.4算法及算法分析、算法描述
1.4.1算法和程序
1.4.2程序性能和算法效率
1.4.3算法分析
1.4.4算法描述
習(xí)題1
第2章線性表和串
2.1線性表的定義
2.1.1線性表的邏輯結(jié)構(gòu)
2.1.2線性表的抽象數(shù)據(jù)類型
2.2線性表的順序存儲及操作
2.2.1線性表順序存儲
2.2.2線性表順序存儲結(jié)構(gòu)下的操作實現(xiàn)
2.3簡單鏈表存儲結(jié)構(gòu)及操作
2.3.1簡單鏈表的存儲
2.3.2簡單鏈表的操作實現(xiàn)
2.4雙向鏈表
2.4.1雙向鏈表的存儲
2.4.2雙向鏈表類定義
2.4.3雙向鏈表的操作
2.5單向循環(huán)鏈表和雙向循環(huán)鏈表
2.5.1單向循環(huán)鏈表的存儲
2.5.2雙向循環(huán)鏈表的存儲
2.6模擬指針方式構(gòu)造簡單鏈表
2.6.1模擬鏈表的存儲空間的構(gòu)建
2.6.2在模擬鏈表空間上構(gòu)建簡單鏈表
2.7多重鏈表
2.8鏈表應(yīng)用
2.8.1結(jié)點移至表首運算
2.8.2鏈表的逆向運算
2.8.3多項式的相加運算
2.8.4十字鏈表結(jié)構(gòu)的應(yīng)用
2.8.5一個較復(fù)雜的機票售票系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)方案
2.9串
2.9.1串的定義
2.9.2串的邏輯結(jié)構(gòu)及運算
2.9.3串的順序存儲結(jié)構(gòu)
2.9.4串的鏈式存儲結(jié)構(gòu)
2.10線性表基本算法的程序?qū)崿F(xiàn)
2.10.1順序存儲結(jié)構(gòu)線性表程序?qū)崿F(xiàn)
2.10.2帶表頭結(jié)點的簡單鏈表程序?qū)崿F(xiàn)
習(xí)題2
第3章堆棧和隊列
3.1堆棧的定義
3.1.1堆棧的邏輯結(jié)構(gòu)
3.1.2堆棧的抽象數(shù)據(jù)類型
3.2堆棧的順序存儲及操作
3.2.1堆棧順序存儲
3.2.2順序存儲結(jié)構(gòu)堆棧的運算實現(xiàn)
3.3堆棧的鏈式存儲及操作
3.3.1堆棧的鏈式存儲
3.3.2鏈式棧類的定義
3.3.3鏈式棧類運算的實現(xiàn)
3.4多個棧共享鄰接空間
3.5堆棧的應(yīng)用
3.5.1檢驗表達式中括號的匹配
3.5.2表達式的求值
3.5.3背包問題求解
3.5.4地圖四染色問題求解
3.6隊列的定義
3.6.1隊列的邏輯結(jié)構(gòu)
3.6.2隊列的抽象數(shù)據(jù)類型
3.7隊列的順序存儲及操作
3.7.1隊列的順序存儲
3.7.2順序存儲結(jié)構(gòu)下隊列的運算實現(xiàn)
3.8隊列的鏈式存儲及操作
3.8.1隊列的鏈式存儲
3.8.2鏈式隊列模板類的定義
3.8.3鏈式隊列的操作
3.9隊列的應(yīng)用
3.9.1列車重排
3.9.2投資組合問題
3.10堆棧和隊列基本算法的程序?qū)崿F(xiàn)
3.10.1堆棧順序存儲結(jié)構(gòu)程序?qū)崿F(xiàn)
3.10.2隊列順序存儲結(jié)構(gòu)程序?qū)崿F(xiàn)
習(xí)題3
第4章樹和二叉樹
4.1樹、森林的概念
4.1.1樹的定義
4.1.2樹的術(shù)語
4.2二叉樹定義及性質(zhì)
4.2.1二叉樹的定義
4.2.2二叉樹的性質(zhì)
4.2.3二叉樹的抽象數(shù)據(jù)類型
4.3二叉樹的存儲結(jié)構(gòu)
4.3.1二叉樹的順序存儲
4.3.2二叉樹的鏈式存儲
4.4二叉樹鏈式存儲結(jié)構(gòu)下的操作
4.4.1二叉樹的操作概念
4.4.2二叉樹的前序、中序、后序遍歷操作
4.4.3二叉樹的層次遍歷運算
4.5線索樹
4.5.1線索樹的概念
4.5.2二叉線索樹的操作
4.6一般樹的表示和遍歷
4.6.1一般樹的二叉鏈表示及其與二叉樹的關(guān)系
4.6.2二叉樹、一般樹及森林的關(guān)系
4.6.3一般樹的遍歷概念
4.6.4一般樹的運算
4.7樹的應(yīng)用
4.7.1分類二叉樹
4.7.2堆樹
4.7.3樹的路徑長度和赫夫曼樹
4.8二叉樹基本算法的程序?qū)崿F(xiàn)
習(xí)題4
第5章圖
5.1圖的概念
5.1.1圖的定義
5.1.2圖的術(shù)語
5.1.3圖的抽象數(shù)據(jù)類型
5.2圖的存儲結(jié)構(gòu)
5.2.1鄰接矩陣表示法
5.2.2鄰接表表示法
5.2.3十字鏈表
5.2.4鄰接多重表
5.3圖的遍歷
5.3.1深度優(yōu)先搜索遍歷
5.3.2寬度優(yōu)先搜索遍歷
5.3.3圖的連通性
5.4最小生成樹
5.4.1生成樹
5.4.2最小代價生成樹
5.5最短路徑
5.5.1單源最短路徑
5.5.2任意兩個頂點之間的路徑
5.6拓撲排序
5.6.1有向無環(huán)圖
5.6.2AOV網(wǎng)的概念
5.6.3AOV網(wǎng)的算法
5.7關(guān)鍵路徑
5.7.1AOE的概念
5.7.2關(guān)鍵路徑的概念
5.7.3關(guān)鍵路徑的算法
習(xí)題5
第6章數(shù)組、矩陣和廣義表
6.1數(shù)組的定義
6.1.1數(shù)組的邏輯結(jié)構(gòu)
6.1.2數(shù)組的抽象數(shù)據(jù)類型
6.2數(shù)組的順序表示及運算
6.2.1數(shù)組的順序存儲結(jié)構(gòu)
6.2.2數(shù)組順序存儲結(jié)構(gòu)描述
6.2.3數(shù)組順序存儲結(jié)構(gòu)下的操作
6.3矩陣的存儲及操作
6.3.1矩陣的定義及操作
6.3.2矩陣的順序存儲
6.3.3特殊矩陣的壓縮存儲及操作
6.3.4稀疏矩陣的壓縮存儲及操作
習(xí)題6
第7章排序
7.1排序的基本概念
7.2待排序數(shù)據(jù)對象的存儲結(jié)構(gòu)
7.3插入排序
7.3.1直接插入排序
7.3.2折半插入算法
7.3.3希爾排序
7.4交換排序
7.4.1冒泡排序
7.4.2快速排序
7.5選擇排序
7.5.1直接選擇排序
7.5.2堆排序
7.5.3樹形選擇排序
7.6歸并排序
7.7基數(shù)排序
7.7.1用二維數(shù)組表示桶
7.7.2用鏈式存儲結(jié)構(gòu)實現(xiàn)桶
7.8內(nèi)部排序方法比較
7.9外排序
7.9.1外部排序
7.9.2多路平衡歸并
習(xí)題7
第8章查找
8.1查找的概念
8.2靜態(tài)查找技術(shù)
8.2.1順序查找
8.2.2二分查找
8.2.3分塊查找
8.3動態(tài)查找技術(shù)
8.3.1平衡二叉樹
8.3.2B樹
8.3.3B+樹
8.4哈希表的查找
8.4.1基本概念
8.4.2構(gòu)造哈希函數(shù)的方法
8.4.3哈希沖突的解決方法
8.4.4哈希表的查找
8.4.5哈希算法
8.4.6哈希表的查找分析
習(xí)題8
第9章文件
9.1外部存儲設(shè)備
9.1.1磁帶
9.1.2磁盤
9.1.3光盤
9.1.4閃存
9.2基本概念
9.3順序文件
9.4索引文件
9.5索引順序文件
9.6直接存取文件
9.7倒排文件
習(xí)題9
附錄AVC++ 6.0編譯環(huán)境介紹
附錄B實踐內(nèi)容及要求
附錄C數(shù)據(jù)結(jié)構(gòu)課程實驗報告格式范本
參考文獻
第5章圖
在數(shù)據(jù)結(jié)構(gòu)中，圖比前面幾章所講述的線性表、樹等都更為復(fù)雜。圖這種數(shù)據(jù)結(jié)構(gòu)在解決實際問題中也有著廣泛的應(yīng)用。例如，當駕車旅游時，需要在眾多路線中選擇一條最佳路線； 對大型工程進行管理時，怎樣才能夠提前完成工程； 在電路板上布線時，如何保證在連線最短的情況下連接多個結(jié)點。這些問題都可以通過本章所講述的內(nèi)容解決。
5．1圖的概念
5．1．1圖的定義
圖就是頂點和邊的集合。一般將圖描述為G={V,E}。其中，V(G)為圖G的頂點集合，必須是有窮非空集合； E(G)為圖G的邊集合，可以是空集。
圖5．1列出了兩個典型的圖。
圖5．1兩個典型的圖
5．1．2圖的術(shù)語
頂點： 圖中的數(shù)據(jù)元素。
邊： 連接圖中頂點的連線，表示兩個頂點之間的某種關(guān)系。邊可以用頂點對來表示。例如，圖5．1(a)中頂點V1和V2之間的關(guān)系可以用(V1,V2)表示，圖5．1(b)中頂點V1到頂點V2之間的關(guān)系可以用來表示。
�。� 連接圖中頂點的有向連線，表示兩個頂點之間的某種關(guān)系�；】梢杂庙旤c對來表示。例如，圖5．1．1(b)中頂點V1到頂點V2之間的關(guān)系可以用頂點對來表示。
弧頭： 弧的終止頂點。
弧尾： 弧的開始頂點。
無向圖： 由頂點和邊組成，無向圖的邊不具備方向性。
有向圖： 由頂點和弧組成。
完全圖： 圖中的任意兩個頂點之間都存在一條邊，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條
圖5.2完全圖和有向完全圖
邊，如圖5．2(a)所示。
有向完全圖： 圖中的任意兩個頂點之間都存在一對相反方向的弧，在一個含有n個頂點的有向完全圖中，有n(n-1)條邊。如圖5．2(b)所示。
稀疏圖： 具有很少邊或弧的圖。
稠密圖： 具有很多邊或弧的圖，即一個圖接近完全圖。
權(quán)： 與圖中的邊或者弧有關(guān)的數(shù)據(jù)信息稱為權(quán)(weight)。在實際應(yīng)用中，權(quán)值可以有某種含義。例如，在一個反映城市交通線路的圖中，邊上的權(quán)值可以表示該條線路的長度或者等級，如圖5．3(a)所示； 對于一個電子線路圖，邊上的權(quán)值可以表示兩個端點之間的電阻、電流或電壓值； 對于反映工程進度的圖而言，邊上的權(quán)值可以表示從前一個工程到后一個工程所需要的時間，如圖5．3(b)所示。
圖5.3權(quán)與網(wǎng)
網(wǎng)： 邊上帶權(quán)的圖稱為網(wǎng)圖或網(wǎng)絡(luò)(network)。如果邊是沒有方向的帶權(quán)圖，就是一個無向網(wǎng)圖，如圖5.3(a)所示； 如果邊是有方向的帶權(quán)圖，則它就是一個有向網(wǎng)圖，如圖5．3(b)所示。
子圖： 如果存在兩個圖G={V,E}和G′={V′,E′}，那么稱圖G′是圖G的子圖。如圖5．4所示，其中(b)和(c)是(a)的子圖。
圖5.4圖和子圖
路徑，路徑長度： 頂點Vp到頂點Vq之間的路徑(path)是指頂點序列Vp,Vi1,Vi2, …, VimVq。其中，(Vp,Vi1)，(Vi1,Vi2)，…,(Vim，Vq)分別為圖中的邊或者弧。路徑上邊或者弧的數(shù)目稱為路徑長度。圖5．1(a)所示的無向圖中，V1→V3→V4→V5與V1→V2→V5是從頂點V1到頂點V5的兩條路徑，路徑長度分別為3和2。
簡單路徑： 沒有重復(fù)頂點的路徑，如圖5．5(a)所示路徑為V0→V1→V3→V2，圖5．5(b)所示的V0→V1→V3→V0→V1→V2不是簡單路徑。
回路： 如果一條路徑的第一個頂點和最后一個頂點是同一個頂點，那么這條路徑構(gòu)成了一個回路。
簡單回路： 除了第一個和最后一個頂點外不再有重復(fù)頂點的回路稱為簡單回路，例如圖5．5(c)所示的路徑V0→V1→V3→V0。
圖5．5路徑和回路
自回路： 如果一條邊的頭和尾是同一個頂點，稱之為自回路。自回路的方向是沒有意義的，它既可以是有向邊，也可以是無向邊。
連通圖、連通分量： 在無向圖中,若從頂點Vi到頂點Vj(i≠j)有路徑，則稱頂點Vi與Vj是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。圖5．1(a)所示的無向圖為連通圖，其連通分量為1。圖5．4(a)中圖G包含兩個連通子圖，其連通分量為2。
強連通圖、強連通分量： 在有向圖中,若對于每一對頂點Vi和Vj(i≠j),都存在一條從Vi到Vj和從Vj到Vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量，如圖5．6所示。
……
書單推薦
