本書用最輕松的圖解方式來講解數據結構，全書采用豐富的圖例闡述數據結構的基本概念及應用，并將重要理論、演算方法做最詳細的詮釋與舉例，是一本兼具內容及專業的數據結構的教學用書。 由于作者長期從事信息教育及寫作，在文字的表達上簡潔明了、邏輯清晰，并安排了大量的習題，供讀者檢驗學習成果。
數據結構毫無疑問是計算機科學既經典又核心的課程之一，不管是從事計算機軟件還是硬件的開發工作，如果沒有系統地學習數據結構或者是沒有專心自學過，很容易被人打上“非專業”的標簽。對于任何在信息技術行業工作的專業人員或者想進入此行業的人來說，什么時候開始學數據結構都不會晚，更不會過時。
從“數據結構”的名字看，它不僅僅只是講授數據的結構以及在計算機內如何存儲和組織數據的方式，這些只是它的表面現象。數據結構背后真正蘊含的是與之息息相關的算法，精心選擇的數據結構配合恰如其分的算法就意味著數據或者信息在計算機內被高效率地存儲和高效率地處理。算法其實就是數據結構的靈魂，它既神秘又神奇“好玩”，當然對初學者也比較難，算法可以說是“聰明人在計算機上的游戲”。
本書是一本綜合而且講述數據結構及其算法分析的教科書，為了便于高校的教學或者讀者自學，作者在描述數據結構原理和算法時文字清晰并且嚴謹，為每個算法及其數據結構提供了演算的詳細圖解。另外，為了適合在教學中讓學生上機實踐或者自學者上機“操練”，本書為每個經典的算法都提供了C語言編寫的完整范例程序的源代碼，每個范例程序都不需要經過修改，直接通過編譯就可以運行，目的就是讓本書的學習者以這些范例程序作為參照迅速掌握數據結構和算法的要點。
全書的所有范例程序都可以在標準的C語言編程環境中編譯通過并且成功運行，我們在改編本書的過程中選用了免費的Dev C 5.11集成開發環境，對原書的所有范例程序進行編譯、修改、調試和測試，并確保它們都可以無誤地運行。附錄A包含了“C/C 編譯程序的介紹與安裝”，其中重點就介紹了Dev C 。附錄B則包含了“C語言快速入門”。
胡昭民現任榮欽科技股份有限公司董事長，美國Rochester Institute of Technology計算機科學研究所畢業，長期從事信息教育及計算機圖書寫作的工作，并監制過多套游戲及教學軟件的研發。
目 錄
第1章 數據結構導論 1
1-1 數據結構簡介 2
1-1-1 數據與信息 2
1-1-2 算法 3
1-1-3 算法的條件 3
1-1-4 數據結構的應用 6
1-2 數據抽象化 7
1-2-1 基本數據類型 7
1-2-2 抽象數據類型 7
1-3 算法與程序設計 8
1-3-1 認識程序設計 8
1-3-2 程序開發流程 9
1-3-3 程序設計的風格 9
1-4 面向對象程序設計 11
1-4-1 封裝(Encapsulation) 12
1-4-2 繼承(Inheritance) 13
1-4-3 多態(Polymorphism) 13
1-5 模塊化設計與C語言 13
1-5-1 函數的基本概念 13
1-5-2 參數類型的介紹 14
1-5-3 參數的傳遞方式 15
1-6 遞歸算法 15
1-6-1 遞歸的定義 15
1-6-2 斐波拉契數列 17
1-6-3 漢諾塔問題 18
1-7 程序效率的分析 23
1-7-1 Big-oh 25
1-7-2 Ω(omega) 26
1-7-3 θ(theta) 27
本章習題 27
第2章 線性表 32
2-1 線性表的定義 33
2-1-1 線性表的用途 33
2-2 數組 34
2-2-1 一維數組 34
2-2-2 二維數組 36
2-2-3 多維數組 40
2-2-4 結構數組 44
2-2-5 字符數組 46
2-2-6 字符串數組 48
2-2-7 指針數組 49
2-3 矩陣 50
2-3-1 矩陣的運算 51
2-3-2 稀疏矩陣 53
2-3-3 上三角形矩陣 55
2-3-4 下三角形矩陣 59
2-3-5 帶狀矩陣 64
本章習題 65
第3章 鏈表 69
3-1 動態分配內存 70
3-1-1 C的動態分配變量 70
3-1-2 C 的動態分配變量 72
3-2 單向鏈表 73
3-2-1 建立單向鏈表 74
3-2-2 遍歷單向鏈表 75
3-2-3 釋放單向鏈表節點的空間 76
3-2-4 單向鏈表插入新節點 77
3-2-5 單向鏈表刪除節點 79
3-2-6 單向鏈表的反轉 81
3-3 環形鏈表 83
3-3-1 環形鏈表的建立與遍歷 83
3-3-2 環形鏈表中插入新節點 85
3-3-3 環形鏈表節點的刪除 86
3-3-4 環形鏈表的連接功能 88
3-4 雙向鏈表 89
3-4-1 雙向鏈表的建立與遍歷 90
3-4-2 雙向鏈表中加入新節點 92
3-4-3 雙向鏈表節點的刪除 94
3-5 鏈表相關應用簡介 96
3-5-1 多項式表式法 96
3-5-2 稀疏矩陣表示法 100
本章習題 102
第4章 堆棧與隊列 109
4-1 堆棧簡介 110
4-1-1 堆棧的基本操作 111
4-1-2 用數組實現堆棧 111
4-1-3 用鏈表實現堆棧 112
4-1-4 堆棧類樣板的實現 114
4-1-5 老鼠走迷宮 116
4-1-6 八皇后問題 119
4-2 算術表達式的表示法 120
4-2-1 中序轉為前序與后序 121
4-2-2 前序與后序轉為中序 126
4-2-3 中序表示法求值 129
4-2-4 前序法的求值運算 130
4-2-5 后序法的求值運算 131
4-3 隊列 132
4-3-1 隊列的基本操作 133
4-3-2 用數組實現隊列 133
4-3-3 環形隊列 135
4-3-4 雙向隊列 139
4-3-5 雙向隊列 141
4-3-6 優先隊列 143
本章習題 144
第5章 樹狀結構 156
5-1 樹的基本概念 157
5-1-1 專有名詞介紹 158
5-2 二叉樹 159
5-2-1 二叉樹的特性 159
5-2-2 特殊二叉樹簡介 160
5-3 二叉樹的存儲方式 161
5-3-1 一維數組表示法 161
5-3-2 鏈表表示法 164
5-4 二叉樹的遍歷 166
5-4-1 中序遍歷 166
5-4-2 后序遍歷 167
5-4-3 前序遍歷 167
5-4-4 二叉樹節點的插入與刪除 170
5-4-5 二叉運算樹 174
5-5 線索二叉樹 176
5-5-1 二叉樹轉為線索二叉樹 176
5-6 樹的二叉樹表示法 180
5-6-1 樹轉化為二叉樹 180
5-6-2 二叉樹轉換成樹 182
5-6-3 森林化為二叉樹 183
5-6-4 二叉樹轉換成森林 184
5-6-5 樹與森林的遍歷 185
5-6-6 確定二叉樹 189
5-7 優化二叉查找樹 191
5-7-1 擴充二叉樹 191
5-7-2 霍夫曼樹 192
5-8 平衡樹 194
5-8-1 平衡樹的定義 194
5-9 高級樹狀結構的研究 196
5-9-1 決策樹 196
5-9-2 B樹 198
5-9-3 二叉空間分割樹 198
5-9-4 四叉樹與八叉樹 199
本章習題 200
第6章 圖形結構 210
6-1 圖形簡介 211
6-1-1 圖的定義 212
6-1-2 無向圖 212
6-1-3 有向圖 214
6-2 圖的數據表示法 215
6-2-1 鄰接矩陣法 215
6-2-2 鄰接表法 218
6-2-3 鄰接復合鏈表法 220
6-2-4 索引表格法 222
6-3 圖的遍歷 225
6-3-1 深度優先遍歷法 225
6-3-2 廣度優先遍歷法 227
6-4 生成樹 229
6-4-1 DFS生成樹和BFS生成樹 229
6-4-2 最小生成樹 231
6-4-3 Kruskal算法 231
6-4-4 Prim算法 235
6-5 圖的最短路徑 236
6-5-1 單點對全部頂點 237
6-5-2 兩兩頂點間的最短路徑 240
6-6 AOV網絡與拓撲排序 244
6-6-1 拓撲排列簡介 244
6-7 AOE網絡 246
6-7-1 關鍵路徑 246
本章習題 248
第7章 排序 257
7-1 排序簡介 258
7-1-1 排序的分類 259
7-2 內部排序法 260
7-2-1 冒泡排序法 260
7-2-2 選擇排序法 262
7-2-3 插入排序法 264
7-2-4 希爾排序法 266
7-2-5 合并排序法 268
7-2-6 快速排序法 269
7-2-7 堆積排序法 271
7-2-8 基數排序法 278
7-3 外部排序法 280
7-3-1 直接合并排序法 280
7-3-2 k路合并法 284
7-3-3 多相合并法 284
本章習題 285
第8章 查找 295
8-1 常見的查找方法 296
8-1-1 順序查找法 296
8-1-2 二分查找法 297
8-1-3 插值查找法 299
8-1-4 斐波那契查找法 301
8-2 哈希查找法 305
8-2-1 哈希法簡介 305
8-3 常見的哈希函數 306
8-3-1 除留余數法 306
8-3-2 平方取中法 307
8-3-3 折疊法 308
8-3-4 數字分析法 308
8-4 碰撞與溢出問題的處理 309
8-4-1 線性探測法 309
8-4-2 平方探測 310
8-4-3 再哈希 310
8-4-4 鏈表 311
本章習題 312
附錄A C/C 編譯程序的介紹與安裝 318
A-1 C/C 編譯程序簡介 319
A-1-1 Visual C 2010 Express 319
A-1-2 C Builder 320
A-1-3 Visual C 320
A-1-4 Dev C 321
A-1-5 GCC 322
A-2 Dev C 的安裝與介紹 322
A-2-1 下載Dev-C 323
A-2-2 安裝Dev C 323
附錄B C語言快速入門介紹與安裝 329
B-1 輕松學C程序 330
B-1-1 編譯與執行 331
B-1-2 編譯程序 332
B-1-3 開始執行程序 333
B-2 C的基本數據處理 333
B-2-1 變量 333
B-2-2 常數 334
B-2-3 數據類型簡介 334
B-3 C語言的輸出與輸入 335
B-3-1 printf()函數 336
B-3-2 scanf()函數 337
B-4 流程控制 338
B-4-1 順序結構 338
B-4-2 選擇結構 339
B-4-3 重復結構 343
B-5 數組簡介 346
B-5-1 字符串簡介 347
B-5-2 字符串數組 347
B-6 函數介紹 349
B-6-1 傳遞參數的方式 350
B-6-2 標準函數庫 352
第8章 查找
在數據處理過程中，是否能在最短時間內查找到所需要的數據，是一個相當值得信息從業人員關心的問題。所謂查找(search，或搜索)指的是從數據文件中找出滿足某些條件的記錄。用以查找的條件稱為“鍵值”(key)，就如同排序所用的鍵值一樣。
例如聯系人中找某人的電話號碼，那么這個人的姓名就成為在聯系人中查找電話號碼的鍵值。通常影響查找時間長短的主要因素包括算法的選擇、數據存儲的方式和結構。
8-1 常見的查找方法
如果根據數據量的大小，可將查找分為：
1. 內部查找：數據量較小的文件，可以一次性全部加載到內存中進行查找。
2. 外部查找：數據量大的文件，無法一次加載到內存中處理，而需使用輔助存儲器來分次處理。
如果從另一個角度來看，查找的技巧又可分為“靜態查找”和“動態查找”兩種。定義如下所示。
1. 靜態查找：指的是在查找過程中，查找的表格或文件的內容不會被改動。例如符號表的查找就是一種靜態查找。
2. 動態查找：指的是在查找過程中，查找的表格或文件的內容可能會被改動，例如在樹狀結構中所談的B-tree查找就屬于一種動態查找。
至于查找技巧中比較常見的方法有順序法、二分查找法、斐波那契法、插值法、哈希法、m路查找樹、B-tree等。為了讓大家能確實掌握各種查找的技巧和基本原理，以便應用于日后的各種領域，現將幾個主要的查找方法分述于后。
8-1-1 順序查找法
順序查找通常用于未經組織化的文件，又稱為線性查找。查找的過程從文件及時項數據開始，按序比較每個鍵值。由于順序查找法是逐項對比，因此只要一找到數據就可以結束數據的查找。以n項數據為例，使用順序查找法來查找數據時，有可能在第1項就找到了，在這種情形下僅需執行一次比較操作。如果數據在第2項、第3項…第n項，則其需要的比較次數分別為2、3、4、…、n次。因此，在平均情況下，順序查找法，查找一項數據需要的平均比較次數為 (n 1)/2。
現在以一個例子來說明，假設已有數列74、53、61、28、99、46、88，若要查找28，則需要比較4次；要查找74僅需比較1次；要查找88則需查找7次，這表示當查找的數列長度n很大時，利用順序查找是不太適合的，它是一種適用于小數據文件的查找方法。
另外，在最差的情況下，逐一對比后沒有找到數據，則必須花費n次，其最壞情況下(Worst Case)的時間復雜度為O(n)。也就是說，除非可以預知要查找的數據大概位于文件的前端，否則當文件的數據項數過大時，順序查找法在查找的效率上顯然不如其他的查找法。
線性查找法的優點是文件或數據事前不需要經過任何的處理與排序，也由于它未考慮到數據的特征對于查找的影響，所以在應用上適合于各種情況，其缺點則是查找的速度較慢。
順序查找法的C語言算法如下所示。
while (val!=-1
{
find=0;
printf("請輸入查找鍵值(1-150)，輸入-1離開：");
scanf("%d",&val);
for (i=0;i
{
if(data[i]==val
{
printf("在第 %3d個位置找到鍵值 [%3d]\n",i 1,data[i]);
find ;
}
}
if(find==0 && val !=-1
printf("######沒有找到 [%3d]######\n",val);
}
8.1.1
請設計一個C程序，以隨機數生成1~150之間的80個整數，然后實現順序查找法的過程。
請參考程序CH08_01.c，本范例程序的運行結果如圖8-1所示。
圖8-1 實現順序查找法的范例程序的運行結果
8-1-2 二分查找法
如果要查找的數據已經事先排好序了，則可使用二分查找法來進行查找。二分查找法是將數據平均分割成兩份，再比較鍵值與中間值的大小，如果鍵值小于中間值，可確定要查找的數據在前半段，否則在后半部。如此分割數次直到找到或確定不存在為止。例如，以下已排序的數列 2、3、5、8、9、11、12、16、18 ，而所要查找值為11時：
首先跟第5個數值 9 比較，如圖8-2所示。
圖8-2 先和中值比較
因為11>9，所以和后半部的中間值 12 比較，如圖8-3所示：
圖8-3 再和后半部的中值比較
因為 11<12，所以和前半部的中間值 11比較，如圖8-4所示：
圖8-4 再和后半部的前半部中值比較
因為 11=11，表示查找到了即查找完成，如果不相等則表示沒有找到。
二分查找法的C語言算法如下所示。
int bin_search(int data[50],int val
{
int low,mid,high;
low=0;
high=49;
printf("查找過程中......\n");
while(low
{
mid=(low high)/2;
if(val
{
printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊\n",val,low 1, data[low],mid 1,data[mid]);
high=mid-1;
}
else if(val>data[mid]
{
printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊\n",val,mid 1, data[mid],high 1,data[high]);
low=mid 1;
}
else
return mid;
}
return -1;
}
使用二分法查找要求被查找的數列事先已排好序，而且數據量不能太大，必須要能直接在內存中執行。此法適合用于不需增刪的靜態數據，因為每次的查找都會比上一次少一半的范圍，所以最多只需要比較log2n 1或log2(n 1) 次，時間復雜度為O(log n)。
8.1.2
請設計一個C程序，以隨機數生成1~150之間的80個整數，然后實現二分查找法的過程與步驟。
請參考程序CH08_02.c，本范例程序的運行結果如圖8-5所示。
圖8-5 實現二分查找法的范例程序的運行結果
8-1-3 插值查找法
插值查找法(interpolation search)又叫作插補查找法，是二分查找法的改進版。它是按照數據位置的分布，利用公式預測數據所在的位置，再以二分法的方式漸漸逼近。使用插值法是假設數據平均分布在數組中，而每一項數據的差距相當接近或有一定的距離比例。插值法的公式為：
Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low
其中key是要查找的鍵，data[high]、data[low]是剩余待查找記錄中的較大值和最小值，假設數據項數為n，其插值查找法的步驟如下所示。
? 將記錄從小到大的順序給予1、2、3、…、n的編號。
? 令low=1，high=n
? 當low
? 令Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low
? 若key
? 若key=keyMid表示成功查找到鍵值的位置
? 若key>keyMid且low≠Mid 1，則令low=Mid 1
二分查找法的C語言算法如下所示。
int bin_search(int data[50],int val
{
int low,mid,high;
low=0;
high=49;
printf("查找過程中......\n");
while(low
{
mid=low ((val-data[low])(high-low)/(data[high]-data[low]));
/內插法公式/
if (val==data[mid]
return mid;
else if (val < data[mid]
{
printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊
\n",val,low 1,data[low],mid 1,data[mid]);
high=mid-1;
}
else if(val > data[mid]
{
printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊
\n",val,mid 1,data[mid],high 1,data[high]);
low=mid 1;
}
}
return -1;
}
一般而言，使用插值查找法要求數據需先經過排序，這樣查找速度才能優于順序查找法，而如果數據的分布越平均，則查找速度越快，甚至可能及時次就找到數據。此法的時間復雜度取決于數據分布的情況，平均而言優于O(log n)。
8.1.3
請設計一個C程序，以隨機數生成1~150之間的50個整數，然后實現插值查找法的過程與步驟。
請參考程序CH08_03.c，本范例程序的運行結果如圖8-6所示。
圖8-6 實現插值查找法的范例程序的運行結果
8-1-4 斐波那契查找法
斐波那契查找法(fibonacci search)又稱為Fibonacci查找法，此法和二分法一樣都是以分割范圍來進行查找，不同的是斐波那契查找法不以對半分割而是以斐波那契級數的方式來分割。
斐波那契級數F(n)的定義如下所示。
斐波那契級數：0、1、1、2、3、5、8、13、21、34、55、89、……。也就是除了第0個和第1個元素外，級數中的每個值都是前兩個值的和。
斐波那契查找法的好處是只用到加減運算而不需用到乘除運算，這從計算機運算的過程來看效率會高于前兩種查找法。在尚未介紹斐波那契查找法之前，我們先來認識斐波那契查找樹。所謂斐波那契查找樹是以斐波那契級數的特性來建立的二叉樹，其建立的原則如下所示。
(1)斐波那契樹的左右子樹均為斐波那契樹。
(2)當數據個數n確定，若想確定斐波那契樹的層數k值是多少，必須找到一個最小的k值，使得斐波那契層數的Fib(k 1)≥n 1。
(3)斐波那契樹的樹根一定是一個斐波那契數，且子節點與父節點差值的值為斐波那契數。
(4)當k≥2時，斐波那契樹的樹根為Fib(k)，左子樹為 (k-1) 層斐波那契樹(其樹根為Fib(k-1))，右子樹為 (k-2) 層斐波那契樹(其樹根為Fib(k) Fib(k-2))。
(5)若n 1值不為斐波那契數的值，則可以找出存在一個m使用Fib(k 1)-m=n 1，m=Fib(k 1)-(n 1)，再按斐波那契樹的建立原則完成斐波那契樹的建立，斐波那契樹的各節點再減去差值m即可，并把小于1的節點去掉。
斐波那契樹建立過程的示意圖如圖8-7所示。
圖8-7 斐波那契樹建立過程的示意圖
也就是說當數據個數為n，且找到一個最小的斐波那契數Fib(k 1)使得Fib(k 1)>n 1，則Fib(k) 就是這棵斐波那契樹的樹根，而Fib(k-2) 則是與左右子樹開始的差值，左子樹用減的；右子樹用加的。例如實際求取n=33的斐波那契樹。
由于n=33，且n 1=34為一個斐波那契樹，并知道斐波那契數列的3項特性。
Fib(0) = 0
Fib(1) = 1
Fib(k) = Fib(k-1) Fib(k-2
得知 Fib(0) = 0、Fib(1) = 1、Fib(2) = 1、Fib(3) = 2、Fib(4) = 3、Fib(5) = 5、Fib(6) = 8、Fib(7) = 13、Fib(8) = 21、Fib(9) = 34
從上式可得知Fib(k 1) = 34 à k = 8，建立二叉樹的樹根為Fib(8) = 21
左子樹的樹根為Fib(8-1) = Fib(7) = 13
右子樹的樹根為Fib(8) Fib(8-2) = 21 8 = 29
按此原則可以建立如圖8-8所示的斐波那契樹。
圖8-8 斐波那契樹
斐波那契查找法是以斐波那契樹來查找數據，如果數據的個數為n，而且n比某一個斐波那契數小，且滿足如下表達式。
Fib(k 1)≥n 1
此時Fib(k) 就是這棵斐波那契樹的樹根，而Fib(k-2) 則是與左右子樹開始的差值，若要查找的鍵值為key，首先比較數組下標Fib(k) 和鍵值key，此時可以有下列3種比較情況。
? 當key值比較小，表示所查找的鍵值key落在1到Fib(k)-1之間，故繼續查找1到Fib(k)-1之間的數據。
? 如果鍵值與數組下標Fib(k) 的值相等，表示成功查找到所要的數據。
? 當key值比較大，表示所找的鍵值key落在Fib(k) 1到Fib(k 1)-1之間，故繼續查找Fib(k) 1到Fib(k 1)-1之間的數據。
斐波那契查找法的C語言算法如下所示。
#define MAX 20
int fib(int n
{
if(n==1 || n==0
return n;
else
return fib(n-1) fib(n-2);
}
int fib_search(int data[MAX],int SearchKey
{
int index=2;
/斐波拉契數列的查找/
while(fib(index
index ;
index--;
/ index >=2 /
/起始的斐波拉契數/
int RootNode=fib(index);
/上一個斐波拉契數/
int diff1=fib(index-1);
/上兩個斐波拉契數即diff2=fib(index-2)/
int diff2=RootNode-diff1;
RootNode--;/這個表達式是配合數組的下標是從0開始存儲數據/
while(1
{
if(SearchKey==data[RootNode]
{
return RootNode;
}
else
{
if(index==2) return MAX; /沒有找到/
if(SearchKey
{
RootNode=RootNode-diff2;/左子樹的新斐波拉契數 /
int temp=diff1;
diff1=diff2;/上一個斐波拉契數/
diff2=temp-diff2;/上兩個斐波拉契數/
index=index-1;
}
else
{
if(index==3) return MAX;
RootNode=RootNode diff2;/右子樹的新斐波拉契數 /
diff1=diff1-diff2;/上一個斐波拉契數/
diff2=diff2-diff1;/上兩個斐波拉契數/
index=index-2;
&nb
圖解數據結構 （第二版），還可以吧，不是很深入！！！
用圖解的方式介紹數據結構，很有創意。
ok
很棒，正在看。印刷精良，簡約大方。很好很好。
非常滿意，很喜歡！
