第1章 緒論 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)算機(jī)科學(xué)中的地位 1.3 算法 1.3.1 算法及其性質(zhì) 1.3.2 基本算法 1.3.3 算法的描述 1.4 算法分析 1.4.1 時(shí)間復(fù)雜度 1.4.2 空間復(fù)雜度 1.4.3 其他方面 習(xí)題 第2章 線性表 2.1 線性表的定義及其基本操作 2.1.1 線性表的定義 2.1.2 線性表的基本操作 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 2.2.1 順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造 2.2.2 幾種常見操作的實(shí)現(xiàn) 2.2.3 順序存儲(chǔ)結(jié)構(gòu)小結(jié) 2.3 線性鏈表及其操作 2.3.1 線性鏈表的構(gòu)造 2.3.2 線性鏈表的基本算法 2.4 循環(huán)鏈表及其操作 2.5 雙向鏈表及其操作 2.5.1 雙向鏈表的構(gòu)造 2.5.2 雙向鏈表的插入與刪除算法 2.6 鏈表的應(yīng)用舉例 2.6.1 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的一元多項(xiàng)式相加 2.6.2 打印文本文件的最后n行 習(xí)題 第3章 數(shù)組 3.1 數(shù)組的概念 3.2 數(shù)組的存儲(chǔ)結(jié)構(gòu) 3.3 矩陣的壓縮存儲(chǔ) 3.3.1 對(duì)稱矩陣的壓縮存儲(chǔ) 3.3.2 對(duì)角矩陣的壓縮存儲(chǔ) 3.4 稀疏矩陣的三元組表表示 3.4.1 稀疏矩陣的三元組表存儲(chǔ)方法 3.4.2 稀疏矩陣的轉(zhuǎn)置算法 3.4.3 稀疏矩陣的相加算法 3.4.4 稀疏矩陣的相乘算法 3.5 稀疏矩陣的鏈表表示 3.5.1 線性鏈表存儲(chǔ)方法 3.5.2 帶行指針向量的鏈表存儲(chǔ)方法 3.5.3 十字鏈表存儲(chǔ)方法 3.6 數(shù)組的應(yīng)用舉例 3.6.1 一元多項(xiàng)式的數(shù)組表示 3.6.2 n階魔方 習(xí)題 第4章 堆棧和隊(duì)列 4.1 堆棧的概念及其操作 4.1.1 堆棧的定義 4.1.2 堆棧的基本操作 4.2 堆棧的順序存儲(chǔ)結(jié)構(gòu) 4.2.1 順序堆棧的構(gòu)造 4.2.2 順序堆棧的基本算法 4.2.3 多個(gè)堆棧共享連續(xù)空間 4.3 堆棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 4.3.1 鏈接堆棧的構(gòu)造 4.3.2 鏈接堆棧的基本算法 4.4 堆棧的應(yīng)用舉例 4.4.1 符號(hào)匹配檢查 4.4.2 數(shù)制轉(zhuǎn)換 4.4.3 堆棧在遞歸中的應(yīng)用 4.4.4 表達(dá)式的計(jì)算 4.4.5 趣味游戲迷宮 4.5 隊(duì)列的概念及其操作 4.5.1 隊(duì)列的定義 4.5.2 隊(duì)列的基本操作 4.6 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 4.6.1 順序隊(duì)列的構(gòu)造 4.6.2 順序隊(duì)列的基本算法 4.6.3 循環(huán)隊(duì)列 4.7 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 4.7.1 鏈接隊(duì)列的構(gòu)造 4.7.2 鏈接隊(duì)列的基本算法 習(xí)題 第5章 廣義表 5.1 廣義表的基本概念 5.2 廣義表的存儲(chǔ)結(jié)構(gòu) 5.3 多元多項(xiàng)式的表示 習(xí)題 第6章 串 6.1 串的基本概念 6.1.1 串的定義 6.1.2 串的幾個(gè)概念 6.2 串的基本操作 6.3 串的存儲(chǔ)結(jié)構(gòu) 6.3.1 串的順序存儲(chǔ)結(jié)構(gòu) 6.3.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 6.4 串的幾個(gè)操作 習(xí)題 第7章 樹與二叉樹 7.1 樹的基本概念 7.1.1 樹的定義 7.1.2 樹的邏輯表示方法 7.1.3 基本術(shù)語 7.1.4 樹的性質(zhì) 7.1.5 樹的基本操作 7.2 樹的存儲(chǔ)結(jié)構(gòu) 7.2.1 多重鏈表表示法 7.2.2 三重鏈表表示法 7.3 二叉樹 7.3.1 二叉樹的定義 7.3.2 二叉樹的基本操作 7.3.3 兩種特殊形態(tài)的二叉樹 7.3.4 二叉樹的性質(zhì) 7.3.5 二叉樹與樹、樹林之間的轉(zhuǎn)換 7.4 二叉樹的存儲(chǔ)結(jié)構(gòu) 7.4.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 7.4.2 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 7.5 二叉樹與樹的遍歷 7.5.1 二叉樹的遍歷 7.5.2 由遍歷序列恢復(fù)二叉樹 7.5.3 二叉樹的等價(jià)性 7.5.4 樹和樹林的遍歷 7.5.5 基于二叉樹遍歷操作的算法舉例 7.6 線索二叉樹 7.6.1 線索二叉樹的構(gòu)造 7.6.2 線索二叉樹的利用 7.6.3 二叉樹的線索化 7.6.4 線索二叉樹的更新 7.7 二叉排序樹 7.7.1 二叉排序樹的定義 7.7.2 二叉排序樹的建立(插入) 7.7.3 在二叉排序樹中刪除結(jié)點(diǎn) 7.7.4 二叉排序樹的查找 7.8 平衡二叉樹 7.9 哈夫曼樹及其應(yīng)用 7.9.1 哈夫曼樹(Huffman)的概念 7.9.2 哈夫曼編碼 習(xí)題 第8章 圖 8.1 圖的基本概念 8.1.1 圖的定義和基本術(shù)語 8.1.2 圖的基本操作 8.2 圖的存儲(chǔ)方法 8.2.1 鄰接矩陣存儲(chǔ)方法 8.2.2 鄰接表存儲(chǔ)方法 8.2.3 有向圖的十字鏈表存儲(chǔ)方法 8.2.4 無向圖的多重鄰接表存儲(chǔ)方法 8.3 圖的遍歷 8.3.1 深度優(yōu)先搜索 8.3.2 廣度優(yōu)先搜索 8.3.3 連通分量 8.4 最小生成樹 8.4.1 普里姆算法 8.4.2 克魯斯卡爾算法 8.5 最短路徑 8.6 AOV網(wǎng)與拓?fù)渑判? 8.6.1 AOV網(wǎng) 8.6.2 拓?fù)渑判? 8.6.3 拓?fù)渑判蛩惴? 8.7 AOE網(wǎng)與關(guān)鍵路徑 8.7.1 AOE網(wǎng) 8.7.2 關(guān)鍵路徑 8.7.3 關(guān)鍵路徑的確定 習(xí)題 第9章 文件及查找 9.1 文件概述 9.1.1 文件的基本概念 9.1.2 文件的存儲(chǔ)介質(zhì) 9.1.3 文件的基本操作 9.2 順序文件 9.2.1 連續(xù)順序文件及其查找 9.2.2 鏈接順序文件及其查找 9.3 索引文件 9.3.1 稠密索引文件 9.3.2 非稠密索引分塊文件 9.3.3 多級(jí)索引文件 9.4 B-樹和B 樹 9.4.1 B-樹的基本概念 9.4.2 B-樹的基本操作 9.4.3 B 樹的基本概念 9.4.4 B 樹的基本操作 9.5 散列(hash)文件 9.5.1 概述 9.5.2 散列函數(shù)的幾種常見構(gòu)造方法 9.5.3 處理沖突的方法 9.5.4 散列文件的操作 9.5.5 散列法的平均查找長度 習(xí)題 第10章 內(nèi)排序 10.1 概述 10.1.1 排序的基本概念 10.1.2 排序的分類 10.2 插入排序 10.3 選擇排序 10.4 泡排序 10.5 謝爾排序 10.6 快速排序 10.7 堆積排序 10.7.1 堆積的定義 10.7.2 堆積排序算法 10.8 二路歸并排序 10.8.1 歸并子算法 10.8.2 一趟歸并掃描子算法 10.8.3 二路歸并排序算法 10.9 基數(shù)排序 10.10 各種內(nèi)排序方法的比較 10.10.1 穩(wěn)定性比較 10.10.2 復(fù)雜性比較 習(xí)題 第11章 外排序 11.1 概述 11.2 磁帶排序 11.2.1 多路平衡歸并排序法 11.2.2 多步歸并排序 11.3 初始?xì)w并段的合理分布與產(chǎn)生 11.3.1 初始?xì)w并段的合理分布 11.3.2 一種產(chǎn)生初始?xì)w并段的方法置換選擇排序 11.4 磁盤排序 習(xí)題 習(xí)題答案 參考文獻(xiàn)