S IY’ BO GIAO DUC VA DAO TAO WE l TRƯỜNG ĐẠI HỌC TÀI CHÍNH - MARKETING KHOA CÔNG NGHỆ THÔNG TIN BAI TAP DO AN ~ wv ~ ^ ` . CAU TRUC DU LIEU VA GIAI THUAT TRUONG DAI HOC TAICHINH MARKETING > Gidne vier Inebng din: Newyén Quie Thanh >> À4ầm học thực hiểm: Nguyễn Xuân TíHi > Ma sé mém hoe: 2121001038 » Mai lov hoc phan: 2121112901202 LOI CAM ON Đầu tiên, em xin chân thành cảm ơn va tri ân sâu sắc đến qúy thầy cô Trường Đại học Tài Chính - Marketing „ đặc biệt là quý thầy cô khoa Công nghệ thông tin và thầy Nguyễn Quốc Thanh đã dạy dỗ tận tình cho chúng em những tháng ngày vừa qua khi mới là sinh viên năm nhất còn bỡ ngỡ về một môi trường học tập mới , thay cô luôn quan tâm chúng em hỏi chúng em không hiểu chỗ nao thi chia sẻ màn hình thầy cô chỉ cho chúng em. Thầy đã truyền đạt cho chúng em rất nhiều kiến thức bé ích, giúp chúng em ngày càng hoàn thiện bản thân mình hơn. Cũng là đồ án môn cấu trúc đữ liệu và giải thuật thì cũng một lần nữa em xinh chúc tất cả các quý thầy cô giáo và Ths.Nguyễn Quốc Thanh ngày càng mạnh khỏe. Em xin chân thành cảm ơn! MUC LUC CHUONG I: GIỚI THIỆU. GiGi thi@U GE Dai. DữỮ liệu mẫu. HH SH HH HH nen hen vu 2 1. Các chức năng trên mảng cấu trÚc.c cv: 2 CHƯƠNG II: TIM KIEM VA SAP XEP TREN MANG CAU TRÚC.1 Nhap danh Sach MON NOC.cccccseceeecseeeeceeeeeeeeeeseeeetsaeeaeeeesseraneeees 4 A) CHUONG CHINN CONL. cc eeccceeeeeeseeeeseeeeesesaesaeseeeaeneeesaeeseersnsseraneere 4 b) Kiém tra (haM Main kiểm tra CC). (chen 5 C) KẾt QUả Chạy. TT n n1 nn nh He n 5 2. Xuất danh sách môn học. c1 n nghe 5 A) Chương trÌnh CON. tu nh K non nano 5 b)_ Kiểm tra (hàm Main kiểm tra CC). (chen 6 C) KẾt QUả Chạy. TT n n1 nn nh He n 7 2.3 Tìm kiếm thông tin môn học theo mã môn học dùng Liner 151121 I NI EI I EI EIU EI I EI EE EE EI EE EEE nnn Eeias 7 A) CHUONG CHINN CONL. cc eeccceeeeeeseeeeseeeeesesaesaeseeeaeneeesaeeseersnsseraneere 7 a) Ki€mtra (ham Main ki€m tra Ct) .4 Tim kiém théng tin m6n hoc theo ma mén hoc dung Binary SEQICN. I NI EI I EI EIU EI I EI EE EE EI EE EEE nnn Eeias 9 A) Chương trÌnh CON. tu nh K non nano 9 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 10 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 11 2.5 Tìm kiếm thông tin môn học theo Tên dùng Liner Search. 11 a) Chương trình COn. cuc nnn ng n TH HT Hong 11 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 11 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 12 2.6 Tìm kiếm thông tin môn học theo Tên dùng Binary Search. 12 a) Chương trình COn. cuc nnn ng n TH HT Hong 12 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 13 C) KOt QUA CHAY.7 Hàm hoán VỊ. cu uc ng ng nh ng TH nen kế HE Đế kết 14 2.8 Sắp xếp danh sách theo MaMH dùng hàm Shaker Sort. 15 a) Chương trình COn. cuc nnn ng n TH HT Hong 15 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 16 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 16 2.9 Sắp xếp danh sách theo MaMH dùng hàm Selection Sort. 16 a) Chương trình COn. cuc nnn ng n TH HT Hong 16 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 17 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 18 2.10 Sắp xếp danh sách theo Tên dùng hàm Interchange Sort. 18 a) Chương trình COn. cuc nnn ng n TH HT Hong 18 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 18 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 19 2.11 Sắp xếp danh sách theo Khóa học dùng hàm Bubble Sort.19 a) Chương trình COn. cuc nnn ng n TH HT Hong 20 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 20 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 21 2.12_ Sắp xếp danh sách theo ĐTB dùng hàm Insertion Sort. 21 a) Chương trình COn. cuc nnn ng n TH HT Hong 21 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 22 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 23 2.13 Sắp xếp danh sách theo Tín chỉ dùng hàm Quick Sort. 23 a) Chương trình COn. cuc nnn ng n TH HT Hong 23 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 24 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 25 2.14_ Sắp xếp danh sách theo MAMH dùng hàm Merge Sort. 25 a) Chương trình COn. cuc nnn ng n TH HT Hong 25 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 29 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 30 CHƯƠNG III: TÌM KIÊM VÀ SẮP XÉP TRÊN DSLK.1 Khởi tạo danh sách liên kết và các chương trình con hỗ trợ.2_ Nhập thông tin môn hỌọc.ccccnn nn nh n Tnhh heo 33 A) Chương trÌnh COn. tt kg nnn nha kho 33 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 33 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 35 3. Xuất thông tin môn hỌc.cnn ng ng Hee 35 A) Chương trÌnh COn. tt kg nnn nha kho 35 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 36 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 38 3. Đếm số phần tử có trong danh sách thông tin môn học. 38 A) Chuong trÌnh COn. tt kg nnn nhkho 38 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 38 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 40 3.5 Tìm kiếm thông tin môn học theo mã môn học bằng Liner 11121. IEE I I EE I EI EEE EEL EE Enea 40 a) Chương trình COn. cuc nnn ng n TH HT Hong 40 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 41 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 43 3.6 Tìm kiếm thông tin môn học theo tên bằng Liner Search. 43 a) Chương trình COn. cuc nnn ng n TH HT Hong 43 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 43 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 45 3.7 Hàm hoán vị hỗ trợ cho một số hàm sắp xếp.8 Sắp xếp thông tin môn học theo MaMH bằng Selection Sort.46 a) Chương trình COn. cuc nnn ng n TH HT Hong 46 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 47 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 48 3.9 Sắp xếp thông tin môn học theo mã môn hoc bang lnterchang€ SOFẨ. nen nền nh nh TH Thế BH Kế TT ben TK bến tà th 48 a) Chương trình COn. cuc nnn ng n TH HT Hong 48 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 49 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 51 3.10 Sắp xếp thông tin môn học theo mã môn học bằng Bubble Sort 51 A) Chương trÌnh COn. tt kg nnn nha kho 51 b)_ Kiểm tra (hàm Main kiểm tra CC). con nhe 52 c) Kết QUả Chạy.nnnnn TT TT Tnhh Huy 54 3.11 Sắp xếp thông tin môn học theo mã môn học bằng Insertion Sort 4 a) Chương trình COn. c c cnnnnnn ng n nghe rro 54 b) Kiểm tra (hàm Main kiểm tra CC).12 Sắp xếp thông tin môn học theo mã môn học bằng Quick Sort 56 a) Chương trình COn. c c cnnnnnn ng n nghe rro 56 b) Kiểm tra (hàm Main kiểm tra CC). 60 DANH MUC BANG, HINH A Bang 1.1 DU QU MAU. 1 K@t qua thdng tin MON NOC. 2 Xuất thông tin môn học. uc HS vn ng nghehàn 7 Hình 2. 3 Tìm kiếm mã môn học bằng Liner Search.c cv cssiiksserervsrxes 9 Hình 2. 4 Tìm kiếm mã môn học bằng Binary Search.ccc ch viyrses 11 Hình 2. 5 Tìm kiếm tên môn học bằng Liner Search.cv cksssisiivrres 12 Hình 2. 6 Tìm kiếm tên môn học bằng Binary Search.ccc ch riyrsea 14 Hình 2. 7 Sắp xếp mã môn học bằng Shaker SOFẨ.cà nh nh nh nh khen 16 Hình 2. 8 Sắp xếp mã môn học băng SeleCtiOn SOF. cu ST nh nh kh 18 Hình 2. 9 Sắp xếp tên môn học bằng Interchange SOT.- nh nen nhe 19 Hình 2. 10 Sắp xếp mã môn học băng Bubble Sort. 11 Sắp xếp theo tên môn học bằng Insertion SOFẨ. che reo 23 Hình 2. 12 Sắp xep tin chi bang Ợ gHơ7ơở7„„7Ừ7Ừýy,d 25 Hình 2. 13 Sắp xếp mã môn học bằng Merge SOF. ch xe 30 Hình 3. 1 Kết quả nhập thông tin môn học vào DSLK.‹ccccccccc‡cc+‡‡ccs+c: 35 Hình 3. 2 Kết quả xuất danh sách môn học ra mản hình. 3 Đém số lượng môn học có trong danh sách.‹cccccc‡‡‡ccxx‡+++: 40 Hình 3. 4 Tìm kiếm mã môn học có tron danh sách đã nhập ở trên. 5 Tìm kiếm tên môn học có trong danh sách đã nhập ở trên. 6 Sắp xếp mã môn học bằng S€l€CEIOH SOẨ. cu cu nh nh kh bế 48 Hình 3. 7 Sắp xếp mã môn học bằng Interchange Sort.8 Sap xếp mã môn học bằng Bubble SOY. cu nh nền kh nhe kéo 54 Hình 3. 9 Sắp xếp m4 mon hoc bang Insertion Sort. 10 Sắp xếp mã môn học bằng Quick Sort.cccccccccccsssssssssessseeseeeeaeeeeess 60 CHUONG I: GIOI THIEU 11. 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ấm 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ự. l 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. l 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: I MaMH: chuỗi gồm I0 ký tự. J TenMH: chuỗi gồm 15 kí tự. l 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; 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 Van 11 4 3 1 3 Anh 10 6 2 6 4 Sw 9 4 3 4 5 Dia 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 duc Bảng 1. 1 Dữ liệu mẫu 1. Các chức năng trén mang cau tric Nhập danh sách môn học. Xuất danh sách môn học.
Cấu Trúc Dữ Liệu và Giải Thuật tại Trường Đại Học Tài Chính - Marketing
Khám phá bài tập đồ án cấu trúc dữ liệu và giải thuật, giúp nâng cao kỹ năng lập trình và tư duy logic cho sinh viên công nghệ thông tin.
Trường đại học
Trường Đại Học Tài Chính - MarketingNgười đăng
Ẩn danh
61
0
0
Phí lưu trữ
30 PointMục lục chi tiết
Tóm tắt
I. Khám Phá Môn Cấu Trúc Dữ Liệu và Giải Thuật tại UFM
Môn học Cấu Trúc Dữ Liệu và Giải Thuật là một trong những môn học nền tảng và quan trọng nhất trong chương trình đào tạo của khoa Công nghệ thông tin UFM. Môn học này không chỉ cung cấp kiến thức về cách tổ chức, quản lý và lưu trữ dữ liệu một cách hiệu quả mà còn trang bị cho sinh viên tư duy giải quyết vấn đề thông qua các thuật toán. Việc nắm vững môn học này là chìa khóa để xây dựng các ứng dụng phần mềm tối ưu, hiệu suất cao và có khả năng mở rộng. Nội dung chương trình học được thiết kế để bao quát từ các cấu trúc dữ liệu cơ bản như mảng, danh sách liên kết, đến các cấu trúc phức tạp hơn như cây và đồ thị. Sinh viên sẽ được học cách phân tích độ phức tạp thời gian và không gian của thuật toán, một kỹ năng thiết yếu cho bất kỳ lập trình viên chuyên nghiệp nào. Toàn bộ kiến thức được truyền tải qua giáo trình Cấu trúc dữ liệu và giải thuật chính thống, kết hợp với các slide bài giảng UFM chi tiết và các bài tập lớn CTDL> mang tính ứng dụng cao, đảm bảo sinh viên không chỉ hiểu lý thuyết mà còn có khả năng áp dụng vào thực tế.
1.1. Mục tiêu và chuẩn đầu ra theo đề cương môn học CTDL GT UFM
Mục tiêu chính của môn học là giúp sinh viên hiểu và áp dụng được các cấu trúc dữ liệu phổ biến để giải quyết bài toán. Theo đề cương môn học CTDL> UFM, sau khi hoàn thành, sinh viên phải có khả năng định nghĩa và cài đặt các cấu trúc dữ liệu như mảng, danh sách liên kết, ngăn xếp, hàng đợi. Sinh viên cũng cần phân biệt và lựa chọn được thuật toán tìm kiếm và thuật toán sắp xếp phù hợp cho từng loại dữ liệu và yêu cầu cụ thể. Một chuẩn đầu ra quan trọng khác là khả năng phân tích hiệu suất thuật toán thông qua ký pháp Big O notation. Điều này giúp sinh viên đưa ra quyết định tối ưu khi thiết kế phần mềm, cân bằng giữa tốc độ xử lý và tài nguyên hệ thống. Đề cương cũng nhấn mạnh kỹ năng lập trình C++ để hiện thực hóa các giải thuật đã học, tạo ra các chương trình hoàn chỉnh và có thể chạy được.
1.2. Vai trò cốt lõi trong chương trình đào tạo của Khoa CNTT UFM
Tại khoa Công nghệ thông tin UFM, Cấu Trúc Dữ Liệu và Giải Thuật được xem là môn học bản lề. Kiến thức từ môn này là tiền đề cho hàng loạt các môn học chuyên ngành khác như Cơ sở dữ liệu, Lập trình hướng đối tượng, Trí tuệ nhân tạo và Phát triển ứng dụng web. Một lập trình viên không nắm vững cấu trúc dữ liệu cũng giống như một kiến trúc sư không hiểu về vật liệu xây dựng. Việc lựa chọn sai cấu trúc dữ liệu có thể dẫn đến các ứng dụng chạy chậm, tốn tài nguyên và khó bảo trì. Do đó, khoa CNTT luôn chú trọng vào việc đảm bảo chất lượng giảng dạy và học tập của môn này, cung cấp đầy đủ tài liệu ôn thi cấu trúc dữ liệu UFM và các nguồn học liệu tham khảo để sinh viên có thể đạt được kết quả tốt nhất, tạo nền tảng vững chắc cho sự nghiệp sau này.
II. Thách Thức Khi Học Cấu Trúc Dữ Liệu và Giải Thuật UFM
Mặc dù là môn học quan trọng, Cấu Trúc Dữ Liệu và Giải Thuật cũng là một thử thách lớn đối với nhiều sinh viên tại Đại học Tài chính - Marketing. Khó khăn không chỉ đến từ tính trừu tượng của các khái niệm lý thuyết mà còn ở yêu cầu cao về kỹ năng lập trình và tư duy logic. Sinh viên phải chuyển đổi từ việc viết các đoạn mã đơn giản sang thiết kế các hệ thống logic phức tạp. Việc hiểu và áp dụng các khái niệm như đệ quy, con trỏ trong lập trình C++ để cài đặt danh sách liên kết đơn hay cây nhị phân tìm kiếm đòi hỏi sự tập trung và luyện tập thường xuyên. Thêm vào đó, việc phân tích độ phức tạp thời gian của một giải thuật không phải là điều dễ dàng, nó yêu cầu nền tảng toán học và khả năng phân tích logic sắc bén. Vượt qua những thách thức này là một quá trình rèn luyện quan trọng, giúp sinh viên trưởng thành hơn trong tư duy lập trình và giải quyết vấn đề.
2.1. Phân tích độ phức tạp thời gian và không gian Big O notation
Một trong những rào cản lớn nhất là khái niệm về độ phức tạp thời gian và Big O notation. Đây là các công cụ toán học dùng để đo lường hiệu suất của thuật toán một cách tổng quát, không phụ thuộc vào phần cứng máy tính. Sinh viên thường gặp khó khăn trong việc xác định độ phức tạp của các vòng lặp lồng nhau, các lời gọi hàm đệ quy, hay phân tích sự khác biệt giữa các trường hợp tốt nhất, trung bình và xấu nhất. Việc không hiểu rõ Big O notation sẽ dẫn đến việc lựa chọn thuật toán không tối ưu, ảnh hưởng trực tiếp đến chất lượng sản phẩm phần mềm. Nắm vững phần kiến thức này đòi hỏi sinh viên phải kết hợp giữa lý thuyết trong giáo trình Cấu trúc dữ liệu và giải thuật và việc thực hành phân tích trên các đoạn mã cụ thể.
2.2. Hiện thực hóa giải thuật bằng ngôn ngữ lập trình C
Lý thuyết suông là chưa đủ. Môn học tại UFM yêu cầu sinh viên phải hiện thực hóa các cấu trúc dữ liệu và giải thuật bằng ngôn ngữ lập trình C++. Thách thức nằm ở việc quản lý bộ nhớ động bằng con trỏ, xử lý các trường hợp biên và đảm bảo mã nguồn chạy đúng với mọi loại dữ liệu đầu vào. Tài liệu đồ án của sinh viên Nguyễn Xuân Tỉnh là một minh chứng rõ ràng, trong đó việc cài đặt các thuật toán sắp xếp như Quick Sort, Merge Sort trên cả mảng và danh sách liên kết đơn đòi hỏi sự tỉ mỉ và chính xác cao. Việc gỡ lỗi (debug) các thuật toán phức tạp cũng là một kỹ năng quan trọng mà sinh viên phải tự rèn luyện trong quá trình làm bài tập lớn CTDL>.
III. Phương Pháp Nắm Vững Các Cấu Trúc Dữ Liệu Cốt Lõi UFM
Để chinh phục môn học Cấu Trúc Dữ Liệu và Giải Thuật, việc nắm vững các cấu trúc dữ liệu cốt lõi là bước đi đầu tiên và quan trọng nhất. Một cấu trúc dữ liệu là một cách tổ chức dữ liệu trong máy tính để có thể được sử dụng một cách hiệu quả. Tại UFM, chương trình học tập trung vào việc giúp sinh viên hiểu sâu sắc bản chất, ưu nhược điểm và các phép toán cơ bản trên từng loại cấu trúc. Sinh viên sẽ bắt đầu với các cấu trúc tuyến tính như mảng và danh sách liên kết đơn, sau đó tiến tới các cấu trúc phi tuyến phức tạp hơn. Phương pháp học hiệu quả là không chỉ học thuộc định nghĩa mà cần phải tự tay cài đặt từng cấu trúc dữ liệu từ đầu. Quá trình này giúp hiểu rõ cách chúng hoạt động 'bên trong', từ đó có thể vận dụng linh hoạt vào việc giải quyết các bài toán thực tế. Tham khảo các slide bài giảng UFM và làm lại các ví dụ trong đó là một cách tuyệt vời để củng cố kiến thức nền tảng.
3.1. Cấu trúc tuyến tính Danh sách liên kết Ngăn xếp và Hàng đợi
Các cấu trúc dữ liệu tuyến tính là nền tảng cơ bản nhất. Trong khi mảng có kích thước cố định, danh sách liên kết đơn (Singly Linked List) mang lại sự linh hoạt trong việc thêm, xóa phần tử mà không cần di dời các phần tử khác. Việc hiểu rõ về con trỏ và quản lý bộ nhớ động là chìa khóa để làm chủ cấu trúc này. Bên cạnh đó, ngăn xếp và hàng đợi (stack and queue) là hai cấu trúc dữ liệu trừu tượng với các quy tắc truy cập đặc biệt (LIFO cho stack, FIFO cho queue). Chúng có vô số ứng dụng trong thực tế, chẳng hạn như quản lý lịch sử duyệt web (stack) hay hệ thống xếp hàng xử lý tác vụ (queue). Sinh viên cần nắm vững các thao tác cơ bản như Push, Pop, Enqueue, Dequeue và cách cài đặt chúng bằng mảng hoặc danh sách liên kết.
3.2. Cấu trúc phi tuyến Cây nhị phân tìm kiếm và Lý thuyết đồ thị
Khi dữ liệu có mối quan hệ phân cấp hoặc mạng lưới, các cấu trúc phi tuyến trở nên cần thiết. Cây nhị phân tìm kiếm (Binary Search Tree) là một cấu trúc dữ liệu dạng cây cho phép thực hiện các thao tác tìm kiếm, chèn, xóa phần tử với hiệu suất rất cao (thường là O(log n)). Nó là nền tảng cho nhiều cấu trúc dữ liệu phức tạp hơn như cây AVL, cây Đỏ-Đen. Một lĩnh vực quan trọng khác là lý thuyết đồ thị, dùng để mô hình hóa các mối quan hệ giữa các đối tượng. Đồ thị có ứng dụng rộng rãi trong mạng xã hội, hệ thống định vị GPS, và tối ưu hóa mạng lưới. Sinh viên cần làm quen với các khái niệm như đỉnh, cạnh, đồ thị vô hướng/có hướng và các thuật toán duyệt đồ thị cơ bản như BFS và DFS.
IV. Bí Quyết Áp Dụng Thuật Toán Sắp Xếp và Tìm Kiếm UFM
Nắm vững cấu trúc dữ liệu chỉ là một nửa của câu chuyện. Nửa còn lại là việc áp dụng các giải thuật hiệu quả để thao tác trên dữ liệu đó. Tại Đại học Tài chính - Marketing, hai nhóm thuật toán quan trọng nhất được giảng dạy là tìm kiếm và sắp xếp. Đây là những bài toán kinh điển và phổ biến nhất trong khoa học máy tính. Việc lựa chọn đúng thuật toán tìm kiếm hay thuật toán sắp xếp có thể tạo ra sự khác biệt lớn về hiệu năng của một chương trình. Ví dụ, tìm kiếm trên một danh sách đã được sắp xếp sẽ nhanh hơn rất nhiều so với danh sách lộn xộn. Như được thể hiện trong tài liệu đồ án môn học, sinh viên UFM được yêu cầu cài đặt và so sánh hiệu quả của nhiều thuật toán khác nhau. Quá trình này giúp sinh viên không chỉ thuộc lòng mã nguồn mà còn hiểu sâu sắc về nguyên lý hoạt động và độ phức tạp thời gian của từng giải pháp, từ đó hình thành tư duy tối ưu hóa.
4.1. Kỹ thuật tìm kiếm Từ tuyến tính Linear đến nhị phân Binary
Tìm kiếm là thao tác cơ bản nhằm xác định vị trí của một phần tử trong tập dữ liệu. Thuật toán tìm kiếm tuyến tính (Linear Search) là phương pháp đơn giản nhất, duyệt qua từng phần tử cho đến khi tìm thấy. Tuy nhiên, nó không hiệu quả với tập dữ liệu lớn. Ngược lại, tìm kiếm nhị phân (Binary Search) mang lại hiệu suất vượt trội, nhưng yêu cầu dữ liệu phải được sắp xếp trước. Đồ án của sinh viên UFM đã triển khai cả hai thuật toán này để tìm kiếm thông tin môn học theo mã và tên. Điều này cho thấy chương trình học nhấn mạnh việc so sánh và lựa chọn thuật toán dựa trên điều kiện của dữ liệu đầu vào. Hiểu rõ khi nào nên dùng Linear Search và khi nào nên dùng Binary Search là một kỹ năng quan trọng.
4.2. Các thuật toán sắp xếp kinh điển Quick Sort Merge Sort etc.
Sắp xếp là quá trình tổ chức lại các phần tử trong một danh sách theo một thứ tự nhất định. Đây là một trong những lĩnh vực được nghiên cứu sâu rộng nhất. Tài liệu đồ án môn học tại UFM đã trình bày việc cài đặt một loạt các thuật toán sắp xếp kinh điển, bao gồm: Selection Sort, Interchange Sort, Bubble Sort, Insertion Sort, Shaker Sort, Quick Sort, và Merge Sort. Mỗi thuật toán có một chiến lược tiếp cận và độ phức tạp thời gian khác nhau. Các thuật toán đơn giản như Bubble Sort dễ cài đặt nhưng chậm (O(n²)), trong khi các thuật toán phức tạp hơn như Quick Sort và Merge Sort lại hiệu quả hơn nhiều (O(n log n)) với dữ liệu lớn. Việc triển khai tất cả các thuật toán này giúp sinh viên có cái nhìn toàn cảnh và thực tiễn về tối ưu hóa hiệu năng.
V. Ứng Dụng Qua Bài Tập Lớn Môn Cấu Trúc Dữ Liệu UFM
Lý thuyết sẽ trở nên vô nghĩa nếu không thể áp dụng vào thực tế. Khoa Công nghệ thông tin UFM hiểu rõ điều này và luôn tích hợp các dự án thực hành vào chương trình giảng dạy. Bài tập lớn CTDL> là một thành phần bắt buộc và chiếm trọng số điểm cao trong môn học. Mục đích của bài tập lớn là tạo cơ hội để sinh viên tổng hợp toàn bộ kiến thức đã học, từ việc lựa chọn cấu trúc dữ liệu phù hợp, cài đặt các thuật toán cần thiết, cho đến việc xây dựng một chương trình hoàn chỉnh giải quyết một bài toán cụ thể. Đề tài thường xoay quanh các bài toán quản lý quen thuộc, như quản lý sinh viên, quản lý thư viện, hoặc như trong tài liệu tham khảo, là quản lý thông tin môn học. Quá trình làm bài tập lớn là cơ hội quý báu để sinh viên rèn luyện kỹ năng lập trình C++, kỹ năng làm việc nhóm, và quan trọng nhất là tư duy của một kỹ sư phần mềm thực thụ.
5.1. Xây dựng chương trình quản lý thông tin môn học thực tế
Như ví dụ từ đồ án của sinh viên Nguyễn Xuân Tỉnh, một bài tập lớn CTDL> điển hình tại UFM yêu cầu xây dựng một hệ thống quản lý thông tin các môn học. Hệ thống này cần thực hiện các chức năng cơ bản như nhập, xuất danh sách, và đặc biệt là các chức năng tìm kiếm và sắp xếp. Sinh viên phải tự định nghĩa cấu trúc dữ liệu để lưu trữ thông tin (ví dụ struct MONHOC), sau đó triển khai các chức năng trên cả cấu trúc mảng và danh sách liên kết đơn. Bài tập này không chỉ kiểm tra kiến thức về thuật toán mà còn đánh giá khả năng thiết kế và tổ chức mã nguồn của sinh viên một cách logic và khoa học. Việc hoàn thành tốt dự án này chứng tỏ sinh viên đã thực sự làm chủ được kiến thức môn học.
5.2. Nguồn tài liệu và slide bài giảng UFM hỗ trợ học tập
Để hỗ trợ sinh viên trong quá trình học và làm bài tập lớn, UFM cung cấp nhiều nguồn tài liệu quý giá. Giáo trình Cấu trúc dữ liệu và giải thuật là tài liệu chính, cung cấp kiến thức lý thuyết một cách hệ thống và bài bản. Bên cạnh đó, các slide bài giảng UFM do giảng viên biên soạn thường chứa các ví dụ minh họa trực quan, các đoạn mã mẫu và tóm tắt những điểm kiến thức quan trọng nhất của mỗi chương. Sinh viên nên tận dụng tối đa các nguồn tài liệu này, kết hợp với việc tìm kiếm thêm các tài liệu ôn thi cấu trúc dữ liệu UFM từ các khóa trước để có sự chuẩn bị tốt nhất cho các bài kiểm tra và kỳ thi cuối kỳ. Sự chủ động trong việc học và tìm kiếm tài liệu là yếu tố quyết định đến thành công trong môn học này.
10/07/2025
TÀI LIỆU LIÊN QUAN
Bạn đang xem trước tài liệu:
Bài tập đồ án cấu trúc dữ liệu và giải thuật
THÔNG TIN CHI TIẾT
Trường học: Trường Đại Học Tài Chính - Marketing
Đề tài: Cấu Trúc Dữ Liệu và Giải Thuật tại Trường Đại Học Tài Chính - Marketing
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ