Cấu trúc dữ liệu – ĐH Cần Thơ

0
75

Lời nói đầu:

Để đáp ứng nhu cầu học tập của các bạn sinh viên, nhất là sinh viên chuyên ngành tin học, Khoa Công Nghệ Thông Tin Trường Đại Học Cần Thơ chúng tôi đã tiến hành biên soạn các giáo trình, bài giảng chính trong chương trình học. Giáo trình môn Cấu Trúc Dữ Liệu này được biên soạn cơ bản dựa trên quyển “Data Structures and Algorithms” của Alfred V. Aho, John E.Hopcroft và Jeffrey D. Ullman do Addison-Wesley tái bản năm 1987. Giáo trình này cũng được biên soạn dựa trên kinh nghiệm giảng dạy nhiều năm môn Cấu Trúc Dữ Liệu và Giải Thuật của chúng tôi.

Tài liệu này được soạn theo đề cương chi tiết môn Cấu Trúc Dữ Liệu của sinh viên chuyên ngành tin học của Khoa Công Nghệ Thông Tin Trường Đại Học Cần Thơ. Mục tiêu của nó nhằm giúp các bạn sinh viên chuyên ngành có một tài liệu cô đọng dùng làm tài liệu học tập, nhưng chúng tôi cũng không loại trừ toàn bộ các đối tượng khác tham khảo. Chúng tôi nghĩ rằng các bạn sinh viên không chuyên tin và những người quan tâm tới cấu trúc dữ liệu và giải thuật sẽ tìm được trong này những điều hữu ích.

Mặc dù đã rất cố gắng nhiều trong quá trình biên soạn giáo trình nhưng chắc chắn giáo trình sẽ còn nhiều thiếu sót và hạn chế. Rất mong nhận được sự đóng góp ý kiến quý báu của sinh viên và các bạn đọc để giáo trình ngày một hoàn thiện hơn.

Cần thơ, ngày 10 tháng 11 năm 2003

Các tác giả: Trần Cao Đệ, Nguyễn Văn Linh, Trương Thị Thanh Tuyền, Lâm Hoài Bảo, Phan Huy Cường, Trần Ngân Bình

MỤC LỤC

CHƯƠNG I: MỞ ĐẦU
I. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
1. Mô hình hóa bài toán thực tế
2. Giải thuật (algorithms)
3. Ngôn ngữ giả và tinh chế từng bước (Pseudo-language and stepwise refinement)
4. Tóm tắt
II. KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE)
1. Khái niệm trừu tượng hóa
2. Trừu tượng hóa chương trình
3. Trừu tượng hóa dữ liệu
III. KIỂU DỮ LIỆU – CẤU TRÚC DỮ LIỆU VÀ KIỂU DỮ LIỆU TRỪU TƯỢNG (DATA TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES)

CHƯƠNG II: CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN (BASIC ABSTRACT DATA TYPES)
I. KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST)
1. Khái niệm danh sách
2. Các phép toán trên danh sách
3. Cài đặt danh sách
II. NGĂN XẾP (STACK)
1. Định nghĩa ngăn xếp
2. Các phép toán trên ngăn xếp
3. Cài đặt ngăn xếp
4. Ứng dụng ngăn xếp để loại bỏ đệ qui của chương trình
III. HÀNG ĐỢI (QUEUE)
1. Định Nghĩa
2. Các phép toán cơ bản trên hàng
3. Cài đặt hàng
4. Một số ứng dụng của cấu trúc hàng
IV. DANH SÁCH LIÊN KẾT KÉP (double – lists)
BÀI TẬP

CHƯƠNG III: CẤU TRÚC CÂY (TREES)
I. CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY
1. Định nghĩa
2. Thứ tự các nút trong cây
3. Các thứ tự duyệt cây quan trọng
4. Cây có nhãn và cây biểu thức
II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY
III. CÀI ĐẶT CÂY
1. Cài đặt cây bằng mảng
2. Biểu diễn cây bằng danh sách các con
3. Biểu diễn theo con trái nhất và anh em ruột phải
4. Cài đặt cây bằng con trỏ
IV. CÂY NHỊ PHÂN (BINARY TREES)
1. Định nghĩa
2. Duyệt cây nhị phân
3. Cài đặt cây nhị phân
V. CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES)
1. Định nghĩa
2. Cài đặt cây tìm kiếm nhị phân
BÀI TẬP

CHƯƠNG IV: TẬP HỢP
I. KHÁI NIỆM TẬP HỢP
II. KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP
III. CÀI ĐẶT TẬP HỢP
1. Cài đặt tập hợp bằng vector Bit
2. Cài đặt bằng danh sách liên kết
IV. TỪ ĐIỂN (dictionary)
1. Cài đặt từ điển bằng mảng
2. Cài đặt từ điển bằng bảng băm
3. Các phương pháp xác định hàm băm
V. HÀNG ƯU TIÊN (priority
1. Khái niệm hàng ưu tiên
2. Cài đặt hàng ưu tiên
BÀI TẬP

CHƯƠNG V: ĐỒ THỊ (GRAPH)
I. CÁC ĐỊNH NGHĨA
II. KIỂU DỮ LIỆU TRỪU TƯỢNG
III. BIỂU DIỄN ĐỒ THỊ
1. Biểu diễn đồ thị bằng ma trận kề
2. Biểu diễn đồ thị bằng danh sách các đỉnh kề
IV. CÁC PHÉP DUYỆT ĐỒ THỊ (traversals of graph)
1. Duyệt theo chiều sâu (depth-first search)
2. Duyệt theo chiều rộng (breadth-first search)
V. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ
1. Bài toán tìm đuờng đi ngắn nhất từ một đỉnh của đồ thị(the single source shorted path
problem)
2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
3. Bài toán tìm bao đóng chuyển tiếp (transitive closure)
4. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree)
BÀI TẬP

Xem trước:

Tải về: http://go.hohoa.org/v

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments