Giới thiệu CTDL & GT

ĐỀ CƯƠNG CHI TIẾT MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (Data Structures and Algorithms)

1. Mục tiêu của môn học: 

Môn học này giúp sinh viên thực sự hiểu được tầm quan trọng của giải thuật và cách tổ chức dữ liệu, là hai thành tố quan trọng nhất cho một chương trình. Ngoài ra, giai đoạn này còn giúp sinh viên củng cố và phát triển kỹ năng lập trình vừa được học trong giai đoạn trước

2. Nội dung tóm tắt:

Môn học trình bày các phương pháp tổ chức và những thao tác cơ sở trên từng cấu trúc dữ liệu, kết hợp với việc phát triển tư duy giải thuật để hình thành nên chương trình máy tính. Công cụ được sử dụng để hiện thực là ngôn ngữ lập trình cấp cao C++.

3. Tài liệu tham khảo:

[1] Robert L.Kruse, Alexander J.Ryba, Data Structures And

     Program Design In C++, Prentice-Hall International, Inc., 1999.

[2] Hoàng Kiếm, Giáo trình cấu trúc dữ liệu - Nhà xuất bản Giáo dục, 1996.

[3] VC++ 6.0

Nội dung chi tiết môn học:

Chương I   Các nguyên tắc lập trình

1.1 Giới thiệu

1.2 Trò chơi sinh tồn (The Game of life)

1.3 Phong cách lập trình

1.4 Viết chương trình (coding), kiểm tra và tinh chế

      từng bước

1.5 Bảo trì chương trình

Chương II    Chồng (Stacks)

2.1 Các loại Stack

2.2 Hiện thực (Cấu trúc và các thao tác)

2.3 Các ví dụ

Chương III  Hàng đợi (Queues)

3.1 Các loại Queue

3.2 Hiện thực (Cấu trúc và các thao tác)

3.3 Ví dụ

Chương IV   Đệ quy

4.1 Giới thiệu về đệ quy

4.2 Nguyên tắc của đệ quy

4.3 Sự quay lui (Backtracking)

4.4 Chương trình cấu trúc cây

Chương V   Danh sách và chuỗi

5.1 Định nghĩa

5.2 Hiện thực (Cấu trúc và các thao tác)

5.3 Chuỗi

5.4 Ứng dụng

5.5 Danh sách liên kết trong các mảng (arrays) 

Chương VI   Tìm kiếm

6.1 Giới thiệu

6.2 Tìm kiếm tuần tự

6.3 Tìm kiếm nhị phân

6.4 Cây so sánh

Chương VII   Sắp xếp

7.1 Giới thiệu

7.2 Phương pháp chèn trực tiếp

7.3 Phương pháp chọn trực tiếp

7.4 Phương pháp Shell Sort

7.5 Merge Sort cho danh sách liên kết

7.6 Quick Sort

7.7 Heap Sort

Chương VIII   Các bảng và phục hồi thông tin

8.1 Giới thiệu

8.2 Các bảng

8.3 Các loại dữ liệu trừu tượng mới

8.4 Ứng dụng Radix sort

8.5 Bảng băm

Chương IX   Cây nhị phân

9.1 Các loại cây nhị phân

9.2 Cây nhị phân tìm kiếm (BST)

9.3 Các tác vụ trên cây BST (duyệt, thêm, xóa, sửa)

9.4 Xây dựng cây nhị phân tìm kiếm

9.5 Cây cân bằng

Chương X   Cây nhiều nhánh

10.1  B - Cây

10.2  Cây đỏ đen (Red-Black)