CHƯƠNG 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 và danh sách liên kết hỗ trợ quản lý thông tin khách hàng thân thiết bao gồm: Mã khách hàng(MaKH), Họ (Ho), Tên (Ten), Năm (Nam), Điểm tích luỹ đang có (Diem), Doanh số mua hàng (Doanhso). Cấu trúc Thông tin khách hàng cần quản lý gồm: MaKH: Mã khách hàng, gồm 1 chuỗi ký tự số có chiều dài 4 ký tự. Ho: Họ và tên chữ lót, chỉ định quản lý các tên tiếng Việt với chiều dài mỗi chữ khoảng 7 ký tự.
Ten: Tên, chỉ gồm 1 chữ Việt với chiều dài tối đa khoảng 7 ký tự. Nam: Năm, gồm 1 chuỗi ký tự số có chiều dài 4 ký tự. Diem: Điểm tích luỹ đang có, ghi nhận điểm tích luỹ của các khách hàng. Doanhso: Doanh số mua hàng, ghi nhận doanh số mua hàng của khách hàng.
Tính theo đơn vị Việt Nam đồng( ngàn đồng ) Cấu trúc dữ liệu hỗ trợ quản lý thông tin khách hàng: MaKH: chuỗi gồm 4 ký tự số. Ho: chuỗi tối đa 30 ký tự. Ten: Chuỗi tối đa 8 ký tự. Nam: chuỗi gồm 4 ký tự số.
Diem: số nguyên không âm (Diem>=0) Doanhso: số thực dương ( ngàn đồng ) Định nghĩa cấu trúc khách hàng: 6 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân struct KhachHang { char MaKH[5]; char Ho[30]; char Ten[8]; char Nam[5]; int Diem; float Doanhso; }kh; 1. Dữ liệu mẫu (>=10 thông tin đối tượng cần xử lý) Bảng 1.1 bảng thông tin khách hàng. STT MaKH Họ đệm Tên Năm Điểm Doanh số 1 2101 Le Tran Thuy 2019 15 8000(đ) 2 2104 Nguyen Binh An 2018 17 15000(đ) 3 2205 Tran Thi Chau 2021 14 6000(đ) 4 1999 Cao Thanh Than 2022 16 11000(đ) h 5 2108 Nguyễn Quỳnh Như 2021 19 12500(đ) 6 2213 Lâm thị Hà 2017 17 13450(đ) 7 2097 Đoàn Như Trúc 2018 18 20000(đ) 8 1978 Vũ Khánh Linh 2019 20 17000(đ) 9 2053 Hồ Hoàng Mai 2022 14 13000(đ) 10 2212 Nguyễn Văn Sơn 2017 16 15672(đ) 7 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân 1. Các chức năng ( liệt kê chức năng sẽ xây dựng) Các chức năng mkng cấu trúc Nhập danh sách khách hàng Xuất danh sách khách hàng Tìm thông tin khách hàng theo mã khách hàng ( dùng Linear Search và Binary Search) Sắp xếp danh sách theo mã khách hàng ( dùng Shaker Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Selection Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Interchange Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Bubble Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Insertion Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Quick Sort ) Sắp xếp danh sách theo mã khách hàng ( dùng Merge Sort ) Các chức năng mkng dslk Nhập danh sách khách hàng Xuất danh sách khách hàng Đếm số khách hàng có trong danh sách Tìm thông tin khách hàng Sắp xếp thông tin khách hàng ( dùng Selection Sort ) Sắp xếp thông tin khách hàng ( dùng Quick Sort ) 8 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân CHƯƠNG 2.
TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU TRÚC 2. Nhập danh sách khách hàng 2. Chương trình con Để nhập danh sách khách hàng, cần xây dựng hai chương trình con gồm: void nhapKH(KhachHang &kh): hỗ trợ nhập thông tin 1 khách hàng gồm mã khách hàng, họ, tên, năm quản lý, điểm tích luỹ, doanh số. void nhapdsKH( KhachHang a[], int &n): hỗ trợ nhập danh sách khách hàng.
//ctc nhập ô cấu trúc void nhapKH(KhachHang kh) { rewind(stdin); cout<<" nhap ma khach hang: "; cin.MaKH,5); cout<<" nhap ho: "; cin.Ho, 30); cout<<" nhap ten: "; cin.Ten, 8); cout<<" nhap nam quan ly: "; cin.Nam, 5); cout<<" nhap diem tich luy: "; 9 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân cin>>kh.Diem; cout<<" nhap doanh so: "; cin>>kh.ignore(); } //ctc nhập mảng cấu trúc void nhapdsKH( KhachHang a[], int n) { for(int i=0;i<n;i++) { cout<<" nhap thong tin khach hang thu "<<i<<": "<<endl; nhapKH(a[i]); cout<<endl; } } 10 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân 2. Kết quk chạy H2nh 2.1: H2nh ảnh kết quả chạy của chương tr2nh con nhập danh sách khách hàng 2. Xuất danh sách khách hàng 2. Chương trình con Để xuất danh sách khách hàng, cần xây dựng hai chương trình con gồm: void xuatKH(KhachHang kh): hỗ trợ xuất thông tin 1 khách hàng gồm mã khách hàng, họ, tên, năm quản lý, điểm tích luỹ, doanh số.
void xuatdsKH(KhachHang a[], int n): hỗ trợ xuất danh sách khách hàng. //ctc xuất ô cấu trúc void xuatKH(KhachHang kh) { cout << "\t" << kh.MaKH; 11 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân cout << "\t" << kh.Ho; cout << " " << kh.Ten; cout << "\t" << kh.Nam; cout << "\t\t" << kh.Diem; cout << "\t\t" << kh.Doanhso; cout << endl; } //ctc xuất mảng cấu trúc void xuatdsKH(KhachHang a[], int n) { cout<<"STT\t\t"<<"maKH\t"<<"ho va ten\t\t"<<"namQL\t"<<"diemtichluy\t"<<"doanhso\t"<<endl; for(int i=0;i<n;i++) { xuatKH(a[i]); } } 2. Kết quk chạy H2nh 2.2: H2nh ảnh kết quả chạy của chương tr2nh con xuất danh sách khách hàng 12 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân 2. Tìm thông tin khách hàng theo mã khách hàng ( dùng Linear Search và Binary Search) 2.
Chương trình con Để tìm thông tin khách hàng theo mã khách hàng, có thể dùng 2 cách Linear Search và Binary Search: int linearSearch(KhachHang a[], int n, char x[]): tìm kiếm tuyến tính. Int BinarySearch(KhachHang a[], int n, char x[]): tìm kiếm nhị phân. T2m thông tin khách hàng theo mã khách hàng bằng Linear Search: //ctc tìm thông tin khách hàng theo mã khách hàng int linearSearch(KhachHang a[], int n, char x[]) { for(int i=0;i<n;i++) { // nếu tìm thấy mã khách hàng thì xuất thông tin khách hàng có cùng mã cần tìm và trả về 0 if (strcmp(a[i].MaKH, x)==0) { cout<<" khach hang can tim la: "<<endl; cout<<"\tmaKH\t"<<"ho va ten\t\t"<<"namQL\t"<<"diemtichluy\t"<<"doanhso\t"<<endl; xuatKH(a[i]); return 0; } 13 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân } return -1;//nếu không tìm thấy mã khách hàng thì trả về -1 } 2. Kết quk chạy H2nh 2.3: H2nh ảnh kết quả chạy của chương tr2nh con linear search theo mã khách hàng T2m thông tin khách hàng theo mã khách hàng bằng Binary Search: // ham tim kiem ma khach hang dung binarysearch int BinarySearch(KhachHang a[], int n, char x[]) { int left=0;// gan left bang vi tri dau int right =n-1;// gan right bang vi tri cuoi int mid=(left+right)/2; // vi tri giua bang trung binh cong cua left va right ShakerSort(a, n); // sap xep lai ma khach hang tu thap den cao while (left<=right && strcmp(a[mid].MaKH, x)!=0) // lap neu left<=right va ma khach hang tai vi tri giua khac ma khach hang can tim 14 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân { if (strcmp(x, a[mid].MaKH)<0) // neu ma khach hang tai vi tri giua lon hon x right=mid-1; // doi bien right ve vi tri mid-1 Else // neu ma khach hang tai vi tri giua nho hon x left=mid+1; // doi bien left ve vi tri mid+1 mid=(left+right)/2; // tinh lai bien mid sau khi bien right hoac left thay doi } if (left>right)// neu thoat khoi vong lap vi left > right { cout<<" khong ton tai khach hang nay!!! "; return -1;// tra ve gia tri -1 } Else // neu thoat khoi vong lap vi tim thay ma khach hang can tim cout<<"\tmaKH\t"<<"ho va ten\t\t"<<"namQL\t"<<"diemtichluy\t"<<"doanhso\t"<<endl; xuatKH(a[mid]);// xuat thong tin khach hang 15 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân return 0;// tra ve gia tri 0 } 2.
Kết quk chạy H2nh 2.4: h2nh ảnh kết quả chạy của chương tr2nh con binary search theo mã khách hàng 2. Sắp xếp danh sách khách hàng theo mã khách hàng: 2. Kết quk khi chưa sắp xếp: H2nh 2.5: H2nh ảnh danh sách khách hàng khi chưa được sắp xếp. Chương trình con Để sắp xếp danh sách khách hàng theo mã khách hàng, có thể dùng: + Shaker Sort: void ShakerSort(KhachHang a[], int n) + Selection Sort: void SelectionSort(KhachHang a[], int n) + Interchange Sort: void InterchangeSort(KhachHang a[], int n) + Bubble Sort: void BubbleSort(KhachHang a[], int n) 16 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân + Insertion Sort: void InsertionSort(KhachHang a[],int n) + QuickSort Sort: void QuickSort(KhachHang a[], int left, int right) + Merge Sort: void mergesort (KhachHang a[], int n) Sắp xếp danh sách theo mã khách hàng ( dùng Shaker Sort ): // ctc sap xep danh sach theo ma khach hang dùng ShakerSort void ShakerSort(KhachHang a[], int n) { int first=0;// gán first bằng phan tu đầu tiên int last =n-1;// gán last bằng phan tu cuối cùng int k=n-1; // số k gán bằng với khách hàng cuối cùng while(first<last)// lặp lại nếu first < last { for(int i=last; i>first;i--)// lap i di tu last ve first if(strcmp(a[i-1].MaKH)>0) { hoanvi(a[j],a[j+1]); // neu ma khach hang j lon hon ma cua khach hang j+1 thi doi cho 2 khach hang k=j;// dua so k ve vi tri j }last=k;// vi tri last luc nay duoc gan bang k } } 2.
Kêt quk chạy dùng Shaker Sort H2nh 2.6: H2nh ảnh danh sách khách hàng sau khi sắp xếp ( dùng shaker sort ) theo mã khách hàng Sắp xếp danh sách theo mã khách hàng ( dùng Selection Sort ): // ctc sap xep danh sach khach hang theo ma khach hang dung selectionsort 18 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân void SelectionSort(KhachHang a[], int n) { int min; for (int i = 0; i < n - 1; i++) { min = i;// gan min bang i for (int j = i + 1; j < n; j++)// lap tu vi tri i+1 den cuoi danh sach if (strcmp(a[j].MaKH)<0)// neu ma khach hang o vi tri j nho hon ma khach hang o vi tri min min = j;// gan min=j de tim ma khach hang nho nhat co trong danh sach hoanvi(a[i], a[min]);// doi cho 2 khach hang } } 19 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân 2. Kết quk chạy dùng Selection Sort H2nh 2.7: H2nh ảnh danh sách khách hàng sau khi sắp xếp ( dùng Selection Sort ) theo mã khách hàng Sắp xếp danh sách theo mã khách hàng ( dùng Interchange Sort ): // ctc sap xep danh sach khach hang theo ma khach hang void InterchangeSort(KhachHang a[], int n) { for (int i = 0; i < n-1; i++) { for (int j = i + 1; j < n; j++)// lap tu vi tri i+1 den cuoi danh sach { if (strcmp(a[i].MaKH) > 0)// neu ma khach hang tai vi tri i > tai vi tri j { hoanvi(a[i], a[j]);// doi cho 2 khach hang } 20 0 0 Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân } } } 2. Kết quk chạy dùng Interchange Sort H2nh 2.
