›
›

Bài giảng Lập trình C - Chương 1: Mảng một chiều - Trần Minh Thái

pptx 121 trang cucquyet12 5170
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lập trình C - Chương 1: Mảng một chiều - Trần Minh Thái", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_lap_trinh_c_chuong_1_mang_mot_chieu_tran_minh_thai.pptx

Nội dung text: Bài giảng Lập trình C - Chương 1: Mảng một chiều - Trần Minh Thái

  1. Lập trình C Chương 1. Mảng một chiều (6 tiết) Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: 09/11/2016 1
  2. Nội dung 1. Khái niệm kiểu dữ liệu mảng một chiều 2. Khai báo 3. Các thao tác nhập/ xuất mảng 4. Kỹ thuật tìm kiếm, liệt kê giá trị trong mảng 5. Kỹ thuật xóa, chèn 6. Chuỗi ký tự và các thao tác xữ lý cơ bản 2
  3. KHÁI NIỆM VÀ KHAI BÁO 3
  4. Khái niệm • Mảng được cấp phát bộ nhớ liên tục và bao gồm nhiều biến thành phần • Mỗi biến thành phần có cùng KDL và cùng tên Giá trị 0 1 2 3 4 5 6 7 8 9 Vị trí Vị trí được tính từ 0 4
  5. Khai báo [ ] ; Ví dụ int a[100]; //Khai bao mang so nguyen a toi da 100 phan tu float b[50]; //Khai bao mang so thuc b toi da 50 phan tu char str[30]; //Khai bao mang ky tu str toi da 30 ky tu Nhằm thuận tiện cho việc viết chương trình, ta nên định nghĩa hằng số MAX ở đầu chương trình – là kích thước tối đa của mảng - như sau: #define MAX 100 int main() { int a[MAX], b[MAX]; //Các lệnh return 0; } 5
  6. Khai báo, gán giá trị ban đầu Gán từng phần tử int a[5] = { 3, 6, 8, 1, 12 }; Giá trị 3 6 8 1 12 Vị trí 0 1 2 3 4 Gán toàn bộ phần tử trong mảng có cùng giá trị int a[8] = { 3 }; Giá trị 3 3 3 3 3 3 3 3 Vị trí 0 1 2 3 4 5 6 7 6
  7. Truy xuất giá trị TênMảng [vị trí cần truy xuất] int main() Vị trí 3 { int a[5] = { 3, 6, 8, 11, 12 }; printf("Gia tri mang tai vi tri 3 = ", a[3]); getch(); return 0; } Kết quả: Gia tri mang tai vi tri 3 = 11 7
  8. Các thao tác trên mảng 1. Nhập 2. Xuất (liệt kê) 3. Tìm kiếm 4. Đếm 5. Sắp xếp 6. Kiểm tra mảng thỏa điều kiện cho trước 7. Tách/ ghép mảng 8. Chèn / xóa 8
  9. THAO TÁC NHẬP VÀ XUẤT 9
  10. Nhập mảng a[0] a[1] a[2] a[3] a[4] a[5] a[n-1] Nhập a[0] Nhập a[1] Nhập a[2] ➔ Nhập a[i], với 0 ≤ i ≤ n-1 Nhập a[n-1] 10
  11. Ví dụ nhập và xuất mảng số nguyên #define MAX 100 void NhapKichThuoc(int &n) { printf("Nhap vao kich thuoc mang: "); scanf("%d", &n); } void NhapMang(int a[], int n) { for (int i = 0; i < n; i++) { printf("* Nhap vao phan tu tai vi tri %d: ", i); scanf("%d", &a[i]); } } 11
  12. void XuatMang(int a[], int n) { for(int i=0; i<n;i++) { printf("%d\t", a[i]); } } int main() { int a[MAX], n; NhapKichThuoc(n); NhapMang(a, n); printf("Cac gia tri trong mang a:\n"); XuatMang(a, n); getch(); return 0; } 12
  13. Phát sinh ngẫu nhiên giá trị nguyên • Sử dụng thư viện hàm và • Dùng hàm srand() trong hàm main() trước khi gọi hàm phát sinh: để khởi tạo bộ giá trị ngẫu nhiên • Dùng hàm rand()%k để phát sinh số ngẫu nhiên: có giá trị từ 0 đến k-1 13
  14. Ví dụ: Chương trình tạo mảng số nguyên có giá trị ngẫu nhiên từ 1 đến MAX #include #include #include #include #pragma warning(disable: 4996); #define MAX 100 void NhapKichThuoc(int &n); void PhatSinh(int a[], int n); void XuatMang(int a[], int n); 14
  15. void NhapKichThuoc(int &n) { printf("Nhap vao kich thuoc mang: "); scanf("%d", &n); } void PhatSinh(int a[], int n) { for (int i = 0; i < n; i++) { a[i] = rand() % MAX + 1; } } void XuatMang(int a[], int n) { for(int i=0; i<n;i++) { printf("%d\t", a[i]); } } 15
  16. int main() { int a[MAX], n; NhapKichThuoc(n); srand((unsigned int)time(NULL)); PhatSinh(a, n); printf("Cac gia tri trong mang a:\n"); XuatMang(a, n); getch(); return 0; } 16
  17. Bài tập Cho mảng một chiều số nguyên a, kích thước n. Hãy viết các hàm: 1. Phát sinh giá trị các phần tử ngẫu nhiên theo thứ tự tăng dần cho a. 2. Phát sinh giá trị các phần tử ngẫu nhiên có giá âm và dương. 17
  18. XUẤT CÓ ĐIỀU KIỆN 18
  19. Liệt kê các phần tử thỏa đk cho trước Mẫu 1: void LietKeXXX( a[], int n) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) Xuất a[i]; } 19
  20. Liệt kê các phần tử thỏa đk cho trước Mẫu 2: void LietKeXXX( a[], int n, int x) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện so với x) Xuất a[i]; } 20
  21. Ví dụ 1: Liệt kê các phần tử có giá trị chẵn trong mảng số nguyên void LietKeChan(int a[], int n) { for (int i = 0; i x) printf(“%d\t”, a[i]); } 21
  22. Ví dụ 3: Chương trình nhập vào mảng một chiều số nguyên a, kích thước n. In ra các phần tử có giá trị lớn hơn x có trong mảng #define MAX 100 void NhapKichThuoc(int &n); void NhapMang(int a[], int n); void XuatMang(int a[], int n); void LietKeLonHonX(int a[], int n, int x); void NhapKichThuoc(int &n) { prinft(“Nhap vao kich thuoc mang: “); scanf(“%d”, &n); } void NhapMang (int a[], int n) { for (int i = 0; i < n; i ++) { printf(“Nhap phan tu tai vi tri %d: “, i); scanf(“%d”, &a[i]); } } 22
  23. void XuatMang (int a[], int n) { for (int i = 0; i x) printf(“%d\t”, a[i]); } 23
  24. int main() { int a[MAX], n, x; NhapKichThuoc(n); NhapMang(a, n); printf("Cac phan tu cua mang:\n"); XuatMang(a, n); printf("Nhap gia tri x: “); scanf(“%d”, &x); printf("Cac phan tu co gia tri lon hon %d:\n", x); LietKeLonHonX(a, n, x); getch(); return 0; } 24
  25. Bài tập tại lớp Cho mảng số nguyên a, gồm n phần tử, viết chương trình gồm các hàm thực hiện các yêu cầu sau: 1. Nhập vào kích thước mảng (0<n<=100), nếu nhập không thỏa miền giá trị thì cho phép người dùng nhập lại 2. Nhập các giá trị vào mảng một chiều a 3. Xuất các phần tử là bội số của 5 trong mảng a 4. Xuất các phần tử là số nguyên tố trong mảng a 5. Hàm main() để gọi thực hiện các yêu cầu từ 1 đến 4 25
  26. THAO TÁC ĐẾM SỐ LƯỢNG 26
  27. Đếm số lượng phần tử Mẫu 1: int DemXXX( a[], int n) { int d = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) d++; return d; } 27
  28. Mẫu 2: int DemXXX( a[], int n, int x) { int d = 0; for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện so với x) d++; return d; } 28
  29. Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố trong mảng số nguyên int LaSNT(int k) int DemSNT(int a[], int n) { { int d = 0; int d = 0; for (int i = 1; i <= k; i++) for (int i = 0; i<n; i++) { { if (k % i == 0) if (LaSNT(a[i]) ==1) { { d++; d++; } } } } if(d == 2) return 1; return d; return 0; } } 29
  30. Ví dụ 2: Đếm các phần tử có giá trị nhỏ hơn x trong mảng số nguyên int DemNhoHonX(int a[], int n, int x) { int d = 0; for (int i = 0; i<n; i++) if (a[i] < x) d++; return d; } 30
  31. Ví dụ 3: Chương trình nhập vào mảng một chiều số nguyên a, kích thước n. Đếm số lượng các phần tử là số nguyên tố có trong mảng #define MAX 100 void NhapKichThuoc(int &n); void NhapMang(int a[], int n); void XuatMang(int a[], int n); int LaSNT(int k); int DemSNT(int a[], int n); void NhapKichThuoc(int &n){ prinft(“Nhap vao kich thuoc mang: “); scanf(“%d”, &n); } void NhapMang (int a[], int n){ for (int i = 0; i < n; i ++) { printf(“Nhap phan tu tai vi tri %d: “, i); scanf(“%d”, &a[i]); } } 31
  32. void XuatMang (int a[], int n) { for (int i = 0; i < n; i ++) printf(“%d\t”, a[i]); int DemSNT(int a[], int n) } { int d = 0; int LaSNT(int k) { for (int i = 0; i<n; i++) int d = 0; if (LaSNT(a[i]) ==1) for (int i = 1; i <= k; i++) d++; if (k % i == 0) return d; d++; } if (d == 2) return 1; return 0; } 32
  33. int main() { int a[MAX], n, kq; NhapKichThuoc(n); NhapMang(a, n); printf("Cac phan tu cua mang:\n"); XuatMang(a, n); kq = DemSNT(a, n); if(kq==0) printf("Khong co so nguyen to trong mang“); else printf("So luong so nguyen to la: %d“, kq); getch(); return 0; } 33
  34. Bài tập Cho mảng một chiều số nguyên a, kích thước n. Hãy viết các hàm: 1. Đếm số lượng các phần tử có giá trị lẻ. 2. Đếm những phần tử có giá trị là bội số của 3. 34
  35. THAO TÁC TÌM KIẾM 35
  36. Tìm phần tử x • Ý tưởng Lần lượt so sánh x với phần tử thứ nhất, thứ hai, của mảng a cho đến khi gặp được phần tử cần tìm, hoặc đã tìm hết mảng mà không thấy x • Minh họa tìm x =10 10 ĐãChưa tìm thấyhết tại 7 5 12 41 10 32 13 9 15 3 vịmảng trí 5 1 2 3 4 5 6 7 8 9 10 • Minh họa tìm x =25 Chưa hết 25 Đã hết mảngmảng 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 36
  37. Code minh họa tìm x trong mảng số nguyên (nếu x không xuất hiện trong mảng trả về -1) int TimVTX(int a[], int n, int x) { for (int i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; } 37
  38. Bài tập Cho mảng một chiều số nguyên a, kích thước n. Viết các hàm sau: 1. Tìm vị trí xuất hiện cuối cùng của phần tử có giá trị x nếu có. 2. Tìm vị trí phần tử có giá trị âm xuất hiện đầu tiên trong mảng. 38
  39. Tìm vị trí phần tử nhỏ nhất? Giả sử cần tìm vị trí phần tử nhỏ nhất trong dãy số sau ? 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 39
  40. Bước 1: Giả sử vị trí phần tử nhỏ nhất là 1 (vtmin), phần tử này có giá trị 10 vtmin 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 40
  41. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 5 nhỏ hơn 10 nên cập nhật vtmin vị trí min 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 41
  42. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 7 lớn hơn 5 nên không cập vtmin nhật vị trí min 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 42
  43. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 3 nhỏ hơn 5 nên cập nhật vtmin vị trí min 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 43
  44. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 9 lớn hơn 3 nên không cập nhật vị trí min vtmin 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 44
  45. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 1 nhỏ hơn 3 nên cập nhật vị trí min vtmin 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 45
  46. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 15 lớn hơn 1 nên không cập nhật vị trí min vtmin 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 46
  47. Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin 2 lớn hơn 1 nên không cập nhật vị trí min vtmin 15 10 9 5 7 3 1 2 1 2 3 4 5 6 7 8 47
  48. Code minh họa tìm vị trí phần tử có giá trị nhỏ nhất trong mảng số nguyên int TimVTMin(int a[], int n) { int vtmin = 0; for (int i = 1; i < n; i++) { if (a[i] < a[vtmin]) vtmin = i; } return vtmin; } 48
  49. Bài tập Cho mảng một chiều số nguyên a, kích thước n. Hãy viết hàm: 1. Tìm vị trí phần tử có giá trị lớn nhất 2. Tìm giá trị phần tử lớn nhất 3. Tìm vị trí phần tử có giá trị âm lớn nhất 49
  50. THAO TÁC TÍNH TOÁN 50
  51. Tính tổng, giá trị trung bình có điều kiện Mẫu tính tổng: TongXXX( a[], int n) { s = 0; for (int i = 0; i<n; i++) { if (a[i] thỏa điều kiện) s += a[i]; } return s; } 51
  52. Mẫu tính trung bình: float TrungBinhXXX( a[], int n) { s = 0; int d = 0; for (int i = 0; i<n; i++) { if (a[i] thỏa điều kiện) { s += a[i]; d ++; } } if (d==0) return 0; return (float) s / d; } 52
  53. Ví dụ 1: Tính tổng các phần tử có giá trị lẻ trong mảng trong mảng số nguyên int TongLe(int a[], int n) { int s = 0; for (int i = 0; i<n; i++) { if (a[i] %2!=0) s += a[i]; } return s; } 53
  54. Ví dụ 2: Tính giá trị trung bình các phần tử có giá trị âm trong mảng số nguyên float TrungBinhAm(int a[], int n) { long s = 0; int d = 0; for (int i = 0; i<n; i++) { if (a[i] < 0) { s += a[i]; d++; } } if (d == 0) return 0; return (float)s / d; } 54
  55. SẮP XẾP MẢNG THEO THỨ TỰ 55
  56. Mẫu phương thức sắp thứ tự tăng: void SapTang( a[], int n) { for (int i = 0; i a[j]) HoanVi(a[i], a[j]); } } void HoanVi( &a, &b) { tam = a; a = b; b = tam; } 56
  57. THAO TÁC KIỂM TRA GIÁ TRỊ MẢNG CÓ THỎA ĐIỀU KIỆN 57
  58. Kiểm tra tồn tại Kiểm tra xem mảng có tồn tại một phần tử thỏa điều kiện nào đó cho trước hay không? → tìm phần tử thỏa điều kiện để kết luận Trả về: • 1 nếu có phần tử thỏa điều kiện • 0 nếu không có phần tử nào thỏa điều kiện 58
  59. Kiểm tra tồn tại int KiemTraTonTaiXXX( a[], int n) { for (int i = 0; i<n; i++) if (a[i] thỏa điều kiện) return 1; return 0; //Không có phần tử nào thỏa điều kiện } 59
  60. Kiểm tra tồn tại Kiểm tra xem mảng số nguyên có tồn tại số lẻ không? int KiemTraTonTaiLe(int a[], int n) { for (int i = 0; i < n; i++) if (a[i] % 2 != 0) return 1; return 0; } 60
  61. Kiểm tra với mọi phần tử • Kiểm tra tất cả các phần tử thỏa điều kiện nào đó cho trước → tìm phần tử không thỏa điều kiện để kết luận mảng không thỏa điều kiện Trả về: • 0 nếu gặp phần tử không thỏa điều kiện • 1 nếu không có phần tử nào không thỏa điều kiện Tìm phủ định của điều kiện cho trước → kết luận 0 61
  62. Kiểm tra với mọi phần tử int KiemTraXXX( a[], int n) { for (int i = 0; i<n; i++) if (a[i] không thỏa điều kiện) return 0; return 1; } 62
  63. Kiểm tra với mọi phần tử Kiểm tra xem mảng số nguyên có toàn bộ là giá trị âm không? int KiemTraToanAm(int a[], int n) { for (int i = 0; i = 0) return 0; return 1; } 63
  64. Bài tập Cho mảng số nguyên kích thước n. Viết các hàm sau: 1. Kiểm tra xem mảng có chứa số nguyên tố không? 2. Kiểm tra xem mảng có thứ tự tăng dần hay không? 3. Kiểm tra xem mảng có chẵn lẻ xen kẽ không? 4. Kiểm tra xem mảng có âm dương xen kẽ không? 64
  65. 1. Kiểm tra xem mảng có chứa số nguyên tố không? /*Kiem tra k co phai la so nguyen to khong? * Neu la so nguyen to thi tra ve 1 * Nguoc lai tra ve 0 */ int LaSNT(int k); /*Kiem tra xem mang a co chua so nguyen to khong? * Neu co thi tra ve 1 * Nguoc lai tra ve 0 */ int CoTonTaiSNT(int a[], int n); 65
  66. int LaSNT(int k) { int d=0; for(int i=1; i<=k; i++) { if(k%i==0) d++; } if(d==2) return 1; //La so nguyen to return 0; } int CoTonTaiSNT(int a[], int n) { for(int i=0; i<n; i++) { if(LaSNT(a[i])==1) return 1; } return 0; } 66
  67. int main() { int a[MAX], n, kq; NhapKT(n); NhapMang(a, n); printf("Mang ban dau: "); XuatMang(a, n); kq=CoTonTaiSNT(a, n); if(kq==1) printf("Ton tai so nguyen to trong mang"); else printf("Khong ton tai so nguyen to trong mang"); getch(); return 0; } 67
  68. 2. Kiểm tra mảng có thứ tự tăng dần? int LaTangDan(int a[], int n) { for(int i=0; i a[i + 1]) return 0; } return 1; } 68
  69. 3. Kiểm tra chẵn lẻ xen kẽ? int LaChanLeXenKe(int a[], int n) { for(int i=0; i<n-1; i++) { if((a[i]+a[i+1])%2==0) return 0; } return 1; } 69
  70. 4. Kiểm tra âm dương xen kẽ int LaAmDuongXenKe(int a[], int n) { for (int i = 0; i = 0) return 0; } return 1; } 70
  71. THAO TÁC CHÈN 71
  72. Chèn phần tử vào mảng • Cho mảng sau: 12 5 7 9 21 38 0 1 2 3 4 5 • Hãy trình bày từng bước chèn 111 vào vị trí 3 của mảng 111 12 5 7 9 21 38 0 1 2 3 4 5 72 72
  73. Chèn phần tử vào mảng 12 5 7 9 21 38 Chèn 111 vào vị trí 3 của mảng 0 1 2 3 4 5 6 1. Di chuyển a[5] sang a[6]: a[6] = a[5] 12 5 7 9 21 38 0 1 2 3 4 5 6 2. Di chuyển a[4] sang a[5]: a[5] = a[4] 12 5 7 9 21 38 0 1 2 3 4 5 6 3. Di chuyển a[3] sang a[4]: a[4] = a[3] 12 5 7 9 21 38 0 1 2 3 4 5 6 4. Gán a[3] = 111 12 5 7 111 9 21 38 0 1 2 3 4 5 6 5. Tăng kích thước n++ 73
  74. Chèn phần tử vào mảng Gọi k là vị trí cần chèn, n là kích thước mảng, x là giá trị cần chèn • a[6] = a[5] i = n-1 • a[5] = a[4] a[i+1]=a[i] • a[4] = a[3] i = k • a[3] = 111 a[k]=x • n++ 74
  75. Chèn phần tử vào mảng BT: Hãy viết hàm chèn phần tử có giá trị x vào vị trí k cho trước trong mảng số nguyên a kích thước n theo mẫu sau: void ChenX(int a[], int &n, int x, int k); 75 75
  76. Chèn phần tử vào mảng void ChenX(int a[], int &n, int x, int k) { for(int i = n-1; i>=k; i ) { a[i+1] = a[i]; } a[k] = x; n++; } 76
  77. Bài tập áp dụng Hãy viết hàm chèn phần tử có giá trị x vào sau phần tử có giá trị nhỏ nhất có trong mảng số nguyên a, kích thước n (giả sử mảng không có giá trị trùng nhau) Gợi ý: 1. Viết hàm tìm vị trí phần tử có giá trị nhỏ nhất (min) 2. Viết hàm chèn x vào sau min (sử dụng hàm ChenX) 77 77
  78. Bài tập áp dụng int TimVTMin(int a[], int n) { int vtmin = 0; for (int i = 1; i < n; i++) { if (a[i] < a[vtmin]) vtmin = i; } return vtmin; } 78
  79. Bài tập áp dụng void ChenXSauMin(int a[], int &n, int x) { int vt = TimVTMin(a, n); ChenX(a, n, x, vt + 1); } 79
  80. THAO TÁC XÓA 80
  81. Xóa phần tử khỏi mảng • Cho mảng sau: 12 5 7 9 21 38 0 1 2 3 4 5 • Hãy trình bày từng bước xóa phần tử tại vị trí 3 trong mảng 12 5 7 9 21 38 0 1 2 3 4 5 81 81
  82. Xóa phần tử khỏi mảng 12 5 7 9 21 38 Xoá phần tử tại vị trí 3 0 1 2 3 4 5 1. Dời a[4] sang a[3]: a[3] = a[4] 12 5 7 21 38 0 1 2 3 4 5 2. Dời a[5] sang a[4]: a[4] = a[5] 12 5 7 21 38 0 1 2 3 4 5 3. Giảm kích thước 1 phần tử: n 12 5 7 21 38 0 1 2 3 4 82
  83. Xoá phần tử khỏi mảng Gọi k là vị trí cần xoá, n là kích thước mảng i=n-2 • a[3] = a[4] a[i]=a[i+1] • a[4] = a[5] i=k Giảm kích thước 1 phần tử: n 83
  84. Xóa phần tử khỏi mảng BT: Hãy viết hàm xóa phần tử tại vị trí k cho trước trong mảng số nguyên a kích thước n theo mẫu sau: void XoaTaiVTk(int a[], int &n, int k); 84 84
  85. Xóa phần tử khỏi mảng void XoaTaiVTk(int a[], int &n, int k) { for (int i = k; i <= n - 2; i++) { a[i] = a[i + 1]; } n ; } 85
  86. Bài tập áp dụng Hãy viết hàm xóa phần tử x (nếu có) trong mảng số nguyên a, kích thước n (giả sử mảng không có giá trị trùng nhau) Gợi ý: 1. Viết hàm tìm vị trí phần tử có giá trị x 2. Viết hàm xoá phần tử x (sử dụng hàm XoaTaiVTk) 86 86
  87. Bài tập áp dụng int TimVTX(int a[], int n, int x) { for (int i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; } 87
  88. Bài tập áp dụng void XoaX(int a[], int &n, int x) { int vt = TimVTX(a, n, x); if (vt != -1) { XoaTaiVTk(a, n, vt); } } 88
  89. CHUỖI KÝ TỰ 89
  90. Khái niệm • Chuỗi ký tự là trường hợp đặc biệt của mảng 1 chiều, là một dãy các phần tử, mỗi phần tử có kiểu ký tự • Hằng ký tự được đặt trong cặp nháy đơn. Ví dụ: ‘a’, ‘1’, ‘ ’ (Ký tự trắng – giữa cặp dấu nháy ‘ phải có 1 khoảng trắng) • Hằng chuỗi được đặt trong cặp nháy kép. Ví dụ: “ho va ten”, “123”, “” (Chuỗi rỗng – không có khoảng trắng) 90 90
  91. Khái niệm • Chuỗi ký tự được kết thúc bằng ký tự ‘\0’ (giá trị 0). Do đó khi khai báo độ dài của chuỗi luôn luôn khai báo dư 1 phần tử để chứa ký tự ‘\0’. • Ví dụ: Chuỗi “NGUYEN VAN A” được lưu ‘N’ ‘G’ ‘U’ ‘Y’ ‘E’ ‘N’ ‘ ‘ ‘V’ ‘A’ ‘N’ ‘ ‘ ‘A’ ‘\0’ 0 1 2 3 4 5 6 7 8 9 10 11 12 → Chuỗi gồm 13 ký tự 91 91
  92. Khai báo chuỗi char [ ] ; Ví dụ: char str[25]; Ý nghĩa khai báo 1 mảng kiểu ký tự tên là str có 25 phần tử (như vậy có thể lưu tối đa 24 ký tự vì phần tử thứ 24 đã chứa ký tự kết thúc chuỗi ‘\0’ ) 92
  93. Khai báo chuỗi • Cách 2: Con trỏ char * ; Ví dụ: char *str; • Phải cấp phát bộ nhớ trước khi sử dụng chuỗi str • Ví dụ: Thư viện malloc.h char *str; str = (char*)malloc(30); //Cấp phát bộ nhớ cho str gồm 30 ký tự !!!Gán trực tiếp thì không cần cấp phát bộ nhớ 93
  94. Nhập chuỗi – string.h • Cú pháp: char *gets(char *str); →Nhận các ký tự nhập từ phím cho đến khi nhấn phím Enter và đưa vào chuỗi str Ví dụ: int main() { char str[80]; printf("Nhap vao chuoi: "); gets(str); printf("Chuoi vua nhap la: %s\n", str); getch(); return 0; } 94
  95. Nhập chuỗi • Lưu ý: Không thể dùng hàm scanf để nhập chuỗi có khoảng trắng • Ví dụ: Giả sử nhập vào chuỗi: “Nguyen Van An” Thì kết quả xuất ra màn hình là: “Nguyen” (do str chỉ lưu chuỗi “Nguyen”) int main() { char str[80]; printf("Nhap vao chuoi: "); scanf("%s", &str); printf("Chuoi vua nhap la: %s\n", str); getch(); return 0; } 95
  96. Xuất chuỗi – string.h • Cú pháp : int puts (const char *s); • Ví dụ: int main() { char *str = "Vi du xuat chuoi"; puts(str); return 0; } → Có thể dùng printf(): printf(“%s”, str); 96
  97. Các hàm xử lý chuỗi - 1. Tính độ dài chuỗi: strlen 2. Sao chép chuỗi: strcpy, strncpy 3. Nối chuỗi: strcat, strncat 4. So sánh chuỗi: strcmp, strncmp, stricmp, strnicmp 5. Tìm kiếm: strchr, strstr 6. Tách chuỗi: strtok 7. Đổi thành chữ in HOA: strupr 8. Đổi thành chữ in thường: strlwr 97
  98. Tính độ dài của chuỗi int strlen(char *s); • Ví dụ: char *str = "Borland International"; printf("Do dai str = %d\n", strlen(str)); → Kết quả: Do dai str = 21 98
  99. Bài tập ví dụ - tính độ dài chuỗi 1. Viết hàm đếm số ký tự trắng trong chuỗi 2. Viết hàm in ra màn hình chuỗi theo thứ tự đảo ngược 3. Viết hàm tìm xem ký tự ch có trong chuỗi không? Nếu có cho biết vị trí xuất hiện đầu tiên của ch 4. Viết hàm kiểm tra xem chuỗi có đối xứng hay không? 5. Viết hàm đổi tất cả các ký tự có trong chuỗi thành chữ HOA (không dùng hàm strupr) 99
  100. 1. Đếm số ký tự trắng trong chuỗi int DemKyTuTrang(char *s) { int d=0; int n=strlen(s); for(int i=0; i<n; i++) { if(s[i]==' ') d++; } return d; } 100
  101. 2. In ra màn hình chuỗi theo thứ tự ngược void XuatChuoiNguoc(char *s) { int n = strlen(s); for (int i = n - 1; i >= 0; i ) printf("%c", s[i]); } 101
  102. Bài tập làm thêm – tính độ dài chuỗi 1. Viết hàm tra xem trong chuỗi có ký tự số hay không nếu có tách ra thành một mảng số riêng 2. Viết hàm đổi ký tự hoa thành thường và ngược lại trong chuỗi ký tự cho trước 3. Viết chương trình tìm kiếm xem ký tự nào xuất hiện nhiều nhất trong chuỗi 4. Viết chương trình đảo ngược các ký tự trong chuỗi Ví dụ: Nhập: ABCDE Chuỗi sau khi đảo ngược là: EDCBA 102
  103. Sao chép chuỗi • Sao chép nội dung chuỗi scr vào chuỗi dest strcpy(char *dest, const char *scr); • Ví dụ: char dest[10]; char *src = "abcdefghi"; strcpy(dest, src); printf("Chuoi dest: %s", dest); → Kết quả: Chuoi dest: abcdefghi 103 103
  104. Sao chép chuỗi • Chép n ký tự từ chuỗi scr sang dest strncpy(char *dest, const char *scr, int n); • Ví dụ: char dest[4]; char *src = "abcdefghi"; strncpy(dest, src, 3); printf("%s\n", dest); → Kết quả: abc 104 104
  105. Nối chuỗi • Nối chuỗi s2 vào sau chuỗi s1 strcat(char *s1, char *s2); • Ví dụ: char s1[] = "Khoa"; char s2[] = "CNTT"; strcat(s1, " "); strcat(s1, s2); printf("%s", s1); → Kết quả: Khoa CNTT 105
  106. Nối chuỗi • Nối n ký tự đầu tiên của chuỗi s2 vào sau chuỗi s1 strncat(char *s1, char *s2, int n); • Ví dụ: char s1[] = "Khoa"; char s2[] = "CNTT"; strcat(s1, " "); strncat(s1, s2, 2); printf("%s", s1); → Kết quả: Khoa CN 106
  107. So sánh chuỗi • So sánh 2 chuỗi s1 và s2 theo nguyên tắc thứ tự từ điển. Phân biệt chữ hoa và thường int strcmp(char *s1, char *s2); • Trả về: • 0: nếu s1 bằng s2 • >0: nếu s1 lớn hơn s2 • <0: nếu s1 nhỏ hơn s2 107
  108. So sánh chuỗi !!! Ký tự HOA < Ký tự thường VD: ‘A’ < ‘a’ (do mã Ascii ‘A’ = 65, mã Ascii ‘a’ = 97) char s1[] = "abc"; char s2[] = "Abc"; int kq = strcmp(s1, s2); if (kq == 0) printf("Hai chuoi bang nhau"); else if (kq < 0) { printf("Chuoi s1 nho hon chuoi s2"); } else printf("Chuoi s1 lon hon chuoi s2"); → Kết quả: Chuoi s1 lon hon chuoi s2 108
  109. So sánh chuỗi • So sánh n ký tự đầu tiên của s1 và s2, giá trị trả về tương tự hàm strcmp() int strncmp(char *s1,char *s2, int n); • Ví dụ: char s1[] = "abcd"; char s2[] = "abef"; if(strncmp(s1, s2, 2)==0) printf("Giong nhau"); else printf("Khac nhau"); → Kết quả: Giong nhau 109
  110. So sánh chuỗi • So sánh chuỗi s1 và s2 nhưng không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp() int stricmp(char *s1, char *s2); • Ví dụ: char s1[] = "abcd"; char s2[] = "abCD"; if(stricmp(s1, s2)==0) printf("Giong nhau"); else printf("Khac nhau"); → Kết quả: Giong nhau 110
  111. So sánh chuỗi • So sánh n ký tự đầu tiên của s1 và s2, không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp() int strnicmp(char *s1, char *s2, int n); • Ví dụ: char s1[] = "aBcd"; char s2[] = "Abef"; if(strnicmp(s1, s2, 2)==0) printf("Giong nhau"); else printf("Khac nhau"); → Kết quả: Giong nhau 111
  112. Tìm ký tự trong chuỗi • Tìm sự xuất hiện đầu tiên của ký tư c trong chuỗi s. char *strchr(char *s, char c); • Trả về: NULL: nếu không có Con trỏ đến ký tự c xuất hiện trong s: nếu tìm thấy 112
  113. Tìm ký tự trong chuỗi • Ví dụ: char s[15]; char *ptr, c = 'm'; strcpy(s, "Vi du tim ky tu"); ptr = strchr(s, c); if (ptr) printf("%c xuat hien tai vi tri %d", c, ptr-s); else printf("Khong tim thay"); → Kết quả: m xuat hien tai vi tri 8 113
  114. Tìm chuỗi con • Tìm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi s1. char *strstr(char *s1, char *s2); • Trả về: NULL: nếu không có Ngược lại: Con trỏ vào chuỗi s2 xuất hiện trong s1 114
  115. Tìm chuỗi con • Ví dụ: char *s1 = "Borland International"; char *s2 = "nation", *ptr; ptr = strstr(s1, s2); if(ptr!=NULL) printf("Vi tri xuat hien cua s2: %d", ptr-s1); else printf("Khong ton tai chuoi s2"); → Kết quả: Vi tri xuat hien cua s2: 13 115
  116. Tách chuỗi char *strtok(char *s1, char *s2); • Nếu s2 có xuất hiện trong s1: Tách chuỗi s1 thành 2 chuỗi: Chuỗi đầu là những ký tự cho đến khi gặp s2 đầu tiên, chuỗi sau là những ký tự còn lại của s1 sau khi đã bỏ đi s2 xuất hiện trong s1 • Nếu s2 không xuất hiện trong s1 thì kết quả vẫn là s1 116
  117. Tách chuỗi → Kết quả: S11 = abc • Ví dụ: S12 = d char input[16] = "abc,d"; char *p; // Lay chuoi dau p = strtok(input, ","); if (p) printf("S11 = %s\n", p); // Lay chuoi con lai, tham so dau la NULL p = strtok(NULL, ""); if (p) printf("S12 = %s", p); 117
  118. Bài tập tách chuỗi 1. Viết hàm đếm xem một chuỗi cho trước có bao nhiêu từ (các từ cách nhau bằng khoảng trắng) 2. Viết hàm đảo ngược các từ 3. Viết hàm tách các từ phân biệt và in ra màn hình (các từ các nhau bởi dấu chấm câu hoặc khoảng trắng) 4. Viết hàm kiểm tra xem chuỗi có tuần hoàn hay không? 5. Viết hàm đổi những ký tự đầu tiên của mỗi từ thành chữ in HOA 118
  119. Đổi sang chữ in HOA • Đổi chuỗi str thành chuỗi in HOA char* strupr(char *str); • Ví dụ: char s1[] = "aBcd"; char *s2 = strupr(s1); printf("s2 = %s", s2); → Kết quả: s2 = ABCD 119
  120. Đổi sang chữ in thường • Đổi chuỗi str thành chuỗi in thường char* strlwr(char *str); • Ví dụ: char s1[] = "aBcd"; char *s2 = strlwr(s1); printf("s2 = %s", s2); → Kết quả: s2 = abcd 120
  121. Q&A 121