Bài giảng Cơ sở lập trình - Chương 7: Mảng - Phan Đình Thế Huân

CƠ SỞ LẬP TRÌNH Phan Đình Thế Huân Tháng 5 - 2008 MẢNG 7 CSLT - Bài 7 Phan Dinh The Huan 2 Nội dung 1. Khái niệm 2. Mảng một chiều 3. Chuỗi ký tự 4. Mảng nhiều chiều CSLT - Bài 7 Phan Dinh The Huan 3 1. Khái niệm 1. Mảng (array) là kiểu dữ liệu có cấu trúc, bao gồm dãy liên tục các phần tử có cùng kiểu dữ liệu 2. Phân loại: z Mảng 1 chiều z Mảng nhiều chiều CSLT - Bài 7 Phan Dinh The Huan 4 Ví dụ Mảng một chiều Chỉ số dòng Chỉ số cột 2112983[M-1] 941521[1] 1273253[0] [N-1][4][3][2][1][0]a a chỉ số 1025817 N-1N-2nn-13210 Mảng hai chiều CSLT - Bài 7 Phan Dinh The Huan 5 2.Mảng 1 chiều 1. Khai báo 2. Truy xuất mảng 3. Một số thao tác cơ bản trên mảng một chiều 4. Mảng và hàm CSLT - Bài 7 Phan Dinh The Huan 6 2.1 Khai báo mảng a. Khai báo: #define N 20 int a[N],n; a chỉ số N-1N-2nn-13210 kiểu DL số lượng số lượng tối đa (khai báo) số lượng thực tế: n<=N CSLT - Bài 7 Phan Dinh The Huan 7 2.1 Khai báo mảng b. Khai báo và khởi gán giá trị: #define N 20 int a[N]={7,1,8,25,4,6,10}; int b[]={7,1,8,25,4,6,10}; const int days[]={31,28,31,30,31,30,31,31,30,31,30,31}; Mảng a có 20 phần tử, với 7 phần tử đầu tiên có giá trị cho trước. Mảng b có 7 phần tử đầu tiên có giá trị cho trước, kích thước của mảng bằng số lượng phần tử cho trước (7 phần tử). Mảng days là mảng chứa các giá trị hằng số, có 12 phần tử. CSLT - Bài 7 Phan Dinh The Huan 8 2.2 Truy xuất mảng 1. Truy xuất trực tiếp thông qua chỉ số: z Cú pháp: [] z VD: z a[0] = 1; // gán giá trị 1 cho phần tử a[0] z printf(“%4d”, a[3]); // in phần tử a[3] ra màn hình z scanf(“%d”, &a[0]); // nhập giá trị cho phần tử a[0] z cout<<a[3]; z cin>>a[3]; CSLT - Bài 7 Phan Dinh The Huan 9 2.3 Một số thao tác cơ bản trên mảng 1 chiều 1. Duyệt mảng 2. Nhập mảng 3. Xuất mảng 4. Tìm kiếm 5. Đếm 6. Sắp xếp 7. Chèn thêm 1 phần tử vào mảng 8. Hủy một phần tử ra khỏi mảng CSLT - Bài 7 Phan Dinh The Huan 10 2.3 Một số thao tác cơ bản trên mảng 1 chiều 1. Duyệt mảng a có n phần tử: for(i=0; i<n; i++) //xử lý trên a[i] a iÆ n-1n-26543210 CSLT - Bài 7 Phan Dinh The Huan 11 2. Nhập giá trị cho mảng a có n phần tử: a iÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều for(i=0; i<n; i++) { cout<<“a[”<<i<<“= ”; cin>>a[i]; } CSLT - Bài 7 Phan Dinh The Huan 12 3. Xuất giá trị của mảng a có n phần tử ra màn hình: a iÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều for(i=0; i<n; i++) { cout.width(8); cout<<a[i]; } độ rộng CSLT - Bài 7 Phan Dinh The Huan 13 4. Tìm kiếm giá trị x trong mảng a :Æ có / không for(i=0; i<n; i++) if(a[i]==x) break; if(i<n) //tìm thấy tại vị trí i else //không tìm thấy a iÆ n-1n-26543210 Cách 1: 2.3 Một số thao tác cơ bản trên mảng 1 chiều CSLT - Bài 7 Phan Dinh The Huan 14 4. Tìm kiếm giá trị x trong mảng a :Æ có / không int found=0;//chưa tìm thấy for(i=0; i<n && !found; i++) if(a[i]==x) found=1; if(found) //tìm thấy tại vị trí i else //không tìm thấy a iÆ n-1n-26543210 Cách 2: dùng ‘cờ’ 2.3 Một số thao tác cơ bản trên mảng 1 chiều CSLT - Bài 7 Phan Dinh The Huan 15 4. Tìm kiếm giá trị x trong mảng a :Æ có / không a[n]=x; for(i=0; a[i]!=x; i++); if(i<n) //tìm thấy tại vị trí i else //không tìm thấy a iÆ x nn-16543210 Cách 3: dùng ‘lính canh’, chú ý n 2.3 Một số thao tác cơ bản trên mảng 1 chiều CSLT - Bài 7 Phan Dinh The Huan 16 5. Tìm và đếm số lượng x trong mảng a : int count=0; for(i=0; i<n; i++) if(a[i]==x) count++; if(count) //tìm thấy count phần tử else //không tìm thấy a iÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều CSLT - Bài 7 Phan Dinh The Huan 17 6. Sắp xếp mảng : //phương pháp chọn trực tiếp int min; for(i=0; i<n-1; i++) { min=i; for(j=i+1;j<n;j++) if(a[min]>a[j]) min=j; hoanVi(a[min],a[i]); } a iÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều CSLT - Bài 7 Phan Dinh The Huan 18 7. Chèn thêm 1 phần tử vào mảng : a chỉ sốÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều (1) Chèn phần tử x tại ví trí k cho trước (2) Chèn phần tử x vào mảng sao cho đảm bảo tính tăng dần CSLT - Bài 7 Phan Dinh The Huan 19 7. (1) Chèn thêm 1 phần tử x vào mảng tại vị trí k: if (k>=0 && k<=n) { for(i=n; i>k; i--) a[i] = a[i-1]; a[k] = x; n++; } a chỉ sốÆ nn-16543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều kx CSLT - Bài 7 Phan Dinh The Huan 20 7. (2) Chèn thêm x sao cho đảm bảo tăng dần: //mảng đã được sắp xếp tăng n++; for(i=n; a[i]>x && i>0; i--) a[i] = a[i-1]; a[i] = x; a chỉ sốÆ nn-16543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều x CSLT - Bài 7 Phan Dinh The Huan 21 8. Hủy một phần tử x ra khỏi mảng : a chỉ sốÆ n-1n-26543210 2.3 Một số thao tác cơ bản trên mảng 1 chiều Gồm các bước: • Tìm kiếm x trong mảng, nếu có thì: • Hủy x bằng cách: dịch chuyển các phần tử bên phải x sang trái 1 đơn vị. • n = n - 1 (xem như bài tập) CSLT - Bài 7 Phan Dinh The Huan 22 2.4. Mảng và hàm 1. Phương pháp truyền mảng vào hàm: tham chiếu 2. Từ khóa const: nếu đặt từ khóa const trước tham số hình thức Æ giá trị của các phần tử trong mảng sẽ là hằng số, không được phép thay đổi CSLT - Bài 7 Phan Dinh The Huan 23 Ví dụ – truyền mảng vào hàm #include void nhapMang(int a[], int n); void inMang(const int a[], int n); void main() { int a[100], n= 10; nhapMang(a, n); inMang(a, n); } void nhapMang(int a[], int n) { cout<<“\nNhap mang:\n”; for(int i=0; i<n; i++) { cout<<“Nhap a[“<<i<<”]=”; cin>>a[i]; } } Giá trị của mảng là hằng số, không cho phép thay đổi ... void inMang(const int a[], int n) { for(int i=0; i<n; i++) { cout.width(4); cout<<a[i]; } } CSLT - Bài 7 Phan Dinh The Huan 24 3. Chuỗi ký tự 1. Các khái niệm 2. Các xử lý thông dụng trên chuỗi 3. Các hàm xử lý chuỗi trong thư viện string.h CSLT - Bài 7 Phan Dinh The Huan 25 3.1Các khái niệm về chuỗi ký tự 1. Định nghĩa: z Chuỗi ký tự là một mảng một chiều các ký tự z Ký tự kết thúc chuỗi là ký tự null - ‘\0’ 2. Khai báo và khởi tạo: z char ten[10]; z char ten[] = “Tin hoc”; z char ten[10]= {‘T’, ‘i’, ‘n’, ‘ ‘, ‘h’, ‘o’, ‘c’,’\0’}; ten iÆ ‘\0’‘c’‘o’‘h’‘ ‘‘n’‘i’‘T’ 9876543210 Chuỗi “Tin hoc” có 7 ký tự nhưng thực tế lưu trữ phải cần ít nhất 8. Truy cập thành phần thông qua chỉ số: VD: ten[4] = ‘h’ CSLT - Bài 7 Phan Dinh The Huan 26 3.1Các khái niệm về chuỗi ký tự 1. Nhập xuất z Nhập: scanf(“%s”, ten); hoặc gets(ten); z Tên mảng cũng là địa chỉ của mảng nên không cần phải sử dụng phép lấy địa chỉ qua ký tự & z Không dùng lệnh cin>>ten; để nhập chuỗi. z Dùng cin.ignore(); cin.getline(ten,>); z Xuất: printf(“%s”, ten); hoặc puts(ten); hoặc dùng lệnh cout<<ten; 2. Duyệt chuỗi: giống như duyệt mảng một chiều for(int i=0; s[i]!=‘\0’; i++) //do something with s[i] CSLT - Bài 7 Phan Dinh The Huan 27 3.2 Các xử lý thông dụng trên chuỗi ký tự 1. Đếm chiều dài chuỗi 2. Đổi chuỗi sang chữ in hoa/ chữ thường 3. Cắt khoảng trắng thừa bên trái chuỗi 4. Cắt khoảng trắng thừa bên phải chuỗi 5. Cắt tất cả khoảng trắng thừa trong chuỗi 6. Đếm số từ trong chuỗi 7. Đảo ngược chuỗi 8. Trích chuỗi con từ chuỗi cho trước 9. Nối hai chuỗi cho trước thành một 10. Tìm một chuỗi có trong chuỗi cho trước không (Xem như bài tập) CSLT - Bài 7 Phan Dinh The Huan 28 3.3 Thư viện string.h 1. memccpy memchr memcmp memcpy memicmp memmove memset movedata movmem setmem 2. stpcpy strcat strchr strcmp strcmpi strcpy strcspn strdup strerror stricmp strlen strlwr 3. strncat strncmp strncmpi strncpy strnicmp strnset 4. strpbrk strrchr strrev strset strspn strstr strtok strxfrm strupr CSLT - Bài 7 Phan Dinh The Huan 29 4. Mảng nhiều chiều 1. Khai báo mảng nhiều chiều 2. Truy xuất mảng nhiều chiều 3. Duyệt mảng nhiều chiều 4. Một số thao tác trên mảng nhiều chiều 5. Truyền mảng vào hàm CSLT - Bài 7 Phan Dinh The Huan 30 4.1 Khai báo mảng nhiều chiều 1. Cú pháp: khai báo mảng k chiều: z [][][]; 2. Ví dụ: z int a[3][4]; //mảng 2 chiều: 3 dòng, 4 cột z int b[3][4][2]; //mảng 3 chiều: 3 lớp, 4 dòng, 2 cột #define M 10 #define N 20 int a[M][N]; // mảng 2 chiều có tối đa 10x20 phần tử int m,n; //số dòng, số cột thực tế CSLT - Bài 7 Phan Dinh The Huan 31 4.1 Khai báo mảng nhiều chiều 3. Khai báo và khởi gán giá trị cho mảng: • int a[2][3]={{1,2,3},{4,5,6}}; • int b[2][2]={{1,2},{3,4}}; • int c[2][2]={{1},{3,4}}; 4343654 0121321 a b c CSLT - Bài 7 Phan Dinh The Huan 32 4.2 Truy xuất mảng nhiều chiều 1. Phương pháp truy xuất trực tiếp thông qua chỉ số. Dòng 0 Dòng 1 Dòng 2 Cột 0 Cột 1 Cột 2 Cột 3 a[ 0 ][ 0 ] a[ 1 ][ 0 ] a[ 2 ][ 0 ] a[ 0 ][ 1 ] a[ 1 ][ 1 ] a[ 2 ][ 1 ] a[ 0 ][ 2 ] a[ 1 ][ 2 ] a[ 2 ][ 2 ] a[ 0 ][ 3 ] a[ 1 ][ 3 ] a[ 2 ][ 3 ] chỉ số dòng tên mảng chỉ số cột CSLT - Bài 7 Phan Dinh The Huan 33 4.3 Duyệt mảng nhiều chiều 1. Duyệt mảng a hai chiều có mxn phần tử for(i=0;i<m;i++) for(j=0;j<n;j++) //xử lý trên a[i][j] 4 5 2 [2] 678[2] 312[1] 564[0] [3][1][0] i j CSLT - Bài 7 Phan Dinh The Huan 34 4.4 Một số thao tác trên mảng nhiều chiều 1. Nhập giá trị cho mảng 2. In mảng ra màn hình 3. Tìm kiếm một phần tử x trong mảng 4. Đếm số lượng phần tử x trong mảng CSLT - Bài 7 Phan Dinh The Huan 35 4.4 Một số thao tác trên mảng nhiều chiều 1. Nhập giá trị cho mảng: nhập qua trung gian for(i=0;i<m;i++) for(j=0;j<n;j++) { printf(“Nhap a[%d][%d]=”,i,j); scanf(“%...”, &x); a[i][j]=x; } CSLT - Bài 7 Phan Dinh The Huan 36 4.4 Một số thao tác trên mảng nhiều chiều 1. Nhập giá trị cho mảng: nhập qua trung gian for(i=0;i<m;i++) for(j=0;j<n;j++) { cout<<“Nhap a[”<<i<<”][“<<j<<”]=”; cin>>x; a[i][j]=x; } x phải cùng kiểu dữ liệu với các phần tử của mảng a C++ CSLT - Bài 7 Phan Dinh The Huan 37 4.4 Một số thao tác trên mảng nhiều chiều 2. In mảng ra màn hình for(i=0;i<m;i++) { for(j=0;j<n;j++) { printf(“%...”,a[i][j]); } printf(“\n”);//xuong dong } CSLT - Bài 7 Phan Dinh The Huan 38 4.4 Một số thao tác trên mảng nhiều chiều 2. In mảng ra màn hình for(i=0;i<m;i++) { for(j=0;j<n;j++) { cout.width(4); cout<<a[i][j]; } cout<<endl;//xuong dong } C++ CSLT - Bài 7 Phan Dinh The Huan 39 4.4 Một số thao tác trên mảng nhiều chiều 3. Tìm kiếm một phần tử x trong mảng for(i=0;i<m;i++) for(j=0;j<n;j++) if(a[i][j]==x) break; if(i<m && j<n) //tim thay tai vi tri i,j else //khong tim thay Cách 1: for(k=0;k<m*n;k++) if(a[k/n][k%n]==x) break; if(k<m*n) //tim thay tai[k/n][k%n] else //khong tim thay CSLT - Bài 7 Phan Dinh The Huan 40 4.4 Một số thao tác trên mảng nhiều chiều 3. Tìm kiếm một phần tử x trong mảng int found=0; for(i=0;i<m && !found;i++) for(j=0;j<n && !found;j++) if(a[i][j]==x) found=1; if(found) //tim thay tai vi tri i,j else //khong tim thay Cách 2: dùng ‘cờ’ CSLT - Bài 7 Phan Dinh The Huan 41 4.4 Một số thao tác trên mảng nhiều chiều 4. Đếm số lượng phần tử x trong mảng int count=0; for(i=0;i<m;i++) for(j=0;j<n;j++) if(a[i][j]==x) count++; if(count) //tim thay count phan tu else //khong tim thay CSLT - Bài 7 Phan Dinh The Huan 42 4.5 Truyền mảng vào hàm #include #include #define N 10 #define M 20 void nhapMaTran(int a[][N], int m, int n); void inMaTran(const int a[][N], int m, int n); void main() { int a[M][N], m= 5, n=10; nhapMaTran(a, m, n); inMaTran(a, m, n); } CSLT - Bài 7 Phan Dinh The Huan 43 void nhapMaTran(int a[][N], int m, int n) { int i,j, x; cout<<“\nNhap ma tran:\n”; for(i=0; i<m; i++) for(j=0; i<n; i++) { cout<<“Nhap a[”<<i<<“][”<<j<<”]=”; cin>>x; a[i][j] = x; } } void inMaTran(const int a[][N], int m, int n) { int i,j; for(i=0; i<m; i++) { for(j=0; j<n; j++) { cout.width(4); cout<<a[i][j]; } cout<<endl;//xuong dong } } CSLT - Bài 7 Phan Dinh The Huan 44 Tóm tắt 1. Mảng là gì? 2. Khai báo mảng một chiều ntn? 3. Khai báo mảng nhiều chiều ntn? 4. Chuỗi ký tự là gì? Chuỗi trong C được lưu trữ như thế nào? Nhập xuất chuỗi ntn? CSLT - Bài 7 Phan Dinh The Huan 45 Ví dụ về mảng 1 chiều số nguyên 1. Tìm giá trị lớn nhất/nhỏ nhất trong mảng 2. Tính giá trị trung bình của mảng 3. Đếm số số chẵn/số số lẻ trong mảng 4. Đếm số nguyên tố trong mảng 5. Kiểm tra xem mảng có tăng dần/giảm dần 6. Tìm kiếm một giá trị trong mảng đã có thứ tự theo pp tìm kiếm nhị phân 7. Biến đổi tất cả các số âm trong mảng thành số dương. CSLT - Bài 7 Phan Dinh The Huan 46 Bài tập 1. Nhập số tiền chi tiêu của 1 sinh viên trong 12 tháng. z Tính chi tiêu trung bình của sinh viên đó. z Sinh viên đó tiêu ít nhất bao nhiêu tiền trong 1 tháng. z Sinh viên đó tiêu nhiều nhất bao nhiêu tiền trong 1 tháng. z Những tháng nào sinh viên đó tiêu tiền nhiều nhất. z Vẽ biểu đồ tiền chi tiêu hằng tháng (dạng cột). CSLT - Bài 7 Phan Dinh The Huan 47 Bài tập (tt) 2. Nhập vào một mảng 2 chiều mxn các số nguyên, hãy cho biết: z Giá trị phần lớn nhất, nhỏ nhất trong mảng. z Các dòng trong mảng có tăng dần hay không. z Đếm số lượng số nguyên tố có trong mảng. 3. Hãy tạo các ma trận vuông nxn như sau: (d)(c)(b)(a) 789101312541314151616151413 615161114116312111091211109 514131215107256788765 43211698143214321 CSLT - Bài 7 Phan Dinh The Huan 48 Bài tập (tt) 4. Viết chương trình quản lý thông tin của một nhân viên bán hàng. Thông tin của nhân viên được lưu trong một mảng 2 chiều như sau: z 12 cột tượng trưng cho 12 tháng z 2 dòng gồm: z Dòng thứ nhất: Số ngày công trong tháng z Dòng thứ hai: Số sản phẩm bán được Hãy cho biết: 1. Thu nhập trong từng tháng và tổng thu nhập trong năm của nhân viên nói trên, biết: lương 1triệu VND/tháng/26 ngày; thưởng 100ngàn/ngày thêm; hoa hồng 1000đồng/sản phẩm. 2. Trung bình, mỗi tháng nhân viên đó đi làm bao nhiêu ngày và bán được bao nhiêu sản phẩm. CSLT - Bài 7 Phan Dinh The Huan 49 Bài tập (tt) 5. Nhập vào một chuỗi ký tự, hãy thực hiện: 1. Đếm số từ có 1 ký tự, 2 ký tự, 2. Liệt kê số lần xuất hiện của các ký tự chữ cái có trong chuỗi. 3. Hãy cho biết ký tự nào xuất hiện nhiều nhất, ký tự nào xuất hiện ít nhất trong chuỗi. CSLT - Bài 7 Phan Dinh The Huan 50 Phụ lục: Bảng mã ASCII CSLT - Bài 7 Phan Dinh The Huan 51 Phụ lục: Bảng mã ASCII (tt) CSLT - Bài 7 Phan Dinh The Huan 52 Phụ lục: Mã mở rộng CSLT - Bài 7 Phan Dinh The Huan 53 Một số bài tập mở rộng 1. Mảng 1 chiều z Bài 1: Sàng Erathosten các số nguyên tố z Bài 2: Bài toán đặt vé máy bay 2. Mảng 2 chiều z Bài 1: Thực hiện các phép toán trên ma trận: giữa ma trận và một số, giữa 2 ma trận, tính định thức ma trận z Bài 2: Ma phương bậc lẻ z Bài 3: Ma trận Sudoku 9x9 CSLT - Bài 7 Phan Dinh The Huan 54 Một số bài tập ứng dụng trò chơi 1. Bàn cờ trò chơi carô mxn. Hãy xây dựng thuật toán và cài đặt hàm kiểm tra tình trạng thắng thua của bàn cờ. 2. Bàn cờ trò chơi dò mìn mxn. Hãy xây dựng thuật toán và cài đặt hàm mở ô lan truyền trong trường hợp ô được mở là một ô trống không có mìn xung quanh. 3. Bàn cờ trò chơi tetris 20x10. Hãy xây dựng thuật toán tìm dòng đầy và quét sập dòng đầy trên bàn cờ.