《數據結構（C語言描述）（第3版）》是2019年7月電子工業出版社出版的圖書，作者是王曉東。
基本介紹
- 書名：數據結構（C語言描述）（第3版）
- 作者：王曉東
- ISBN：9787121344428
- 頁數：260頁
- 定價：49元
- 出版社：電子工業出版社
- 出版時間：2019年7月
- 開本：16開
內容簡介,目錄,
內容簡介
本書是國家精品課程教材，以教育部計算機科學與技術教學指導委員會發布的高等學校計算機科學與技術本科專業規範”為依據，以基本數據結構為知識單元而編寫。全書共分12章，包括引論、表、棧、佇列、排序與選擇、樹、圖、集合、符號表、字典、優先佇列、並查集等。 全書採用C語言作為描述語言，內容豐富，敘述簡明，理論與實踐並重，每章設有套用舉例和算法實驗題，並為任課教師免費提供電子課件和課程實驗用數據。 讀者對象：可作為高等學校計算機、電子信息、信息與計算科學、信息管理與信息系統等專業的數據結構課程教材，也適合工程技術人員和自學者學習參考。
目錄
第1 章 引論 ············································································································································1
1.1 算法及其複雜性的概念 ··········································································································1
1.1.1 算法與程式 ························································································································1
1.1.2 算法複雜性的概念 ·············································································································1
1.1.3 算法複雜性的漸近性態·······································································································3
1.2 算法的表達與數據表示 ··········································································································5
1.2.1 問題求解 ···························································································································5
1.2.2 表達算法的抽象機制 ··········································································································5
1.3 抽象數據類型 ··························································································································8
1.3.1 抽象數據類型的基本概念 ···································································································8
1.3.2 使用抽象數據類型的好處 ···································································································9
1.4 數據結構、數據類型和抽象數據類型 ··············································································· 10
1.5 用C 語言描述數據結構與算法 ··························································································· 11
1.5.1 變數和指針 ······················································································································ 11
1.5.2 函式與參數傳遞 ·············································································································· 12
1.5.3 結構 ······························································································································· 13
1.5.4 動態存儲分配 ················································································································· 14
1.6 遞歸 ········································································································································ 15
1.6.1 遞歸的基本概念 ·············································································································· 15
1.6.2 間接遞歸 ························································································································ 17
本章小結 ········································································································································· 18
習題1 ·············································································································································· 18
算法實驗題1 ·································································································································· 19
第2 章 表 ············································································································································· 21
2.1 表的基本概念 ······················································································································· 21
2.2 用數組實現表 ······················································································································· 22
2.3 用指針實現表 ······················································································································· 26
2.4 用間接定址方法實現表 ······································································································· 30
2.5 用游標實現表 ······················································································································· 32
2.6 循環鍊表 ································································································································ 37
2.7 雙鍊表 ···································································································································· 39
2.8 表的搜尋游標 ······················································································································· 43
2.8.1 用數組實現表的搜尋游標 ································································································ 43
2.8.2 單循環鍊表的搜尋游標···································································································· 44
VI
2.9 套用舉例 ································································································································ 45
本章小結 ········································································································································· 47
習題2 ·············································································································································· 47
算法實驗題2 ·································································································································· 49
第3 章 棧 ············································································································································· 52
3.1 棧的基本概念 ······················································································································· 52
3.2 用數組實現棧 ······················································································································· 53
3.3 用指針實現棧 ······················································································································· 55
3.4 套用舉例 ································································································································ 57
本章小結 ········································································································································· 60
習題3 ·············································································································································· 60
算法實驗題3 ·································································································································· 62
第4 章 佇列 ········································································································································· 64
4.1 佇列的基本概念 ··················································································································· 64
4.2 用指針實現佇列 ··················································································································· 64
4.3 用循環數組實現佇列 ··········································································································· 67
4.4 套用舉例 ································································································································ 70
本章小結 ········································································································································· 74
習題4 ·············································································································································· 74
算法實驗題4 ·································································································································· 75
第5 章 排序與選擇算法 ····················································································································· 78
5.1 簡單排序算法 ······················································································································· 78
5.1.1 冒泡排序算法 ················································································································· 79
5.1.2 插入排序算法 ················································································································· 79
5.1.3 選擇排序算法 ················································································································· 80
5.1.4 簡單排序算法的計算複雜性 ····························································································· 80
5.2 快速排序算法 ······················································································································· 81
5.2.1 算法基本思想及實現 ······································································································· 81
5.2.2 算法的性能 ····················································································································· 82
5.2.3 隨機快速排序算法 ·········································································································· 83
5.2.4 非遞歸快速排序算法 ······································································································· 83
5.2.5 三數取中劃分算法 ·········································································································· 84
5.2.6 三劃分快速排序算法 ······································································································· 85
5.3 合併排序算法 ······················································································································· 86
5.3.1 算法基本思想及實現 ······································································································· 86
5.3.2 對基本算法的改進 ·········································································································· 87
5.3.3 自底向上的合併排序算法 ································································································ 88
5.3.4 自然合併排序算法 ·········································································································· 88
5.3.5 鍊表結構的合併排序算法 ································································································ 89
5.4 線性時間排序算法 ··············································································································· 90
VII
5.4.1 計數排序算法 ················································································································· 90
5.4.2 桶排序算法 ····················································································································· 91
5.4.3 基數排序算法 ················································································································· 92
5.5 中位數與第k 小元素 ············································································································ 94
5.5.1 平均情況下的線性時間選擇算法 ······················································································ 94
5.5.2 最壞情況下的線性時間選擇算法 ······················································································ 95
5.6 套用舉例 ································································································································ 98
本章小結 ······································································································································· 100
習題5 ············································································································································ 100
算法實驗題5 ································································································································ 101
第6 章 樹 ··········································································································································· 104
6.1 樹的定義 ······························································································································ 104
6.2 樹的遍歷 ······························································································································ 106
6.3 樹的表示法 ·························································································································· 108
6.3.1 父結點數組表示法 ········································································································ 108
6.3.2 兒子鍊表表示法 ············································································································ 108
6.3.3 左兒子右兄弟表示法 ····································································································· 108
6.4 二叉樹的基本概念 ············································································································· 109
6.5 二叉樹的運算 ······················································································································ 111
6.6 二叉樹的實現 ······················································································································ 112
6.6.1 二叉樹的順序存儲結構··································································································· 112
6.6.2 二叉樹的結點度表示法··································································································· 113
6.6.3 用指針實現二叉樹 ········································································································· 113
6.7 線索二叉樹 ··························································································································· 118
6.8 二叉搜尋樹 ··························································································································· 119
6.9 線段樹 ·································································································································· 128
6.10 序列樹 ································································································································ 134
6.11 套用舉例 ···························································································································· 142
本章小結 ······································································································································· 147
習題6 ············································································································································ 147
算法實驗題6 ································································································································ 149
第7 章 散列表 ··································································································································· 154
7.1 集合的基本概念 ················································································································· 154
7.1.1 集合的定義和記號 ········································································································ 154
7.1.2 定義在集合上的基本運算 ······························································································ 155
7.2 簡單集合的實現方法 ········································································································· 156
7.2.1 用位向量實現集合 ········································································································ 156
7.2.2 用鍊表實現集合 ············································································································ 158
7.3 散列技術 ······························································································································ 161
7.3.1 符號表 ·························································································································· 161
VIII
7.3.2 開散列 ·························································································································· 163
7.3.3 閉散列 ·························································································································· 164
7.3.4 散列函式及其效率 ········································································································ 168
7.3.5 閉散列的重新散列技術·································································································· 169
7.4 套用舉例 ······························································································································ 170
本章小結 ······································································································································· 171
習題7 ············································································································································ 172
算法實驗題7 ································································································································ 173
第8 章 優先佇列 ······························································································································· 176
8.1 優先佇列的定義 ················································································································· 176
8.2 優先佇列的簡單實現 ········································································································· 177
8.3 優先權樹和堆 ····················································································································· 177
8.4 用數組實現堆 ····················································································································· 179
8.5 可並優先佇列 ····················································································································· 181
8.5.1 左偏樹的定義 ··············································································································· 182
8.5.2 用左偏樹實現可並優先佇列 ··························································································· 182
8.6 套用舉例 ······························································································································ 185
本章小結 ······································································································································· 190
習題8 ············································································································································ 190
算法實驗題8 ································································································································ 191
第9 章 並查集 ··································································································································· 194
9.1 並查集的定義及其簡單實現 ····························································································· 194
9.2 用父結點數組實現並查集 ································································································· 195
9.3 套用舉例 ······························································································································ 198
本章小結 ······································································································································· 201
習題9 ············································································································································ 201
算法實驗題9 ································································································································ 202
第10 章 圖 ········································································································································· 205
10.1 圖的基本概念 ··················································································································· 205
10.2 抽象數據類型圖 ··············································································································· 208
10.3 圖的表示法 ························································································································ 209
10.5.3 用鄰接表實現賦權有向圖 ···························································································· 218
10.5.4 用鄰接表實現賦權無向圖 ···························································································· 221
10.6 圖的遍歷 ···························································································································· 222
10.6.1 廣度優先搜尋 ·············································································································· 222
10.6.2 深度優先搜尋 ·············································································································· 224
