Giáo trình Cấu trúc dữ liệu - Đại học 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
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
2
Trang
Cấu trúc dữ liệu
Mục lục
MỤC LỤC
CHƯƠNG I MỞ ĐẦU..............................................................................................................9
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
4. Tóm tắt................................................................................................................................17
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
TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES)..........................................................20
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
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
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
CÀI ĐẶT CÂY.....................................................................................................................79
1. Cài đặt cây bằng mảng .......................................................................................................79
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
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
KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP ....................................................................104
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
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
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
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
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
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
4
Trang
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
6
Cấu trúc dữ liệu
Phần tổng quan
để 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.
5. Danh mục tài liệu tham khảo
[1] Aho, A. V. , J. E. Hopcroft, J. D. Ullman. "Data Structure and Algorihtms", Addison–
Wesley; 1983
[2] Đỗ 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.
[3] N. Wirth " Cấu trúc dữ liệu + giải thuật= Chương trình", 1983.
[4] Nguyễn Trung Trực, "Cấu trúc dữ liệu". BK tp HCM, 1990.
[5] Lê Minh Trung ; “Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu “; 1997
7
Trang
Cấu trúc dữ liệu
Phần tổng quan
[6] Ngô Trung Việt, “Ngôn ngữ lập trình C và C++ Bài giảng- Bài tập – Lời giải mẫu”;
NXB Giao thông vận tải, 2000.
[7] Nguyễn Đình Tê, Hoàng Đức Hải, “ Giáo trình lý thuyết và bài tập ngôn ngữ C” ,
NXB Giáo dục; 1998.
[8] Lê Xuân Trường, “ Giáo trình cấu trúc dữ liệu bằng ngôn ngữ C++”; NXB thống kê;
1999.
[9] Nguyễn Thanh Thủy, Nguyễn Quang Huy ,” Bài tập lập trình ngôn ngữ C”, NXB
Khoa học kỹ thuật, 1999.
[10] Michel T. Goodrich, Roberto Tamassia, David Mount, “Data Structures and
Algorithms in C++”. Weley International Edition; 2004.
8
Trang
Cấu trúc dữ liệu
Chương I:Mở đầu
CHƯƠNG I
MỞ ĐẦU
TỔNG QUAN
1. Mục tiêu
Sau khi học xong chương này, sinh viên sẽ:
Nắm được các bước trong lập trình để giải quyết cho một bài toán.
Nắm vững khái niệm kiểu dữ liệu trừu tượng, sự khác nhau giữa kiểu dữ liệu, kiểu dữ
liệu trừu tượng và cấu trúc dữ liệu.
2. Kiến thức cơ bản cần thiết
Các kiến thức cơ bản cần thiết để học chương này bao gồm:
Khả năng nhận biết và giải quyết bài toán theo hướng tin học hóa.
3. Tài liệu tham khảo
Aho, A. V. , J. E. Hopcroft, J. D. Ullman. "Data Structure and Algorihtms", Addison–
Wesley; 1983 (chapter 1)
Đỗ 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. (Chương 1)
4. Nội dung cốt lõi
Chương này chúng ta sẽ nghiên cứu các vấn đề sau:
- Cách tiếp cận từ bài toán đến chương trình
- Kiểu dữ liệu trừu tượng (Abstract Data Type).
- Kiểu dữ liệu – Kiểu dữ liệu trừu tượng – Cấu trúc dữ liệ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ế
Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bài toán.
Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phải trả lời rõ
ràng câu hỏi "phải làm gì?" sau đó là "làm như thế nào?". Thông thường, khi khởi đầu, hầu
9
Cấu trúc dữ liệu
Chương I: Mở đầu
hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức tạp của bài toán
thực tế, ta phải hình thức hóa nó, nghĩa là phát biểu lại bài toán thực tế thành một bài toán
hình thức (hay còn gọi là mô hình toán). Có thể có rất nhiều bài toán thực tế có cùng một
mô hình toán.
Ví dụ 1: Tô màu bản đồ thế giới.
Ta cần phải tô màu cho các nước trên bản đồ thế giới. Trong đó mỗi nước đều được tô
một màu và hai nước láng giềng (cùng biên giới) thì phải được tô bằng hai màu khác nhau.
Hãy tìm một phương án tô màu sao cho số màu sử dụng là ít nhất.
Ta có thể xem mỗi nước trên bản đồ thế giới là một đỉnh của đồ thị, hai nước láng giềng
của nhau thì hai đỉnh ứng với nó được nối với nhau bằng một cạnh. Bài toán lúc này trở
thành bài toán tô màu cho đồ thị như sau: Mỗi đỉnh đều phải được tô màu, hai đỉnh có cạnh
nối thì phải tô bằng hai màu khác nhau và ta cần tìm một phương án tô màu sao cho số màu
được sử dụng là ít nhất.
Ví dụ 2: Đèn giao thông
Cho một ngã năm như hình I.1, trong đó C và E là các đường một chiều theo chiều mũi
tên, các đường khác là hai chiều. Hãy thiết kế một bảng đèn hiệu điều khiển giao thông tại
ngã năm này một cách hợp lý, nghĩa là: phân chia các lối đi tại ngã năm này thành các
nhóm, mỗi nhóm gồm các lối đi có thể cùng đi đồng thời nhưng không xảy ra tai nạn giao
thông (các hướng đi không cắt nhau), và số lượng nhóm là ít nhất có thể được.
Ta có thể xem đầu vào (input) của bài toán là tất cả các lối đi tại ngã năm này, đầu ra
(output) của bài toán là các nhóm lối đi có thể đi đồng thời mà không xảy ra tai nạn giao
thông, mỗi nhóm sẽ tương ứng với một pha điều khiển của đèn hiệu, vì vậy ta phải tìm kiếm
lời giải với số nhóm là ít nhất để giao thông không bị tắc nghẽn vì phải chờ đợi quá lâu.
Trước hết ta nhận thấy rằng tại ngã năm này có 13 lối đi: AB, AC, AD, BA, BC, BD,
DA, DB, DC, EA, EB, EC, ED. Tất nhiên, để có thể giải được bài toán ta phải tìm một cách
10
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
nào đó để thể hiện mối liên quan giữa các lối đi này. Lối nào với lối nào không thể đi đồng
thời, lối nào và lối nào có thể đi đồng thời. Ví dụ cặp AB và EC có thể đi đồng thời, nhưng
AD và EB thì không, vì các hướng giao thông cắt nhau. Ở đây ta sẽ dùng một sơ đồ trực
quan như sau: tên của 13 lối đi được viết lên mặt phẳng, hai lối đi nào nếu đi đồng thời sẽ
xảy ra đụng nhau (tức là hai hướng đi cắt qua nhau) ta nối lại bằng một đoạn thẳng, hoặc
cong, hoặc ngoằn ngoèo tuỳ thích. Ta sẽ có một sơ đồ như hình I.2. Như vậy, trên sơ đồ này,
hai lối đi có cạnh nối lại với nhau là hai lối đi không thể cho đi đồng thời.
Với cách biểu diễn như vậy ta đã có một đồ thị (Graph), tức là ta đã mô hình hoá bài toán
giao thông ở trên theo mô hình toán là đồ thị; trong đó mỗi lối đi trở thành một đỉnh của đồ
thị, hai lối đi không thể cùng đi đồng thời được nối nhau bằng một đoạn ta gọi là cạnh của
đồ thị. Bây giờ ta phải xác định các nhóm, với số nhóm ít nhất, mỗi nhóm gồm các lối đi có
thể đi đồng thời, nó ứng với một pha của đèn hiệu điều khiển giao thông. Giả sử rằng, ta
dùng màu để tô lên các đỉnh của đồ thị này sao cho:
¾ Các lối đi cho phép cùng đi đồng thời sẽ có cùng một màu: Dễ dàng nhận thấy rằng
hai đỉnh có cạnh nối nhau sẽ không được tô cùng màu.
¾ Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là ít nhất.
Tóm lại, ta phải giải quyết bài toán sau:
"Tô màu cho đồ thị ở hình I.2 sao cho:
¾ Hai đỉnh có cạnh nối với nhau (hai còn gọi là hai đỉnh kề nhau) không cùng màu.
¾ Số màu được dùng là ít nhất."
11
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
Hai bài toán thực tế “tô màu bản đồ thế giới” và “đèn giao thông” xem ra rất khác biệt
nhau nhưng sau khi mô hình hóa, chúng thực chất chỉ là một, đó là bài toán “tô màu đồ thị”.
Đối với một bài toán đã được hình thức hoá, chúng ta có thể tìm kiếm cách giải trong
thuật ngữ của mô hình đó và xác định có hay không một chương trình có sẵn để giải. Nếu
không có một chương trình như vậy thì ít nhất chúng ta cũng có thể tìm được những gì đã
biết về mô hình và dùng các tính chất của mô hình để xây dựng một giải thuật tốt.
2. Giải thuật (algorithms)
Khi đã có mô hình thích hợp cho một bài toán ta cần cố gắng tìm cách giải quyết bài toán
trong mô hình đó. Khởi đầu là tìm một giải thuật, đó là một chuỗi hữu hạn các chỉ thị
(instruction) mà mỗi chỉ thị có một ý nghĩa rõ ràng và thực hiện được trong một lượng thời
gian hữu hạn.
Knuth (1973) định nghĩa giải thuật là một chuỗi hữu hạn các thao tác để giải một bài toán
nào đó. Các tính chất quan trọng của giải thuật là:
¾ Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước.
¾ Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải
được thực hiện chính xác, nhất quán.
¾ Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một
lượng thời gian hữu hạn.
Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output).
Nói tóm lại, một giải thuật phải giải quyết xong công việc khi ta cho dữ liệu vào. Có
nhiều cách để thể hiện giải thuật: dùng lời, dùng lưu đồ, ... Và một lối dùng rất phổ biến là
dùng ngôn ngữ giả, đó là sự kết hợp của ngôn ngữ tự nhiên và các cấu trúc của ngôn ngữ lập
trình.
Ví dụ: Thiết kế giải thuật để giải bài toán “ tô màu đồ thị” trên
Bài toán tô màu cho đồ thị không có giải thuật tốt để tìm lời giải tối ưu, tức là, không có
giải thuật nào khác hơn là "thử tất cả các khả năng" hay "vét cạn" tất cả các trường hợp có
thể có, để xác định cách tô màu cho các đỉnh của đồ thị sao cho số màu dùng là ít nhất.
Thực tế, ta chỉ có thể "vét cạn" trong trường hợp đồ thị có số đỉnh nhỏ, trong trường hợp
ngược lại ta không thể "vét cạn" tất cả các khả năng trong một lượng thời gian hợp lý, do
vậy ta phải suy nghĩ cách khác để giải quyết vấn đề:
Thêm thông tin vào bài toán để đồ thị có một số tính chất đặc biệt và dùng các tính
chất đặc biệt này ta có thể dễ dàng tìm lời giải, hoặc
Thay đổi yêu cầu bài toán một ít cho dễ giải quyết, nhưng lời giải tìm được chưa chắc
là lời giải tối ưu. Một cách làm như thế đối với bài toán trên là "Cố gắng tô màu cho đồ thị
12
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
bằng ít màu nhất một cách nhanh chóng". Ít màu nhất ở đây có nghĩa là số màu mà ta tìm
được không phải luôn luôn là số màu của lời giải tối ưu (ít nhất) nhưng trong đa số trường
hợp thì nó sẽ trùng với đáp số của lời giải tối ưu và nếu có chênh lệch thì nó "không chênh
lệch nhiều" so với lời giải tối ưu, bù lại ta không phải "vét cạn" mọi khả năng có thể! Nói
khác đi, ta không dùng giải thuật "vét cạn" mọi khả năng để tìm lời giải tối ưu mà tìm một
giải pháp để đưa ra lời giải hợp lý một cách khả thi về thời gian. Một giải pháp như thế gọi
là một HEURISTIC.
HEURISTIC cho bài toán tô màu đồ thị, thường gọi là giải thuật "háu ăn" (GREEDY) là:
¾ Chọn một đỉnh chưa tô màu và tô nó bằng một màu mới C nào đó.
¾ Duyệt danh sách các đỉnh chưa tô màu. Đối với một đỉnh chưa tô màu, xác định xem
nó có kề với một đỉnh nào được tô bằng màu C đó không. Nếu không có, tô nó bằng màu C
đó.
Ý tưởng của Heuristic này là hết sức đơn giản: dùng một màu để tô cho nhiều đỉnh nhất
có thể được (các đỉnh được xét theo một thứ tự nào đó), khi không thể tô được nữa với màu
đang dùng thì dùng một màu khác. Như vậy ta có thể "hi vọng" là số màu cần dùng sẽ ít
nhất.
Ví dụ: Đồ thị hình I.3 và cách tô màu cho nó
Tô theo GREEDY
Tối ưu
(xét lần lượt theo số thứ tự các
(thử tất cả các khả năng)
đỉnh)
1: đỏ; 2: đỏ
3: xanh;4: xanh
5: vàng
1,3,4 : đỏ
2,5 : xanh
13
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
Rõ ràng cách tô màu trong giải thuật "háu ăn" không luôn luôn cho lời giải tối ưu nhưng
nó được thực hiện một cách nhanh chóng.
Trở lại bài toán giao thông ở trên và áp dụng HEURISTIC Greedy cho đồ thị trong hình
I.2 (theo thứ tự các đỉnh đã liệt kê ở trên), ta có kết quả:
Tô màu xanh cho các đỉnh: AB,AC,AD,BA,DC,ED
Tô màu đỏ cho các đỉnh: BC,BD,EA
Tô màu tím cho các đỉnh: DA,DB
Tô màu vàng cho các đỉnh: EB,EC
Như vậy ta đã tìm ra một lời giải là dùng 4 màu để tô cho đồ thị hình I.2. Như đã nói, lời
giải này không chắc là lời giải tối ưu. Vậy liệu có thể dùng 3 màu hoặc ít hơn 3 màu không?
Ta có thể trở lại mô hình của bài toán và dùng tính chất của đồ thị để kiểm tra kết quả. Nhận
xét rằng:
Một đồ thị có k đỉnh và mỗi cặp đỉnh bất kỳ đều được nối nhau thì phải dùng k màu để tô.
Hình I.4 chỉ ra hai ví dụ với k=3 và k=4.
Hình I.4
¾ Một đồ thị trong đó có k đỉnh mà mỗi cặp đỉnh bất kỳ trong k đỉnh này đều được nối
nhau thì không thể dùng ít hơn k màu để tô cho đồ thị.
Đồ thị trong hình I.2 có 4 đỉnh: AC,DA,BD,EB mà mỗi cặp đỉnh bất kỳ đều được nối
nhau vậy đồ thị hình I.2 không thể tô với ít hơn 4 màu. Điều này khẳng định rằng lời giải
vừa tìm được ở trên trùng với lời giải tối ưu.
Như vậy ta đã giải được bài toán giao thông đã cho. Lời giải cho bài toán là 4 nhóm, mỗi
nhóm gồm các lối có thể đi đồng thời, nó ứng với một pha điều khiển của đèn hiệu. Ở đây
cần nhấn mạnh rằng, sở dĩ ta có lời giải một cách rõ ràng chặt chẽ như vậy là vì chúng ta đã
giải bài toán thực tế này bằng cách mô hình hoá nó theo một mô hình thích hợp (mô hình đồ
thị) và nhờ các kiến thức trên mô hình này (bài toán tô màu và heuristic để giải) ta đã giải
quyết được bài toán. Điều này khẳng định vai trò của việc mô hình hoá bài toán.
14
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
3. Ngôn ngữ giả và tinh chế từng bước (Pseudo-language and stepwise refinement)
Một khi đã có mô hình thích hợp cho bài toán, ta cần hình thức hoá một giải thuật trong
thuật ngữ của mô hình đó. Khởi đầu là viết những mệnh đề tổng quát rồi tinh chế dần thành
những chuỗi mệnh đề cụ thể hơn, cuối cùng là các chỉ thị thích hợp trong một ngôn ngữ lập
trình. Chẳng hạn với heuristic GREEDY, giả sử đồ thị là G, heuristic sẽ xác định một tập
hợp Newclr các đỉnh của G được tô cùng một màu, mà ta gọi là màu mới C ở trên. Để tiến
hành tô màu hoàn tất cho đồ thị G thì Heuristic này phải được gọi lặp lại cho đến khi toàn
thể các đỉnh đều được tô màu.
void GREEDY ( GRAPH *G, SET *Newclr )
{
/*1*/ Newclr = ∅;
/*2*/ for (mỗi đỉnh v chưa tô màu của G)
/*3*/
if (v không được nối với một đỉnh nào trong Newclr)
{
/*4*/
/*5*/
đánh dấu v đã được tô màu;
thêm v vào Newclr;
}
}
Trong thủ tục bằng ngôn ngữ giả này chúng ta đã dùng một số từ khoá của ngôn ngữ C
xen lẫn các mệnh đề tiếng Việt. Điều đặc biệt nữa là ta dùng các kiểu GRAPH, SET có vẻ
xa lạ, chúng là các "kiểu dữ liệu trừu tượng" mà sau này chúng ta sẽ viết bằng các khai báo
thích hợp trong ngôn ngữ lập trình cụ thể. Dĩ nhiên, để cài đặt thủ tục này ta phải cụ thể hoá
dần những mệnh đề bằng tiếng Việt ở trên cho đến khi mỗi mệnh đề tương ứng với một
đoạn mã thích hợp của ngôn ngữ lập trình. Chẳng hạn mệnh đề if ở /*3*/ có thể chi tiết hoá
hơn nữa như sau:
void GREEDY ( GRAPH *G, SET *Newclr )
{
/*1*/ Newclr= ∅;
/*2*/ for (mỗi đỉnh v chưa tô màu của G)
{
/*3.1*/
int found=0;
15
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
/*3.2*/
/*3.3*/
/*3.4*/
/*3.5*/
for (mỗi đỉnh w trong Newclr)
if (có cạnh nối giữa v và w)
found=1;
if found==0
{
/*4*/
/*5*/
đánh dấu v đã được tô màu;
thêm v vào Newclr;
}
}
}
Hình I.5: Biểu diễn tập hợp các đỉnh như là một danh sách (LIST)
GRAPH và SET ta coi như tập hợp. Có nhiều cách để biểu diễn tập hợp trong ngôn ngữ
lập trình, để đơn giản ta xem các tập hợp như là một danh sách (LIST) các số nguyên biểu
diễn chỉ số của các đỉnh và kết thúc bằng một giá trị đặc biệt NULL (hình I.5). Với những
qui ước như vậy ta có thể tinh chế giải thuật GREEDY một bước nữa như sau:
void GREEDY ( GRAPH *G, LIST *Newclr )
{
int found;
int v,w ;
Newclr= ∅;
v= đỉnh đầu tiên chưa được tô màu trong G;
while (v<>null) {
found=0;
w=đỉnh đầu tiên trong newclr;
while( w<>null) && (found=0) {
16
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
if có cạnh nối giữa v và w
found=1;
else w= đỉnh kế tiếp trong newclr;
}
if found==0 {
Đánh dấu v đã được tô màu;
Thêm v vào Newclr;
}
v= đỉnh chưa tô màu kế tiếp trong G;
}
}
4. Tóm tắt
Từ những thảo luận trên chúng ta có thể tóm tắt các bước tiếp cận với một bài toán bao
gồm:
1. Mô hình hoá bài toán bằng một mô hình toán học thích hợp.
2. Tìm giải thuật trên mô hình này. Giải thuật có thể mô tả một cách không hình
thức, tức là nó chỉ nêu phương hướng giải hoặc các bước giải một cách tổng quát.
3. Phải hình thức hoá giải thuật bằng cách viết một thủ tục bằng ngôn ngữ giả, rồi
chi tiết hoá dần ("mịn hoá") các bước giải tổng quát ở trên, kết hợp với việc dùng
các kiểu dữ liệu trừu tượng và các cấu trúc điều khiển trong ngôn ngữ lập trình để
mô tả giải thuật. Ở bước này, nói chung, ta có một giải thuật tương đối rõ ràng, nó
gần giống như một chương trình được viết trong ngôn ngữ lập trình, nhưng nó
không phải là một chương trình chạy được vì trong khi viết giải thuật ta không
chú trọng nặng đến cú pháp của ngôn ngữ và các kiểu dữ liệu còn ở mức trừu
tượng chứ không phải là các khai báo cài đặt kiểu trong ngôn ngữ lập trình.
4. Cài đặt giải thuật trong một ngôn ngữ lập trình cụ thể (Pascal,C,...). Ở bước này ta
dùng các cấu trúc dữ liệu được cung cấp trong ngôn ngữ, ví dụ Array, Record,...
để thể hiện các kiểu dữ liệu trừu tượng, các bước của giải thuật được thể hiện
bằng các lệnh và các cấu trúc điều khiển trong ngôn ngữ lập trình được dùng để
cài đặt giải thuật.
Tóm tắt các bước như sau:
17
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
Mô hình toán học
Kiểu dữ liệu trừu tượng
Cấu trúc dữ liệu
Giải thuật không hình thức Chương trình ngôn ngữ giả
Chương trình Pascal,
C,...
II. KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE -ADT)
1. Khái niệm trừu tượng hóa
Trong tin học, trừu tượng hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn và dễ hiểu
hơn. Cụ thể trừu tượng hóa là che đi những chi tiết, làm nổi bật cái tổng thể. Trừu tượng hóa
có thể thực hiện trên hai khía cạnh là trừu tượng hóa dữ liệu và trừu tượng hóa chương trình.
2. Trừu tượng hóa chương trình
Trừu tượng hóa chương trình là sự định nghĩa các chương trình con để tạo ra các phép
toán trừu tượng (sự tổng quát hóa của các phép toán nguyên thủy). Chẳng hạn ta có thể tạo
ra một chương trình con Matrix_Mult để thực hiện phép toán nhân hai ma trận. Sau khi
Matrix_mult đã được tạo ra, ta có thể dùng nó như một phép toán nguyên thủy (chẳng hạn
phép cộng hai số).
Trừu tượng hóa chương trình cho phép phân chia chương trình thành các chương trình
con. Sự phân chia này sẽ che dấu tất cả các lệnh cài đặt chi tiết trong các chương trình con.
Ở cấp độ chương trình chính, ta chỉ thấy lời gọi các chương trình con và điều này được gọi
là sự bao gói.
Ví dụ như một chương trình quản lý sinh viên được viết bằng trừu tượng hóa có thể là:
void Main() {
Nhap( Lop);
Xu_ly (Lop);
Xuat (Lop);
}
Trong chương trình trên, Nhap, Xu_ly, Xuat là các phép toán trừu tượng. Chúng che dấu
bên trong rất nhiều lệnh phức tạp mà ở cấp độ chương trình chính ta không nhìn thấy được.
Còn Lop là một biến thuộc kiểu dữ liệu trừu tượng mà ta sẽ xét sau.
V
Chương trình được viết theo cách gọi các phép toán trừu tượng có lệ thuộc vào
cách cài đặt kiểu dữ liệu không?
18
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
3. Trừu tượng hóa dữ liệu
Trừu tượng hóa dữ liệu là định nghĩa các kiểu dữ liệu trừu tượng
Một kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán
(operator) trừu tượng được định nghĩa trên mô hình đó. Ví dụ tập hợp số nguyên cùng với
các phép toán hợp, giao, hiệu là một kiểu dữ liệu trừu tượng.
Trong một ADT các phép toán có thể thực hiện trên các đối tượng (toán hạng) không chỉ
thuộc ADT đó, cũng như kết quả không nhất thiết phải thuộc ADT. Tuy nhiên phải có ít
nhất một toán hạng hoặc kết quả phải thuộc ADT đang xét.
ADT là sự tổng quát hoá của các kiểu dữ liệu nguyên thuỷ.
Để minh hoạ ta có thể xét bản phác thảo cuối cùng của thủ tục GREEDY. Ta đã dùng một
danh sách (LIST) các số nguyên và các phép toán trên danh sách newclr là:
¾ Tạo một danh sách rỗng.
¾ Lấy phần tử đầu tiên trong danh sách và trả về giá trị null nếu danh sách rỗng.
¾ Lấy phần tử kế tiếp trong danh sách và trả về giá trị null nếu không còn phần tử kế
tiếp.
¾ Thêm một số nguyên vào danh sách.
Nếu chúng ta viết các chương trình con thực hiện các phép toán này, thì ta dễ dàng thay
các mệnh đề hình thức trong giải thuật bằng các câu lệnh đơn giản
Câu lệnh
Mệnh đề hình thức
MAKENULL(newclr)
w=FIRST(newclr)
newclr= ∅
w=phần tử đầu tiên trong newclr
w=phần tử kế tiếp trong newclr
Thêm v vào newclr
w=NEXT(w,newclr)
INSERT( v,newclr)
Điều này cho thấy sự thuận lợi của ADT, đó là ta có thể định nghĩa một kiểu dữ liệu tuỳ ý
cùng với các phép toán cần thiết trên nó rồi chúng ta dùng như là các đối tượng nguyên
thuỷ. Hơn nữa chúng ta có thể cài đặt một ADT bằng bất kỳ cách nào, chương trình dùng
chúng cũng không thay đổi, chỉ có các chương trình con biểu diễn cho các phép toán của
ADT là thay đổi.
19
Trang
Cấu trúc dữ liệu
Chương I: Mở đầu
Cài đặt ADT là sự thể hiện các phép toán mong muốn (các phép toán trừu tượng) thành
các câu lệnh của ngôn ngữ lập trình, bao gồm các khai báo thích hợp và các thủ tục thực
hiện các phép toán trừu tượng. Để cài đặt ta chọn một cấu trúc dữ liệu thích hợp có trong
ngôn ngữ lập trình hoặc là một cấu trúc dữ liệu phức hợp được xây dựng lên từ các kiểu dữ
liệu cơ bản của ngôn ngữ lập trình.
V
Sự khác nhau giữa kiểu dữ liệu và kiểu dữ liệu trừu tượng là gì?
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)
Mặc dù các thuật ngữ kiểu dữ liệu (hay kiểu - data type), cấu trúc dữ liệu (data structure),
kiểu dữ liệu trừu tượng (abstract data type) nghe như nhau, nhưng chúng có ý nghĩa rất khác
nhau.
Kiểu dữ liệu là một tập hợp các giá trị và một tập hợp các phép toán trên các giá trị đó. Ví
dụ kiểu Boolean là một tập hợp có 2 giá trị TRUE, FALSE và các phép toán trên nó như
OR, AND, NOT …. Kiểu Integer là tập hợp các số nguyên có giá trị từ -32768 đến 32767
cùng các phép toán cộng, trừ, nhân, chia, Div, Mod…
Kiểu dữ liệu có hai loại là kiểu dữ liệu sơ cấp và kiểu dữ liệu có cấu trúc hay còn gọi là
cấu trúc dữ liệu.
Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị dữ liệu của nó là đơn nhất. Ví dụ: kiểu
Boolean, Integer….
Kiểu dữ liệu có cấu trúc hay còn gọi là cấu trúc dữ liệu là kiểu dữ liệu mà giá trị dữ liệu
của nó là sự kết hợp của các giá trị khác. Ví dụ: ARRAY là một cấu trúc dữ liệu.
Một kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán
trên nó. Có thể nói kiểu dữ liệu trừu tượng là một kiểu dữ liệu do chúng ta định nghĩa ở mức
khái niệm (conceptual), nó chưa được cài đặt cụ thể bằng một ngôn ngữ lập trình.
Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn gnữ lập trình cụ thể, chúng ta phải
thực hiện hai nhiệm vụ:
1. Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc dữ liệu hoặc một kiểu dữ liệu trừu
tượng khác đã được cài đặt.
2. Viết các chương trình con thực hiện các phép toán trên kiểu dữ liệu trừu tượng mà ta
thường gọi là cài đặt các phép toán.
20
Trang
Tải về để xem bản đầy đủ
151 trang
32622
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu - Đại học Cần Thơ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_dai_hoc_can_tho.pdf
