本書結合編者多年教學經驗，全面系統地介紹了數據結構的基本概念和知識，條理清晰、重點突出，內容循序漸進、深入淺出，既注重理論知識的講解，又注重算法設計的訓練，突出了理論性與實用性。全書共分9章，第1章作為全書的綜述和基礎，介紹了數據結構、算法的相關概念和算法分析方法等，其后各章分別討論了線性表、棧和隊列、串、多維數組和廣義表、樹和二叉樹、圖、數據結構的定義、表示和實現，*后兩章介紹了查找和內部排序的各種方法。在重點章節中，還結合精心編寫的應用實例，介紹了應用數據結構和算法解決實際問題及進行程序設計的方法，增強了讀者對基本知識的理解與掌握，有利于提高分析問題的能力和程序設計的能力。全書采用C語言作為數據結構和算法的描述語言。
本書可作為高等學校計算機類、信息類及相近專業本科生的數據結構課程教材，也可供從事計算機軟件開發和工程應用的人員學習和參考。
本書全面系統地介紹了數據結構的基本概念和知識，既注重理論知識，又注重算法設計的訓練。在重點章節中，結合精心編寫的應用實例，介紹了應用數據結構和算法解決實際問題和進行程序設計的方法，增強了讀者對基本知識的理解與掌握，更有利于分析問題能力和程序設計能力的提高。
數據結構是計算機程序設計的重要理論基礎，是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。數據結構的內容不僅是一般程序設計（特別是非數值性程序設計）的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序的重要基礎。它不僅是計算機專業的核心課程，也是其他理工專業的熱門選修課。在計算機的應用領域中，數據結構有著廣泛的應用。
計算機的程序是對信息進行加工處理，而信息的表示和組織又直接關系到處理信息程序的效率。隨著計算機的普及、信息量的增加、信息范圍的拓寬，使許多系統程序和應用程序的規模很大，結構又相當復雜，因此，為了編寫出一個好的程序，必須分析待處理對象的特征及各對象之間存在的關系。這就是數據結構這門課所要研究的問題。數據的結構，直接影響算法的選擇和效率。
本書共分9章，第1章介紹了數據結構的基本概念和算法分析的初步知識；第2章到第5章介紹了線性表、棧和隊列、串、多維數組和廣義表等線性結構的基本概念及常用算法的實現；第6章和第7章介紹了非線性結構的樹、二叉樹、圖等數據結構的存儲結構和不同存儲結構上的一些操作的實現；第8章介紹了各種查找表及查找方法；第9章介紹了各種排序算法。本書計劃學時為64學時左右，其中上機實習為12學時左右。教師可根據專業情況，選講或不講目錄中帶*的章節。
本書是作者根據自己的教學經驗總結，為地方本科院校計算機類學生編寫的教材。作者在教學過程中發現，大多數學生在初學數據結構時，容易誤解算法與程序之間的關系，經常會把書中的算法當作程序直接在編譯器上進行運行測試。為了解決這個問題，本書采用C語言作為數據結構和算法的描述語言，并且對關鍵的算法都安排了比較完整的C語言程序供學生上機實習參考，只要添加上主函數，程序即可運行。本書力求做到選材精練、敘述簡潔、通俗易懂，盡量避免抽象理論的介紹和復雜公式的推導。對各種數據結構均從實際出發，通過對實例的分析，使學生理解數據結構的基本概念。在每章后面帶有適量的習題，習題中編排了較多的選擇題和填空題，并配有習題答案，方便學生自學參考。
由于作者水平有限，書中難免會有不足之處，敬請廣大讀者批評指正。
編著者
第1章概論1
1.1什么是數據結構1
1.1.1數據和數據元素1
1.1.2數據對象與數據類型2
1.1.3數據結構2
1.2為什么要學習數據結構5
1.2.1學習數據結構的重要性5
1.2.2數據結構的應用舉例5
1.3算法和算法分析7
1.3.1什么是算法7
1.3.2算法的描述和設計7
1.3.3算法分析8
本章小結10
習題10
第2章線性表12
2.1線性表的基本概念12
2.1.1線性表的定義12
2.1.2線性表的基本操作13
2.2線性表的順序存儲13
2.2.1順序表13
2.2.2順序表的基本操作14
2.2.3順序存儲方式舉例17
2.3線性表的鏈式存儲20
2.3.1單鏈表的基本概念20
2.3.2單鏈表的基本操作22
2.3.3鏈式存儲舉例25
2.3.4循環鏈表28
2.3.5雙向鏈表30
2.3.6雙向循環鏈表332.3.7靜態鏈表34
2.4線性表順序存儲與鏈式存儲的比較35
2.5線性表的應用36
2.5.1約瑟夫問題36
2.5.2多項式加法38
2.5.3電文加密40
本章小結42
習題43
第3章棧和隊列45
3.1棧45
3.1.1棧的定義與基本操作45
3.1.2順序棧的存儲結構和操作的實現47
3.1.3鏈棧的存儲結構和操作的實現50
3.2棧的應用52
3.2.1數制轉換52
3.2.2括號匹配問題54
3.2.3子程序的調用55
3.2.4利用一個順序棧逆置一個帶頭節點的單鏈表56
3.2.5后綴表達式59
3.3隊列61
3.3.1隊列的定義與基本操作61
3.3.2鏈隊列的存儲結構和操作的實現62
3.3.3順序隊列的存儲結構和操作的實現64
3.4隊列的應用68
3.4.1打印楊輝三角形68
3.4.2迷宮問題： 尋找一條從迷宮入口到出口的最短路徑71
3.5遞歸74
3.5.1遞歸的定義與實現74
3.5.2遞歸消除77
本章小結81
習題81
第4章串85
4.1串的定義和基本操作85
4.1.1串的定義85
4.1.2串的基本操作87
4.2串的表示和實現88
4.2.1串的定長順序存儲88
4.2.2串的堆存儲結構91
4.2.3串的塊鏈存儲結構93
4.3串的模式匹配算法97
4.3.1基本的模式匹配算法97
4.3.2模式匹配的改進算法KMP算法100
本章小結102
習題102
第5章多維數組和廣義表104
5.1多維數組104
5.1.1多維數組的定義104
5.1.2數組的存儲結構105
5.2矩陣的壓縮存儲 106
5.2.1特殊矩陣106
5.2.2稀疏矩陣108
5.3廣義表 114
本章小結116
習題117
第6章樹和二叉樹118
6.1樹的概念與基本操作118
6.1.1樹的定義118
6.1.2樹的一些基本概念119
6.1.3樹的基本操作120
6.2二叉樹120
6.2.1二叉樹的定義和基本操作120
6.2.2二叉樹的性質121
6.2.3二叉樹的存儲結構123
6.3二叉樹的遍歷與線索化124
6.3.1二叉樹的遍歷124
6.3.2線索二叉樹127
6.3.3基于遍歷的應用與線索二叉樹的應用129
6.3.4標識符樹134
6.4樹和森林134
6.4.1樹的存儲結構134
6.4.2樹、森林和二叉樹之間的轉換137
6.4.3樹和森林的遍歷140
6.5哈夫曼樹及其應用142
6.5.1與哈夫曼樹相關的基本概念142
6.5.2哈夫曼樹的應用144
6.5.3哈夫曼編碼算法的實現146
*6.6樹的計數147
本章小結150
習題151
第7章圖154
7.1圖的基本概念154
7.1.1圖的定義154
7.1.2圖的相關術語155
7.2圖的存儲結構157
7.2.1鄰接矩陣表示法157
7.2.2鄰接表表示法159
7.3圖的遍歷163
7.3.1深度優先搜索法163
7.3.2廣度優先搜索法165
7.3.3非連通圖的遍歷167
7.4生成樹與最小生成樹167
7.4.1生成樹的概念167
7.4.2構造最小生成樹的普里姆(Prim)算法168
7.4.3構造最小生成樹的克魯斯卡爾(Kruskal)算法171
7.5最短路徑173
7.5.1從某個源點到其余各頂點的最短路徑174
7.5.2每一對頂點之間的最短路徑178
7.6拓撲排序181
7.7關鍵路徑184
本章小結190
習題190
第8章查找195
8.1查找的基本概念195
8.1.1查找表和查找195
8.1.2查找表的數據結構表示196
8.1.3平均查找長度ASL196
8.2線性表的查找196
8.2.1順序查找 196
8.2.2二分查找198
8.2.3分塊查找201
8.3樹表的查找203
8.3.1二叉排序樹203
*8.3.2平衡二叉樹208
*8.3.3B-樹212
8.4散列表的查找221
8.4.1散列表的概念221
8.4.2散列函數的構造方法222
8.4.3處理沖突的方法 223
8.4.4散列表上的運算 227
本章小結230
習題230
第9章排序232
9.1排序的基本概念232
9.1.1關鍵字與排序232
9.1.2排序的穩定性233
9.1.3排序方法的分類233
9.1.4排序算法性能評價233
9.1.5不同存儲方式的排序過程233
9.2插入排序234
9.2.1直接插入排序234
9.2.2希爾排序237
9.3交換排序239
9.3.1冒泡排序239
9.3.2快速排序(霍爾排序)240
9.4選擇排序244
9.4.1直接選擇排序244
9.4.2堆排序245
9.5歸并排序250
9.6基數排序253
9.6.1桶排序253
9.6.2多關鍵字的排序253
9.6.3鏈式基數排序254
9.7內部排序算法比較257
9.8外部排序簡介259
本章小結259
習題260
參考文獻263
新書資訊