Cấu Trúc Dữ Liệu và Giải Thuật trong Quản Lý Danh Mục Đồng Hồ

Đồ án nghiên cứu môn học cấu trúc dữ liệu và giải thuật, áp dụng công nghệ tiên tiến, tối ưu giải pháp kỹ thuật cho bài toán ., phục vụ nghiên cứu và ứng dụng thực tiễn

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Cấu Trúc Dữ Liệu và Giải Thuật
• Đề tài: Cấu Trúc Dữ Liệu và Giải Thuật trong Quản Lý Danh Mục Đồng Hồ
• Loại tài liệu: Đồ Án Tốt Nghiệp
• Năm xuất bản: 2023
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. Chương 1: Giới thiệu
• 1.1. Giới thiệu đề bài
• 1.2. Cấu trúc
• 1.3. Dữ liệu mẫu
• 1.4. Các chức năng
• 2. 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.2. Kiểm tra
• 2.3. Kết quả chạy phần tử
• 2.4. Tìm thông tin đồng hồ theo hãng sản xuất dùng Linearsearch và Binarysearch
• 2.5. Sắp xếp danh sách theo Mã sản phẩm dùng Shaker Sort
• 2.6. Sắp xếp danh sách theo Mã sản phẩm dùng Selection Sort
• 2.7. Sắp xếp danh sách theo Hãng sản xuất dùng Interchange Sort
• 2.8. Sắp xếp danh sách theo Trọng lượng dùng Bubble Sort

Tóm tắt

I. Vai trò của Cấu trúc dữ liệu và Giải thuật quản lý đồng hồ

Trong bối cảnh thương mại điện tử cạnh tranh, việc tối ưu hóa hiệu năng website e-commerce là yếu tố sống còn. Đối với ngành hàng đặc thù như đồng hồ, nơi sản phẩm có vô số thuộc tính (thương hiệu, loại máy, chất liệu, giá), một hệ thống quản lý danh mục hiệu quả đóng vai trò nền tảng. Cốt lõi của hệ thống này chính là Cấu trúc Dữ liệu và Giải thuật. Lựa chọn đúng cấu trúc dữ liệu không chỉ giúp lưu trữ thông tin một cách khoa học mà còn quyết định tốc độ truy xuất, tìm kiếm và hiển thị sản phẩm. Một cấu trúc được thiết kế tốt sẽ giảm thiểu độ trễ, cải thiện đáng kể trải nghiệm người dùng. Tương tự, các giải thuật thông minh cho phép thực hiện các tác vụ phức tạp như sắp xếp, lọc sản phẩm theo nhiều tiêu chí, hay xây dựng hệ thống gợi ý sản phẩm một cách nhanh chóng và chính xác. Việc bỏ qua yếu tố này dẫn đến hệ thống chậm chạp, khó mở rộng và gây thất vọng cho khách hàng. Ngược lại, một nền tảng vững chắc về Cấu trúc Dữ liệu và Giải thuật trong quản lý danh mục đồng hồ giúp doanh nghiệp vận hành trơn tru, dễ dàng quản lý hàng ngàn SKU đồng hồ và tạo ra lợi thế cạnh tranh bền vững trên thị trường số. Nền tảng này ảnh hưởng trực tiếp đến tốc độ tải trang, khả năng điều hướng và cuối cùng là tỷ lệ chuyển đổi của website.

1.1. Tác động trực tiếp đến hiệu năng và tốc độ website

Tốc độ tải trang là một trong những yếu tố xếp hạng quan trọng của Google. Một hệ thống với cấu trúc dữ liệu cồng kềnh và giải thuật không hiệu quả sẽ dẫn đến việc tối ưu hóa truy vấn database trở nên kém cỏi. Mỗi khi người dùng truy cập một trang danh mục, hệ thống phải thực hiện các truy vấn phức tạp để lấy dữ liệu. Nếu giải thuật có độ phức tạp thuật toán cao, thời gian xử lý sẽ tăng theo cấp số nhân khi số lượng sản phẩm tăng lên. Điều này gây ra độ trễ lớn, khiến người dùng phải chờ đợi lâu. Kỹ thuật caching dữ liệu danh mục, dù hữu ích, cũng không thể giải quyết triệt để vấn đề nếu gốc rễ nằm ở cấu trúc. Do đó, việc lựa chọn cấu trúc như cây B-Tree cho danh mục hoặc bảng băm tra cứu sản phẩm từ đầu là cực kỳ quan trọng để đảm bảo khả năng mở rộng và duy trì hiệu năng cao.

1.2. Nâng cao trải nghiệm người dùng UX khi tìm kiếm sản phẩm

Trải nghiệm người dùng không chỉ dừng lại ở giao diện đẹp. Nó còn là việc khách hàng có thể tìm thấy sản phẩm mong muốn một cách nhanh chóng và dễ dàng nhất. Một cấu trúc cây danh mục logic giúp người dùng dễ dàng duyệt qua các tầng sản phẩm thông qua điều hướng breadcrumb. Hơn nữa, các giải thuật mạnh mẽ cho phép triển khai các tính năng nâng cao như faceted search (tìm kiếm đa diện). Thay vì chỉ tìm kiếm theo tên, người dùng có thể lọc đồng thời theo nhiều thuộc tính: thương hiệu, khoảng giá, loại máy, khả năng chống nước. Đây là yếu tố then chốt giúp giữ chân khách hàng và tăng khả năng mua hàng. Nếu không có nền tảng giải thuật tốt, việc triển khai các bộ lọc phức tạp này sẽ rất chậm hoặc không khả thi.

II. Thách thức về Cấu trúc dữ liệu Giải thuật quản lý đồng hồ

Việc xây dựng hệ thống quản lý danh mục đồng hồ đối mặt với nhiều thách thức đặc thù. Đầu tiên là sự đa dạng và phức tạp của thuộc tính sản phẩm. Một chiếc đồng hồ không chỉ có Mã sản phẩm (MaSP) và Hãng sản xuất (HangSX), mà còn có vô số thông số khác như Giới tính, Trọng lượng, Thời gian bảo hành, Giá, loại dây, loại máy, v.v. Việc thiết kế một schema database cho sản phẩm linh hoạt để quản lý toàn bộ các thuộc tính này đòi hỏi sự phân tích kỹ lưỡng. Thách thức thứ hai là quy mô dữ liệu. Một website thương mại điện tử lớn có thể có hàng chục nghìn mẫu đồng hồ khác nhau. Khi dữ liệu phình to, các giải thuật tìm kiếm và sắp xếp đơn giản như tìm kiếm tuyến tính (Linear Search) trở nên cực kỳ chậm chạp. Điều này đặt ra yêu cầu phải áp dụng các giải thuật có độ phức tạp thuật toán thấp hơn. Cuối cùng, yêu cầu về trải nghiệm người dùng ngày càng cao đòi hỏi các tính năng tìm kiếm và lọc phải phản hồi tức thì, ngay cả với các truy vấn phức tạp. Việc cân bằng giữa tính linh hoạt của hệ thống, hiệu năng xử lý và khả năng mở rộng là bài toán cốt lõi mà các nhà phát triển phải giải quyết khi ứng dụng Cấu trúc Dữ liệu và Giải thuật.

2.1. Vấn đề quản lý thuộc tính sản phẩm PIM đa dạng

Mỗi dòng đồng hồ có thể có những bộ thuộc tính riêng biệt. Đồng hồ lặn có thông số chống nước, đồng hồ thông minh có hệ điều hành, đồng hồ xa xỉ có vật liệu quý. Một cấu trúc dữ liệu cứng nhắc sẽ không thể đáp ứng được sự đa dạng này. Hệ thống quản lý thuộc tính sản phẩm (PIM) cần một kiến trúc linh hoạt, thường là mô hình EAV (Entity-Attribute-Value) hoặc sử dụng các cơ sở dữ liệu NoSQL như MongoDB. Việc lựa chọn sai mô hình dữ liệu ngay từ đầu có thể dẫn đến việc phải tái cấu trúc toàn bộ hệ thống khi sản phẩm mới được thêm vào, gây tốn kém thời gian và chi phí.

2.2. Sự bùng nổ dữ liệu và bài toán về hiệu năng truy vấn

Khi số lượng đồng hồ tăng từ vài trăm lên vài chục nghìn, các truy vấn đơn giản để lọc sản phẩm có thể mất vài giây để thực thi, một khoảng thời gian không thể chấp nhận được trong thương mại điện tử. Đây là lúc việc tối ưu hóa truy vấn database trở nên cấp thiết. Các kỹ thuật như đánh chỉ mục (indexing) trên các cột thường xuyên được lọc, tối ưu hóa câu lệnh JOIN, và sử dụng các giải thuật tìm kiếm hiệu quả như Binary Search (trên dữ liệu đã sắp xếp) là bắt buộc. Theo tài liệu nghiên cứu của Đỗ Tường Vy (Trường Đại học Tài chính – Marketing), việc so sánh giữa Linear Search và Binary Search cho thấy sự khác biệt rõ rệt về hiệu năng khi áp dụng trên tập dữ liệu lớn.

III. Top Cấu trúc dữ liệu tối ưu việc quản lý danh mục đồng hồ

Để giải quyết các thách thức đã nêu, việc lựa chọn cấu trúc dữ liệu phù hợp là bước đi chiến lược. Không có một cấu trúc dữ liệu hoàn hảo cho mọi tác vụ; thay vào đó, một hệ thống hiệu quả thường kết hợp nhiều loại cấu trúc khác nhau. Đối với việc tổ chức danh mục, cấu trúc cây danh mục là lựa chọn phổ biến và hiệu quả nhất, cho phép phân cấp danh mục sản phẩm một cách tự nhiên. Khi cần truy xuất nhanh một sản phẩm cụ thể dựa trên mã SKU, bảng băm tra cứu sản phẩm lại tỏ ra vượt trội nhờ tốc độ truy cập O(1) trong trường hợp lý tưởng. Tài liệu gốc của Đỗ Tường Vy đã minh họa việc sử dụng cấu trúc struct dongho trong C++ để định nghĩa một sản phẩm, sau đó lưu trữ chúng trong các cấu trúc cơ bản như mảng và danh sách liên kết. Mặc dù đây là cách tiếp cận nền tảng, các hệ thống thực tế thường xây dựng dựa trên những ý tưởng này để tạo ra các schema database cho sản phẩm phức tạp hơn, có khả năng mở rộng tốt hơn. Việc hiểu rõ ưu và nhược điểm của từng cấu trúc dữ liệu sẽ giúp kiến trúc sư hệ thống đưa ra quyết định đúng đắn.

3.1. Cấu trúc Cây Tree cho việc phân cấp danh mục sản phẩm

Cấu trúc cây, đặc biệt là các biến thể như cây B-Tree cho danh mục, là lựa chọn lý tưởng để biểu diễn mối quan hệ cha-con giữa các danh mục. Ví dụ, 'Đồng hồ' là nút gốc, các nhánh con là 'Đồng hồ Nam', 'Đồng hồ Nữ'. 'Đồng hồ Nam' lại có các nhánh con như 'Đồng hồ Thể thao', 'Đồng hồ Cổ điển'. Cấu trúc này không chỉ giúp tổ chức dữ liệu logic mà còn dễ dàng cho việc tạo điều hướng breadcrumb và sitemap, hai yếu tố quan trọng cho SEO. Nó cũng đơn giản hóa việc quản trị, cho phép thêm, xóa, hoặc di chuyển cả một nhánh danh mục một cách dễ dàng.

3.2. Bảng băm Hash Table để tra cứu sản phẩm tức thì

Khi người dùng xem chi tiết một sản phẩm hoặc hệ thống cần lấy thông tin từ mã SKU, tốc độ là yếu tố tiên quyết. Bảng băm tra cứu sản phẩm (hoặc Dictionary/Map trong nhiều ngôn ngữ lập trình) cho phép truy xuất thông tin sản phẩm gần như ngay lập tức. Bằng cách sử dụng mã sản phẩm (MaSP) làm khóa, hệ thống có thể tìm thấy toàn bộ thông tin liên quan mà không cần phải duyệt qua toàn bộ danh sách. Điều này cực kỳ hữu ích trong việc xây dựng các tính năng như giỏ hàng, quản lý đơn hàng, và tối ưu hóa các API nội bộ.

3.3. Mảng và Danh sách liên kết trong các tác vụ cơ bản

Tài liệu nghiên cứu được phân tích đã tập trung vào việc triển khai các giải thuật trên hai cấu trúc dữ liệu cơ bản: mảng (array) và danh sách liên kết (linked list). Mảng cung cấp khả năng truy cập ngẫu nhiên nhanh chóng (O(1)) nhưng lại cứng nhắc về kích thước. Ngược lại, danh sách liên kết linh hoạt trong việc thêm/xóa phần tử nhưng việc truy cập một phần tử cụ thể lại chậm hơn (O(n)). Việc hiểu rõ sự khác biệt này là nền tảng. Trong thực tế, mảng thường được dùng để hiển thị một trang sản phẩm (ví dụ 20 sản phẩm/trang), trong khi danh sách liên kết có thể được ứng dụng trong các kịch bản cần sự thay đổi cấu trúc dữ liệu động.

IV. Phương pháp chọn Giải thuật cho tìm kiếm sắp xếp đồng hồ

Bên cạnh cấu trúc dữ liệu, giải thuật là linh hồn của hệ thống quản lý danh mục. Các giải thuật quyết định cách hệ thống xử lý yêu cầu của người dùng, từ việc tìm một sản phẩm cụ thể đến việc hiển thị danh sách sản phẩm theo một thứ tự mong muốn. Trong tài liệu nghiên cứu của Đỗ Tường Vy, một loạt các thuật toán sắp xếp đồng hồ và tìm kiếm đã được triển khai và so sánh, bao gồm Linear Search, Binary Search, Quick Sort, Selection Sort, Bubble Sort, và nhiều hơn nữa. Việc lựa chọn giải thuật phù hợp phụ thuộc vào nhiều yếu tố: kích thước dữ liệu, dữ liệu đã được sắp xếp hay chưa, và yêu cầu về độ ổn định của giải thuật. Ví dụ, thuật toán tìm kiếm theo thuộc tính (Binary Search) chỉ hiệu quả trên dữ liệu đã được sắp xếp, nhưng cho hiệu năng vượt trội so với tìm kiếm tuyến tính. Tương tự, Quick Sort thường rất nhanh nhưng trong trường hợp xấu nhất, hiệu năng của nó có thể giảm sút. Hiểu rõ các đặc tính này là chìa khóa để xây dựng một bộ lọc sản phẩm (product filtering) mạnh mẽ và hiệu quả.

4.1. So sánh giải thuật tìm kiếm Linear Search và Binary Search

Nghiên cứu đã chỉ ra sự khác biệt cơ bản giữa hai phương pháp. Linear Search (tìm kiếm tuyến tính) duyệt qua từng phần tử cho đến khi tìm thấy kết quả. Giải thuật này đơn giản nhưng không hiệu quả với tập dữ liệu lớn (độ phức tạp O(n)). Ngược lại, Binary Search (tìm kiếm nhị phân) yêu cầu dữ liệu phải được sắp xếp trước. Nó hoạt động bằng cách liên tục chia đôi không gian tìm kiếm, giúp giảm đáng kể thời gian tìm kiếm (độ phức tạp O(log n)). Trong ứng dụng thực tế, khi tìm kiếm theo mã sản phẩm hoặc hãng sản xuất, nếu danh sách đã được sắp xếp, Binary Search là lựa chọn tối ưu hơn hẳn.

4.2. Lựa chọn thuật toán sắp xếp đồng hồ phù hợp với yêu cầu

Các thuật toán sắp xếp đồng hồ như Quick Sort, Merge Sort thường được ưu tiên cho các tập dữ liệu lớn do hiệu năng trung bình tốt (O(n log n)). Trong khi đó, các giải thuật đơn giản hơn như Selection Sort, Bubble Sort, Insertion Sort (độ phức tạp O(n²)) chỉ phù hợp với các tập dữ liệu nhỏ hoặc trong mục đích học thuật. Tài liệu nghiên cứu đã cung cấp mã nguồn triển khai chi tiết các giải thuật này để sắp xếp danh sách đồng hồ theo nhiều tiêu chí khác nhau như Mã sản phẩm, Trọng lượng, Giá, và Thời gian bảo hành. Điều này cho thấy tính ứng dụng thực tiễn của việc lựa chọn đúng giải thuật cho từng yêu cầu nghiệp vụ cụ thể.

4.3. Hướng tới các giải thuật nâng cao Phân loại và Gợi ý

Ngoài tìm kiếm và sắp xếp, các giải thuật hiện đại còn mở ra nhiều khả năng. Các giải thuật học máy có thể được sử dụng để phân loại sản phẩm tự động, giúp một chiếc đồng hồ mới được đưa vào đúng danh mục mà không cần can thiệp thủ công. Hơn nữa, các giải thuật lọc cộng tác (collaborative filtering) hoặc dựa trên nội dung (content-based filtering) là nền tảng để xây dựng hệ thống gợi ý sản phẩm thông minh, đề xuất các mẫu đồng hồ mà người dùng có khả năng quan tâm nhất, từ đó tăng doanh thu và sự gắn kết của khách hàng.

V. Tương lai Cấu trúc dữ liệu và Giải thuật trong E commerce

Thế giới thương mại điện tử không ngừng phát triển, và vai trò của Cấu trúc Dữ liệu và Giải thuật cũng ngày càng trở nên quan trọng và phức tạp hơn. Trong tương lai, việc quản lý danh mục sẽ không chỉ dừng lại ở việc lưu trữ và truy xuất. Xu hướng cá nhân hóa trải nghiệm người dùng đòi hỏi các hệ thống phải thông minh hơn, có khả năng dự đoán nhu cầu của khách hàng. Các giải thuật học máy và trí tuệ nhân tạo (AI) sẽ được tích hợp sâu hơn để tự động hóa nhiều quy trình. Ví dụ, hệ thống có thể tự động tối ưu hóa thứ tự hiển thị sản phẩm dựa trên hành vi của từng người dùng, hoặc sử dụng xử lý ngôn ngữ tự nhiên để cải thiện chức năng tìm kiếm, hiểu được cả những truy vấn dạng văn nói. Việc tối ưu hóa hiệu năng website e-commerce sẽ chuyển từ tối ưu hóa truy vấn sang tối ưu hóa các mô hình dự đoán. Các cấu trúc dữ liệu mới, được thiết kế riêng cho các tác vụ học máy, cũng sẽ dần được áp dụng. Tóm lại, tương lai của ngành này nằm ở sự kết hợp nhuần nhuyễn giữa khoa học máy tính nền tảng và trí tuệ nhân tạo để tạo ra những trải nghiệm mua sắm thông minh và liền mạch.

5.1. Cá nhân hóa danh mục bằng giải thuật Machine Learning

Thay vì hiển thị cùng một danh sách sản phẩm cho tất cả mọi người, các hệ thống tương lai sẽ sử dụng giải thuật học máy để sắp xếp lại danh mục dựa trên lịch sử duyệt web, các sản phẩm đã mua, và thậm chí cả các yếu tố nhân khẩu học của người dùng. Hệ thống gợi ý sản phẩm sẽ trở thành một phần không thể thiếu của trang danh mục, chứ không chỉ là một widget riêng lẻ. Điều này đòi hỏi các cấu trúc dữ liệu có khả năng xử lý và truy vấn dữ liệu người dùng phức tạp trong thời gian thực.

5.2. Tìm kiếm thông minh Từ khóa đến ngữ nghĩa Semantic Search

Chức năng tìm kiếm sẽ vượt qua việc khớp từ khóa đơn thuần. Semantic Search, được hỗ trợ bởi các mô hình ngôn ngữ lớn, sẽ hiểu được ý định đằng sau truy vấn của người dùng. Ví dụ, người dùng có thể tìm 'đồng hồ lặn Thụy Sĩ dưới 20 triệu' và hệ thống sẽ hiểu và trả về kết quả chính xác, thay vì chỉ tìm các sản phẩm có chứa tất cả các từ khóa đó trong mô tả. Điều này yêu cầu các giải thuật xử lý ngôn ngữ tự nhiên và cấu trúc dữ liệu đồ thị (Graph Database) để biểu diễn mối quan hệ giữa các thực thể sản phẩm.

Trích đoạn nội dung tài liệu

BO TAI CHINH TRUONG DAI HOC TAI CHINH — MARKETING _ DOANMONHOC | CAU TRUC DU LIEU VA GIAI THUAT Giang vién : Nguyễn Quốc Thanh Sinh viên thực hiện : Đễ Tường Vy MSSV : 2021010354 Lớp :20DHT05 TPHCM - 12/2020 Bài thực hành Cấu trúc dữ liệu và giải thuật BỘ TÀI CHÍNH TRƯỜNG ĐẠI HỌC TAI CHINH — MARKETING _ DOANMONHOC | CAU TRUC DU LIEU VA GIAI THUAT Giang vién : Nguyễn Quốc Thanh Sinh viên thực hiện : Đễ Tường Vy MSSV : 2021010354 Lớp :20DHT05 TPHCM - 12/2020 2 Bài thực hành Cấu trúc dữ liệu và giải thuật MỤC LỤC Lờ I®:0082s. 5 Ch ii SIc ii .1 Gi Gthi GU nh ố. - -- - Ă KH HH HH HH TH HT th kg 6 1.3 Dữ lỆ U mẫu.4 Cac CHUC in . 8 Ch ngr?: Tìm kiêâm và säâp xêâp trên m ¿ng cââu †rÚC.3 Tìm kiêâm mã sản phẩm w ¡ Linearsearch và Binarysearch:.4 Tìm thông tin DH theo hang s 4 xudat dùng Linearsearch và Binarysearch.5 Săâp xêâp danh sách theo Mã sản plá m dùng Shaker Sort.6 Săâp xêâp danh sách theo Mã sản plá m dùng Selection Sort.7 Sãâp xêâp danh sách theo Hãng s ủ xuâât dùng Interchange Sort.8 Sãâp xêâp danh sách theo Trọng trợ ng dùng Bubble Sort.9 Sãâp xêâp danh sách theo Giá dùng Insertion Sort.10 Sãâp xêâp danh sách theo thời gian Bị. o hành dùng Quick Sort. 30 Ch ngr8: Tìm kiêâm và säâp xêâp trên danh sách liên kêât.2 Các thao tác cơ là n trên DSLÍ. ---- SH TH HH.3 Tìm kiêâm thông tin đôêng hôê theo mã sản phâm.4 Tìm thông tin ĐH theo tên hãng sả xuâât dùng Linear Search.5 Săâp xêâp danh sách theo mã sản phá m dùng Sharker Sort.6 Săâp xêâp danh sách theo Mã sản plâ m dùng Selection Sort.7 Săâp xêâp danh sách theo Mã sản phá m dùng Interchange Sort.8 Sãâp xêâp danh sách theo Trọng trợ ng dùng Bubble Sort.9 Sãâp xêâp danh sách theo thời gian Bi o hành dùng Insertion Sort.10 Sãâp xêâp danh sách theo thời gian li o hành dùng Quick Sort. 52 Bài thực hành Cấu trúc dữ liệu và giải thuật Bài thực hành Cấu trúc dữ liệu và giải thuật Lời Cam Đoan Tôi xin cam đoan bài đồ án này là do chính tôi thực hiện cùng với sựu hô trợ từ giáo viên giảng dạy bộ môn hướng dân và các bạn bè trong nhóm học tập không đánh cắp do an của người khác làm của riêng cho mình và hướng quyền lợi trên công sức của người khác . Tôi xin chịu hoàn toàn trách nhiệm về lời cam đoan trên ! Sinh Viên Đỗ Tường Wy Bài thực hành Cấu trúc dữ liệu và giải thuật Lời Cảm Ơn Lời nói đầu tiên em xin gửi lời cám ơn đến giáo viên trong toàn khoa CNTT của Trường Đại Học Tài chính Marketing nói chung và 2 giáo viên chuyên ngành giảng dạy bộ môn cấu trúc đữ liệu và giải thuật nói riêng. Và em xin gửi lời cám ơn đặc biệt nhất đến Thầy Nguyễn Quốc Thanh giáo viên giảng dạy và hướng dẫn em thực hiện tốt bài đồ án lần này . Em xin trân trong cam on ! Sinh Vién D6 Tuong Vy Bài thực hành Cấu trúc dữ liệu và giải thuật 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 tinh, .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 Thong tin san pham dé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 đài LI 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 I 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 II 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) 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 ho: struct dongho { char MaSP[11]; char HangSxX[1@]; 1.3 Dữ liệu mẫu char GioiTinh[1®]; >= 10 thông tin đối tượng cần quản lý int TrongLuong; int BaoHanh; STT Ma SP Hang SX | Giới tính | Trọng float Gia; lượng l 1910 Casio Nam 70g 2 1901 Tag Nam 160g Heuer 1903 Rolex Nam 156g 4 1904 Omega Trung 55g tinh 5 1907 Longines | Nt 140g § 6 1906 Tissot Trung 180g tinh 7 1905 Timex Trung 100g tinh 8 1908 Calvin Nữ 902 Klein 9 1902 Movado | Nam 100g 10 1909 Citizen Nam 150g 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 (đù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 (dung Linear Search ) - Tìm thông tin ĐH theo tén (dung 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) 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 al], 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 //Ctc nhập ô cấu trúc -void nhap_o(dongho &a) { cout << "\nNhap ma san pham: "; cin.MaSP, 11); cout << "\nNhap hang san xuat: ”"; cin.HangSX, 19); cout << "\nNhap gioi tỉnh: "; cin.GioiTinh, 19); cout << "\nNhap trong luong san pham (g): "; cin >> a.TrongLuong; cout << "\nNhap thoi gian bao hanh (thang): ”; cin >> a.BaoHanh; cout << "\nNhap gia (trieu VND): "; cin >> a.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 int main() { //Khai báo mảng số nguyên 100 phần tử dongho arr[100]; int soft = 2; //Nhập mảng tương ứng với số phần tử đã nhập ở trên cout << "\nNhap vao thong tin san pham dong ho”; nhap_mang(arr, soft); return 0; } 2.3 Kết quả chạy phan tu a[0]: ma san pham: 1901 hang san xuat: Casio gioi tinh: Nam trong luong san pham (g): 70 thoi gian bao hanh (thang): gia (trieu VND): 5 phan tu a[1]: ma san pham: 1903 hang san xuat: Rolex gioi tinh: Nam trong luong san pham (g): 156 thoi gian bao hanh (thang): 24 gia (trieu VND): 100 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 đự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 : voiđ xuat_mang (dongho a[].int n):hồ trợ xuất mảng sản phâm đồng hồ //ctc xuất ô cấu trúc void xuat_o(dongho a) ( cout << a.2 Kiểm tra (Hàm main kiêm tra ctc) int main() { //Khai báo mảng số nguyên 190 phần tử - dongho anr[199]; int soft = 2; //Nhập mảng tương ứng với số phần tử đã nhập ở trên cout << "\nNhap vao thong tin san pham dong ho”; nhap_mang(arr, soft); cout << "\nDanh sach cac san pham dong ho: ”; xuat_mang(arr, soft); return 9; } 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 Danh sach cac san pham dong ho: Danh sach thong tin cua cac san pham dong ho: 1901 Cas1o Nam 70(g) 60(thang) 5 (trieu) ` 1903 Rolex Nam 56(g) 24(thang) 100 (trieu) j 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: O 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. //Tìm kiếm LS theo mã sản phẩm void LinearSearch(dongho a[], int n) { char x[5]; cout << "\nNhap ma san pham muon tim: "; cin.MaSP, x) != 9) it+; if (i < n) { cout << "\nThong tin cua ma san pham ” << x << " la:”; xuat_o(a[i]); } else cout << "\nKhong tim thay"; O void BinarySearch(dongho al], int n): giai thuat tim kiém nhi phan, hé trợ tìm ra đồng hồ có mã so can tim. 14 Bài thực hành Cấu trúc dữ liệu và giải thuật //Tìm kiếm BS theo mã sp int BinarySearch(dongho a[], int n) { char x[5]; int left = 0; int right =n - 1; int mid = (right + left) / 2; cout << "\nNhap ma san pham muon tim: "; cin.MaSP) right = mid - 1; else left = mid + 1; mid = (right + left) / 2; } if (left <= right) { cout << "\nThong tin cua ma san pham ” << x << ” la:”; xuat_o(a[mid]); } else cout << "\nKhong tim thay"; return mid; } 2.