DJ8--算法與程序設(shè)計(jì)-v1

1、第 2 頁第一章 基于計(jì)算機(jī)的問題求解 第二章 計(jì)算機(jī)信息數(shù)字化基礎(chǔ) 第三章 計(jì)算機(jī)的工作原理與硬件體系結(jié)構(gòu)第四章 計(jì)算機(jī)軟件平臺第五章 計(jì)算機(jī)網(wǎng)絡(luò)平臺第六章 數(shù)據(jù)處理與數(shù)據(jù)庫第七章 計(jì)算與計(jì)算學(xué)科第八章 算法與程序設(shè)計(jì)第九章 實(shí)用軟件 第十章 計(jì)算機(jī)科學(xué)前沿技術(shù)第 3 頁第八章 算法與程序設(shè)計(jì) 奧巴馬關(guān)于奧巴馬關(guān)于“100100萬個(gè)萬個(gè)3232位整數(shù)排序位整數(shù)排序”問題的回答。問題的回答。20082008年奧巴馬當(dāng)選美國總統(tǒng)后訪問谷歌總部，谷歌董事年奧巴馬當(dāng)選美國總統(tǒng)后訪問谷歌總部，谷歌董事長埃里克長埃里克. .施密特問了他一個(gè)問題：施密特問了他一個(gè)問題：“獲得總統(tǒng)這份工獲得總統(tǒng)這份工作很難

2、，獲得谷歌的工作也很難。為檢驗(yàn)奧巴馬的資作很難，獲得谷歌的工作也很難。為檢驗(yàn)奧巴馬的資格，如果為格，如果為100100萬個(gè)萬個(gè)3232位整數(shù)排序，最有效的辦法是什位整數(shù)排序，最有效的辦法是什么？么？”奧巴馬答：奧巴馬答：“總之，冒泡排序是錯(cuò)的總之，冒泡排序是錯(cuò)的?！钡?4 頁 8.1 算法 8.2 典型問題的算法設(shè)計(jì) 8.3 數(shù)據(jù)結(jié)構(gòu) 8.4 程序設(shè)計(jì)第8章 算法與程序設(shè)計(jì)第八章 算法與程序設(shè)計(jì) 第 5 頁 8.1 算法8.1.1 算法的定義“一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個(gè)解決某一特定類型的問題的運(yùn)算序列。”當(dāng)代著名計(jì)算機(jī)科學(xué)家D.E.KnuthTHE ART OF C

3、OMPUTER PROGRAMMING 求解問題的分步驟方法 輸入數(shù)據(jù)輸出結(jié)果算法非正式定義示意圖 簡單地說，算法就是解決問題的有限步驟。第 6 頁8.1.1 算法的定義例8-1以黑藍(lán)兩色墨水交換為例問題描述：有黑和藍(lán)兩個(gè)墨水瓶，因錯(cuò)把黑墨水裝在了藍(lán)瓶子里，而藍(lán)墨水錯(cuò)裝在了黑瓶子里，要求將其互換。算法分析：因?yàn)閮蓚€(gè)瓶子的墨水不能直接交換，所以引入第三個(gè)墨水瓶。如果第三個(gè)墨水瓶為白色，其交換步驟如下 8.1 算法第 7 頁8.1.1 算法的定義算法分兩大類：數(shù)值運(yùn)算算法非數(shù)值運(yùn)算算法 數(shù)值運(yùn)算是指對問題求數(shù)值解如：多項(xiàng)式插值、微分方程求解、函數(shù)的定積分求解、上述的隊(duì)列算法等，都屬于數(shù)值運(yùn)算范圍。

4、 非數(shù)值運(yùn)算包括非常廣泛的領(lǐng)域如：資料檢索、事務(wù)管理、數(shù)據(jù)處理等，上述的“黑藍(lán)兩色墨水交換”也是非數(shù)值運(yùn)算算法。 8.1 算法第 8 頁8.1.2 算法的基本特征算法具有以下基本特征： 有窮性：一個(gè)算法必須在執(zhí)行有限個(gè)操作步驟后終止 確定性：算法中每一步的含義必須是確切的，不可出現(xiàn)任何二義性 有效性：算法中的每一步操作都應(yīng)該能有效執(zhí)行，一個(gè)不可執(zhí)行的操作是無效的 有零個(gè)或多個(gè)輸入：這里的輸入是指在算法開始之前所需要的初始數(shù)據(jù)，輸入的多少取決于特定的問題 有一個(gè)或多個(gè)輸出：所謂輸出是指與輸入有某種特定關(guān)系的量，在一個(gè)完整的算法中至少會有一個(gè)輸出。 8.1 算法第 9 頁8.1.3 算法的表示方法

5、1.偽代碼表示方法例8-2求解 sum=1+2+3+4+5+（n-1）+n算法用偽代碼表示算法開始； 輸入 n 的值； i 1； sum 0； 循環(huán)開始i=n sum sum + i； i i + 1； 循環(huán)結(jié)束 輸出 sum 的值； 算法結(jié)束； 8.1 算法第 10 頁起止框判斷框處理框輸入/輸出框注釋框流向線連接點(diǎn)8.1.3 算法的表示方法2.流程圖表示方法 8.1 算法第 11 頁標(biāo)準(zhǔn)流程圖符號含義符號名稱符 號功 能起止框表示算法的開始和結(jié)束輸入/輸出框表示算法的輸入/輸出操作，框內(nèi)填寫需輸入或輸出的各項(xiàng)處理框表示算法中的各種處理操作，框內(nèi)填寫處理說明或算式判斷框表示算法中的條件判斷操

6、作，框內(nèi)填寫判斷條件注釋框表示算法中某操作的說明信息，框內(nèi)填寫文字說明流程線 和表示算法的執(zhí)行方向連接點(diǎn)8.1.3 算法的表示方法 8.1 算法第 12 頁 T里保存： 1+2+3+K的連加和。重復(fù)進(jìn)行某種運(yùn)算，運(yùn)算對象有規(guī)律地變化, 采用循環(huán)結(jié)構(gòu)。 例: 給定K值，求1到 K連加和。循環(huán)開始輸出 T 的值結(jié)束輸入KT+I TI+1 IIKYN1I，0 TT=1+2+3+K。 1 I 0 T T+I T(I=1,2,3,K) 8.1 算法第 13 頁8.1.4 算法設(shè)計(jì)與優(yōu)化算法執(zhí)行效率包括時(shí)間效率和空間效率兩方面，稱為時(shí)間復(fù)雜性（Time Complexity）和空間復(fù)雜性（Space Co

7、mplexity) 對于具體問題，通常有很多不同的解決方法，即不同的算法。不同算法可能就有不同效率，有時(shí)候你選擇了正確的算法，但卻不一定是有效的算法。算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度，有時(shí)降低時(shí)間復(fù)雜度（或空間復(fù)雜度）是以犧牲空間復(fù)雜度（或時(shí)間復(fù)雜度）為代價(jià)的對于不同的問題，應(yīng)具體問題具體分析，找出問題的最佳算法。 8.1 算法第 14 頁練習(xí)與思考8-1 冒泡排序法為什么很慢？ 假如要給十個(gè)數(shù)排序，請畫出表達(dá)冒泡排序法的流程圖，并思考這個(gè)算法為什么慢？可以通過什么途徑解決？ 8.1 算法第 15 頁 8.1 算法 8.2 典型問題的算法設(shè)計(jì) 8.3 數(shù)據(jù)結(jié)構(gòu) 8.4 程序設(shè)計(jì)第8章 算

8、法與程序設(shè)計(jì)第八章 算法與程序設(shè)計(jì) 第 16 頁對4個(gè)數(shù)0,2,3,9按從大到小的順序排序:冒泡法0,2,3,9 0 22,0,3,9 0 32,3,0,9 0 92,3,9,0 2 33,2,9,0 2 93,9,2,0 3 9第一輪（n-1=3）次比較，（n-1=3）次交換第二輪（n-2=2）次比較，（n-2=2）次交換9,3,2,0 第三輪（n-3=1）次比較，（n-3=1）次交換引入引入 8.2 典型問題的算法設(shè)計(jì)第 17 頁8.2.1 成績排名問題排序算法問題描述：在一個(gè)班級有30名同學(xué)，一次考試每個(gè)同學(xué)有一個(gè)考試成績，如何將這30名同學(xué)的成績由高至低進(jìn)行排序？ 問題分析：這是一個(gè)排

9、序問題。一般認(rèn)為，日常的數(shù)據(jù)處理中有1/4的時(shí)間應(yīng)用在排序上，據(jù)不完全統(tǒng)計(jì)，到目前為止的排序算法有上千種。算法設(shè)計(jì)：1、用選擇排序解決方案2、用插入排序解決方案 8.2 典型問題的算法設(shè)計(jì)第 18 頁8.2.1 成績排名問題排序算法1、用選擇排序解決方案?首先在30名同學(xué)中找到最高的分?jǐn)?shù)，使其排在第1位；?然后在剩下的分?jǐn)?shù)中再找最高的分?jǐn)?shù)，使其排在第2位；?依次類推，直至所有的分?jǐn)?shù)都已經(jīng)排完。這是一種常見的人工實(shí)現(xiàn)方式，這種解決方案其實(shí)就是計(jì)算機(jī)排序算法中的選擇排序。 8.2 典型問題的算法設(shè)計(jì)第 19 頁對5個(gè)數(shù)5,7,4,2,8按從小到大的順序排序:選擇法5,7,4,2,8 5 22,7,

10、4,5,8 7 42,4,7,5,8 7 52,4,5,7,8 2,4,5,7,8 第一輪（n-1=4）次比較第二輪（n-2=3）次比較完成排序 第三輪（n-3=2）次比較第四輪（n-2=1）次比較引引 8.2 典型問題的算法設(shè)計(jì)第 20 頁選擇排序的改進(jìn)： 以冒泡排序法為基礎(chǔ)，在兩兩比較后，不馬上進(jìn)行交換，而是在找到最大（或最小）的數(shù)之后，記錄該數(shù)的位置(在數(shù)組中的下標(biāo))，待一輪比較完畢，再將最大（或最小）的數(shù)一次交換到位。 8.2 典型問題的算法設(shè)計(jì)第 21 頁8.2.1 成績排名問題排序算法2、用插入排序解決方案?首先將第1位同學(xué)的分?jǐn)?shù)放在一個(gè)隊(duì)列中；?然后將第2位同學(xué)的分?jǐn)?shù)與隊(duì)列中的第

11、1位同學(xué)的分?jǐn)?shù)進(jìn)行比較，如果分?jǐn)?shù)比其高，則放在后面，如果分?jǐn)?shù)比其低，則放在前面；?然后將第3位同學(xué)的分?jǐn)?shù)與隊(duì)列中的兩位同學(xué)的分?jǐn)?shù)進(jìn)行比較，找到一個(gè)插入并仍保持有序的位置，將第3位同學(xué)的分?jǐn)?shù)插入到該位置；?依次類推，直至將30位同學(xué)的分?jǐn)?shù)都插入到相應(yīng)位置。這也是一種常見的人工實(shí)現(xiàn)方式，該解決方案在計(jì)算機(jī)排序算法中叫做插入排序。 8.2 典型問題的算法設(shè)計(jì)第 22 頁插入排序基本思想假設(shè)：已經(jīng)存在一個(gè)長度為N的有序(從小到大排列)的數(shù)據(jù)序列，要將一個(gè)新的數(shù)插入到該序列中，要求插入后的新序列(長度為N+1)仍然保持有序。 算法關(guān)鍵是要確定新數(shù)據(jù)插入的合適位置。對于一個(gè)有序序列，從后向前進(jìn)行比較，若序

12、列中的數(shù)大于要插入的數(shù)，則將數(shù)列中的數(shù)向后移動；否則，完成插入操作。 8.2 典型問題的算法設(shè)計(jì)第 23 頁8.2.1 成績排名問題排序算法還有哪些經(jīng)典的排序算法？比較一下這些排序算法的特點(diǎn)，以及在哪種數(shù)據(jù)下能達(dá)到最佳性能？ 8.2 典型問題的算法設(shè)計(jì)第 24 頁8.2.2 斐波那契數(shù)列問題遞歸算法問題描述：著名意大利數(shù)學(xué)家列昂納多斐波那契（Leonardo Fibonacci）1202年提出一個(gè)有趣的數(shù)學(xué)問題：假定一對雌雄的大兔每一個(gè)月能生一對雌雄的小兔，每對小兔過一個(gè)月能長成大兔再生小兔，問一對兔子一年能繁殖幾對小兔？于是得到一個(gè)數(shù)列：1，1，2，3，5，8，13，21，34，55，89，

13、144，233，377， 610， 987， 1597，這就是著名的菲波那契數(shù)列。問題分析：題目中數(shù)列的規(guī)律很容易發(fā)現(xiàn)：后面的一個(gè)數(shù)總是前兩個(gè)數(shù)的和。如果按照人的思維習(xí)慣來計(jì)算，該問題看似很容易，但實(shí)際做起來就會遇到問題。在數(shù)學(xué)上，斐波那契數(shù)列是以遞歸的方法來定義的。 8.2 典型問題的算法設(shè)計(jì)第 25 頁8.2.2 斐波那契數(shù)列問題遞歸算法1、數(shù)學(xué)方法求解這是一個(gè)典型的遞歸關(guān)系。根據(jù)以上分析可見，在數(shù)學(xué)上，斐波納契數(shù)列以如下遞歸方法定義：122111nnnFFFFF 8.2 典型問題的算法設(shè)計(jì)第 26 頁8.2.2 斐波那契數(shù)列問題遞歸算法情景問題8-1 如果你看到有這樣一個(gè)題目：某人把一個(gè)

14、8*8的方格切成四塊，拼成一個(gè)5*13的長方形，故作驚訝地問你：為什么6465？你知道這是為什么嗎？提示：斐波那契數(shù)列有一項(xiàng)性質(zhì)，從第二項(xiàng)開始，每個(gè)奇數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積多1，每個(gè)偶數(shù)項(xiàng)的平方都比前后兩項(xiàng)之積少1。 8.2 典型問題的算法設(shè)計(jì)第 27 頁8.2.2 斐波那契數(shù)列問題遞歸算法2、算法設(shè)計(jì)遞歸算法就是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題，對這個(gè)子問題用函數(shù)（或過程）來描述，然后遞歸調(diào)用該函數(shù)（或過程）以獲得問題的最終解。遞歸算法描述簡潔而且易于理解，所以使用遞歸算法的計(jì)算機(jī)程序也清晰易讀。 8.2 典型問題的算法設(shè)計(jì)第 28 頁8.2.2 斐波那契數(shù)列問題遞歸算法2、算法

15、設(shè)計(jì)遞歸算法一般有三個(gè)要求（1）每次調(diào)用在規(guī)模上都有所縮?。?）相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備（3）在問題的規(guī)模最小時(shí)，必須直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的遞歸算法需要關(guān)鍵的兩步（1）確定遞歸公式（2）確定邊界（終止）條件 8.2 典型問題的算法設(shè)計(jì)第 29 頁8.2.2 斐波那契數(shù)列問題遞歸算法遞歸算法：遞歸函數(shù)用偽代碼描述為：Int Fib(int n) /斐波那契（Fibonacci）數(shù)列 if (n = 1或 n = 2) return 1; /邊界條件，無需遞歸if (n=3) return Fib(n-1)+Fib(n-2); /

16、通過遞歸公式求解return 0; /預(yù)防錯(cuò)誤 8.2 典型問題的算法設(shè)計(jì)第 30 頁8.2.2 斐波那契數(shù)列問題遞歸算法練習(xí)與思考8-2 對于當(dāng)前普通的計(jì)算機(jī)來說，求解斐波那契數(shù)列第50項(xiàng)的值所需要的時(shí)間不超過1秒。不妨嘗試一下，通過人工計(jì)算所需的時(shí)間大約是多久？ 總結(jié)一下，在這個(gè)問題上，人的思維與計(jì)算機(jī)思維是否有相同之處？計(jì)算機(jī)解決問題的優(yōu)勢是什么？ 8.2 典型問題的算法設(shè)計(jì)第 31 頁8.2.3 最大公約數(shù)問題-迭代算法問題描述：公約數(shù)，亦稱“公因數(shù)”。如果一個(gè)整數(shù)同時(shí)是幾個(gè)整數(shù)的約數(shù)，稱這個(gè)整數(shù)為它們的“公約數(shù)”；公約數(shù)中最大的稱為最大公約數(shù)。求最大公約數(shù)是數(shù)學(xué)中的經(jīng)典問題。問題分析

17、：歐幾里德算法（又稱輾轉(zhuǎn)相除法）是求解最大公約數(shù)的傳統(tǒng)方法，其算法的核心基于這樣一個(gè)原理： 如果有兩個(gè)正整數(shù)a和b（a = b），r為a除以b的余數(shù)，則有a和b的公約數(shù)與b和r的最大公約數(shù)是相等的這一結(jié)論(證明從略)?；谶@個(gè)原理，經(jīng)過反復(fù)迭代執(zhí)行，直到余數(shù)r為0時(shí)結(jié)束迭代，此時(shí)的除數(shù)便是a和b的最大公約數(shù)。 8.2 典型問題的算法設(shè)計(jì)第 32 頁8.2.3 最大公約數(shù)問題-迭代算法利用迭代算法解決問題，需要做好以下三個(gè)方面的工作：（1）確定迭代變量。（2）建立迭代關(guān)系式。（3）對迭代過程進(jìn)行控制。 8.2 典型問題的算法設(shè)計(jì)第 33 頁8.2.3 最大公約數(shù)問題-迭代算法圖8-5 歐幾里德算

18、法的迭代計(jì)算過程3、用迭代算法求解最大公約數(shù)以136和58為例：第1步，13658=2 余20；第2步，5820=2 余18；第3步，2018=1 余2；第4步，182=9 余0算法結(jié)束。則最大公約數(shù)為2。 8.2 典型問題的算法設(shè)計(jì)第 34 頁 8.1 算法 8.2 典型問題的算法設(shè)計(jì) 8.3 數(shù)據(jù)結(jié)構(gòu) 8.4 程序設(shè)計(jì)第8章 算法與程序設(shè)計(jì)第八章 算法與程序設(shè)計(jì) 第 35 頁 8.3 數(shù)據(jù)結(jié)構(gòu)8.3.1 計(jì)算機(jī)語言中的數(shù)據(jù)組織1.數(shù)組的數(shù)據(jù)組織數(shù)組是一種在實(shí)際應(yīng)用中非常重要的數(shù)據(jù)組織形式，在大量的程序設(shè)計(jì)中，也是循環(huán)控制結(jié)構(gòu)的重要支撐。 舉例來說，當(dāng)完成10個(gè)變量的求和計(jì)算，可以通過聲明1

19、0個(gè)變量a1、a2、a3、a4、a5、a6、a7、a8、a9、a10，將變量賦值后，通過計(jì)算a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 即可獲得最終的答案。而假如需要完成1000個(gè)變量甚至10000個(gè)變量的求和計(jì)算，則聲明1000個(gè)變量甚至10000個(gè)變量，顯然是一種不合適的行為。 如在C語言中，聲明100個(gè)整數(shù)變量的數(shù)組形式如下：int arr100;第 36 頁8.3.1 計(jì)算機(jī)語言中的數(shù)據(jù)組織1.數(shù)組的數(shù)據(jù)組織圖8-6 數(shù)組的存儲與存取形式 8.3 數(shù)據(jù)結(jié)構(gòu)第 37 頁8.3.1 計(jì)算機(jī)語言中的數(shù)據(jù)組織1.數(shù)組的數(shù)據(jù)組織100個(gè)變量的

20、求和操作可以使用如下的算法形式來完成，形式非常簡潔。int sum = 0;for(i=0; i100; i+)sum += arri; 8.3 數(shù)據(jù)結(jié)構(gòu)第 38 頁2. 結(jié)構(gòu)體的數(shù)據(jù)組織表8-4 學(xué)生成績表學(xué)號學(xué)號姓名姓名性別性別英語英語線性代數(shù)線性代數(shù)物理物理離散數(shù)學(xué)離散數(shù)學(xué)1104030308趙男806481851104030309錢男715483601104030301孫女756083501104030317李男816784601104030324周女827260678.3.1 計(jì)算機(jī)語言中的數(shù)據(jù)組織 8.3 數(shù)據(jù)結(jié)構(gòu)第 39 頁2.結(jié)構(gòu)體的數(shù)據(jù)組織如: 針對上述的數(shù)據(jù)表格，可以針對每

21、一名同學(xué)的數(shù)據(jù)組裝成一個(gè)結(jié)構(gòu)體類型，以C語言為例，其定義如下：struct studentint no;char name20;char sex5;float score4;通過這種“結(jié)構(gòu)體”，可以將“列式存儲方式”改變?yōu)椤靶惺酱鎯Ψ绞健保瑥亩谒惴ǖ膶?shí)現(xiàn)。8.3.1 計(jì)算機(jī)語言中的數(shù)據(jù)組織 8.3 數(shù)據(jù)結(jié)構(gòu)第 40 頁1.數(shù)據(jù)結(jié)構(gòu)的概念通常，一些常用的、成熟的方法整理成為若干固定的數(shù)據(jù)組織形式，這就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)中的典型形式有數(shù)組、棧、隊(duì)列、鏈表、樹、圖、堆、散列表等類型。8.3.2 數(shù)據(jù)結(jié)構(gòu) 8.3 數(shù)據(jù)結(jié)構(gòu)第 41 頁2. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)可以根據(jù)其是否具有底層結(jié)構(gòu)劃分成基本

22、類型和構(gòu)造類型兩類，而常見的基本類型有：8.3.2 數(shù)據(jù)結(jié)構(gòu) 8.3 數(shù)據(jù)結(jié)構(gòu)第 42 頁3. 數(shù)據(jù)的存儲結(jié)構(gòu)常見的存儲映像方式如下： 順序方式 鏈接方式 索引方式 散列方式上面4種方式可以混合使用，同一種數(shù)據(jù)在不同的算法和應(yīng)用中也可以采用不同的存儲映像方式，從而形成不同的數(shù)據(jù)結(jié)構(gòu)。8.3.2 數(shù)據(jù)結(jié)構(gòu) 8.3 數(shù)據(jù)結(jié)構(gòu)第 43 頁4. 數(shù)據(jù)的運(yùn)算數(shù)據(jù)以一定的方式組織在一起的目的是為了對其進(jìn)行加工處理，常見的運(yùn)算有：插入在已有數(shù)據(jù)結(jié)構(gòu)中添加新的數(shù)據(jù)元素或結(jié)點(diǎn)。刪除 刪除數(shù)據(jù)結(jié)構(gòu)中的某個(gè)數(shù)據(jù)元素或結(jié)點(diǎn)。查找 在數(shù)據(jù)結(jié)構(gòu)中查找某特定數(shù)據(jù)元素。排序 按某種特定規(guī)律改變數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素或結(jié)點(diǎn)的排列

23、順序。更新 改變數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的值。8.3.2 數(shù)據(jù)結(jié)構(gòu) 8.3 數(shù)據(jù)結(jié)構(gòu)第 44 頁練習(xí)與思考8-3 如果你要編寫給100個(gè)數(shù)排序的程序，你會考慮用什么形式存放數(shù)據(jù)？為什么？ 8.3 數(shù)據(jù)結(jié)構(gòu)第 45 頁 8.1 算法 8.2 典型問題的算法設(shè)計(jì) 8.3 數(shù)據(jù)結(jié)構(gòu) 8.4 程序設(shè)計(jì)第8章 算法與程序設(shè)計(jì)第八章 算法與程序設(shè)計(jì) 第 46 頁 8.4 程序設(shè)計(jì)8.4.1 計(jì)算機(jī)語言與語言處理系統(tǒng)1.計(jì)算機(jī)語言的分類從發(fā)展角度 機(jī)器語言、匯編語言和高級語言第一代：機(jī)器語言 （2進(jìn)制機(jī)器指令，機(jī)器能直接執(zhí)行）第二代：匯編語言 （符號代替機(jī)器語言，需要翻譯）第三代：高級語言 （英語和數(shù)學(xué)語言代替機(jī)

24、器語言，需要翻譯）第 47 頁1.計(jì)算機(jī)語言的分類從高級語言自身特點(diǎn) 過程式語言，如：Cobol、Forturn、Algol、Pascal、Ada、C； 函數(shù)式語言，如：Lisp； 數(shù)據(jù)流語言，如S：ISAL、VAL； 面向?qū)ο笳Z言，如：Smalltalk、CLU、C+； 邏輯語言，如：Prolog； 字符串語言，如：SNOBOL； 并發(fā)程序設(shè)計(jì)語言，如：Concurrent、 Pascal、Modula 2等類型的語言。 8.4 程序設(shè)計(jì)8.4.1 計(jì)算機(jī)語言與語言處理系統(tǒng)第 48 頁2.計(jì)算機(jī)語言處理系統(tǒng) 解釋源程序解釋程序邊解釋邊執(zhí)行結(jié)果用戶編輯 編輯器出錯(cuò)目標(biāo)程序可執(zhí)行程序庫文件連接程序編譯程序編輯器出錯(cuò)編譯編譯連接編輯 用戶源程序結(jié)果 8.4 程序設(shè)計(jì)8.4.1 計(jì)算機(jī)語言與語言處理系統(tǒng)第 49 頁1.數(shù)據(jù)結(jié)構(gòu)與算法程序=數(shù)據(jù)結(jié)構(gòu)+算法程序設(shè)計(jì)過程的四個(gè)步驟（1）分析問題，建立數(shù)學(xué)模型。（2）確定數(shù)據(jù)結(jié)構(gòu)和算法。（3）編制程序。（4）調(diào)試程序。 8.4 程序設(shè)計(jì)8.4.2 面向過程程序設(shè)計(jì)第 50 頁2.結(jié)構(gòu)化程序設(shè)計(jì)