1. Mục đích yêu cầu Môn học cấu trúc dữliệu cung cấp cho sinh viên một khối lượng lớn các kiến thức cơbản vềcác kiểu dữliệu trừu tượng và các phép toán trên kiểu dữliệu đó. Sau khi học xong môn này, sinh viên cần phải: – Nắm vững khái niệm kiểu dữliệu, kiểu dữliệu trừu tượng. – Nắm vững và cài đặt được các kiểu dữliệu trừu tượng cơbản nhưdanh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng băm, đồthịbằng một ngôn ngữlập trình căn bản. – Vận dụng được các kiểu dữliệu trừu tượng đểgiải quyết bài toán đơn giản trong thực tế. 2. Đối tượng sửdụng Môn học cấu trúc dữliệu được dùng đểgiảng dạy cho các sinh viên sau: – Sinh viên năm thứ2 chuyên ngành Tin học (môn bắt buộc ) – Sinh viên năm thứ2 chuyên ngành Toántin, Lý tin (môn bắt buộc) – Sinh viên năm thứhai chuyên ngành Điện tử- Viễn thông và tự động hóa (môn tựchọn) 3. Nội dung cốt lõi Nội dung giáo trình gồm 5 chương và đuợc trình bày trong 60 tiết cho sinh viên, trong đó có khoảng 40 tiết lý thuyết và 20 tiết bài tập mà giáo viên sẽhướng dẫn cho sinh viên trên lớp. Bên cạnh tài liệu này còn có tài liệu thực hành cấu trúc dữliệu, do vậy nội dung giáo trình hơi chú trọng vềcác cấu trúc dữliệu và các giải thuật trên các cấu trúc dữliệu đó hơn là các chương trình hoàn chỉnh trong ngôn ngữlập trình C. Chương 1:Trình bày cách tiếp cận từmột bài toán đến chương trình, nó bao gồm mô hình hoá bài toán, thiết lập cấu trúc dữliệu theo mô hình bài toán, viết giải thuật giải quyết bài toán và các bước tinh chếgiải thuật đưa đến cài đặt cụthểtrong một ngôn ngữ lập trình Chương 2:Trình bày kiểu dữliệu trừu tượng danh sách, các cấu trúc dữliệu đểcài đặt danh sách. Ngăn xếp và hàng đợi cũng được trình bày trong chương này nhưlà hai cấu trúc danh sách đăc biệt. Ở đây chúng tôi cũng muốn trình bày việc ứng dụng ngăn xếp để khử đệqui của chương trình và nêu một số ứng dụng của hàng đợi. Cuối chương, chúng tôi trình bày cấu trúc danh sách liên kết kép cho những bài toán cần duyệt danh sách theo hai chiều xuôi, ngược một cách thuận lợi. Chương này có nhiều cài đặt tương đối chi tiết đểcác bạn sinh viên mới tiếp cận với lập trình có cơhội nâng cao khảnăng lập trình trong ngôn ngữC đồng thời cũng nhằm minh hoạviệc cài đặt một kiểu dữliệu trừu tượng trong một ngôn ngữlập trình cụthể. Chương 3:Chương này giới thiệu vềkiểu dữliệu trừu tượng cây, khái niệm cây tổng quát, các phép duyệt cây tổng quát và cài đặt cây tổng quát. Kế đến chúng tôi trình bày về cây nhịphân, các cách cài đặt cây nhịphân và ứng dụng cây nhịphân đểxây dựng mã Huffman. Cuối cùng, chúng tôi trình bày cây tìm kiếm nhịphân nhưlà một ứng dụng của cây nhịphân đểlưu trữvà tìm kiếm dữliệu. Chương 4: Chương này dành đểnói vềkiểu dữliệu trừu tượng tập hợp, các cách đơn giản đểcài đặt tập hợp nhưcài đặt bằng vectơbít hay bằng danh sách có hoặc không có thứtự. Phần chính của chương này trình bày cấu trúc dữliệu tự điển, đó là tập hợp với ba phép toán thêm, xoá và tìm kiếm phần tử, cùng với các cấu trúc thích hợp cho nó nhưlà bảng băm và hàng ưu tiên. Chương 5: Trình bày kiểu dữliệu trừu tượng đồthị, các cách biểu diễn đồthịhay là cài đặt đồthị. Ở đây chúng tôi cũng trình bày các phép duyệt đồthịbao gồm duyệt theo chiều rộng và duyệt theo chiều sâu một đồthị. Do hạn chếvềthời lượng lên lớp nên chúng tôi không tách riêng ra đểtrình bày đồthịcó hướng, đồthịvô hướng nhưng chúng tôi sẽphân biệt nó ởnhững chổcần thiết. Chương này đềcập một sốbài toán thường gặp trên đồthịnhưlà bài toán tìm đường đi ngắn nhất, bài toán tìm cây phủtối thiểu. Chương này được giới thiệu đểsinh viên tham khảo thêm vềcách cài đặt đồthị và các bài toán trên đồthị. 4. Kiến thức tiên quyết Đểhọc tốt môn học cấu trúc dữliệu này, sinh viên cần phải có các kiến thức cơbản sau: – Kiến thức và kỹnăng lập trình căn bản. – Kiến thức toán rời rạc.