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ā),目標 了解基本解決問題的技巧 能夠發(fā)展出完整的從上到下，可進行逐步細部修改過程的演算法 能夠使用選擇敘述式if, if/else 來選擇要執(zhí)行的動作 能夠使用 while重複結(jié)構(gòu)，來重複執(zhí)行一些敘述式 了解計數(shù)器控制結(jié)構(gòu)和旗標 (警示)訊號控制結(jié)構(gòu) 能夠使用遞增、遞減、指定和邏輯運算子,3,Chapter 3 結(jié)構(gòu)化程式的開發(fā),大綱 3.1 簡介 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ī)劃：範例研究一 (計數(shù)器控制迴圈 Counter-Controlled Repetition) 3.9 從上到下，逐步細部修改的演算法規(guī)劃：範例研究二 (旗標訊號控制迴圈 Sentinel-Controlled Repetition) 3.10 從上到下，逐步細部修改的演算法規(guī)劃：範例研究三 (巢狀控制結(jié)構(gòu) Nested Control Structures) 3.11 指定運算子 3.12 遞增和遞減運算子,4,3.1 簡介,在寫程式之前： 對問題有個通盤的了解 仔細規(guī)劃解決此問題的方式 開始寫程式時： 需要知道有哪些程式區(qū)段可以使用 要使用好的程式設(shè)計觀念,5,3.2 Algorithms 演算法,所有的計算問題 可藉由執(zhí)行一系列經(jīng)特定安排的動作加以解決。 解決問題的程序即所謂的 Algorithm 演算法 包括： 將要作的動作) 這些動作的執(zhí)行順序 Program control 程式 控制 指定程式中敘述式的執(zhí)行順序,起床、脫掉睡衣、洗澡、穿衣服、吃早餐、開車上班,起床、脫掉睡衣、穿衣服、洗澡、吃早餐、開車上班,6,3.3 Pseudocode 虛擬碼,Pseudocode(虛擬碼) 是給人看的、非正規(guī)的語言，主要功用是發(fā)展演算法 類似日常用的英文 並不能在電腦上實際執(zhí)行 其功用是幫助程式設(shè)計者在寫程式之前，先想出程式該怎麼寫。 (這是演算法、虛擬碼的目的) 可以很容易地轉(zhuǎn)換為相對的 C 程式 只由可以執(zhí)行的敘述式組成 (不包含變數(shù)宣告),7,3.4 Control Structures 控制結(jié)構(gòu),Sequential execution 循序式執(zhí)行 敘述式按順序從上到下執(zhí)行。 Transfer of control 控制權(quán)轉(zhuǎn)移 接下來要執(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 流程圖 用圖形來表示演算法 用一些特殊涵義的圖示(如：矩形、菱形、橢圓、小圓圈)表示所要執(zhí)行的動作、用箭號連接。 矩形表示動作(任何型態(tài)的動作，包括輸入、輸出) 橢圓形表示程式的開始與結(jié)束 小圓圈表示一段程式的開始與結(jié)束 單一入口/單一出口 的控制結(jié)構(gòu) 將一個控制結(jié)構(gòu)的出口點接到下個控制結(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) 選取不同功能的動作 虛擬碼的例子： If students grade is greater than or equal to 60 Print “Passed” 若條件為 true print 敘述式會被執(zhí)行，之後再執(zhí)行下個敘述。 若條件為 false print 敘述式會被忽略，直接執(zhí)行下個敘述。 縮排比較容易閱讀 C 的編譯器會忽略空白字元(whitespace characters)，包括：空白、定位(tab)、新行(newline)等字元。,11,3.5 if 選擇結(jié)構(gòu),將虛擬碼轉(zhuǎn)換為 C 敘述: if ( grade = 60 ) printf(“Passedn“); 菱形符號 (decision symbol) 表示要作決定 包含要作判斷的運算式(條件) 測試條件是否成立、執(zhí)行適當?shù)臄⑹?if 結(jié)構(gòu)是單一入口/單一出口的結(jié)構(gòu) C 語言中的條件是否成立：以運算式結(jié)果為 0 的話就代表不成立(偽)，否則就成立(真)。,12,3.5 if 選擇結(jié)構(gòu),前面虛擬碼的流程圖,良好的程式設(shè)計習慣 3.1-3.2 在程式中採用前後一致的縮排方式，可以大幅增加程式的可讀性。建議用固定大小的內(nèi)縮量( 英吋或3格) 虛擬碼在程式設(shè)計階段常用來想出程式的架構(gòu)。然後再將虛擬碼的程式轉(zhuǎn)換成 C 程式碼。,13,3.6 if/else 選擇結(jié)構(gòu),if 只有當條件成立時才執(zhí)行某個動作 if/else 當條件成立執(zhí)行一個動作，條件不成立執(zhí)行另一個動作 (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),三元條件運算子 (?:) 有三個引數(shù)、運算元 (條件, 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 放在另一個 if/else 選擇結(jié)構(gòu)中，可以測試多種狀況，達到多選一的效果 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” 只要一個條件成立、其餘的都被跳過,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(複合敘述式) 將好幾個敘述用大括號包起來，成為一個複合敘述式 例如：: if ( grade = 60 ) printf( “Passed.n” ); else / 要記得加括號 printf( “Failed.n“ ); printf( “You must take this course again.n“ ); 如果沒有加大括號的話 printf( “You must take this course again.n“ ); 就一定會被執(zhí)行。 Block 複合敘述式加上變數(shù)宣告,19,3.6 if/else 選擇結(jié)構(gòu),Syntax errors / 語法錯誤，compiler 看不懂。 由編譯器引起的錯誤 Logic errors /邏輯錯誤，執(zhí)行結(jié)果有錯誤 Errors which have their effect at execution time Non-fatal logic errors /非致命錯誤，可執(zhí)行完，結(jié)果錯誤 program runs, but has incorrect output Fatal logic errors /致命錯誤，執(zhí)行到一半被強迫停止。 program exits prematurely,20,良好的程式設(shè)計習慣 3.3-3.4 將 if/else 結(jié)構(gòu)的兩個本體敘述式都予以縮排處理 如果需要安排好幾層的縮排，每層都用相同的縮排量 軟體工程的觀點 3.1 複合敘述式(compound statement) 可以放在任何單行敘述式可出現(xiàn)的地方。,21,常見的程式設(shè)計錯誤 3.1-3.2 如果忘記加上大括號的任一邊，就無法限制複合敘述式的範圍，就會導致程式出現(xiàn)語法錯誤或者邏輯錯誤。 若在 if 結(jié)構(gòu)的條件式後面多放一個分號，這會讓單選擇的 if 結(jié)構(gòu)產(chǎn)生邏輯錯誤，會讓雙選擇的 if 結(jié)構(gòu)產(chǎn)生語法錯誤(若在 if 的部份包含一個實際的敘述式). 避免錯誤的小技巧 3.1 有些程式設(shè)計者寫程式時，會先將複合敘述的左右大括號一次先打好，可避免遺漏的情形。,22,3.7 while 重複結(jié)構(gòu),重複結(jié)構(gòu) 程式設(shè)計者指定在某條件持續(xù)成立時、重複執(zhí)行某個動作 虛擬碼 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 或是一個 compound statment,product 最後變成 1024 才結(jié)束。,23,3.7 while 重複結(jié)構(gòu),while 迴圈的流程圖,常見的程式設(shè)計錯誤 3.3-3.4 若在 while 結(jié)構(gòu)的本體裡面沒提供最後會造成 while 條件變成 false 的動作，這一般會產(chǎn)無窮迴圈的錯誤，也就是重複結(jié)構(gòu)永遠不會終止。 若將關(guān)鍵字 while 拼成大寫字母的 While(記得 C 是大小寫有別的語言)，就是語法錯誤。所有 C 的關(guān)鍵字都只包含小寫字母，例如： while, if 和 else。,24,3.8 演算法的規(guī)劃：範例研究一 (計數(shù)器控制迴圈 Counter-Controlled Repetition),Counter-controlled repetition 計數(shù)控制重複結(jié)構(gòu) 迴圈重複執(zhí)行到計數(shù)器達到特定值為止 Definite repetition 明確的重複 重複次數(shù)事先知道 例如: 十個人的班級舉行小考，輸入每個人的分數(shù)(0-100的整數(shù))，請計算這次小考的平均分數(shù)。,25,3.8 Formulating Algorithms (Counter-Controlled Repetition),此範例的虛擬碼 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 下面是此範例的 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。,常見的程式錯誤 3.5 若 counter 或 total 沒有作初始化，你程式的結(jié)果很可能不正確，這是邏輯錯誤。,28,3.9 利用從上到下，逐步細部修改的演算法規(guī)劃：範例研究二（警示訊號控制迴圈),讓我們將前面的問題一般化 Develop a class-averaging program that will process an arbitrary number of grades each time the program is run. 寫一個計算全班平均分數(shù)的程式，班級的人數(shù)可以任意 不知道學生人數(shù) 如何知道程式何時要停止？ Sentinel value(警示值) 指出資料結(jié)束 當警示值被輸入時，迴圈也必須結(jié)束 選擇一個適當?shù)闹诞斁局?，警示值必須與正常的資料不同（這例子中可以用 1 當警示值）,29,3.9 利用從上到下，逐步細部修改的演算法規(guī)劃：範例研究二（警示訊號控制迴圈),從上到下、逐步細部修改(Top-down, stepwise refinement) 一開始只用單獨一行敘述如下： Determine the class average for the quiz(計算小考全班平均分數(shù)) 分成比較小的工作、並按順序?qū)懴聛恚?Initialize variables(初始化變數(shù)) Input, sum and count the quiz grades(輸入、計算人數(shù)、總分) Calculate and print the class average (計算並印出平均分數(shù)),30,3.9 利用從上到下，逐步細部修改的演算法規(guī)劃：範例研究二（警示訊號控制迴圈),很多程式都可以分成三個部份 Initialization 初始化 將程式變數(shù)作初始化 Processing 處理 輸入資料、並適當?shù)卣{(diào)整變數(shù)內(nèi)容 Termination 停止 計算並印出最後結(jié)果 將初始化的步驟分成更小的細節(jié) Initialize variables to Initialize total to zero (total 初始設(shè)為 0) Initialize counter to zero (counter 初始設(shè)為 0),31,3.9 利用從上到下，逐步細部修改的演算法規(guī)劃：範例研究二（警示訊號控制迴圈),改進 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) 改進 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 利用從上到下，逐步細部修改的演算法規(guī)劃：範例研究二（警示訊號控制迴圈),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è)計錯誤 3.63.9 若選取的警示值也是合法的資料數(shù)值，就是邏輯錯誤。 企圖除以 0 時會造成致命錯誤。 使用浮點數(shù)時假設(shè)它是用精確的方式來儲存會造錯誤的結(jié)果，大部份電腦的浮點數(shù)是用近似的方式儲存。,良好的程式設(shè)計習慣 3.5-3.6 執(zhí)行除法時，若除數(shù)（式）的值可能為 0，請以適合的方式明確地先測試這個狀況是否發(fā)生（就可在錯誤發(fā)生時，印出錯誤訊息），而不是任由發(fā)生致命錯誤。 在利用旗標(警示值)訊號控制迴圈的結(jié)構(gòu)中，要求使用者輸入資料的提示，必須明確的提醒使用者規(guī)定的旗標值是多少。,37,避免錯誤的小技巧 3.3 不要比較兩個浮點數(shù)是否相等或不相等，而是比較兩者的差是否小於某個指定的小數(shù)值範圍。,38,3.10 從上到下，逐步細部修改的演算法規(guī)劃：範例研究三 (巢狀控制結(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)高學費). 我們可觀察到： 這個程式必須處理10個測驗結(jié)果，可用計數(shù)控制迴圈 每個測驗結(jié)果都是數(shù)字 不是 1就是 2，若輸入不是 1, 就假設(shè)是 2。 用兩個計數(shù)器 分別計算 passed 與 failed 的人數(shù) 在程式完成所有的考試結(jié)果後，必須判斷是否有8位以上的學生通過考試。 開始分析的虛擬碼： Analyze exam results and decide if tuition should be raised (分析考試結(jié)果並決定學費是否調(diào)漲),39,3.10 從上到下，逐步細部修改的演算法規(guī)劃：範例研究三 (巢狀控制結(jié)構(gòu)),第一次細部修改 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 第二次細部修改 Initialize variables to Initialize passes to zero Initialize failures to zero Initialize student counter to one,40,3.10 從上到下，逐步細部修改的演算法規(guī)劃：範例研究三 (巢狀控制結(jié)構(gòu)),第二次細部修改 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 第二次細部修改 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 從上到下，逐步細部修改的演算法規(guī)劃：範例研究三 (巢狀控制結(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,增進效能的小技巧 3.1 在變數(shù)宣告時順便初始化，可以避免忘記作初始化所帶來的問題。 軟體工程的觀點 3.73.8 經(jīng)驗顯示利用電腦解決問題最困難的地方是，如何設(shè)計出該問題的演算法，一旦演算法想出來，就可以從演算法直接導出可執(zhí)行的 C 程式。 很多有經(jīng)驗的程式設(shè)計者寫程式時都不用虛擬碼，他們認為最終目的就是在電腦上解決問題，寫虛擬碼只是浪費時間。這種想法對一些簡單和常見的問題是實情，但是當要寫大型或複雜的系統(tǒng)時，就會導致嚴重的錯誤和時間的耽擱。,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