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