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

目    錄
第1章  緒論 11.1  數(shù)據(jù)結(jié)構(gòu)的討論范疇 11.2  數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況 31.3  數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念 51.3.1  基本概念和術(shù)語 51.3.2  數(shù)據(jù)結(jié)構(gòu) 61.3.3  數(shù)據(jù)類型和抽象數(shù)據(jù)類型 101.4  數(shù)據(jù)結(jié)構(gòu)的算法描述 121.4.1  算法 121.4.2  算法的描述 131.5  數(shù)據(jù)結(jié)構(gòu)的算法分析 171.5.1  算法效率的度量 171.5.2  算法的空間需求 191.6  習(xí)題 20第2章  線性表 232.1  線性表的類型定義 232.1.1  線性表的定義 242.1.2  線性表的抽象數(shù)據(jù)類型 242.2  線性表的順序表示與實現(xiàn) 272.2.1  線性表的順序存儲表示 282.2.2  順序表中基本操作的實現(xiàn) 282.2.3  順序存儲結(jié)構(gòu)小結(jié) 342.2.4  應(yīng)用舉例 352.3  線性表的鏈式表示與實現(xiàn) 382.3.1  線性表的鏈式存儲表示 392.3.2  單鏈表中基本操作的實現(xiàn) 392.3.3  循環(huán)鏈表 442.3.4  雙向鏈表 442.3.5  靜態(tài)鏈表 472.3.6  鏈式存儲結(jié)構(gòu)小結(jié) 482.3.7  應(yīng)用舉例 482.4  順序表示與鏈式表示比較 532.4.1  基于空間的考慮 532.4.2  基于時間的考慮 542.4.3  基于語言的考慮 542.5  習(xí)題 54第3章  棧和隊列 583.1  棧 583.1.1  棧的定義 583.1.2  棧的抽象數(shù)據(jù)類型 593.1.3  棧的順序存儲表示與實現(xiàn) 603.1.4  棧的鏈式存儲表示與實現(xiàn) 633.1.5  應(yīng)用舉例 643.2  隊列 733.2.1  隊列的定義 733.2.2  隊列的抽象數(shù)據(jù)類型 733.2.3  隊列的順序存儲表示與實現(xiàn) 743.2.4  隊列的鏈式存儲表示與實現(xiàn) 783.2.5  應(yīng)用舉例 803.3  習(xí)題 83第4章  串 854.1  串的類型定義 854.1.1  串的定義 854.1.2  串的抽象數(shù)據(jù)類型 864.2  串的存儲表示與實現(xiàn) 884.2.1  定長順序存儲表示 884.2.2  堆分配存儲表示 914.2.3  塊鏈存儲表示 954.2.4  應(yīng)用舉例 964.3  串的模式匹配 974.3.1  串的模式匹配BF算法 974.3.2  串的模式匹配KMP算法 994.4  習(xí)題 103第5章  多維數(shù)組與廣義表 1055.1  多維數(shù)組 1055.1.1  數(shù)組的定義 1055.1.2  數(shù)組的抽象數(shù)據(jù)類型 1065.1.3  數(shù)組的順序存儲表示和實現(xiàn) 1075.1.4  應(yīng)用舉例 1105.2  矩陣的壓縮存儲 1115.2.1  特殊矩陣 1125.2.2  稀疏矩陣 1145.2.3  應(yīng)用舉例 1245.3  廣義表 1285.3.1  廣義表的定義 1285.3.2  廣義表的抽象數(shù)據(jù)類型 1295.3.3  廣義表的鏈式存儲表示與實現(xiàn) 1305.3.4  應(yīng)用舉例 1385.4  習(xí)題 142第6章  二叉樹與樹 1446.1  二叉樹 1446.1.1  二叉樹的定義 1446.1.2  二叉樹的基本術(shù)語 1456.1.3  二叉樹的抽象數(shù)據(jù)類型 1476.1.4  二叉樹的基本性質(zhì) 1486.1.5  二叉樹的存儲表示 1506.2  遍歷二叉樹 1536.2.1  遍歷二叉樹的定義 1546.2.2  遍歷二叉樹的遞歸算法 1556.2.3  遍歷二叉樹的非遞歸算法 1566.2.4  基于遍歷操作的其他算法 1626.2.5  應(yīng)用舉例 1636.3  線索二叉樹 1686.3.1  線索二叉樹的引出 1686.3.2  線索二叉樹的定義 169
6.3.3  線索二叉樹的存儲表示與實現(xiàn) 1706.3.4  應(yīng)用舉例 1766.4  樹和森林 1776.4.1  樹和森林的定義 1776.4.2  樹的抽象數(shù)據(jù)類型 1786.4.3  樹的存儲表示 1796.4.4  樹和森林與二叉樹的轉(zhuǎn)換 1836.4.5  樹和森林的遍歷 1876.4.6  應(yīng)用舉例 1896.5  Huffman樹及其應(yīng)用 1976.5.1  Huffman樹的定義 1976.5.2  Huffman算法 1996.5.3  Huffman樹的存儲表示與實現(xiàn) 2006.5.4  Huffman編碼 2016.5.5  Huffman編碼的存儲表示與實現(xiàn) 2026.5.6  應(yīng)用舉例 2036.6  習(xí)題 205第7章  圖 2107.1  圖的類型定義 2107.1.1  圖的定義 2107.1.2  圖的基本術(shù)語 2107.1.3  圖的抽象數(shù)據(jù)類型 2147.1.4  應(yīng)用舉例 2157.2  圖的存儲表示與實現(xiàn) 2167.2.1  鄰接矩陣表示法 2167.2.2  鄰接表表示法 2197.2.3  十字鏈表表示法 2227.2.4  鄰接多重表表示法 2247.1.5  應(yīng)用舉例 2267.3  圖的遍歷 2277.3.1  深度優(yōu)先搜索遍歷圖 2277.3.2  廣度優(yōu)先搜索遍歷圖 2287.3.3  應(yīng)用舉例 2297.4  最小生成樹 230
7.4.1  生成樹 2307.4.2  最小生成樹 2317.4.3  應(yīng)用舉例 2377.5  最短路徑 2387.5.1  求某個源點到其他頂點的最段路徑 2397.5.2  求每一對頂點之間的最短路徑 2427.5.3  應(yīng)用舉例 2447.6  拓撲排序 2457.6.1  AOV網(wǎng) 2457.6.2  拓撲排序 2477.6.3  應(yīng)用舉例 2497.7  關(guān)鍵路徑 2507.7.1  AOE 網(wǎng) 2507.7.2  關(guān)鍵路徑的概念 2517.7.3  求關(guān)鍵路徑的算法實現(xiàn) 2527.7.4  應(yīng)用舉例 2547.8  習(xí)題 255第8章  查找表 2608.1  靜態(tài)查找表 2628.1.1  靜態(tài)查找表的抽象數(shù)據(jù)類型 2628.1.2  靜態(tài)查找表的順序存儲表示 2628.1.3  順序查找 2628.1.4  折半查找 2638.1.5  分塊查找 2658.1.6  應(yīng)用舉例 2678.2  動態(tài)查找表 2688.2.1  動態(tài)查找的抽象數(shù)據(jù)類型 2688.2.2  動態(tài)查找表的存儲表示 2698.2.3  二叉排序樹 2698.2.4  平衡二叉樹 2748.2.5  B-樹和B+樹 2808.2.6  鍵樹 2888.2.7  應(yīng)用舉例 2928.3  哈希表 2988.3.1  哈希表的定義 2998.3.2  哈希函數(shù)的構(gòu)造方法 3008.3.3  處理沖突的方法 3038.3.4  哈希表的查找和分析 3058.3.5  應(yīng)用舉例 3088.4  習(xí)題 310第9章  內(nèi)部排序 3149.1  插入排序法 3159.1.1  直接插入排序 3159.1.2  希爾排序 3179.1.3  應(yīng)用舉例 3189.2  交換排序法 3199.2.1  冒泡排序 3199.2.2  快速排序 3209.2.3  應(yīng)用舉例 3239.3  選擇排序法 3239.3.1  直接選擇排序 3249.3.2  堆排序 3259.3.3  應(yīng)用舉例 3319.4  歸并排序法 3319.4.1  兩個有序序列的歸并 3319.4.2  2-路歸并排序 3329.4.3  應(yīng)用舉例 3339.5  基數(shù)排序法 3339.5.1  多關(guān)鍵字排序 3339.5.2  鏈式基數(shù)排序 3359.5.3  應(yīng)用舉例 3399.6  各種內(nèi)部排序法的比較 3409.7  習(xí)題 341第10章  外部排序 34410.1  外存儲設(shè)備簡介 34410.1.1  磁帶信息的存取 34410.1.2  磁盤信息的存取 34510.1.3  光盤信息的存取 34610.2  磁帶文件歸并排序 34710.2.1  平衡歸并排序 34710.2.2  多步歸并排序 34810.2.3  應(yīng)用舉例 35310.3  磁盤文件歸并排序 35610.3.1  初始歸并段的生成 35610.3.2  置換選擇排序法 35710.3.3  應(yīng)用舉例 35810.4  最佳歸并樹 35910.4.1  最佳歸并樹的定義 35910.4.2  最佳歸并樹的設(shè)計 36110.4.3  應(yīng)用舉例 36210.5  習(xí)題 362第11章  文件 36411.1  基本概念 36411.1.1  文件的概念 36411.1.2  文件的分類 36511.1.3  文件的邏輯結(jié)構(gòu) 36511.1.4  文件的物理結(jié)構(gòu) 36611.2  順序文件 36611.2.1  順序文件的查找 36711.2.2  順序文件的修改 36711.2.3  順序文件的特點 36811.3  索引文件 36811.3.1  索引文件的分類 36811.3.2  索引文件的存儲 36911.3.3  索引文件的操作 36911.3.4  利用查找表建立 多級索引 370
11.4  ISAM和VSAM文件 37111.4.1  ISAM 文件 37111.4.2  VSAM 文件 37411.5  哈希文件 37611.5.1  哈希文件的操作 37711.5.2  哈希文件的特點 37811.6  多關(guān)鍵字文件 37811.6.1  多重表文件 37811.6.2  倒排文件 38011.7  應(yīng)用舉例 38111.8  習(xí)題 384第12章  數(shù)據(jù)結(jié)構(gòu)程序設(shè)計方法 38612.1  從問題到程序的求解過程 38612.1.1  建立數(shù)據(jù)結(jié)構(gòu)模型設(shè)計 抽象數(shù)據(jù)類型 38612.1.2  算法設(shè)計 38712.1.3  實現(xiàn)抽象數(shù)據(jù)類型 38812.1.4  編制程序代碼并進行 靜態(tài)測試和動態(tài)調(diào)試 38912.2  程序的規(guī)范說明 39112.3  應(yīng)用舉例 392附錄A  部分習(xí)題答案 402參考書目 409