《大學(xué)計算機基礎(chǔ)》第二層次子課程-C 程序設(shè)計基礎(chǔ)(2010V1).ppt

1、1,大學(xué)計算機基礎(chǔ),北京航空航天大學(xué),教學(xué)課件,2,第二層次子課程 C 程序設(shè)計基礎(chǔ),5.3 程序設(shè)計步驟與程序設(shè)計方法,5.1 程序和程序設(shè)計語言,5.2 算法,5.4 常用程序設(shè)計語言,5.5 程序設(shè)計范型,3,本課程重點,程序的概念 程序設(shè)計語言的結(jié)構(gòu) 算法的概念與描述方法 程序設(shè)計步驟 程序設(shè)計方法 VC 集成開發(fā)環(huán)境,4,5.1 程序和程序設(shè)計語言,5.1.1 程序的一般概念 5.1.2 程序設(shè)計語言的概述 5.1.3 程序設(shè)計語言的結(jié)構(gòu),5,5.1.1程序的一般概念,生活中程序的概念,何事？,策劃,導(dǎo)演,例1：年終總結(jié)會的程序： 會議主持宣布會議開始 領(lǐng)導(dǎo)講話 個人或團隊代表發(fā)言

2、領(lǐng)導(dǎo)總結(jié) 會議主持宣布會議結(jié)束,6,5.1.1程序的一般概念（續(xù)1）,生活中程序的概念,步行 騎車 開車 時間 紅綠燈 鐵道 上坡、下坡,依據(jù)實際案例并精心計算,解決該計算問題的方法、步驟就包含了程序的概念。,例2：某人從甲地到丙地去。,7,5.1.1程序的一般概念（續(xù)2）,計算機程序的概念：,為實現(xiàn)某一算法而編寫的指令序列。 宏觀地描述該指令序列，可用計算機的 機器語言 匯編語言 高級語言 用經(jīng)典的公式可表示為： 程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 1976年Niklaus Wirth（也是Pascal語言發(fā)明者，1984年獲得圖靈獎）的專著： Algorithms Data Structures

3、 Programs,8,5.1.2程序設(shè)計語言的概述,程序設(shè)計編寫程序的全過程。 有學(xué)者認為： 程序設(shè)計 = 算法 + 數(shù)據(jù)結(jié)構(gòu) + 程序設(shè)計語言,程序設(shè)計語言人和計算機之間對話和交流的一種工具，用于描述計算機所執(zhí)行的操作。,計算機程序設(shè)計語言有幾百種，但是最常用的不過10多種，了解一些程序設(shè)計語言的不同特性，有助于為特定任務(wù)而選擇適當(dāng)?shù)某绦蛟O(shè)計語言。,9,不同類型的計算機語言,機器語言（Machine Language） 匯編語言（Assembly Language ） 高級語言（High Level Language）,程序設(shè)計語言的特點,10,1.機器語言（Machine Languag

4、e）,指令指揮計算機完成某個基本操作的命令。,指令系統(tǒng)所有的指令集合。 （第一代程序設(shè)計語言） 機器語言用二進制代碼表示指令系統(tǒng)的語言。 機器語言程序由二進制代碼按一定規(guī)則組成的、能被機器理解和運行的指令序列。（也稱可執(zhí)行程序 ） 例如：計算累加器A=8+10的機器語言程序如下：,11,2.匯編語言（Assembly Language ）,匯編語言實質(zhì)就是以容易記憶的代碼或英文單詞來代替約定的機器指令。（第二代程序設(shè)計語言）,例如：用ADD表示加、SUB表示減、JMP表示跳轉(zhuǎn)、MOV表示數(shù)據(jù)的傳送指令等 。 匯編源程序使用匯編語言編寫的程序。 例如：上述計算累加器A=8+10的匯編語言程序如下

5、：,12,3.高級語言（High Level Language）,高級語言類似數(shù)學(xué)語言或人的自然語言，同時又不依賴于某種計算機硬件，使得設(shè)計編制的程序能夠在所有機器上通用。 （第三代程序設(shè)計語言）,程序設(shè)計語言在不同的系統(tǒng)平臺使用比較普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA 67、Pascal、C、Smalltalk 80、Ada、C+、VC、VB、Delphi、Java、JavaScript、C#、Visual BASIC.NET。 可視化語言構(gòu)成了命令式語言中的另一個子類。最流行的可視化語言Visual BASIC（1999年），已被V

6、isual BASIC.NET（2002年）取代。提供拖拉式生成代碼段的功能。一度被認作第四代語言，此說法已不再使用了。,13,程序設(shè)計語言的特點,機器語言的特點： 編程難 效率高 需要指令系統(tǒng) 難讀 難維護,高級語言的特點： 編程容易 效率低 需要編譯系統(tǒng) 易讀 易維護,匯編語言的特點： 編程不容易 效率較高 需要匯編程序 不易讀 不易維護,14,5.1.3程序設(shè)計語言的結(jié)構(gòu),程序結(jié)構(gòu)的多樣性： 結(jié)構(gòu)化程序 模塊化程序 面向?qū)ο蟮某绦蚪Y(jié)構(gòu),一個良好結(jié)構(gòu)的程序具有以下等特點： 結(jié)構(gòu)清晰 容易閱讀 容易理解 容易驗證 容易維護 1996年，計算機科學(xué)家Boehm和Jacopini提出并從數(shù)學(xué)上證

7、明 任何一個算法，都能以三種基本控制結(jié)構(gòu)表示，即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。,15,結(jié)構(gòu)化程序設(shè)計中順序結(jié)構(gòu),按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序。,16,結(jié)構(gòu)化程序設(shè)計中選擇結(jié)構(gòu),根據(jù)條件的判斷確定應(yīng)該執(zhí)行哪一條分支的語句序列。（又稱為分支結(jié)構(gòu) ）,單分支、多分支結(jié)構(gòu)？,17,結(jié)構(gòu)化程序設(shè)計中循環(huán)結(jié)構(gòu),主要用于重復(fù)執(zhí)行相同的語句序列（被稱為循環(huán)體），當(dāng)（直到）測試條件為假時才可終止執(zhí)行循環(huán)體。,18,結(jié)構(gòu)化程序設(shè)計的特點,每種結(jié)構(gòu)，只有一個入口和一個出口，這是結(jié)構(gòu)化設(shè)計的一個原則。,遵循結(jié)構(gòu)化程序設(shè)計的原則，按照結(jié)構(gòu)化程序設(shè)計方法設(shè)計出的程序具有明顯的優(yōu)點： 其一，程序易讀

8、、理解和維護。程序員用結(jié)構(gòu)化編程方法，將復(fù)雜程序分解成若干子結(jié)構(gòu)，便于控制、降低程序的復(fù)雜性，因此容易編寫程序，同時便于驗證程序。 其二，提高編程工作效率，降低軟件開發(fā)成本。由于結(jié)構(gòu)化編程方法能夠把錯誤控制到最低限度，因此能夠減少調(diào)試和查錯的時間。,19,5.2 算法,5.2.1 算法的定義、分類與特征 5.2.2 算法的描述方法 5.2.3 程序設(shè)計典型算法,20,5.2.1算法的定義、分類與特征,Algorithms Data Structures Programs 1976年 N Wirth 的程序概念，在計算機軟件開發(fā)行業(yè)中產(chǎn)生了極為深遠的影響，從而推動了軟件開發(fā)技術(shù)和方法步入正軌，使

9、人們開始深入研究數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計與分析的技術(shù)和方法。,#include void main() /c1_5.cpp int a, b; printf(Please enter a and b:); scanf(%d%d, ,#include void main() /c1_6.cpp int a, b, c; printf(Please enter a and b:); scanf(%d%d, ,21,1. 算法的定義與分類,CPU所遵循的機器周期與下面這個算法一樣簡單。 只要未發(fā)出停機指令就執(zhí)行以下步驟： 取一條指令。 解碼該指令。 執(zhí)行該指令。,生活當(dāng)中的普通活動剝豌豆。 獲得一籃子未剝

10、皮的豌豆和一只空碗。 只要籃中還有豌豆就執(zhí)行下面的步驟： 從籃子里拿出一個豌豆。 剝開豌豆的豆莢。 把剝落得豆放到碗里面。 扔掉空豆莢。,22,1. 算法的定義與分類 （續(xù)1）,算法的定義算法是定義一個可終止過程的一組有序的、無歧義的、可執(zhí)行的步驟的集合。 華氏溫度與攝氏溫度的轉(zhuǎn)換問題 算法1：用代數(shù)公式表示 算法2：用指令表示 將攝氏溫度數(shù)值乘以 ，然后在乘積上加32。,外行則認為該指令是模糊的、有歧義的。,算法的細致程度,23,1. 算法的定義與分類 （續(xù)2）,用一張正方形的紙折疊成一只鳥 該過程通過自然的溝通方式常常會引起誤解。 有些時候是因為算法描述中使用的術(shù)語可能擁有多種含義。 計算

11、機科學(xué)解決歧義性問題的方法 建立一組嚴格定義的構(gòu)件塊。 利用一系列的構(gòu)件塊來構(gòu)建算法的表示。 這種構(gòu)件塊稱作原語（primitive）。,24,1. 算法的定義與分類 （續(xù)3）,原語被用于消除算法表示中的歧義性問題。 語法是原語的符號表示（air）。 語義是指該原語的含義（氣體物質(zhì)）。 原語的集合以及說明如何組合這些原語來表示比較復(fù)雜的想法的規(guī)則集合就構(gòu)成了一種程序設(shè)計語言。 程序、算法和進程既是不同的卻又有關(guān)聯(lián)的。 程序是一個算法的表示。 進程是執(zhí)行算法的活動。,25,1. 算法的概念,算法解決某個具體問題而采取的方法與步驟的完整和準(zhǔn)確的描述。 是指令的有限序列，其中每一條指令表示一個或多個

12、操作。 是問題的程序化解決方案，這些解決方案本身并不是答案，而是獲得答案的精確指令。,算法的分類 順序算法：是由馮諾依曼型計算機體系結(jié)構(gòu)所決定的，其主要思想是指令逐條運行，每次執(zhí)行一步操作。 并行算法：要求在一些更新式的計算機中可以在同一時間執(zhí)行多條指令。,26,2. 算法的特征,一個算法必須具備五項基本特征：有窮性、確定性、數(shù)據(jù)輸入、數(shù)據(jù)輸出和可行性。,（1）有窮性算法是有序指令的集合，并在執(zhí)行有窮步驟后能夠終止。 （2）確定性每條指令必須有確切的含義，且無二義性。在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入數(shù)據(jù)只能得到相同的輸出數(shù)據(jù)。 （3）輸入數(shù)據(jù)可有零個或多個輸入數(shù)據(jù)。這

13、些輸入數(shù)據(jù)取自于某個特定對象的集合。 （4）輸出數(shù)據(jù)必須有一個或多個輸出數(shù)據(jù)。 （5）可行性描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)，也可以證明整個算法實施后可以得到預(yù)期的解。,27,2. 算法的特征（續(xù)1）,算法的發(fā)現(xiàn) 程序開發(fā)由兩個活動組成發(fā)現(xiàn)潛在的算法和以程序的方式表示算法。 問題求解的藝術(shù) 數(shù)學(xué)家（波利亞GPolya）在1945年提出非嚴格定義的問題求解階段：,第1階段 理解問題。 第2階段 設(shè)計一個解決問題的計劃。 第3階段 完成計劃。 第4階段 從準(zhǔn)確度及其是否有潛力作為一個解決其他問題的工具這 兩方面來評估這個計劃。,上述階段移植到程序開發(fā)中變成： 第1階段 理解問

14、題。 第2階段 尋找一個可能解決問題的算法過程的思路。 第3階段 闡明算法并且用程序?qū)⑵浔磉_出來。 第4階段 從準(zhǔn)確度及其是否有潛力作為一個工具解決其他問題這兩方面來評估這個程序。,階段與步驟的差異,28,例. 甲承擔(dān)了確認乙的3個孩子年齡的任務(wù),乙告訴甲3個孩子的年齡乘積是36。 在考慮了這個線索以后，甲要求乙給出另外的線索。 乙告訴甲3個孩子的年齡之和。 甲再次要求乙給出其他線索。 乙告訴甲：他的最大的一個孩子彈鋼琴。 在得到這個線索之后，甲得到了乙的3個孩子的年齡。,（1，1，36） （1，6，6） （1，2，18） （2，2，9） （1，3，12） （2，3，6） （1，4， 9） （

15、3，3，4） （a）乘積為36的三元組,這種解決問題過程中的不規(guī)則性是開發(fā)問題求解的系統(tǒng)方法的基礎(chǔ)。 另一個不規(guī)則性在于，那些還沒有得到明顯成功的問題解決者所得到的神奇靈感可能在完成其他任務(wù)的時候突然成為了原來問題的一個解決方法。,1+1+36=38 1+6+6=13 1+2+18=21 2+2+9=13 1+3+12=16 2+3+6=11 1+4+ 9 =14 3+3+4=10 （b）a中的每個三元組的和,2+2+9=13,29,例. 求甲乙丙丁賽跑的名次排序,在甲、乙、丙和丁進行賽跑之前，他們分別對結(jié)果進行預(yù)測： 甲預(yù)測乙將會獲勝。 乙預(yù)測丁將是最后一名。 丙預(yù)測甲是第三名 丁預(yù)測甲的預(yù)

16、測將是正確的。 這幾個預(yù)測只有一個是正確的，并且是最后的獲勝者做出的預(yù)測。,解1：丙、乙、甲、丁 解2：丙、丁、甲、乙,進入問題后，會發(fā)現(xiàn)：獲得完整的解決方法的過程僅僅是將我們的知識在此處擴展應(yīng)用。,被排除,30,算法的入門,知道怎樣進入問題并不等于知道如何去做這件事。為了得到立足點，也就是認識到如何把對于問題的初始介入擴展為問題的解決方法，就為要求問題解決者創(chuàng)造一個可能的入口。 對于如何入門？波利亞和其他人提出了很多通用的方法。 反方向解決問題（白紙與紙鳥） 尋找一個相關(guān)的、解決起來較簡單的并且在此以前已經(jīng)得到解決的問題，然后嘗試把這個解決方法用到當(dāng)前問題中。 逐步求精（stepwise r

17、efinement）數(shù)據(jù)處理中一種重要設(shè)計方法 自頂向下方法（top-down methodology）一般到特殊 自底向上方法（bottom-up methodology）特殊到一般,31,算法的入門 （續(xù)1）,四個人名（ David 、 Alice 、 Carol和Bob ）按照升序排序指令。 交換名字 David和Alice。 將名字Carol移到Alice和David之間。 將名字Bob移到Alice和Carol之間。,通常，程序開發(fā)并不是去解決一個問題的一個特定實例，而是要去尋找一種適用于求解一個問題的所有實例的一般算法。 可以通過考慮一個特殊的情況來進入問題，然后得到一個能夠用于開

18、發(fā)通用算法的一般原則。 （三個人名排序指令）,特定實例,32,例5.1 一個非算法的計數(shù)過程, 令n為0； 置n為n+1； 返回。,結(jié)論：不能稱為算法。 原因：違背了算法特征中（1）、（4）、（5）。,有窮性（有效性）：考察下面這條指令: 給出一個所有整數(shù)的列表。,33,例5.2 計數(shù)器算法,用自然語言編寫一個不超過1萬次的計數(shù)器算法： 令n為0； 置n為n+1 若n小于10000，則返回；否則，輸出n之值，且算法到此結(jié)束。,結(jié)論：是算法。 原因：符合算法特征。,在算法設(shè)計過程中，其實還有有關(guān)正確性、可讀性、健壯性、效率與低存儲量需求，以及算法效率的度量等問題。,34,5.2.2算法的描述方法

19、,流程圖（FlowChart） PAD圖（Problem Analysis Diafram，問題分析圖） N-S圖 自然語言 偽代碼 UML圖 （Unified Modeling Language，統(tǒng)一建模語言）,35,1. 流程圖,流程圖（框圖）用不同形狀的幾何圖形表示不同性質(zhì)的操作，用流程線指明算法的執(zhí)行方向。ANSI(美國國家標(biāo)準(zhǔn)化協(xié)會)、ISO（國際標(biāo)準(zhǔn)化組織）和我國國家標(biāo)準(zhǔn)中均有類似的規(guī)定。常見的流程圖符號如下：,向下或向右的流程線可以不畫出箭頭。當(dāng)流程線有交叉時，則畫一半圓通過交叉點。,36,用流程圖描述的計數(shù)器算法,37,2. PAD圖,由日立公司推出的PAD圖是一種二維圖。即從

20、上向下順序執(zhí)行，從左到右表示層次關(guān)系。表示三種基本結(jié)構(gòu)的PAD圖如下：,38,3. N-S圖,1973年美國兩位學(xué)者提出無流程線的N-S圖（盒圖）。,結(jié)構(gòu)化程序設(shè)計由三種基本結(jié)構(gòu)而組成，則算法也應(yīng)采用結(jié)構(gòu)化描述方法，N-S圖的基本單元是矩形框，框內(nèi)可以有三種基本結(jié)構(gòu)，形如堆積木，也只有一個入口和一個出口。三種基本結(jié)構(gòu)的N-S圖如下：,39,用N-S圖描述的計數(shù)器算法,40,4. 自然語言,自然語言是人們?nèi)粘Ｉ?、工作和學(xué)習(xí)中使用的通用語言，使用自然語言的文字描述算法通俗易懂，但也有它的缺陷：,（1）容易產(chǎn)生歧義性，因為自然語言經(jīng)常要根據(jù)上下文才能判別其含義，不太嚴格。 （2）自然語言很難清楚地

21、表達算法的邏輯流程，對于算法中的條件判斷、循環(huán)，尤其是在這些處理中還有多層嵌套，就很難用清晰而直觀的語言來表達算法的流程。因此僅適于描述簡單問題。,41,5. 偽代碼,偽代碼是介于自然語言和計算機語言之間的文字和符號，它不能被計算機所理解，但使用偽代碼描述的算法很容易轉(zhuǎn)變成某種編程語言。,/用偽代碼描述的計數(shù)器算法如下： n 0 do n n+1 while n 10000 輸出n，且算法到此結(jié)束。,常用的偽代碼是用自然語言與類Pascal或類C語言相結(jié)合的方法來描述算法。,42,流程圖形的繪制工具,當(dāng)使用圖形描述算法時，流程圖形的繪制工具有很多。,一般比較簡單的圖形可用Word或PowerP

22、oint中的繪圖工具欄來制作完成，若安裝了功能強大的Microsoft Office Visio 2003，則可以更快地繪制具有專業(yè)水平的高質(zhì)量圖形。 在Visio 2003中： 含有豐富的基本流程圖形狀。 能夠快速、簡便地建立流程圖、組織圖、日歷時間表和其它多種圖表。 支持縮放矢量圖形（SVG），這是一種新的圖形格式標(biāo)準(zhǔn)。 集合Internet的運用，可使用不同的語言創(chuàng)建繪圖、創(chuàng)建包含多種語言的繪圖以及跨多種語言共享繪圖和展開協(xié)作。 通過支持新的漢字編碼標(biāo)準(zhǔn)GB18030，可從這個新的字符編碼集中創(chuàng)建包含漢字的繪圖。,43,5.2.3程序設(shè)計典型算法,算法數(shù)值算法或非數(shù)值算法：,數(shù)值算法主要

23、用于數(shù)值求解或分析，如：求和、求平方根、解方程、用組合梯形法則求定積分等。 非數(shù)值算法主要用于各領(lǐng)域管理類的信息處理，如：各種排序、查找等。 本節(jié)介紹一些簡單的常用算法，并假設(shè)各數(shù)據(jù)均能滿足值域要求。,44,1. 求3個整數(shù)的最大值算法,為了編寫求3個整數(shù)最大值的通用實現(xiàn)過程，采用主函數(shù)調(diào)用子函數(shù)的形式描述算法。,（1）主函數(shù)算法描述如下： 輸入三個整數(shù)a,b,c; max = max3(a,b,c); 輸出max。,（2）max3 子函數(shù)算法描述如下： 從a與b中取大數(shù)送m中; 從m與c中取大數(shù)送m中; 返回m給主函數(shù)。,45,求3個整數(shù)的最大值的C程序,/*使C預(yù)編譯包含I/O頭文件，則可

24、用scanf、printf函數(shù) */ #include void main(void) int a, b, c, max; /* 定義 4 個整型變量 */ int max3(int a, int b, int c); /* max3 函數(shù)原形聲明 */ printf(“Input 3 integer numbers:”);/* 輸出雙引號中的提示信息 */ scanf(“%d%d%d”, /* 輸出 max 中的最大值 */ /* End of main function */,/* 求 3 個整數(shù)的最大值的子函數(shù) max3 */ int max3(int a,int b,int c) /*

25、 max3 函數(shù)將返回整型值 */ int m; /* 定義 m 整型變量 */ if( a b ) m = a; /* 從 a 與 b 中取大數(shù)送 m 中 */ else m = b; if( m c ) ; /* 從 m 與 c 中取大數(shù)送 m 中，“；”即m=m */ else m = c; return(m); /* 返回 m 給主函數(shù) */ /* End of max3 function */,/Lab2.c,46,2. 歐幾里得算法,求解兩個不全為0的非負整數(shù)m和n的最大公約數(shù)，可以采用以下歐幾里得算法。,（1）歐幾里得算法主函數(shù)描述如下： 輸入兩個不全為0的非負整數(shù)m,n; Ec

26、d = Euclid(m,n); 輸出Ecd，且算法到此結(jié)束。,（2）Euclid(m,n) 子函數(shù)算法描述如下： while n 0 do r m mod n m n n r return m,47,3. 兩個變量值的交換算法,計算機實現(xiàn)的兩個變量值的交換算法如下：, 令 a=5, b=10 c a, a b, b c 輸出 a 和 b 的值。,/* 兩個變量值交換算法的 C 源程序 */ void main(void) int a=5, b=10, c; /* 定義 a、b、c 3個整型變量 */ printf(“交換前: a=%d, b=%dn”, a, b);/* 交換前輸出a和b的值

27、 */ c = a; /* 將 a 中的值賦值給 c */ a = b; /* 將 b 中的值賦值給 a */ b = c; /* 將 c 中的值賦值給 b */ printf(“交換后: a=%d, b=%dn”, a, b); /* 交換后輸出a和b的值*/ /* End of main function */,三角對換法,48,4. 排序算法,給定一個有n個元素可排序的序列，例如數(shù)字數(shù)據(jù)或字符串?dāng)?shù)據(jù)等，要求按照升序或降序方式重新排列。,排序算法：如冒泡排序法、選擇排序法、插入排序法、合并排序法、快速排序法等等排序算法。,49,蠻力法中的選擇排序法,按照降序方式排序的選擇排序算法：,Sel

28、ectionSort（ Array 0.n-1 ） /* 本算法用選擇排序法對給定數(shù)組按照降序方式排序 */ /* Array0.n-1 是有n個元素的可排序數(shù)組 */ /* 本算法的結(jié)果在Array數(shù)組中 */ for i 0 to n-2 do max i for j i+1 to n-1 do if Array j Array max max j swap Array i and Array max ,50,選擇排序法的 C 程序,/* SelectionSort( Array 0.n-1 )選擇排序算法的 C 源程序 */ void SelectionSort( int n, int

29、Array ) int i, j, max, t; /* 定義4個整型變量 */ for( i=0; i Arraymax ) max = j; /* 記錄大數(shù)元素的下標(biāo)位置 */ /* 利用 t 變量做三角對換 */ t = Arrayi, Arrayi=Arraymax, Arraymax=t; /* End of SelectionSort function */,51,選擇排序法降序方式排序操作過程,例如：對序列89，29，68，90，17，34，45操作。,| 89 29 68 90 17 34 45 90 | 29 68 89 17 34 45 90 89 | 68 29 17 3

30、4 45 90 89 68 | 29 17 34 45 90 89 68 45 | 17 34 29 90 89 68 45 34 | 17 29 90 89 68 45 34 29 | 17,每行表示該算法的一次迭代，即從尾部到豎線的一遍掃描；找到的最大元素用黑體字表示，豎線左邊元素已經(jīng)位于它們的最終位置，所以在當(dāng)前和以后的循環(huán)中，都不必再操作了。排序操作過程如下：,52,插入排序的基本思想,每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。,初始狀態(tài)： 5 4 10 20 12 3,排序,53,在插入排序過程中，由于尋找插入位置的方法不同又可以

31、分為不同的插入排序法，這里只介紹最簡單的直接插入排序法。,直接插入排序,排序,將姓名列表用偽代碼表達的插入排序算法: procedure Sort(list) N2; while(N的值不超過列表的長度）do (把列表的第N項作為主元項； 把主元項移到一個臨時位置使該列表留出一個空位置； while(如果這個空位置上面存在一個名字并且那個名字比主元大) do (把這個名字向下移到空位置上使該名字上面留出一個空位置) 把主元項插到列表的空位置上； NN+1 ),54,直接插入排序函數(shù)模板,/用直接插入排序法對數(shù)組A中的元素進行升序排列 template /9-11.h 源10-1.h void

32、InsertionSort(T A , int n) int i, j; T temp; for(i=1; i 0 / 插入位置已找到，立即插入。 ,直接插入排序,55,應(yīng)用直接插入排序函數(shù)模板排序,/9-11.cpp 源10-1.cpp #include 10-1.h void main( ) int i, data = 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 ; const int Max=10; cout 排序前的原始數(shù)據(jù)： endl; for(i=0; iMax; i+) cout datai ; cout endl; cout “開始以直接插入排序。 endl;

33、InsertionSort(data, Max); cout “直接插入排序結(jié)果： endl; for(i=0; iMax; i+) cout datai ; cout endl; ,直接插入排序,/9_11.cpp,56,選擇排序的基本思想,每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次選擇后，將選出的那個記錄與第 i 個記錄做交換。,排序,57,直接選擇排序,在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是

34、通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。,排序,58,直接選擇排序函數(shù)模板,template void Swap(T ,直接選擇排序,template /9-12.h void SelectionSort(T A , int n) int smallIndex; /每一次選出的最小元素之下標(biāo) int i, j; for (i = 0; i n-1; i+) smallIndex = i; / 在元素Ai+1An-1中逐個比較顯出最小值 for (j = i+1; j n; j+) if (Aj AsmallIndex) smallIndex = j; Swap(Ai, Asm

35、allIndex); ,59,應(yīng)用直接選擇排序函數(shù)模板排序,/9-12.cpp #include 10-2.h void main( ) int i, data = 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 ; const int Max=10; cout 排序前的原始數(shù)據(jù)： endl; for(i=0; iMax; i+) cout datai ; cout endl; cout 開始以直接選擇排序。 endl; SelectionSort(data, Max); cout 直接選擇排序結(jié)果： endl; for(i=0; iMax; i+) cout datai ; co

36、ut endl; ,直接選擇排序,/9_12.cpp,60,交換排序的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。最簡單的交換排序方法是起泡排序。,排序,61,對具有n個元素的序列按升序進行起泡排序的步驟：,首先將第1個元素與第2個元素進行比較，若為逆序，則將兩元素交換。然后比較第2、第3個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟起泡排序，最大的元素便被交換到第n個位置。 對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排

37、序完畢。對n個元素的序列，起泡排序最多需要進行n-1趟。,起泡排序,62,起泡排序過程示意圖,對整數(shù)序列 8 5 2 4 3 按升序排序,起泡排序,8 5 2 4 3,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始狀態(tài),第一趟結(jié)果,第二趟結(jié)果,第三趟結(jié)果,第四趟結(jié)果,小的逐漸上升,每趟沉下一個最大的,63,起泡排序函數(shù)模板,/ 用起泡法對數(shù)組A的n個元素進行排序 template /9-13.h void BubbleSort(T A, int n) int i,j; int lastExchangeIndex; /用于記錄每趟被交換的最后一對元素中較小的

38、下標(biāo) i = n-1; / i是下一趟需參與排序交換的元素之最大下標(biāo) while (i 0) /持續(xù)排序過程，直到最后一趟排序沒有交換發(fā)生，或已達n-1趟 lastExchangeIndex = 0; /每一趟開始時，設(shè)置交換標(biāo)志為0（未交換） for(j = 0; j i; j+) /每一趟對元素A0Ai進行比較和交換 if (Aj+1 Aj) /如果元素Aj+1 Aj，交換之 Swap(Aj, Aj+1); lastExchangeIndex = j; /記錄被交換的一對元素中較小的下標(biāo) i = lastExchangeIndex; / 將i設(shè)置為本趟被交換的最后一對元素中較小的下標(biāo) ,起

39、泡排序,64,應(yīng)用起泡排序函數(shù)模板排序,/9-13.cpp #include 10-3.h void main( ) int i, data = 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 ; const int Max=10; cout 排序前的原始數(shù)據(jù)： endl; for(i=0; iMax; i+) cout datai ; cout endl; cout 開始以起泡排序。 endl; BubbleSort(data, Max); cout 起泡排序結(jié)果： endl; for(i=0; iMax; i+) cout datai ; cout endl; ,起泡排序,/9

40、_13.cpp,65,順序查找基本思想,從數(shù)組的首元素開始，逐個元素與待查找的關(guān)鍵字進行比較，直到找到相等的。若整個數(shù)組中沒有與待查找關(guān)鍵字相等的元素，就是查找不成功。,查找,66,順序查找函數(shù)模板,#ifndef SEARCH_METHODS /9-14.h #define SEARCH_METHODS /用順序查找法在數(shù)組 list 中查找值為key的元素 /若找到，返回該元素下標(biāo)，否則返回-1 template int SeqSearch(T list , int n, T key) for(int i=0; i n; i+) if (listi = key) return i; ret

41、urn -1; #endif / SEARCH_METHODS,查找,67,用偽代碼表達的順序搜索算法,procedure Search(List, TargetValue) if( List 空) then (宣布查找失敗) else (選擇列表中的第一個表項作為TestEntry; while( TargetValue TestEntry 并且還有表項沒有檢查) （選擇列表中下一個表項作為TestEntry ）； if (TargetValue = TestEntry ) then (宣布查找成功) else (宣布查找失敗) ) end if,順序搜索是以一種循環(huán)的方式重復(fù)執(zhí)行一個過程。

42、,List：空列表 或 升序列表,68,折半查找的基本思想,如果是在一個元素排列有序的數(shù)組中進行查找，可采用折半查找方法。 對已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。,查找,69,折半查找過程示意圖,用折半查找法，在下列序列中查找值為21的元素：,M=(L+H)/2=3,L=M+1=4,21=listM,Low L Mid M HighH,21listM,M=(L+H)/2=4,21listM,查找,70,折半查找函數(shù)模板,/ 用折半查找方法，在元素呈升序排列的數(shù)組l

43、ist中查找值為key的元素 template /9-15.h int BinSearch(T list , int n, T key) int mid, low=0, high=n-1; T midvalue; while(low = high) / low = high 表示整個數(shù)組尚未查找完 mid = (low+high) / 2; / 求中間元素的下標(biāo) midvalue = listmid; / 取出中間元素的值 if(key = midvalue) return mid; / 若找到,返回下標(biāo) else if( key midvalue ) high = mid-1; /若keym

44、idvalue將查找范圍縮小到數(shù)組的前一半 else low = mid+1; /否則將查找范圍縮小到數(shù)組的后一半 return -1; / 沒有找到返回-1 ,折半查找,71,用偽代碼表達的二分搜索算法,procedure Search(List, TargetValue) if( List 空) then (報告查找失敗) else 選擇列表的中間項作為TestEntry; 執(zhí)行以下與條件相符case指令塊 case 1: TargetValue = TestEntry （報告查找成功） case 2: TargetValue TestEntry (應(yīng)用Search過程查看TargetVa

45、lue是否在List中位于TestEntry 項之后的部分，并報告查找結(jié)果) end if,二分搜索是把每一階段重復(fù)當(dāng)作前一階段的子任務(wù)，該技術(shù)被稱作遞歸（recursion）,72,算法的有效性和準(zhǔn)確性,盡管當(dāng)今的計算機每秒可以處理數(shù)百萬條指令，有效性仍舊是算法設(shè)計中所關(guān)注的一個主要問題。通常，在效率高低的兩個算法之間的選擇能夠產(chǎn)生對于問題的實用或者不實用的兩種解。 例如：一個大學(xué)的教務(wù)主任需要面對檢索和更新學(xué)生記錄的任務(wù)。假設(shè)：給定一個學(xué)生的學(xué)號（目標(biāo)值），要在“當(dāng)前學(xué)生”文件（包括3萬多條學(xué)生記錄）中找到。,73,算法的有效性和準(zhǔn)確性（續(xù)）,使用順序搜索算法：不能推斷究竟要查找多少條記錄

46、才能得到結(jié)果?？梢约俣ㄔ诙啻尾檎抑?，認為平均查找深度是表的一半長度。所以估計平均每次大概需要尋找15000條記錄。 10ms/一條記錄 則： 150s 1ms/一條記錄 則： 15s 結(jié)論：無法容忍。 使用二分搜索算法：通過比較目標(biāo)值和表的中間項來進行查找。如果不是期望的記錄，則至少將查找限制在原始表的一半。因此,30000、15000、7500、3750最多15次之后，目標(biāo)值應(yīng)該被找到。 10ms/一條記錄 則： 0.15s 結(jié)論：瞬間完成。,74,算法的有效性和準(zhǔn)確性（續(xù)）,總結(jié)：使用搜索方法的選擇將對該應(yīng)用產(chǎn)生了巨大影響。該例子表現(xiàn)了計算機科學(xué)領(lǐng)域中對大家熟知的算法分析的重要性，這種分

47、析包含了對于資源的研究，比如算法需要消耗的時間或者存儲空間資源。這種研究的一個主要應(yīng)用在于給出了二選一算法之間不同優(yōu)點的評估。 算法分析通常包括最優(yōu)情況分析、最差情況分析和平均情況分析。 不能關(guān)注于表的特定長度，而是要嘗試列出某種可以表示任何長度的表中進行查找的算法的性能公式。 具體而言，當(dāng)需要在長度為n 的表中應(yīng)用時： 順序搜索算法的平均查找長度是n/2。 二分搜索算法在最差情況下的查找長度不超過lgn （ lgn表示以2為底n的對數(shù) ）,75,插入排序算法的最差情況分析圖,執(zhí)行算法所需要的時間,列表的長度,增加列表長度時時間的長度,列表長度均勻增長,長度為n 的列表中進行最多需要 次比較。

48、,76,二分搜索法的最差情況分析圖,執(zhí)行算法所需要的時間,列表的長度,增加列表長度時時間的長度,列表長度均勻增長,在長度為n 的列表中進行查找的時候最多需要查詢lgn項。,77,查找算法,查找是指從給定的集合（或者是多重集，它允許幾個元素具有相同的值）中查找一個給定的值（稱為查找鍵 K）。,常用的查找算法有順序查找和折半查找，還有那些將原來的集合表示為另一種形式以方便查找的算法等等。 順序查找直接從頭到尾搜索集合的查找鍵。 折半查找必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合的查找鍵，所以，當(dāng)集合是有序的時候，使用折半查找效率高、速度快。,78,判定哪一種算法是最佳方案,針對排序

49、和查找方面的算法更多，例如，采用分治法、減治法、變治法等等方法中的各種排序和查找算法。,運用經(jīng)典的算法設(shè)計技術(shù)時空權(quán)衡、動態(tài)規(guī)劃、貪婪技術(shù)等；算法能力的極限中的決策樹技術(shù)、在多項式的時間內(nèi)求解、數(shù)值分析，超越算法能力的極限中的回溯發(fā)、分支界限法和近似算法設(shè)計技術(shù)。,技術(shù)和思維方式都是不可或缺的,鞭策學(xué)習(xí)和掌握程序設(shè)計中的算法設(shè)計與分析技術(shù),托馬斯愛迪生（1847-1931）的名言：“不斷關(guān)注那些已被他人成功應(yīng)用的新思路。你的原創(chuàng)思想只應(yīng)該應(yīng)用在那些你正在研究的問題上”。,79,5.3 程序設(shè)計步驟與程序設(shè)計方法,5.3.1 程序設(shè)計步驟 5.3.2 程序設(shè)計方法,80,5.3.1程序設(shè)計步驟,

50、一般程序設(shè)計應(yīng)該包含以下4個步驟：,（1）針對具體問題進行分析了解問題性質(zhì)，明確問題解決所達目標(biāo)，提供的輸入是什么？最終實現(xiàn)的輸出是什么？執(zhí)行中要做什么？怎么做？并建立相應(yīng)的數(shù)學(xué)模型。 （2）確定數(shù)據(jù)結(jié)構(gòu)并設(shè)計相應(yīng)的算法對具體問題進行概念抽象，構(gòu)造出解決問題的輪廓，設(shè)計程序的數(shù)據(jù)結(jié)構(gòu)和算法。 （3）編寫實現(xiàn)算法的程序根據(jù)算法確定解決問題的詳細步驟，通常是通過繪制程序流程圖，來描述問題處理的過程；然后按照流程圖的描述選用某種程序設(shè)計語言編寫程序。 （4）測試與調(diào)試程序在程序設(shè)計過程中，經(jīng)常不是那么一帆風(fēng)順的，尤其是初學(xué)者會遇到各種這樣或那樣的問題，還有一些問題可能是不可預(yù)測的，往往不得不返到上一

51、步驟中更改或調(diào)整相應(yīng)的內(nèi)容，并將相應(yīng)文檔也一并修改，通過舉一反三的方法來解決給定問題。,81,測試程序與調(diào)試程序,測試程序,為了發(fā)現(xiàn)程序中的設(shè)計錯誤而運行程序 。 所使用的測試用例尤其重要，因為不僅需要合法值域用例，而且非法值域用例也是必須的。 程序測試的成功與否直接可以體現(xiàn)程序健壯性。 當(dāng)軟件項目是由團隊開發(fā)時，測試程序可分為：單元測試、組裝測試和確認測試。 調(diào)試程序 錯誤定位和糾錯的過程，這一過程的快慢與程序設(shè)計人員的編程經(jīng)歷和經(jīng)驗是密切相關(guān)的 。,82,高級語言編寫和運行過程,83,5.3.2程序設(shè)計方法,早期的程序設(shè)計方法 結(jié)構(gòu)化程序設(shè)計方法 面向?qū)ο蟪绦蛟O(shè)計方法,84,1.早期的程序

52、設(shè)計方法,早期的程序設(shè)計方法追求程序的高效率，編程過份依賴技巧，忽視程序清晰，而不注重所編寫程序的結(jié)構(gòu)，很少考慮程序的規(guī)范化問題，也就是沒有固定程序設(shè)計方法的時期。,程序的可讀性、可重用性都很差。其中典型問題是：頻繁使用goto語句，特意算計如何節(jié)省內(nèi)存空間。 雖然這些方法存在很多問題，但當(dāng)時受限于計算機運行速度慢、內(nèi)存容量小、硬件價格昂貴，程序的規(guī)模也比較小，對于單人完成較為簡單的任務(wù)，事實上這些方法還是經(jīng)常被采用的。,85,2.結(jié)構(gòu)化程序設(shè)計方法,結(jié)構(gòu)化程序設(shè)計方法出現(xiàn)在70年代中期。,隨著計算機硬件成本急劇下降，軟件需要處理的復(fù)雜問題也就越來越多。 為了擺脫6070年代初的軟件危機，因為

53、當(dāng)時編程無章可循，程序常常帶有強烈的個人色彩，程序的可讀性差，程序的調(diào)試和維護更困難，促使人們認真反省和研究程序設(shè)計中一系列根本性問題：,程序的基本結(jié)構(gòu)是什么？ 程序設(shè)計應(yīng)當(dāng)采用什么方法？ 算法設(shè)計先于程序編碼？ 清晰第一，效率第二？ 程序設(shè)計技術(shù)與方法如何規(guī)范化和工程化？,解決手工作坊式軟件開發(fā)的弊端,86,結(jié)構(gòu)化程序設(shè)計方法的特點,使得程序?qū)哟畏置?、邏輯清晰、功能獨立，簡化了開發(fā)程序的復(fù)雜性，增加了程序的可靠性，能夠充分發(fā)揚團隊精神快速而高效地完成項目開發(fā)，增強系統(tǒng)的可維護性，使程序設(shè)計更加規(guī)范化。,結(jié)構(gòu)化程序設(shè)計方法的特點： 自頂向下、逐步求精 劃分功能模塊 結(jié)構(gòu)化編程,87,3.面向?qū)?/p>

54、象程序設(shè)計方法,面向?qū)ο蟪绦蛟O(shè)計方法出現(xiàn)在80年代中后期。,隨著計算機硬件技術(shù)的高速發(fā)展，計算機的性能也越來越強，用途也更加廣泛。軟件產(chǎn)業(yè)所面臨的問題需求不斷擴大，程序也就越來越龐大而復(fù)雜。 在面向過程的程序設(shè)計中軟件設(shè)計的主要工作就是用不同的功能模塊分別描述它們的求解過程。 在結(jié)構(gòu)化程序設(shè)計中數(shù)據(jù)和處理數(shù)據(jù)的過程分離為相互獨立的實體，它只是封裝了各個功能模塊，而每個功能模塊可以隨意修改未加封裝的數(shù)據(jù)。 新時期的新問題，以及軟件產(chǎn)業(yè)的更高要求，迫使人們再次尋求更加科學(xué)、更加先進的程序設(shè)計方法。,88,面向?qū)ο蟪绦蛟O(shè)計（ OOP ）,Object-Oriented Programming 是建立

55、在結(jié)構(gòu)化程序設(shè)計基礎(chǔ)上的，但它不再是從功能入手，而是從對象入手。,采用的是一種結(jié)構(gòu)模擬的方法。用“類”描述具有相同屬性特征的一組對象，用“封裝”將對象的屬性和行為分別用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來描述，并將它們綁定在一起形成一個可供訪問的基本邏輯單元，利用“繼承”實現(xiàn)類與類之間的數(shù)據(jù)和方法的共享。,89,面向?qū)ο蟪绦蛟O(shè)計的重要概念,面向?qū)ο蟪绦蛟O(shè)計的重要概念： 對象（Object） 類（Class） 消息（Message） 方法（Method）,90,對象（Object）,面向?qū)ο蟪绦蛟O(shè)計中的對象現(xiàn)實世界中的客體在應(yīng)用程序中的具體體現(xiàn)，其中封裝了客體的屬性信息和行為方式，并用數(shù)據(jù)表示屬性，用方法表示

56、行為方式。,對象中的數(shù)據(jù)記錄了客體的屬性狀態(tài)，方法決定了客體所能夠?qū)嵤┑牟僮餍袨楹团c其它對象進行通信的接口方式。 對象并非孤立存在，消息傳遞是對象之間相互聯(lián)系的唯一途徑，發(fā)送者發(fā)送消息，接收者通過調(diào)用相應(yīng)的方法響應(yīng)消息，這個過程被不斷地重復(fù)，從而驅(qū)動整個程序的運轉(zhuǎn)。,91,類（Class）,人類在認知客觀世界時，將眾多的事物歸納、劃分成一些類，這是經(jīng)常采用的思維方法。分類所依據(jù)的原則是抽象。,類是具有相同屬性和行為方式的一組對象的集合，或者說，類是指對一組具有相同特征（包括屬性、操作、方法、關(guān)系、行為）的對象的抽象描述，任何對象都是某個類的實例。 對象是系統(tǒng)運行時將類作為生成對象實例的模板，通

57、過分配私有存儲空間，然后對相應(yīng)的屬性賦初始值而創(chuàng)建的，這個過程在面向?qū)ο蟪绦蛟O(shè)計中稱為“實例化”。 類與對象的關(guān)系猶如模具與鑄件之間的關(guān)系。,92,消息（Message）,消息一個對象要求另一個對象實施某項操作的請求。,在一條消息中，需要包含消息的接收者和要求接收者執(zhí)行某項操作的請求，但具體的操作過程由接收者自行決定，這樣可以很好地保證系統(tǒng)的模塊性。 消息傳遞是對象之間相互聯(lián)系的唯一途徑。發(fā)送者發(fā)送消息，接收者通過調(diào)用相應(yīng)的方法響應(yīng)消息，這個過程被不斷地重復(fù)，從而驅(qū)動整個程序的運轉(zhuǎn)。,93,方法（Method）,面向?qū)ο蠹夹g(shù)中的方法針對對象的屬性的各種操作。,將一些通用的過程或函數(shù)編寫好并封裝

58、起來，作為方法直接提供給用戶調(diào)用。,94,面向?qū)ο蟪绦蛟O(shè)計幾個重要的基本特征,面向?qū)ο蟪绦蛟O(shè)計幾個重要的基本特征： 抽象（Abstract） 封裝（Encapsulation） 繼承（Inheritance） 多態(tài)（Polymorphism）,95,抽象（Abstract）,抽象忽略事物的非本質(zhì)特征，只注意那些與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而找出事物的共性，把具有共同性質(zhì)的事物劃分為一類，得出一個抽象的概念。,在理解復(fù)雜的現(xiàn)實世界和解決復(fù)雜的特定問題時，如何從繁雜的信息集中抽取出有用的、能夠反映事物本質(zhì)的東西，降低其復(fù)雜程度是解決問題的關(guān)鍵，而抽象正是降低復(fù)雜度的最佳途徑。 抽象可分為過程抽象和數(shù)據(jù)抽象 過程抽象即功能抽象，舍棄個別功能，抽取共同擁有的功能。 數(shù)據(jù)抽象一種更高級別的抽象，它將現(xiàn)實世界中存在的客體作為抽象單元，其抽象內(nèi)容既包括客體的屬性特征，也包括行為特征（起到信息隱藏的作用）。它是面向?qū)ο蟪绦蛟O(shè)