數(shù)據(jù)結構

第一章 緒論 1.1 為什么要學習數(shù)據(jù)結構 1.2 基本概念和術語 1.3 算法描述 1.4 算法分析 習 題第二章 線性表 2.1 線性表的概念 2.2 順序表 2.2.1 順序表的定義和特點 2.2.2 順序表的存儲及其操作 2.2.3 順序表的性能分析 2.3 單鏈表 2.3.1 單鏈表 2.3.2 單鏈表的操作 2.4 循環(huán)鏈表 2.5 雙向鏈表 2.6 鏈表的應用：多項式及其運算 2.6.1 多項式的表示 2.6.2 多項式的加法 習 題第三章 堆棧和隊列 3.1 堆棧的定義 3.2 堆棧的表示和實現(xiàn) 3.3 堆棧的應用 3.3.1 數(shù)制轉(zhuǎn)換 3.3.2 括弧匹配檢驗 3.3.3 迷宮問題 3.3.4 表達式求解問題 3.4 堆棧與遞歸 3.4.1 遞歸 3.4.2 遞歸與非遞歸的轉(zhuǎn)換 3.5 隊列 3.6 循環(huán)隊列 3.7 隊列的應用 習 題第四章 數(shù)組和串 4.1 數(shù)組的類型定義和基本運算 4.2 數(shù)組的存儲結構 4.3 特殊矩陣的壓縮存儲 4.3.1 對稱矩陣 4.3.2 三角矩陣 4.3.3 對角矩陣 4.3.4 稀疏矩陣 4.4 廣義表 4.4.1 廣義表(Lists，又稱列表)是線性表的推廣 4.4.2 廣義表的存儲結構和操作 4.5 串 4.5.1 串的定義 4.5.2 串的順序存儲結構 4.5.3 串的模式匹配算法 習題第五章 樹和二叉樹 5.1 樹 5.1.1 樹的定義和基本術語 5.1.2 樹的表示方法 5.1.3 樹的抽象數(shù)據(jù)類型 5.1.4 樹的存儲結構 5.2 二叉樹 5.2.1 二叉樹(Binary Tree)的定義 5.2.2 二叉樹的兩種特殊形態(tài) 5.2.3 二叉樹的性質(zhì) 5.2.4 二叉樹的抽象數(shù)據(jù)類型 5.2.5 二叉樹的存儲結構 5.2.6 二叉樹的二叉鏈存儲結構的實現(xiàn)及操作 5.3 二叉樹的遍歷 5.3.1 二叉樹的基本遍歷方法 5.3.2 二叉樹的層次遍歷方法 5.4 線索二叉樹 5.5 二叉樹、樹和森林 5.5.1 樹和二叉樹的轉(zhuǎn)換 5.5.2 森林和二叉樹的轉(zhuǎn)換 5.6 樹的應用 5.6.1 哈夫曼樹(Huffman) 5.6.2 哈夫曼樹的構造 5.6.3 哈夫曼樹的應用 5.6.4 哈夫曼樹的編碼問題設計與實現(xiàn) 習題第六章 圖 6.1 圖 6.1.1 圖的基本術語 6.1.2 圖的抽象數(shù)據(jù)類型ADT 6.2 圖的存儲結構 6.2.1 鄰接矩陣存儲結構 6.2.2 鄰接表存儲結構 6.2.3 十字鏈表存儲結構 6.2.4 鄰接多重表存儲結構 6.3 圖的實現(xiàn) 6.3.1 基于鄰接矩陣的圖基本操作實現(xiàn) 6.3.2 基于鄰接表的圖基本操作實現(xiàn) 6.4 圖的遍歷 6.4.1 深度優(yōu)先搜索 6.4.2 廣度優(yōu)先搜索 6.4.3 連通分量 6.5 最小生成樹 6.5.1 基本概念 6.5.2 Kruskal算法 6.5.3 Prim算法 6.5.4 最小生成樹應用 6.6 最短路徑 6.6.1 從某個源點到其他各頂點的最短路徑 6.6.2 每一對頂點之間的最短路徑 6.7 有向無環(huán)圖及其應用 6.7.1 基本概念 6.7.2 AOV網(wǎng)和拓撲排序 6.7.3 AOV網(wǎng)應用及實現(xiàn) 6.7.4 AOE網(wǎng)和關鍵路徑 6.7.5 關鍵路徑應用和實現(xiàn) 習題第七章 查找 7.1 查找的基本概念 7.2 靜態(tài)查找表 7.2.1 順序表的查找 7.2.2 有序表的查找 7.2.3 索引順序表的查找 7.3 動態(tài)查找表 7.3.1 二叉查找樹(二叉排序樹) 7.3.2 平衡二叉樹 7.4 哈希表 7.4.1 基本概念 7.4.2 哈希函數(shù)構造方法 7.4.3 處理沖突的方法 7.4.4 哈希表的查找及分析 習 題第八章 排序 8.1 排序的基本概念 8.2 插入排序(insertion sort) 8.2.1 直接插入排序 8.2.2 希爾排序(Shell sort) 8.3 選擇排序(selection sort) 8.3.1 簡單選擇排序 8.3.2 堆排序 8.4 交換排序 8.4.1 冒泡排序(bubble sort) 8.4.2 快速排序(quick sort) 8.5 歸并排序(merge sort) 8.6 基數(shù)排序(radix sort) 8.6.1 多關鍵字排序 8.6.2 鏈式基數(shù)排序 8.7 性能比較 習題第九章 文件 9.1 有關文件的基本概念 9.1.1 文件概念 9.1.2 文件分類 9.2 文件的邏輯結構及物理結構 9.2.1 文件的邏輯結構及操作 9.2.1 文件的存儲結構(亦稱物理結構) 9.3 順序文件 9.4 索引文件 9.5 ISAM文件和VSAM文件 9.5.1 ISAM文件 9.5.2 VSAM文件 9.6 散列文件 習題