 |
-- 會員 / 註冊 --
|
 |
|
|
|
數據結構與算法——理論與實踐 ( 簡體 字) |
| 作者：唐培和,徐奕奕 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 40360
詢問書籍請說出此書號！【缺書】
NT售價： 260 元 |
| 出版日：1/1/2015 |
| 頁數：416 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121244674 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：《數據結構與算法》作為一門獨立的課程始于1968年。那時在美國一些大學中，雖然把《數據結構》規定為一門課程，但對其范圍仍沒有明確界定。當時，“數據結構”幾乎與圖論、表、樹的理論為同義語。由于數據必須在計算機中進行處理，因此不但應考慮數據本身的數學性質，而且必須考慮數據的存儲結構。隨著數據庫系統的不斷發展，在數據結構課程中又增加了文件管理的內容。20世紀60年代末到70年代初出現了大型程序，軟件也相對獨立，結構化程序設計成為程序設計方法學的主要內容，人們開始越來越重視數據結構，認為程序設計的實質是對確定的問題選擇一種好的數據結構，加上設計一種好的算法。從20世紀70年代中期到80年代初，各種版本的數據結構著作就相繼出現。
也就是說，在計算機專業教育中，剛開始并沒有《數據結構與算法》這樣的課程。后來人們意識到，在系統軟件與應用軟件設計中有不少“數據結構”和“算法”是常用的、普適的，把它們抽象、提煉出來，就形成了這門課程。這種抽象與提煉不僅必要，也十分有意義。就像文學作品一樣，應該“源于生活，高于生活，給人們以美的熏陶與享受”。
眾所周知，算法側重于解決問題的思想與方法，程序強調的是計算機上的實現。因此，算法比程序更宏觀、更抽象、更簡練、更易懂，講解算法比講解程序更容易讓學術掌握算法的本質與核心。如果用一種具體的語言來描述算法，會使學生陷于程序的語法細節而不能自拔，從而影響學生對算法的理解。
正因為算法“源于”程序、算法“高于”程序，所以本書作者不贊成用一種具體語言（如C/C++語言）來描述算法，盡管這種“功利性”的教材市面上很多。
不妨看一個非常簡單的例子——輸出數組所有元素的值，為保證原汁原味，編碼格式都沒做調整。形式如下所示：
template ＜class T＞
void PrintArray(T list[], int n)
{
while (n＞0){
count＜＜list[n-1]＜＜ ’’;
- -n;
}
}
針對此例，如果按本教材的風格寫成算法，形式如下：
void PrintArray( list[], n)
{
while ( n ＞ 0 )
{
print( list[n-1] );
nn - 1;
}
}
對比一下，不難看出哪種方式更有利于教學。
從另一個角度來說，如何把算法轉換成程序正是該課程重要的教學目標之一。如果學生課后能把教材和課堂上講解的算法轉換成由某一種語言描述的程序并上機實踐，就能加深學生對算法的理解以及提升學生的實踐能力。
因此，從教學的角度來說，當學生學完某一門具體的計算機語言、學完數據結構與算法、學完程序設計方法學的相關知識后，通過一些綜合性的課題或項目來綜合這些理論、知識與技能，以達到真正意義上的“融會”與“貫通”。而不是過早地把它們融合在一起，讓學生抓不住本質、摸不著頭腦。
另外，數據結構與算法與程序設計方法學（如面向對象方法學）沒有必然的聯系。筆者認為，只有學生真正應用算法設計系統或應用程序時，才應該考慮程序設計方法學方面的問題。否則，算法設計與某種具體的程序設計方法學相結合，就會使算法復雜化，從而影響學生對算法的理解。
基于以上認知，本書事先定義一種簡潔的、類C語言的算法描述語言，所有算法都用它來描述，然后要求或鼓勵學生利用實驗或課外條件完成由算法到程序的轉換。
本書除了作為課堂教學重要的參考書外，主要是給學生看的。課前看，叫預習；課后看，叫復習。課堂上顯然不需要學生看教材，否則教師的講課就多余了。因此，如何讓學生容易讀懂教材應該作為衡量教材的一個重要指標。最忌諱的是把教材寫成了學術著作，以展示作者的學術水平。從這個角度上來說，本書力求用生活中的一些例子來闡明一些理論和思想（即貼近“生活”），盡量體現通俗易懂，盡量不要讓學生“望而生畏”。盡管這樣做可能會使本書不那么“陽春白雪”，但只要對教學有利，還是很值得的。
站在學習者的角度來說，學什么都希望了解“前因后果”，即為什么要學這些東西？以及學習這些東西有什么意義（或者有什么用）？作為教師或者教材，應該給出相應的解答，否則學習者是缺乏“本源動力”的。本書在這方面應該說盡力而為了。比如，第8章“查找與搜索引擎”，除了講述為什么要學習“查找”外，用較大篇幅介紹Google搜索引擎，相信會激發學習者的興趣。事實上，Google是數據結構與算法的集大成者，又是非常成功的典型代表。如果讀者具有了較好的程序設計能力，相信學完本課程后，自己都能構造一個簡單的、專用的搜索引擎！
全書共9章。
第1章介紹數據結構與算法的基本概念，并對此進行詳盡的解讀，如算法設計的準則、算法與程序的對比等。
第2章介紹順序存儲結構的線性表，側重順序存儲結構的特點及其建立在該結構上的操作（算法）。
第3章介紹鏈式存儲結構的線性表，強調其與順序存儲結構的差異與互補及其建立在鏈表結構上的操作，并介紹靜態鏈表及其應用。
第4章介紹串及其基本概念與操作，重點在串的模式匹配。
第5章介紹數組、特殊矩陣和廣義表，并引出數據壓縮與人工智能等概念。
第6章介紹樹與二叉樹，重點在二叉樹及其應用，如哈夫曼編碼、二叉排序樹等。
第7章介紹圖及其應用，設計的概念較多，重在圖的存儲結構、遍歷及其應用，如最小生成樹、最短路徑、拓撲排序等。
第8章介紹查找與搜索引擎，在講解基本的查找方法后，結合Google重點講述搜索引擎的構造思想和方法。
第9章介紹幾大類排序方法，如插入排序、選擇排序、交換排序、歸并排序、基數排序等。
本課程相對來說比較抽象，學生不容易理解和掌握。雖然教材或黑板上的示意圖可以幫助人們理解，但用一個節點表示一個數據元素，用一根線段表示數據元素之間的關系，這樣畫出來的示意圖本身就是比較抽象的。要在此基礎上理解其存儲結構、建立在存儲結構上的算法以及算法的執行情況，自然變得非常困難，這就是本課程難以學習和掌握的癥結所在。為之，人們開發了各種教學軟件，幫助學生學習數據結構與算法。
為此，作者組織人力開發了“數據結構與算法綜合集成演示系統”，本系統集成了圖、鏈表、矩陣轉置、二叉樹、排序、數據查找等主要內容，涵蓋了《數據結構與算法》課程的絕大部分內容，集成度高，以非常直觀、方便的方式演示了圖、二叉樹等復雜的數據結構元素之間的層次及網狀關系。本系統基于相應的數據結構，演示了各種數據結構基礎之上的算法，如遍歷、最短矩陣、拓撲排序等。本系統還集成了演示動畫。
例如，對于網狀結構而言，可以利用作圖元直接在屏幕上繪制數據結構的網狀圖，根據網狀圖可自動轉換成機器內部的數據結構（鄰接矩陣或鄰接表），繪制的網狀結構可以文件的形式存儲，實現了基于鄰接表與鄰接矩陣的各種相關算法，并可查看相關算法和代碼。如圖1所示。
圖1
又如，學生對各種排序算法的理解相對容易，但對各種不同算法的效果難以體會。本系統囊括了課程里面幾乎所有的排序算法，可自動產生100∼10000000個數據供測試算法效率用。根據用戶的選擇，調用相應的排序算法，可精確記錄排序算法所耗費的時間，能顯示排序的結果并用柱狀圖、時間列表來對比排序算法的優劣性。
全書由唐培和教授負責統籌、安排、協調、統稿、審核等，其中第4章、第5章以及每章習題由徐奕奕副教授負責撰寫，其余章節由唐培和教授負責撰寫。唐新來教授審閱了部分章節。
本書的出版得到了廣西教育廳特色專業及課程一體化項目建設經費（GXTSZY217）、廣西高校名師專項經費、廣西高等教育教學改革工程重點項目（2014JGZ133）經費的資助。電子工業出版社的有關同志為本書的出版做了大量的工作。在此一并表示感謝。
本書綜合了作者多年的教學經驗，也吸取了同行很多學者的成果。參考文獻中列出了部分引用的文獻，恐有遺漏（特別是網上的文獻），敬請諒解！
由于作者水平有限，時間倉促，難免錯漏。不當之處，請讀者批評指正。歡迎全國同行交流經驗與體會，聯系方式：tangpeihe@163.com。
本書為教師提供相關教學資源，有需要者，請登錄華信教育資源網http://www.hxedu.com.cn，注冊之后進行下載。
作 者 |
內容簡介：本書以數據的邏輯結構為線索，介紹數據結構及其建立在數據結構之上的操作和算法，內容涉及數據結構與算法的基本概念、順序存儲結構的線性表、鏈式存儲結構的線性表、串、數組、特殊矩陣與廣義表、樹與二叉樹、圖及其應用、查找與搜索引擎、排序等。
本書既強調“算法”與“數據結構”之間緊密的依賴關系，也注重算法描述的簡潔與干練；既有完整的理論體系，也有很好的應用案例。為了增強可理解性，本書案例與生活實踐相聯系。
本書以知識單元為基本構件，既可拆卸也可重組，內容豐富，表述詳盡，可讀性強，適合不同類型的本科院校按照不同的培養規格組織教學。 |
目錄：第1章 數據結構與算法概述 1
1.1 引言 1
1.1.1 《數據結構與算法》課程到底研究什么 1
1.1.2 《數據結構與算法》課程介紹 1
1.1.3 為什么要學習《數據結構與算法》課程 2
1.2 基本概念和術語 3
1.2.1 數據 3
1.2.2 數據項 3
1.2.3 數據元素 4
1.2.4 數據對象 4
1.2.5 數據結構 4
1.2.6 數據結構的形式化描述 6
1.2.7 數據的邏輯結構、存儲結構與物理結構 7
1.2.8 數據結構實例 7
1.3 算法 9
1.3.1 什么是算法 9
1.3.2 算法的性質 11
1.3.3 算法和程序 12
1.4 算法的表示（描述） 14
1.4.1 自然語言 14
1.4.2 計算機語言 15
1.4.3 圖形化工具 16
1.4.4 偽代碼 17
1.5 算法設計的準則 19
1.5.1 正確性 19
1.5.2 可讀性 20
1.5.3 健壯性 20
1.5.4 效率 21
1.6 算法效率分析 24
1.6.1 事后統計的方法 25
1.6.2 事前分析估算的方法 25
1.6.3 算法的空間復雜度 28
1.7 抽象數據類型 30
閱讀材料 32
習題1 35
第2章 順序存儲結構的線性表 39
2.1 基本概念和操作 39
2.1.1 什么是線性表 39
2.1.2 線性表的邏輯結構 40
2.1.3 線性表的基本操作 40
2.1.4 線性表的順序存儲結構 41
2.1.5 線性表的插入與刪除操作（算法） 42
2.1.6 順序表應用舉例 45
2.2 堆棧 47
2.2.1 堆棧的定義 47
2.2.2 棧的順序存儲結構與操作（算法） 48
2.2.3 堆棧在算法設計中的應用 51
2.3 隊列 63
2.3.1 隊列的定義 64
2.3.2 隊列的順序存儲結構與操作（算法） 64
2.3.3 循環隊列 66
2.3.4 隊列應用舉例 68
2.4 集合及其運算 71
2.4.1 集合的定義 71
2.4.2 集合運算 72
2.4.3 集合的順序存儲結構和操作實現 72
小結 75
習題2 75
第3章 鏈式存儲結構的線性表 79
3.1 什么是鏈式存儲結構的線性表 79
3.2 線性鏈表的操作（算法） 82
3.2.1 線性鏈表的構造 83
3.2.2 求表長 86
3.2.3 查找操作 86
3.2.4 線性鏈表的插入 87
3.2.5 線性鏈表的刪除 89
3.3 棧的鏈式存儲結構 90
3.4 隊列的鏈式存儲結構 92
3.5 循環鏈表 93
3.6 雙向鏈表 94
3.7 靜態鏈表 95
3.8 鏈表應用 97
3.9 一元多項式的存儲和相加 100
3.10 集合的鏈式存儲結構與操作 103
3.11 順序表和鏈表的比較 106
習題3 107
第4章 串 110
4.1 基本概念 111
4.2 串的存儲結構 112
4.2.1 順序存儲結構 112
4.2.2 鏈式存儲結構 113
4.3 串的基本操作 113
4.3.1 串復制 114
4.3.2 求字符串的長度 115
4.3.3 字符串連接 115
4.3.4 取子串 115
4.3.5 判斷兩個字符串是否相等 116
4.3.6 插入字符串 117
4.3.7 刪除子串 117
4.3.8 字符串清空 118
4.3.9 判斷字符串是否為空 118
4.3.10 字符串比較 118
4.4 串的模式匹配算法 119
4.4.1 模式匹配及其BF算法 119
4.4.2 模式匹配的一種改進算法——KMP算法 120
4.4.3 其他模式匹配算法 124
4.5 串操作應用舉例 132
習題4 133
第5章 數組、特殊矩陣與廣義表 136
5.1 數組的定義和運算 136
5.1.1 數組的基本概念 136
5.1.2 數組的特點 137
5.2 數組的順序存儲結構 137
5.2.1 一維數組 137
5.2.2 二維數組 138
5.2.3 三維數組 138
5.2.4 n維數組 139
5.3 特殊矩陣的壓縮存儲與處理 141
5.3.1 基本原則 141
5.3.2 對稱矩陣的壓縮存儲 141
5.3.3 三角矩陣的壓縮存儲 142
5.3.4 對角矩陣（帶狀矩陣）的壓縮存儲 143
5.4 稀疏矩陣 144
5.4.1 稀疏矩陣的三元組表存儲 145
5.4.2 稀疏矩陣的轉置 145
5.4.3 稀疏矩陣的快速轉置算法 147
5.5.4 稀疏矩陣的乘積 148
5.4.5 稀疏矩陣的十字鏈表存儲 151
5.5 廣義表 155
5.5.1 廣義表的定義 155
5.5.2 廣義表的特性 156
5.5.3 廣義表的基本操作 156
5.5.4 廣義表的存儲 157
5.5.5 廣義表的基本操作 159
習題5 162
第6章 樹與二叉樹 166
6.1 基本概念 166
6.1.1 什么是樹 166
6.1.2 基本概念和術語 167
6.1.3 樹的表示方法 167
6.1.4 樹的基本操作 168
6.1.5 樹的存儲結構 168
6.2 二叉樹 173
6.2.1 二叉樹的定義 173
6.2.2 二叉樹的基本形態 173
6.2.3 兩種特殊的二叉樹 174
6.2.4 二叉樹具有的重要性質 175
6.2.5 二叉樹的存儲結構 176
6.2.6 二叉樹的基本操作 179
6.3 二叉樹的遍歷 179
6.3.1 二叉樹的遍歷 179
6.3.2 先序遍歷算法 180
6.3.3 中序遍歷 181
6.3.4 后序遍歷 182
6.3.5 按層次順序遍歷二叉樹 183
6.3.6 遍歷算法的應用 184
6.4 二叉樹其他運算 185
6.4.1 建造二叉樹算法 185
6.4.2 求二叉樹高度（深度） 186
6.4.3 求二叉樹寬度 186
6.4.4 二叉樹查找 187
6.4.5 輸出一棵二叉樹 188
6.4.6 清除一棵二叉樹 188
6.5 線索二叉樹 189
6.5.1 建立線索樹 189
6.5.2 檢索結點 191
6.5.3 在線索二叉樹上插入一個結點 192
6.6 樹與森林 193
6.6.1 樹與二叉樹的轉換 193
6.6.2 森林與二叉樹的轉換 194
6.6.3 樹和森林的遍歷 194
6.7 樹的應用 197
6.7.1 判定樹 197
6.7.2 集合的表示 198
6.7.3 關系等價求等價類問題 199
6.8 二叉排序樹 200
6.8.1 二叉排序樹的定義 200
6.8.2 二叉排序樹的構造 201
6.8.3 二叉排序樹的查找 203
6.8.4 二叉排序樹的更新 205
6.8.5 二叉排序樹的刪除 205
6.9 哈夫曼樹及其應用 207
6.9.1 基本概念 207
6.9.2 哈夫曼樹的構造 208
6.9.3 哈夫曼編碼 210
6.9.4 最佳判定過程 211
6.10 平衡二叉樹 212
6.10.1 平衡二叉樹的引入 212
6.10.2 平衡二叉樹的定義 212
6.10.3 最小不平衡二叉樹 213
6.10.4 不平衡二叉樹的調整方法 214
6.10.5 建立平衡二叉樹舉例 218
6.10.6 平衡二叉樹與二叉排序樹比較 219
習題6 220
第7章 圖及其應用 223
7.1 基本概念和術語 225
7.1.1 圖的定義 225
7.1.2 完全圖、稠密圖、稀疏圖 226
7.1.3 頂點的度 227
7.1.4 子圖 227
7.1.5 路徑和回路 227
7.1.6 連通和連通分量 227
7.1.7 強連通圖和強連通分量 227
7.1.8 權和網 228
7.2 圖的存儲結構 229
7.2.1 鄰接矩陣 229
7.2.2 鄰接表 231
7.2.3 十字鏈表 234
7.2.4 鄰接多重表 236
7.2.5 圖的邊集數組 237
7.3 圖的遍歷 237
7.3.1 深度優先搜索 237
7.3.2 廣度優先搜索 239
7.3.3 搜索算法在搜索引擎中的應用 242
7.4 圖的連通性 243
7.4.1 無向圖的連通性 243
7.4.2 有向圖的連通性 244
7.4.3 生成樹和生成森林 245
7.4.4 關結點和重連通分量 245
7.5 最小生成樹 248
7.5.1 什么是生成樹 248
7.5.2 構造最小生成樹的普里姆（Prim）算法 248
7.5.3 構造最小生成樹的Kruskal算法 252
7.6 最短路徑 255
7.6.1 求某一個源點到其他頂點的最短路徑 256
7.6.2 Bellman-Ford算法 259
7.6.3 每對頂點之間的最短路徑 262
7.7 有向無環圖及其應用 267
7.7.1 有向無環圖的概念 267
7.7.2 AOV網與拓撲排序 268
7.7.3 AOE網與關鍵路徑 272
習題7 277
第8章 查找與搜索引擎 281
8.1 基本概念與術語 281
8.2 順序查找 283
8.3 二分查找（折半查找） 285
8.3.1 二分查找的定義 285
8.3.2 二分查找算法 286
8.3.3 二分查找判定樹 287
8.3.4 二分查找性能分析 287
8.4 有序表的插值查找和斐波那契查找 288
8.4.1 插值查找 288
8.4.2 斐波那契查找 288
8.5 分塊查找 289
8.6 B-樹和B+樹上的查找 291
8.6.1 B-樹及其查找 291
8.6.2 B+樹 293
8.7 哈希表與散列查找 294
8.7.1 散列的概念 295
8.7.2 哈希函數 295
8.7.3 散列存儲的沖突 298
8.7.4 裝填因子 298
8.7.5 沖突解決方法 298
8.7.6 散列存儲的平均查找長度 302
8.7.7 散列存儲的優缺點 303
8.8 搜索引擎及其相關技術 303
8.8.1 網頁的自動下載與存儲 304
8.8.2 網頁索引技術 306
8.8.3 網頁排名技術 310
習題8 323
第9章 排序 326
9.1 基本概念 327
9.2 插入排序 327
9.2.1 直接插入排序 327
9.2.2 折半插入排序 329
9.2.3 表插入排序 330
9.2.4 希爾排序 332
9.3 交換排序 336
9.3.1 冒泡排序 336
9.3.2 快速排序 337
9.4 選擇排序 343
9.4.1 簡單選擇排序 343
9.4.2 樹形選擇排序 346
9.4.3 堆排序 350
9.5 歸并排序 356
9.6 分配排序 359
9.6.1 箱排序 359
9.6.2 基數排序 360
9.6.3 多關鍵字排序 363
9.7 外排序 364
9.7.1 外部排序的方法 364
9.7.2 多路歸并的實現 365
9.8 排序方法之比較 368
習題9 369 |
| 序： |
|
