Bài giảng Kỹ thuật lập trình: Lập trình cấu trúc

0KỸ THUẬT LẬP TRÌNH LẬP TRÌNH CẤU TRÚC (structured programming) NỘI DUNG: ƒ Khái niệm lập trình cấu trúc ƒ So sánh với lập trình hướng đối tượng ƒ Cấu trúc lệnh. Lệnh có cấu trúc ƒ Kỹ thuật sử dụng cấu trúc lệnh (cấu trúc điều khiển) trong ngôn ngữ C. 1 Khái niệm lập trình cấu trúc ƒ Nguyên lý chủ đạo trong công nghệ phần mềm ƒ Phân rã bài toán thành những bài toán nhỏ hơn để triển khai và đảm bảo tính đúng đắn của chương trình ƒ Nguyên lý cơ bản của lập trình cấu trúc bao gồm: • Phát triển chương trình từ trên xuống (Top−down development) • Thiết kế môđun (Modular design) 2 ƒ Phương pháp đi từ trên xuống: • Đi từ cái chung đến cái riêng, từ kết luận đến chi tiết, từ tổng thể đến đơn vị ƒ Mô đun hóa: • Nhóm các câu lệnh lại với nhau tạo ra những môđun có quan hệ với nhau. Nói cách khác: chương trình được phân tách thành các phần chức năng quan hệ logic với nhau. ƒ Ưu điểm: Dễ viết (write), duyệt lỗi (debug), và dễ hiểu chương trình hơn. 3 ƒ Triển khai chương trình từ trên xuống trong ngôn ngữ C: #include /* 1. Các hàm thư viện */ #define /* 2. Định nghĩa hằng */ typedef /* 3. Định nghĩa kiểu dữ liệu */ /* 4. Khai báo nguyên mẫu các hàm */ function prototype /* 5. Khai báo các biến toàn cục */ int main (void) /* 6. “Chương trình chính” */ { Khai báo các biến; Tập lệnh; } /* 7. “Các chương trình con”- các hàm */ 1 /* Fig. 6.22: fig06_22.c 2 Double-subscripted array example */ 3 #include 4 #define STUDENTS 3 5 #define EXAMS 4 6 7 /* function prototypes */ 8 int minimum( const int grades[][ EXAMS ], int pupils, int tests ); 9 int maximum( const int grades[][ EXAMS ], int pupils, int tests ); 10 double average( const int setOfGrades[], int tests ); 11 void printArray( const int grades[][ EXAMS ], int pupils, int tests ); 12 13 /* function main begins program execution */ 14 int main() 15 { 16 int student; /* counter */ 17 18 /* initialize student grades for three students (rows) */ 19 const int studentGrades[ STUDENTS ][ EXAMS ] = 20 { { 77, 68, 86, 73 }, 21 { 96, 87, 89, 78 }, 22 { 70, 90, 86, 81 } }; 23 Ví dụ: 3 sinh viên tương ứng với 3 hàng điểm sau: { { 77, 68, 86, 73 }, { 96, 87, 89, 78 }, { 70, 90, 86, 81 } }; Tìm điểm cao nhất, thấp nhất, tính điểm trung bình của mỗi sinh viên 24 /* output array studentGrades */ 25 printf( "The array is:\n" ); 26 printArray( studentGrades, STUDENTS, EXAMS ); 27 28 /* determine smallest and largest grade values */ 29 printf( "\n\nLowest grade: %d\nHighest grade: %d\n", 30 minimum( studentGrades, STUDENTS, EXAMS ), 31 maximum( studentGrades, STUDENTS, EXAMS ) ); 32 33 /* calculate average grade for each student */ 34 for ( student = 0; student <= STUDENTS - 1; student++ ) { 35 printf( "The average grade for student %d is %.2f\n", 36 student, average( studentGrades[ student ], EXAMS ) ); 37 } /* end for */ 38 39 return 0; /* indicates successful termination */ 40 41 } /* end main */ 42 43 /* Find the minimum grade */ 44 int minimum( const int grades[][ EXAMS ], int pupils, int tests ) 45 { 46 int i; /* counter */ 47 int j; /* counter */ 48 int lowGrade = 100; /* initialize to highest possible grade */ 49 50 /* loop through rows of grades */ 51 for ( i = 0; i < pupils; i++ ) { 52 53 /* loop through columns of grades */ 54 for ( j = 0; j < tests; j++ ) { 55 56 if ( grades[ i ][ j ] < lowGrade ) { 57 lowGrade = grades[ i ][ j ]; 58 } /* end if */ 59 60 } /* end inner for */ 61 62 } /* end outer for */ 63 64 return lowGrade; /* return minimum grade */ 65 66 } /* end function minimum */ 67 68 /* Find the maximum grade */ 69 int maximum( const int grades[][ EXAMS ], int pupils, int tests ) 70 { 71 int i; /* counter */ 72 int j; /* counter */ 73 int highGrade = 0; /* initialize to lowest possible grade */ 74 75 /* loop through rows of grades */ 76 for ( i = 0; i < pupils; i++ ) { 77 78 /* loop through columns of grades */ 79 for ( j = 0; j < tests; j++ ) { 80 81 if ( grades[ i ][ j ] > highGrade ) { 82 highGrade = grades[ i ][ j ]; 83 } /* end if */ 84 85 } /* end inner for */ 86 87 } /* end outer for */ 88 89 return highGrade; /* return maximum grade */ 90 91 } /* end function maximum */ 92 93 /* Determine the average grade for a particular student */ 94 double average( const int setOfGrades[], int tests ) 95 { 96 int i; /* counter */ 97 int total = 0; /* sum of test grades */ 98 99 /* total all grades for one student */ 100 for ( i = 0; i < tests; i++ ) { 101 total += setOfGrades[ i ]; 102 } /* end for */ 103 104 return ( double ) total / tests; /* average */ 105 106 } /* end function average */ 107 108 /* Print the array */ 109 void printArray( const int grades[][ EXAMS ], int pupils, int tests ) 110 { 111 int i; /* counter */ 112 int j; /* counter */ 113 114 /* output column heads */ 115 printf( " [0] [1] [2] [3]" ); 116 117 /* output grades in tabular format */ 118 for ( i = 0; i < pupils; i++ ) { 119 120 /* output label for row */ 121 printf( "\nstudentGrades[%d] ", i ); 122 The array is: [0] [1] [2] [3] studentGrades[0] 77 68 86 73 studentGrades[1] 96 87 89 78 studentGrades[2] 70 90 86 81 Lowest grade: 68 Highest grade: 96 The average grade for student 0 is 76.00 The average grade for student 1 is 87.50 The average grade for student 2 is 81.75 123 /* output grades for one student */ 124 for ( j = 0; j < tests; j++ ) { 125 printf( "%-5d", grades[ i ][ j ] ); 126 } /* end inner for */ 127 128 } /* end outer for */ 129 130 } /* end function printArray */ 10 ƒ Quy tắc cấu trúc: Có thể viết bất kỳ chương trình nào chỉ với 3 cấu trúc điều khiển cơ bản: • Tuần tự (Sequential) • Lựa chọn (hay Rẽ nhánh) (Selecttion) • Lặp (Repetition) 11 ƒ So sánh với lập trình hướng đối tượng (Object Oriented Programming) • Trong OOP điểm trọng tâm không phải là mã (code) mà là cái chúng ta muốn mã thực hiện trên đó (đặt trọng tâm vào đối tượng!) • Mô tả đối tượng gồm các thuộc tính thuộc hai nhóm: – Nhóm tính chất thứ nhất: khuôn dạng, sự tổ chức, kiến trúc (ví dụ: tên gọi, kích thước, mầu sắc, … – Nhóm tính chất thứ 2: sự vận động, sự tương tác với các đối tượng khác (ví dụ: cách tạo lập, hủy bỏ, sự cập nhật (thay đổi kích thước, mầu sắc,..), hình thức tổ hợp với các đối tượng khác • Trong OOP sử dụng các khái niệm cơ bản: đối tượng(object), lớp (class), tính kế thừa (inheritance), phương thức (methods), and tính đa hình (polymorphism). 12 ƒ Mã nguồn cho lập trình cấu trúc ---Bắt đầu chương trình var1 var2 var3 function1 { ... } function2 { ... } function3 { ... } main { ... } --- Kết thúc chương trình ƒ Object Oriented Programming: --- Bắt đầu chương trình object { varA varB functionA { ... } functionB { ... } } varC varD functionC { ... } main { ... } --- Kết thúc chương trình 13 ƒ Lập trình cấu trúc bắt buộc lập trình viên tiếp cận lập trình bắt đầu từ cách nhìn bài toán ở mức khái niệm, thiết kế chương trình trước khi tiến hành mã hóa (viết code) ƒ Lập trình cấu trúc giúp xóa bỏ mã rối (spaghetti code) và đảm bảo tính đúng đắn của chương trình. 14 Cấu trúc lệnh. Thuật toán Chương trình − Các thao tác được điều khiển bởi các lệnh − Các đối tượng chịu thao tác được mô tả thông qua các Cấu trúc dữ liệu Bài toán 15 T F if statement (single selection) TF if…else statement (double selection) T F đa lựa chọn (multiple selection) T F T F . . . Cấu trúc lựa chọn Seq uence . . . Cấu trúc lệnh. 16 Lặp với điều kiện trước T F do while statement T F T F for statement Cấu trúc lệnh. Cấu trúc lặp while statement Lặp với điều kiện sau Lặp với số lần lặp cho trước 17 Cấu trúc lựa chọn trong C ƒ Ví dụ: if ( grade >= 60 ) printf( "Passed\n" ); true false grade >= 60 print “Passed” 18 ƒ Ví dụ: if ( grade >= 60 ) printf( "Passed\n"); else printf( "Failed\n"); truefalse print “Failed” print “Passed” grade >= 60 19 ƒ Sử dụng Toán tử điều kiện (?:) • Thể hiện ba tham số (điều kiện, giá trị nếu true, giá trị nếu false) • Có thể viết lệnh thực hiện, như sau: printf( "%s\n", grade >= 60 ? "Passed" : "Failed" ); • Hoặc có thể viết dưới dạng: grade >= 60 ? printf( “Passed\n” ) : printf( “Failed\n” ); 20 Lệnh lặp while trong C int product = 2; while ( product <= 1000 ) product = 2 * product; product <= 1000 product = 2 * product true false 21 ƒ Lặp được kiểm soát bằng biến đếm (Counter) • Lặp đến khi “biến đếm” đạt được giá trị định trước • Số lần lặp xác định: số lần lặp biết trước • Ví dụ: Tính điểm trung bình của 10 sinh viên (giả sử điểm là số nguyên trong khoảng từ 0 đến 100). • Viết giả lệnh: Đọc vào từ bàn phím 10 số nguyên mô tả điểm của sinh viên và tính trung bình cộng Đặt total bằng 0 Đặt biến đếm counter bằng 1 While counter nhỏ hơn hoặc bằng 10 Input điểm của sinh viên tiếp theo Cộng điểm vừa đọc vào total Tăng biến counter lên 1 Tính điểm trung bình: lấy total chia cho 10 Print kết quả điểm trung bình 1 /* Fig. 3.8: fig03_08.c 2 Class average program with sentinel-controlled repetition */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 int counter; /* number of grades entered */ 9 int grade; /* grade value */ 10 int total; /* sum of grades */ 11 12 float average; /* number with decimal point for average */ 13 14 /* initialization phase */ 15 total = 0; /* initialize total */ 16 counter = 0; /* initialize loop counter */ 17 18 /* processing phase */ 19 /* get first grade from user */ 20 printf( "Enter grade, -1 to end: " ); /* prompt for input */ 21 scanf( "%d", &grade ); /* read grade from user */ 22 23 /* loop while sentinel value not yet read from user */ 24 while ( grade != -1 ) { 25 total = total + grade; /* add grade to total */ 26 counter = counter + 1; /* increment counter */ 27 28 printf( "Enter grade, -1 to end: " ); /* prompt for input */ 29 scanf("%d", &grade); /* read next grade */ 30 } /* end while */ 31 32 /* termination phase */ 33 /* if user entered at least one grade */ 34 if ( counter != 0 ) { 35 36 /* calculate average of all grades entered */ 37 average = ( float ) total / counter; 38 39 /* display average with two digits of precision */ 40 printf( "Class average is %.2f\n", average ); 41 } /* end if */ 42 else { /* if no grades were entered, output message */ 43 printf( "No grades were entered\n" ); 44 } /* end else */ 45 46 return 0; /* indicate program ended successfully */ 47 48 } /* end function main */ Program Output 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 25 Lặp kiểm soát bởi biến điều khiển (cờ): ƒ Ví dụ vấn đề đặt ra là: • Viết chương trình tính điểm trung bình của một lớp học mà số điểm đưa vào là tuỳ ý và khác nhau mỗi khi chạy chương trình. • Không biết trước số sinh viên • Làm thế nào để biết chương trình sẽ kết thúc ? ƒ Sử dụng giá trị điều khiển (lính gác) • Cũng có thể gọi là giá trị tín hiệu, giá trị cờ (flag) • Thể hiện “kết thúc lặp, tính toán xong.” • Kết thúc lặp khi người dùng nhập vào đúng giá trị cờ • Giá trị cờ là giá trị được chọn trước, ngoài phạm vi các giá trị vào thông thường, chẳng hạn giá trị cờ đặt là: -1 thì kết thúc lặp. 26 Viết giả lệnh với 3 pha: Khởi tạo, Nhập và tính tổng điêm, Tính và in giá trị trung bình Gán cho total giá trị 0; Gán cho biến đếm counter giá trị 0 Input điểm đầu tiên ( có thể là cờ) While người dùng chưa dựng cờ Cộng điểm vào biến total Tăng biến đếm lần nhập điểm lên 1 Input điểm của sinh viên tiếp theo (có thể là cờ) If counter khác 0 Tính giá trị trung bình, chia total cho biến counter Hiển thị giá trị trung bình else Hiển thị “Bạn đã không vào điểm” 1 /* Fig. 3.8: fig03_08.c 2 Class average program with sentinel-controlled repetition */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 int counter; /* number of grades entered */ 9 int grade; /* grade value */ 10 int total; /* sum of grades */ 11 12 float average; /* number with decimal point for average */ 13 14 /* initialization phase */ 15 total = 0; /* initialize total */ 16 counter = 0; /* initialize loop counter */ 17 18 /* processing phase */ 19 /* get first grade from user */ 20 printf( "Enter grade, -1 to end: " ); /* prompt for input */ 21 scanf( "%d", &grade ); /* read grade from user */ 22 23 /* loop while sentinel value not yet read from user */ 24 while ( grade != -1 ) { 25 total = total + grade; /* add grade to total */ 26 counter = counter + 1; /* increment counter */ 27 28 printf( "Enter grade, -1 to end: " ); /* prompt for input */ 29 scanf("%d", &grade); /* read next grade */ 30 } /* end while */ 31 32 /* termination phase */ 33 /* if user entered at least one grade */ 34 if ( counter != 0 ) { 35 36 /* calculate average of all grades entered */ 37 average = ( float ) total / counter; 38 39 /* display average with two digits of precision */ 40 printf( "Class average is %.2f\n", average ); 41 } /* end if */ 42 else { /* if no grades were entered, output message */ 43 printf( "No grades were entered\n" ); 44 } /* end else */ 45 46 return 0; /* indicate program ended successfully */ 47 48 } /* end function main */ 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 30 Bản chất của việc lặp được kiểm soát bởi biến đếm: ƒ Các yêu cầu lặp kiểm soát bởi biến đếm Counter • Tên của biến kiểm soát (hoặc đếm số lần lặp) • Giá trị đầu tiên của biến kiểm soát • Với mỗi lần lặp thì biến kiểm soát sẽ thay đổi giá trị và có thể tăng lên hoặc giảm xuống • Cần điều kiện để kiểm tra giá trị cuối của biến kiểm soát 31 Lệnh lặp for trong C 32 ƒ Lệnh lặp For có thể được viết thành lặp while như sau: Khởi tạo ban đầu; while ( Kiểm tra điều kiện tiếp tục lặp ) { Các lệnh; tăng biến điều khiển (biến đếm); } ƒ Khởi tạo ban đầu và việc thay đổi biến đếm • Sử dụng dấu “,” trong danh sách biến điều khiển • Ví dụ: for (int i = 0, j = 0; j + i <= 10; j++, i++) printf( "%d\n", j + i ); Trong đó: i, j cùng được khởi tạo ban đầu, làm điều kiện thoát khỏi vòng lặp for, và được tăng giá trị sau mỗi lần lặp. 33 ƒ Các biểu thức số học • Khởi tạo ban đầu, tiếp tục lặp lại, và việc thay đổi biến điều khiển có thể là các biểu thức số học. Nếu x = 2 và y = 10 for ( j = x; j <= 4 * x * y; j += y / x ) thì viết tương đương: for ( j = 2; j <= 80; j += 5 ) ƒ Lưu ý về lệnh for : • Thay đổi biến điều khiển: tăng hoặc giảm. • Nếu điều kiện tiếp tục lặp ngay từ ban đầu nhận giá trị false – Khối lệnh trong vòng lặp không được thực hiện – Cần kiểm soát xử lý với các lệnh tiếp sau lệnh for 34 Lệnh đa lựa chọn switch ƒ switch • Được sử dụng khi một biến hoặc biểu thức được kiểm tra tất cả các giá trị có thể, mỗi giá trị tương ứng với những hành động khác nhau. ƒ Cú pháp • Dãy các nhãn case và một trường hợp default khi value nằm ngoài tập giá trị. switch ( value ){ case '1': Câu lệnh; break; case '2': Câu lệnh; break; default: Câu lệnh; break; } • break; thoát khỏi lệnh 35 true false . . . case a case a action(s) break case b case b action(s) break false false case z case z action(s) break true true default action(s) 1 /* Fig. 4.7: fig04_07.c 2 Counting letter grades */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 int grade; /* one grade */ 9 int aCount = 0; /* number of As */ 10 int bCount = 0; /* number of Bs */ 11 int cCount = 0; /* number of Cs */ 12 int dCount = 0; /* number of Ds */ 13 int fCount = 0; /* number of Fs */ 14 15 printf( "Enter the letter grades.\n" ); 16 printf( "Enter the EOF character to end input.\n" ); 17 18 /* loop until user types end-of-file key sequence */ 19 while ( ( grade = getchar() ) != EOF ) { 20 21 /* determine which grade was input */ 22 switch ( grade ) { /* switch nested in while */ 23 24 case 'A': /* grade was uppercase A */ 25 case 'a': /* or lowercase a */ 26 ++aCount; /* increment aCount */ 27 break; /* necessary to exit switch */ 28 29 case 'B': /* grade was uppercase B */ 30 case 'b': /* or lowercase b */ 31 ++bCount; /* increment bCount */ 32 break; /* exit switch */ 33 34 case 'C': /* grade was uppercase C */ 35 case 'c': /* or lowercase c */ 36 ++cCount; /* increment cCount */ 37 break; /* exit switch */ 38 39 case 'D': /* grade was uppercase D */ 40 case 'd': /* or lowercase d */ 41 ++dCount; /* increment dCount */ 42 break; /* exit switch */ 43 44 case 'F': /* grade was uppercase F */ 45 case 'f': /* or lowercase f */ 46 ++fCount; /* increment fCount */ 47 break; /* exit switch */ 48 49 case '\n': /* ignore newlines, */ 50 case '\t': /* tabs, */ 51 case ' ': /* and spaces in input */ 52 break; /* exit switch */ 53 54 default: /* catch all other characters */ 55 printf( "Incorrect letter grade entered." ); 56 printf( " Enter a new grade.\n" ); 57 break; /* optional; will exit switch anyway */ 58 } /* end switch */ 59 60 } /* end while */ 61 62 /* output summary of results */ 63 printf( "\nTotals for each letter grade are:\n" ); 64 printf( "A: %d\n", aCount ); /* display number of A grades */ 65 printf( "B: %d\n", bCount ); /* display number of B grades */ 66 printf( "C: %d\n", cCount ); /* display number of C grades */ 67 printf( "D: %d\n", dCount ); /* display number of D grades */ 68 printf( "F: %d\n", fCount ); /* display number of F grades */ 69 70 return 0; /* indicate program ended successfully */ 71 72 } /* end function main */ Enter the letter grades. Enter the EOF character to end input. a b c C A d f C E Incorrect letter grade entered. Enter a new grade. D A b ^Z Totals for each letter grade are: A: 3 B: 2 C: 3 D: 2 F: 1 40 Lệnh lặp do…while trong C ƒ Lệnh lặp do…while • Điều kiện lặp sẽ được kiểm tra sau khi khối lệnh lặp được thực hiện. – Tất cả các hành động (lệnh) trong khối lặp được thực hiện ít nhất một lần. • Cú pháp: do { Câu lệnh; } while (điều kiện ); true false action(s) condition 41 ƒ Ví dụ 1 /* Fig. 4.9: fig04_09.c 2 Using the do/while repetition statement */ 3 #include 4 5 /* function main begins program execution */ 6 int main() 7 { 8 int counter = 1; /* initialize counter */ 9 10 do { 11 printf( "%d ", counter ); /* display counter */ 12 } while ( ++counter <= 10 ); /* end do...while */ 13 14 return 0; /* indicate program ended successfully */ 15 16 } /* end function main */ 1 2 3 4 5 6 7 8 9 10 42 Các lệnh break và continue ƒ break • Tác dụng thoát ngay lập tức khỏi các lệnh while, for, do…while hoặc lệnh switch • Chương trình sẽ thực hiện từ lệnh đầu tiên sau vòng lặp • Sử dụng lệnh break – Thoát sớm khỏi vòng lặp – Bỏ qua những giá trị còn lại trong lệnh switch 43 ƒ continue • Bỏ qua những lệnh còn lại trong khối lệnh lặp while, for hoặc do…while – Tiếp tục quá trình với lần lặp tiếp theo của lệnh lặp • while và do…while – Kiểm tra việc tiếp tục lặp ngay sau khi lệnh continue được thực hiện • for – Biểu thức tăng g