Chapter3–結(jié)構(gòu)化程式的開發(fā).ppt

1,Computer Programming - C,Andres, Wen-Yuan Liao Department of Computer Science and Engineering De Lin Institute of Technology .tw .tw/andres,2,Chapter 3 結(jié)構(gòu)化程式的開發(fā),目標(biāo) 了解基本解決問題的技巧 能夠發(fā)展出完整的從上到下，可進(jìn)行逐步細(xì)部修改過程的演算法 能夠使用選擇敘述式if, if/else 來(lái)選擇要執(zhí)行的動(dòng)作 能夠使用 while重複結(jié)構(gòu)，來(lái)重複執(zhí)行一些敘述式 了解計(jì)數(shù)器控制結(jié)構(gòu)和旗標(biāo) (警示)訊號(hào)控制結(jié)構(gòu) 能夠使用遞增、遞減、指定和邏輯運(yùn)算子,3,Chapter 3 結(jié)構(gòu)化程式的開發(fā),大綱 3.1 簡(jiǎn)介 3.2 演算法 3.3 虛擬碼 3.4 控制結(jié)構(gòu) 3.5 if 選擇結(jié)構(gòu) 3.6 if/else 選擇結(jié)構(gòu) 3.7 while重複結(jié)構(gòu) 3.8 演算法的規(guī)劃：範(fàn)例研究一 (計(jì)數(shù)器控制迴圈 Counter-Controlled Repetition) 3.9 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二 (旗標(biāo)訊號(hào)控制迴圈 Sentinel-Controlled Repetition) 3.10 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究三 (巢狀控制結(jié)構(gòu) Nested Control Structures) 3.11 指定運(yùn)算子 3.12 遞增和遞減運(yùn)算子,4,3.1 簡(jiǎn)介,在寫程式之前： 對(duì)問題有個(gè)通盤的了解 仔細(xì)規(guī)劃解決此問題的方式 開始寫程式時(shí)： 需要知道有哪些程式區(qū)段可以使用 要使用好的程式設(shè)計(jì)觀念,5,3.2 Algorithms 演算法,所有的計(jì)算問題 可藉由執(zhí)行一系列經(jīng)特定安排的動(dòng)作加以解決。 解決問題的程序即所謂的 Algorithm 演算法 包括： 將要作的動(dòng)作) 這些動(dòng)作的執(zhí)行順序 Program control 程式 控制 指定程式中敘述式的執(zhí)行順序,起床、脫掉睡衣、洗澡、穿衣服、吃早餐、開車上班,起床、脫掉睡衣、穿衣服、洗澡、吃早餐、開車上班,6,3.3 Pseudocode 虛擬碼,Pseudocode(虛擬碼) 是給人看的、非正規(guī)的語(yǔ)言，主要功用是發(fā)展演算法 類似日常用的英文 並不能在電腦上實(shí)際執(zhí)行 其功用是幫助程式設(shè)計(jì)者在寫程式之前，先想出程式該怎麼寫。 (這是演算法、虛擬碼的目的) 可以很容易地轉(zhuǎn)換為相對(duì)的 C 程式 只由可以執(zhí)行的敘述式組成 (不包含變數(shù)宣告),7,3.4 Control Structures 控制結(jié)構(gòu),Sequential execution 循序式執(zhí)行 敘述式按順序從上到下執(zhí)行。 Transfer of control 控制權(quán)轉(zhuǎn)移 接下來(lái)要執(zhí)行的敘述式不按順序 早期控制權(quán)轉(zhuǎn)移的指令是 goto：可轉(zhuǎn)移到(幾乎)任何地方去。 Structured programming goto elimination (消除goto) Bohm 和 Jacopini 證明所有程式都可只用三種控制結(jié)構(gòu)寫 Sequence structure控制結(jié)構(gòu) C 內(nèi)建的執(zhí)行方式 Selection structures 選擇結(jié)構(gòu) C 有三種型態(tài) - if, if/else, 與 switch Repetition structures 重複結(jié)構(gòu) C 有三種型態(tài) - while, do/while, 與 for,8,3.4 Control Structures 控制結(jié)構(gòu),Flowchart 流程圖 用圖形來(lái)表示演算法 用一些特殊涵義的圖示(如：矩形、菱形、橢圓、小圓圈)表示所要執(zhí)行的動(dòng)作、用箭號(hào)連接。 矩形表示動(dòng)作(任何型態(tài)的動(dòng)作，包括輸入、輸出) 橢圓形表示程式的開始與結(jié)束 小圓圈表示一段程式的開始與結(jié)束 單一入口/單一出口 的控制結(jié)構(gòu) 將一個(gè)控制結(jié)構(gòu)的出口點(diǎn)接到下個(gè)控制結(jié)構(gòu)的入口 (堆疊式控制結(jié)構(gòu)). 使程式更容易建立,9,3.4 Control Structures 控制結(jié)構(gòu),C循序結(jié)構(gòu)流程圖,C選擇結(jié)構(gòu)流程圖,10,3.5 if 選擇結(jié)構(gòu),選擇結(jié)構(gòu) 選取不同功能的動(dòng)作 虛擬碼的例子： If students grade is greater than or equal to 60 Print “Passed” 若條件為 true print 敘述式會(huì)被執(zhí)行，之後再執(zhí)行下個(gè)敘述。 若條件為 false print 敘述式會(huì)被忽略，直接執(zhí)行下個(gè)敘述。 縮排比較容易閱讀 C 的編譯器會(huì)忽略空白字元(whitespace characters)，包括：空白、定位(tab)、新行(newline)等字元。,11,3.5 if 選擇結(jié)構(gòu),將虛擬碼轉(zhuǎn)換為 C 敘述: if ( grade = 60 ) printf(“Passedn“); 菱形符號(hào) (decision symbol) 表示要作決定 包含要作判斷的運(yùn)算式(條件) 測(cè)試條件是否成立、執(zhí)行適當(dāng)?shù)臄⑹?if 結(jié)構(gòu)是單一入口/單一出口的結(jié)構(gòu) C 語(yǔ)言中的條件是否成立：以運(yùn)算式結(jié)果為 0 的話就代表不成立(偽)，否則就成立(真)。,12,3.5 if 選擇結(jié)構(gòu),前面虛擬碼的流程圖,良好的程式設(shè)計(jì)習(xí)慣 3.1-3.2 在程式中採(cǎi)用前後一致的縮排方式，可以大幅增加程式的可讀性。建議用固定大小的內(nèi)縮量( 英吋或3格) 虛擬碼在程式設(shè)計(jì)階段常用來(lái)想出程式的架構(gòu)。然後再將虛擬碼的程式轉(zhuǎn)換成 C 程式碼。,13,3.6 if/else 選擇結(jié)構(gòu),if 只有當(dāng)條件成立時(shí)才執(zhí)行某個(gè)動(dòng)作 if/else 當(dāng)條件成立執(zhí)行一個(gè)動(dòng)作，條件不成立執(zhí)行另一個(gè)動(dòng)作 (two-way selection 二選一) 虛擬碼 if students grade is greater than or equal to 60 print “Passed” else print “Failed” C 程式碼 if ( grade = 60 ) printf(“Passedn“); else printf(“Failedn“);,14,3.6 if/else 選擇結(jié)構(gòu),三元條件運(yùn)算子 (?:) 有三個(gè)引數(shù)、運(yùn)算元 (條件, value if true, value if false) 前面的虛擬碼可改寫成： Printf(“%sn”, grade = 60 ? “Passed” : “Failed” );,15,3.6 if/else 選擇結(jié)構(gòu),巢狀 if/else 結(jié)構(gòu) (重疊式) 將 if/else 放在另一個(gè) if/else 選擇結(jié)構(gòu)中，可以測(cè)試多種狀況，達(dá)到多選一的效果 if students grade is greater than or equal to 90 Print “A” else if students grade is greater than or equal to 80 Print “B” else if students grade is greater than or equal to 70 Print “C” else if students grade is greater than or equal to 60 Print “D” else Print “F” 只要一個(gè)條件成立、其餘的都被跳過,P.21,16,3.6 if/else 選擇結(jié)構(gòu),if (grade = 90) printf( “An”); else if (grade = 80) printf( “Bn”); else if (grade = 70) printf( “Cn”); else if (grade = 60) printf( “Dn”); else printf( “Fn”);,17,3.6 if/else 選擇結(jié)構(gòu),if (grade = 90) printf( “An”); else if (grade = 80) printf( “Bn”); else if (grade = 70) printf( “Cn”); else if (grade = 60) printf( “Dn”); else printf( “Fn”);,多選一的寫法。,18,3.6 if/else 選擇結(jié)構(gòu),Compound statement(複合敘述式) 將好幾個(gè)敘述用大括號(hào)包起來(lái)，成為一個(gè)複合敘述式 例如：: if ( grade = 60 ) printf( “Passed.n” ); else / 要記得加括號(hào) printf( “Failed.n“ ); printf( “You must take this course again.n“ ); 如果沒有加大括號(hào)的話 printf( “You must take this course again.n“ ); 就一定會(huì)被執(zhí)行。 Block 複合敘述式加上變數(shù)宣告,19,3.6 if/else 選擇結(jié)構(gòu),Syntax errors / 語(yǔ)法錯(cuò)誤，compiler 看不懂。 由編譯器引起的錯(cuò)誤 Logic errors /邏輯錯(cuò)誤，執(zhí)行結(jié)果有錯(cuò)誤 Errors which have their effect at execution time Non-fatal logic errors /非致命錯(cuò)誤，可執(zhí)行完，結(jié)果錯(cuò)誤 program runs, but has incorrect output Fatal logic errors /致命錯(cuò)誤，執(zhí)行到一半被強(qiáng)迫停止。 program exits prematurely,20,良好的程式設(shè)計(jì)習(xí)慣 3.3-3.4 將 if/else 結(jié)構(gòu)的兩個(gè)本體敘述式都予以縮排處理 如果需要安排好幾層的縮排，每層都用相同的縮排量 軟體工程的觀點(diǎn) 3.1 複合敘述式(compound statement) 可以放在任何單行敘述式可出現(xiàn)的地方。,21,常見的程式設(shè)計(jì)錯(cuò)誤 3.1-3.2 如果忘記加上大括號(hào)的任一邊，就無(wú)法限制複合敘述式的範(fàn)圍，就會(huì)導(dǎo)致程式出現(xiàn)語(yǔ)法錯(cuò)誤或者邏輯錯(cuò)誤。 若在 if 結(jié)構(gòu)的條件式後面多放一個(gè)分號(hào)，這會(huì)讓單選擇的 if 結(jié)構(gòu)產(chǎn)生邏輯錯(cuò)誤，會(huì)讓雙選擇的 if 結(jié)構(gòu)產(chǎn)生語(yǔ)法錯(cuò)誤(若在 if 的部份包含一個(gè)實(shí)際的敘述式). 避免錯(cuò)誤的小技巧 3.1 有些程式設(shè)計(jì)者寫程式時(shí)，會(huì)先將複合敘述的左右大括號(hào)一次先打好，可避免遺漏的情形。,22,3.7 while 重複結(jié)構(gòu),重複結(jié)構(gòu) 程式設(shè)計(jì)者指定在某條件持續(xù)成立時(shí)、重複執(zhí)行某個(gè)動(dòng)作 虛擬碼 while there are more items on my shopping list Purchase next item and cross it off my list while 迴圈一直重複到條件不成立為止 例如： int product = 2; while ( product = 1000 ) product = 2 * product;,while 的 body 可以是單一的 statement 或是一個(gè) compound statment,product 最後變成 1024 才結(jié)束。,23,3.7 while 重複結(jié)構(gòu),while 迴圈的流程圖,常見的程式設(shè)計(jì)錯(cuò)誤 3.3-3.4 若在 while 結(jié)構(gòu)的本體裡面沒提供最後會(huì)造成 while 條件變成 false 的動(dòng)作，這一般會(huì)產(chǎn)無(wú)窮迴圈的錯(cuò)誤，也就是重複結(jié)構(gòu)永遠(yuǎn)不會(huì)終止。 若將關(guān)鍵字 while 拼成大寫字母的 While(記得 C 是大小寫有別的語(yǔ)言)，就是語(yǔ)法錯(cuò)誤。所有 C 的關(guān)鍵字都只包含小寫字母，例如： while, if 和 else。,24,3.8 演算法的規(guī)劃：範(fàn)例研究一 (計(jì)數(shù)器控制迴圈 Counter-Controlled Repetition),Counter-controlled repetition 計(jì)數(shù)控制重複結(jié)構(gòu) 迴圈重複執(zhí)行到計(jì)數(shù)器達(dá)到特定值為止 Definite repetition 明確的重複 重複次數(shù)事先知道 例如: 十個(gè)人的班級(jí)舉行小考，輸入每個(gè)人的分?jǐn)?shù)(0-100的整數(shù))，請(qǐng)計(jì)算這次小考的平均分?jǐn)?shù)。,25,3.8 Formulating Algorithms (Counter-Controlled Repetition),此範(fàn)例的虛擬碼 Set total to zero Set grade counter to one While grade counter is less than or equal to ten Input the next grade Add the grade into the total Add one to the grade counter Set the class average to the total divided by ten Print the class average 下面是此範(fàn)例的 C 程式碼,26,27,Enter grade: 98 Enter grade: 76 Enter grade: 71 Enter grade: 87 Enter grade: 83 Enter grade: 90 Enter grade: 57 Enter grade: 79 Enter grade: 82 Enter grade: 94 Class average is 81,總分是 817，但平均為整數(shù)，所以結(jié)果是 81。,常見的程式錯(cuò)誤 3.5 若 counter 或 total 沒有作初始化，你程式的結(jié)果很可能不正確，這是邏輯錯(cuò)誤。,28,3.9 利用從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二（警示訊號(hào)控制迴圈),讓我們將前面的問題一般化 Develop a class-averaging program that will process an arbitrary number of grades each time the program is run. 寫一個(gè)計(jì)算全班平均分?jǐn)?shù)的程式，班級(jí)的人數(shù)可以任意 不知道學(xué)生人數(shù) 如何知道程式何時(shí)要停止？ Sentinel value(警示值) 指出資料結(jié)束 當(dāng)警示值被輸入時(shí)，迴圈也必須結(jié)束 選擇一個(gè)適當(dāng)?shù)闹诞?dāng)警示值，警示值必須與正常的資料不同（這例子中可以用 1 當(dāng)警示值）,29,3.9 利用從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二（警示訊號(hào)控制迴圈),從上到下、逐步細(xì)部修改(Top-down, stepwise refinement) 一開始只用單獨(dú)一行敘述如下： Determine the class average for the quiz(計(jì)算小考全班平均分?jǐn)?shù)) 分成比較小的工作、並按順序?qū)懴聛?lái)： Initialize variables(初始化變數(shù)) Input, sum and count the quiz grades(輸入、計(jì)算人數(shù)、總分) Calculate and print the class average (計(jì)算並印出平均分?jǐn)?shù)),30,3.9 利用從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二（警示訊號(hào)控制迴圈),很多程式都可以分成三個(gè)部份 Initialization 初始化 將程式變數(shù)作初始化 Processing 處理 輸入資料、並適當(dāng)?shù)卣{(diào)整變數(shù)內(nèi)容 Termination 停止 計(jì)算並印出最後結(jié)果 將初始化的步驟分成更小的細(xì)節(jié) Initialize variables to Initialize total to zero (total 初始設(shè)為 0) Initialize counter to zero (counter 初始設(shè)為 0),31,3.9 利用從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二（警示訊號(hào)控制迴圈),改進(jìn) Input, sum and count the quiz grades to Input the first grade (possibly the sentinel) While the user has not as yet entered the sentinel Add this grade into the running total Add one to the grade counter Input the next grade (possibly the sentinel) 改進(jìn) Calculate and print the class average to If the counter is not equal to zero Set the average to the total divided by the counter Print the average Else Print “No grades were entered”,32,3.9 利用從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究二（警示訊號(hào)控制迴圈),Initialize total to zero Initialize counter to zero Input the first grade While the user has not as yet entered the sentinel Add this grade into the running total Add one to the grade counter Input the next grade (possibly the sentinel) If the counter is not equal to zero Set the average to the total divided by the counter Print the average else Print “No grades were entered”,33,34,35,Enter grade, -1 to end: 75 Enter grade, -1 to end: 94 Enter grade, -1 to end: 97 Enter grade, -1 to end: 88 Enter grade, -1 to end: 70 Enter grade, -1 to end: 64 Enter grade, -1 to end: 83 Enter grade, -1 to end: 89 Enter grade, -1 to end: -1 Class average is 82.50,Enter grade, -1 to end: -1 No grades were entered,36,常見的程式設(shè)計(jì)錯(cuò)誤 3.63.9 若選取的警示值也是合法的資料數(shù)值，就是邏輯錯(cuò)誤。 企圖除以 0 時(shí)會(huì)造成致命錯(cuò)誤。 使用浮點(diǎn)數(shù)時(shí)假設(shè)它是用精確的方式來(lái)儲(chǔ)存會(huì)造錯(cuò)誤的結(jié)果，大部份電腦的浮點(diǎn)數(shù)是用近似的方式儲(chǔ)存。,良好的程式設(shè)計(jì)習(xí)慣 3.5-3.6 執(zhí)行除法時(shí)，若除數(shù)（式）的值可能為 0，請(qǐng)以適合的方式明確地先測(cè)試這個(gè)狀況是否發(fā)生（就可在錯(cuò)誤發(fā)生時(shí)，印出錯(cuò)誤訊息），而不是任由發(fā)生致命錯(cuò)誤。 在利用旗標(biāo)(警示值)訊號(hào)控制迴圈的結(jié)構(gòu)中，要求使用者輸入資料的提示，必須明確的提醒使用者規(guī)定的旗標(biāo)值是多少。,37,避免錯(cuò)誤的小技巧 3.3 不要比較兩個(gè)浮點(diǎn)數(shù)是否相等或不相等，而是比較兩者的差是否小於某個(gè)指定的小數(shù)值範(fàn)圍。,38,3.10 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究三 (巢狀控制結(jié)構(gòu)),問題: A college has a list of test results (1 = pass, 2 = fail) for 10 students. Write a program that analyzes the results. If more than 8 students pass, print “Raise Tuition“(調(diào)高學(xué)費(fèi)). 我們可觀察到： 這個(gè)程式必須處理10個(gè)測(cè)驗(yàn)結(jié)果，可用計(jì)數(shù)控制迴圈 每個(gè)測(cè)驗(yàn)結(jié)果都是數(shù)字 不是 1就是 2，若輸入不是 1, 就假設(shè)是 2。 用兩個(gè)計(jì)數(shù)器 分別計(jì)算 passed 與 failed 的人數(shù) 在程式完成所有的考試結(jié)果後，必須判斷是否有8位以上的學(xué)生通過考試。 開始分析的虛擬碼： Analyze exam results and decide if tuition should be raised (分析考試結(jié)果並決定學(xué)費(fèi)是否調(diào)漲),39,3.10 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究三 (巢狀控制結(jié)構(gòu)),第一次細(xì)部修改 Initialize variables Input the ten quiz grades and count passes and failures Print a summary of the exam results and decide if tuition should be raised 第二次細(xì)部修改 Initialize variables to Initialize passes to zero Initialize failures to zero Initialize student counter to one,40,3.10 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究三 (巢狀控制結(jié)構(gòu)),第二次細(xì)部修改 Input the ten quiz grades and count passes and failures to While student counter is less than or equal to ten Input the next exam result If the student passed Add one to passes Else Add one to failures Add one to student counter 第二次細(xì)部修改 Print a summary of the exam results and decide if tuition should be raised to Print the number of passes Print the number of failures If more than eight students passed Print “Raise tuition”,41,3.10 從上到下，逐步細(xì)部修改的演算法規(guī)劃：範(fàn)例研究三 (巢狀控制結(jié)構(gòu)),Initialize passes to zero Initialize failures to zero Initialize student to one While student counter is less than or equal to ten Input the next exam result If the student passed Add one to passes else Add one to failures Add one to student counter Print the number of passes Print the number of failures If more than eight students passed Print “Raise tuition”,42,增進(jìn)效能的小技巧 3.1 在變數(shù)宣告時(shí)順便初始化，可以避免忘記作初始化所帶來(lái)的問題。 軟體工程的觀點(diǎn) 3.73.8 經(jīng)驗(yàn)顯示利用電腦解決問題最困難的地方是，如何設(shè)計(jì)出該問題的演算法，一旦演算法想出來(lái)，就可以從演算法直接導(dǎo)出可執(zhí)行的 C 程式。 很多有經(jīng)驗(yàn)的程式設(shè)計(jì)者寫程式時(shí)都不用虛擬碼，他們認(rèn)為最終目的就是在電腦上解決問題，寫虛擬碼只是浪費(fèi)時(shí)間。這種想法對(duì)一些簡(jiǎn)單和常見的問題是實(shí)情，但是當(dāng)要寫大型或複雜的系統(tǒng)時(shí)，就會(huì)導(dǎo)致嚴(yán)重的錯(cuò)誤和時(shí)間的耽擱。,43,44,45,Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Passed 6 Failed 4,Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 1 Passed 9 Failed 1 Raise tuition,46,3.11 Assignment Operators,Assignment operators abbreviate assignment expressions c = c + 3; can be abbreviated as c += 3; using the addition assignment operator Statements of th