Tổng quan về cấu trúc dữ liệu và giải thuật
TRƯỜNG ĐẠI HỌC ĐÀ LẠT
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN THỊ THANH BÌNH
BÀI GIẢNG TÓM TẮT
CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI 2
Dành cho sinh viên ngành công nghệ thông tin
(Lưu hành nội bộ)
Đà Lạt 2008
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
công nghệ thông tin, Khoa Công Nghệ Thông Tin Trường Đại Học Đà Lạt 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
Tài liệu này được soạn theo đề cương chi tiết môn Cấu Trúc Dữ Liệu Và Thuật Giải 2
của Khoa Công Nghệ Thông Tin Trường Đại Học Đà Lạt. 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.
Mặc dù đã rất cố gắng nhiều trong quá trình biên soạn giáo trình, song không khỏi 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.
Đà Lạt, ngày 30 tháng 06 năm 2008
1
Mục lục
Chương I: Cây ............................................................................................................................... 4
I. Các thuật ngữ cơ bản trên cây ................................................................................................ 4
1. Định nghĩa ......................................................................................................................... 4
2. Thứ tự các nút trong cây.................................................................................................... 5
3. Các thứ tự duyệt cây quan trọng........................................................................................ 6
4. Cây có nhãn và cây biểu thức............................................................................................ 6
II. Cây nhị phân (Binary Trees)................................................................................................... 8
1. Định nghĩa ......................................................................................................................... 8
2. Vài tính chất của cây nhị phân........................................................................................... 9
3. Biểu diễn cây nhị phân ...................................................................................................... 9
4. Duyệt cây nhị phân............................................................................................................ 9
5. Cài đặt cây nhị phân ........................................................................................................ 10
IV. Cây tìm kiếm nhị phân (Binary Search Trees).................................................................... 12
1. Định nghĩa ........................................................................................................................ 12
2. Cài đặt cây tìm kiếm nhị phân.......................................................................................... 13
V. Cây nhị phân tìm kiếm cân bằng (Cây AVL)....................................................................... 21
1. Cây nhị phân cân bằng hoàn toàn..................................................................................... 21
2. Xây dựng cây nhị phân cân bằng hoàn toàn..................................................................... 21
3. Cây tìm kiếm nhị phân cân bằng (cây AVL).................................................................... 22
Bài tập........................................................................................................................................ 32
Chương II: Đồ Thị....................................................................................................................... 35
I. Các định nghĩa................................................................................................................... 35
III. Biểu diễn đồ thị.................................................................................................................... 36
1. Biểu diễn đồ thị bằng ma trận kề...................................................................................... 37
2. Biểu diễn đồ thị bằng danh sách các đỉnh kề.................................................................... 38
IV. Các phép duyệt đồ thị (traversals of Graph)........................................................................ 38
1. Duyệt theo chiều sâu (Depth-first search) ........................................................................ 38
2. Duyệt theo chiều rộng (breadth-first search).................................................................... 40
V. Một số bài toán trên đồ thị................................................................................................... 43
1. Bài toán tìm đường đi ngắn nhất từ một đỉnh của đồ thị.................................................. 43
2. Bài toán tìm bao đóng chuyển tiếp. .................................................................................. 47
3. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree)................................. 48
Bài tập........................................................................................................................................ 53
Chương III: Bảng Băm ............................................................................................................... 55
I. Phương pháp băm................................................................................................................. 55
II. Các hàm băm ..................................................................................................................... 57
1. Phương pháp chia ............................................................................................................. 57
2. Phương pháp nhân ............................................................................................................ 57
3. Hàm băm cho các giá trị khoá là xâu ký tự...................................................................... 58
III. Các phương pháp giải quyết va chạm.................................................................................. 59
1. Phương pháp định địa chỉ mở........................................................................................... 59
2. Phương pháp tạo dây chuyền............................................................................................ 62
IV. Cài đặt bảng băm địa chỉ mở............................................................................................... 63
V. Cài đặt bảng băm dây chuyền.............................................................................................. 66
VI. Hiệu quả của các phương pháp băm.................................................................................... 69
2
Bài tập........................................................................................................................................ 71
Chương IV: Một số phương pháp thiết kế thuật giải............................................................... 73
I. Phương pháp chia để trị........................................................................................................ 73
1. Mở đầu.............................................................................................................................. 73
2. Tìm kiếm nhị phân............................................................................................................ 74
3. Bài toán Min-Max ............................................................................................................ 75
4. Thuật toán QuickSort........................................................................................................ 76
II. Phương pháp quay lui ........................................................................................................... 79
1. Mở đầu.............................................................................................................................. 79
2. Bài toán liệt kê dãy nhị phân độ dài n .............................................................................. 80
3. Bài toán liệt kê các hoán vị............................................................................................... 80
4. Bài toán duyệt đồ thị theo chiều sâu (DFS)...................................................................... 81
III. Phương pháp tham lam........................................................................................................ 83
1. Mở đầu.............................................................................................................................. 83
2. Bài toán người du lịch ...................................................................................................... 84
3. Thuật toán Prim - Tìm cây bao trùm nhỏ nhất ................................................................. 86
4. Bài toán chiếc túi sách...................................................................................................... 86
Bài tập........................................................................................................................................ 87
Tài liệu tham khảo....................................................................................................................... 89
3
Chương I
Cây
Mục tiêu
Sau khi học xong chương này, sinh viên phải:
- Nắm vững khái niệm về cây (trees).
- Cài đặt được cây và thực hiện các phép toán trên cây.
Kiến thức cơ bản cần thiết
Để học tốt chương này, sinh viên phải nắm vững kỹ năng lập trình căn bản như:
- Kiểu con trỏ (pointer)
- Các cấu trúc điều khiển, lệnh vòng lặp.
- Lập trình theo từng module (chương trình con) và cách gọi chương trình con
đó.
- Lập trình đệ qui và gọi đệ qui.
- Kiểu dữ liệu trừu tượng danh sách
Nội dung
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau:
- Các thuật ngữ cơ bản.
- Kiểu dữ liệu trừu tượng Cây
- Cây nhị phân
- Cây tìm kiếm nhị phân
- Cây nhị phân tìm kiếm cân bằng AVL
I. Các thuật ngữ cơ bản trên cây
Cây là một tập hợp các phần tử gọi là nút (nodes) trong đó có một nút được phân biệt
gọi là nút gốc (root). Trên tập hợp các nút này có một quan hệ, gọi là mối quan hệ cha
- con (parenthood), để xác định hệ thống cấu trúc trên các nút. Mỗi nút, trừ nút gốc, có
duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào.
Mỗi nút biểu diễn một phần tử trong tập hợp đang xét và nó có thể có một kiểu nào đó
bất kỳ, thường ta biểu diễn nút bằng một kí tự, một chuỗi hoặc một số ghi trong vòng
tròn. Mối quan hệ cha con được biểu diễn theo qui ước nút cha ở dòng trên nút con ở
dòng dưới và được nối bởi một đoạn thẳng. Một cách hình thức ta có thể định nghĩa
cây một cách đệ qui như sau:
1. Định nghĩa
- Một nút đơn độc là một cây. Nút này cũng chính là nút gốc của cây.
- Giả sử ta có n là một nút đơn độc và k cây T1,.., Tk với các nút gốc tương ứng là
n1,.., nk thì có thể xây dựng một cây mới bằng cách cho nút n là cha của các nút
4
n1,.., nk. Cây mới này có nút gốc là nút n và các cây T1,.., Tk được gọi là các cây
con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu.
Ví dụ: xét mục lục của một quyển sách. Mục lục này có thể xem là một cây
Hình I.1: Cây mục lục sách
Nút gốc là sách, nó có ba cây con có gốc là C1, C2, C3. Cây con thứ 3 có gốc C3 là
một nút đơn độc trong khi đó hai cây con kia (gốc C1 và C2) có các nút con.
Nếu n1,.., nk là một chuỗi các nút trên cây sao cho ni là nút cha của nút ni+1, với i=1..k-
1, thì chuỗi này gọi là một đường đi trên cây (hay ngắn gọn là đường đi) từ n1 đến nk.
Độ dài đường đi được định nghĩa bằng số nút trên đường đi trừ 1. Như vậy độ dài
đường đi từ một nút đến chính nó bằng không.
Nếu có đường đi từ nút a đến nút b thì ta nói a là tiền bối (ancestor) của b, còn b gọi là
hậu duệ (descendant) của nút a. Rõ ràng một nút vừa là tiền bối vừa là hậu duệ của
chính nó. Tiền bối hoặc hậu duệ của một nút khác với chính nó gọi là tiền bối hoặc
hậu duệ thực sự. Trên cây nút gốc không có tiền bối thực sự. Một nút không có hậu
duệ thực sự gọi là nút lá (leaf). Nút không phải là lá ta còn gọi là nút trung gian
(interior). Cây con của một cây là một nút cùng với tất cả các hậu duệ của nó.
Chiều cao của một nút là độ dài đường đi lớn nhất từ nút đó tới lá. Chiều cao của cây
là chiều cao của nút gốc. Độ sâu của một nút là độ dài đường đi từ nút gốc đến nút đó.
Các nút có cùng một độ sâu i ta gọi là các nút có cùng một mức i. Theo định nghĩa này
thì nút gốc ở mức 0, các nút con của nút gốc ở mức 1.
Ví dụ: đối với cây trong hình I.1 ta có nút C2 có chiều cao 2. Cây có chiều cao 3. nút
C3 có chiều cao 0. Nút 2.1 có độ sâu 2. Các nút C1,C2,C3 cùng mức 1.
2. Thứ tự các nút trong cây
Nếu ta phân biệt thứ tự các nút con của cùng một nút thì cây gọi là cây có thứ tự, thứ
tự qui ước từ trái sang phải. Như vậy, nếu kể thứ tự thì hai cây sau là hai cây khác
nhau:
Hình I.2: Cây có thứ tự khác nhau
5
có thể bạn quan tâm
Cấu trúc dữ liệu và giải các thuật toán
229
755
274
Cơ sở dữ liệu
229
(New)
Bài giảng cấu trúc dữ liệu và giải thuật
98
572
1.222
Cơ sở dữ liệu
98
(New)
Luận văn: Nhà máy Z153 (Tổng cục Kĩ thuật) - Quy trình quản lý sử dụng...
88
620
293
Kinh tế quản lý
88
(New)
Tiểu luận: Khái niệm về Matlab,tổng quan về cấu trúc dữ liệu Matlab, c...
138
1.776
303
Kỹ thuật
138
(New)
Luận văn: Nhà máy Z153 – Tổng cục Kĩ thuật và nội dung công tác quản t...
88
779
328
Kinh tế quản lý
88
(New)
TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU CHẾ SỐ, TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU...
66
851
440
Kỹ thuật
66
(New)
Luận văn thạc sỹ kỹ thuật điện: Tổng quan về kỹ thuật WiMAX và giải ph...
93
773
364
Thạc sĩ cao học
93
(New)
Tóm tắt luận án thạc sĩ: Tổng quan các phương pháp khai thác dữ liệu,...
19
948
381
Thạc sĩ cao học
19
(New)
thông tin tài liệu
Tài liệu cung cấp những kiến thức chung về cấu trúc dữ liệu và cách giải thuật
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Giáo trình Quản trị học của Đại học kinh tế quốc dân
Tâm lý xã hội VÀ Hệ tư tưởng
Mẫu slide chủ đề âm nhạc
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
Các hiệu ứng HTML cho trang web
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
