Đồ án xây dựng chức năng tìm kiếm và sắp xếp trên mảng cấu trúc và danh sách liên kết theo chủ đề được chọn
- 60 trang
- file .pdf
lOMoARcPSD|16911414
BỘ TÀI CHÍNH
TRƯỜNG ĐẠI HỌC TÀI CHÍNH MARKETING
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN
XÂY DỰNG CHỨC NĂNG TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU
TRÚC VÀ DANH SÁCH LIÊN KẾT THEO CHỦ ĐỀ ĐƯỢC CHỌN
Giảng viên hướng dẫn: Thầy Nguyễn Quốc Thanh.
Sinh viên thực hiện: 2121012043_Nguyễn Khánh Vân.
Mã lớp học phần: 2121112001208
TP.HCM, ngày: 9 tháng: 4 năm 2022
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
TRƯỜNG ĐẠI HỌC TÀI CHÍNH – MARKETING
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN KHÁNH VÂN
ĐỒ ÁN
XÂY DỰNG CHỨC NĂNG TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU
TRÚC VÀ DANH SÁCH LIÊN KẾT THEO CHỦ ĐỀ ĐƯỢC CHỌN
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN QUẢN LÝ
NGƯỜI HƯỚNG DẪN: THS.NGUYỄN QUỐC THANH
TP.HCM, ngày: 9 tháng: 4 năm:2022
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
MỤC LỤC
Table of Contents
DANH MỤC BẢNG................................................................................................................3
DANH MỤC HÌNH ẢNH.........................................................................................................4
CHƯƠNG 1. GIỚI THIỆU..................................................................................................6
1.1. Giới thiệu đềề bài..............................................................................................................6
1.2. Cấấu trúc............................................................................................................................6
1.3. Dữ liệu mấẫu (>=10 thông tn đôấi tượng cấền xử lý)............................................................7
1.4. Các chức năng ( liệt kề chức năng sẽẫ xấy dựng)................................................................8
CHƯƠNG 2. TÌM KIẾẾM VÀ SẮẾP XẾẾP TRẾN MẢNG CẤẾU TRÚC............................................9
2.1. Nhập danh sách khách hàng.............................................................................................9
2.1.1. Chương trình con.............................................................................................................................9
2.1.2. Kếết quả chạy...................................................................................................................................11
2.2. Xuấất danh sách khách hàng............................................................................................11
2.2.1. Chương trình con...........................................................................................................................11
2.2.2. Kếết quả chạy...................................................................................................................................12
2.3. Tìm thông tn khách hàng thẽo mã khách hàng ( dùng Linẽar Sẽarch và Binary Sẽarch). 13
2.3.1. Chương trình con...........................................................................................................................13
2.3.2. Kếết quả chạy...................................................................................................................................14
2.3.3. Kếết quả chạy...................................................................................................................................16
2.4. Săấp xềấp danh sách khách hàng thẽo mã khách hàng:.....................................................16
2.4.1. Kếết quả khi chưa sắếp xếếp:..............................................................................................................16
2.4.2. Chương trình con...........................................................................................................................16
2.4.3. Kết quả chạy dùng Shaker Sort......................................................................................................18
2.4.4. Kếết quả chạy dùng Selecton Sort..................................................................................................19
2.4.5. Kếết quả chạy dùng Interchange Sort..............................................................................................21
2.4.6. Kếết quả chạy dùng Bubble Sort......................................................................................................22
2.4.7. Kếết quả chạy dùng Inserton Sort...................................................................................................23
2.4.8. Kếết quả chạy dùng Quick Sort........................................................................................................25
2.4.9. Kếết quả chạy dùng Merge Sort.......................................................................................................28
2.5. Để kiểm tra các chương trình con ta dùng 2 hàm:..........................................................28
CHƯƠNG 3. TÌM KIẾẾM VÀ SẮẾP XẾẾP TRẾN DANH SÁCH LIẾN KẾẾT.....................................35
3.1. Định nghĩa phần tử danh sách......................................................................................35
3.1.1. Chương trình con...........................................................................................................................35
3.2. Định nghĩa danh sách....................................................................................................35
1
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
3.2.1. Chương trình con...........................................................................................................................35
3.3. Khởi tạo danh sách.......................................................................................................35
3.3.1. Chương trình con...........................................................................................................................35
3.4. Tạo phần tử danh sách..................................................................................................36
3.4.1. Chương trình con...........................................................................................................................36
3.5. Nhập danh sách khách hàng.........................................................................................36
3.5.1. Chương trình con...........................................................................................................................36
3.5.2. kết quả chạy...................................................................................................................................37
3.6. Xuất danh sách khách hàng..........................................................................................38
3.6.1. Chương trình con...........................................................................................................................38
3.6.2. Kết quả chạy...................................................................................................................................39
3.7. Đếm số khách hàng có trong danh sách........................................................................39
3.7.1. Chương trình con...........................................................................................................................39
3.7.2. Kết quả chạy...................................................................................................................................40
3.8. Tìm kiếm thông tin khách hàng có trong danh sách....................................................40
3.8.1. Chương trình con...........................................................................................................................40
3.8.2. kết quả chạy...................................................................................................................................41
3.9. sắp xếp danh sách khách hàng theo mã khách hàng....................................................41
3.9.1. chương trình con............................................................................................................................41
3.9.2. Danh sách khi chưa sắp xếp:..........................................................................................................42
3.9.3. Kết quả chạy dùng Selection Sort..................................................................................................43
3.9.4. Kết quả chạy dùng Interchange Sort...................................................................................45
3.9.5. Kết quả chạy dùng Bubble Sort .........................................................................................47
3.9.6. Kết quả chạy dùng Insertion Sort........................................................................................49
3.9.7. Kết quả chạy dùng Quick Sort.......................................................................................................51
3.10. Kiểm tra chương trình con...........................................................................................51
3.10.1. Để kiểm tra các chương trình con ta sử dụng 2 hàm:...............................................................51
3.10.2. kết quả chạy..............................................................................................................................55
CHƯƠNG 4. KẾT LUẬN...........................................................................................56
4.1. Các chức năng đã làm được..........................................................................................56
4.2. Các chức năng chưa làm được......................................................................................56
CHƯƠNG 5. TÀI LIỆU THAM KHẢO................................................................................58
2
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
DANH MỤC BẢNG
Bảng 1.1 bảng thông tin khách hàng....................................................................5
3
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
DANH MỤC HÌNH ẢNH
Hình 2.1: Hình ảnh kết quả chạy của chương trình con nhập danh sách khách hàng...11
Hình 2.2: Hình ảnh kết quả chạy của chương trình con xuất danh sách khách hàng...12
Hình 2.3: Hình ảnh kết quả chạy của chương trình con linear search theo mã khách
hàng...................................................................................................................14
Hình 2.4: hình ảnh kết quả chạy của chương trình con binary search theo mã khách
hàng...................................................................................................................16
Hình 2.5: Hình ảnh danh sách khách hàng khi chưa được sắp xếp............................16
Hình 2.6: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng shaker sort ) theo mã
khách hàng.........................................................................................................18
Hình 2.7: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Selection Sort ) theo
mã khách hàng....................................................................................................19
Hình 2.8: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Interchange Sort )
theo mã khách hàng.............................................................................................21
Hình 2.9: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Bubble Sort ) theo mã
khách hàng..........................................................................................................22
Hình 2.10: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Insertion Sort ) theo
mã khách hàng....................................................................................................23
Hình 2.11: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng QuickSort Sort )
theo mã khách hàng.............................................................................................25
Hình 2.12: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Merge Sort ) theo
mã khách hàng....................................................................................................28
Hình 2.13: Hình ảnh kết quả chạy liệt kê các chức năng trong chương trình và kiểm tra.
..........................................................................................................................34
Hình 3.1: Hình ảnh kết quả chạy hàm nhập danh sách khách hàng...........................38
Hình 3.2: HÌnh ảnh kết quả chạy xuất danh sách khách hàng...................................39
Hình 3.3: Hình ảnh kết quả chạy đếm số khách hàng có trong danh sách là..............40
Hình 3.4: hình ảnh kết quả chạy chức năng tìm kiếm khách hàng theo mã khách hàng..
..........................................................................................................................41
Hình 3.5: Hình ảnh danh sách khách hàng khi chưa sắp xếp....................................42
Hình 3.6: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng selection sort )......43
Hình 3.7: Hình ảnh danh sách khách hàng sau khi sắp xếp (dùng Interchange sort )...45
Hình 3.8: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Bubble sort )........47
Hình 3.9: Hình ảnh danh sách khách hàng sau khi sắp xếp(dùng Insertion sort )........49
Hình 3.10: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng quick sort ).........51
Hình 3.11: Hình ảnh kết quả chạy liệt kê các chức năng trong chương trình và kiểm tra.
..........................................................................................................................55
4
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
5
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
CHƯƠNG 1. GIỚI THIỆU
1.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).
1.2. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
1.4. Các chức năng ( liệt kê chức năng sẽ xây dựng)
Các chức năng mảng 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 mảng 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.1. Nhập danh sách khách hàng
2.1.1. 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.getline(kh.MaKH,5);
cout<<" nhap ho: ";
cin.getline(kh.Ho, 30);
cout<<" nhap ten: ";
cin.getline(kh.Ten, 8);
cout<<" nhap nam quan ly: ";
cin.getline(kh.Nam, 5);
cout<<" nhap diem tich luy: ";
9
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.Doanhso;
cin.ignore();
}
//ctc nhập mảng cấu trúc
void nhapdsKH( KhachHang a[], int n)
{
for(int i=0;i {
cout<<" nhap thong tin khach hang thu "< nhapKH(a[i]);
cout< }
}
10
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
2.1.2. Kết quả chạy
Hình 2.1: Hình ảnh kết quả chạy của chương trình con nhập danh sách khách
hàng
2.2. Xuất danh sách khách hàng
2.2.1. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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"< for(int i=0;i {
xuatKH(a[i]);
}
}
2.2.2. Kết quả chạy
Hình 2.2: Hình ảnh kết quả chạy của chương trình con xuất danh sách khách
hàng
12
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
2.3. Tìm thông tin khách hàng theo mã khách hàng ( dùng Linear Search và Binary
Search)
2.3.1. 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.
Tìm 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ế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: "< cout<<"\tmaKH\t"<<"ho va
ten\t\t"<<"namQL\t"<<"diemtichluy\t"<<"doanhso\t"< xuatKH(a[i]);
return 0;
}
13
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3.2. Kết quả chạy
Hình 2.3: Hình ảnh kết quả chạy của chương trình con linear search theo mã
khách hàng
Tìm 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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"< xuatKH(a[mid]);// xuat thong tin khach hang
15
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3.3. Kết quả chạy
Hình 2.4: hình ảnh kết quả chạy của chương trình con binary search theo mã
khách hàng
2.4. Sắp xếp danh sách khách hàng theo mã khách hàng:
2.4.1. Kết quả khi chưa sắp xếp:
Hình 2.5: Hình ảnh danh sách khách hàng khi chưa được sắp xếp.
2.4.2. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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 {
for(int i=last; i>first;i--)// lap i di tu last ve first
if(strcmp(a[i-1].MaKH,a[i].MaKH)>0)
{
hoanvi(a[i-1],a[i]);
// neu ma cua khach hang i-1 lon hon ma cua khach hang i thi doi cho 2 khach
hang
k=i;// dua so k ve vi tri i
}first=k;// vi tri first luc nay duoc gan bang k
17
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
for(int j=first; j // lap j di tu first den last
if(strcmp(a[j].MaKH,a[j+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.4.3. Kêt quả chạy dùng Shaker Sort
Hình 2.6: Hình ả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
Downloaded by Nguynhavy Ha Vy ([email protected])
BỘ TÀI CHÍNH
TRƯỜNG ĐẠI HỌC TÀI CHÍNH MARKETING
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN
XÂY DỰNG CHỨC NĂNG TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU
TRÚC VÀ DANH SÁCH LIÊN KẾT THEO CHỦ ĐỀ ĐƯỢC CHỌN
Giảng viên hướng dẫn: Thầy Nguyễn Quốc Thanh.
Sinh viên thực hiện: 2121012043_Nguyễn Khánh Vân.
Mã lớp học phần: 2121112001208
TP.HCM, ngày: 9 tháng: 4 năm 2022
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
TRƯỜNG ĐẠI HỌC TÀI CHÍNH – MARKETING
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN KHÁNH VÂN
ĐỒ ÁN
XÂY DỰNG CHỨC NĂNG TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU
TRÚC VÀ DANH SÁCH LIÊN KẾT THEO CHỦ ĐỀ ĐƯỢC CHỌN
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN QUẢN LÝ
NGƯỜI HƯỚNG DẪN: THS.NGUYỄN QUỐC THANH
TP.HCM, ngày: 9 tháng: 4 năm:2022
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
MỤC LỤC
Table of Contents
DANH MỤC BẢNG................................................................................................................3
DANH MỤC HÌNH ẢNH.........................................................................................................4
CHƯƠNG 1. GIỚI THIỆU..................................................................................................6
1.1. Giới thiệu đềề bài..............................................................................................................6
1.2. Cấấu trúc............................................................................................................................6
1.3. Dữ liệu mấẫu (>=10 thông tn đôấi tượng cấền xử lý)............................................................7
1.4. Các chức năng ( liệt kề chức năng sẽẫ xấy dựng)................................................................8
CHƯƠNG 2. TÌM KIẾẾM VÀ SẮẾP XẾẾP TRẾN MẢNG CẤẾU TRÚC............................................9
2.1. Nhập danh sách khách hàng.............................................................................................9
2.1.1. Chương trình con.............................................................................................................................9
2.1.2. Kếết quả chạy...................................................................................................................................11
2.2. Xuấất danh sách khách hàng............................................................................................11
2.2.1. Chương trình con...........................................................................................................................11
2.2.2. Kếết quả chạy...................................................................................................................................12
2.3. Tìm thông tn khách hàng thẽo mã khách hàng ( dùng Linẽar Sẽarch và Binary Sẽarch). 13
2.3.1. Chương trình con...........................................................................................................................13
2.3.2. Kếết quả chạy...................................................................................................................................14
2.3.3. Kếết quả chạy...................................................................................................................................16
2.4. Săấp xềấp danh sách khách hàng thẽo mã khách hàng:.....................................................16
2.4.1. Kếết quả khi chưa sắếp xếếp:..............................................................................................................16
2.4.2. Chương trình con...........................................................................................................................16
2.4.3. Kết quả chạy dùng Shaker Sort......................................................................................................18
2.4.4. Kếết quả chạy dùng Selecton Sort..................................................................................................19
2.4.5. Kếết quả chạy dùng Interchange Sort..............................................................................................21
2.4.6. Kếết quả chạy dùng Bubble Sort......................................................................................................22
2.4.7. Kếết quả chạy dùng Inserton Sort...................................................................................................23
2.4.8. Kếết quả chạy dùng Quick Sort........................................................................................................25
2.4.9. Kếết quả chạy dùng Merge Sort.......................................................................................................28
2.5. Để kiểm tra các chương trình con ta dùng 2 hàm:..........................................................28
CHƯƠNG 3. TÌM KIẾẾM VÀ SẮẾP XẾẾP TRẾN DANH SÁCH LIẾN KẾẾT.....................................35
3.1. Định nghĩa phần tử danh sách......................................................................................35
3.1.1. Chương trình con...........................................................................................................................35
3.2. Định nghĩa danh sách....................................................................................................35
1
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
3.2.1. Chương trình con...........................................................................................................................35
3.3. Khởi tạo danh sách.......................................................................................................35
3.3.1. Chương trình con...........................................................................................................................35
3.4. Tạo phần tử danh sách..................................................................................................36
3.4.1. Chương trình con...........................................................................................................................36
3.5. Nhập danh sách khách hàng.........................................................................................36
3.5.1. Chương trình con...........................................................................................................................36
3.5.2. kết quả chạy...................................................................................................................................37
3.6. Xuất danh sách khách hàng..........................................................................................38
3.6.1. Chương trình con...........................................................................................................................38
3.6.2. Kết quả chạy...................................................................................................................................39
3.7. Đếm số khách hàng có trong danh sách........................................................................39
3.7.1. Chương trình con...........................................................................................................................39
3.7.2. Kết quả chạy...................................................................................................................................40
3.8. Tìm kiếm thông tin khách hàng có trong danh sách....................................................40
3.8.1. Chương trình con...........................................................................................................................40
3.8.2. kết quả chạy...................................................................................................................................41
3.9. sắp xếp danh sách khách hàng theo mã khách hàng....................................................41
3.9.1. chương trình con............................................................................................................................41
3.9.2. Danh sách khi chưa sắp xếp:..........................................................................................................42
3.9.3. Kết quả chạy dùng Selection Sort..................................................................................................43
3.9.4. Kết quả chạy dùng Interchange Sort...................................................................................45
3.9.5. Kết quả chạy dùng Bubble Sort .........................................................................................47
3.9.6. Kết quả chạy dùng Insertion Sort........................................................................................49
3.9.7. Kết quả chạy dùng Quick Sort.......................................................................................................51
3.10. Kiểm tra chương trình con...........................................................................................51
3.10.1. Để kiểm tra các chương trình con ta sử dụng 2 hàm:...............................................................51
3.10.2. kết quả chạy..............................................................................................................................55
CHƯƠNG 4. KẾT LUẬN...........................................................................................56
4.1. Các chức năng đã làm được..........................................................................................56
4.2. Các chức năng chưa làm được......................................................................................56
CHƯƠNG 5. TÀI LIỆU THAM KHẢO................................................................................58
2
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
DANH MỤC BẢNG
Bảng 1.1 bảng thông tin khách hàng....................................................................5
3
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
DANH MỤC HÌNH ẢNH
Hình 2.1: Hình ảnh kết quả chạy của chương trình con nhập danh sách khách hàng...11
Hình 2.2: Hình ảnh kết quả chạy của chương trình con xuất danh sách khách hàng...12
Hình 2.3: Hình ảnh kết quả chạy của chương trình con linear search theo mã khách
hàng...................................................................................................................14
Hình 2.4: hình ảnh kết quả chạy của chương trình con binary search theo mã khách
hàng...................................................................................................................16
Hình 2.5: Hình ảnh danh sách khách hàng khi chưa được sắp xếp............................16
Hình 2.6: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng shaker sort ) theo mã
khách hàng.........................................................................................................18
Hình 2.7: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Selection Sort ) theo
mã khách hàng....................................................................................................19
Hình 2.8: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Interchange Sort )
theo mã khách hàng.............................................................................................21
Hình 2.9: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Bubble Sort ) theo mã
khách hàng..........................................................................................................22
Hình 2.10: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Insertion Sort ) theo
mã khách hàng....................................................................................................23
Hình 2.11: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng QuickSort Sort )
theo mã khách hàng.............................................................................................25
Hình 2.12: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Merge Sort ) theo
mã khách hàng....................................................................................................28
Hình 2.13: Hình ảnh kết quả chạy liệt kê các chức năng trong chương trình và kiểm tra.
..........................................................................................................................34
Hình 3.1: Hình ảnh kết quả chạy hàm nhập danh sách khách hàng...........................38
Hình 3.2: HÌnh ảnh kết quả chạy xuất danh sách khách hàng...................................39
Hình 3.3: Hình ảnh kết quả chạy đếm số khách hàng có trong danh sách là..............40
Hình 3.4: hình ảnh kết quả chạy chức năng tìm kiếm khách hàng theo mã khách hàng..
..........................................................................................................................41
Hình 3.5: Hình ảnh danh sách khách hàng khi chưa sắp xếp....................................42
Hình 3.6: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng selection sort )......43
Hình 3.7: Hình ảnh danh sách khách hàng sau khi sắp xếp (dùng Interchange sort )...45
Hình 3.8: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng Bubble sort )........47
Hình 3.9: Hình ảnh danh sách khách hàng sau khi sắp xếp(dùng Insertion sort )........49
Hình 3.10: Hình ảnh danh sách khách hàng sau khi sắp xếp ( dùng quick sort ).........51
Hình 3.11: Hình ảnh kết quả chạy liệt kê các chức năng trong chương trình và kiểm tra.
..........................................................................................................................55
4
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
5
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
CHƯƠNG 1. GIỚI THIỆU
1.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).
1.2. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
1.4. Các chức năng ( liệt kê chức năng sẽ xây dựng)
Các chức năng mảng 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 mảng 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.1. Nhập danh sách khách hàng
2.1.1. 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.getline(kh.MaKH,5);
cout<<" nhap ho: ";
cin.getline(kh.Ho, 30);
cout<<" nhap ten: ";
cin.getline(kh.Ten, 8);
cout<<" nhap nam quan ly: ";
cin.getline(kh.Nam, 5);
cout<<" nhap diem tich luy: ";
9
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.Doanhso;
cin.ignore();
}
//ctc nhập mảng cấu trúc
void nhapdsKH( KhachHang a[], int n)
{
for(int i=0;i
cout<<" nhap thong tin khach hang thu "<
cout<
}
10
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
2.1.2. Kết quả chạy
Hình 2.1: Hình ảnh kết quả chạy của chương trình con nhập danh sách khách
hàng
2.2. Xuất danh sách khách hàng
2.2.1. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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"<
xuatKH(a[i]);
}
}
2.2.2. Kết quả chạy
Hình 2.2: Hình ảnh kết quả chạy của chương trình con xuất danh sách khách
hàng
12
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
2.3. Tìm thông tin khách hàng theo mã khách hàng ( dùng Linear Search và Binary
Search)
2.3.1. 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.
Tìm 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ế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: "<
ten\t\t"<<"namQL\t"<<"diemtichluy\t"<<"doanhso\t"<
return 0;
}
13
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3.2. Kết quả chạy
Hình 2.3: Hình ảnh kết quả chạy của chương trình con linear search theo mã
khách hàng
Tìm 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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"<
15
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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.3.3. Kết quả chạy
Hình 2.4: hình ảnh kết quả chạy của chương trình con binary search theo mã
khách hàng
2.4. Sắp xếp danh sách khách hàng theo mã khách hàng:
2.4.1. Kết quả khi chưa sắp xếp:
Hình 2.5: Hình ảnh danh sách khách hàng khi chưa được sắp xếp.
2.4.2. 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
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ á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
for(int i=last; i>first;i--)// lap i di tu last ve first
if(strcmp(a[i-1].MaKH,a[i].MaKH)>0)
{
hoanvi(a[i-1],a[i]);
// neu ma cua khach hang i-1 lon hon ma cua khach hang i thi doi cho 2 khach
hang
k=i;// dua so k ve vi tri i
}first=k;// vi tri first luc nay duoc gan bang k
17
Downloaded by Nguynhavy Ha Vy ([email protected])
lOMoARcPSD|16911414
Đồ án Cấu Trúc Dữ Liệu và Giải Thuật_Nguyễn Khánh Vân
for(int j=first; j
if(strcmp(a[j].MaKH,a[j+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.4.3. Kêt quả chạy dùng Shaker Sort
Hình 2.6: Hình ả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
Downloaded by Nguynhavy Ha Vy ([email protected])