基本介紹
- 書名：數據結構實用教程（C++版）
- ISBN： 9787121110764
- 頁數：280
- 定價：￥32.00元
- 出版社：電子工業出版社
- 出版時間： 2011-1-1
- 開本：16
內容介紹,圖書信息,目錄,第1章,第2章,第3章,第4章,第5章,第6章,第7章,前言,適用對象,
內容介紹
本書為國家級優秀教學團隊教學成果。根據教育部高等學校計算機科學與技術教學指導委員會制定的《高等學校計算機科學與技術專業發展戰略研究報告暨專業規範》編寫，首先介紹了數據結構的核心基礎知識——數據、數據類型、數據結構等基本概念和算法、算法的性能度量等知識，然後集中討論了四種基本的數據結構——集合、線性表、樹和圖，同時介紹了棧、佇列、串、數組以及廣義表等數據結構，最後介紹了排序和查找的幾種基礎算法及實現（用C 語言）。強調數據結構的工程套用，以模板的形式給出各種不同數據對象套用數據結構的多個實例，從而實現數據結構與工程套用的有機結合。
圖書信息
主編： 萬健
副主編：王立波 趙葆華 吳志芳
策劃編輯：章海濤
責任編輯：章海濤
特約編輯：曹劍鋒
印刷：北京市順義興華印刷廠
裝訂：三河市雙峰印刷裝訂有限公司
字數：446千字
目錄
第1章
緒 論
1.1 數據與數據類型 1
1.1.1 數據 1
1.1.2 數據的計算機表示與數據類型 2
1.1.3 抽象數據類型 5
1.2 數據結構 7
1.3 算法與算法分析 10
1.3.1 算法 10
1.3.2 算法的性能分析與度量 11
1.3.3 算法的時間複雜度 11
1.3.4 算法的空間複雜度 14
習題1 14
第2章
線性表
2.1 線性表的類型定義及結構特徵 15
2.2 線性表類型的實現——順序映像 17
2.3 線性表類型的實現——鏈式存儲映像 26
2.3.1 單鍊表26
2.3.2 其他形式的鍊表 35
2.4 線性表的套用 37
2.4.1 兩個有序表的合併 38
2.4.2 集合運算 40
2.4.3 一元多項式的表示和相加 42
習題2 47
第3章
其他線性結構
3.1 棧 48
3.1.1 棧的定義和基本操作 48
3.1.2 棧的存儲結構及操作實現 49
3.1.3 棧的套用舉例 55
3.2 佇列 68
3.2.1 佇列的定義和基本操作 68
3.2.2 佇列的存儲結構及操作實現 70
3.2.3 佇列套用舉例 77
3.3 串 83
3.3.1 串的基本概念和基本操作 83
3.3.2 串的存儲結構 85
3.4 數組 87
3.4.1 數組的定義和基本操作 87
3.4.2 數組的存儲表示 89
3.4.3 特殊矩陣的壓縮存儲 90
3.4.4 稀疏矩陣的壓縮存儲 92
3.5 廣義表 96
3.5.1 廣義表的基本概念和基本操作 97
3.5.2 廣義表的存儲結構 99
習題3 101
第4章
樹型結構
4.1 樹、森林的定義及基本術語 104
4.2 二叉樹 105
4.2.1 二叉樹的結構定義 105
4.2.2 幾種特殊形態的二叉樹 106
4.2.3 二叉樹的性質 107
4.2.4 二叉樹的存儲結構 108
4.2.5 二叉鍊表類的定義 110
4.2.6 二叉樹的遞歸遍歷 114
4.2.7 幾個二叉樹基本操作的例子 116
4.2.8 二叉樹的非遞歸遍歷 118
4.2.9 其他部分成員函式的實現 121
4.2.10 主函式（演示二叉鍊表類部分基本操作的執行結果） 123
4.2.11 線索二叉樹 126
4.3 樹與森林的再討論 129
4.3.1 樹的存儲結構 129
4.3.2 樹和森林的遍歷 132
4.4 樹型結構的套用 134
4.4.1 算術表達式求值 134
4.4.2 樹與等價問題 139
4.4.3 赫夫曼樹及赫夫曼編碼 145
習題4 154
第5章
圖
5.1 圖的定義和術語 156
5.2 圖的存儲結構 160
5.2.1 鄰接矩陣表示法 160
5.2.2 鄰接表表示法 162
5.2.3 十字鍊表表示法 164
5.2.4 鄰接多重表表示法 165
5.3 圖的基本操作 167
5.3.1 類的定義與實現 167
5.3.2 圖的遍歷 175
5.3.3 圖的連通性 181
5.4 最小生成樹 182
5.4.1 Prim算法 183
5.4.2 Kruskal算法 186
5.5 拓撲排序和關鍵路徑 187
5.5.1 有向無環圖 187
5.5.2 拓撲排序 188
5.5.3 關鍵路徑 190
5.6 最短路徑 194
5.6.1 單源最短路徑 194
5.6.2 每對頂點間的最短路徑 197
習題5 199
第6章
查 找
6.1 查找表的定義 201
6.2 靜態查找表 202
6.2.1 順序查找 202
6.2.2 折半查找 203
6.2.3 分塊查找 206
6.3 動態查找表 207
6.3.1 二叉排序樹 207
6.3.2 平衡二叉排序樹 213
6.3.3 B?樹和B+樹 221
6.4 哈希查找 226
6.4.1 哈希表的定義 226
6.4.2 哈希函式的構造方法 227
6.4.3 處理衝突的辦法 229
6.4.4 哈希表的查找及分析 231
6.4.5 哈希表的構建與查找算法 233
習題6 236
第7章
排 序
7.1 插入類排序 237
7.1.1 直接插入排序 238
7.1.2 折半插入排序 239
7.1.3 2-路插入排序 240
7.1.4 希爾排序 241
7.2 分劃類排序 242
7.2.1 冒泡排序 242
7.2.2 快速排序 243
7.3 選擇類排序 247
7.3.1 簡單選擇排序 247
7.3.2 樹形選擇排序 248
7.3.3 堆排序 249
7.4 歸併類排序 252
7.5 基數排序 254
7.5.1 多關鍵字的排序 254
7.5.2 基數排序 254
7.6 內部排序的比較 259
7.7 外部排序 262
7.7.1 外部存儲設備 262
7.7.2 外部排序的方法 262
7.7.3 敗者樹 263
習題7 264
參考文獻 269
前言
數據結構的概念最早由C.A.R.Hoare於1966年提出。在他的經典論文《數據結構筆記》中，他首次系統地論述了一組數據結構的構造、表示和操作等問題。1973年，D.E.Knuth在《電腦程式設計技巧》第一卷中給出了關於“信息結構”的系統論述。1976年，N.Wirth用“算法+數據結構=程式”這個公式表達了算法與數據結構的聯繫和它們在程式設計中的地位。從此確立了數據結構在計算機相關專業中的核心基礎課程地位。
“數據結構”是一門關於非數值數據在計算機中表示、變換及處理的課程。這裡指的“數據”實質是指計算機所能表示的各種不同數據對象的集合。對於每一具體的數據對象，其數據元素之間的關係都不是孤立的。數據元素之間的內在聯繫被稱為結構。從數據元素之間的關係特徵分析，各種數據對象的數據元素之間的關係僅呈以下四種結構之一：集合結構、線性結構、樹型結構、圖型結構。
“數據結構”課程的主要內容是針對以上四種結構，先從邏輯層面討論結構的關係特徵及抽象操作，再討論結構在計算機中的存儲表示（映像），並在存儲表示的基礎上給出相應結構的基本操作及實現，在此基礎上討論各種結構的套用。
目前的《數據結構》教材大體上按上述結構，在描述算法時大多採用類C或Pascal的算法描述語言。算法描述語言具有簡潔和更關注於算法本身的優點，但對許多剛學完電腦程式設計語言、編程能力尚且不足的學生，將這些算法轉變為可編譯運行的程式時，會碰到一些困難。
在長期的教學過程中，我們認為，“數據結構”是一門兼具理論性與實踐性的課程，在掌握程式設計語言後，本課程還是一門加強與提高學生程式設計能力的重要課程。因此，本書以傳統的數據結構的主要內容為主線，在充分討論結構的邏輯特徵與存儲表示的基礎上，用C++語言完成數據結構與描述和實現。同時，我們更加強調數據結構的套用，對不同的結構類型設計多個套用實例，每一算法或程式的編寫力求高效、易讀，並遵循程式設計的規範，從而幫助讀者將數據結構與工程套用有機結合起來。
本書另一個特點是將面向對象的方法引入到數據結構領域。面向對象技術不僅是一種程式設計方法學，而且是一種認識方法學，“數據結構”討論的正是數據的描述和處理，與面向對象的認知方法具有天然的聯繫。面向對象程式設計語言提供的封裝、繼承、多態和泛型程式設計等機制，為數據結構抽象數據類型的程式實現提供了很好的描述工具。本書以C++為程式設計語言，因此課程講授時，可針對學生的具體情況，重點複習一下類與對象、運算符重載、模板、STL等相關知識。
歷經30多年的發展，“數據結構”課程的主要討論範疇基本已取得共識。儘管計算機套用領域仍在不斷地擴大並產生了許多新的數據結構和算法，但數據結構最基本和最核心的內容還是各種經典教材中反覆強調的最具有代表性的那些知識。2006年，教育部高等學校計算機科學與技術教學指導委員會編制了《高等學校計算機科學與技術專業發展戰略研究報告暨專業規範》。其中，算法與數據結構涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多個知識單元，知識點包括：遞歸、面向對象程式設計的基本理論、基本數據結構（包括：堆疊、佇列、鍊表、哈希表串、數組和廣義表、樹型結構及套用、圖型結構及套用）、常用排序算法、常用查找技術、算法分析基礎等。2009年，教育部考試中心制定了全國碩士研究生入學統一考試關於“數據結構”科目的考試大綱。以上內容構成了我們編寫本書的大綱依據。
本書的編寫團隊是國家級優秀教學團隊的重要成員，在科學研究、工程軟體開發方面具有長期的工作經驗，特別是在長期的計算機專業教學中，針對教與學環節上的問題，形成了編寫《數據結構》教材的共識。歷經一年多的時間，編寫團隊反覆討論研究，精心選取案例，相信對讀者會有所幫助。
本書的編寫將做到“三個結合”的原則：與現代軟體開發技術相結合、與工程套用背景相結合、與提高學生的程式設計能力相結合，以C++為程式設計工具，避免傳統的採用偽算法語言造成的與實際程式設計相脫節的現象，突出數據組織與算法的具體實現以及工程問題的數據結構表達，從而實現將“數據結構”回歸為程式設計與軟體開發基礎課程的目標。
本書第1章由萬健編寫，第2、4章由王立波編寫，第3章由趙葆華編寫，第5～7章由周麗、徐翀、沈靜及吳志芳編寫，李衛明審閱並修改了全書的案例程式，任雪萍審閱了全書內容並編寫了教學課件。全書的內容由上述編寫者共同多次討論定稿。
適用對象
研究生本科教育、工科、計算機、程式語言
