數據結構：面向信息學競賽（簡體書）

目錄
教育技術學專業主幹課程系列教材總序
序
前言
第1章 概述 1
1.1 數據結構 2
1.1.1 數據與數據結構的定義 2
1.1.2 邏輯結構、物理結構和抽象數據類型 3
1.2 算法與算法分析 5
1.2.1 算法 5
1.2.2 算法的性質和判斷算法優劣的標準 5
1.2.3 算法分析 7
1.3 全國青少年信息學奧林匹克聯賽簡介 10
1.4 C++ STL簡介 11
習題 12
第2章 線性表 13
2.1 順序表 13
2.1.1 順序表的基本概念 13
2.1.2 順序表的實現 14
2.1.3 順序表操作的時間復雜度 19
2.2 C++ STL中順序表的用法 19
2.3 信息學競賽中順序表的應用 21
2.4 單鏈表 26
2.4.1 鏈表的基本概念 26
2.4.2 鏈表的實現 28
2.4.3 鏈表操作的時間復雜度 32
2.5 循環鏈表、雙向鏈表和靜態鏈表 32
2.5.1 循環鏈表 32
2.5.2 雙向鏈表 33
2.5.3 靜態鏈表 35
2.6 C++ STL中鏈表的用法 36
2.7 信息學競賽中鏈表的應用 37
習題 39
第3章 棧與隊列 40
3.1 棧 40
3.1.1 棧的基本概念 40
3.1.2 順序棧的實現 41
3.2 C++ STL中棧的用法 42
3.3 信息學競賽中棧的應用 42
3.4 隊列 48
3.4.1 隊列的基本概念 48
3.4.2 鏈式隊列的實現 51
3.5 C++ STL中隊列的用法 52
3.5.1 隊列queue的用法 52
3.5.2 優先級隊列priority_queue的用法 52
3.6 信息學競賽中隊列的應用 54
習題 57
第4章 遞歸 59
4.1 基本概念與用法 59
4.1.1 遞歸的基本概念 59
4.1.2 遞歸的特點 61
4.2 遞歸與棧的關係 61
4.3 遞歸算法 63
4.3.1 窮舉法 63
4.3.2 分治法 65
4.3.3 回溯法 70
4.4 信息學競賽中遞歸的應用 74
習題 78
第5章 串 79
5.1 串的基本概念 79
5.2 串的存儲結構 80
5.2.1 串的順序存儲 80
5.2.2 串的鏈式存儲 85
5.3 串的模式匹配算法 85
5.3.1 Brute-Force算法 85
5.3.2 KMP算法 87
5.4 C++ STL中字符串的用法 91
5.4.1 string的頭文件、定義與初始化 91
5.4.2 string的基本操作 91
5.5 信息學競賽中字符串的應用 93
習題 95
第6章 樹 97
6.1 樹的基本概念 97
6.2 二叉樹 98
6.2.1 二叉樹的基本概念與性質 98
6.2.2 二叉樹遍歷 101
6.3 哈夫曼樹 108
6.3.1 變長編碼 108
6.3.2 哈夫曼樹與哈夫曼編碼 110
6.4 樹與森林 115
6.4.1 樹與森林的表示方法 115
6.4.2 等價類問題與並查集算法 118
6.5 信息學競賽中樹的應用 121
習題 123
第7章 圖 125
7.1 圖的基本概念 125
7.1.1 圖的定義 125
7.1.2 圖的基本術語 125
7.2 圖的存儲方法 127
7.2.1 鄰接矩陣存儲方法 127
7.2.2 鄰接表存儲方法 129
7.3 圖的遍歷 131
7.3.1 深度優先搜索遍歷 131
7.3.2 廣度優先搜索遍歷 132
7.3.3 非連通圖的遍歷 133
7.4 *小生成樹問題 134
7.4.1 生成樹 134
7.4.2 *小生成樹 135
7.4.3 普裡姆算法 135
7.4.4 克魯斯卡爾算法 139
7.5 *短路徑問題 140
7.5.1 單源*短路徑 140
7.5.2 任意兩點間的*短路徑 144
7.6 拓撲排序 147
7.7 信息學競賽中圖的應用 149
習題 154
第8章 排序 156
8.1 冒泡排序 156
8.1.1 冒泡排序算法 156
8.1.2 冒泡排序的時間復雜度 159
8.2 插入排序 159
8.2.1 插入排序算法 159
8.2.2 插入排序的時間復雜度 161
8.3 歸並排序 161
8.3.1 歸並排序算法 161
8.3.2 歸並排序的時間復雜度 163
8.4 快速排序 165
8.4.1 快速排序算法 165
8.4.2 快速排序的時間復雜度 167
8.5 堆排序 170
8.5.1 堆的概念與建立堆的方法 170
8.5.2 堆排序算法 174
8.5.3 堆排序的時間復雜度 175
8.6 比較排序算法的實質 175
8.7 基數排序 177
8.7.1 線性時間排序算法 177
8.7.2 基數排序算法 178
8.7.3 鏈式基數排序算法 179
8.8 各種排序算法復雜度比較 181
8.9 C++ STL中排序算法的用法 182
8.9.1 幾種常用的STL sort算法函數簡介 182
8.9.2 sort函數使用方法 183
8.10 信息學競賽中排序的應用 184
習題 188
第9章 查找 189
9.1 二分查找法 189
9.1.1 二分查找法的實現 189
9.1.2 C++ STL中二分查找的用法 191
9.2 哈希表 193
9.2.1 哈希函數 194
9.2.2 開放定址法 195
9.2.3 鏈地址法 198
9.2.4 哈希表的時間復雜度 199
9.2.5 C++ STL中哈希表的用法 201
9.3 查找樹 203
9.3.1 二叉查找樹 203
9.3.2 紅黑樹 210
9.3.3 C++ STL中二叉查找樹的用法 217
9.4 信息學競賽中查找的應用 219
習題 223
第10章 動態規劃 225
10.1 動態規劃基礎 225
10.2 背包問題 230
10.3 區間動態規劃 234
10.4 信息學競賽中動態規劃的應用 238
習題 244
習題參考答案或提示 245
參考文獻 248

第1章 概述
什麼是數據結構？為什麼要學習它？
計算機和互聯網已經成為社會生活的重要組成部分，人們對各種計算機術語也越來越熟悉。因此，大部分計算機專業課程只聽名字就大概能知道或者猜到課程要講什麼，如“計算機網絡”、“操作系統”、“數據庫”或者“人工智能”。
但“數據結構”這個詞平常很少見，即使是科技時訊節目，也不會有“近日某國科學家發現了一種新型的數據結構”之類的報道。
既然如此，*好先通過幾個例子了解一下什麼是數據結構。
假設你是某個生活在幾十年前的“化石級”程序員，你和你周圍所有人掌握的計算機知識就是C語言，或許還有某個簡單的圖形庫。通過你們的不懈努力和艱苦攻關，你們先後完成了圖書管理系統、人事管理系統、飛機訂票系統和產品銷售系統等系統。這時你突然發現一個問題，這些系統要求的功能其實差不多，都是對圖書、員工、票據或產品組成的集合的增加、刪除、查詢、排序等操作。如果把圖書、產品等具體內容分離出來，而專門對數據集合和對數據集合的操作進行深入的研究，就可以得到一套系統的開發方法，甚至可以把這套方法寫成庫函數，以後開發類似系統時只需按圖索驥即可。
將具體問題抽象化之後，你會發現，一些看上去並不相關的領域其實需要解決的問題本質上是完全相同的，如以下兩個問題：
(1) 對於物流運輸行業，並不是總是直接從出發地到目的地，中間通常會經過若幹個城市。如何設計一個系統，只要將所有城市之間的運力和運輸成本等信息輸入，就可以計算出任意出發地到目的地的*優運輸路線(許多大型物流、快遞公司都有類似的系統，有些甚至精確計算到街道和十字路口)。
(2) 對於計算機網絡，信息發送者和接收者通常都不是直接相連的，而是經過若幹個路由器。如何設計一種方法，只要能獲取所有路由器之間的傳輸時延和帶寬限制，路由器就會自己選擇*優路徑，並向*優路徑上的下一個路由器發送數據包(現在的互聯網絡由就是建立在這種方法上的)。
只要稍加思考，就會發現這兩個問題的實質是一樣的：已知一個由許多頂點連接而成的網狀結構，並且已知這些頂點間的連接成本，要求設計一種方法，能讓計算機替我們找出任意兩頂點間成本*低的路徑。
數據結構學習和研究的主要目的是：對一些常見的具體問題進行抽象，並加以學習研究，以便今後碰到類似問題可以舉一反三。有些時候這門研究也被稱為算法研究。“算法”應該聽起來比“數據結構”稍微親切一些，畢竟這個詞在科技新聞和網絡文章裡經常出現。
1968年，美國的高德納(Donald E. Knuth)教授開創了數據結構和算法的*初體系，他的著作《計算機程序設計藝術》是第一部系統闡述數據結構和算法的著作。1971年，沃斯(Niklaus Wirth)進一步提出了“算法+數據結構=程序”的結構化程序設計理念，他反對拿到問題就直接編寫代碼，而是分若幹步進行，逐步求精。第一步先確定所需要的數據結構、寫出算法的大致框架，第二步編寫出的程序抽象度有所降低，直至*後編寫出可執行的程序。隨著計算機硬件和編程工具的快速發展以及軟件需求者群體的改變，今天的軟件開發模式已經發生了很大變化，面向物件、測試驅動開發、重構、設計模式和迭代式開發等新的軟件工程方法開始取代結構化程序設計理念，但“算法+數據結構=程序”這一公式仍被稱為計算機科學中的“E = mc2”。在計算機發明以來的短短數十年間，計算機領域的無數科學家和工程師對各種數據結構和算法進行了非常深入及廣泛的研究，研究成果應用於計算機科學和工程的各個領域，成為計算機程序設計的基石。經過數十年的研究和探索，傳統意義上的數據結構體系已經完整地建立，各種相關研究也基本完成，各種數據結構和算法作為程序設計的基石，被許多語言吸收為它們基本類庫、函數庫或擴展工具包的一部分。
1.1 數據結構
1.1.1 數據與數據結構的定義
數據(data)是計算機可以存儲和處理的所有內容的統稱。計算機中的各種文件，包括文字、圖像、聲音和視頻等，都是數據；計算機內存和緩存中所有的內容，都是數據；甚至計算機的源代碼和可執行代碼，也屬於數據。
數據元素(data element)是數據的基本單位。例如，學生信息表中的一個學生，圖書管理系統中的一本圖書，互聯網上的一臺路由器，在程序設計或數據結構分析中通常作為一條數據進行考慮，或者說是一個數據元素。但是一個學生又可以包括姓名、學號、專業等信息(表1-1)，這些信息稱為數據項。
表1-1 學生信息表
數據結構(data structure)是相互之間存在一種或多種特定關係的數據元素的集合。根據元素間關係的不同，可以大致將數據結構分為三大類：線性結構、樹形結構和圖狀結構。如果用圓圈(又稱結點)表示一個數據元素，用結點間的連接線表示兩個數據元素之間的關係，那麼可以將這三種結構畫成類似圖1 1所示的示意圖。
圖1-1 三種基本數據結構
結合示意圖，這裡先簡要說明三種基本數據結構的特點，本書後面還會分別進行詳細介紹。
線性結構中，除了開始和末尾結點，每個結點只有**的前驅(左側)結點和後繼(右側)結點。
樹形結構中，除了開始結點(*上方的結點)，每個結點只有**的前驅(上層)結點；除了終端結點(沒有下層結點的結點)，每個結點有一個或多個後繼(下層)結點。整個結構像一棵反向的樹，*上面是樹根，*下面是樹葉，中間是樹枝，因此稱為樹形結構。
圖狀結構中，每個結點可以有多個前驅結點和多個後繼結點。圖狀結構也是數據結構基本關係中*復雜的一種。
這裡“前驅”和“後繼”是為了分析問題的需要而臨時定義的兩結點間的關係，有些問題中數據元素存在前後關係，有些問題中數據元素不存在前後關係，讀者不必過分糾結這一概念。
1.1.2 邏輯結構、物理結構和抽象數據類型
另外兩個經常會用到的概念是邏輯結構和物理結構。
邏輯結構是使用自然語言去描述只存在於想象中的數據之間的關係，或者用更規範的方式來描述——為數據間的關係建立數學模型。
物理結構是數據在計算機中實際存儲的情況，所以也稱為存儲結構。
邏輯結構用於說明“做什麼”，而物理結構旨在說明“如何做”。它們的關係有點像兩位計算機創始人圖靈(Alan Turing)和埃克特(J. Presper Eckert)各自眼中的計算機。在圖靈眼中，計算機只不過是一條無窮的紙帶，它記錄和保存狀態，並根據輸入內容和當前狀態進行輸出。在埃克特眼中，計算機是一個占地170m2，由數萬個電子管、電阻器和電容器組成的耗電大戶，每一次加法都需要一組電氣元件齊心協力才能完成。
舉個例子，可以把線性結構描述為如下數學形式：
對於數據元素構成的集合，存在數據關係。
D是一個集合，它定義了之前線性結構示意圖中的所有結點。關係R也是一個集合，它定義了之前示意圖中所有結點間的連接。
但是這一定義並沒有為我們用代碼實現這種數據結構提供太多有用的信息。如圖1 2所示，如果用加以限定的數組來實現線性表，那麼在內存中ai確實剛好緊跟在ai1後面；如果用鏈表來實現，那麼在內存中ai可能在ai-1後面，也可能在它前面，ai與ai-1間可能會跳過很多內存空間。如果我們去推敲計算機中存儲數據的細節，那麼就屬於分析存儲結構了。
圖1-2 邏輯上的線性結構可以對應不同的物理結構
邏輯結構定義了數據集合與數據關係，但即使對於一個抽象的問題，僅僅定義集合和關係也是不夠的，至少還需要定義對數據集合的基本操作。
舉例來說，如果需要抽象學生管理系統、圖書管理系統、產品管理系統的主要特征，那麼除了定義一個並列、有序關係的集合，還應該定義包括對集合內的數據進行增加、刪除、排序和檢索等基本操作，之後就可以根據這些定義來逐一實現這些基本操作，*後把研究的結果用於各種具體的系統。只有這樣，我們對抽象問題的研究才有意義。
定義一個數據集合、集合中各元素間的數據關係以及對數據集合的基本操作，稱為定義一種抽象數據類型(abstract data type)。
數據結構的研究基本上圍繞抽象數據類型展開：首先找到一類具有共同特征的問題，將這種問題定義為一種抽象數據類型，然後分析和實現這種抽象數據類型的各種基本操作，從而得到一種具有通用性的數據結構或算法。
從C語言實現的角度來看，可以認為抽象數據類型是定義了一個結構體和一系列以這個結構體類型的變量為參數的函數。從C++或者Java等面向物件的程序設計語言實現的角度來看，抽象數據類型定義了一個類或模板類。
1.2 算法與算法分析
有了數據結構，還要有用數據結構具體解決問題的方法，也就是算法。算法和數據結構密不可分，離開算法，數據結構沒有存在的價值。因此，在學習數據結構的過程中一般都會同時學習相關算法。
1.2.1 算法
算法(algorithm)是使用計算機求解特定問題步驟的一種描述，它是一系列解決問題的清晰指令。
算法並不限定描述語言，甚至可以用自然語言描述算法。但算法終究是要指揮計算機解決問題的，而計算機又不像人一樣能主動對問題進行界定、補充、分析和嘗試，為確保算法沒有超出計算機的理解能力，*好是用一種程序設計語言來描述它。
因為算法的讀者是人而不是計算機或編譯器，所以算法描述不需要像源代碼那麼精確，只要作者和讀者能理解彼此的意思即可，有時候算法會用不標準的語言來描述，忽略一些不太重要的細節和步驟，這些語言稱為偽代碼。
1.2.2 算法的性質和判斷算法優劣的標準
一個算法應該具備以下五條性質：
(1) 有窮性，即算法必須能在執行有限個步驟之後終止。
(2) 確定性，即算法的每一步驟必須有確切的定義，讀者理解時不會產生歧義。
(3) 可行性，即算法的任何步驟都可以分解為有限次基本的可執行操作，不會超出程序設計語言語法可以實現操作的範圍。
(4) 有輸入，一個算法有0個或多個輸入。
(5) 有輸出，一個算法有1個或多個輸出。
除了這些基本性質，算法還應該具備以下特點，這些特點有時不是必需的，而是用來判斷一個算法優劣的標準。
(1) 正確性。這條標準看上去非常可笑，難道還能允許錯誤的算法存在嗎？對於絕大部分程序，理論上確實不應該出現任何錯誤，尤其是一些事關國計民生、人命關天的程序，如航天、軍事、銀行、電力和通信行業，程序一旦出現了錯誤(稱為bug)，可能導致難以彌補的重大損失。至於同學們做練習的程序出了錯，那更是不要怪機器不給力，要認認真真分析問題。
然而，在統計科學和人工智能領域，少量錯誤不可避免，必須接受。舉個例子，即使是*先進的人臉檢測算法，也不能保證100%的正確率，在復雜的光照、遮擋、陰影和混雜背景下，正確率甚至更低。自然語言理解、語音識別、目標跟蹤、垃圾郵件過濾和信息檢索等領域都存在類似的問題，科學家和工程師為減少1%的錯誤而歡欣鼓舞。對於這些算法，正確率是判斷程序好壞*重要的性能指標。
(2) 可讀性。即使算法設計的目標是讓機器去執行命令，算法本身仍然是作者和讀者交流的重要工具，也可以讓作者清晰記錄下自己的設計思路以備將來查詢和修改，因此良好的書寫和描述方法有助於人對算法的理解。這一原則對於源代碼同樣適用，源代碼不僅僅要作為給機器的指令，也是程序員之間相互交流的重要手段。如何書寫可讀性強的源代碼，可以參考林銳博士等所著的《高質量程序設計指南——C++/C語言》。
(3) 健壯性(robustness)。健壯性是指當輸入數據的取值不在合理範圍內時，算法也能做適當處理，而不是崩潰或出現邏輯錯誤。例如，一個計算器程序，當輸入的除數為0時，應該給出相應的出錯信息，而不是毫無知覺地進行計算。又如，當