資料結構與實訓(第3版)（簡體書）

全書共8章。第1章介紹了數據結構和算法的基本概念；第2～4章介紹了線性表、堆棧、隊列、串、數組等常用的線性結構；第5、6章介紹了非線性結構、樹形結構和圖狀結構；第7、8章介紹了兩種基本技術：查找和排序的常用算法。附錄A介紹了實訓的相關知識，包括實訓的步驟、實訓報告規范和實訓的環境。本書對每一種數據結構都詳細闡述了基本概念、各種不同的存儲結構以及在不同存儲結構上的主要算法的實現，并給出豐富的典型例題，以幫助讀者理解。

張紅霞，洛陽理工學院計算機系副教授。碩士，專業計算機科學軟件理論。教齡17年，講授過以下課程：C語言程序設計、數據結構、VB程序設計、數據庫原理及應用、編譯方法等。

第1章 概論t1
1．1 引言t1
1．1．1 什么是數據結構t1
1．1．2 數據結構研究什么t1
1．2 數據結構的基本概念t3
1．3 算法和算法的分析t4
1．3．1 算法及算法的描述t4
1．3．2 算法設計的要求t4
1．3．3 算法的分析t5
1．4 總結與提高t7
習題t8
第2章 線性表t11
2．1 線性表的定義及運算t11
2．1．1 線性表的定義t11
2．1．2 線性表的基本運算t11
2．2 線性表的順序存儲結構t12
2．2．1 順序表t12
2．2．2 順序表上基本運算的實現t13
2．3 線性表的鏈式存儲結構t16
2．3．1 單鏈表及其基本運算t16
2．3．2 循環鏈表t20
2．4 順序表與鏈表的比較t21
2．5 典型題例t22
2．6 實訓例題t24
2．6．1 實訓例題1：有序順序表的建立及查找t24
2．6．2 實訓例題2：多項式的表示和相加t27
2．7 總結與提高t31
2．7．1 主要知識點t31
2．7．2 提高題例t32
習題t33
實訓習題t35
第3章 堆棧和隊列t36
3．1 堆棧t36
3．1．1 堆棧的定義及基本運算t36
3．1．2 堆棧的順序存儲結構t36
3．1．3 堆棧的鏈式存儲結構t39
3．2 棧典型題例t42
3．3 隊列t43
3．3．1 隊列的定義及運算t43
3．3．2 隊列的順序存儲結構t44
3．3．3 隊列的鏈式存儲結構t46
3．4 隊列典型題例t48
3．5 實訓例題t50
3．5．1 實訓例題1：順序循環隊列的操作t50
3．5．2 實訓例題2：括號配對t52
3．6 總結與提高t56
3．6．1 主要知識點t56
3．6．2 提高題例t56
習題t58
實訓習題t60
第4章 串與數組t62
4．1 串及其基本運算t62
4．1．1 串的基本概念t62
4．1．2 串的基本運算t63
4．2 串的存儲結構t64
4．2．1 串的順序存儲t64
4．2．2 串的堆存儲結構t66
4．2．3 串的鏈式存儲t67
4．3 數組t68
4．3．1 數組的定義t68
4．3．2 一維數組、二維數組和多維數組t69
4．4 典型題例t70
4．5 實訓例題t71
4．5．1 實訓例題1：字符串操作t71
4．5．2 實訓例題2：二維數組t74
4．6 總結與提高t76
4．6．1 主要知識點t76
4．6．2 提高題例t77
習題t79
實訓習題t81
第5章 樹和二叉樹t82
5．1 樹t82
5．1．1 樹的基本概念t82
5．1．2 樹的基本操作t84
5．1．3 樹的存儲結構t85
5．2 二叉樹t88
5．2．1 二叉樹的定義及基本操作t88
5．2．2 二叉樹的性質t89
5．2．3 二叉樹的存儲結構t91
5．3 遍歷二叉樹t93
5．3．1 二叉樹的遍歷方法t93
5．3．2 二叉樹遍歷算法應用典型例題t102
5．4 樹和二叉樹的關系t104
5．4．1 樹轉換為二叉樹t104
5．4．2 樹的遍歷t105
5．5 哈夫曼樹及其應用t106
5．5．1 哈夫曼樹的定義及構造t106
5．5．2 哈夫曼樹的應用t109
5．6 典型題例t111
5．7 實訓例題t113
5．7．1 實訓例題1：根據順序存儲建立二叉鏈表，并對二叉樹進行先序、中序、后序遍歷t113
5．7．2 實訓例題2：設計哈夫曼編碼t116
5．8 總結與提高t121
5．8．1 主要知識點t121
5．8．2 提高題例t122
習題t124
實訓習題t126
第6章 圖t127
6．1 圖的定義和術語t127
6．1．1 圖的定義t127
6．1．2 圖的基本術語t127
6．1．3 圖的基本操作t129
6．2 圖的存儲結構t130
6．2．1 鄰接矩陣t130
6．2．2 鄰接表t132
6．2．3 鄰接矩陣和鄰接表的比較t135
6．3 圖的遍歷t135
6．3．1 連通圖的深度優先搜索t135
6．3．2 連通圖的廣度優先搜索t137
6．3．3 非連通圖的遍歷t139
6．4 小生成樹t139
6．4．1 生成樹及小生成樹t139
6．4．2 普里姆算法t140
6．4．3 克魯斯卡爾算法t141
6．5 短路徑t142
6．6 拓撲排序t145
6．7 典型題例t149
6．8 實訓例題t152
6．8．1 實訓例題1：圖的遍歷t152
6．8．2 實訓例題2：設計學習計劃t158
6．9 總結與提高t162
6．9．1 主要知識點t162
6．9．2 提高題例t162
習題t164
實訓習題t166
第7章 查找t168
7．1 基本概念t168
7．2 線性表的查找t168
7．2．1 順序查找t169
7．2．2 折半查找t170
7．2．3 分塊查找t172
7．3 二叉排序樹的查找t173
7．3．1 二叉排序樹的定義t173
7．3．2 二叉排序樹的查找算法t174
7．3．3 二叉排序樹的建立與插入t175
7．3．4 二叉排序樹的查找算法分析t177
7．4 哈希表的查找t178
7．4．1 哈希表的概念t178
7．4．2 哈希函數的構造方法t179
7．4．3 處理沖突的方法t181
7．4．4 哈希表上的運算t184
7．5 典型題例t186
7．6 實訓例題t189
7．6．1 實訓例題1：構造二叉排序樹t189
7．6．2 實訓例題2：哈希表的操作t192
7．7 總結與提高t197
7．7．1 主要知識點t197
7．7．2 提高題例t198
習題t200
實訓習題t201
第8章 排序t202
8．1 排序的基本概念t202
8．2 插入排序t202
8．2．1 直接插入排序t203
8．2．2 希爾排序t204
8．3 交換排序t206
8．3．1 冒泡排序t206
8．3．2 快速排序t207
8．4 選擇排序t209
8．4．1 直接選擇排序t209
8．4．2 堆排序t210
8．5 各種內部排序方法的比較t214
8．7 典型題例t215
8．8 實訓例題t217
8．8．1 實訓例題1：不同排序算法的比較t217
8．8．2 實訓例題2：學生成績名次表t225
8．9 總結與提高t231
8．9．1 主要知識點t231
8．9．2 提高題例t232
習題t233
實訓習題t236
附錄A 數據結構實訓指南t237