數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版 第2版）

第1章 緒論 11.1 數(shù)據(jù)結(jié)構(gòu)的概念及分類 11.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 11.1.2 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本術(shù)語(yǔ) 21.1.3 數(shù)據(jù)結(jié)構(gòu)的分類 51.1.4 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu) 61.1.5 定義在數(shù)據(jù)結(jié)構(gòu)上的操作 71.1.6 “好”數(shù)據(jù)結(jié)構(gòu) 71.2 使用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu) 71.2.1 C語(yǔ)言的數(shù)據(jù)類型 81.2.2 算法的控制結(jié)構(gòu) 91.2.3 算法的函數(shù)結(jié)構(gòu) 101.2.4 動(dòng)態(tài)存儲(chǔ)分配 121.2.5 邏輯和關(guān)系運(yùn)算的約定 121.2.6 輸入與輸出 131.3 算法和算法設(shè)計(jì) 131.3.1 算法的定義和特性 131.3.2 算法的設(shè)計(jì)步驟 141.3.3 算法設(shè)計(jì)的基本方法 151.4 算法分析與度量 181.4.1 算法的評(píng)價(jià)標(biāo)準(zhǔn) 181.4.2 算法的時(shí)間和空間復(fù)雜度度量 181.4.3 算法的漸近分析 21小結(jié) 24習(xí)題 24第2章 線性表 272.1 線性表 272.1.1 線性表的定義和特點(diǎn) 272.1.2 線性表的主要操作 282.2 順序表 292.2.1 順序表的定義和特點(diǎn) 292.2.2 順序表的結(jié)構(gòu)定義 302.2.3 順序表查找操作的實(shí)現(xiàn) 312.2.4 順序表插入和刪除操作的實(shí)現(xiàn) 322.2.5 順序表的應(yīng)用：集合運(yùn)算 342.3 單鏈表 352.3.1 單鏈表的定義和特點(diǎn) 352.3.2 單鏈表的結(jié)構(gòu)定義 362.3.3 單鏈表中的插入與刪除 362.3.4 帶頭結(jié)點(diǎn)的單鏈表 402.3.5 單鏈表的遍歷與創(chuàng)建 422.3.6 單鏈表的應(yīng)用：集合運(yùn)算 442.3.7 循環(huán)鏈表 462.3.8 雙向鏈表 502.3.9 靜態(tài)鏈表 532.4 順序表與線性鏈表的比較 542.5 線性表的應(yīng)用：一元多項(xiàng)式及其運(yùn)算 562.5.1 一元多項(xiàng)式的表示 562.5.2 多項(xiàng)式的結(jié)構(gòu)定義 572.5.3 多項(xiàng)式的加法 592.5.4 擴(kuò)展閱讀：多項(xiàng)式的乘法 60小結(jié) 62習(xí)題 63第3章 棧和隊(duì)列 663.1 棧 663.1.1 棧的概念 663.1.2 順序棧 673.1.3 擴(kuò)展閱讀：多棧處理 703.1.4 鏈?zhǔn)綏? 733.1.5 擴(kuò)展閱讀：棧的混洗 743.2 隊(duì)列 763.2.1 隊(duì)列的概念 763.2.2 循環(huán)隊(duì)列 763.2.3 鏈?zhǔn)疥?duì)列 803.3 棧的應(yīng)用 823.3.1 數(shù)制轉(zhuǎn)換 823.3.2 括號(hào)匹配 833.3.3 表達(dá)式的計(jì)算與優(yōu)先級(jí)處理 843.3.4 棧與遞歸的實(shí)現(xiàn) 883.4 隊(duì)列的應(yīng)用 913.5 在算法設(shè)計(jì)中使用遞歸 923.5.1 漢諾塔問(wèn)題與分治法 923.5.2 直接把遞歸過(guò)程改為非遞歸過(guò)程 943.5.3 擴(kuò)展閱讀：遞歸過(guò)程的非遞歸模擬算法 953.5.4 迷宮問(wèn)題與回溯法 983.5.5 計(jì)算組合數(shù)與動(dòng)態(tài)規(guī)劃 1013.6 擴(kuò)展閱讀：雙端隊(duì)列 1023.6.1 雙端隊(duì)列的概念 1023.6.2 輸入受限的雙端隊(duì)列 1033.6.3 輸出受限的雙端隊(duì)列 1043.6.4 雙端隊(duì)列的存儲(chǔ)表示 1043.7 擴(kuò)展閱讀：優(yōu)先隊(duì)列 1063.7.1 優(yōu)先隊(duì)列的概念 1063.7.2 優(yōu)先隊(duì)列的實(shí)現(xiàn) 107小結(jié) 108習(xí)題 108第4章 數(shù)組、串和廣義表 1124.1 數(shù)組 1124.1.1 一維數(shù)組 1124.1.2 多維數(shù)組 1144.2 特殊矩陣的壓縮存儲(chǔ) 1164.2.1 對(duì)稱矩陣的壓縮存儲(chǔ) 1174.2.2 三對(duì)角矩陣的壓縮存儲(chǔ) 1184.2.3 擴(kuò)展閱讀：w對(duì)角矩陣的壓縮存儲(chǔ) 1194.3 稀疏矩陣 1204.3.1 稀疏矩陣的概念 1204.3.2 稀疏矩陣的順序存儲(chǔ)表示 1214.3.3 稀疏矩陣的鏈表表示 1244.4 字符串 1254.4.1 字符串的概念 1264.4.2 字符串的初始化和賦值 1264.4.3 自定義字符串的存儲(chǔ)表示 1284.4.4 串的模式匹配 1324.5 廣義表 1404.5.1 廣義表的概念 1404.5.2 廣義表的性質(zhì) 1414.5.3 廣義表的鏈接表示 1414.5.4 擴(kuò)展閱讀：三元多項(xiàng)式的表示 147小結(jié) 148習(xí)題 149第5章 樹(shù)與二叉樹(shù) 1525.1 樹(shù)的基本概念 1525.1.1 樹(shù)的定義和術(shù)語(yǔ) 1525.1.2 樹(shù)的基本操作 1545.2 二叉樹(shù)及其存儲(chǔ)表示 1555.2.1 二叉樹(shù)的概念 1555.2.2 二叉樹(shù)的性質(zhì) 1565.2.3 二叉樹(shù)的主要操作 1585.2.4 二叉樹(shù)的順序存儲(chǔ)表示 1595.2.5 二叉樹(shù)的鏈表存儲(chǔ)表示 1605.3 二叉樹(shù)的遍歷 1615.3.1 二叉樹(shù)遍歷的遞歸算法 1625.3.2 遞歸遍歷算法的應(yīng)用舉例 1635.3.3 二叉樹(shù)遍歷的非遞歸算法 1665.3.4 利用隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層次序遍歷 1695.3.5 非遞歸遍歷算法的應(yīng)用舉例 1705.3.6 二叉樹(shù)的計(jì)數(shù) 1715.4 線索二叉樹(shù) 1745.4.1 線索二叉樹(shù)的概念 1745.4.2 線索二叉樹(shù)的種類 1755.4.3 中序線索二叉樹(shù)的建立和遍歷 1765.4.4 先序與后序線索二叉樹(shù) 1785.5 樹(shù)與森林 1805.5.1 樹(shù)的存儲(chǔ)表示 1805.5.2 森林與二叉樹(shù)的轉(zhuǎn)換 1845.5.3 樹(shù)與森林的深度優(yōu)先遍歷 1855.5.4 樹(shù)與森林的廣度優(yōu)先遍歷 1875.5.5 樹(shù)遍歷算法的應(yīng)用舉例 1885.6 Huffman樹(shù) 1905.6.1 帶權(quán)路徑長(zhǎng)度的概念 1905.6.2 Huffman樹(shù)的概念 1915.6.3 擴(kuò)展閱讀：最優(yōu)判定樹(shù) 1945.6.4 Huffman編碼 1965.7 堆 1985.7.1 小根堆和大根堆 1985.7.2 堆的建立 1995.7.3 堆的插入 2015.7.4 堆的刪除 2025.8 等價(jià)類與并查集 2025.8.1 等價(jià)關(guān)系與等價(jià)類 2025.8.2 確定等價(jià)類的方法 2035.8.3 并查集的定義及其實(shí)現(xiàn) 2035.8.4 并查集操作的分析和改進(jìn) 2055.9 擴(kuò)展閱讀：八皇后問(wèn)題與樹(shù)的剪枝 2075.9.1 八皇后問(wèn)題的提出 2075.9.2 八皇后問(wèn)題的狀態(tài)樹(shù) 2085.9.3 八皇后問(wèn)題算法 210小結(jié) 211習(xí)題 212第6章 圖 2166.1 圖的基本概念 2166.1.1 與圖有關(guān)的若干概念 2166.1.2 圖的基本操作 2196.2 圖的存儲(chǔ)結(jié)構(gòu) 2216.2.1 圖的鄰接矩陣表示 2216.2.2 圖的鄰接表表示 2256.2.3 鄰接矩陣表示與鄰接表表示的比較 2296.2.4 圖的鄰接多重表和十字鏈表表示 2306.3 圖的遍歷 2316.3.1 深度優(yōu)先搜索 2326.3.2 廣度優(yōu)先搜索 2346.3.3 連通分量 2356.3.4 雙連通圖 2376.3.5 有向圖的強(qiáng)連通分量 2386.4 最小生成樹(shù) 2406.4.1 最小生成樹(shù)求解和貪心法 2406.4.2 Kruskal算法 2426.4.3 Prim算法 2446.4.4 擴(kuò)展閱讀：其他建立最小生成樹(shù)的方法 2466.5 最短路徑 2486.5.1 非負(fù)權(quán)值的單源最短路徑 2486.5.2 擴(kuò)展閱讀：邊上權(quán)值為任意值的單源最短路徑問(wèn)題 2526.5.3 所有頂點(diǎn)之間的最短路徑 2546.5.4 無(wú)權(quán)值的最短路徑 2576.6 活動(dòng)網(wǎng)絡(luò) 2596.6.1 AOV網(wǎng)絡(luò)與拓?fù)渑判? 2596.6.2 AOE網(wǎng)絡(luò)與關(guān)鍵路徑法 262小結(jié) 267習(xí)題 268 第7章 查找 2737.1 查找的概念及簡(jiǎn)單查找方法 2737.1.1 查找的基本概念 2737.1.2 順序查找法 2747.1.3 折半查找法 2767.1.4 擴(kuò)展閱讀：次優(yōu)查找樹(shù) 2797.1.5 擴(kuò)展閱讀：斐波那契查找和插值查找 2827.1.6 擴(kuò)展閱讀：跳表 2837.2 二叉查找樹(shù) 2847.2.1 二叉查找樹(shù)的概念 2857.2.2 二叉查找樹(shù)的查找 2857.2.3 二叉查找樹(shù)的插入 2867.2.4 二叉查找樹(shù)的刪除 2887.2.5 二叉查找樹(shù)的性能分析 2897.3 AVL樹(shù) 2927.3.1 AVL樹(shù)的概念 2927.3.2 平衡化旋轉(zhuǎn) 2937.3.3 AVL樹(shù)的插入 2957.3.4 AVL樹(shù)的刪除 2967.3.5 AVL樹(shù)的性能分析 2997.4 B樹(shù) 3007.4.1 索引順序表與分塊查找 3007.4.2 多級(jí)索引結(jié)構(gòu)與m叉查找樹(shù) 3017.4.3 B樹(shù)的概念 3027.4.4 B樹(shù)上的查找 3047.4.5 B樹(shù)上的插入 3057.4.6 B樹(shù)上的刪除 3067.4.7 B 樹(shù) 3087.5 擴(kuò)展閱讀：其他查找樹(shù) 3117.5.1 紅黑樹(shù) 3117.5.2 伸展樹(shù) 3137.5.3 字典樹(shù) 3157.6 散列表及其查找 3177.6.1 散列的概念 3187.6.2 常見(jiàn)的散列函數(shù) 3187.6.3 解決沖突的開(kāi)地址法 3217.6.4 解決沖突的鏈地址法 3277.6.5 散列法分析 329小結(jié) 330習(xí)題 330第8章 排序 3358.1 排序的概念 3358.1.1 排序的相關(guān)概念 3358.1.2 排序算法的性能分析 3368.1.3 數(shù)據(jù)表的結(jié)構(gòu)定義 3378.2 插入排序 3388.2.1 直接插入排序 3388.2.2 基于靜態(tài)鏈表的直接插入排序 3398.2.3 折半插入排序 3418.2.4 希爾排序 3428.3 交換排序 3438.3.1 起泡排序 3448.3.2 快速排序 3458.3.3 快速排序的改進(jìn)算法 3488.4 選擇排序 3508.4.1 簡(jiǎn)單選擇排序 3508.4.2 錦標(biāo)賽排序 3518.4.3 堆排序 3528.5 歸并排序 3568.5.1 二路歸并排序的設(shè)計(jì)思路 3568.5.2 二路歸并排序的遞歸算法 3568.5.3 擴(kuò)展閱讀：基于鏈表的歸并排序算法 3588.5.4 擴(kuò)展閱讀：迭代的歸并排序算法 3598.6 基數(shù)排序 3618.6.1 基數(shù)排序 3628.6.2 MSD基數(shù)排序 3628.6.3 LSD基數(shù)排序 3648.7 內(nèi)排序算法的分析和比較 3678.7.1 排序方法的下界 3678.7.2 各種內(nèi)排序方法的比較 3688.8 外排序 3718.8.1 常用的外存儲(chǔ)器與緩沖區(qū) 3718.8.2 基于磁盤(pán)的外排序過(guò)程 3728.8.3 m路平衡歸并的過(guò)程 3748.8.4 初始?xì)w并段的生成 3788.8.5 最佳歸并樹(shù) 3818.8.6 磁帶歸并排序 382小結(jié) 385習(xí)題 386附錄A 實(shí)訓(xùn)作業(yè)要求與樣例 391A.1 實(shí)訓(xùn)作業(yè)要求 391A.2 實(shí)訓(xùn)作業(yè)樣例 392附錄B 詞匯索引 397參考文獻(xiàn) 405