數(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ù)語(yǔ) 51.3.2  數(shù)據(jù)結(jié)構(gòu) 61.3.3  數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型 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  線性表的類(lèi)型定義 232.1.1  線性表的定義 242.1.2  線性表的抽象數(shù)據(jù)類(lèi)型 242.2  線性表的順序表示與實(shí)現(xiàn) 272.2.1  線性表的順序存儲(chǔ)表示 282.2.2  順序表中基本操作的實(shí)現(xiàn) 282.2.3  順序存儲(chǔ)結(jié)構(gòu)小結(jié) 342.2.4  應(yīng)用舉例 352.3  線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 382.3.1  線性表的鏈?zhǔn)酱鎯?chǔ)表示 392.3.2  單鏈表中基本操作的實(shí)現(xiàn) 392.3.3  循環(huán)鏈表 442.3.4  雙向鏈表 442.3.5  靜態(tài)鏈表 472.3.6  鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)小結(jié) 482.3.7  應(yīng)用舉例 482.4  順序表示與鏈?zhǔn)奖硎颈容^ 532.4.1  基于空間的考慮 532.4.2  基于時(shí)間的考慮 542.4.3  基于語(yǔ)言的考慮 542.5  習(xí)題 54第3章  棧和隊(duì)列 583.1  棧 583.1.1  棧的定義 583.1.2  棧的抽象數(shù)據(jù)類(lèi)型 593.1.3  棧的順序存儲(chǔ)表示與實(shí)現(xiàn) 603.1.4  棧的鏈?zhǔn)酱鎯?chǔ)表示與實(shí)現(xiàn) 633.1.5  應(yīng)用舉例 643.2  隊(duì)列 733.2.1  隊(duì)列的定義 733.2.2  隊(duì)列的抽象數(shù)據(jù)類(lèi)型 733.2.3  隊(duì)列的順序存儲(chǔ)表示與實(shí)現(xiàn) 743.2.4  隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示與實(shí)現(xiàn) 783.2.5  應(yīng)用舉例 803.3  習(xí)題 83第4章  串 854.1  串的類(lèi)型定義 854.1.1  串的定義 854.1.2  串的抽象數(shù)據(jù)類(lèi)型 864.2  串的存儲(chǔ)表示與實(shí)現(xiàn) 884.2.1  定長(zhǎng)順序存儲(chǔ)表示 884.2.2  堆分配存儲(chǔ)表示 914.2.3  塊鏈存儲(chǔ)表示 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ù)類(lèi)型 1065.1.3  數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn) 1075.1.4  應(yīng)用舉例 1105.2  矩陣的壓縮存儲(chǔ) 1115.2.1  特殊矩陣 1125.2.2  稀疏矩陣 1145.2.3  應(yīng)用舉例 1245.3  廣義表 1285.3.1  廣義表的定義 1285.3.2  廣義表的抽象數(shù)據(jù)類(lèi)型 1295.3.3  廣義表的鏈?zhǔn)酱鎯?chǔ)表示與實(shí)現(xiàn) 1305.3.4  應(yīng)用舉例 1385.4  習(xí)題 142第6章  二叉樹(shù)與樹(shù) 1446.1  二叉樹(shù) 1446.1.1  二叉樹(shù)的定義 1446.1.2  二叉樹(shù)的基本術(shù)語(yǔ) 1456.1.3  二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型 1476.1.4  二叉樹(shù)的基本性質(zhì) 1486.1.5  二叉樹(shù)的存儲(chǔ)表示 1506.2  遍歷二叉樹(shù) 1536.2.1  遍歷二叉樹(shù)的定義 1546.2.2  遍歷二叉樹(shù)的遞歸算法 1556.2.3  遍歷二叉樹(shù)的非遞歸算法 1566.2.4  基于遍歷操作的其他算法 1626.2.5  應(yīng)用舉例 1636.3  線索二叉樹(shù) 1686.3.1  線索二叉樹(shù)的引出 1686.3.2  線索二叉樹(shù)的定義 169
6.3.3  線索二叉樹(shù)的存儲(chǔ)表示與實(shí)現(xiàn) 1706.3.4  應(yīng)用舉例 1766.4  樹(shù)和森林 1776.4.1  樹(shù)和森林的定義 1776.4.2  樹(shù)的抽象數(shù)據(jù)類(lèi)型 1786.4.3  樹(shù)的存儲(chǔ)表示 1796.4.4  樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 1836.4.5  樹(shù)和森林的遍歷 1876.4.6  應(yīng)用舉例 1896.5  Huffman樹(shù)及其應(yīng)用 1976.5.1  Huffman樹(shù)的定義 1976.5.2  Huffman算法 1996.5.3  Huffman樹(shù)的存儲(chǔ)表示與實(shí)現(xiàn) 2006.5.4  Huffman編碼 2016.5.5  Huffman編碼的存儲(chǔ)表示與實(shí)現(xiàn) 2026.5.6  應(yīng)用舉例 2036.6  習(xí)題 205第7章  圖 2107.1  圖的類(lèi)型定義 2107.1.1  圖的定義 2107.1.2  圖的基本術(shù)語(yǔ) 2107.1.3  圖的抽象數(shù)據(jù)類(lèi)型 2147.1.4  應(yīng)用舉例 2157.2  圖的存儲(chǔ)表示與實(shí)現(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  最小生成樹(shù) 230
7.4.1  生成樹(shù) 2307.4.2  最小生成樹(shù) 2317.4.3  應(yīng)用舉例 2377.5  最短路徑 2387.5.1  求某個(gè)源點(diǎn)到其他頂點(diǎn)的最段路徑 2397.5.2  求每一對(duì)頂點(diǎn)之間的最短路徑 2427.5.3  應(yīng)用舉例 2447.6  拓?fù)渑判?nbsp;2457.6.1  AOV網(wǎng) 2457.6.2  拓?fù)渑判?nbsp;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)鍵路徑的算法實(shí)現(xiàn) 2527.7.4  應(yīng)用舉例 2547.8  習(xí)題 255第8章  查找表 2608.1  靜態(tài)查找表 2628.1.1  靜態(tài)查找表的抽象數(shù)據(jù)類(lèi)型 2628.1.2  靜態(tài)查找表的順序存儲(chǔ)表示 2628.1.3  順序查找 2628.1.4  折半查找 2638.1.5  分塊查找 2658.1.6  應(yīng)用舉例 2678.2  動(dòng)態(tài)查找表 2688.2.1  動(dòng)態(tài)查找的抽象數(shù)據(jù)類(lèi)型 2688.2.2  動(dòng)態(tài)查找表的存儲(chǔ)表示 2698.2.3  二叉排序樹(shù) 2698.2.4  平衡二叉樹(shù) 2748.2.5  B-樹(shù)和B+樹(shù) 2808.2.6  鍵樹(shù) 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  兩個(gè)有序序列的歸并 3319.4.2  2-路歸并排序 3329.4.3  應(yīng)用舉例 3339.5  基數(shù)排序法 3339.5.1  多關(guān)鍵字排序 3339.5.2  鏈?zhǔn)交鶖?shù)排序 3359.5.3  應(yīng)用舉例 3399.6  各種內(nèi)部排序法的比較 3409.7  習(xí)題 341第10章  外部排序 34410.1  外存儲(chǔ)設(shè)備簡(jiǎn)介 34410.1.1  磁帶信息的存取 34410.1.2  磁盤(pán)信息的存取 34510.1.3  光盤(pán)信息的存取 34610.2  磁帶文件歸并排序 34710.2.1  平衡歸并排序 34710.2.2  多步歸并排序 34810.2.3  應(yīng)用舉例 35310.3  磁盤(pán)文件歸并排序 35610.3.1  初始?xì)w并段的生成 35610.3.2  置換選擇排序法 35710.3.3  應(yīng)用舉例 35810.4  最佳歸并樹(shù) 35910.4.1  最佳歸并樹(shù)的定義 35910.4.2  最佳歸并樹(shù)的設(shè)計(jì) 36110.4.3  應(yīng)用舉例 36210.5  習(xí)題 362第11章  文件 36411.1  基本概念 36411.1.1  文件的概念 36411.1.2  文件的分類(lèi) 36511.1.3  文件的邏輯結(jié)構(gòu) 36511.1.4  文件的物理結(jié)構(gòu) 36611.2  順序文件 36611.2.1  順序文件的查找 36711.2.2  順序文件的修改 36711.2.3  順序文件的特點(diǎn) 36811.3  索引文件 36811.3.1  索引文件的分類(lèi) 36811.3.2  索引文件的存儲(chǔ) 36911.3.3  索引文件的操作 36911.3.4  利用查找表建立 多級(jí)索引 370
11.4  ISAM和VSAM文件 37111.4.1  ISAM 文件 37111.4.2  VSAM 文件 37411.5  哈希文件 37611.5.1  哈希文件的操作 37711.5.2  哈希文件的特點(diǎn) 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è)計(jì)方法 38612.1  從問(wèn)題到程序的求解過(guò)程 38612.1.1  建立數(shù)據(jù)結(jié)構(gòu)模型設(shè)計(jì) 抽象數(shù)據(jù)類(lèi)型 38612.1.2  算法設(shè)計(jì) 38712.1.3  實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型 38812.1.4  編制程序代碼并進(jìn)行 靜態(tài)測(cè)試和動(dòng)態(tài)調(diào)試 38912.2  程序的規(guī)范說(shuō)明 39112.3  應(yīng)用舉例 392附錄A  部分習(xí)題答案 402參考書(shū)目 409