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 hỗ trợ quản lý danh mục đồng hồ được bán một đơn vị gồm các thông tin: Mã sản phẩm (MaSP); Hãng sản xuất (HangSX); Giới tính (đồng hồ nữ, đồng hồ nam, trung tính, .2 Cấu trúc Mô tả cấu trúc được yêu cầu, chọn CTDL để thể hiện, khai báo/định nghĩa cấu trúc Thông tin sản phẩm đồng hồ cần quản lý gồm: - MaSP: Mã sản phẩm, gồm một chuỗi ký tự số có chiều dài 11 ký tự. - HangSX: Hãng sản xuất, chiều dài mỗi chữ khoảng 10 ký tự - GioiTinh: Giới tính, chỉ gồm 1 chữ với chiều dài chữ khoảng 10 ký tự - TrongLuong: Trọng lượng đồng hồ - BaoHanh: Thời gian bảo hành của đồng hồ - Gia: Giá bán của đồng hồ Cấu trúc dữ liệu hỗ trợ quản lý thông tin các đồng hồ: - MaSP: chuỗi gồm 11 ký tự số - HangSX: chuỗi tối đa 10 ký tự - GioiTinh: chuỗi tối đa 10 ký tự - TrongLuong: số nguyên không âm (TrongLuong >= 0) - BaoHanh: số nguyên không âm (BaoHanh >= 0) 7 Bài thực hành Cấu trúc dữ liệu và giải thuật - Gia : số thực dương (Gia>=0) Định nghĩa cấu trúc đồng hồ: 1.3 Dữ liệu mẫu >= 10 thông tin đối tượng cần quản lý STT Mã SP Hãng SX Giới tính Trọng lượng 1 1910 Casio Nam 70g 2 1901 Tag Nam 160g Heuer 3 1903 Rolex Nam 156g 4 1904 Omega Trung 55g tính 5 1907 Longines Nữ 140g s 6 1906 Tissot Trung 180g tính 7 1905 Timex Trung 100g tính 8 1908 Calvin Nữ 90g Klein 9 1902 Movado Nam 100g 10 1909 Citizen Nam 150g 8 Bài thực hành Cấu trúc dữ liệu và giải thuật 1.4 Các chức năng (Liệt kê các chức năng sẽ xây dựng) Các chức năng trên mảng cấu trúc - Nhập danh sách đồng hồ - Xuất danh sách đồng hồ - Tìm thông tin ĐH theo mã số x (dùng Linear Search và Binary Search) - Tìm thông tin ĐH theo hãng sản xuất (dùng Linear Search và Binary Search) - Sắp xếp danh sách theo Mã sản phẩm (dùng Shaker Sort) - Sắp xếp danh sách theo Mã sản phẩm (dùng Selection Sort) - Sắp xếp danh sách theo Mã sản phẩm (dùng Interchange Sort) - Sắp xếp danh sách theo Trọng lượng (dùng Bubble Sort) - Sắp xếp danh sách theo Giá (dùng Insertion Sort) - Sắp xếp danh sách theo thời gian Bảo hành (dùng Quick Sort) - Sắp xếp danh sách theo Mã sản phẩm (dùng Merge Sort) Các chức năng trên danh sách liên kết - Nhập danh sách đồng hồ - Xuất danh sách đồng hồ - Tìm thông tin ĐH theo mã sp x (dùng Linear Search ) - Tìm thông tin ĐH theo tên (dùng Linear Search ) - Sắp xếp danh sách theo Mã sản phẩm (dùng Shaker Sort) - Sắp xếp danh sách theo Mã sản phẩm (dùng Selection Sort) - Sắp xếp danh sách theo Mã sản phẩm (dùng Interchange Sort) - Sắp xếp danh sách theo Trọng lượng (dùng Bubble Sort) - Sắp xếp danh sách theo Giá (dùng Insertion Sort) - Sắp xếp danh sách theo thời gian Bảo hành (dùng Quick Sort) - Sắp xếp danh sách theo Trọng lượng (dùng Merge Sort) 9 Bài thực hành Cấu trúc dữ liệu và giải thuật 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 đồng hồ 2.1 Chương trình con Để nhập danh sách đồng hồ, cần xây dựng hai chương trình con gồm: - void nhap_o(dongho &a): hỗ trợ nhập thông tin một sinh viên gồm MaSp, HangSX, GioiTinh, TrongLuong, Baohanh, Gia - void nhap_mang(dongho a[], int n) hỗ trợ nhập danh sách đồng hồ 10 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra (Hàm main kiểm tra ctc) 11 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.3 Kết quả chạy 2.2 Xuất thông tin đồng hồ 2.1 Chương trình con -Để xuất danh sách sản phẩm đồng hồ ,ta cũng cần phải xây dựng 2 chương trình con gồm : 12 Bài thực hành Cấu trúc dữ liệu và giải thuật +Xuất ô :void xuat_o(dongho a ):hỗ trợ xuất thông tin đã nhập của một sản phẩm đồng hồ +Xuất mảng : void xuat_mang (dongho a[],int n):hổ trợ xuất mảng sản phẩm đồng hồ 2.3 Kết quả chạy 13 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.3 Tìm kiếm mã sản phẩm với Linearsearch và Binarysearch: 2.1 Chương trình con Thực hiện tìm kiếm với khóa chính là Mã sản phẩm (dữ liệu khóa) Để tìm thông tin theo mã số của đồng hồ, cần xây dựng như sau: void_LinearSearch(dongho a[], int n): giải thuật tìm kiếm tuyến tính, hỗ trợ tìm ra đồng hồ có mã số cần tìm. void BinarySearch(dongho a[], int n): giải thuật tìm kiếm nhị phân, hỗ trợ tìm ra đồng hồ có mã số cần tìm. 14 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra 15 Bài thực hành Cấu trúc dữ liệu và giải thuật Hàm main test cho phần tìm kiếm theo mã sp bằng Linear Search Hàm main test cho phần tìm kiếm theo mã số bằng Binary Search 2.3 Kết quả chạy Kết quả chạy tìm thông tin đồng hồ có mã số 1903 có trong danh sách hàm test 16 Bài thực hành Cấu trúc dữ liệu và giải thuật Kết quả chạy tìm thông tin đồng hồ có mã số 1902 không có trong danh sách test 2.4 Tìm thông tin ĐH theo hãng sản xuất dùng Linearsearch và Binarysearch 2.1 Chương trình con Thực hiện tìm kiếm với khóa chính là Hãng sản xuất (dữ liệu khóa) Để tìm thông tin theo mã số của đồng hồ, cần xây dựng như sau: void_LinearSearch_h(dongho a[], int n): giải thuật tìm kiếm tuyến tính, hỗ trợ tìm ra đồng hồ có hãng sản xuất cần tìm.
17 Bài thực hành Cấu trúc dữ liệu và giải thuật void BinarySearch_h(dongho a[], int n): giải thuật tìm kiếm nhị phân, hỗ trợ tìm ra đồng hồ có hãng sản xuất cần tìm. 18 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra 19 Bài thực hành Cấu trúc dữ liệu và giải thuật Hàm main test cho phần tìm kiếm theo hãng sản xuất bằng Linear Search Hàm main test cho phần tìm kiếm theo hãng dản xuất bằng Binary Search 2.3 Chạy kết quả Kết quả chạy tìm thông tin đồng hồ có hãng sản xuất Omega có trong danh sách hàm test 20 Bài thực hành Cấu trúc dữ liệu và giải thuật Kết quả chạy tìm thông tin đồng hồ có hãng sản xuất Casio không có trong danh sách hàm test 2.5 Sắp xếp danh sách theo Mã sản phẩm dùng Shaker Sort 2.1 Chương trình con void ShakerSort(dongho arr[],int n): giải thuật sắp xếp các thông tin theo mã số. Về ý tưởng giải thuật xuất phát từ cuối dãy, xét các phần tử gần nhau, nếu là nghịch thế thì hoán vị hai phần tử này với mục đích đẩy phần tử bé nhất về đầu dãy. Trong mỗi lần sắp xếp sẽ thực hiện 2 lượt: Lượt đi: đẩy phần tử bé nhất về đầu dãy.
Lượt về: đẩy phần tử lớn nhất về cuối dãy. void swap(dongho &a, dongho &b): hàm hoán vị hỗ trợ cho phần sắp xếp trong chương trình con. 21 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra 22 Bài thực hành Cấu trúc dữ liệu và giải thuật Hàm main test cho phần sắp xếp thông tin theo mã sản phẩm bằng Shaker Sort.3 Chạy kết quả 2.6 Sắp xếp danh sách theo Mã sản phẩm dùng Selection Sort 2.1 Chương trình con Để sắp xếp thông tin theo mã sản phầm, ta cần xây dựng như sau: void SelectionSort(dongho arr[], int n): giải thuật sắp xếp bằng chọn trực tiếp. Với ý tưởng chọn phần tử nhỏ nhất trong mảng, đưa phần tử này về đầu mảng, tiếp tục lặp lại để sắp xếp mảng từ vị trí thứ 2.
void hoanvi(dongho &a, dongho &b): hàm hoán vị hỗ trợ việc hoán vị các phần tử trong chương trình con SelectionSort. 23 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra Hàm main test cho phần sắp xếp thông tin theo mã sản phẩm bằng Selection Sort.3 Chạy kết quả 24 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.7 Sắp xếp danh sách theo Hãng sản xuất dùng Interchange Sort 2.1 Chương trình con Để sắp xếp thông tin theo Hãn sản xuất, ta cần xây dựng như sau: void InterchangeSort(dongho arr[], int n): giải thuật sắp xếp bằng đổi chỗ trực tiếp. Với ý tưởng bắt đầu từ đầu mảng, tìm các nghịch thế (phần tử sau bé hơn phần tử trước) của phần tử này, thực hiện hoán vị nếu có, sau đó lặp lại từ phần tử kế tiếp cho đến khi mảng được sắp xếp. void hoanvi(Bangdiem &a, Bangdiem &b): thuật toán hoán vị hỗ trợ hoán vị các phần tử nghịch thế trong chương trình con Interchange Sort.
25 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra Hàm main test cho phần sắp xếp thông tin theo mã sản phẩm bằng Interchange Sort.3 Chạy kết quả 26 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.8 Sắp xếp danh sách theo Trọng lượng dùng Bubble Sort 2.1 Chương trình con Để sắp xếp thông tin theo trọng lượng, ta cần xây dựng như sau: void BubbleSort(dongho a[], int n): giải thuật sắp xếp nổi bọt. Với ý tưởng xuất phát từ cuối dãy, hoán vị các cặp nghịch thế kế tiếp nhau và cứ lặp lại cho đến khi mảng được sắp xếp. void hoanvi(dongho &a, dongho &b): hàm hoán vị hỗ trợ cho việc hoán vị các nghịch thế trong chương trình con Bubble Sort. 27 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra Hàm main test cho phần sắp xếp thông tin theo trọng lượng bằng Bubble Sort.3 Chạy kết quả 28 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.9 Sắp xếp danh sách theo Giá dùng Insertion Sort 2.1 Chương trình con Để sắp xếp thông tin theo giá, ta cần xây dựng như sau: void InsertionSort(dongho arr[], int n): giải thuật sắp xếp chèn trực tiếp.
Với ý tưởng chia mảng cần sắp xếp thành 2 mảng con, mảng T chứa arr[0], mảng P chứa phần còn lại. Chọn 1 phần tử arr[i] trong P, tìm vị trí thích hợp và chèn arr[i] vào mảng T. Lặp lại cho đến khi mảng P rỗng void hoanvi(dongho &a, dongho &b): hàm hoán vị hỗ trợ cho việc hoán vị các nghịch thế trong chương trình con Insertion Sort. 29 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.2 Kiểm tra Hàm main test cho phần sắp xếp thông tin theo giá bằng Insertion Sort.3 Chạy kết quả 30 Bài thực hành Cấu trúc dữ liệu và giải thuật 2.10 Sắp xếp danh sách theo thời gian Bảo hành dùng Quick Sort 2.