數據結構與算法（倉頡版）

周元哲，1974年9月生，西安郵電大學副教授，從事計算機專業科研和教學。講授“C程序設計語言”“數據庫原理”“軟件測試”“Python程序設計”“軟件工程”“軟件算法與競賽“等課程。在 2020年“第十三屆中國大學生計算機設計大賽全國總決賽”中，指導本校“軟件工程 1802 班”同學榮獲二等獎；作為軟件算法指導教師，榮獲 ACM-ICPC、CCPC區域賽等多屆銀牌、銅牌等獎項；“中國高校計算機大賽-團體程序設計天梯賽”優秀指導教師。兼任臨潼區華清小學胡王分校區科學副校長，是多所小初中的校外科普專家。九三學社社員，陜西省計算機教育學會理事，西安郵電大學軟件教師，榮獲 ACM-ICPC、CCPC、C4天梯賽、藍橋杯等算法優秀指導教師。 在機械工業出版社等出版《Python程序設計基礎》《數據結構與算法（Python版）》等多本教材。

前言
第1 章　數據結構與算法1
1.1　程序 1
1.2　數據結構 2
1.2.1　一個例子 . 2
1.2.2　數據結構組成部分 2
1.2.3　核心地位 . 4
1.3　算法 4
1.3.1　五個屬性 . 5
1.3.2　三個層次 . 6
1.4　算法覆雜性 6
1.4.1　空間覆雜度 7
1.4.2　時間覆雜度 7
1.4.3　算法效率 . 7
1.5　算法表示方式 .8
1.5.1　程序流程圖 8
1.5.2　N-S 圖 9
1.6　習題 10
第2 章　倉頡語言基礎12
2.1　倉頡語言簡介 12
2.1.1　倉頡語言發展歷程 . 12
2.1.2　倉頡語言核心特點 . 13
2.1.3　倉頡語言應用場合 . 14
2.1.4　倉頡語言版本 14
2.1.5　倉頡語言編輯器 15
2.2　倉頡語言在數據結構和算法方面的優勢 15
2.2.1　性能優勢 15
2.2.2　安全健壯 15
2.2.3　開發效率 15
2.3　CodeArts IDE for Cangjie 16
2.3.1　下載與安裝 . 16
2.3.2　關聯 Cangjie SDK 17
2.3.3　第一個程序——Hello，Cangjie ！ 18
2.3.4　倉頡文件架構 19
2.4　VS Code 與倉頡插件 20
2.4.1　下載與安裝VS Code 20
2.4.2　VS Code 安裝倉頡插件 20
2.5　DevEco Studio 開發環境 21
2.6　cjpm 項目管理 .22
2.6.1　安裝與驗證 . 22
2.6.2　常用命令 22
2.7　習題 23
第3 章　倉頡語言數據類型24
3.1　變量 24
3.1.1　變量基本概念 24
3.1.2　命名規則 24
3.1.3　變量分類 25
3.2　三種聲明方式 25
3.2.1　不可變變量 . 25
3.2.2　可變變量 26
3.2.3　常量 . 26
3.3　基本數據類型 26
3.3.1　整數類型 26
3.3.2　浮點數類型 . 28
3.3.3　布爾值類型 . 28
3.3.4　字符類型 29
3.3.5　Unit 類型 30
3.4　運算符 31
3.4.1　算術運算符 . 31
3.4.2　關系運算符 . 33
3.4.3　賦值運算符 . 34
3.4.4　邏輯運算符 . 35
3.4.5　位運算符 37
3.4.6　運算符優先級 38
3.5　習題 41
第4 章　三大流程控制結構42
4.1　三種基本結構 42
4.2　順序結構 .42
4.2.1　輸入語句 43
4.2.2　輸出語句 44
4.3　分支結構 .45
4.3.1　單分支 45
4.3.2　雙分支 46
4.3.3　多分支 46
4.3.4　分支嵌套 50
4.4　循環結構 .52
4.4.1　循環結構概述 52
4.4.2　while 循環語句 . 52
4.4.3　do-while 循環語句 53
4.4.4　for-in 循環語句 . 54
4.4.5　break 語句 55
4.4.6　continue 語句 . 56
4.4.7　循環嵌套 58
4.5　實例——雞兔同籠問題 .59
4.6　習題 59
第5 章　函數61
5.1　函數概述 .61
5.1.1　函數基本概念 61
5.1.2　函數聲明 61
5.2　實參與形參 62
5.2.1　基本類型作為參數 . 62
5.2.2　引用類型作為參數 . 62
5.3　參數分類 .63
5.3.1　非命名參數 . 63
5.3.2　命名參數 64
5.3.3　非命名參數和命名參數 64
5.4　Lambda 表達式 65
5.4.1　Lambda 表達式基本概念 65
5.4.2　舉例 . 65
5.5　函數重載 .66
5.5.1　函數重載基本概念 . 66
5.5.2　函數重載實現 66
5.6　遞歸函數 .67
5.6.1　引入 . 67
5.6.2　原理和實現 . 68
5.6.3　漢諾塔問題 . 69
5.7　變量作用域 70
5.7.1　局部變量 71
5.7.2　全局變量 71
5.8　實例——心靈感應魔法 .72
5.9　習題 76
第 6 章　數據容器.77
6.1　數據容器簡介 77
6.2　字符串類型 77
6.2.1　單行字符串和多行字符串 . 77
6.2.2　字符串與字符 78
6.2.3　字符串操作 . 78
6.2.4　字符串成員函數 80
6.3　枚舉類型 .81
6.3.1　枚舉基本概念 81
6.3.2　枚舉方法實現 82
6.4　元組類型 .83
6.4.1　元組基本概念 83
6.4.2　元組操作 83
6.4.3　元組解構 83
6.5　區間類型 .84
6.5.1　區間類型基本概念 . 84
6.5.2　區間類型操作 84
6.6　數組類型 .85
6.6.1　數組基本概念 85
6.6.2　創建數組 85
6.6.3　數組操作函數 87
6.7　結構體 88
6.7.1　結構體基本概念 88
6.7.2　結構體成員變量 88
6.7.3　結構體普通構造函數 89
6.8　ArrayList .90
6.8.1　創建ArrayList 90
6.8.2　ArrayList 增刪改查操作 . 90
6.8.3　與 Array<T> 對比 92
6.9　HashMap .92
6.9.1　HashMap 基本概念 92
6.9.2　HashMap 操作 92
6.10　HashSet .93
6.10.1　HashSet 基本概念 93
6.10.2　HashSet 操作 94
6.11　值類型和引用類型 .95
6.11.1　值類型 . 95
6.11.2　引用類型 96
6.12　實例——統計字符串中各字符出現的次數 .97
6.13　習題 .98
第 7 章　泛型99
7.1　泛型概述 .99
7.1.1　泛型基本概念 99
7.1.2　泛型優點 99
7.2　泛型函數 100
7.2.1　全局泛型函數 . 100
7.2.2　局部泛型函數 . 101
7.3　泛型結構體 .101
7.4　泛型類 102
7.5　泛型接口 103
7.6　std.collection 包 104
7.6.1　forEach<T> 104
7.6.2　filter<T> . 105
7.6.3　map<T，R> 105
7.6.4　reduce <T> 106
7.7　實例——學生課程信息管理系統 .107
7.7.1　功能描述 107
7.7.2　代碼 107
7.7.3　代碼解析 .113
7.8　習題 .114
第 8 章　面向對象基礎 117
8.1　面向對象概述 117
8.1.1　類和對象 .117
8.1.2　類與結構體的關系 118
8.1.3　類實現 118
8.2　構造函數 119
8.2.1　普通構造函數 119
8.2.2　主構造函數 120
8.3　成員變量 120
8.3.1　實例成員變量 . 120
8.3.2　靜態成員變量 . 121
8.4　屬性 .122
8.4.1　可變屬性 122
8.4.2　不可變屬性 123
8.5　封裝性與訪問控制 .123
8.5.1　封裝性基本概念 123
8.5.2　四種訪問 123
8.5.3　倉頡實現封裝性 125
8.6　繼承性 126
8.6.1　繼承性基本概念 126
8.6.2　倉頡實現繼承性 126
8.7　重寫和重定義 127
8.7.1　實例成員重寫 . 127
8.7.2　靜態成員重定義 129
8.8　多態性 129
8.8.1　多態性基本概念 129
8.8.2　倉頡實現多態性 130
8.9　抽象類 131
8.9.1　抽象類基本概念 131
8.9.2　抽象類實現 131
8.10　接口 133
8.10.1　接口基本概念 133
8.10.2　接口實現 . 133
8.11　實例——數字猜謎遊戲 .134
8.12　習題 136
第 9 章　文件.138
9.1　文件概述 138
9.1.1　ASCII 文件 138
9.1.2　二進制文件 138
9.2　I/O 操作 139
9.3　ASCII 文件操作 139
9.3.1　ASCII 文件打開模式 . 139
9.3.2　讀寫ASCII 文件 141
9.4　二進制文件操作 142
9.4.1　寫二進制文件 . 142
9.4.2　讀二進制文件 . 143
9.5　習題 .143
第 10 章　異常處理145
10.1　錯誤類型 145
10.1.1　語法錯誤 . 145
10.1.2　運行時錯誤 145
10.1.3　邏輯錯誤 . 146
10.2　異常類型體系 .147
10.2.1　Error 類 148
10.2.2　Exception 類 148
10.3　捕獲和處理異常 151
10.3.1　trycatch . 151
10.3.2　Option<T> 152
10.3.3　自定義異常類型 . 153
10.4　調試 154
10.4.1　標準調試 . 154
10.4.2　反向調試 . 154
10.4.3　CodeArts IDE for Cangjie 調試 154
10.5　習題 155
第 11 章 線性表 .157
11.1　線性表概述 157
11.1.1　線性表基本概念 . 157
11.1.2　線性表特性 157
11.2　線性表存儲 157
11.2.1　線性表順序存儲 . 158
11.2.2　線性表鏈式存儲 . 158
11.3　線性表操作 158
11.3.1　具體內容 . 158
11.3.2　實現代碼 . 158
11.4　棧 159
11.4.1　棧基本概念 159
11.4.2　棧操作 160
11.5　隊列 161
11.5.1　隊列基本概念 161
11.5.2　隊列操作 . 163
11.6　串 164
11.6.1　串基本概念 164
11.6.2　串操作 165
11.7　實例——模式匹配 166
11.8　習題 171
第 12 章 樹和二叉樹173
12.1　樹和二叉樹概述 173
12.1.1　樹相關概念 173
12.1.2　二叉樹基本概念 . 174
12.1.3　二叉樹特性 174
12.2　二叉樹存儲 176
12.2.1　二叉樹順序存儲 . 176
12.2.2　二叉樹鏈式存儲 . 176
12.3　二叉樹遍歷 177
12.3.1　二叉樹遍歷基本概念 177
12.3.2　四種遍歷實現 177
12.4　由遍歷序列創建二叉樹 183
12.4.1　由先序遍歷和中序遍歷推出後序遍歷 . 183
12.4.2　由中序遍歷和後序遍歷推出先序遍歷 . 184
12.4.3　由先序遍歷和後序遍歷推出中序遍歷 . 184
12.5　哈夫曼樹 184
12.5.1　哈夫曼編碼 184
12.5.2　哈夫曼算法 185
12.6　樹和二叉樹存儲與轉換 192
12.6.1　樹的存儲 . 192
12.6.2　樹與二叉樹轉換 . 193
12.7　實例——數學表達式的中序二叉樹 .194
12.8　習題 198
第 13 章 圖論201
13.1　圖相關概念 201
13.2　圖的存儲 202
13.2.1　鄰接矩陣 . 202
13.2.2　鄰接表 203
13.3　圖的遍歷 203
13.3.1　深度優先遍歷 203
13.3.2　廣度優先遍歷 208
13.4　最小生成樹 212
13.4.1　克魯斯卡爾（Kruskal） 算法 . 212
13.4.2　普裏姆（Prim） 算法 . 216
13.5　最短路徑 219
13.5.1　迪傑斯特拉（Dijkstra） 算法 219
13.5.2　弗洛伊德（Floyd） 算法 224
13.6　習題 228
第 14 章 查找231
14.1　查找算法 231
14.1.1　查找基本概念 231
14.1.2　兩種方式 . 231
14.2　基於線性表查找 231
14.2.1　順序查找 . 231
14.2.2　二分查找 . 233
14.2.3　分塊查找 . 235
14.3　二叉排序樹 238
14.3.1　二叉排序樹特性 . 238
14.3.2　二叉排序樹操作 . 239
14.4　平衡二叉樹 244
14.4.1　平衡因子 . 245
14.4.2　構建平衡二叉樹 . 245
14.4.3　平衡二叉樹實現代碼 248
14.5　哈希表 .256
14.5.1　哈希表基本概念 . 256
14.5.2　倉頡實現哈希表 . 256
14.6　實例——出現次數最多的整數 256
14.7　習題 257
第 15 章　排序259
15.1　排序概述 259
15.1.1　排序基本概念 259
15.1.2　排序分類 . 259
15.2　插入排序 260
15.2.1　直接插入排序 260
15.2.2　折半插入排序 262
15.2.3　希爾排序 . 263
15.3　交換排序 265
15.3.1　冒泡排序 . 265
15.3.2　快速排序 . 267
15.4　選擇排序 269
15.4.1　簡單選擇排序 269
15.4.2　堆排序 271
15.5　歸並排序 274
15.5.1　分治策略 . 274
15.5.2　歸並排序過程 275
15.5.3　歸並排序實現代碼 275
15.6　排序總結 276
15.6.1　時間性能 . 276
15.6.2　空間性能 . 276
15.6.3　穩定性能 . 276
15.6.4　排序算法選擇準則 277
15.7　實例——求最大值或最小值 .277
15.8　習題 278
附錄　ArkTS 編程語言 280
參考文獻282