Bài giảng Phương pháp lập trình - Chương IV: Mảng (Array) - Nguyễn Văn Thắng

Nội dung text: Bài giảng Phương pháp lập trình - Chương IV: Mảng (Array) - Nguyễn Văn Thắng

1. CHƯƠNG IV:MẢNG(ARRAY)
2. KHÁI NIỆM • Mảng là một tập hợp các phần tử cố định có cùng một kiểu được đặt liên tiếp trong bộ nhớ gọi là kiểu phần tử. • Kiểu phần tử có thể là: số, ký tự . • Mỗi phần tử được xác định bởi một chỉ số biểu thị vị trí của phần tử trong mảng. Giảng Viên: Nguyễn Văn Thắng
3. KHÁI NIỆM • Nếu mảng có n phần tử thì chỉ số của các phần tử có giá trị từ 0 đến n-1. • Số phần tử trong mảng được gọi là kích thước của mảng. luôn cố định, phải được xác định trước và không đổi trong suốt quá trình thực hiện chương trình. Giảng Viên: Nguyễn Văn Thắng
4. MẢNG 1 CHIỀU
5. Khai báo mảng • Khai báo mảng với số phần tử tường minh • Ví dụ: int a[5] Giá trị a a 7 5 3 8 6 a[0] a[1] a[2] a[3] a[4] a[0] a[1] a[2] a[3] a[4] Vị trí Giảng Viên: Nguyễn Văn Thắng
6. Khai báo mảng • Khai báo mảng với số phần tử không xác định (khai báo không tường minh) Ví dụ: int a[] • Kiểu khai báo này thường được áp dụng trong các trường hợp: ─ Vừa khai báo vừa gán giá trị ─ Khai báo mảng là tham số hình thức của hàm. Giảng Viên: Nguyễn Văn Thắng
7. Vừa khai báo vừa gán giá trị [ ]= {gtri1, gtri2, } Ví dụ: char str[] = "HELLO"; H E L L 0 \0 int a[] = {5, 10, 15}; a 5 10 15 a[0] a[1] a[2] Giảng Viên: Nguyễn Văn Thắng
8. Vừa khai báo vừa gán giá trị • Nếu vừa khai báo vừa gán giá trị thì số phần tử của mảng là số giá trị mà ta gán cho mảng trong cặp dấu {}. • Sử dụng hàm sizeof() để lấy số phần tử của mảng như sau: Số phần tử=sizeof(tên mảng)/ sizeof(kiểu) Giảng Viên: Nguyễn Văn Thắng
9. Khai báo mảng là tham số hình thức của hàm • Trong một số trường hợp ta cần phải truyền một mảng tới một hàm như là một tham số • Trong C++, việc truyền theo tham số giá trị một khối nhớ là không hợp lệ • Để có thể nhận mảng là tham số thì khai báo hàm theo cú pháp: [] Ví dụ: void procedure(int arg[ ]) Giảng Viên: Nguyễn Văn Thắng
10. Ví dụ #include void printarray (int arg[], int length) { for (int n=0; n<length; n++) cout <<setw(3)<< arg[n] ; } int main (){ int x[] = {5, 10, 15}; int y[] = {2, 4, 6, 8, 10}; printarray (x,3); printarray (y,5); return 0; } Giảng Viên: Nguyễn Văn Thắng
11. Truy xuất từng phần tử của mảng • Cú pháp: [ ][ ][ ][ ] • Ví dụ: M[0], M[2], M[1][5], • Chỉ số của phần tử mảng là một biểu thức có giá trị là kiểu số nguyên. • Với cách truy xuất này thì có thể coi như là một biến có kiểu dữ liệu là kiểu được chỉ ra trong khai báo biến mảng.Giảng Viên: Nguyễn Văn Thắng
12. Ví dụ: #include #include int main() { int n,i,j,tam; int dayso[ ]={66, 65, 69, 68, 67, 70}; clrscr(); n=sizeof(dayso); //Lấy số phần tử cout<< " Noi dung cua mang "; for (i=0;i<n;i++) cout<<setw(3)<<dayso[i]; return 0; } Giảng Viên: Nguyễn Văn Thắng
13. Ví dụ: Đổi một số nguyên dương thập phân thành số nhị phân void main() { n=46 2 int i,j=0,n,np[20]; 2 cout >n; n%2 0 23 do 1 11 2 { 5 2 1 np[j]=n%2; 2 2 j++; 1 2 1 n=n/2; 0 }while(n>0); 1 0 cout 0 ; i ) np cout<<setw(3)<<np[i]; 0 1 1 1 1 1 getch(); } np[j] Giảng Viên: Nguyễn Văn Thắng
14. Ví dụ : Nhập vàò một mảng số nguyên sau đó sắp xếp theo thứ tự tăng dần #include #define n 5 main ( ) { int a [ n ] ; int i , j, t ; for ( i = 0 ; i >a[i]; cout<<endl; } for ( i = 0 ; i < n - 1 ; i ++)//sắp xếp for ( j = i + 1 ; j < n ; j ++ ) if ( a [ i ] < a [j ] ) { t = a [ i ] ; a [ i ] = a [ j ]; a [j ] = t ; } for ( i = 0 ; i < n ; i ++ )//xuất mảng cout<<setw(3)<<a[i]; getch ( ) Giảng Viên: Nguyễn Văn Thắng }
15. Sử dụng hàm tạo số ngẫu nhiên • C++ cung cấp hàm random để tạo ra các số ngẫu nhiên. • Cú pháp: int random(int n) • Kết quả của hàm là các số nguyên từ 0 đến n-1 • Khi sử dụng random ta phải gọi randomize để khởi tạo chế độ tạo số ngẫu nhiên. • Muốn sử dụng các hàm trên thì trong chương trỉnh ta phải khai báo #include Giảng Viên: Nguyễn Văn Thắng
16. Ví dụ : Chương trình sau tạo giá trị ngẫu nhiên cho một mảng n phần tử, thực hiện sắp xếp và in mảng lên màn hình trước và sau khi sắp xếp. #include #include #include #include void taomang(int a[], int n) { randomize; cout <<"Tao mang ngẫu nhiên :\n"; for (int i=0; i<n; i++) a[i]=random(100); Giảng Viên: Nguyễn Văn Thắng }
17. Ví dụ : Chương trình sau tạo giá trị ngẫu nhiên cho một mảng n phần tử, thực hiện sắp xếp và in mảng lên màn hình trước và sau khi sắp xếp void sapxepmang(int a[], int n) { int i, j,tam; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(a[i]<a[j]) { tam=a[i]; a[i]=a[j]; a[j]=tam; } } Giảng Viên: Nguyễn Văn Thắng
18. Ví dụ : Chương trình sau tạo giá trị ngẫu nhiên cho một mảng n phần tử, thực hiện sắp xếp và in mảng lên màn hình trước và sau khi sắp xếp void inmang(int a[], int n) { for(int i=0; i<n; i++) cout <<setw(3)<<a[i]; } Giảng Viên: Nguyễn Văn Thắng
19. Ví dụ : Chương trình sau tạo giá trị ngẫu nhiên cho một mảng n phần tử, thực hiện sắp xếp và in mảng lên màn hình trước và sau khi sắp xếp(viết dưới dạng hàm) void main() { int n, a[]; clrscr(); cout >n; taomang(a, n); cout<<“Mang truoc khi sap xep:\n”; inmang(a, n); sapxepmang(a,n) cout<<“Mang sau khi sap xep:\n”; inmang(a, n); getch(); return; } Giảng Viên: Nguyễn Văn Thắng
20. MẢNG NHIỀU CHIỀU
21. Khai báo mảng nhiều chiều • Mảng nhiều chiều có thể được coi như mảng của mảng • Một mảng hai chiều có thể được xem như là một bảng hai chiều gồm các phần tử có kiểu dữ liệu cụ thể và giống nhau. Giảng Viên: Nguyễn Văn Thắng
22. Khai báo mảng 2 chiều tường minh • Cú pháp • Ví dụ: int a[3][5]; Giảng Viên: Nguyễn Văn Thắng
23. Khai báo mảng hai chiều int A[3][3]; 0,0 0,1 0,2 0,0 0,1 0,2 1,0 1,1 1,2 1,0 1,1 1,2 2,0 2,1 2,2 2,0 2,1 2,2 5 7 6 int A[hàng][ cột]; Đường chéo chính 2 8 9 5 1 4 Giá Giảng Viên: Nguyễn Văn Thắng trị
24. Khai báo mảng 2 chiều không tường minh • Để khai báo mảng 2 chiều không tường minh, ta vẫn phải chỉ ra số phần tử của chiều thứ hai (chiều cuối cùng). • Cú pháp: • Cách khai báo này cũng được áp dụng trong trường hợp vừa khai báo, vừa gán trị hay đặt mảng 2 chiều làGiảngtham Viên: Nguyễnsố hình Văn Thắngthức của hàm
25. Truy xuất từng phần tử của mảng 2 chiều • Cú pháp: Tên mảng[Chỉ số 1][Chỉ số 2] • Ví dụ: a[1][3] Giảng Viên: Nguyễn Văn Thắng
26. Ví dụ : #define cot 5 #define hang 3 int arr [hang][cot]; int n,m; int main () { for (i=0 ; i<hang ; i++) for (j=0 ; j<cot ; j++) { a[i][j]=(i+1)*(j+1); } return 0; } Giảng Viên: Nguyễn Văn Thắng
27. Khai báo mảng 2 chiều như một tham số • Trong C++ không thể truyền toàn bộ một khối bộ nhớ bằng một giá trị như là một tham số đến một hàm, nhưng được phép truyền địa chỉ của nó • Để chấp nhận những mảng như là những tham số của hàm thì khi khai báo hàm phải chỉ rõ trong các tham số của nó loại phần tử của mảng [ ][Số phần tử chiều 2] Giảng Viên: Nguyễn Văn Thắng
28. #include #include void Nhap(int a[][10],int M,int N) { for(int i=0 ; i > a[i][j]; // a[i][j]=so ngau nhien } } void InMaTran(int a[ ][10], int M, int N) { for(int i=0;i<M;i++) { for(int j=0; j< N; j++) cout<<setw(3)<<a[i][j]; cout<<"\n"; } } Giảng Viên: Nguyễn Văn Thắng
29. Các phương pháp tìm kiếm và sắp xếp trên mảng
30. Tìm kiếm Tìm kiếm trên mảng một chiều: • Xây dưng hàm int search(int a[ ],int n, int x) Tìm một giá trị x trên mảng a có n phần tử. Kết quả của hàm trả về vị trí tìm thấy, hàm trả về giá trị âm khi không tìm thấy. Giảng Viên: Nguyễn Văn Thắng
31. Tìm kiếm int search1(int a[ ],int n, int x) { for (int i=0; i<n; i++) if (a[i] == x ) return (i); return (-1); } Giảng Viên: Nguyễn Văn Thắng
32. Tìm kiếm Tìm kiếm trên mảng hai chiều: • Xây dưng hàm int search2(int a[ ][COLS],int n, int x) • Tìm một giá trị x trên mảng a có n dòng và COLS cột. • Kết quả của hàm trả về vị trí tìm thấy, hàm trả về giá trị âm khi không tìm thấy. Giảng Viên: Nguyễn Văn Thắng
33. Tìm kiếm int search2 (int m[ ][ ], int n, int m, int x, int &r, int &c) { int i=0, j=0; r = -1; c = -1; for (; i<n; i++) for (; j<m; j++) if (m[i][j] == x ) { c= i; r = j; return (1); } return (-1); } Giảng Viên: Nguyễn Văn Thắng
34. Sắp xếp Sắp xếp trên mảng một chiều: Viết hàm sort(a[ ],n) sắp xếp một mảng n phần tử theo thứ tự tăng. Sắp xếp trên mảng một chiều: Nguyên tắc sắp xếp mảng hai chiều là đưa toàn bộ giá trị của mảng hai chiều ra một mảng một chiều, tiếp theo sắp xếp trên mảng một chiều này và cuối cùng là đưa các giá trị từ mảng một chiều vào mảng hai chiều. Viết hàm sort2(a[][COLS],n) dể sắp xếp một mảng n dòng, COLS cột phần tử theo thứ tự tăng. Giảng Viên: Nguyễn Văn Thắng