本書是為“數據結構”課程編寫的教材。繫統地介紹了數據結構基礎理論知識及算法設計方法，前半部分從抽像數據類型角度討論了各種基本類型的數據結構及其應用，主要包括：線性表、棧和隊列、串、數組和廣義表、樹與二叉樹及圖。

●第1章緒論1.1數據結構的範疇1.1.1計算機處理問題的分類1.1.2非數值性問題的求解1.2數據結構發展的概況1.3數據結構相關的概念1.3.1數據的概念1.3.2結構的概念1.3.3類型的概念1.4算法描述與算法分析1.4.1算法的概念1.4.2算法描述1.4.3算法分析習題第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.4.1基於空間的比較2.4.2基於時間的比較習題第3章棧和隊列3.1棧3.1.1棧的類型定義3.1.2棧的存儲表示及操作實現3.1.3棧與遞歸問題3.2隊列3.2.1隊列的類型定義3.2.2隊列的存儲表示及操作實現習題第4章串4.1串的類型定義4.1.1串的定義4.1.2串的抽像數據類型4.2串的存儲表示及操作實現4.2.1定長順序存儲表示4.2.2堆分配存儲表示4.2.3串的塊鏈存儲表示4.3串的模式匹配4.3.1簡單的模式匹配方法——BF算法4.3.2改進的模式匹配方法——KMP算法習題第5章數組和廣義表5.1數組5.1.1數組的類型定義5.1.2數組的順序表示及操作實現5.2矩陣的壓縮存儲5.2.1特殊矩陣的壓縮存儲5.2.2稀疏矩陣的壓縮存儲5.3廣義表5.3.1廣義表的類型定義5.3.2廣義表的鏈式表示及操作實現習題第6章樹和二叉樹6.1樹6.1.1樹的類型定義6.1.2樹的存儲表示及操作實現6.2二叉樹6.2.1二叉樹的類型定義6.2.2二叉樹的重要性質6.2.3二叉樹的存儲表示及操作實現6.2.4線索二叉樹6.3樹和森林與二叉樹的轉換6.3.1樹與二叉樹的轉換6.3.2森林與二叉樹的轉換6.4哈夫曼樹及其應用6.4.1哈夫曼樹6.4.2哈夫曼編碼習題第7章圖7.1圖的類型定義7.1.1圖的定義7.1.2圖的抽像數據類型7.1.3圖的遍歷7.2圖的存儲表示與操作實現7.2.1鄰接矩陣7.2.2鄰接表7.2.3十字鏈表7.2.4鄰接多重表7.2.5圖的操作實現7.3圖的連通性及其應用7.3.1無向圖的連通分量7.3.2生成樹和生成森林7.3.3最小生成樹7.4有向無環圖及其應用7.4.1拓撲排序7.4.2關鍵路徑7.5最短路徑7.5.1單源最短路徑7.5.2其他最短路徑習題第8章查找8.1查找的基本概念8.2靜態查找表8.2.1靜態查找表的類型定義8.2.2順序表的查找8.2.3有序表的查找8.2.4索引順序表的查找8.3動態查找表8.3.1動態查找表的類型定義8.3.2二叉排序樹和平衡二叉樹8.3.3B-樹、B+樹和鍵樹8.4哈希表8.4.1哈希表的定義8.4.2哈希函數的構造8.4.3處理衝突的方法8.4.4哈希表上的查找習題第9章排序9.1排序的基本概念9.2插入排序9.2.1直接插入排序9.2.2希爾排序9.3交換排序9.3.1冒泡排序9.3.2快速排序9.4選擇排序9.4.1簡單選擇排序9.4.2堆排序9.5歸並排序9.5.12路歸並排序9.5.2歸並排序9.6基數排序9.6.1多關鍵字排序9.6.2鏈式基數排序9.7排序方法比較習題第10章文件10.1文件的基本概念10.2順序文件10.2.1順序文件的查找10.2.2順序文件的修改10.2.3順序文件的特點10.3索引文件10.3.1索引文件的分類10.3.2索引文件的存儲10.3.3索引文件的操作10.3.4利用查找表建立多級索引10.4索引順序文件10.4.1ISAM文件10.4.2VSAM文件10.5哈希文件10.5.1哈希文件的操作10.5.2哈希文件的特點10.6多關鍵字文件10.6.1多重表文件10.6.2倒排文件10.7文件綜合舉例習題第11章課程實驗11.1實驗概述11.1.1教學目的11.1.2實驗步驟11.2實驗內容11.2.1線性表11.2.2棧和隊列11.2.3串11.2.4數組和廣義表11.2.5樹和二叉樹11.2.6圖11.2.7查找11.2.8排序附錄習題參考答案

本書繫統地介紹數據結構基礎理論知識及算法設計，第1~7章從抽像數據類型的角度討論各種基本類型的數據結構及其應用，主要包括線性表、棧和隊列、串、數組和廣義表、樹和二叉樹及圖； 第8章和第9章主要討論查找和排序的各種實現方法及其綜合比較； 第10章介紹不同類型文件的基本操作方法； 第11章介紹數據結構課程實驗的目的、步驟及內容； 附錄給出全書習題的參考答案。全書采用類C語言作為數據結構和算法的描述語言，隨書配備電子教案，以及第11章實驗的源代碼。本書在內容選取上符合人纔培養目標的要求及教學規律和認知規律，在組織編排上體現“先理論、後應用、理論與應用相結合”的原則，並兼顧學科的廣度和深度，力求適用面廣。本書具有結構嚴謹、層次清楚、概念準確、深入淺出、描述清晰等特點。本書可作為計算機類專業和信息類相關專業的本科或專科教材，也可供從事計算機工程與應用工作的科技工作者參考。

彭波 主編 著

“數據結構”課程是計算機、電子信息類及相關專業的專業基礎。它在整個課程體繫中處於承上啟下的核心地位： 一方面擴展和深化在離散數學、程序設計語言等課程學到的基本技術和方法； 另一方面為進一步學習操作繫統、編譯原理、數據庫等專業知識奠定堅實的理論與實踐基礎。本課程在教給學生數據結構設計和算法設計的同時，培養學生的抽像思維能力、邏輯推理能力和形式化思維方法，增強分析問題、解決問題和總結問題的能力，更重要的是培養專業興趣，樹立創新意識。本書在內容選取上符合人纔培養目標的要求及教學規律和認知規律，在組織編排上體現“先理論、後應用、理論與應用相結合”的原則，並兼顧學科的廣度和深度，力求適用面廣泛。全書共分11章。第1章綜述數據、數據結構和抽像數據類型等基本概念及算法描述與分析方法； 第2~7章主要從抽像數據類型的角度分別討論線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖等基本類型的數據結構及其等