Cấu trúc dữ liệu
PGS. TS. Trần Cao Đệ
PGS. TS. Trần Cao Đệ
HK 1 Năm 2015-2016
HK 1 Năm 2015-2016
Mục đích yêu cầu
•Môn học cấu trúc dữ liệu cung cấp 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 cơ bản trên
kiểu dữ liệu đó.
•Sau khi học xong môn này, sinh viên sẽ:
–Nắm được 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ế.
Nội dung giáo trình
Nội dung giáo trình
•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
•Chương 2:
–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ấu trúc danh sách liên kết kép
•Chương 3:
–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.
–Cây nhị phân, các cách cài đặt
cây nhị phân
–Cây tìm kiếm nhị phân
•Chương 4:
–Kiểu dữ liệu trừu tượng tập hợp,
–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:
–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ị.
–Các phép duyệt đồ thị
–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.…
Thời lượng
Thời lượng
•LT 3 tín chỉ (45 tiết) : hoc tại lớp 9 buổi
–30 tiết giảng lý thuyết
–15 tiết bài tập mà giáo viên sẽ hướng dẫn cho sinh
viên trên lớp.
–Vắng 3 buổi: cấm thi
•Thực hành 1TC: tại phòng máy 6 buổi
–1 tín chỉ: 15 tiết = 6 buổi
–ngôn ngữ lập trình C (Dev C++)
–Vắng 1 buổi: cấm thi
Tài liệu tham khảo
Tài liệu tham khảo
Tham khảo chính: Giáo trình môn CTDL. Trần Cao Đệ,
2012, download trên www.cit.ctu.edu.vn/~tcde
[1] Aho, A. V. , J. E. Hopcroft, J. D. Ullman, "Data Structure and Algorihtms",
Addison–Wesley; 1983.
[2] Michel T. Goodrich, Roberto Tamassia, David Mount, “Data Structures
and Algorithms in C++”, Weley International Edition; 2004.
[3] Đỗ Xuân Lôi, "Cấu trúc dữ liệu và giải thuật", Nhà xuất bản khoa học và kỹ
thuật, Hà nội, 1995.
[4] N. Wirth " Cấu trúc dữ liệu + giải thuật= Chương trình", 1983.