C/C++ 常用算法手冊, 3/e C/C++常用算法手册(第3版)

第1篇算法基礎篇

第1章算法概述
1.1什麼是算法1 
1.2算法的發展歷史2 
1.3算法的分類3 
1.4算法相關概念的區別3 
1.5算法的表示4 
1.5.1自然語言表示4 
1.5.2流程圖表示5 
1.5.3 NS圖表示6 
1.5.4偽代碼表示6 
1.6偽代碼與算法程序的對應7 
1.6.1基本對應規則7 
1.6.2分支結構8 
1.6.3循環結構9 
1.6.4數組及函數9 
1.7算法的性能評價10 
1.8算法實例10 
1.8.1查找數字11 
【程序示例1-1】在擁有20個整數數據的數組中查找某個數據11 
1.8.2創建項目12 
1.8.3編譯執行13 
1.9算法的新進展14 
1.10小結15 

第2章數據結構
2.1數據結構概述16 
2.1.1什麼是數據結構16 
2.1.2數據結構中的基本概念17 
2.1.3數據結構的內容17 
2.1.4數據結構的分類19
2.1.5數據結構的幾種存儲方式19 
2.1.6數據類型20 
2.1.7常用的數據結構21 
2.1.8選擇合適的數據結構解決實際問題22 
2.2線性表22 
2.2.1什麼是線性表22 
2.2 .2線性表的基本運算23 
2.3順序表結構23 
2.3.1準備數據24 
2.3.2初始化順序表24 
2.3.3計算順序表長度25 
2.3.4插入結點25 
2.3.5追加結點25 
2.3. 6刪除結點26 
2.3.7查找結點26 
2.3.8顯示所有結點27 
2.3.9順序表操作示例27 
【程序示例2-1】對某班級學生學號、姓名和年齡數據進行順序表操作27 
2.4鍊錶結構31 
2.4.1什麼是鍊錶結構31 
2.4.2準備數據32 
2.4.3追加結點32 
2.4.4插入頭結點33 
2.4.5查找結點34 
2.4.6插入結點34 
2.4. 7刪除結點35 
2.4.8計算鍊錶長度36 
2.4.9顯示所有結點37 
2.4.10鍊錶操作示例37 
【程序示例2-2】使用鍊錶操作實現用戶管理37
2.5棧結構41 
2.5.1什麼是棧結構41 
2.5.2準備數據42 
2.5.3初始化棧結構43 
2.5.4判斷空棧43 
2.5.5判斷滿棧43 
2.5.6清空棧44 
2.5.7釋放空間44 
2.5.8入棧44 
2.5.9出棧45 
2.5.10讀結點數據45 
2.5.11棧結構操作示例45 
【程序示例2-3】使用棧結構實現學生數據操作45 
2.6隊列結構48 
2.6. 1什麼是隊列結構48 
2.6.2準備數據49 
2.6.3初始化隊列結構49 
2.6.4判斷空隊列50 
2.6.5判斷滿隊列50 
2.6.6清空隊列50 
2.6.7釋放空間51 
2.6.8入隊列51 
2.6.9出隊列52 
2.6.10讀結點數據52 
2.6.11計算隊列長度52 
2.6.12隊列結構操作示例53 
【程序示例2-4】使用隊列結構實現學生數據操作53 
2.7樹結構56 
2.7 .1什麼是樹結構56 
2.7.2樹的基本概念57 
2.7.3二叉樹57
2.7.4準備數據61 
2.7.5初始化二叉樹61 
2.7.6添加結點62 
2.7.7查找結點63 
2.7.8獲取左子樹64 
2.7.9獲取右子樹64 
2.7.10判斷空樹65 
2.7 .11計算二叉樹深度65 
2.7.12清空二叉樹65 
2.7.13顯示結點數據66 
2.7.14遍歷二叉樹66 
2.7.15樹結構操作示例68 
【程序示例2-5】經典二叉樹的遍歷（4種遍歷方式） 68 
2.8圖結構70 
2.8.1什麼是圖結構71 
2.8.2圖的基本概念71 
2.8.3準備數據75 
2.8.4創建圖77 
2.8.5清空圖78 
2.8.6顯示圖78 
2.8.7遍歷圖79 
2.8.8圖結構操作示例80 
【程序示例2-6】使用深度優先遍曆算法遍歷圖操作程序80 
2.9小結83 

第3章基本算法思想
3.1常用算法思想概述84 
3.2窮舉算法思想85 
3.2. 1窮舉算法基本思想85 
3.2.2窮舉算法示例85 
【程序示例3-1】雞兔同籠問題86
3.3遞推算法思想87 
3.3.1遞推算法基本思想87 
3.3.2遞推算法示例87 
【程序示例3-2】兔子產仔問題88 
3.4遞歸算法思想89 
3.4.1遞歸算法基本思想89 
3.4. 2遞歸算法示例90 
【程序示例3-3】求數字12的階乘90 
3.5分治算法思想91 
3.5.1分治算法基本思想91 
3.5.2分治算法示例91 
【程序示例3-4】從30枚銀幣中找出僅有的1枚假銀幣93 
3.6概率算法思想95 
3.6.1概率算法基本思想95 
3.6.2概率算法示例96 
【程序示例3-5】利用蒙特卡羅算法計算圓周率π 96 
3.7小結97 

第2篇算法應用篇

第4章排序算法
4.1排序算法概述98 
4.2冒泡排序法99 
4.2.1冒泡排序算法99 
4.2.2冒泡排序算法示例100 
【程序示例4-1】對包含10個數字的整型數組進行排序100 
4.3選擇排序法102 
4.3.1選擇排序算法102 
4.3.2選擇排序算法示例103 
【程序示例4-2】對包含10個數字的整型數組進行排序103 
4.4插入排序法105
4.4.1插入排序算法105 
4.4.2插入排序算法示例106 
【程序示例4-3】對包含10個數字的整型數組進行排序106 
4.5 Shell排序法108 
4.5.1 Shell排序算法108 
4.5.2 Shell排序算法示例109 
【程序示例4-4】對包含10個數字的整型數組進行排序109 
4.6快速排序法111 
4.6.1快速排序算法111 
4.6.2快速排序算法示例112 
【程序示例4-5】對包含18個數字的整型數組進行排序112 
4.7堆排序法114 
4.7.1堆排序算法114 
4.7.2堆排序算法示例119 
【程序示例4-6】對包含10個數字的整型數組進行排序119 
4.8合併排序法121 
4.8.1合併排序算法121 
4.8.2合併排序算法示例124 
【程序示例4-7】對包含15個數字的整型數組進行排序124 
4.9排序算法的效率127 
4.10排序算法的其他應用128 
4.10.1反序排序128 
4.10.2反序插入排序算法示例129 
【程序示例4-8】對包含10個數字的整型數組進行排序129 
4.10.3字符串的排序130 
4.10.4字符串排 示例131
【程序示例4-9】用快速排序算法對包含16個字母的字符串進行排序131 
4.10.5字符串數組的排序133 
4.10.6字符串數組排序示例134 
【程序示例4-10】用快速排序算法對包含5個單詞的字符串數組進行排序134 
4.11小結135
 
第5章查找算法
5.1查找算法概述136 
5.2順序查找137 
5.2.1順序查找算法137 
5.2.2順序查找操作示例137 
【程序示例5- 1】在包含15個數字的數組中查找第7個數字137 
5.3折半查找139 
5.3.1折半查找算法139 
5.3.2折半查找操作示例141 
【程序示例5-2】在包含15個數字的數組中查找第11個數字141 
5.4小結143
 
第6章基本數學問題
6.1判斷閏年144 
【程序示例6-1】判斷2000年到3000年之間所有的閏年145 
6.2多項式計算146 
6.2.1一維多項式求值146 
6.2.2一維多項式求值示例147 
【程序示例6-2】計算多項式在x取不同值時的值147 
6.2.3二維多項式求值148 
6.2.4二維多項式求值示例148 
【程序示 6-3】求4×5的二維多項式在給定處的值149
6.2.5多項式乘法150 
6.2.6多項式乘法示例150 
【程序示例6-4】計算兩個多項式的乘積多項式150 
6.2.7多項式除法151 
6.2.8多項式除法示例152 
【程序示例6-5】計算A (x)/B(x)的商多項式和余多項式153 
6.3隨機數生成154 
6.3.1 C語言中的隨機函數154 
【程序示例6-6】在0～32767之間產生一組隨機數154 
【程序示例6-7】輸出0～100之間的隨機整數155 
6.3.2 [0,1]之間均勻分佈的隨機數算法156 
【程序示例6-8】輸出10個0～1之間的隨機數156 
6.3.3產生任意範圍的隨機數157 
【程序示例6-9】輸出10個10.0～20.0之間的浮點隨機數157 
6.3.4 [m,n]之間均勻分佈的隨機整數算法158 
【程序示例6-10】輸出10個100～200之間的隨機整數158 
6.3.5正態分佈的隨機數生成算法159 
【程序示例6-11】輸出10個正態分佈的隨機數160 
6.4複數運算161 
6.4.1簡單的複數運算161 
6.4.2簡單複數運算示例163 
【程序示例6-12】計算兩個複 的加減乘除163 
6.4.3複數的冪運算164 
6.4.4複數的冪運算示例164
【程序示例6-13】一個複數的n（n=5）次冪運算164 
6.4.5復指數運算166 
6.4.6復指數運算示例166 
【程序示例6-14】一個複數的複指數運算166 
6.4 .7復對數運算167 
6.4.8復對數運算示例167 
【程序示例6-15】一個複數的複對數計算167 
6.4.9復正弦運算168 
6.4.10復正弦運算示例168 
【程序示例6 -16】一個複數的複正弦運算168 
6.4.11复餘弦運算169 
6.4.12复餘弦運算示例170 
【程序示例6-17】一個複數的複餘弦運算170 
6.5階乘170 
6.5.1使用循環計算階乘171 
6.5.2循環計算階乘示例171 
【程序示例6-18】求輸入整數的階乘運算結果171 
6.6計算π的近似值172 
6.6.1割圓術172 
6.6.2割圓術算法示例174 
【程序示例6- 19】用割圓術計算圓周率π（根據輸入的切割次數） 174 
6.6.3級數公式175 
6.6.4級數公式算法示例176 
【程序示例6-20】用級數公式的算法計算圓周率π 176 
6.7矩陣運算177 
6.7.1矩陣加法177
6.7.2矩陣加法示例178 
【程序示例6-21】計算兩個矩陣相加178 
6.7.3矩陣減法179 
6.7.4矩陣減法示例179 
【程序示例6-22】計算兩個矩陣相減179 
6.7. 5矩陣乘法180 
6.7.6矩陣乘法示例181 
【程序示例6-23】計算兩個矩陣相乘181 
6.8方程求解183 
6.8.1線性方程求解—高斯消元法183 
6.8.2高斯消元法示例186 
【程序示例6-24】3個變量、3個方程的方程組的高斯消元法求解186 
6.8.3非線性方程求解—二分法188 
6.8.4二分法算法示例189 
【程序示例6-25】使用二分法來求方程的解189 
6.8.5非線性方程求解—牛頓迭代法190 
6.8.6牛頓迭代法示例191 
【程序示例6-26】使用牛頓迭代法求方程的解191 
6.9小結193 

第7章複雜的數值計算算法
7.1拉格朗日插值194 
7.1.1拉格朗日插值算法194 
7.1.2拉格朗日插值示例195 
【程序示例7-1】給出10個數據點，求解x不同取值時的函數近似值196 
7.2數值積分198 
7.2.1數值積 算法198
7.2.2數值積分示例199 
【程序示例7-2】求解兩個定積分的數值計算結果199 
7.3開平方201 
7.3.1開平方算法201 
7.3.2開平方示例201 
【程序示例7-3】求解兩個數字開方的數值計算結果201 
7.4極值問題的求解算法203 
7.4.1極值求解算法203 
7.4.2迭代法極值求解示例205 
【程序示例7-4】給定函數和其對應的導函數，請對該函數求解205 
7.5特殊函數的計算算法209 
7.5.1伽瑪函數算法209 
7.5.2伽瑪函數求解示例210 
【程序示例7-5】求解伽瑪函數(2.0)和(3.0 )的值211 
7.5.3貝塔函數算法213 
7.5.4貝塔函數求解示例214 
【程序示例7-6】求解貝塔函數B(2.0,3.0)和B(1.5,4.5)的值214 
7.5.5正弦積分函數算法216 
7.5.6正弦積分函數求解示例217 
【程序示例7-7】求解正弦積分函數Si(2.0)和Si(5.5)的值218 
7.5.7餘弦積分函數算法220 
7.5.8餘弦積分函數求解示例221 
【程序示例7-8】求解餘弦積分函數Co(2.0)和Co(5.5)的值22 1 
7.5.9指數積分函數算法223
7.5.10指數積分函數求解示例225 
【程序示例7-9】求解指數積分函數Ex(2.0)和Ex(5.5)的值225 
7.6小結227 

第8章經典數據結構問題
8.1動態數組排序228 
8.1.1動態數組的存儲和排序算法228 
8.1.2動態數組排序示例229 
【程序示例8-1】對以0結束的動態字符數組進行排序229 
8.2約瑟夫環231 
8.2.1約瑟夫環算法232 
8.2.2約瑟夫環應用233 
【程序示例8-2】總數為41人，報數3者自殺，求解約瑟夫環的解233 
8.2.3約瑟夫環推廣應用算法235 
8.2.4約瑟夫環推廣應用236 
【程序示例8-3】 n個人環坐（順時針編號1、2、3…n），每人隨機取一張寫有數字的紙條，
報數m者出列，同時其手中數字為新的出列數字，求解約瑟夫環236 
8.3城市之間的最短總距離和最短距離238 
8.3.1最短總距離算法238 
8.3.2最短路徑算法241 
8.3.3最短總距離求解示例243 
【程序示例8-4】計算某地區5個城市間的最短總距離243 
8.4括 匹配247 
8.4.1括號匹配算法248 
8.4.2括號匹配求解示例249 
【程序示例8-5】對以0結束的一組括號進行匹配250
8.5小結253 

第9章數論問題
9.1數論概述及分類254 
9.1.1數論概述254 
9.1.2數論的分類255 
9.1.3基本概念256 
9.2完全數257 
9.2.1完全數概述257 
9.2.2生成完全數算法258 
9.2.3查找完全數算法示例259 
【程序示例9-1】查找10000以內的所有完全數259 
9.3親密數（對） 260 
9.3.1親密數（對）概述260 
9.3.2查找親密數對算法260 
9.3.3查找親密數對算法示例261 
【程序示例9-2】查找5000以內的所有親密數對261 
9.4水仙花數263 
9.4.1水仙花數概述263 
9.4.2查找水仙花數算法263 
9.4.3查找水仙花數算法示例264 
【程序示例9-3】查找3位數和4位數的水仙花數264 
9.5自守數266 
9.5.1自守數概述266 
9.5.2查找自守數算法267 
9.5.3查找自守數算法示例268 
【程序示例9-4】用兩種算法查找1000以內和200000以內的自守數268 
9.6最大公約數和最小公倍數270
9.6.1計算最大公約數算法—輾轉相除法270 
9.6.2計算最大公約數算法—Stein算法271 
9.6.3計算最小公倍數算法272 
9.6.4計算最大公約數示例273 
【程序示例9-5】用輾轉相除法計算12和34的最大公約數273 
9.6.5計算最小公倍數示例274 
【程序示例9-6】求12和34的最小公倍數274 
9.7素數275 
9.7.1素數概述275 
9.7.2查找判斷素數算法276 
9.7.3查找判斷素數算法示例276 
【程序示例9-7】查找判斷1～1000之間的所有素數276 
9.8回文素數277 
9.8.1回文素數概述277 
9.8.2查找判斷回文素數算法278 
9.8.3查找判斷回文素數算法示例279 
【程序示例9-8】查找判斷0～50000之間的回文素數279 
9.9平方回文數280 
9.9.1平方回文數概述280 
9.9.2查找判斷平方回文數算法281 
9.9.3查找判斷平方回文數算法示例281 
【程序示例9-9】判斷查找1～1000之間哪些數的平方可以得到回文數281 
9.10分解質因數283 
9.10 .1質因數分 解算法283 
9.10.2質因數分解算法示例284
【程序示例9-10】對合數1155分解質因數284 
9.11小結285 

第10章算法經典趣題
10.1百錢買百雞286 
10.1.1算法解析286 
10.1.2求解示例287 
【程序示例10-1 】百錢買雞問題示例287 
10.2五家共井288 
10.2.1算法解析288 
10.2.2求解示例289 
【程序示例10-2】五家共井問題示例290 
10.3猴子吃桃291 
10.3.1算法解析291 
10.3.2求解示例292 
【程序示例10-3】猴子吃桃問題示例292 
10.4舍罕王賞麥293 
10.4.1算法解析293 
10.4.2求解示例294 
【程序示例10-4】舍罕王賞麥問題示例294 
10.5漢諾塔295 
10.5.1算法解析295 
10.5.2求解示例296 
【程序示例10-5】漢諾塔問題示例297 
10.6竊賊問題298 
10.6.1算法解析298 
10.6.2求解示例300 
【程序示例10-6】竊賊問題示例300 
10.7馬踏棋盤303 
10.7.1算法解析303
10.7.2求解示例304 
【程序示例10-7】馬踏棋盤問題示例304 
10.8八皇后問題306 
10.8.1算法解析306 
10.8.2求解示例308 
【程序示例10-8】八皇后問題示例308 
10.9青蛙過河310 
10.9.1算法解析310 
10.9.2求解示例311 
【程序示例10-9】青蛙過河問題示例311 
10.10三色旗314 
10.10.1算法解析314 
10.10.2求解示例315 
【程序示例10- 10】三色旗問題示例316 
10.11漁夫捕魚317 
10.11.1算法解析318 
10.11.2求解示例318 
【程序示例10-11】漁夫捕魚問題示例318 
10.12愛因斯坦的階梯319 
10.12.1算法解析320 
10.12.2求解示例320 
【程序示例10-12】愛因斯坦的階梯問題示例320 
10.13常勝將軍321 
10.13.1算法解析321 
10.13.2求解示例322 
【程序示例10-13】常勝將軍問題解析322 
10.14三色球324 
10.14.1算法解析324
10.14.2求解示例324 
【程序示例10-14】三色球問題示例325 
10.15小結326 

第11章遊戲中的算法
11.1撲克遊戲問題——10點半327 
11.1.1算法解析327 
11.1.2求解示例331 
【程序示例11-1】10點半撲克遊戲示例332 
11.2生命遊戲334 
11.2.1生命遊戲的原理334 
11.2.2算法解析335 
11.2.3求解示例337 
【程序示例11-2】生命遊戲示例337 
11.3小結341 

第3篇算法面試題篇

第12章智商邏輯推理類面試題
12.1腦筋急轉彎342 
12.1.1中國有多少輛汽車342 
12.1.2下水道的蓋子為什麼是圓形的343 
12.1.3分蛋糕344 
12.1.4你怎樣改造和重新設計一個ATM銀行自動取款機344 
12.2邏輯推理345 
12.2.1哪個開關控制哪盞燈345 
12.2.2戴帽子346 
12.2.3海盜分金347 
12.2.4罪犯認罪348 
12.2.5找出質量不相同的球349 
12.2.6有多少人及格349
12.2.7他說的是真話嗎350 
12.3計算推理351 
12.3.1倒水問題351 
12.3.2騙子購物352 
12.3.3求最大的連續組合值（華為校園招聘筆試題） 353 
12.3.4巧妙過橋354 
12.3.5字符移動（金山筆試題） 357 
12.4小結358 

第13章數學能力測試
13.1 100盞燈359 
13.2用一筆劃出經過9個點的4條直線360 
13.3在9個點上畫10條線361 
13.4時、分和秒針重合問題361 
13.5可以喝多少瓶汽水364 
13.6怎樣拿到第100號球365 
13.7燒繩計時366 

第14章算法常見面試題及解答
14.1排序類算法面試題367 
14.1. 1排序算法效率367 
14.1.2雞尾酒排序算法368 
【程序示例14-1】用雞尾酒排序算法對一組整數進行排序368 
14.1.3文件排序370 
14.1.4城市名稱371 
【程序示例14-2】對任意輸入的5個城市的拼音按照字母順序重新排列輸出371 
14.2查找類算法面試題372 
14.2.1遞歸求極值372 
【程序示例14-3】用遞歸法求10個整數中的最大值372
14.2.2尋找共同元素373 
【程序示例14-4】查找並輸出兩個整型數組中同時出現的元素374 
14.2.3查找最大子串375 
【程序示例14-5】在一個由0和1組成的字符串中，查找0和1連續出現的最大次數375 
14.3綜合類算法面試題377 
14.3.1求序列和377 
【程序示例14-6】求給出數據序列的前100項之和377 
14.3. 2遞歸求累加和378 
【程序示例14-7】用遞歸算法求1+2+3+4+…+100之和378 
14.3.3猜蘋果數379 
【程序示例14-8】用遞歸算法計算給定題目中5個人各自擁有的蘋果數379 
14.3.4逆置字符串380 
【程序示例14-9】將一個輸入的字符串在不額外開闢空間的情況下進行逆置380 
14.3.5位運算求負數381 
【程序示例14-10】計算正整數20對應的負數（只可使用位運算實現） 381 
14.4小結382 

第15章數據結構常見面試題及解答
15.1基本數據結構面試題383 
15.1.1如何實現數據緩存區383 
15.1.2出棧隊列384 
15.1.3入棧隊列 384 
15.1.4二叉樹葉結點個數385 
15.1.5有向圖和無向圖386 
15.2數據結構應用面試題386
15.2.1設計包含min函數的棧386 
【程序示例15-1】在函數min、push及pop時間複雜度都是O(1)的情況下，
設計包含min函數的棧387 
15.2.2設計計算指定結點層數算法390 
【程序示例15-2】在給定的二叉樹中，計算字符C的層數390 
15.2.3鍊錶法篩選成績391 
【程序示例15-3】某班級8位學生的成績已給出，使用鍊錶結構及指針操作來輸出及格
的成績分數391 
15.2.4將二叉樹轉變成排序的雙向鍊錶393 
【程序示例15-4】將給出的二叉樹轉換成一個排序的雙向鍊錶（不能創建新的結點，
只調整數指針的方向） 393 
15.2.5單鍊錶逆轉394 
【程序示例15-5】編寫算法將一個單鍊錶實現逆轉395 
15.3小結396 

注：以下內容讀者可從本書的二維碼整體下載包中獲取
第4篇算法高級應用篇

第16章密碼學算法
16.1密碼學概述398 
16.1.1密碼學的發展398 
16.1.2密碼學的基本概念399 
16.1.3柯克霍夫斯原則400 
16.1.4經典 密碼學算法400 
16.2換位加密解密401 
16.2.1換位加密解密算法401 
16.2.2換位加密解密算法示例404
16.3替換加密解密407 
16.3.1替換加密解密算法407 
16.3.2替換加密解密算法示例408 
16.4位加密解密410 
16.4.1位加密解密算法410 
16.4.2位加密解密算法示例412 
16.5一次一密加密解密413 
16.5.1一次一密加密解密算法414 
16.5.2一次一密加密解密算法示例415 
16.6小結417 

第17章壓縮與解壓縮算法
17.1壓縮與解壓縮概述418 
17.1.1壓縮與解壓縮分類418 
17.1 .2典型的壓縮解壓縮算法419 
17.2壓縮算法419 
17.3解壓縮算法422 
17.4壓縮/解壓縮示例425 
17.5小結428