本書(shū)主要講述了各種基本數(shù)據(jù)結(jié)構(gòu)的概念, 包括數(shù)據(jù)結(jié)構(gòu)的邏輯定義、物理實(shí)現(xiàn)及其相應(yīng)運(yùn)算, 并運(yùn)用大量經(jīng)典的算法舉例說(shuō)明怎樣用這些抽象的概念來(lái)解決實(shí)際問(wèn)題。全書(shū)共分9章, 分為: 緒論，線性表和串，堆棧和隊(duì)列，樹(shù)和二叉樹(shù)，圖，數(shù)組、矩陣和廣義表，排序，查找，文件。
本書(shū)是作者在三十多年數(shù)據(jù)結(jié)構(gòu)教學(xué)經(jīng)驗(yàn)總結(jié)的基礎(chǔ)上編寫(xiě)而成。全書(shū)共分為9章，內(nèi)容涵蓋數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表和串、棧和隊(duì)列、樹(shù)和二叉樹(shù)、圖、數(shù)組和矩陣、排序、查找、文件。
本書(shū)采用C++程序設(shè)計(jì)語(yǔ)言對(duì)算法進(jìn)行描述。本書(shū)不僅介紹了數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，而運(yùn)用大量的實(shí)際案例充實(shí)教材的內(nèi)容，力求既有理論深度，又有實(shí)用價(jià)值。在書(shū)中的附錄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í)題答案。
本書(shū)是按高等院校計(jì)算機(jī)專(zhuān)業(yè)及信息管理專(zhuān)業(yè)本科四年制教學(xué)計(jì)劃“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)大綱要求編寫(xiě)的教材，還可以作為計(jì)算機(jī)科技工作者及其相關(guān)專(zhuān)業(yè)人員的參考書(shū)。在學(xué)習(xí)本書(shū)知識(shí)前，要求讀者具備C++程序設(shè)計(jì)的知識(shí)。
“數(shù)據(jù)結(jié)構(gòu)”已成為一門(mén)比較成熟的課程。它是計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件研制者的必修課程。數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)基礎(chǔ)性研究?jī)?nèi)容之一，掌握這個(gè)領(lǐng)域的知識(shí)對(duì)于利用計(jì)算機(jī)資源高效地開(kāi)發(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)用問(wèn)題。
從理論上講：數(shù)據(jù)結(jié)構(gòu)的概念嚴(yán)謹(jǐn)、抽象；每種數(shù)據(jù)結(jié)構(gòu)類(lèi)型描述層次清晰可見(jiàn)——概念層、邏輯定義層、物理存儲(chǔ)層、運(yùn)算實(shí)現(xiàn)層；每種數(shù)據(jù)結(jié)構(gòu)類(lèi)型描述反映了實(shí)現(xiàn)問(wèn)題的思想、實(shí)現(xiàn)的前提以及不同實(shí)現(xiàn)方式的特點(diǎn)和優(yōu)劣。
數(shù)據(jù)結(jié)構(gòu)描述的內(nèi)容看上去如同程序，但不是程序，它是程序設(shè)計(jì)思想的抽象化、一般化，它不依賴(lài)于某種物理設(shè)備甚至某種語(yǔ)言系統(tǒng)，學(xué)習(xí)者通過(guò)“數(shù)據(jù)結(jié)構(gòu)”課程不僅能獲得專(zhuān)業(yè)知識(shí)，而且能學(xué)到一種思維方式。
從實(shí)踐上講，數(shù)據(jù)結(jié)構(gòu)是建立在抽象化描述基礎(chǔ)之上的實(shí)踐性理論，這門(mén)學(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ū)敘述了各種基本數(shù)據(jù)結(jié)構(gòu)的概念，包括數(shù)據(jù)結(jié)構(gòu)的邏輯定義、物理實(shí)現(xiàn)及其相應(yīng)運(yùn)算，并舉例說(shuō)明怎樣用這些抽象的概念來(lái)解決實(shí)際問(wèn)題。通過(guò)本書(shū)的學(xué)習(xí)不僅能正確地掌握數(shù)據(jù)結(jié)構(gòu)的基本理論，并能運(yùn)用這些理論來(lái)解決實(shí)際問(wèn)題。
本書(shū)是編者集多年從事計(jì)算機(jī)軟件設(shè)計(jì)實(shí)踐及講授“數(shù)據(jù)結(jié)構(gòu)”課程的體會(huì)，并參考分析了國(guó)內(nèi)外數(shù)據(jù)結(jié)構(gòu)書(shū)籍文獻(xiàn)編寫(xiě)而成的。本書(shū)采用廣泛使用的C++語(yǔ)言描述算法，并進(jìn)行了適當(dāng)?shù)乃惴◤?fù)雜性分析。
“數(shù)據(jù)結(jié)構(gòu)”課程不但理論性很強(qiáng)，同時(shí)實(shí)踐性也很強(qiáng)。本書(shū)在每一章的最后都安排了適量的習(xí)題，供讀者練習(xí)。
本書(shū)共分9章，介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念及線性表和串、棧和隊(duì)列、樹(shù)和二叉樹(shù)、圖、數(shù)組和矩陣、排序、查找、文件的數(shù)據(jù)結(jié)構(gòu)、算法及其應(yīng)用案例。
本書(shū)由王少波、張志編著。王少波負(fù)責(zé)編寫(xiě)第1、2、3、4、7章及附錄，張志負(fù)責(zé)編寫(xiě)第5、6、8、9章，全書(shū)由王少波負(fù)責(zé)統(tǒng)稿。
在成書(shū)過(guò)程中，編者參考了有關(guān)書(shū)籍，在此向這些書(shū)籍的作者表示感謝。
由于編者水平有限，書(shū)中可能存在不妥與疏漏之處，懇請(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)類(lèi)型
1.2.4靜態(tài)存儲(chǔ)空間分配回收和動(dòng)態(tài)存儲(chǔ)空間分配回收
1.3數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型和數(shù)據(jù)結(jié)構(gòu)
1.3.1類(lèi)和數(shù)據(jù)類(lèi)型
1.3.2抽象數(shù)據(jù)類(lèi)型
1.3.3數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型
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ù)類(lèi)型
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雙向鏈表類(lèi)定義
2.4.3雙向鏈表的操作
2.5單向循環(huán)鏈表和雙向循環(huán)鏈表
2.5.1單向循環(huán)鏈表的存儲(chǔ)
2.5.2雙向循環(huán)鏈表的存儲(chǔ)
2.6模擬指針?lè)绞綐?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ù)類(lèi)型
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)綏ｎ?lèi)的定義
3.3.3鏈?zhǔn)綏ｎ?lèi)運(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背包問(wèn)題求解
3.5.4地圖四染色問(wèn)題求解
3.6隊(duì)列的定義
3.6.1隊(duì)列的邏輯結(jié)構(gòu)
3.6.2隊(duì)列的抽象數(shù)據(jù)類(lèi)型
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ì)列模板類(lèi)的定義
3.8.3鏈?zhǔn)疥?duì)列的操作
3.9隊(duì)列的應(yīng)用
3.9.1列車(chē)重排
3.9.2投資組合問(wèn)題
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章樹(shù)和二叉樹(shù)
4.1樹(shù)、森林的概念
4.1.1樹(shù)的定義
4.1.2樹(shù)的術(shù)語(yǔ)
4.2二叉樹(shù)定義及性質(zhì)
4.2.1二叉樹(shù)的定義
4.2.2二叉樹(shù)的性質(zhì)
4.2.3二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型
4.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
4.3.1二叉樹(shù)的順序存儲(chǔ)
4.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)
4.4二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的操作
4.4.1二叉樹(shù)的操作概念
4.4.2二叉樹(shù)的前序、中序、后序遍歷操作
4.4.3二叉樹(shù)的層次遍歷運(yùn)算
4.5線索樹(shù)
4.5.1線索樹(shù)的概念
4.5.2二叉線索樹(shù)的操作
4.6一般樹(shù)的表示和遍歷
4.6.1一般樹(shù)的二叉鏈表示及其與二叉樹(shù)的關(guān)系
4.6.2二叉樹(shù)、一般樹(shù)及森林的關(guān)系
4.6.3一般樹(shù)的遍歷概念
4.6.4一般樹(shù)的運(yùn)算
4.7樹(shù)的應(yīng)用
4.7.1分類(lèi)二叉樹(shù)
4.7.2堆樹(shù)
4.7.3樹(shù)的路徑長(zhǎng)度和赫夫曼樹(shù)
4.8二叉樹(shù)基本算法的程序?qū)崿F(xiàn)
習(xí)題4
第5章圖
5.1圖的概念
5.1.1圖的定義
5.1.2圖的術(shù)語(yǔ)
5.1.3圖的抽象數(shù)據(jù)類(lèi)型
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最小生成樹(shù)
5.4.1生成樹(shù)
5.4.2最小代價(jià)生成樹(shù)
5.5最短路徑
5.5.1單源最短路徑
5.5.2任意兩個(gè)頂點(diǎn)之間的路徑
5.6拓?fù)渑判?br />
5.6.1有向無(wú)環(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ù)類(lèi)型
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樹(shù)形選擇排序
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平衡二叉樹(shù)
8.3.2B樹(shù)
8.3.3B+樹(shù)
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磁盤(pán)
9.1.3光盤(pán)
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)
書(shū)單推薦
