Bài giảng Kỹ thuật lập trình - Chương III: Mảng, chuỗi và hàm

LOGO Chương III Mảng, Chuỗi và Hàm COMPANY LOGO www.themegallery.com Nội dung chính Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 2 3.1. Mảng 3.2. Chuỗi 3.3. Mảng chuỗi 3.4. Hàm 3.5. Đệ quy 3.6. Hàm và mảng dữ liệu 3.7. Tổ chức chương trình COMPANY LOGO www.themegallery.com 3.1 Mảng Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 3 Mảng là tập hợp các phần tử có cùng kiểu dữ liệu được sắp xếp liền kề nhau trong bộ nhớ. A. Mảng một chiều Cú pháp khai báo: • [số thành phần] ; // không khởi tạo • [số thành phần] = { dãy giá trị } ; /* có khởi tạo */ • [ ] = { dãy giá trị } ; // có khởi tạo Cách sử dụng: Để chỉ thành phần thứ i (hay chỉ số i) của một mảng ta viết tên mảng kèm theo chỉ số trong cặp ngoặc vuông []. Mảng A A[0] A[1] A[2] A[3] A[4] A[5] A[6] COMPANY LOGO www.themegallery.com Ví dụ: Tìm phần tử nhỏ nhất của mảng một chiều Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 4 #include using namespace std; int main() { float a[100], min;// a chứa tối đa 100 số int i, n; cout> n; for (i = 0; i<n; i++) { cout>a[i] ; } min = a[0]; for (i = 1; i<n; i++) if (a[i] < min) min = a[i]; cout << "So be nhat la " << min << '\n'; } COMPANY LOGO www.themegallery.com 3.1 Mảng Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 5 B. Mảng nhiều chiều Để thuận tiện trong việc biểu diễn các loại dữ liệu phức tạp như ma trận hoặc các bảng biểu có nhiều chỉ tiêu, C++ đưa ra kiểu dữ liệu mảng nhiều chiều. Tuy nhiên, việc sử dụng mảng nhiều chiều rất khó lập trình vì vậy trong mục này chúng ta chỉ bàn đến mảng hai chiều. COMPANY LOGO www.themegallery.com 3.1 Mảng Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 6 Hình bên minh họa mảng 2 chiều với 3 dòng và 4 cột. Thực chất trong bộ nhớ, tất cả 12 phần tử của mảng được sắp liên tiếp theo từng dòng của mảng như minh hoạ trong hình dưới đây. 0 1 2 3 0 A[0][0] A[0][1] A[0][2] A[0][3] 1 A[1][0] A[1][1] A[1][2] A[1][3] 2 A[2][0] A[2][1] A[2][2] A[2][3] A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] A[1][2] A[1][3] A[2][0] A[2][1] A[2][2] A[2][3] Dòng 0 Dòng 1 Dòng 2 COMPANY LOGO www.themegallery.com Mảng hai chiều Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 7 Cú pháp khai báo: [m][n] ; – m, n là số hàng, số cột của mảng. – Kiểu thành phần là kiểu của m*n phần tử trong mảng. – Trong khai báo cũng có thể được khởi tạo bằng dãy các dòng giá trị, các dòng cách nhau bởi dấu phẩy, mỗi dòng được bao bởi cặp ngoặc {} và toàn bộ giá trị khởi tạo nằm trong cặp dấu {}. Sử dụng: Để truy nhập phần tử của mảng ta sử dụng tên mảng kèm theo 2 chỉ số chỉ vị trí hàng và cột của phần tử. Các chỉ số này có thể là các biểu thức thực, khi đó C++ sẽ tự chuyển kiểu sang nguyên. COMPANY LOGO www.themegallery.com Ví dụ: Tìm phần tử nhỏ nhất của mảng hai chiều Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 8 #include using namespace std; int main() { float a[100][100], min;// a chứa tối đa 10000 số int i, j, m, n; cout> m>> n; for (i = 0; i<m; i++) for (j = 0; j<n; j++) { cout>a[i][j]; } min = a[0][0];//Gán min bằng phần tử đầu tiên for (i = 1; i<n; i++) for (j = 0; j < n; j++) if (a[i][j] < min) min = a[i][j]; cout << "So be nhat la " << min << '\n'; } COMPANY LOGO www.themegallery.com 3.2 Chuỗi Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 9 Chuỗi hay xâu kí tự là một mảng các kí tự bất kì được kết thúc bằng kí tự ‘\0’. Hình vẽ trên minh hoạ 3 xâu, mỗi xâu được chứa trong mảng kí tự có độ dài tối đa là 8. Nội dung xâu thứ nhất là “TINHOC" có độ dài thực tế là 6 kí tự, chiếm 7 ô trong mảng (thêm ô chứa kí tự kết thúc '\0'). Xâu thứ hai có nội dung “TIN" với độ dài 3 (chiếm 4 ô) và xâu cuối cùng biểu thị một xâu rỗng (chiếm 1 ô). Chú ý : Mảng kí tự được khai báo với độ dài 8 tuy nhiên các xâu có thể chỉ chiếm một số kí tự nào đó trong mảng này và tối đa là 7 kí tự. 0 1 2 3 4 5 6 7 T I N H O C \0 T I N \0 H O C \0 \0 T I H O C \0 COMPANY LOGO www.themegallery.com 3.2 Chuỗi Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 10 Khai báo chuỗi: char [độ dài] ; // không khởi tạo char [độ dài] = xâu kí tự ; // có khởi tạo char [] = xâu kí tự ; // có khởi tạo ‒ Độ dài mảng là số kí tự tối đa có thể có trong xâu. Độ dài thực sự của xâu chỉ tính từ đầu mảng đến dấu kết thúc xâu (không kể dấu kết thúc xâu ‘\0’). Do vậy trong khai báo độ dài của mảng cần phải khai báo thừa ra một phần tử. ‒ Cách khai báo thứ hai có kèm theo khởi tạo xâu, đó là dãy kí tự đặt giữa cặp dấu nháy kép. ‒ Cách khai báo thứ 3 tự chương trình sẽ quyết định độ dài của mảng bởi xâu khởi tạo (bằng độ dài xâu + 1). Ví dụ: char thang[] = "Muoi hai" ; // độ dài mảng = 9 COMPANY LOGO www.themegallery.com 3.2 Chuỗi Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 11 Cách sử dụng: Sử dụng tương tự như mảng các giá trị số Nhập chuỗi với hàm cin.getline(s, n); Ví dụ: #include using namespace std; int main() { char hoten[25]; cout<< "Nhap vao ho ten:\n"; cin.getline(hoten, 24); cout << "Xin chao: " <<hoten<< '\n'; } COMPANY LOGO www.themegallery.com Một số hàm xử lý chuỗi trong #include Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 12 • strcpy(s, t) ; Hàm sẽ sao chép toàn bộ nội dung của xâu t (kể cả kí tự kết thúc xâu ‘\0’) vào cho xâu s. Để sử dụng hàm này cần đảm bảo độ dài của mảng s ít nhất cũng bằng độ dài của mảng t. Trong trường hợp ngược lại kí tự kết thúc xâu sẽ không được ghi vào s và điều này có thể gây treo máy khi chạy chương trình. Ví dụ: #include #include using namespace std; int main() { char s[10], t[10]; strcpy(t,"Face");// được, gán "Face" cho t strcpy(s,t);// được, sao chép t sang s cout << s << " to " << t<<'\n'; // in ra: Face to Face } COMPANY LOGO www.themegallery.com Một số hàm xử lý chuỗi trong #include Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 13 • strncpy(s, t, n) ; Sao chép n kí tự của t vào s. Hàm này chỉ làm nhiệm vụ sao chép, không tự động gắn kí tự kết thúc xâu cho s. Do vậy NSD phải thêm lệnh đặt kí tự '\0' vào cuối xâu s sau khi sao chép xong. Ví dụ: #include #include using namespace std; int main() { char s[15], t[20] = "Tin hoc dai cuong"; strncpy(s, t, 3); // copy 3 kí tự "Tin" vào s s[3]=' '; //Gán kí tự khoảng trống cho s[3] strncpy(s+4, t+8, 9); //copy "dai cuong" vào s từ vị trí thứ 4 s[13] = '\0'; // kết thúc xâu s cout <<"Chuoi s la: " << s<<'\n'; //Xuất ra “Tin dai cuong” } COMPANY LOGO www.themegallery.com Một số hàm xử lý chuỗi trong #include Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 14 • strcat(s, t); Nối một bản sao của t vào sau s (thay cho phép +). Hiển nhiên hàm sẽ loại bỏ kí tự kết thúc xâu s trước khi nối thêm t. Việc nối sẽ đảm bảo lấy cả kí tự kết thúc của xâu t vào cho s (nếu s đủ chỗ) vì vậy NSD không cần thêm kí tự này vào cuối xâu. Ví dụ: #include #include using namespace std; int main() { char a[100] = "Nam", b[4] = "Bac"; strcat(a, " va "); strcat(a, b); cout << a; //Sẽ xuất ra “Nam va Bac” } COMPANY LOGO www.themegallery.com Một số hàm xử lý chuỗi trong #include Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 15 • strncat(s, t, n); Nối bản sao n kí tự đầu tiên của xâu t vào sau xâu s. Hàm tự động đặt thêm dấu kết thúc xâu vào s sau khi nối xong. Tương tự, có thể sử dụng cách viết strncat(s, t+k, n) để nối n kí tự từ vị trí thứ k của xâu t cho s. • strcmp(s, t); Hàm so sánh 2 xâu s và t (thay cho các phép toán so sánh). Giá trị trả lại là hiệu 2 kí tự khác nhau đầu tiên của s và t. Từ đó, nếu s1 < s2 thì hàm trả lại giá trị âm, bằng 0 nếu s1==s2, và dương nếu s1 > s2. Trong trường hợp chỉ quan tâm đến so sánh bằng, nếu hàm trả lại giá trị 0 là 2 xâu bằng nhau và nếu giá trị trả lại khác 0 là 2 xâu khác nhau. COMPANY LOGO www.themegallery.com Một số hàm xử lý chuỗi trong #include Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 16 • strncmp(s, t, n) ; Giống hàm strcmp(s, t) nhưng chỉ so sánh tối đa n kí tự đầu tiên của hai xâu. • strcmpi(s, t) ; Như strcmp(s, t) nhưng không phân biệt chữ hoa, thường. • strupr(s); Hàm đổi xâu s thành in hoa, và cũng trả lại xâu in hoa đó. • strlwr(s); Hàm đổi xâu s thành in thường, kết quả trả lại là xâu s. • strlen(s) ; Hàm trả giá trị là độ dài của xâu s. COMPANY LOGO www.themegallery.com 3.3 Mảng chuỗi Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 17 Mảng chuỗi là mảng trong đó các phần tử của nó là một chuỗi. Cú pháp khai báo : Trong đó : kích_thước là số lượng phần tử tối đa của mảng, độ_dài_chuỗi là kích thước của các phần tử. Để truy cập đến các phần tử ta chỉ cần viết tên mảng kèm chỉ số của nó ở trong cặp dấu [] đầu tiên. char Tên_mảng[Kích_thước][độ_dài_chuỗi]; COMPANY LOGO www.themegallery.com Ví dụ về mảng chuỗi Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 18 #include using namespace std; int main() { char Sinh_vien[10][25]; //Mảng Sinh_vien gồm 10 chuỗi int i; for( i=0; i<10; i++) { cout<<"Nhap vao ho va ten sinh vien thu " <<i+1<<" :\n"; cin.getline(Sinh_vien[i], 24);//Nhập tối đa 24 kí tự cho chuỗi Sinh_vien[i] } cout<<"Danh sach sinh vien vua nhap la: \n"; for( i=0; i<10; i++) cout<<"Sinh vien thu "<<i+1<<": "<<Sinh_vien[i]<<"\n"; } COMPANY LOGO www.themegallery.com 3.4 Hàm Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 19  Định nghĩa hàm: Hoặc : Lưu ý: C không cho phép các hàm lồng nhau, nghĩa là phần định nghĩa của hàm này phải độc lập hoàn toàn với hàm khác. Kiểu_trả_về tên_hàm (kiểu và danh_sách_tham_số) { /* thân hàm */ Các_câu_lệnh ; return giá_trị ; } #define Tên_hàm(Các_tham_số) Biểu_thức_Giá_trị COMPANY LOGO www.themegallery.com 3.4 Hàm Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 20  Khai báo nguyên mẫu hàm : Khai báo nguyên mẫu hàm sẽ cung cấp cho trình biên dịch mô tả về một hàm sẽ được định nghĩa ở một vị trí nào đó trong chương trình:  Gọi hàm:  Trong danh_sách_đối_số không đưa ra kiểu dữ liệu của đối số. Nếu hàm cần truyền nhiều đối số thì chúng phải tách nhau bởi dấu phẩy. Nếu đối số là mảng thì chỉ cần ghi tên mảng. Kiểu_trả_về tên_hàm (kiểu và danh_sách_tham_số); Tên_hàm (danh_sách_đối_số) ; COMPANY LOGO www.themegallery.com Ví dụ 1: Định nghĩa và gọi hàm tính giai thừa Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 21 #include using namespace std; long factorial(int n); //Khai báo nguyên mẫu cho hàm factorial int main() { cout<<"6! = "<<factorial(6); //Gọi hàm factorial với tham số là 6 } long factorial(int n)//Định nghĩa hàm factorial với 1 tham số nguyên n { long p=1, i; if(n>=0) // Chỉ tính giai thừa cho số không âm { for( i=2; i<=n; i++) p*= i; return p; //Trả về cho hàm factorial giá trị bằng p } else cout<< "Khong tinh duoc giai thua so am"; } COMPANY LOGO www.themegallery.com Ví dụ 2: Hàm tính giá trị lớn nhất của 3 số Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 22 #include using namespace std; #define max(a,b,c) a>b?(a>c?a:c):(b>c?b:c) int main() { int x, y, z, t; cout<<"Nhap vao 3 so nguyen:\n"; cin>>x>>y>>z; cout<<"So lon nhat trong ba so vua nhap la: "; t=max(x,y,z); //Gọi hàm max cout<< t; } COMPANY LOGO www.themegallery.com 3.5 Đệ quy Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 23  Hàm đệ quy là hàm mà từ một điểm trong thân của nó có thể gọi tên hàm của chính nó.  Cấu trúc tổng quát của hàm đệ qui thường như sau: if (trường hợp cơ sở) { trình bày cách giải // giả định đã có cách giải } else // trường hợp tổng quát { Gọi lại hàm với tham đối "bé" hơn } COMPANY LOGO www.themegallery.com Ví dụ 1: Hàm đệ quy tính UCLN của 2 số Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 24 #include using namespace std; int UCLN(int a, int b) { if(a==b)return a; //Trường hợp cơ sở if(a>b)return UCLN(a-b, b); //Thuật toán Euclid if(a<b)return UCLN(a, b-a); } int main() { int x, y, uc; cout>x>>y; cout<<"UCLL cua 2 so "<<x<<" va "<<y<<" la: "<< UCLN(x,y); } COMPANY LOGO www.themegallery.com Ví dụ 2: Tính số hạng thứ n của dãy Fibonaci Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 25 #include using namespace std; int Fibo(int n) { if(n==1)return 0;//Phần tử đầu tiên bằng 0 if(n==2)return 1;//Phần tử thứ 2 bằng 1 if(n>2)return Fibo(n-1)+ Fibo(n-2); //Phần tử thứ n bằng tổng của (phần tử thứ n-1) và (phần tử thứ n-2) } int main() { cout<<"Phan tu thu 7 cua day Fibonacci la: "; cout<<Fibo(7); cout<<"\n8 phan tu dau tien cua day Fibonacci la:\n"; for(int i=1; i<=8; i++) cout<<Fibo(i)<<"\t"; } COMPANY LOGO www.themegallery.com 3.6 Hàm và mảng dữ liệu Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 26 #include // Ví dụ minh họa hàm và mảng một chiều using namespace std; void sort(int a[], int size) //Hàm sắp xếp mảng tăng dần { int i, j, t; for(i=0; i<size-1; i++) for(j=i+1; j<size; j++) if(a[i]>a[j]) //Nếu phần tử a[i]>a[j] ( a[j] - Các phần tử sau a[i]) { t=a[i]; a[i]=a[j]; a[j]=t; } //hoán đổi a[i] cho a[j] } int main() { int a[8]={1,5,2,9,8,7,0,3}; sort(a,8); // Sắp xếp mảng a tang dần for(int i=0; i<8; i++) cout<<a[i]<<"\t"; } COMPANY LOGO www.themegallery.com 3.6 Hàm và mảng dữ liệu Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 27 #include// Ví dụ minh họa hàm và mảng hai chiều using namespace std; int MAX(int a[][50], int row, int col) //row và col là số hàng và cột của mảng { int i, j, mc =a[0][0];//biến mc gán bằng phần tử đầu tiên của mảng for(i=0;i<row;i++) for(j=0;j<col;j++) if(a[i][j]>mc) mc=a[i][j]; return mc; //Trả về mc (chính là giá trị lớn nhất của mảng) cho hàm MAX } int main() { int b[][50]={{2,15},{21,8},{16,-3}};// Số cột phải bằng 50 – như trong MAX cout<<"Phan tu lonn nhat cua mang la: "<<MAX(b,3,2); // Mảng b truyền vào hàm MAX với số hàng là 3, số cột là 2 } COMPANY LOGO www.themegallery.com 3.7 Tổ chức chương trình Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 28  Các loại biến và phạm vi  Biến cục bộ  Biến ngoài hay biến toàn cục  Biến với mục đích đặc biệt  Biến hằng và từ khóa const  Biến tĩnh và từ khóa static  Biến thanh ghi và từ khóa register  Biến ngoài và từ khóa extern  Các chỉ thị tiền xử lý  Chỉ thị bao hàm tệp #include  Chỉ thị macro #define  Chỉ thị #ifdef và #ifndef COMPANY LOGO www.themegallery.com Bài tập chương III Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 29 Viết chương trình giải các bài tập sau ( nên dùng hàm) : Bài 1. Nhập dữ liệu cho dãy số nguyên gồm n phần tử (n<=50). A. Xác định số phần tử là số chẵn mà lớn hơn 30 trong mảng B. Tìm giá trị nhỏ nhất trong mảng và số lần xuất hiện của nó C. Sắp xếp mảng tăng dần D. Xóa tất cả các phần tử có giá trị bằng x ở trong mảng E. Chèn vào mảng phần tử y sao cho mảng vẫn tăng dần. Bài 2. Nhập dữ liệu cho 2 ma trận số nguyên A và B đều gồm m hàng n cột. A. Xuất từng ma trận và ma trận tổng A+B B. Tìm phần tử lớn nhất trên từng ma trận và trên cả 2 ma trận C. Tổng các phần tử trên ma trận nào là lớn hơn D. Sắp xếp ma trận A tăng dần, ma trận B giảm dần COMPANY LOGO www.themegallery.com Bài tập chương III Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 30 Bài 4. Nhập dữ liệu cho xâu kí tự str[100] A. Xuất ra màn hình xâu str B. Xâu str có bao nhiêu kí tự và trong đó bao nhiêu kí tự là số C. Loại bỏ các kí tự không phải là chữ hoặc không phải khoảng trống trong xâu str D. Đổi chữ thường trong xâu str thành chữ in hoa E. Chèn vào xâu str một xâu str2 khác vào vị trí bất kì trong str. Bài 5. Nhập dữ liệu cho mảng chuỗi A gồm n sinh viên (n<=50). A. Xuất các chuỗi trong A ra màn hình B. Tìm xem trong A có bao nhiêu người có họ là “Nguyen” C. Dựa vào họ hãy sắp xếp A tăng dần (a  z). D. Xuất ra màn hình tên của các sinh viên dưới dạng chữ in hoa. COMPANY LOGO www.themegallery.com Bài tập chương III Trường ĐH GTVT TP.HCM - Bài giảng : Kỹ thuật lập trình 31 Bài 6. Viết hàm đệ qui tính n! A. Tính tổ hợp chập k của n phần tử ( Nếu tồn tại) B. Tính hệ số của số hạng thứ k trong khai triển nhị thức Newton của : ( + ) C. Xuất ra tất cả các hệ số của khai triển nhị thức ở câu B trên D. Xuất ra màn hình tam giác Pascal Bài 7. Viết hàm đệ qui tính số fibonaci thứ n. A. Xuất ra n phần tử đầu tiên của dãy Fibonacci B. Xuất ra màn hình k phần tử chẵn đầu tiên của dãy Fibonacci C. Xuất ra phần tử lẻ thứ m của dãy Fibonacci ( Cho dãy Fibonacci: 0,1, 1, 2, 3, 5, 8, 13, 21,.) Bài 8. Tính: với n dấu căn33331  ...S LOGO www.themegallery.com