數(shù)據(jù)結(jié)構(gòu)

第1章 緒 論１
1．1 數(shù)據(jù)結(jié)構(gòu)１
1．1．1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性１
1．1．2 什么是數(shù)據(jù)結(jié)構(gòu)３
1．1．3 數(shù)據(jù)的邏輯結(jié)構(gòu)５
1．1．4 數(shù)據(jù)的存儲結(jié)構(gòu)１０
1．1．5 數(shù)據(jù)的運算１２
1．2 算法１３
1．2．1 什么是算法１３
1．2．2 算法的描述１３
1．2．3 算法設(shè)計１６
1．2．4 算法設(shè)計要求１８
1．2．5 算法分析１８
1．3 程序、程序設(shè)計與程序設(shè)計方法學(xué)２０
1．3．1 程序２０
1．3．2 程序設(shè)計２０
1．3．3 程序設(shè)計方法學(xué)２１
1．4 計算思維與抽象數(shù)據(jù)類型２３
1．4．1 計算思維２４
1．4．2 計算機求解問題２５
1．4．3 抽象數(shù)據(jù)類型２６
1．4．4 數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型２８
1．5 課程設(shè)計相關(guān)知識２８
1．5．1 課程設(shè)計目的與內(nèi)涵２９
1．5．2 課程設(shè)計步驟２９
1．5．3 課程設(shè)計報告規(guī)范３０
課后練習(xí)與課程設(shè)計３０
第二章 線性表３２
2．1 線性表ADT３２
2．2 順序表３３
2．2．1 向量的順序存儲表示３４
2．2．2 向量運算３５
2．2．3 應(yīng)用舉例４０
2．2．4 不等長結(jié)點的索引表示——目錄表４３
2．3 鏈表４３
2．3．1 指針與指針對象４３
2．3．2 單鏈表４６
2．3．3 線性表的兩種存儲比較５８
2．3．4 可利用空間表及其管理５８
2．4 線性表的其它鏈接存儲表示６０
2．4．1 循環(huán)鏈表６０
2．4．2 雙向鏈表６１
2．4．3 靜態(tài)鏈表６３
2．5 課程設(shè)計相關(guān)內(nèi)容與應(yīng)用示例６６
2．5．1 算法設(shè)計中的基本方法６６
2．5．2 一元多項式相乘６７
課后練習(xí)與課程設(shè)計７１
第3章 棧和隊列74
3．1 棧ADT74
3．2 順序棧75
3．2．1 順序棧的存儲表示75
3．2．2 順序?；具\算的實現(xiàn)76
3．3 鏈接棧79
3．3．1 鏈接棧的存儲表示79
3．3．2 鏈接?；具\算的實現(xiàn)80
3．4 棧的應(yīng)用舉例80
3．4．1 數(shù)制轉(zhuǎn)換81
3．4．2 表達式求值82
3．5 隊列ADT86
3．6 順序隊列87
3．6．1 順序隊列的存儲表示87
3．6．2 順序隊列基本運算的實現(xiàn)87
3．7 鏈接隊列90
3．7．1 鏈接隊列的存儲表示90
3．7．2 鏈接隊列基本運算的實現(xiàn)91
3．8 隨機事件模擬93
3．9 課程設(shè)計相關(guān)內(nèi)容與應(yīng)用示例96
3．9．1 遞歸概念96
3．9．2 遞歸過程設(shè)計98
3．9．3 遞歸過程與非遞歸過程98
課后練習(xí)與課程設(shè)計100
第4章 幾種特殊線性表104
4．1 串104
4．1．1 串的基本概念104
4．1．2 串ADT105
4．1．3 串的存儲表示107
4．1．4 串運算的實現(xiàn)109
4．2 數(shù)組111
4．2．1 數(shù)組ADT111
4．2．2 數(shù)組的順序存儲表示112
4．3 矩陣113
4．3．1 對稱矩陣的壓縮存儲114
4．3．2 對角矩陣的壓縮存儲114
4．3．3 稀疏矩陣的三元組順序表存儲表示116
4．3．4 稀疏矩陣的十字鏈表存儲表示117
4．3．5 稀疏矩陣的轉(zhuǎn)置運算118
4．3．6 稀疏矩陣的插入運算120
4．4 廣義表121
4．4．1 廣義表的基本概念121
4．4．2 廣義表ADT122
4．4．3 廣義表的存儲表示123
4．4．4 多元多項式的存儲表示125
4．5 課程設(shè)計相關(guān)知識與應(yīng)用示例127
4．5．1 梵天塔問題127
4．5．2 再談遞歸過程設(shè)計128
4．5．3 求廣義表的深度129
課后練習(xí)與課程設(shè)計131
第5章 內(nèi)排序１３３
5．1 排序的基本概念１３３
5．2 直接插入排序１３４
5．3 直接選擇排序１３６
5．4 冒泡排序１３８
5．5 希爾排序１４１
5．6 快速排序１４３
5．7 歸并排序１４８
5．7．1 排序文件的歸并１４８
5．7．2 2-路歸并排序１４９
5．8 基數(shù)排序１５１
5．9 各種排序方法的比較１５４
5．10 課程設(shè)計相關(guān)知識與應(yīng)用示例１５７
5．10．1 自頂向下設(shè)計技術(shù)與方法１５７
5．10．2 逐步求精設(shè)計技術(shù)與方法１５７
5．10．3 積木游戲１５８
課后練習(xí)與課程設(shè)計１６０
第6章 樹和二叉樹163
6．1 樹的基本概念163
6．2 樹的存儲結(jié)構(gòu)165
6．2．1 樹的標準形式存儲結(jié)構(gòu)166
6．2．2 樹的逆形式存儲結(jié)構(gòu)167
6．2．3 樹的擴充標準形式存儲結(jié)構(gòu)167
6．2．4 樹的雙親數(shù)組存儲結(jié)構(gòu)168
6．2．5 樹的孩子鏈表存儲結(jié)構(gòu)169
6．2．6 樹的三重鏈表存儲結(jié)構(gòu)170
6．3 樹的遍歷和樹的線性表示171
6．3．1 樹的前序遍歷171
6．3．2 樹的后序遍歷173
6．3．3 樹的層次遍歷174
6．3．4 樹的線性表示176
6．4 二叉樹177
6．4．1 二叉樹定義和二叉樹ADT177
6．4．2 二叉樹的性質(zhì)179
6．4．3 二叉樹與樹（或森林）之間的轉(zhuǎn)換180
6．4．4 二叉樹的存儲表示183
6．5 二叉樹遍歷186
6．5．1 二叉樹遍歷187
6．5．2 由遍歷序列構(gòu)造二叉樹197
6．5．3基于二叉樹遍歷操作的算法舉例198
6．6 線索二叉樹200
6．6．1 線索二叉樹201
6．6．2 線索二叉樹的利用202
6．6．3 二叉樹的線索化205
6．7 哈夫曼樹及其應(yīng)用206
6．7．1 二叉樹的路徑長度和帶權(quán)路徑長度206
6．7．2 哈夫曼樹和哈夫曼算法208
6．7．3 哈夫曼樹的應(yīng)用210
6．8 課程設(shè)計相關(guān)知識與應(yīng)用示例216
6．8．1 結(jié)構(gòu)化方法概述216
6．8．2 模塊化設(shè)計技術(shù)與方法217
6．8．3 模塊化應(yīng)用示例218
課后練習(xí)與課程設(shè)計220
第七章 圖223
7．1 圖的基本概念223
7．2 圖的存儲結(jié)構(gòu)227
7．2．1 鄰接矩陣227
7．2．2 鄰接表229
7．3 圖的遍歷231
7．3．1 深度優(yōu)先搜索法232
7．3．2 廣度優(yōu)先搜索法233
7．3．3 求圖的（強）連通分量235
7．4 生成樹與最小生成樹235
7．4．1 生成樹概念235
7．4．2 最小生成樹236
7．5 最短路徑240
7．5．1 單源最短路徑241
7．5．2 每一對頂點間的最短路徑245
7．6 拓撲排序247
7．6．1 AOV網(wǎng)247
7．6．2 拓撲排序248
7．7 關(guān)鍵路徑250
7．7．1 AOE網(wǎng)250
7．7．2 關(guān)鍵路徑250
7．8 課程設(shè)計相關(guān)知識與應(yīng)用示例254
7．8．1 遞推算法254
7．8．2 分治法概述255
7．8．3 數(shù)字旋轉(zhuǎn)方陣255
課后練習(xí)與課程設(shè)計258
第8章 查 找262
8．1 線性表查找262
8．1．1 順序查找262
8．1．2 折半查找264
8．1．3 分塊查找266
8．2 樹型結(jié)構(gòu)查找267
8．2．1 二叉排序樹267
8．2．2 平衡查找樹271
8．2．3 B樹和B+樹278
8．2．4 堆排序284
8．3 哈希表及其查找286
8．3．1 哈希表286
8．3．2 哈希函數(shù)構(gòu)造方法287
8．3．3 解決沖突方法290
8．3．4 哈希表查找292
8．4 課程設(shè)計相關(guān)知識與應(yīng)用示例294
8．4．1 動態(tài)規(guī)劃法概述294
8．4．2 貪心法概述295
8．4．3 背包問題296
課后練習(xí)與課程設(shè)計298
第9章 文件與外部排序301
9．1 文件概述301
9．2 文件組織302
9．2．1 順序文件302
9．2．2 索引文件303
9．2．3 哈希文件305
9．2．4 多關(guān)鍵字文件306
9．3 外部排序308
9．3．1 2-路平衡歸并排序法308
9．3．2 多路平衡歸并排序法310
9．3．3 置換-選擇排序312
9．3．4 最優(yōu)歸并樹316
9．4 課程設(shè)計相關(guān)知識與應(yīng)用示例317
9．4．1 回溯法概述317
9．4．2 分支限界法概述319
9．4．3 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計示例321
課后練習(xí)與課程設(shè)計322
參考文獻324