本書是一個(gè)新的計(jì)算機(jī)教育時(shí)代的產(chǎn)物，計(jì)算思維就是這個(gè)時(shí)代的名稱。一般認(rèn)為科學(xué)思維主要分為理論思維、實(shí)驗(yàn)思維和計(jì)算思維三大類，所以理論、實(shí)驗(yàn)和計(jì)算成為推動(dòng)人類文明進(jìn)步和科技發(fā)展的三大支柱。而計(jì)算思維的主要內(nèi)容則包括了問題求解、系統(tǒng)設(shè)計(jì)和人類行為理解。
在高等院校的計(jì)算機(jī)教育領(lǐng)域，一直存在兩種截然不同的教材： 一種是面向計(jì)算機(jī)和信息專業(yè)領(lǐng)域的，眾多成熟和系統(tǒng)性很強(qiáng)的教材并形成學(xué)科教育的基礎(chǔ)；另一種則是面向所有專業(yè)的計(jì)算機(jī)基礎(chǔ)教材，由于其中的內(nèi)容大部分是面向計(jì)算機(jī)基本應(yīng)用的，所以技術(shù)選擇對平臺工具具有一定的依賴性，而且隨著技術(shù)的變換而不斷變化。
由于計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，技術(shù)和平臺工具選擇的相互依賴會(huì)導(dǎo)致大部分專業(yè)工作者在學(xué)校所接觸到的信息技術(shù)和產(chǎn)品不久就成為"明日黃花"并為更新的技術(shù)和產(chǎn)品所替代，甚至一種計(jì)算工具尚未掌握，新一代的工具又產(chǎn)生了。這種狀況往往令人目不暇接，以至于無所適從。另一方面，計(jì)算機(jī)科學(xué)的基礎(chǔ)內(nèi)容，那些在計(jì)算機(jī)科學(xué)課程系列中被認(rèn)為極為重要的核心理念和基本方法，雖然變化緩慢，但由于其枯燥艱深，難以為廣大的其他專業(yè)工作者所了解和掌握。
在這個(gè)新的計(jì)算機(jī)教育時(shí)代，大學(xué)計(jì)算機(jī)課程的重要任務(wù)之一是讓學(xué)習(xí)者體驗(yàn)到計(jì)算原理的相互影響以及問題有效解決的思維方式，并從中獲得計(jì)算的愉悅。
本書的目的就是朝著這個(gè)方向努力。希望在有限的時(shí)間里，將計(jì)算機(jī)科學(xué)的核心理念傳播給非計(jì)算機(jī)專業(yè)的讀者，并且，希望這些理念是可以觀察、驗(yàn)證和投入實(shí)際應(yīng)用的--即使這種應(yīng)用水平還屬于初級階段，可能存在很多需要改進(jìn)的地方。
進(jìn)入21世紀(jì)，社會(huì)信息化不斷向縱深發(fā)展，各行各業(yè)的信息化進(jìn)程不斷加速。我國的高等教育也進(jìn)入了一個(gè)新的歷史發(fā)展時(shí)期，尤其是高校的計(jì)算機(jī)基礎(chǔ)教育，正在步入更加科學(xué)，更加合理，更加符合21世紀(jì)高校人才培養(yǎng)目標(biāo)的新階段。
為了進(jìn)一步推動(dòng)高校計(jì)算機(jī)基礎(chǔ)教育的發(fā)展，教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)近期了《關(guān)于進(jìn)一步加強(qiáng)高等學(xué)校計(jì)算機(jī)基礎(chǔ)教學(xué)的意見暨計(jì)算機(jī)基礎(chǔ)課程教學(xué)基本要求》(以下簡稱《教學(xué)基本要求》) . 《教學(xué)基本要求》針對計(jì)算機(jī)基礎(chǔ)教學(xué)的現(xiàn)狀與發(fā)展，提出了計(jì)算機(jī)基礎(chǔ)教學(xué)改革的指導(dǎo)思想；按照分類、分層次組織教學(xué)的思路，《教學(xué)基本要求》提出了計(jì)算機(jī)基礎(chǔ)課程教學(xué)內(nèi)容的知識結(jié)構(gòu)與課程設(shè)置。《教學(xué)基本要求》認(rèn)為，計(jì)算機(jī)基礎(chǔ)教學(xué)的典型核心課程包括大學(xué)計(jì)算機(jī)基礎(chǔ)、計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)、計(jì)算機(jī)硬件技術(shù)基礎(chǔ)(微機(jī)原理與接口、單片機(jī)原理與應(yīng)用)、數(shù)據(jù)庫技術(shù)及應(yīng)用、多媒體技術(shù)及應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)及應(yīng)用。《教學(xué)基本要求》中介紹了上述六門核心課程的主要內(nèi)容，這為今后的課程建設(shè)及教材編寫提供了重要的依據(jù)。在下一步計(jì)算機(jī)課程規(guī)劃工作中，建議各校采用"1+X"的方案，即"大學(xué)計(jì)算機(jī)基礎(chǔ)"+ 若干必修或選修課程。
教材是實(shí)現(xiàn)教學(xué)要求的重要保障。為了更好地促進(jìn)高校計(jì)算機(jī)基礎(chǔ)教育的改革，我們組織了國內(nèi)部分高校教師進(jìn)行了深入的討論和研究，根據(jù)《教學(xué)基本要求》中的相關(guān)課程教學(xué)基本要求組織編寫了這套"大學(xué)計(jì)算機(jī)基礎(chǔ)教育規(guī)劃教材".
本套教材的特點(diǎn)如下：
(1) 體系完整，內(nèi)容先進(jìn)，符合大學(xué)非計(jì)算機(jī)專業(yè)學(xué)生的特點(diǎn)，注重應(yīng)用，強(qiáng)調(diào)實(shí)踐。
(2) 教材的作者來自全國各個(gè)高校，都是教育部高等學(xué)校計(jì)算機(jī)基礎(chǔ)課程教學(xué)指導(dǎo)委員會(huì)推薦的專家、教授和教學(xué)骨干。
(3) 注重立體化教材的建設(shè)， 除主教材外，還配有多媒體電子教案、習(xí)題與實(shí)驗(yàn)指導(dǎo)，以及教學(xué)網(wǎng)站和教學(xué)資源庫等。
(4) 注重案例教材和實(shí)驗(yàn)教材的建設(shè)，適應(yīng)教師指導(dǎo)下的學(xué)生自主學(xué)習(xí)的教學(xué)模式。
(5) 及時(shí)更新版本，力圖反映計(jì)算機(jī)技術(shù)的新發(fā)展。
本套教材將隨著高校計(jì)算機(jī)基礎(chǔ)教育的發(fā)展不斷調(diào)整，希望各位專家、教師和讀者不吝提出寶貴的意見和建議，我們將根據(jù)大家的意見不斷改進(jìn)本套教材的組織、編寫工作，為我國的計(jì)算機(jī)基礎(chǔ)教育的教材建設(shè)和人才培養(yǎng)做出更大的貢獻(xiàn)。
"大學(xué)計(jì)算機(jī)基礎(chǔ)教育規(guī)劃教材"叢書主編
教育部高等學(xué)校計(jì)算機(jī)基礎(chǔ)課程教學(xué)指導(dǎo)委員會(huì)副主任委員
程向前
生于1954年11月，男，管理信息理學(xué)碩士，高級工程師，西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心副主任。
教授課程：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)與應(yīng)用；管理信息系統(tǒng)；負(fù)責(zé)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心的實(shí)驗(yàn)環(huán)境建設(shè)和日常運(yùn)行；負(fù)責(zé)計(jì)算機(jī)網(wǎng)絡(luò)，管理信息系統(tǒng)課程雙語教學(xué)改革項(xiàng)目；"計(jì)算機(jī)網(wǎng)絡(luò)"精品課程的主要完成人之一。
合作出版教材及教輔資料10本，獨(dú)立出版教材2本。其中，《計(jì)算機(jī)網(wǎng)絡(luò)》2002年2月獲教材一等獎(jiǎng)(排名第四)，《硬件技術(shù)基礎(chǔ)》2002年2月獲教材二等獎(jiǎng)(排名第三)。
第1章 RAPTOR程序設(shè)計(jì)基礎(chǔ)1
1.1 程序與算法的基本概念1
1.1.1 為什么要學(xué)習(xí)程序設(shè)計(jì)1
1.1.2 程序設(shè)計(jì)的發(fā)展階段2
1.1.3 為什么要使用RAPTOR可視化程序設(shè)計(jì)環(huán)境6
1.1.4 程序設(shè)計(jì)語言的基本概念8
1.1.5 RAPTOR的特點(diǎn)10
1.2 RAPTOR基本程序環(huán)境10
1.2.1 基本符號10
1.2.2 變量11
1.2.3 常量15
1.2.4 輸入語句15
1.2.5 數(shù)據(jù)處理語句16
1.2.6 過程調(diào)用語句19
1.2.7 輸出語句20
1.2.8 注釋21
1.3 RAPTOR控制結(jié)構(gòu)23
1.3.1 順序控制23
1.3.2 選擇控制23
1.3.3 決策表達(dá)式24
1.3.4 循環(huán)控制27
1.4 RAPTOR數(shù)組變量31
1.4.1 一維數(shù)組的創(chuàng)建32
1.4.2 二維數(shù)組的創(chuàng)建33
1.4.3 數(shù)組的運(yùn)算34
1.4.4 如何使用數(shù)組變量34
1.4.5 平行數(shù)組35
1.4.6 數(shù)組應(yīng)用中的注意事項(xiàng)35
1.5 RAPTOR子程序和子圖的定義及調(diào)用35
1.6 計(jì)算問題求解的一般過程401.6.1 理解問題40
1.6.2 制定計(jì)劃41
1.6.3 執(zhí)行計(jì)劃42
1.6.4 回顧與總結(jié)42
1.6.5 使用計(jì)算機(jī)進(jìn)行問題求解: 程序開發(fā)周期43
1.7 小結(jié)與回顧44
習(xí)題44
第2章 算法設(shè)計(jì)與可視化46
2.1 算法初步46
2.1.1 算法的由來與定義46
2.1.2 算法的特性49
2.1.3 算法設(shè)計(jì)的要求49
2.2 算法效率的度量51
2.2.1 算法效率的基本估算方法51
2.2.2 實(shí)驗(yàn)驗(yàn)證方法53
2.3 算法復(fù)雜度53
2.3.1 函數(shù)的漸近增長54
2.3.2 算法時(shí)間復(fù)雜度定義54
2.3.3 推算大?O?階方法55
2.4 計(jì)算的可視化問題57
2.4.1 算法設(shè)計(jì)的可視化57
2.4.2 計(jì)算過程的可視化58
2.4.3 計(jì)算問題和結(jié)果的可視化60
2.4.4 RAPTOR與流程圖規(guī)范之間的關(guān)系與差別61
2.5 RAPTOR算法設(shè)計(jì)常用子程序63
2.5.1 隨機(jī)數(shù)的產(chǎn)生與存儲63
2.5.2 將計(jì)算結(jié)果存儲到文件64
2.5.3 從文件中讀入基礎(chǔ)數(shù)據(jù)65
2.5.4 RAPTOR圖形輸出67
2.5.5 RAPTOR圖形窗口中的用戶交互74
2.5.6 圖形輸出案例: 隨機(jī)漫步的模擬模型75
2.6 小結(jié)與回顧81
習(xí)題81
第3章 基本算法和策略83
3.1 基本算法83
3.1.1 蠻力法83
3.1.2 分段函數(shù)84
3.1.3 遞推法86
3.1.4 模運(yùn)算89
3.1.5 字符和字符串運(yùn)算89
3.1.6 遞歸93
3.1.7 數(shù)論問題98
3.1.8 組合計(jì)算102
3.1.9 迭代法105
3.2 基本策略108
3.2.1 貪心策略108
3.2.2 分治策略110
3.2.3 回溯策略111
3.2.4 動(dòng)態(tài)規(guī)劃114
3.2.5 將遞歸算法轉(zhuǎn)化為非遞歸的實(shí)現(xiàn)117
3.2.6 基本算法策略的討論119
3.3 小結(jié)與回顧121
習(xí)題121
第4章 模型化124
4.1 從有限狀態(tài)機(jī)到圖靈機(jī)124
4.1.1 什么是模型125
4.1.2 如何建立模型126
4.1.3 什么是有限狀態(tài)機(jī)126
4.1.4 如何設(shè)計(jì)和應(yīng)用有限狀態(tài)機(jī)129
4.1.5 可視化有限狀態(tài)機(jī)的實(shí)現(xiàn)案例: 電子寵物游戲130
4.1.6 什么是圖靈機(jī)136
4.1.7 如何使用RAPTOR模擬圖靈機(jī)139
4.1.8 有限狀態(tài)機(jī)與圖靈機(jī)的比較148
4.2 使用RAPTOR實(shí)現(xiàn)抽象數(shù)據(jù)類型149
4.2.1 對現(xiàn)實(shí)世界中的問題進(jìn)行數(shù)據(jù)抽象149
4.2.2 使用RAPTOR實(shí)現(xiàn)線性表151
4.2.3 使用RAPTOR實(shí)現(xiàn)樹155
4.3 小結(jié)與回顧164
習(xí)題164
第5章 排序與查找166
5.1 排序166
5.1.1 計(jì)算機(jī)如何進(jìn)行排序167
5.1.2 直接插入排序169
5.1.3 桶排序172
5.1.4 冒泡排序172
5.1.5 快速排序176
5.1.6 歸并排序178
5.1.7 排序算法的分析178
5.2 查找180
5.2.1 順序查找180
5.2.2 二分查找181
5.2.3 分塊查找182
5.2.4 哈希查找188
5.2.5 查找算法的分析198
5.3 小結(jié)與回顧199
習(xí)題199
第6章 信息論、哈夫曼編碼與二叉樹201
6.1 問題的引入201
6.1.1 信息表達(dá)203
6.1.2 數(shù)字表達(dá)204
6.1.3 字符表達(dá)205
6.2 信息論基礎(chǔ)207
6.2.1 什么是信息207
6.2.2 信息的量化208
6.3 哈夫曼編碼212
6.3.1 哈夫曼編碼原理213
6.3.2 使用RAPTOR實(shí)現(xiàn)哈夫曼編碼的算法215
6.4 二叉樹220
6.4.1 二叉樹的遍歷224
6.4.2 堆排序227
6.4.3 二叉搜索樹228
6.4.4 平衡二叉樹236
6.5 小結(jié)和回顧240
習(xí)題241
第7章 圖論基礎(chǔ)與應(yīng)用243
7.1 圖的定義和常用術(shù)語244
7.2 圖的存儲246
7.2.1 鄰接矩陣存儲原理246
7.2.2 使用RAPTOR建立已知圖的鄰接矩陣248
7.2.3 鄰接表存儲原理249
7.2.4 使用RAPTOR建立已知圖的鄰接表252
7.3 圖的遍歷253
7.3.1 深度優(yōu)先搜索254
7.3.2 廣度優(yōu)先搜索255
7.3.3 求圖的連通分量 256
7.4 圖算法的應(yīng)用258
7.4.1 最小網(wǎng)絡(luò)建設(shè)成本258
7.4.2 最短的旅行路線260
7.4.3 地圖著色問題266
7.4.4 商業(yè)網(wǎng)點(diǎn)的最省布點(diǎn)方案269
7.5 在RAPTOR中實(shí)現(xiàn)圖算法的可視化271
7.5.1 圖類算法的問題可視化271
7.5.2 真實(shí)的地圖與抽象圖的疊加274
7.5.3 棋類游戲的實(shí)現(xiàn)276
7.6 小結(jié)與回顧279
習(xí)題279
第8章 計(jì)算工具的評估和選擇281
8.1 計(jì)算工具的精度評估281
8.1.1 誤差的來源282
8.1.2 誤差、相對誤差和有效數(shù)字283
8.1.3 計(jì)算工具的精度設(shè)計(jì)與誤差284
8.1.4 誤差分析與實(shí)踐289
8.2 從RAPTOR到C++的算法環(huán)境轉(zhuǎn)換290
8.2.1 遞歸程序290
8.2.2 文件輸入輸出292
8.2.3 圖形問題294
8.2.4 RAPTOR的轉(zhuǎn)換和編譯問題297
8.2.5 RAPTOR與C/C++的比較與選擇300
8.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)與RAPTOR303
8.3.1 OOP的基本概念304
8.3.2 封裝304
8.3.3 繼承305
8.3.4 多態(tài)性305
8.3.5 典型的面向?qū)ο蟮某绦蛘Z言306
8.3.6 RAPTOR對OOP的支持306
8.4 逆向工程: 從代碼到流程圖312
8.4.1 CVF介紹312
8.4.2 CVF流程圖與RAPTOR的比較315
8.4.3 AutoFlowchart介紹315
8.5 電子表格軟件與數(shù)值計(jì)算316
8.6 小結(jié)與回顧320
習(xí)題320
附錄A RAPTOR圖形操作指南322
A.1 RAPTOR圖形坐標(biāo)322
A.2 色彩322
A.2.1 設(shè)置顏色323
A.2.2 生成隨機(jī)色彩323
A.3 繪圖操作323
A.3.1 清理窗口324
A.3.2 畫弧324
A.3.3 畫圓325
A.3.4 畫橢圓325
A.3.5 繪制可以旋轉(zhuǎn)角度的橢圓326
A.3.6 繪制位圖326
A.3.7 裝載位圖327
A.3.8 畫線327
A.3.9 填色327
A.3.10 取得像素的色彩328
A.3.11 設(shè)置像素的色彩328
A.4 鍵盤操作328
A.4.1 取鍵值329
A.4.2 取鍵字符串329
A.4.3 判斷某個(gè)鍵是否處于按下狀態(tài)330
A.4.4 判斷某個(gè)擊鍵動(dòng)作是否已經(jīng)發(fā)生過330
A.4.5 等待鍵入331
A.5 鼠標(biāo)操作331
A.5.1 取得鼠標(biāo)按鍵與指針位置331
A.5.2 取得鼠標(biāo)指針的X值331
A.5.3 取得鼠標(biāo)指針的Y值332
A.5.4 判斷鼠標(biāo)鍵是否處于按下狀態(tài)332
A.5.5 判斷鼠標(biāo)鍵是否被按下過332
A.5.6 判斷鼠標(biāo)鍵是否已經(jīng)釋放333
A.5.7 等待某個(gè)鼠標(biāo)按鍵動(dòng)作333
A.6 文本操作333
A.6.1 顯示數(shù)字334
A.6.2 顯示文本334
A.6.3 取得字模的高度334
A.6.4 取得字模的寬度335
A.6.5 設(shè)置字號335
A.7 窗口操作335
A.7.1 關(guān)閉窗口335
A.7.2 取得窗口的較大高度336
A.7.3 取得窗口的較大寬度336
A.7.4 判斷圖形窗口是否打開336
A.7.5 打開圖形窗口337
A.7.6 設(shè)置窗口的標(biāo)題欄337
A.7.7 平滑動(dòng)畫顯示效果337
術(shù)語對照表339參考文獻(xiàn)348參考網(wǎng)站349
參考文獻(xiàn)197
希望該書成為計(jì)算思維領(lǐng)域最實(shí)用的學(xué)習(xí)工具，為我國計(jì)算機(jī)相關(guān)專業(yè)的發(fā)展作出應(yīng)有的貢獻(xiàn)。
——廣東工業(yè)大學(xué) 程良倫 教授
該書將程序設(shè)計(jì)語言、算法、數(shù)據(jù)結(jié)構(gòu)、圖論等傳統(tǒng)課程中基礎(chǔ)性、應(yīng)用性較強(qiáng)的知識融合在一起，可使得教學(xué)工作事半功倍。
——肇慶學(xué)院 胡忠望 教授
該書內(nèi)容很，涉及計(jì)算學(xué)科所需相關(guān)知識和相應(yīng)的工具。
——福州大學(xué) 陳國龍 教授
作者的工作非常有意義。這種可以理解和操作的"計(jì)算思維能力培養(yǎng)"具有很大的示范效應(yīng)，可以推廣到所有的學(xué)校和專業(yè)。
——桂林電子科技大學(xué) 董榮勝 教授
該書非常適合廣大非計(jì)算機(jī)專業(yè)的學(xué)生使用，即使對于低年級的專業(yè)學(xué)生，也是很好的教材。
——華東理工大學(xué) 陳志華 副教授
We invented RAPTOR because our students here in the United States also are primarily visual learners. We found that RAPTOR allowed them to be more successful in designing and implementing small algorithms than using a traditional programming language.
——Dr.Martin C. Carlisle
