第1章 數(shù)據(jù)結(jié)構(gòu)概述 1.1 數(shù)據(jù)結(jié)構(gòu)研究的問題 1.1.1 計算機解決實際問題的一般步驟 1.1.2 數(shù)據(jù)結(jié)構(gòu)學科概念及其所研究的內(nèi)容 1.1.3 數(shù)據(jù)結(jié)構(gòu)的建模舉例 1.2 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念 1.2.1 數(shù)據(jù)的有關(guān)概念 1.2.2 數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語 1.2.3 數(shù)據(jù)類型的概念 1.3 算法與算法性能分析 1.3.1 算法概念及特點 1.3.2 算法的設(shè)計要求 1.3.3 算法的性能分析 1.4 數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介 習題 第2章 線性表 2.1 線性表的類型定義 2.1.1 線性表的概念與邏輯結(jié)構(gòu) 2.1.2 線性表的ADT定義 2.2 線性表的順序存儲結(jié)構(gòu)及其算法實現(xiàn) 2.2.1 線性表的順序存儲結(jié)構(gòu) 2.2.2 順序表的基本算法實現(xiàn) 2.2.3 順序表應(yīng)用舉例 2.3 線性表的鏈式存儲與算法實現(xiàn) 2.3.1 單鏈表存儲結(jié)構(gòu) 2.3.2 單鏈表基本運算的實現(xiàn) 2.3.3 雙向鏈表 2.3.4 循環(huán)鏈表 2.3.5 靜態(tài)鏈表 2.3.6 單鏈表應(yīng)用舉例 習題 第3章 棧和隊列 3.1 棧 3.1.1 棧的概念及ADT定義 3.1.2 棧的存儲表示與算法實現(xiàn) 3.2 棧的應(yīng)用舉例 3.3 隊列 3.3.1 隊列的定義及ADT定義 3.3.2 隊列的存儲結(jié)構(gòu)及算法實現(xiàn) 習題 第4章 串 4.1 串的概念及其ADT定義 4.1.1 串的基本概念及術(shù)語 4.1.2 串的ADT定義 4.2 串的定長順序存儲及基本運算 4.2.1 串的定長順序存儲表示及其算法實現(xiàn) 4.2.2 定長順序串的基本運算 4.3 串的堆存儲結(jié)構(gòu)及算法實現(xiàn) 4.3.1 串的堆存儲結(jié)構(gòu) 4.3.2 堆串的算法實現(xiàn) 4.4 串的匹配算法 4.4.1 簡單匹配算法 4.4.2 KMP匹配算法 4.4.3 串的其他存儲映像 習題 第5章 數(shù)組與廣義表 5.1 數(shù)組 5.1.1 數(shù)組類型與存儲結(jié)構(gòu) 5.1.2 數(shù)組的內(nèi)存映像 5.2 特殊矩陣的壓縮存儲 5.2.1 對稱矩陣 5.2.2 三角矩陣 5.2.3 帶狀矩陣 5.3 稀疏矩陣 5.3.1 稀疏矩陣的三元組存儲結(jié)構(gòu)與矩陣的轉(zhuǎn)置和乘法 5.3.2 稀疏矩陣的十字鏈表存儲與矩陣的加法和減法 5.4 廣義表 5.4.1 廣義表的概念與ADT定義 5.4.2 廣義表的存儲 5.4.3 廣義表的基本操作算法 5.4.4 廣義表的應(yīng)用舉例 習題 第6章 二叉樹 6.1 二叉樹的概念與性質(zhì) 6.1.1 二叉樹的定義及相關(guān)術(shù)語 6.1.2 二叉樹的性質(zhì) 6.2 二叉樹的存儲結(jié)構(gòu)與創(chuàng)建算法 6.2.1 二叉樹的存儲結(jié)構(gòu) 6.2.2 二叉樹的創(chuàng)建算法 6.3 二叉樹的遍歷算法及其應(yīng)用 6.3.1 二叉樹的遞歸遍歷算法 6.3.2 二叉樹的非遞歸遍歷算法 6.3.3 二叉樹遍歷算法的應(yīng)用 6.3.4 由遍歷序列恢復(fù)二叉樹 6.4 線索二叉樹 6.4.1 線索二叉樹的定義及結(jié)構(gòu) 6.4.2 線索二叉樹的基本操作算法 6.5 哈夫曼樹 6.5.1 哈夫曼樹的概念與構(gòu)造算法 6.5.2 哈夫曼的應(yīng)用 習題 第7章 樹與森林 7.1 樹的概念與ADT定義 7.1.1 樹的定義及其相關(guān)術(shù)語 7.1.2 樹的ADT定義 7.1.3 樹與森林的性質(zhì) 7.2 樹與森林的存儲結(jié)構(gòu) 7.3 樹、森林與二叉樹的轉(zhuǎn)換 7.3.1 樹轉(zhuǎn)換成二叉樹 7.3.2 森林轉(zhuǎn)換成二叉樹 7.3.3 二叉樹轉(zhuǎn)換成樹或森林 7.4 樹和森林的遍歷 7.4.1 樹的遍歷 7.4.2 森林的遍歷 7.5 樹的應(yīng)用 7.5.1 集合的表示 7.5.2 求等價類問題 習題 第8章 圖 8.1 圖的基本概念與類型定義 8.1.1 圖的概念與相關(guān)術(shù)語 8.1.2 圖的ADT定義 8.2 圖的存儲表示與創(chuàng)建算法 8.2.1 鄰接矩陣存儲表示與創(chuàng)建算法 8.2.2 鄰接表存儲表示與創(chuàng)建算法 8.2.3 有向圖的十字鏈表存儲表示與創(chuàng)建算法 8.2.4 無向圖的鄰接多重表存儲表示 8.3 圖的遍歷算法 8.3.1 深度優(yōu)先搜索算法 8.3.2 廣度優(yōu)先搜索算法 8.4 圖的連通性 8.4.1 無向圖的連通性 8.4.2 有向圖的連通性 8.4.3 生成樹和生成森林 8.4.4 關(guān)結(jié)點和重連通分量 8.5 最小生成樹 8.5.1 最小生成樹的概念 8.5.2 構(gòu)造最小生成樹的Prim算法 8.5.3 構(gòu)造最小生成樹的Kruskal算法 8.6 最短路徑問題 8.6.1 從一個源點到其他各頂點的最短路徑 8.6.2 每一對頂點之間的最短路徑 8.7 有向無環(huán)圖及其應(yīng)用 8.7.1 有向無環(huán)圖的概念 8.7.2 AOV網(wǎng)與拓撲排序 8.7.3 AOE網(wǎng)與關(guān)鍵路徑 習題 第9章 查找 9.1 查找概述 9.1.1 查找表的有關(guān)概念 9.1.2 查找表的類型說明 9.1.3 查找算法的性能分析 9.2 靜態(tài)查找表 9.2.1 靜態(tài)查找表的結(jié)構(gòu) 9.2.2 順序表的查找 9.2.3 有序表的查找 9.2.4 有序表的其他查找方法 9.2.5 靜態(tài)樹表的查找 9.3 動態(tài)查找表 9.3.1 二叉排序樹 9.3.2 平衡二叉樹(AVL樹) 9.3.3 B-樹和B+樹 9.4 哈希表查找 9.4.1 哈希表與哈希方法 9.4.2 哈希函數(shù)的常用構(gòu)造方法 9.4.3 處理沖突的方法 9.4.4 哈希表的查找分析 習題 第10章 排序 10.1 基本概念 10.2 插入排序 10.2.1 直接插入排序 10.2.2 折半插入排序 10.2.3 表插入排序 10.2.4 希爾排序 10.3 交換排序 10.3.1 冒泡排序 10.3.2 快速排序 10.4 選擇排序 10.4.1 簡單選擇排序 10.4.2 樹形選擇排序 10.4.3 堆排序(heap sort) 10.5 二路歸并排序 10.6 基數(shù)排序 10.6.1 多關(guān)鍵字排序 10.6.2 鏈式基數(shù)排序 10.6.3 計數(shù)排序 10.7 各種排序算法的比較 10.8 外排序 10.8.1 外部排序的方法 10.8.2 多路平衡歸并的實現(xiàn) 習題 參考文獻