Tin học đại cương - Phần 2: Lập trình bằng ngôn ngữ C - Bài 4: Con trỏ và mảng

11 TIN HỌC ĐẠI CƯƠNG PHẦN 2: LẬP TRÌNH BẰNG NGÔN NGỮ C BÀI 4: CON TRỎ VÀ MẢNG VIỆN CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG SOICT 2 BÀI 4: CON TRỎ VÀ MẢNG 4.1. Con trỏ và địa chỉ  4.1.1. Tổng quan về con trỏ 4.2. Mảng  4.2.1. Khái niệm mảng  4.2.2. Khai báo và sử dụng mảng  4.2.3. Các thao tác cơ bản làm việc trên mảng 4.3. Sử dụng con trỏ làm việc với mảng 23 4.1.1. Tổng quan về con trỏ a. Địa chỉ và giá trị của một biến  Bộ nhớ như một dãy các byte nhớ.  Các byte nhớ được xác định một cách duy nhất qua một địa chỉ.  Biến được lưu trong bộ nhớ.  Khi khai báo một biến Chương trình dịch sẽ cấp phát cho biến đó một số ô nhớ liên tiếp đủ để chứa nội dung của biến. Ví dụ một biến số nguyên (int) được cấp phát 2 byte. Địa chỉ của một biến chính là địa chỉ của byte đầu tiên trong số đó. 4 4.1.1. Tổng quan về con trỏ a. Địa chỉ và giá trị của một biến (tiếp)  Một biến luôn có hai đặc tính: Địa chỉ của biến. Giá trị của biến.  Ví dụ: int i, j; i = 3; j = i + 1; Biến Địa chỉ Giá trị i FFEC 3 j FFEE 4 35 4.1.1. Tổng quan về con trỏ b. Khái niệm và khai báo con trỏ  Con trỏ là một biến mà giá trị của nó là địa chỉ của một vùng nhớ.  Khai báo con trỏ: Cú pháp khai báo một con trỏ như sau: Kieu_du_lieu *ten_bien_con_tro;  Ví dụ int i = 3; int *p; p = &i;  Một con trỏ chỉ có thể trỏ tới một đối tượng cùng kiểu. Biến Địa chỉ Giá trị i FFEC 3 p FFEE FFEC 6 BÀI 4: CON TRỎ VÀ MẢNG 4.1. Con trỏ và địa chỉ  4.1.1. Tổng quan về con trỏ 4.2. Mảng  4.2.1. Khái niệm mảng  4.2.2. Khai báo và sử dụng mảng  4.2.3. Các thao tác cơ bản làm việc trên mảng 4.3. Sử dụng con trỏ làm việc với mảng 47 4.2.1. Khái niệm mảng Mảng là một tập hợp hữu hạn các phần tử có cùng kiểu dữ liệu được lưu trữ liên tiếp nhau trong bộ nhớ. Các phần tử trong mảng có cùng tên (và cũng là tên mảng) nhưng phân biệt với nhau ở chỉ số cho biết vị trí của chúng trong mảng . c[6] -45 6 0 72 1543 -89 0 62 -3 1 6453 78 c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] 8 4.2.2. Khai báo và sử dụng mảng a. Khai báo: Cú pháp:  Kieu_du_lieu ten_mang[kich_thuoc_mang]; n phần tử của mảng c: c[ 0 ], c[ 1 ],...,c[ n – 1 ] Ví dụ: Câu lệnh: char c[12]; Khai báo một mảng: Tên là c, có 12 phần tử, Các phần tử thuộc kiểu char c[6] -45 6 0 72 1543 -89 0 62 -3 1 6453 78 c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] 59 4.2.2. Khai báo và sử dụng mảng a. Khai báo (tiếp): Mảng Hai chiều:  Mỗi phần tử của mảng cũng là một mảng khác  Cú pháp khai báo mảng 2 chiều: Kiểu_dữ_liệu tên_mảng[số_hàng][số_cột];  Ví dụ: int a[6][5]; Mảng nhiều chiều:  Vd: int b[3][4][5]; 10 4.2.2. Khai báo và sử dụng mảng b. Sử dụng mảng:  Truy cập vào 1 phần tử của mảng thông qua tên mảng và chỉ số của phần tử đó.  Cú pháp: ten_mang[chi_so_cua_phan_tu]  Ví dụ 1: int mang_nguyen[3]; mang_nguyen[0]: Phần tử thứ 1. mang_nguyen[1]: Phần tử thứ 2. mang_nguyen[2]: Phần tử thứ 3. 611 4.2.2. Khai báo và sử dụng mảng b. Sử dụng mảng (tiếp):  Ví dụ 2: int a[6][5]; a[0] là phần tử đầu tiên của mảng, là 1 mảng  Phần tử đầu tiên của mảng a[0] là a[0][0], a[2][3] sẽ là phần tử thứ 4 của phần tử mảng một chiều thứ 3 của a.  a[i][j] sẽ là phần tử thứ j+1 của a[i], mà phần tử a[i] lại là mảng thứ i+1 của a. 12 Sử dụng mảng 2 chiều: Ví dụ: int mang[n][m]; Muốn truy cập tới phẩn tử hàng thứ i+1, cột thứ j+1 ta dùng cú pháp sau: mang[i][j]; 1 2 5 9 2 22 55 56 4 212 23 34 713 4.2.3. Các thao tác cơ bản làm việc trên mảng a. Nhập dữ liệu cho mảng: Nhập dữ liệu cho từng phần tử của mảng Ví dụ: int b[10]; int i; for(i = 0; i < 10; i++) { printf(“\n Nhap gia tri cho b[%d]”, i); scanf(“%d”,&b[i]); } 14 4.2.3. Các thao tác cơ bản làm việc trên mảng a. Nhập dữ liệu cho mảng (tiếp): Trường hợp không biết mảng sẽ có bao nhiêu phần tử mà chỉ biết số phần tử tối đa có thể có của mảng. Ví dụ: int a[100];//Khai bao mang, so phan tu toi da la 100 int n; // Bien luu giu so phan tu thuc su cua mang int i; printf(“\n Cho biet so phan tu cua mang: “); scanf(“%d”,&n); for(i = 0; i < n; i++) { printf("\n a[%d] = ", i); scanf("%d",&a[i]); } 815 4.2.3. Các thao tác cơ bản làm việc trên mảng a. Nhập dữ liệu cho mảng (tiếp): Mảng có thể được khởi tạo giá trị ngay khi khai báo int a[4] = {4, 9, 22, 16}; float b[3] = {40.5, 20.1, 100}; char c[5] = {‘h’, ‘e’, ‘l’, ‘l’, ‘o’};  Câu lệnh thứ nhất có tác dụng tương đương với 4 lệnh gán: a[0] = 4; a[1] = 9; a[2] = 22; a[3] = 16; 16 b. Xuất dữ liệu chứa trong mảng: #include #include #define KT 6 void main() { int a[KT]; int i, k; //Nhap gia tri cho cac phan tu mang a tu ban phim for(i = 0; i < KT; i++) { printf(“\n a[%d] = “, i); scanf(“%d”, &a[i]); } printf("\nBat dau hien thi gia tri cac phan tu\n"); printf(“\n a[3] = %d”, a[3]); //Hien thi gia tri tat ca cac phan tu //Moi phan tu tren 1 dong for(i = 0; i < KT; i++) printf(“\n%d”, a[i]); 917 b. Xuất dữ liệu chứa trong mảng: printf(“\n”); // Xuong dong moi // Hien thi gia tri cua tat ca cac phan tu mang a // tren 1 dong, cac phan tu cach nhau 1 dau tab for(i = 0; i < KT; i++) printf(“%d\t“, a[i]); // Hien thi k phan tu tren mot dong printf(“\n Cho biet gia tri cua k = “); scanf(“%d”,&k); for(i = 0; i < KT; i++) { printf(“%d “, a[i]); if((i+1)%k == 0)//xuong dong khi da hien thi k ptu printf(“\n”); } } 18 Kết quả: 10 19 c. Tìm các phần tử có giá trị lớn nhất, nhỏ nhất #define KT 100 int a[KT]; max = a[0]; Dùng vòng lặp for so sánh max với phần tử có chỉ số từ 1, 2,, n-1 của mảng a. 20 c. Tìm các phần tử có giá trị lớn nhất, nhỏ nhất int a[100]; int i, n; int max; printf("\n Cho biet so phan tu cua mang: "); scanf("%d",&n); for(i = 0; i < n; i++) { printf("\n a[%d] = ",i); scanf("%d",&a[i]); } 11 21 max = a[0]; //Lan luot so sanh voi cac phan //tu con lai trong mang for(i = 1; i < n; i++) if(max < a[i]) max = a[i]; printf("\n Phan tu lon nhat trong mang la: %d", max); 22 4.2.3. Các thao tác cơ bản làm việc trên mảng Tìm kiếm trên mảng Sắp xếp mảng 12 23 Tìm kiếm trên mảng Bài toán:  Viết chương trình yêu cầu người dùng nhập vào 10 số thực  Cho phép người dùng nhập vào 1 giá trị k (để tìm kiếm) 24 Tìm kiếm trên mảng (tiếp) Yêu cầu:  Hiển thị dãy số người dùng vừa nhập.  Hiển thị lên màn hình: Số luợng phần tử (trong dãy vừa nhập) có giá trị bằng k. Vd: có 3 phần tử có giá trị bằng k thì hiện lên: Trong dãy vừa nhập có 3 số có giá trị bằng k) 13 25 Tìm kiếm trên mảng (tiếp) Cấu trúc dữ liệu:  Dùng mảng để lưu trữ dãy số do người dùng nhập vào. Giải thuật:  Duyệt lần lượt các phần tử của mảng và đếm xem có bao nhiêu phần tử có giá trị bằng k. 26 Tìm kiếm trên mảng (tiếp) Các biến chính cần dùng:  Mảng để lưu trữ 10 phần tử: m  Biến để lưu số lượng phần tử bằng k: dem 14 27 Tìm kiếm trên mảng (tiếp) #include #include float m[10]; float k; int i, dem; 28 void main () { clrscr(); //nhap du lieu for(i=0;i<10;i++) { printf("\n Nhap gia tri cho m[%d]:",i); scanf("%f ",&m[i]); } 15 29 printf("\nHay nhap vao mot so de tim kiem:"); scanf("%f", &k); // Đếm số phần tử có giá trị bằng k dem=0; for (i=0;i<10;i++) if (m[i]==k) dem++; 30 // In ra dãy vừa nhập printf("\n Day so vua duoc nhap vao :"); for (i=0;i<10;i++) printf("%-8.3f",m[i]); // In ra số phần tử tìm được printf("\n So phan tu co gia tri bang %8.3f la:%d",k,dem); getch(); } 16 31 32 Tìm kiếm trên mảng (tiếp) Mở rộng:  Cho phép người dùng nhập vào số lượng phần tử của mảng.  Tìm kiếm số lượng các số thỏa mãn tính chất nào đó: vd: chẵn, lẻ, chia hết cho 5, nguyên tố  Tìm kiếm kết hợp với thao tác trên các giá trị tìm được: tính tổng các số âm, các số nguyên tố, 17 33 Bài toán sắp xếp Bài toán: Viết chương trình cho phép nhập vào n số kiểu int. (n do người dùng nhập vào, tối đa là 100, chưa cần kiểm tra đầu vào n) 1)Hiển thị dãy người dùng đã nhập ra màn hình 2) Sắp xếp dãy số đó theo thứ tự không giảm 3)Hiển thị dãy đã sắp xếp ra màn hình. 34 Bài toán sắp xếp (tiếp) Cấu trúc dữ liệu: Dùng mảng để lưu trữ dãy số: m Giải thuật: Selection Sort (Sắp xếp kiểu lựa chọn):  n là số phần tử của dãy  Thực hiện n-1 bước: 18 35 Bài toán sắp xếp (tiếp) Giải thuật (tiếp):  Bước 1: Tìm phần tử nhỏ nhất trong n phần tử và đặt vào vị trí của phần tử đầu tiên  Bước 2: Tìm phần tử nhỏ thứ 2 trong n phần tử và đặt vào vị trí của phần tử thứ 2 ~ tìm phần tử nhỏ nhất trong n-1 phần tử còn lại và đặt vào vị trí của phần tử thứ 2. 36 Bài toán sắp xếp (tiếp) Giải thuật (tiếp):  Bước 3: tìm phần tử nhỏ nhất trong n-2 phần tử còn lại và đặt vào vị trí của phần tử thứ 3. ..  Bước n-1: tìm phần tử nhỏ nhất trong 2 phần tử còn lại và đặt vào vị trí thứ n-1. 19 37 Bài toán sắp xếp (tiếp) Các biến và kỹ thuật sử dụng:  Mảng, các biến để thực hiện vòng lặp  Sử dụng bài toán tìm phần tử nhỏ nhất và lưu chỉ số của phần tử đó: chiso  Thực hiện đưa một phần tử chiso về vị trí x sử dụng thuật toán đổi chỗ. 38 Mã chương trình Bài toán sắp xếp #include #include int m[100]; int n,i,j, chiso; void main () { clrscr(); printf("Cho biet so phan tu cua mang:"); scanf("%d",&n); 20 39 //Nhập dữ liệu cho dãy for(i=0;i<n;i++) { printf("\n Nhap gia tri cho m[%d]:",i); scanf("%d",&m[i]); } 40 //In dãy vừa được nhập printf("\n Day truoc khi sap xep:\n"); for (i=0;i<n;i++) printf("%5d",m[i]); 21 41 // Bắt đầu qúa trình sắp xếp for (i=0;i<n-1;i++) { //tìm số nhỏ nhất trong n-i+1 số chiso=i; for (j=i+1;j<n;j++) if (m[chiso] > m[j]) chiso = j; printf(“Phan tu nho nhat trong so cac phan tu tu %d den %d la %d”,i+1,n-1,m[chiso]); getch(); 42 //đưa số nhỏ nhất trong n-i+1 //số về đúng vị trí của nó int tam; if (chiso!=i) { tam=m[i]; m[i]=m[chiso]; m[chiso]=tam; } } 22 43 //In giá trị của mảng sau khi xếp printf("\nMang sau khi sap xep theo thu tu khong giam:\n"); for (i=0;i<n;i++) printf("%5d",m[i]); getch(); } 44 23 45 Bài toán sắp xếp (tiếp) Mở rộng: Kiểm tra số lượng của dãy: Dùng vòng lặp while Sắp xếp không tăng, sắp xếp với số thực, ký tự. 46 Bài tập 1. Viết chương trình  Nhập vào một số nguyên n (n < 10)  Nhập n số nguyên lưu vào một mảng.  Đưa ra màn hình phần tử lớn nhất và nhỏ nhất  Tính và đưa ra màn hình tổng các số vừa nhập. 2. Viết chương trình tính tổng bình phương của các số âm trong một mảng các số nguyên. 24 47 3. Cho một mảng các số thực nhập từ người dùng. Tính tổng các phần tử cực đại (phần tử cực đại địa phương là phần tử lớn hơn các phần tử ngay trước và ngay sau nó). Ví dụ như các số in đậm trong dãy dưới đây. 1 5 2 6 3 5 1 8 6 Xét từ phần từ thứ 2 đến phần tử áp chót 48 4. Viết chương trình xóa phần tử tại vị trí thứ k trong một mảng n phần tử (0<=k<n). 5. Viết chương trình nhập vào một mảng số tự nhiên. Hãy in ra màn hình: Dòng 1 : gồm các số lẻ, tổng cộng có bao nhiêu số lẻ. Dòng 2 : gồm các số chẵn, tổng cộng có bao nhiêu số chẵn. 25 49 Câu hỏi?