Chương 5: Mảng, chuỗi và con trỏ

TIN HỌC ĐẠI CƯƠNG Lý thuyết: 6 buổi Thực hành: 8 buổi GVHD: Dương Khai Phong Email: khaiphong@gmail.com Ngôn ngữ lập trình: C NỘI DUNG CÁC BUỔI HỌC 1. Tổng quan về C (chương 1,2) 2. Các cấu trúc điều khiển trong C (chương 3) 3. Hàm và cấu trúc chương trình (chương 4) 4. Mảng, chuỗi và con trỏ (chương 5) 5. Kiểu cấu trúc, đệ qui, tập tin (chương 6,7,8) 6. Ôn tập CHƯƠNG 5: MẢNG, CHUỔI VÀ CON TRỎ 1. Khái niệm về mảng. 2. Các bài toán liên quan đến mảng. 3. Chuỗi ký tự. 4. Con trỏ và bộ nhớ. 5. Mối liên hệ giữa mảng,chuỗi,con trỏ và hàm. 1. KHÁI NIỆM VỀ MẢNG * Xét ví dụ: viết CT quản lí điểm trung bình của 100 sinh viên. #include “stdio.h” #include “conio.h” void main() { float dtb1; float dtb2; .. float dtb100; } Nhận xét:  Khai báo biến quá nhiều => khó quản lí.  Khó truy xuất và thao tác. … 1. KHÁI NIỆM VỀ MẢNG a/ Khái niệm mảng: là một tập hợp nhiều biến có cùng kiểu dữ liệu và cùng tên, khi đó mỗi phần tử của mảng được truy xuất thông qua chỉ số. b/ Cú pháp khai báo mảng: * Ví dụ: int a[10], b[3][2]; => Dòng lệnh trên khai báo hai mảng: - Mảng a là mảng 1 chiều có 10 phần tử số nguyên - Mảng b là mảng 2 chiều (3 dòng, 2 cột) có 6 phần tử số nguyên (mảng 2 chiều còn gọi là ma trận) * Ví dụ: vừa khai báo vừa khởi tạo mảng: (xem trang 116) int a[3]={2,5,7}; 1. KHÁI NIỆM VỀ MẢNG c/ Chỉ số của mảng: phải là 1 giá trị kiểu int không vượt quá kích thước của mảng và bắt đầu từ 0. * Ví dụ: int a[5] => Dòng lệnh trên cho biết:  Mảng a gồm 5 phần tử có kiểu số nguyên  Chỉ số các phần tử được đánh số từ 0..4 (a[0] , a[1] , a[2] , a[3] , a[4]) => Như vậy, để truy xuất phần tử của mảng ta dùng cú pháp: Tên_mảng[chỉ_số_của_mảng] * Ví dụ: int so,a[5]; a[0] = 5; // gán giá trị 5 cho phần tử thứ 0 của mảng. a[3] = 8; // gán giá trị 8 cho phần tử thứ 3 của mảng. so = a[3]; // lấy giá trị của phần tử thứ 3 gán cho biến so. 2. CÁC BÀI TOÁN LIÊN QUAN ĐẾN MẢNG a/ Nhập / xuất mảng b/ Tìm kiếm giá trị trong mảng c/ Sắp xếp mảng tăng dần / giảm dần d/ Sửa giá trị cho phần tử thứ i trong mảng e/ Xóa phần tử thứ i trong mảng 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG a/ Nhập / xuất mảng: // Nhập mảng … void main() { int a[5]; // Nhap gia tri cho cac ptu for (int i=0;i<5;i++) { printf(“a[%d] = ”,i+1); scanf(“%d”,&a[i]); } } // Xuất mảng … void main() { int a[5]; // Da nhap xong mang a // Xuat cac ptu mang a for (int i=0;i<5;i++) { printf(“%d \t ”,a[i]); } } (mảng 1 chiều) 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG a/ Nhập / xuất mảng: // Nhập mảng void main() { int a[3][2]; // Nhap gia tri cho cac ptu for (int i=0;i<3;i++) for (int j=0;j<2;j++) { printf(“a[%d] [%d]= ”,i+1,j+1); scanf(“%d”,&a[i][j]); } } // Xuất mảng void main() { int a[3][2]; // Da nhap xong mang a // Xuat cac ptu mang a for (int i=0;i<3;i++) { for (int j=0;j<2;j++) printf(“%d \t”,a[i][j]); printf(“\n”); } } (mảng 2 chiều – ma trận) Lưu ý: nếu là mảng 2 chiều số thực thì ta bắt buộc phải nhập thông qua một biến phụ khác rồi mới gán cho a[i][j] (xem trang 114) 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG b/ Tìm kiếm giá trị trong mảng: Có 2 thuật toán dùng để tìm kiếm:  Tìm kiếm tuyến tính  Tìm kiếm nhị phân (học ở môn CTDL1) * Tìm kiếm tuyến tính:  Ý tưởng: bắt đầu từ phần tử đầu tiên (phần tử thứ 0) và duyệt qua tất cả các phần tử, nếu tìm thấy phần tử bằng khóa x thì báo tìm thấy và dừng, ngược lại báo không tìm thấy.  Thuật toán: • B1: i=0; // bắt đầu từ phần tử đầu tiên • B2: so sánh a[i] với x, có 2 khả năng  a[i] = x : tìm thấy và dừng  a[i] x : sang B3 • B3: i=i=+1 // xét phần tử kế tiếp trong mảng  Nếu i>n: hết mảng, không tìm thấy và dừng  Ngược lại : lặp lại B2 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG b/ Thuật toán tìm kiếm tuyến tính: Giả sử mảng a gồm 5 phần tử: 2 3 7 6 5 Kiểm tra x = 6 có trong mảng a hay không? 2 3 7 6 5 0 1 2 3 4 Chỉ số mảng x=6 i x=6 Dừng 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG b/ Thuật toán tìm kiếm tuyến tính: void main() { int a[5], so; // Da nhap xong mang a printf(“Nhap gia tri can tim: ”); scanf(“%d”,&so); for (int i=0;i<5;i++) { if (a[i]==so) break; } if (i<n) printf(“Tim thay %d trong mang”,so); else printf(“Khong tim thay %d trong mang”,so); } 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Sắp xếp mảng tăng dần / giảm dần: Có rất nhiều thuật toán dùng để sắp xếp:  Đổi chỗ trực tiếp (Interchange Sort)  Nổi bọt (Bubble Sort)  Chọn trực tiếp (Selection Sort)  Chèn trực tiếp (Insert Sort)  … => xem từ trang 162 – 167 (hoặc giáo trình môn Cấu trúc dữ liệu 1) 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Sắp xếp mảng tăng dần: Đổi chỗ trực tiếp - Interchange Sort Ý tưởng: • B1: bắt đầu từ phần tử đầu tiên của mảng, tìm phần tử có giá trị nhỏ hơn để đổi chỗ (hoán vị) với nhau, thực hiện tiếp tục cho các phần tử còn lại cho đến khi phần tử đầu tiên là phần tử nhỏ nhất. • B2: lặp lại bước 1 nhưng bắt đầu bằng phần tử kế tiếp… => Nhận xét: từ ý tưởng trên cho thấy ta cần 2 vòng lặp for lồng nhau để thực hiện việc sắp xếp. 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Sắp xếp mảng tăng dần: Đổi chỗ trực tiếp - Interchange Sort Thuật toán: • B1: i = 0 // bắt đầu từ đầu mảng • B2: j=i+1; // tìm các phần tử a[j]i; • B3: Trong j<n thực hiện Nếu a[j]<a[i] thì hoán_vị(a[i],a[j]) j=j+1; • B4: i=i+1; Nếu i<n-1: lặp lại bước 2 Ngược lại: dừng 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Sắp xếp mảng tăng dần: (Đổi chỗ trực tiếp - Interchange Sort ) Giả sử mảng a gồm 5 phần tử: 6 7 3 2 5 0 1 2 3 4 Chỉ số mảng i j 6 7 3 2 5 j=i+1 j 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG void hoanvi(int &a,int &b); void main() { int a[5], so; // Da nhap xong mang a for (int i=0;i<4;i++) for (int j=i+1;j<5;j++) { if (a[j]<a[i]) hoanvi(a[j],a[i]); } } c/ Sắp xếp mảng tăng dần: (Đổi chỗ trực tiếp - Interchange Sort ) 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Sửa giá trị cho phần tử thứ i trong mảng:  Các bước thực hiện: • B1: xác định chỉ số của phần tử cần sửa giá trị trong mảng. • B2: thực hiện cập nhật lại giá trị mới. Ví dụ: thay thế phần tử có giá trị 3 trong mảng (2,3,7,6,5) bằng giá trị 5. 2 3 7 6 5 0 1 2 3 4 Chỉ số mảng x=3 i 5 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG c/ Xóa phần tử thứ i trong mảng:  Xét ví dụ: xóa phần tử có giá trị 7 trong mảng (2,3,7,6,5) 0 1 2 3 4Chỉ số mảng x=7 i Bước 1: xác định chỉ số k của phần tử có giá trị = 7. Bước 2: di chuyển các phần tử bên phải của chỉ số k về một chỉ số. Bước 3: cập nhật lại kích thước của mảng n=n-1. n=54 2 3 7 6 5 3. CHUỖI KÝ TỰ a/ Khái niệm: • Chuỗi ký tự là một trường hợp riêng của mảng một chiều mà mỗi phần tử trong mảng là một ký tự. Tuy nhiên, khác với mảng ký tự, chuỗi ký tự được kết thúc bằng một ký hiệu đặc biệt là NULL có mã ASCII bằng không - 0 (ký hiệu ‘\0’). => Như vậy một chuỗi ký tự được khai báo là char chuoi[20] chỉ có thể chứa được 19 ký tự vì ký tự cuối cùng phải là ‘\0’. Ví dụ: char s1=“HELLO”, khi đó trong bộ nhớ sẽ lưu như sau: char s2=“”, chuỗi rỗng khi đó trong bộ nhớ sẽ lưu như sau: H E L L O \0 \0 3. CHUỖI KÝ TỰ b/ Các vấn đề liên quan đến chuỗi: • Nhập / xuất chuỗi (xem trang 44,125) • Các phép toán không tồn tại đối với chuỗi:  So sánh: == , != , …  Gán nội dung chuỗi: s1=s2; => Để giải quyết các vấn đề này, ta cần sử dụng các hàm chuẩn trong thư viện “string.h”. (xem trang 123) 3. CHUỖI KÝ TỰ * Ví dụ: các hàm xử lý chuỗi thường dùng void main() { char s1[25],s2=“xin chao”; int chieudai; strcpy(s1, s2); // sao chép nội dung từ s2 sang s1 chieudai=strlen(s1); // lấy chiều dài trong chuỗi , kq: 8 ký tự strcat(s1, “ cac ban”); // nối thêm cho s1 chuỗi “ cac ban” if (strcmp(s1,s2)==0) // so sánh s1,s2: (0: s1=s2, -1: s1s2) printf(“s1 bang s2”); s1[4]=‘C’; // thay thế ký tự c trong chuỗi thành ‘C’ } 4. CON TRỎ VÀ BỘ NHỚ a/ Khái niệm con trỏ b/ Các phép toán trên con trỏ c/ Con trỏ và cấp phát vùng nhớ 4. CON TRỎ VÀ BỘ NHỚ a/ Khái niệm con trỏ: • Con trỏ là một kiểu biến đặc biệt dùng để lưu địa chỉ vùng nhớ. • Cú pháp khai báo: *Tên_con_trỏ; • Ví dụ: int a=3,*p; p=&a; // con trỏ p trỏ tới địa chỉ của đối tượng là biến a. *p=5 // con trỏ p cập nhật lại giá trị của đối tượng là biến a = 5 4. CON TRỎ VÀ BỘ NHỚ b/ Các phép toán trên con trỏ: • Các phép toán 1 ngôi (xem trang 128)  Toán tử &: lấy địa chỉ của đối tượng.  Toán tử *: truy nhập đến nội dung đối tượng. • Các phép toán khác trên con trỏ (xem trang 130)  Phép gán =: ta có thể thực hiện phép gán cho 2 con trỏ có cùng kiểu (nếu khác kiểu thì phải ép kiểu).  Phép truy nhập bộ nhớ.  Phép so sánh. 4. CON TRỎ VÀ BỘ NHỚ c/ Con trỏ và cấp phát vùng nhớ: (xem trang 155) * Xét ví dụ: viết CT quản lí điểm của 1000 sinh viên void main() { float dtb[1000]; … }  Nhận xét: Khi chương trình thực thi thì máy tính luôn luôn cấp một vùng nhớ để chứa một mảng có kích thước 1000 phần tử float => lãng phí bộ nhớ.  Khi CT cần gia tăng số lượng học viên lên 5000 sinh viên thì người lập trình phải chỉnh sửa lại code. 4. CON TRỎ VÀ BỘ NHỚ c/ Con trỏ và cấp phát vùng nhớ: (xem trang 155) => Để giải quyết bài toán này ta dùng cấp phát vùng nhớ động khi thực hiện chương trình. void main() { float *dtb; int n; printf(“Cho biet so luong:”); scanf(“%d”,&n); dtb=(float *)malloc(n*sizeof(float)); if (dtb==NULL) { printf(“Khong du vung nho”); exit(1); } free (dtb); } Lệnh sizeof cho biết kích cỡ theo byte của một kiểu dữ liệu (int,char,float,..) Lệnh free giải phóng vùng nhớ Lệnh malloc cấp phát vùng nhớ để lưu giữ n số thực