TÀI LIỆU TÀI LIỆU Giáo trình cấu trúc dữ liệu và giải thuật pdf

Yopovn · 3/4/24

TÀI LIỆU Giáo trình cấu trúc dữ liệu và giải thuật pdf được soạn dưới dạng file PDF gồm 151 trang. Các bạn xem và tải về ở dưới.

Giáo trình Cấu trúc dữ liệu và giải thuật – ĐH Cần Thơ

NGUYỄN VĂN LINH
TRẦN CAO ĐỆ

TRƯƠNG THỊ THANH TUYỀN

LÂM HOÀI BẢO
PHAN HUY CƯỜNG
TRẦN NGÂN BÌNH

CẤU TRÚC DỮ LIỆU

Trang 1

Cấu trúc dữ liệu Lời nói đầu

ĐẠI HỌC CẦN THƠ – 12/2003

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

Trang 2

Cấu trúc dữ liệu Mục lục

MỤC LỤC

CHƯƠNG I MỞ ĐẦU..............................................................................................................9 U
I. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH...................................................................................9
1. Mô hình hóa bài toán thực tế................................................................................................9
2. Giải thuật (algorithms) .......................................................................................................12
3. Ngôn ngữ giả và tinh chế từng bước (Pseudo-language and stepwise refinement) ...........15
4. Tóm tắt................................................................................................................................17
II. KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE)................................................18
1. Khái niệm trừu tượng hóa...................................................................................................18
2. Trừu tượng hóa chương trình .............................................................................................18
3. Trừu tượng hóa dữ liệu.......................................................................................................19
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)..........................................................20
CHƯƠNG II CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN...............................................22
(BASIC ABSTRACT DATA TYPES) ......................................................................................22
I. KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST) .........................................................24
1. Khái niệm danh sách ..........................................................................................................24
2. Các phép toán trên danh sách .............................................................................................24
3. Cài đặt danh sách................................................................................................................26
II. NGĂN XẾP (STACK) .............................................................................................................43
1. Định nghĩa ngăn xếp...........................................................................................................43
2. Các phép toán trên ngăn xếp ..............................................................................................44
3. Cài đặt ngăn xếp .................................................................................................................45
4. Ứng dụng ngăn xếp để loại bỏ đệ qui của chương trình.....................................................48
III. HÀNG ĐỢI (QUEUE)........................................................................................................53
1. Định Nghĩa .........................................................................................................................53
2. Các phép toán cơ bản trên hàng..........................................................................................53
3. Cài đặt hàng........................................................................................................................53
4. Một số ứng dụng của cấu trúc hàng....................................................................................62
IV. DANH SÁCH LIÊN KẾT KÉP (double - lists) ...................................................................62
BÀI TẬP............................................................................................................................................68
CHƯƠNG III CẤU TRÚC CÂY (TREES) ...............................................................................73
I. CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY...............................................................................74
1. Định nghĩa ..........................................................................................................................74
2. Thứ tự các nút trong cây.....................................................................................................75
3. Các thứ tự duyệt cây quan trọng.........................................................................................75
4. Cây có nhãn và cây biểu thức.............................................................................................76
II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY ...................................................................................78
III. CÀI ĐẶT CÂY.....................................................................................................................79
1. Cài đặt cây bằng mảng .......................................................................................................79

Trang 3

Cấu trúc dữ liệu Mục lục

2. Biểu diễn cây bằng danh sách các con ...............................................................................85
3. Biểu diễn theo con trái nhất và anh em ruột phải:..............................................................86
4. Cài đặt cây bằng con trỏ .....................................................................................................87
IV. CÂY NHỊ PHÂN (BINARY TREES)....................................................................................87
1. Định nghĩa ..........................................................................................................................87
2. Duyệt cây nhị phân.............................................................................................................88
3. Cài đặt cây nhị phân ...........................................................................................................89
V. CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES).....................................................92
1. Định nghĩa ..........................................................................................................................92
2. Cài đặt cây tìm kiếm nhị phân............................................................................................93
BÀI TẬP..........................................................................................................................................100
CHƯƠNG IV TẬP HỢP ......................................................................................................103
I. KHÁI NIỆM TẬP HỢP.........................................................................................................104
II. KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP ....................................................................104
III. CÀI ĐẶT TẬP HỢP..........................................................................................................105
1. Cài đặt tập hợp bằng vector Bit........................................................................................105
2. Cài đặt bằng danh sách liên kết ........................................................................................107
IV. TỪ ĐIỂN (dictionary) .....................................................................................................111
1. Cài đặt từ điển bằng mảng................................................................................................111
2. Cài đặt từ điển bằng bảng băm .........................................................................................113
3. Các phương pháp xác định hàm băm ...............................................................................122
V. HÀNG ƯU TIÊN (priority queue) ....................................................................................123
1. Khái niệm hàng ưu tiên ....................................................................................................123
2. Cài đặt hàng ưu tiên..........................................................................................................124
BÀI TẬP..........................................................................................................................................131
CHƯƠNG V ĐỒ THỊ (GRAPH) .............................................................................................133
I. CÁC ĐỊNH NGHĨA ..............................................................................................................134
II. KIỂU DỮ LIỆU TRỪU TƯỢNG ĐỒ THỊ............................................................................135
III. BIỂU DIỄN ĐỒ THỊ ........................................................................................................136
1. Biểu diễn đồ thị bằng ma trận kề......................................................................................136
2. Biểu diễn đồ thị bằng danh sách các đỉnh kề: ..................................................................138
IV. CÁC PHÉP DUYỆT ĐỒ THỊ (traversals of graph).........................................................138
1. Duyệt theo chiều sâu (depth-first search).........................................................................139
2. Duyệt theo chiều rộng (breadth-first search)....................................................................140
V. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ ....................................................................................143
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) ...................................................................................................................................143
2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.............................................................145
3. Bài toán tìm bao đóng chuyển tiếp (transitive closure)....................................................146

Trang 4

Cấu trúc dữ liệu Mục lục

4. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree).................................147
BÀI TẬP..........................................................................................................................................150

Trang 5

Cấu trúc dữ liệu Phần tổng quan

PHẦN TỔNG QUAN

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án tin, 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