數據結構與算法分析新視角（簡體書）

資料結構是高等學校電腦及其相關專業的核心課程，是電腦程式設計的基礎。本書按照“像外行一樣思考，像專家一樣實踐”的解決問題的思維方法，列舉大量實際或工程案例，從具體問題中引出抽象概念，運用類比、圖形化描述等各種方式，對經典資料結構內容做深入淺出的介紹。在介紹資料結構和演算法的基本概念和演算法分析方法的基礎之上，從軟體發展的角度，通過應用背景或知識背景介紹、資料分析、函數設計、演算法設計、測試調試等環節，分別對順序表、鏈表、棧、佇列、串、陣列、樹、圖等基本類型的資料結構進行了分析和討論；介紹資料的典型操作方法，如數據排序方法和查找方法；介紹常見的如遞迴法、分治法、動態規劃、貪心法等經典演算法。

周幸妮，西安電子科技大學副教授，長期從事“資料結構”、“C程式設計語言”等課程的教學工作，著有《C程式設計》等教材。

從新視角來看待舊問題，則需要創造性的思維——愛因斯坦
資料結構的教與學經歷
六七年前上資料結構課時，駕輕就熟地依然按照一貫的講法上課。上了幾次課後，收到班上一位同學的E-mail，信中說：“我自己是特別熱愛寫程式的。一方面我很熟悉電腦，軟硬體都有涉獵，所以學起來就不缺基礎的相關知識（像記憶體、寄存器、電子電路等等這些都很熟悉）；另一方面我好像很能適應，也很喜歡這種思維方式……但好像班上不少的同學對資料結構的學習理解和接受起來還是比較困難的……”
教授資料結構的課程也有十餘年了，一直以來，學生們總是認為資料結構不是一門容易學的課程，“在眾多的專業課中，資料結構被很多學生認為是一門很難學習的課程。”[1]雖然我在學校讀書時沒有學過資料結構的課程，只是因為後來要教書，才自學的資料結構。在自學的過程中，也並沒有覺著內容怎麼難啊，這是怎麼回事呢？
仔細回想一下自己學習與工作的經歷過程，或許就是來信的這位同學說的，是因為在學習資料結構書本知識之前，已經有了較強的程式設計的技能、一些資料結構實際應用的先驗知識吧。比如，在研究所工作時首次參加的軟體發展專案中，就有多進程、鏈表、佇列、散列等的實際應用，雖然在學校並沒有學過這些概念，而是先接觸到實際項目中要處理的問題，再看到其他程式師的具體演算法處理和程式實現方法，從實際的問題切入，就比較容易理解相應的資料組織形式和對應的演算法，等到後來再接觸到書本的理論知識，就有一種一通百通，豁然開朗的感覺。還有一個原因是在軟體發展過程中逐漸熟悉並掌握了程式調試方法，對常式通過跟蹤的方法，很容易弄清執行的路徑和結果，對演算法的設計和實現的理解也起到了事半功倍的效果。
回頭來看學生們學習的教科書，概念的介紹是傳統意義上的敘述方式，抽象度很高，但從實際到抽象、從抽象到實際的過程介紹不足，即感性認識不足，抽象就難以理解接受。“現在有一個不好的傾向，就是教材或課堂過於重視抽象化的知識，忽視應用背景。資料結構的教材是這一傾向的代表。這對入門階段的學生來講是不適宜的，因為學生難以走進所涉及的抽象世界，最終表現為不知道在講什麼。”[2]
再看我的學生，既沒有實際軟體發展的經驗也沒有熟練的程式設計調試基礎，對資料結構結構沒有感性認識，先接觸的是那些抽象的概念，感到理解和接受困難也就可以理解了。鄒恒明在《資料結構：炫動的0、1之弦》一書中指出，對於很多人來說，資料結構的概念並不難，真正的難點是：
（1）如何實現從資料結構概念到程式實現的跨越（即如何實現一個資料結構）；
（2）如何實現從實際應用到資料結構抽象的跨越（即如何利用資料結構解決實際問題）。
對於我來說，僅僅在學校學了一點點程式設計語言（記得所有上機時間加起來不超過20小時），沒有任何資料結構的知識，剛出校門就參與了歷時三年多後來獲得國家科技進步三等獎的大型軟體發展工作，以及後續多個電信使用者單位的實際軟體安裝、應用調試和維護工作，親歷了實現了上述兩個“跨越”的最實際生動的案例。雖然專案的開發過程非常艱苦，有在使用者單位調試現場連續大半年的天天加班到深夜、第二天依然要正點到機房的超負荷工作，有通宵的跟蹤調試，有24小時線上系統記憶體洩漏的巨大壓力，有上線後雙機備份系統同時崩潰爭分奪秒找bug的驚心動魄，等等。應該說自己是很幸運的，雖然在學校僅僅學習了一點點程式設計的概念，但在工作中根據需要自學和向同事學習了很多新知識、經驗和技巧，這樣的實踐磨練，對後來的程式設計類課程的理解和教授，是非常有益的。
學習資料結構困難的癥結所在
回想與總結起來，之所以要有上述兩個鴻溝要“跨越”，也是由於學校的傳統教科書教法和實際的應用要求脫節造成的。
弗裡德里希?威廉?尼采曾寫道：“人們無法理解他沒有經歷過的事情。”[3]換句話來說，我們只接受與過去早已理解的事物相關的資訊。這是一種比較學習的過程，在這個過程中，大腦要尋找每條資訊之間的聯繫，借助以往經驗來理解新事物[4]。
“歐拉認為，如果不能把解決數學問題背後的思維過程教給學生的話，數學教學就是沒有意義的。現代電腦實質上的發明者萊布尼茲也說過：在我看來，沒有什麼能比探索發明的源頭還要重要，它遠比發明本身更重要。從小到大，我們看過的數學書幾乎無一不是歐幾裡德式的：從定義到定理，再到推論。這樣的書完全而徹底地扭曲了數學發現的真實過程。目前幾乎所有的演算法書的講解方式也都是歐幾裡德式的，每一個推導步驟都是精准制導直接面向資料結構目標的，實際上，這完全把人類大腦創造發明的步驟給反過來了。對讀者來說，這就等於直接告訴你答案和做法了，然後讓你去驗證這個答案和做法是可行或成立的，而關於答案和做法到底是怎麼來的，從問題到答案之間經歷了怎樣的思維過程，卻鮮有書能夠很好地闡釋。對於這類知識講述（歐幾裡德方式）方式的批判，西方（尤其是在數學領域）早就有了。”[5]
傳統資料結構教科書的一般模式都是給出問題，然後直接給出演算法，而實際上要用電腦解決問題，必須要考慮的處理步驟有：如何分析問題中的已知資訊，如何提煉資料及資料間的聯繫（資料的邏輯結構），如何選用合適的存儲方式（資料的存儲結構）將邏輯結構存到電腦中，然後在存儲結構之上按照自頂向下逐步細化的方法給出演算法，這才是真正解決實際問題的思維方法和步驟，也是軟體發展中實際採用的方法。傳統教科書的問題在於沒有一個思維過程的引導與分析，致使概念論述、實現細節有餘，設計實現過程描述不足，讓學生看到的只是一個個問題具體的詳解，而把握不住演算法設計的總方法和原則。
本書嘗試從學以致用的角度，注意給出問題或演算法的知識背景或應用背景，增加一些在實際軟體發展中的演算法應用背景或實例；強調演算法的分析方法、設計思路、給出重要演算法的測試及調試分析，彌補上述傳統教科書中的不足。教學生以“軟體發展的方法”處理問題，使學生容易理解並掌握它，在實際的軟體發展過程中能靈活地選擇適當的邏輯結構、存儲結構及相應的演算法，設計性能優、效率高、可讀性強、易維護的程式，達到資料結構課程最終的目的。
程式設計與資料結構的關係
我們在學習資料結構知識之前要有程式設計的基礎，那麼我們先來看看與程式設計相關的問題。
什麼是程式設計？程式設計不僅僅是對語法的掌握，還涉及下面的諸多方面：
（1）程式的解題思路——演算法是基本運算及規定的運算順序所構成的完整的解題步驟，是程式的靈魂，演算法的優劣直接影響程式的效率。本書的演算法描述方法見稍後的說明。
（2）程式的運行速度——程式運行的速度受很多因素的影響。使用者對程式的運行速度往往是有要求的，如實時回應系統。
（3）程式的運行空間——代碼運行需要相應的記憶體空間及相關運行環境。在有些應用場合，對程式佔用空間是有限制的，如嵌入式系統。
（4）代碼規範——代碼要按照一定的規範格式書寫，以保證代碼的一致性，便於交流和維護。
（5）程式的結構—— 一個功能複雜的程式由多個功能相對獨立的模組組成。模組內高內聚，模組間低耦合，是判斷程式結構是否合理的標準。
（6）模組介面——模組間的資訊交流通過介面完成，模組間資訊傳遞參數的設置應該合理有效。
（7）程式的測試與調試——要有精心設計的測試樣例來測試程式是否正確。調試是高效率完成軟體產品的有效方法。一個程式高手，也是調試專家，調試的經驗方法多數都是實踐中得到的。
我們在學習資料結構知識之前要有程式設計的基礎，那麼資料結構與程式設計間的關係是怎樣的呢？應該說資料結構是編寫規模龐大、邏輯複雜的更高級程式所需的基礎。表0.1給出了程式設計與高級程式設計的特點。
表0.1 程式設計與高級程式設計
涉及課程 主要內容 課程目標
結構化程式
設計 程式設計基礎類課程 語言語法形式、語句使用規則
模組設計思想 編寫簡單程式
解決簡單問題
高級程式設計技術 資料結構 資料的抽象思維方法 編寫規模龐大、
邏輯複雜的程式
演算法的規範聲明、演算法的性能分析、演算法的性能評價
軟體工程 部件（模組）設計思想、軟體工程思想
……
程式設計的首要問題是模組劃分及相關問題，另一個重要方面，是把要解決問題的資訊轉換成電腦能認識並接收的資料，這一轉換過程就是資料的抽象過程。要處理規模龐大的複雜問題，必須掌握資料的抽象思維方法，同時還要熟練掌握演算法的規範聲明、演算法的性能分析、演算法的性能評價等諸多技能。
資料結構與其他課程的關係
作為一門重要的專業核心必修課程，“資料結構與演算法”課程既是對以往課程的深入和擴展，也為深入學習其他專業課程打下基礎。課程中排序問題演算法以及基本的樹、圖等資料結構，是電腦科學的基本功。B+樹、散列（Hash）等高級資料結構，也是資料庫、作業系統、編譯原理、電腦網路等重要專業課程的基礎。本課程在電腦學科中與其他課程的關係如圖0.1所示。

圖0.1 “資料結構與演算法”課程在電腦學科中的重要地位
資料結構的重要性
商用程式師肖舸在他的博客中寫道：“這麼多年，我做過遊戲、通信、工業控制、教育、VoIP、伺服器集群等各個方向的項目，不可謂不寬。
但是我知道的是，其實我都是在用一種方法寫程式。那就是從最底層的資料結構和演算法開始做起，用最基本的C、C++語言開發。用來用去，還是那麼幾個資料結構，佇列、堆疊，等等。
這好比武俠小說裡面的內功，內力修好了，學招式，非常容易。但如果沒有內力，練再好的招式，見到高手就軟了。一力破十慧，就是這個道理。在絕對的實力面前，任何花招都是沒有用的。”[6]
對清華大學電腦系歷屆畢業生和部分研究生追蹤調查顯示，幾乎所有的學生都認為“資料結構”是他們在學校裡學過的最有用的課程之一；資料結構是國內外許多軟體發展機構要求考核的基本課程之一；IT業公司面試或筆試考核的絕大部分內容是資料結構或演算法；資料結構也是電腦科學與技術、軟體工程等專業研究生考試必考科目。
資料結構會過時嗎
電子電腦自20世紀四十年代誕生以來硬體上不斷更新換代，軟體也是同步發展的，作為軟體的一個分支程式設計語言也從機器語言發展到了第四代，但無論軟體如何發展，無

第1章 緒論 1
1.1 從程式設計說起 1
1.2 程式要處理的資料 5
1.3 資料結構的引入 11
1.4 資料結構的基本概念 13
1.4.1 資料結構基本術語 13
1.4.2 資料結構的三個要素 13
1.5 如何設計演算法 16
1.5.1 演算法的定義及表示方法 16
1.5.2 演算法設計與函數設計的關係 17
1.5.3 軟體設計描述方法 18
1.5.4 演算法設計的一般步驟 19
1.6 如何評價演算法的優劣 21
1.6.1 演算法的設計要求 21
1.6.2 演算法效率的度量方法 22
1.7 演算法性能的事前分析方法 23
1.7.1 問題的規模與演算法的策略 23
1.7.2 演算法效率的上限與下限 25
1.7.3 漸進的上限——演算法的時間
複雜度 28
1.7.4 演算法時間複雜度的綜合討論 29
1.7.5 演算法的空間效率分析方法 33
1.8 演算法性能綜合考量 37
1.9 本章小結 38
習題 38
第2章 結點邏輯關係為線性的結構——線性表 41
2.1 從邏輯結構角度看線性表 41
2.1.1 實際問題中的線性關係 41
2.1.2 線性表的邏輯結構 42
2.2 線性表的存儲結構方法之一——順序表 43
2.2.1 順序表的存儲結構設計 43
2.2.2 順序表的運算 46
2.2.3 順序存儲結構的討論 53
2.3 線性表的存儲結構方法之二——鏈表 53
2.3.1 單鏈表的存儲 56
2.3.2 單鏈表的運算 60
2.3.3 單鏈表的討論 78
2.3.4 迴圈鏈表 78
2.3.5 雙向鏈表 81
2.3.6 鏈表小結 86
2.4 線性表的應用舉例 87
2.4.1 逆序輸出單鏈表結點值 87
2.4.2 一元多項式的相加 88
2.5 順序表和鏈表的比較 95
2.6 本章小結 96
習題 97
第3章 運算受限的線性表——棧和佇列 100
3.1 棧——按照先入後出的方式管理的線性表 100
3.1.1 棧處理模式的引入 100
3.1.2 棧的邏輯結構 104
3.1.3 棧的存儲結構設計 106
3.1.4 棧的操作 107
3.1.5 各種棧結構的比較 123
3.1.6 棧的應用舉例 123
3.2 隊列——按照先入先出方式管理的線性表 132
3.2.1 佇列處理模式的引入 133
3.2.2 佇列的邏輯結構 136
3.2.3 佇列的順序存儲結構 137
3.2.4 順序佇列的基本操作 148
3.2.5 佇列的鏈式存儲結構 152
3.2.6 鏈佇列的基本操作 153
3.2.7 各種佇列結構的比較 160
3.2.8 佇列的應用舉例 161
3.3 本章小結 171
習題 172
第4章 內容特殊的線性表——多維陣列與字串 175
4.1 多維陣列 175
4.1.1 陣列的概念 175
4.1.2 陣列的存儲結構 177
4.2 矩陣的壓縮存儲 181
4.2.1 對稱矩陣的壓縮存儲 182
4.2.2 三角矩陣的壓縮存儲 183
4.2.3 對角矩陣的壓縮存儲 183
4.2.4 疏鬆陣列的壓縮存儲 185
4.3 字串 189
4.3.1 字串的定義 189
4.3.2 字串的存儲結構 190
4.3.3 字串的查找——模式匹配 195
4.4 本章小結 211
習題 213
第5章 結點邏輯關係分層次的非線性結構——樹 216
5.1 實際問題中的樹 216
5.2 樹的邏輯結構 219
5.2.1 樹的定義和基本術語 219
5.2.2 樹的操作定義 222
5.3 樹的存儲結構 222
5.3.1 樹的連續存儲方式 223
5.3.2 樹的鏈式存儲方式 224
5.4 二叉樹的邏輯結構 226
5.4.1 二叉樹的概念 229
5.4.2 二叉樹的基本性質 230
5.4.3 二叉樹的操作定義 231
5.5 二叉樹的存儲結構及實現 231
5.5.1 二叉樹的順序結構 232
5.5.2 二叉樹的鏈式存儲
結構——二叉鏈表 235
5.5.3 建立動態二叉鏈表 236
5.6 二叉樹結點的查找 問題——樹的遍歷 240
5.6.1 樹的廣度優先遍歷 242
5.6.2 樹的深度優先遍歷 244
5.6.3 樹的遍歷的應用 255
5.7 樹的應用 259
5.7.1 運算式樹 259
5.7.2 線索二叉樹 260
5.7.3 哈夫曼樹及哈夫曼編碼 265
5.8 廣義表 278
5.8.1 廣義表的定義 279
5.8.2 廣義表的存儲 281
5.8.3 廣義表的基本運算 287
5.9 本章小結 293
習題 295
第6章 結點邏輯關係任意的非線性結構——圖 299
6.1 實際問題中的圖及抽象 299
6.2 圖的邏輯結構 304
6.2.1 圖的定義和基本術語 304
6.2.2 圖的操作定義 307
6.3 圖的存儲結構及實現 308
6.3.1 圖的陣列標記法1—— 鄰接矩陣 308
6.3.2 圖的陣列標記法2—— 邊集陣列 310
6.3.3 圖的鏈表標記法1——鄰接表 311
6.3.4 圖的鏈表標記法2—— 十字鏈表 316
6.3.5 圖的鏈表標記法3——鄰接多重表 317
6.3.6 圖各種存儲結構的歸結比較 319
6.4 圖的基本操作 320
6.4.1 鄰接矩陣的操作 320
6.4.2 鄰接表的操作 322
6.5 圖的頂點查找問題——圖的遍歷 328
6.5.1 圖的廣度優先遍歷BFS 329
6.5.2 圖的深度優先遍歷DFS 334
6.5.3 圖的遍歷小結 340
6.6 圖的經典應用——圖中的樹問題 340
6.6.1 生成樹 342
6.6.2 最小生成樹MST 343
6.6.3 求最小生成樹演算法1——Prim 演算法 344
6.6.4 求最小生成樹演算法2——Kruskal演算法 349
6.6.5 生成樹演算法小結 356
6.7 圖的經典應用——最短路徑問題 357
6.7.1 最短路徑問題的引入 357
6.7.2 單源最短路徑演算法——Dijkstra演算法 359
6.7.3 各頂點對間最短路徑演算法——Floyd演算法 364
6.7.4 最短路徑問題小結 369
6.8 圖的經典應用——活動頂點與活動邊的問題 370
6.8.1 圖的活動頂點排序問題的引入 370
6.8.2 AOV網與拓撲排序——活動頂點排序問題 373
6.8.3 AOE網與關鍵路徑——活動邊最長問題 378
6.8.4 活動頂點與活動邊問題小結 390
6.9 本章小結 390
習題 391
第7章 資料的處理方法——排序技術 397
7.1 概述 397
7.1.1 排序的基本概念 397
7.1.2 排序演算法的分類 399
7.2 插入排序 399
7.2.1 直接插入排序 399
7.2.2 希爾排序 402
7.3 交換排序 404
7.3.1 冒泡排序 404
7.3.2 快速排序 406
7.4 選擇排序 409
7.4.1 簡單選擇排序 410
7.4.2 堆排序 411
7.5 歸併排序 415
7.6 分配排序 418
7.6.1 桶排序 418
7.6.2 基數排序 421
7.7 各種排序演算法的比較 424
7.8 本章小結 427
習題 428
第8章 資料的處理——索引與查找技術 431
8.1 索引的基本概念 433
8.1.1 索引的定義 433
8.1.2 索引的邏輯特徵 434
8.1.3 索引的主要操作 435
8.2 線性索引技術 435
8.2.1 稠密索引 435
8.2.2 分塊索引 436
8.2.3 多重表 437
8.2.4 倒排表 439
8.3 樹形索引 441
8.3.1 二叉排序樹 441
8.3.2 B樹 448
8.4 查找概述 452
8.4.1 查找的基本概念 452
8.4.2 查找演算法的性能 453
8.5 線性表的查找技術 453
8.5.1 順序查找 453
8.5.2 有序表查找 454
8.5.3 索引查找 459
8.6 樹表的查找技術 461
8.6.1 二叉排序樹 461
8.6.2 B樹 462
8.6.3 在非數值有序表上的查找——字典樹 462
8.7 散列表的查找技術 464
8.7.1 散列概述 465
8.7.2 散列函數的設計 467
8.7.3 處理衝突的方法 469
8.7.4 散列查找的性能分析 473
8.8 本章小結 474
習題 476
第9章 經典演算法 479
9.1 遞迴演算法 479
9.1.1 遞迴的概念及要素 479
9.1.2 遞迴的應用場景 481
9.1.3 遞迴的電腦實現 482
9.1.4 遞迴方法特點分析 483
9.1.5 遞迴演算法實例 485
9.1.6 遞迴小結 487
9.2 分治演算法 487
9.2.1 分治是什麼 487
9.2.2 分治法的適用條件 488
9.2.3 分治問題的類型 488
9.2.4 分治法小結 490
9.3 動態規劃 491
9.3.1 什麼是動態規劃 491
9.3.2 動態規劃的解題方法 493
9.3.3 動態規劃解題實例 495
9.3.4 動態規劃小結 500
9.4 貪心演算法 501
9.4.1 貪心演算法是什麼 501
9.