程序基本算法教程

第1章程式與演算法/1
1.1電腦基礎知識/1
1.1.1硬體/1
1.1.2軟體/2
1.2程式設計/3
1.2.1程式設計內容/3
1.2.2程式設計過程/3
1.3演算法/3
1.3.1五個屬性/5
1.3.2三個層次/5
1.4演算法複雜性/6
1.4.1空間複雜度/6
1.4.2時間複雜度/7
1.4.3演算法評價標準/7
1.4.4演算法效率/8
1.5演算法表示方式/10
1.5.1程式流程圖/10
1.5.2 NS圖/10
1.5.3偽語言/11
1.6習題/11

第2章程式設計語言/13
2.1程式設計語言演變歷史/13
2.1.1機器語言/13
2.1.2組合語言/13
2.1.3面向過程設計語言/13
2.1.4物件導向程式設計語言/14
2.1.5智慧化語言/14
2.2結構化程式設計/14
2.2.1自頂向下/14
2.2.2逐步細化/14
2.2.3模組化設計/15
2.2.4結構化編碼/15
2.3三種基本結構/15
2.3.1順序結構/16
2.3.2選擇結構/16
2.3.3迴圈結構/17
2.4高級程式設計語言的基本結構/18
2.4.1面向過程程式設計語言/18
2.4.2物件導向程式設計語言/19
2.5代碼書寫規則/20
2.5.1縮進/20
2.5.2邏輯行與物理行/20
2.5.3注釋/21
2.5.4編碼習慣/21
2.6程式調試/22
2.6.1調試策略/23
2.6.2三種調試工具/23
2.7選擇語言的標準/25
2.7.1專案應用領域/25
2.7.2演算法複雜度/25
2.7.3資料結構複雜性/25
2.7.4開發人員水準/26
2.8習題/26

第3章資料結構/27
3.1概述/27
3.2線性表/27
3.2.1相關概念/27
3.2.2線性表存儲/28
3.3棧/32
3.3.1相關概念/32
3.3.2棧的存儲/32
3.4佇列/34
3.4.1概念/34
3.4.2佇列存儲/34
3.5樹/39
3.5.1相關概念/39
3.5.2二叉樹的性質/40
3.5.3二叉樹存儲/41
3.5.4二叉樹遍歷/42
3.5.5二叉樹創建/46
3.6圖/46
3.6.1相關概念/46
3.6.2圖的存儲/47
3.6.3圖的遍歷/52
3.6.42小生成樹/55
3.6.52短路徑/57
3.7習題/61

第4章查找與排序/63
4.1查找/63
4.1.1順序查找/63
4.1.2折半查找/63
4.1.3分塊查找/65
4.2排序/66
4.2.1插入類/67
4.2.2交換類/70
4.2.3選擇類/72
4.2.4歸併類/78
4.3排序法總結/79
4.3.1時間性能/79
4.3.2空間性能/79
4.3.3穩定性能/79
4.4習題/80

第5章窮舉法/82
5.1概述/82
5.2例題/82
5.2.1楊輝三角形/82
5.2.2螺旋數陣/84
5.2.3百錢買百雞/84
5.2.4啤酒和飲料/86
5.3有意思的數/87
5.3.1素數/87
5.3.2孿生素數/88
5.3.3回文素數/89
5.3.4水仙花數/90
5.3.5北斗七星數/91
5.3.6完全數/92
5.3.7倒序數/93
5.4習題/93

第6章遞迴法/94
6.1概述/94
6.1.1簡介/94
6.1.2記憶體組織方式/95
6.1.3遞迴適用場合/95
6.2基本遞迴/96
6.2.1相關概念/96
6.2.2基本遞迴運行原理/97
6.3尾遞迴/98
6.3.1相關概念/98
6.3.2尾遞迴運行原理/98
6.4相似術語解析/99
6.4.1遞迴與迴圈/99
6.4.2反覆運算和遞推/99
6.4.3反覆運算與遍歷/100
6.4.4遞迴和遞推/100
6.5例題/103
6.5.12大公約數/103
6.5.22近公共子結點/105
6.5.3漢諾塔問題/106
6.5.4平面劃分/107
6.5.5切面條/109
6.5.6全排列問題/110
6.5.7整數劃分問題/112
6.6習題/113

第7章分治法/114
7.1概述/114
7.2從求陣列2值談起/114
7.3演算法框架/120
7.4查找與排序中的分治法/122
7.4.1二分查找演算法/122
7.4.2快速排序演算法/123
7.5乘法中的分治法/126
7.5.1大整數乘法/126
7.5.2Strassen矩陣乘法/128
7.6棋盤覆蓋問題/132
7.7習題/135

第8章動態規劃法/136
8.1概述/136
8.2矩陣連乘積問題/136
8.3字串相似度問題/144
8.3.12長公共子序列問題/144
8.3.2編輯距離問題/149
8.4數字三角形問題/151
8.501背包問題/152
8.6習題/154

第9章貪心法/156
9.1概述/156
9.2活動安排問題/157
9.3貪心演算法和動態規劃演算法關係/159
9.42優裝載問題/161
9.52優分解問題/163
9.6單源2短路徑問題/164
9.7習題/168

第10章回溯法/170
10.1概述/170
10.2從背包問題看回溯法的演算法框架/170
10.3裝載問題/175
10.4批次處理作業調度問題/177
10.5皇后問題/179
10.6小重量機器設計問題/181
10.7工作分配問題/182
10.8習題/183附錄各類軟體競賽/184

A.1電腦認證考試/184
A.2全國電腦等級考試/184
A.3電腦技術與軟體專業技術資格(水準)考試/185
A.4ACM國際大學生程式設計競賽/185
A.5藍橋杯/185
A.6全國Java程式設計大賽/186參考文獻/187

程式與演算法作為程式設計語言學核心內容,本書的作者多年從事程式設計語言(如VB、C、C++、Python等)和演算法教學,發現學生在語法的學習上花費太多的精力,往往還不能領會到編寫程式的真諦所在。因此,本書不討論程式設計語言的語法細節,注重基本演算法、基本理論、基本技能的教學,在內容的選取上力圖精簡,主要培養學生掌握程式設計的基本方法及提高其應用開發能力的思想。
　　
本書共分10章,主要內容包括程式與演算法、程式設計語言、資料結構、查找與排序、窮舉法、遞迴法、分治法、動態規劃法、貪心法、回溯法以及附錄。
　　
本書由周元哲、劉偉、鄧萬宇編寫,其中,劉偉編寫分治法、動態規劃法、貪心法、回溯法章節,鄧萬宇編寫資料結構、查找與排序章節,其餘章節由周元哲編寫,全書由周元哲負責本書大綱擬訂與統稿工作。
　　
學習電腦程式設計的最好方法是實踐。本書採用Python、VB.NET和C等高級程式設計語言進行講解,所有程式都在VisualC6.0下調試運行通過。建議讀者上機編寫、運行和調試本書所給的常式。
　　
西安郵電大學電腦學院的王玉清、孟偉君老師對本書的編寫給予了大力的支持並提出了指導性意見,陳琳、郝羽等提出了很多寶貴的意見。清華大學出版社的張民老師對本教材的寫作大綱、寫作風格等提出了很多寶貴的意見。衷心感謝上述各位的支持和幫助。本書在寫作過程中參閱了大量中外文的專著、教材、論文、報告及網上的資料,由於篇幅所限,未能一一列出。在此,向各位作者表示敬意和衷心的感謝。
　　
本書可作為高等院校各專業學生學習程式設計和軟體競賽的教材或教學參考書,也可作為程式師和社會讀者的自學輔助用書。由於作者水準有限,時間緊迫,本書難免有不足之處,我們誠懇期待讀者的批評與指正,以使本書日臻完善。
　　
作者
2016年2月