CHƯƠNG I: GIỚI THIỆU 1. Giới thiệu đề bài Xây dựng chức năng tìm kiếm và sắp xếp trên các cấu trúc hỗ trợ quản lý thông tin các môn học bao gồm các thông tin: Mã môn học (MaMH), Tên môn học (TenMH), Số tín chỉ (SoTC), Số giờ lý thuyết (GioLT), Số giờ thực hành (GioTH), Số giờ tự học (TuHoc). Cấu trúc (khai báo/định nghĩa cấu trúc) Thông tin môn học cần quản lý gồm: MaMH: Mã số môn học, gồm một chuỗi ký tự số có chiều dài 10 ký tự. TenMH: Tên môn học, chỉ quản lý các tên Tiếng Việt với chiều dài 15 ký tự.
SoTC: Số tín chỉ, cho biết số lượng tín chỉ của môn học. GioLT: Giờ lí thuyết, số giờ học lí thuyết của môn học. GioTH: Giờ thực hành, số giờ học thực hành của môn học. Cấu trúc dữ liệu hỗ trợ quản lý thông tin môn học: MaMH: chuỗi gồm 10 ký tự.
TenMH: chuỗi gồm 15 kí tự. SoTC: số nguyên không âm. GioLT: số thực dương. GioTH: số thực dương.
TuHoc: số thực dương. Định nghĩa cấu trúc môn học: struct MONHOC { char MaMH[10]; char TenMH[15]; int SoTC; float GioLT; 0 0 float GioTH; float Tuhoc; }; 1. Dữ liệu mẫu Mã Tên Số tín Giờ lý Giờ Tự môn môn chỉ thuyết thực học học học hành 1 Toán 12 5 5 2 2 Văn 11 4 3 1 3 Anh 10 6 2 6 4 Sử 9 4 3 4 5 Địa 7 5 4 3 6 Tin 15 3 1 5 7 Lí 6 6 2 6 8 Hóa 8 4 5 2 9 Sinh 13 5 4 4 10 Thể 4 7 2 1 dục Bảng 1. 1 Dữ liệu mẫu 1.
Các chức năng trên mảng cấu trúc Nhập danh sách môn học. Xuất danh sách môn học. Tìm thông tin môn học theo mã môn học (dùng hàm Liner Searrch). Tìm thông tin môn học theo mã mã môn học (dùng hàm Binary Search).
Tìm thông tin môn học theo Tên môn học (dùng hàm Liner Searrch). Tìm thông tin môn học theo Tên môn học (dùng hàm Binary Searrch). Sắp xếp danh sách theo Mã môn học dùng hàm Shaker Sort. Sắp xếp danh sách theo Mã môn học dùng hàm Selection Sort.
Sắp xếp danh sách theo Tên môn học dùng hàm Interchange Sort. Sắp xếp danh sách theo Mã môn học dùng hàm Bubble Sort. Sắp xếp danh sách theo Tên môn học dùng hàm Insertion Sort. Sắp xếp danh sách theo Tín chỉ dùng hàm Quick Sort.
Sắp xếp danh sách theo Mã môn học dùng hàm Merge Sort. 0 0 Các chức năng trên danh sách liên kết Nhập danh sách môn học. Xuất danh sách môn học. Tìm thông tin môn học theo Mã môn học dùng hàm Liner Search.
Tìm thông tin môn học theo Tên môn học dùng hàm Liner Search. Sắp xếp danh sách theo Mã môn học dùng hàm Selection Sort. Sắp xếp danh sách theo Tên môn học dùng hàm Interchange Sort. Sắp xếp danh sách theo Tín chỉ dùng hàm Bubbler Sort.
Sắp xếp danh sách theo Tên môn học dùng hàm Insertion Sort. Sắp xếp danh sách theo Mã môn học dùng hàm Quick Sort. 0 0 CHƯƠNG II: TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU TRÚC 2.1 Nhập danh sách môn học a) Chương trình con Để nhập danh sách môn học, cần xây dựng hai chương trình con gồm: void nhap_o(MONHOC& a);: hỗ trợ nhập thông tin một môn học gồm mã môn học, tên môn học, tín chỉ, giờ lý thuyết, giờ thực hành, tự học. void nhap_Mang(MONHOC a[], int n);: hỗ trợ nhập danh sách môn học.
//Nh ập ô cho thông tin môn học void nhap_o(MONHOC& a) { cout << " Ma mon hoc:"; cin.MaMH, 10); cout << " Ten mon hoc:"; cin.TenMH, 10); cout << " So tin chi:"; cin >> a.SoTC; cout << " Gio li thuyet:"; cin >> a.GioLT; cout << " Gio thuc hanh:"; cin >> a.GioTH; cout << " Tu hoc:"; cin >> a.ignore(); } //Nh ập Thông tin môn học void nhap_Mang(MONHOC a[], int n) { for (int i = 0; i < n; i++) { cout << "\n Nhap sinh vien thu " << i << ":" << endl; nhap_o(a[i]); cout << endl; 0 0 } } b) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); return 0; } c) Kết quả chạy Hình 2. 1 Kết quả thông tin môn học 2.2 Xuất danh sách môn học a) Chương trình con void xuat_o(MONHOC a);: hỗ trợ xuất một thông tin môn học gồm: mã môn học, tên môn học, số tín chỉ, giờ lý thuyết, giờ thực hành, tự học. void xuat_Mang(MONHOC a[], int n); //Xu ất ô cho thông tin môn học void xuat_o(MONHOC a) 0 0 { cout << " Ma mon hoc:" << a.MaMH << endl; cout << " Ten mon hoc:" << a.TenMH << endl; cout << " So tin chi:" << a.SoTC << endl; cout << " Gio li thuyet:" << a.GioLT << endl; cout << " Gio thuc hanh:" << a.GioTH << endl; cout << " Tu hoc:" << a.Tuhoc << endl; } //Xu ất thông tin môn học void xuat_Mang(MONHOC a[], int n) { cout << " ==========> Danh sach mon hoc: <==========" << endl; for (int i = 0; i < n; i++) { xuat_o(a[i]); cout << endl; } } b) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); //ki ểm tra ph ần xuất Xuat_Mang(dsmh, spt); return 0; } 0 0 c) Kết quả chạy Hình 2. 2 Xuất thông tin môn học 2.3 Tìm kiếm thông tin môn học theo mã môn học dùng Liner Search a) Chương trình con int LinerSearch(MONHOC a[], int n, char x[]): Tìm kiếm thông tin môn học theo MaMH.
//Dùng LinearSearch để tìm mã môn học int LinearSearch(MONHOC a[], int n, char x[]) { for (int i = 0; i < n; i++) if (strcmp(a[i].MaMH, x) == 0) return i; return -1; } a) Kiểm tra (hàm Main kiểm tra ctc) void Main() { 0 0 const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); xuat_Mang(dsmh, spt); char MaMH[10]; cout << "\n Nhap ma mon hoc muon tim: "; cin.getline(MaMH, 11); //Tìm kiếm MaMH bằng linersearch int i = LinearSearch(dsmh, spt, MaMH); if (i >= 0) { cout << "\n ==========> Ket qua tim kiem ma mon hoc bang LinerSearch: <==========\n "; xuat_o(dsmh[i]); } else cout << "\n ==========> Khong co thong tin <=========="; } b) Kết quả chạy Hình 2. 3 Tìm kiếm mã môn học bằng Liner Search 2.4 Tìm kiếm thông tin môn học theo mã môn học dùng Binary Search a) Chương trình con 0 0 int BinarySearch(MONHOC a[], int n, char x[]): Tìm kiếm thông tin môn học theo MaMH. //Hàm tìm ki ếm BinarySearch theo MAMH int BinarySearch(MONHOC a[], int n, char x[]) { int left = 0; int right = n - 1; int mid = (left + right) / 2; while (left <= right && strcmp(a[mid].MaMH) < 0) right = mid - 1; else left = mid + 1; mid = (left + right) / 2; } if (left > right) return (-1); return (mid); } d) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); xuat_Mang(dsmh, spt); char MaMH[10]; cout << "\n Nhap ma mon hoc muon tim: "; cin.getline(MaMH, 11); //Tìm Kiếm MaMH bằng BinarySearch int j = BinarySearch(dsmh, spt, MaMH); if (j >= 0) 0 0 { cout << "\n ==========> Ket qua tim kiem Ma mon hoc bang BinarySearch: <==========\n "; xuat_o(dsmh[j]); } else cout << "\n ==========> Khong co thong tin <=========="; } e) Kết quả chạy Hình 2. 4 Tìm kiếm mã môn học bằng Binary Search 2.5 Tìm kiếm thông tin môn học theo Tên dùng Liner Search a) Chương trình con int LinerSearch2(MONHOC a[], int n, char x[]): Tìm kiếm thông tin môn học theo tên.
//Hàm LinerSearch theo tên môn học int LinerSearch2(MONHOC a[], int n, char x[]) { int i = 0; while (strcmp(a[i].TenMH, x) == 0) return i; if (strcmp(a[n - i].TenMH, x) == 0) return (n - i); 0 0 return (-1); } f) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); xuat_Mang(dsmh, spt); char TenMH[10]; cout << "\n Nhap Ten mon hoc can tim: "; cin.getline(TenMH, 11); //kiểm tra linearsearch 2 cout << "Nhap TenMH can tim:"; cin.getline(TenMH, 3); int i = LinearSearch2(dsmh, spt, TenMH); if (i >= 0) { cout << " ==========> Ket qua tim kiem: <==========" << endl; xuat_o(dsmh[i]); } else cout << " ==========> Khong co thong tin <==========" << endl; } g) Kết quả chạy Hình 2. 5 Tìm kiếm tên môn học bằng Liner Search 0 0 2.6 Tìm kiếm thông tin môn học theo Tên dùng Binary Search a) Chương trình con int BinarySearch2(MONHOC a[], int n, char x[]): Tìm kiếm thông tin môn học theo tên //Hàm BinarySearch theo tên môn học int BinarySearch2(MONHOC a[], int n, char x[]) { int l = 0; int r = n - 1; int mid = (l + r) / 2; while (l <= r && strcmp(a[mid].TenMH, x) > 0) r = mid - 1; else l = mid + 1; mid = (l + r) / 2; } if (l > r) return(-1); return mid; } h) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); xuat_Mang(dsmh, spt); char TenMH[10]; cout << "\n Nhap Ten mon hoc can tim: "; cin.getline(TenMH, 11); 0 0 //Tìm kiếm bằng BinarySearch theo Tên môn học int k = BinarySearch2(dsmh, spt, TenMH); if (k >= 0) { cout << "\n ==========> Ket qua tim kiem Ten mon hoc bang BinarySearch: <==========\n"; xuat_o(dsmh[k]); } else cout << "\nKhong co thong tin"; i) Kết quả chạy Hình 2. 6 Tìm kiếm tên môn học bằng Binary Search 2.7 Hàm hoán vị void hoanvi(MONHOC& a, MONHOC& b): chương trình hỗ trợ hoán đổi thông tin. //hoán vị void hoanvi(MONHOC& a, MONHOC& b) { MONHOC temp = a; a = b; b = temp; } 2.8 Sắp xếp danh sách theo MaMH dùng hàm Shaker Sort 0 0 { cout << " Ma mon hoc:" << a.MaMH << endl; cout << " Ten mon hoc:" << a.TenMH << endl; cout << " So tin chi:" << a.SoTC << endl; cout << " Gio li thuyet:" << a.GioLT << endl; cout << " Gio thuc hanh:" << a.GioTH << endl; cout << " Tu hoc:" << a.Tuhoc << endl; } 0 0 //Xu ất thông tin môn học void xuat_Mang(MONHOC a[], int n) { cout << " ==========> Danh sach mon hoc: <==========" << endl; for (int i = 0; i < n; i++) { xuat_o(a[i]); cout << endl; } } b) Kiểm tra (hàm Main kiểm tra ctc) void Main() { const int spt = 3; MONHOC dsmh[spt]; nhap_Mang(dsmh, spt); //ki ểm tra ph ần xuất Xuat_Mang(dsmh, spt); return 0; } 0 0 c) Kết quả chạy Hình 2.
2 Xuất thông tin môn học 2.3 Tìm kiếm thông tin môn học theo mã môn học dùng Liner Search a) Chương trình con int LinerSearch(MONHOC 0 a[], int n, char x[]): Tìm 0 kiếm thông tin môn học theo MaMH.
