數據結構與算法教程(C++版)

數據結構與算法教程(C++版)

《數據結構與算法教程(C++版)》是2012年出版的圖書,作者是唐寧九、游洪躍、孫界平、朱宏、楊秋輝

基本介紹

  • 書名:數據結構與算法教程(C++版)
  • ISBN:9787302280309
  • 頁數:378頁
  • 定價:39元
  • 出版社:清華大學出版社
  • 出版時間:2012年12月1日
  • 裝幀:平裝
  • 開本:16
  • 叢書名高等學校計算機課程規劃教材
圖書簡介,圖書前言,圖書目錄,

圖書簡介

本書結合C++面向對象程式設計的特點,構建了數據結構與算法,書中的所有算法都在Visual C++ 6.0、Visual C++2005、Visual C++2005 Express、Dev-C++和MinGW Developer Studio開發環境中進行了嚴格的測試,而且,在作者個人網頁上提供了大量的教學支持內容。
本書在內容組織上特別考慮了讀者的可接受性;在算法實現時,重點考慮了程式的可讀性;並且在習題、上機實驗或課程設計中進一步實現更強的功能。通過本書學習,讀者不但能迅速提高數據結構與算法的水平,還能提高C++程式設計的能力,經過適當的選擇,本書可以作為數據結構、數據結構與算法分析、數據結構與算法設計、數據結構與算法等課程的教材,本書可作為高等院校計算機及相關專業的教材,也可供其他從事軟體開發工作的讀者學習參考使用。

圖書前言

希望各位能夠抽出寶貴的時間將你對本教材的建議或意見,當然也可以發表對國內外的數據結構與算法課程教學的任何意見寄給作者,你的意見將是我們再版修訂教材的重要參考。
張衛華、彭駿、譚斌、李培宇、何凱霖、姜琳、聶清彬、黃維、鄒昌文、王文昌、周焯華、胡開文、沈潔、周德華與歐陽等人對本書做了大量的工作,包括提供資料,調試算法,參與了部分內容的編寫,在此特向他們表示感謝;作者還要感謝為本書提供直接或間接幫助的每一個朋友,由於你們熱情的幫助或鼓勵,激發了作者寫好本書的信心以及寫作熱情。
本書的出版要感謝清華大學出版社各位編輯及評審專家,由於他們為本書的出版傾注了大量熱情,也由於他們具有前瞻性的眼光才讓讀者有機會看到本書。
儘管作者有良好而負責任的嚴格態度,並做出了最大努力,但由於作者水平有限,書中難免有不妥之處,因此,敬請各位讀者不吝賜教,以便作者有一個提高的機會,並在再版時儘量採用你們的意見。

圖書目錄

第1章 緒論1
1.1 數據結構的概念和學習數據結構的必要性1
1.2 數據結構的基本概念2
1.2.1 數據2
1.2.2 數據元素和數據項2
1.2.3 數據結構2
1.3 抽象數據類型及其實現4
1.3.1 數據類型4
1.3.2 抽象數據類型(Abstract Data Type--ADT)4
1.3.3 C++的類和對象4
1.3.4 運算符重載6
1.3.5 有關C++的動態存儲分配9
1.3.6 C++的模板(template) 10
1.4 算法和算法分析11
1.4.1 算法11
1.4.2 算法分析12
??1.5 實用程式軟體包15
1.6 深入學習導讀19
1.7 習題119
第2章 線性表21
2.1 線性表的邏輯結構21
2.2 線性表的順序存儲結構23
2.3 線性表的鏈式存儲結構31
2.3.1 單鍊表31
2.3.2 循環鍊表39
2.3.3 雙向鍊表43
??2.3.4 在鍊表結構中保存當前位置和元素個數46
??2.4 實例研究: 一元多項式的表示55
2.5 深入學習導讀60
2.6 習題260
第3章 棧和佇列61
3.1 棧61
3.1.1 棧的基本概念61
3.1.2 順序棧62
3.1.3 鏈式棧67
3.2 佇列74
3.2.1 佇列的基本概念74
3.2.2 鏈佇列75
3.2.3 循環佇列--佇列的順序存儲結構79
??3.2.4 佇列套用--顯示二項式(a+b)?i的係數84
??3.3 實例研究: 表達式求值85
3.4 深入學習導讀88
3.5 習題389
第4章 串90
4.1 串類型的定義90
4.2 字元串的實現91
4.3 字元串模式匹配算法98
4.3.1 簡單字元串模式匹配算法98
???4.3.2 KMP字元串模式匹配算法99
???4.4 實例研究: 文本編輯104
4.5 深入學習導讀114
4.6 習題4114
第5章 數組和廣義表115
5.1 數組115
5.1.1 數組的基本概念115
5.1.2 數組的順序表116
???5.1.3 數組的類定義118
5.2 矩陣122
5.2.1 矩陣的定義和操作122
5.2.2 特殊矩陣123
5.2.3 稀疏矩陣128
5.3 廣義表139
5.3.1 基本概念139
??5.3.2 廣義表的存儲結構141
5.4 深入學習導讀151
5.5 習題5152
第6章 樹和二叉樹153
6.1 樹的基本概念153
6.1.1 樹的定義153
6.1.2 基本術語154
6.2 二叉樹155
6.2.1 二叉樹的定義155
6.2.2 二叉樹的性質157
6.2.3 二叉樹的存儲結構160
6.3 二叉樹遍歷168
6.3.1 遍歷的定義168
6.3.2 遍歷算法169
??6.3.3 二叉樹遍歷套用舉例175
6.4 線索二叉樹180
6.4.1 線索的概念180
??6.4.2 線索二叉樹的實現182
6.5 樹和森林190
6.5.1 樹的存儲表示190
??6.5.2 樹的顯示198
6.5.3 森林的存儲表示198
6.5.4 樹和森林的遍歷203
6.5.5 樹和森林與二叉樹的轉換206
6.6 哈夫曼樹與哈夫曼編碼208
6.6.1 哈夫曼樹的基本概念209
6.6.2 哈夫曼樹構造算法210
6.6.3 哈夫曼編碼210
??6.6.4 哈夫曼樹的實現212
???6.7 樹的計數216
???6.8 實例研究: 樹與等價關係218
6.9 深入學習導讀222
6.10 習題6222
第7章 圖224
7.1 圖的定義和術語224
7.2 圖的存儲表示228
7.2.1 鄰接矩陣228
7.2.2 鄰接表234
7.3 圖的遍歷242
7.3.1 深度優先搜尋242
7.3.2 廣度優先搜尋244
7.4 連通無向網的最小代價生成樹246
7.4.1 Prim算法246
7.4.2 Kruskal算法249
7.5 有向無環圖及套用252
7.5.1 拓撲排序253
7.5.2 關鍵路徑256
7.6 最短路徑260
7.6.1 單源點最短路徑問題260
7.6.2 所有頂點之間的最短路徑263
7.7 深入學習導讀265
7.8 習題7265
第8章 查找267
8.1 查找的基本概念267
8.2 靜態表的查找270
8.2.1 順序查找270
8.2.2 有序表的查找271
8.3 動態查找表274
8.3.1 二叉排序樹274
??8.3.2 二叉平衡樹285
??8.3.3 B-樹和B?+-樹310
8.4 散列表312
8.4.1 散列表的概念312
8.4.2 構造散列函式的方法313
8.4.3 處理衝突的方法313
??8.4.4 散列表的實現315
8.5 深入學習導讀320
8.6 習題8320
第9章 排序321
9.1 概述321
9.2 插入排序322
9.2.1 直接插入排序322
9.2.2 Shell排序324
9.3 交換排序325
9.3.1 起泡排序325
9.3.2 快速排序326
9.4 選擇排序329
9.4.1 簡單選擇排序330
9.4.2 堆排序331
9.5 歸併排序334
??9.6 基數排序338
9.6.1 多關鍵排序338
9.6.2 基數排序339
??9.7 各種內部排序方法討論341
??9.8 外部排序342
9.8.1 外部排序基礎342
9.8.2 外部排序的方法343
??9.9 實例研究: 各種排序算法運行時間測試344
9.10 深入學習導讀347
9.11 習題9347
?*第10章 檔案349
10.1 主存儲器和輔助存儲器349
10.2 各種常用檔案結構349
10.2.1 順序檔案349
10.2.2 索引檔案350
10.2.3 散列檔案351
10.2.4 VSAM檔案351
10.2.5 多關鍵字檔案352
10.3 深入學習導讀354
10.4 習題10354
第11章 算法設計與分析355
11.1 算法設計355
11.1.1 遞歸算法355
11.1.2 分治算法357
?*11.1.3 回溯算法358
11.2 算法分析361
11.2.1 遞歸分析361
?**11.2.2 利用生成函式進行分析362
11.3 深入學習導讀363
11.4 習題11364
附錄A 調和級數365
附錄B 課本的軟體包366
附錄C 實驗題目371
附錄D 課程設計項目372D1 算術表達式求值372
D2 簡單本文編輯器372
D3 壓縮軟體373
?**D4 公園導遊系統373
?*D5 專家系統套用--動物遊戲373
?*D6 詞典變位詞檢索系統374
附錄E 實驗報告格式375
附錄F 課程設計報告格式376
參考文獻377
第1章 緒論1
1.1 數據結構的概念和學習數據結構的必要性1
1.2 數據結構的基本概念2
1.2.1 數據2
1.2.2 數據元素和數據項2
1.2.3 數據結構2
1.3 抽象數據類型及其實現4
1.3.1 數據類型4
1.3.2 抽象數據類型(Abstract Data Type--ADT)4
1.3.3 C++的類和對象4
1.3.4 運算符重載6
1.3.5 有關C++的動態存儲分配9
1.3.6 C++的模板(template) 10
1.4 算法和算法分析11
1.4.1 算法11
1.4.2 算法分析12
??1.5 實用程式軟體包15
1.6 深入學習導讀19
1.7 習題119
第2章 線性表21
2.1 線性表的邏輯結構21
2.2 線性表的順序存儲結構23
2.3 線性表的鏈式存儲結構31
2.3.1 單鍊表31
2.3.2 循環鍊表39
2.3.3 雙向鍊表43
??2.3.4 在鍊表結構中保存當前位置和元素個數46
??2.4 實例研究: 一元多項式的表示54
2.5 深入學習導讀59
2.6 習題260
第3章 棧和佇列61
3.1 棧61
3.1.1 棧的基本概念61
3.1.2 順序棧62
3.1.3 鏈式棧67
3.2 佇列73
3.2.1 佇列的基本概念73
3.2.2 鏈佇列75
3.2.3 循環佇列--佇列的順序存儲結構79
??3.2.4 佇列套用--顯示二項式(a+b)?i的係數84
??3.3 實例研究: 表達式求值85
3.4 深入學習導讀88
3.5 習題388
第4章 串89
4.1 串類型的定義89
4.2 字元串的實現90
4.3 字元串模式匹配算法97
4.3.1 簡單字元串模式匹配算法97
???4.3.2 KMP字元串模式匹配算法98
???4.4 實例研究: 文本編輯103
4.5 深入學習導讀113
4.6 習題4113
第5章 數組和廣義表114
5.1 數組114
5.1.1 數組的基本概念114
5.1.2 數組的順序表115
???5.1.3 數組的類定義117
5.2 矩陣121
5.2.1 矩陣的定義和操作121
5.2.2 特殊矩陣122
5.2.3 稀疏矩陣127
5.3 廣義表138
5.3.1 基本概念138
??5.3.2 廣義表的存儲結構140
5.5 深入學習導讀150
5.6 習題5151
第6章 樹和二叉樹152
6.1 樹的基本概念152
6.1.1 樹的定義152
6.1.2 基本術語153
6.2 二叉樹154
6.2.1 二叉樹的定義154
6.2.2 二叉樹的性質156
6.2.3 二叉樹的存儲結構159
6.3 二叉樹遍歷166
6.3.1 遍歷的定義167
6.3.2 遍歷算法168
??6.3.3 二叉樹遍歷套用舉例174
6.4 線索二叉樹179
6.4.1 線索的概念179
??6.4.2 線索二叉樹的實現181
6.5 樹和森林188
6.5.1 樹的存儲表示188
??6.5.2 樹的顯示196
6.5.3 森林的存儲表示197
6.5.4 樹和森林的遍歷201
6.5.5 樹和森林與二叉樹的轉換204
6.6 哈夫曼樹與哈夫曼編碼206
6.6.1 哈夫曼樹的基本概念207
6.6.2 哈夫曼樹構造算法208
6.6.3 哈夫曼編碼208
??6.6.4 哈夫曼樹的實現210
???6.7 樹的計數213
???6.8 實例研究: 樹與等價關係216
6.9 深入學習導讀220
6.10 習題6220
第7章 圖222
7.1 圖的定義和述語222
7.2 圖的存儲表示226
7.2.1 鄰接矩陣226
7.2.2 鄰接表232
7.3 圖的遍歷240
7.3.1 深度優先搜尋240
7.3.2 廣度優先搜尋242
7.4 圖的最小代價生成樹244
7.4.1 Prim算法244
7.4.2 Kruskal算法247
7.5 有向無環圖及套用250
7.5.1 拓撲排序251
7.5.2 關鍵路徑253
7.6 最短路徑258
7.6.1 單源點最短路徑問題258
7.6.2 所有頂點之間的最短路徑261
7.8 深入學習導讀263
7.9 習題7263
第8章 查找265
8.1 查找的基本概念265
8.2 靜態表的查找268
8.2.1 順序查找268
8.2.2 有序表的查找269
8.3 動態查找表272
8.3.1 二叉排序樹272
??8.3.2 二叉平衡樹283
??8.3.3 B-樹和B?+-樹307
8.4 散列表310
8.4.1 散列表的概念310
8.4.2 構造散列函式的方法310
8.4.3 處理衝突的方法311
??8.4.4 散列表的實現312
8.5 深入學習導讀317
8.6 習題8318
第9章 排序319
9.1 概述319
9.2 插入排序320
9.2.1 直接插入排序320
9.2.1 Shell排序322
9.3 交換排序323
9.3.1 起泡排序323
9.3.2 快速排序324
9.4 選擇排序327
9.4.1 簡單選擇排序328
9.4.2 堆排序329
9.5 歸併排序332
?*9.6 基數排序336
9.6.1 多關鍵排序336
9.6.2 基數排序337
?*9.7 各種內部排序方法討論339
?*9.8 外部排序340
9.8.1 外部排序基礎340
9.8.2 外部排序的方法341
?*9.9 實例研究: 各種排序算法運行時間測試342
9.10 深入學習導讀345
9.11 習題9345
?*第10章 檔案347
10.1 主存儲器和輔助存儲器347
10.2 各種常用檔案結構347
10.2.1 順序檔案347
10.2.2 索引檔案348
10.2.3 散列檔案349
10.2.4 VSAM檔案349
10.2.5 多關鍵字檔案350
10.3 深入學習導讀352
10.4 習題10352
第11章 算法設計與分析353
11.1 算法設計353
11.1.1 遞歸算法353
11.1.2 分治算法355
?*11.1.3 回溯算法356
11.2 算法分析359
11.2.1 遞歸分析359
?**11.2.2 利用生成函式進行分析360
11.4 深入學習導讀361
11.5 習題11362附錄A 調和級數363附錄B 課本的軟體包364附錄C 實驗課目369附錄D 課程設計項目370D.1 算術表達式求值370
D.2 簡單本文編輯器370
D.3 壓縮軟體371
?**D.4 公園導遊系統371
?*D.5 專家系統套用--動物遊戲371
?*D.6 詞典變位詞檢索系統372附錄E 實驗報告格式373附錄F 課程設計報告格式374參考文獻375

相關詞條

熱門詞條

聯絡我們