本書主要講述了各種基本數(shù)據(jù)結(jié)構(gòu)的概念, 包括數(shù)據(jù)結(jié)構(gòu)的邏輯定義、物理實(shí)現(xiàn)及其相應(yīng)運(yùn)算, 并運(yùn)用大量經(jīng)典的算法舉例說明怎樣用這些抽象的概念來解決實(shí)際問題。全書共分9章, 分為: 緒論，線性表和串，堆棧和隊(duì)列，樹和二叉樹，圖，數(shù)組、矩陣和廣義表，排序，查找，文件。
本書是作者在三十多年數(shù)據(jù)結(jié)構(gòu)教學(xué)經(jīng)驗(yàn)總結(jié)的基礎(chǔ)上編寫而成。全書共分為9章，內(nèi)容涵蓋數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表和串、棧和隊(duì)列、樹和二叉樹、圖、數(shù)組和矩陣、排序、查找、文件。
本書采用C++程序設(shè)計(jì)語言對(duì)算法進(jìn)行描述。本書不僅介紹了數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，而運(yùn)用大量的實(shí)際案例充實(shí)教材的內(nèi)容，力求既有理論深度，又有實(shí)用價(jià)值。在書中的附錄A中還給出了數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐中，如采用VC++6.0作為軟件環(huán)境時(shí)，VC++系統(tǒng)實(shí)用操作的簡(jiǎn)介。另外在附錄B中給出了本課程學(xué)習(xí)中應(yīng)該完成的基本實(shí)驗(yàn)要求，在每章的后面都附有相關(guān)的習(xí)題和部分習(xí)題答案。
本書是按高等院校計(jì)算機(jī)專業(yè)及信息管理專業(yè)本科四年制教學(xué)計(jì)劃“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)大綱要求編寫的教材，還可以作為計(jì)算機(jī)科技工作者及其相關(guān)專業(yè)人員的參考書。在學(xué)習(xí)本書知識(shí)前，要求讀者具備C++程序設(shè)計(jì)的知識(shí)。
“數(shù)據(jù)結(jié)構(gòu)”已成為一門比較成熟的課程。它是計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件研制者的必修課程。數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)基礎(chǔ)性研究?jī)?nèi)容之一，掌握這個(gè)領(lǐng)域的知識(shí)對(duì)于利用計(jì)算機(jī)資源高效地開發(fā)計(jì)算機(jī)程序是非常必要的。
數(shù)據(jù)結(jié)構(gòu)理論的應(yīng)用范圍已經(jīng)深入到編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫(kù)、人工智能、信息科學(xué)、系統(tǒng)工程、計(jì)算機(jī)輔助設(shè)計(jì)及信息管理領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)主要解決非數(shù)值計(jì)算應(yīng)用問題。
從理論上講：數(shù)據(jù)結(jié)構(gòu)的概念嚴(yán)謹(jǐn)、抽象；每種數(shù)據(jù)結(jié)構(gòu)類型描述層次清晰可見——概念層、邏輯定義層、物理存儲(chǔ)層、運(yùn)算實(shí)現(xiàn)層；每種數(shù)據(jù)結(jié)構(gòu)類型描述反映了實(shí)現(xiàn)問題的思想、實(shí)現(xiàn)的前提以及不同實(shí)現(xiàn)方式的特點(diǎn)和優(yōu)劣。
數(shù)據(jù)結(jié)構(gòu)描述的內(nèi)容看上去如同程序，但不是程序，它是程序設(shè)計(jì)思想的抽象化、一般化，它不依賴于某種物理設(shè)備甚至某種語言系統(tǒng)，學(xué)習(xí)者通過“數(shù)據(jù)結(jié)構(gòu)”課程不僅能獲得專業(yè)知識(shí)，而且能學(xué)到一種思維方式。
從實(shí)踐上講，數(shù)據(jù)結(jié)構(gòu)是建立在抽象化描述基礎(chǔ)之上的實(shí)踐性理論，這門學(xué)科只有賦予實(shí)踐的內(nèi)容才具有完備性，具體化是該學(xué)科的又一特點(diǎn)。在計(jì)算機(jī)系統(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)的邏輯定義、物理實(shí)現(xiàn)及其相應(yīng)運(yùn)算，并舉例說明怎樣用這些抽象的概念來解決實(shí)際問題。通過本書的學(xué)習(xí)不僅能正確地掌握數(shù)據(jù)結(jié)構(gòu)的基本理論，并能運(yùn)用這些理論來解決實(shí)際問題。
本書是編者集多年從事計(jì)算機(jī)軟件設(shè)計(jì)實(shí)踐及講授“數(shù)據(jù)結(jié)構(gòu)”課程的體會(huì)，并參考分析了國(guó)內(nèi)外數(shù)據(jù)結(jié)構(gòu)書籍文獻(xiàn)編寫而成的。本書采用廣泛使用的C++語言描述算法，并進(jìn)行了適當(dāng)?shù)乃惴◤?fù)雜性分析。
“數(shù)據(jù)結(jié)構(gòu)”課程不但理論性很強(qiáng)，同時(shí)實(shí)踐性也很強(qiáng)。本書在每一章的最后都安排了適量的習(xí)題，供讀者練習(xí)。
本書共分9章，介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念及線性表和串、棧和隊(duì)列、樹和二叉樹、圖、數(shù)組和矩陣、排序、查找、文件的數(shù)據(jù)結(jié)構(gòu)、算法及其應(yīng)用案例。
本書由王少波、張志編著。王少波負(fù)責(zé)編寫第1、2、3、4、7章及附錄，張志負(fù)責(zé)編寫第5、6、8、9章，全書由王少波負(fù)責(zé)統(tǒng)稿。
在成書過程中，編者參考了有關(guān)書籍，在此向這些書籍的作者表示感謝。
由于編者水平有限，書中可能存在不妥與疏漏之處，懇請(qǐng)讀者不吝指教。
編者
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)存儲(chǔ)空間分配回收和動(dòng)態(tài)存儲(chǔ)空間分配回收
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線性表的順序存儲(chǔ)及操作
2.2.1線性表順序存儲(chǔ)
2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)
2.3簡(jiǎn)單鏈表存儲(chǔ)結(jié)構(gòu)及操作
2.3.1簡(jiǎn)單鏈表的存儲(chǔ)
2.3.2簡(jiǎn)單鏈表的操作實(shí)現(xiàn)
2.4雙向鏈表
2.4.1雙向鏈表的存儲(chǔ)
2.4.2雙向鏈表類定義
2.4.3雙向鏈表的操作
2.5單向循環(huán)鏈表和雙向循環(huán)鏈表
2.5.1單向循環(huán)鏈表的存儲(chǔ)
2.5.2雙向循環(huán)鏈表的存儲(chǔ)
2.6模擬指針方式構(gòu)造簡(jiǎn)單鏈表
2.6.1模擬鏈表的存儲(chǔ)空間的構(gòu)建
2.6.2在模擬鏈表空間上構(gòu)建簡(jiǎn)單鏈表
2.7多重鏈表
2.8鏈表應(yīng)用
2.8.1結(jié)點(diǎn)移至表首運(yùn)算
2.8.2鏈表的逆向運(yùn)算
2.8.3多項(xiàng)式的相加運(yùn)算
2.8.4十字鏈表結(jié)構(gòu)的應(yīng)用
2.8.5一個(gè)較復(fù)雜的機(jī)票售票系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)方案
2.9串
2.9.1串的定義
2.9.2串的邏輯結(jié)構(gòu)及運(yùn)算
2.9.3串的順序存儲(chǔ)結(jié)構(gòu)
2.9.4串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
2.10線性表基本算法的程序?qū)崿F(xiàn)
2.10.1順序存儲(chǔ)結(jié)構(gòu)線性表程序?qū)崿F(xiàn)
2.10.2帶表頭結(jié)點(diǎn)的簡(jiǎn)單鏈表程序?qū)崿F(xiàn)
習(xí)題2
第3章堆棧和隊(duì)列
3.1堆棧的定義
3.1.1堆棧的邏輯結(jié)構(gòu)
3.1.2堆棧的抽象數(shù)據(jù)類型
3.2堆棧的順序存儲(chǔ)及操作
3.2.1堆棧順序存儲(chǔ)
3.2.2順序存儲(chǔ)結(jié)構(gòu)堆棧的運(yùn)算實(shí)現(xiàn)
3.3堆棧的鏈?zhǔn)酱鎯?chǔ)及操作
3.3.1堆棧的鏈?zhǔn)酱鎯?chǔ)
3.3.2鏈?zhǔn)綏ｎ惖亩x
3.3.3鏈?zhǔn)綏ｎ愡\(yùn)算的實(shí)現(xiàn)
3.4多個(gè)棧共享鄰接空間
3.5堆棧的應(yīng)用
3.5.1檢驗(yàn)表達(dá)式中括號(hào)的匹配
3.5.2表達(dá)式的求值
3.5.3背包問題求解
3.5.4地圖四染色問題求解
3.6隊(duì)列的定義
3.6.1隊(duì)列的邏輯結(jié)構(gòu)
3.6.2隊(duì)列的抽象數(shù)據(jù)類型
3.7隊(duì)列的順序存儲(chǔ)及操作
3.7.1隊(duì)列的順序存儲(chǔ)
3.7.2順序存儲(chǔ)結(jié)構(gòu)下隊(duì)列的運(yùn)算實(shí)現(xiàn)
3.8隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及操作
3.8.1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
3.8.2鏈?zhǔn)疥?duì)列模板類的定義
3.8.3鏈?zhǔn)疥?duì)列的操作
3.9隊(duì)列的應(yīng)用
3.9.1列車重排
3.9.2投資組合問題
3.10堆棧和隊(duì)列基本算法的程序?qū)崿F(xiàn)
3.10.1堆棧順序存儲(chǔ)結(jié)構(gòu)程序?qū)崿F(xiàn)
3.10.2隊(duì)列順序存儲(chǔ)結(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二叉樹的存儲(chǔ)結(jié)構(gòu)
4.3.1二叉樹的順序存儲(chǔ)
4.3.2二叉樹的鏈?zhǔn)酱鎯?chǔ)
4.4二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的操作
4.4.1二叉樹的操作概念
4.4.2二叉樹的前序、中序、后序遍歷操作
4.4.3二叉樹的層次遍歷運(yùn)算
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一般樹的運(yùn)算
4.7樹的應(yīng)用
4.7.1分類二叉樹
4.7.2堆樹
4.7.3樹的路徑長(zhǎng)度和赫夫曼樹
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圖的存儲(chǔ)結(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最小代價(jià)生成樹
5.5最短路徑
5.5.1單源最短路徑
5.5.2任意兩個(gè)頂點(diǎn)之間的路徑
5.6拓?fù)渑判?br />
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ù)組的順序表示及運(yùn)算
6.2.1數(shù)組的順序存儲(chǔ)結(jié)構(gòu)
6.2.2數(shù)組順序存儲(chǔ)結(jié)構(gòu)描述
6.2.3數(shù)組順序存儲(chǔ)結(jié)構(gòu)下的操作
6.3矩陣的存儲(chǔ)及操作
6.3.1矩陣的定義及操作
6.3.2矩陣的順序存儲(chǔ)
6.3.3特殊矩陣的壓縮存儲(chǔ)及操作
6.3.4稀疏矩陣的壓縮存儲(chǔ)及操作
習(xí)題6
第7章排序
7.1排序的基本概念
7.2待排序數(shù)據(jù)對(duì)象的存儲(chǔ)結(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用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(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動(dòng)態(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外部存儲(chǔ)設(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實(shí)踐內(nèi)容及要求
附錄C數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告格式范本
參考文獻(xiàn)
書單推薦
