第1章 緒論1.1 引言1.1.1 為什么要學習數據結構1.1.2 數據結構課程的主要內容1.2 基本概念和常用術語1.2.1 基本概念和術語1.2.2 數據結構1.2.3 抽象數據類型1.3 算法和算法分析1.3.1 算法的定義1.3.2 算法評價與分析1.3.3 算法效率的度量1.4 本章小結習題第2章 線性表2.1 線性表的邏輯結構2.1.1 線性表的定義2.1.2 線性表的基本運算2.2 線性表的順序存儲及運算實現2.2.1 線性表的順序存儲結構2.2.2 順序表上基本運算的實現2.3 線性表的鏈式存儲及運算實現2.3.1 單鏈表2.3.2 循環鏈表2.3.3 雙向鏈表2.3.4 靜態鏈表2.3.5 單鏈表應用舉例2.4 順序表和鏈表的比較2.5 本章小結習題第3章 棧和隊列3.1 棧3.1.1 棧的定義及其基本運算3.1.2 棧的存儲結構和基本運算的實現3.2 棧的應用舉例3.2.1 應用棧解決數制的轉換問題3.2.2 表達式求值3.3 棧與遞歸3.3.1 遞歸的概念3.3.2 棧與遞歸3.4 隊列3.4.1 隊列的定義和基本運算3.4.2 循環隊列——隊列的順序表示和實現3.4.3 鏈隊——隊列的鏈式表示和實現3.5 本章小結習題第4章 串4.1 串及其基本運算4.1.1 串的基本概念4.1.2 串的基本運算4.2 串的存儲結構4.2.1 串的順序存儲結構4.2.2 串的鏈式存儲結構4.3 串的模式匹配4.3.1 樸素的模式匹配算法4.3.2 KMP算法4.4 串的應用舉例4.5 本章小結習題第5章 數組和廣義表5.1 數組的概念5.1.1 數組的定義5.1.2 二維數組5.2 數組的順序存儲5.3 矩陣的壓縮存儲5.3.1 特殊矩陣5.3.2 稀疏矩陣5.4 廣義表5.4.1 廣義表的定義5.4.2 廣義表的存儲結構5.5 本章小結習題第6章 樹6.1 樹的概念和操作6.1.1 樹的定義6.1.2 樹的基本術語6.1.3 樹的基本操作6.1.4 樹的表示6.2 二叉樹6.2.1 二叉樹的概念6.2.2 二叉樹的性質6.2.3 二叉樹的存儲結構6.2.4 二叉樹的基本操作6.3 二叉樹的遍歷6.3.1 二叉樹的遍歷方法及遞歸實現6.3.2 二叉樹遍歷的非遞歸實現6.3.3 二叉樹的層次遍歷6.3.4 二叉樹遍歷算法的應用6.4 線索二叉樹6.4.1 線索二叉樹的基本概念6.4.2 線索二叉樹的基本操作6.5 樹和森林6.5.1 樹的存儲結構6.5.2 樹.森林與二叉樹的相互轉換6.5.3 樹和森林的遍歷6.6 二叉樹的應用6.6.1 霍夫曼樹及其應用6.6.2 表達式求值6.7 本章小結習題第7章 圖7.1 圖的定義和術語7.1.1 圖的基本概念7.1.2 圖的基本操作7.2 圖的存儲結構7.2.1 鄰接矩陣7.2.2 鄰接表7.2.3 鄰接多重表7.2.4 十字鏈表7.3 圖的遍歷7.3.1 深度優先搜索7.3.2 廣度優先搜索7.4 *小生成樹7.4.1 普里姆(Prim)算法7.4.2 克魯斯卡爾(Kruskal)算法7.5 有向無環圖及其應用7.5.1 拓撲排序7.5.2 關鍵路徑7.6 *短路徑7.6.1 從某個源點到其他各頂點的*短路徑7.6.2 每一對頂點之間的*短路徑7.7 本章小結習題第8章 查找8.1 基本概念8.2 線性表查找8.2.1 順序查找8.2.2 在順序存儲的有序表上查找8.3 樹表查找8.3.1 二叉排序樹8.3.2 平衡二叉樹8.3.3 B-樹8.4 散列表查找8.4.1 散列表8.4.2 常用的散列函數8.4.3 處理沖突的方法及散列表的構造8.4.4 散列表上的查找8.4.5 散列表上的刪除8.5 本章小結習題第9章 排序9.1 排序的基本概念及分類9.1.1 排序概念9.1.2 排序分類9.1.3 排序數據的數據類型說明9.2 插入排序9.2.1 直接插入排序9.2.2 折半插入排序9.2.3 希爾排序9.3 交換排序9.3.1 冒泡排序9.3.2 快速排序9.4 選擇排序9.4.1 簡單選擇排序9.4.2 堆排序9.5 歸并排序9.6 基數排序9.7 內部排序的比較與選擇9.7.1 內部排序算法性能比較9.7.2 內部排序算法的選擇9.8 外部排序簡介9.9 本章小結習題第10章 文件10.1 文件的基本知識10.1.1 文件的基本概念10.1.2 文件的邏輯結構與物理結構10.1.3 文件的操作10.2 順序文件10.2.1 存儲在順序存儲器上的順序文件10.2.2 存儲在直接存儲器上的順序文件10.3 索引文件10.3.1 索引文件構成10.3.2 索引文件的存儲10.3.3 索引文件的操作10.3.4 利用查找表建立多級索引10.4 索引順序文件10.4.1 ISAM文件10.4.2 VSAM文件10.5 散列文件10.5.1 散列文件的組織方式10.5.2 散列文件的操作10.5.3 散列文件的特點10.6 多關鍵字文件10.6.1 多關鍵字文件概念10.6.2 多關鍵字文件與其他文件的區別10.6.3 多重表文件10.6.4 倒排文件10.7 本章小結習題參考文獻