Tài liệu môn học cấu trúc dữ liệu và giải thuật (Full 7 chương)

Trong ngôn ngữ lập trình, dữ liệu bao gồm hai kiểu chính là :

- Kiểu dữ liệu đơn giản : char, int, long, float, enumeration, subrange.

- Kiểu dữ liệu có cấu trúc : struct, array, file (kiểu dữ liệu có kích thước không đổi)...

Giáo trình này tập trung vào việc nghiên cứu các kiểu dữ liệu có cấu trúc có kích thước không đổi hoặc thay đổi trong ngôn ngữ lập trình, mô tả thông qua ngôn ngữ C. Ngoài ra còn giới thiệu các giải thuật chung quanh các cấu trúc dữ liệu này như cách tổ chức, thực hiện các phép toán tìm kiếm, sắp thứ tự nội, sắp thứ tự ngoại...

Điều kiện để có thể tìm hiểu rõ ràng về môn học này là học viên đã biết các khái niệm về kỹ thuật lập trình trên ngôn ngữ C. Trong phần mở đầu, bài giảngnày sẽ giới thiệu cách thức phân tích & thiết kế một giải thuật trước khi tìm hiểu về các cấu trúc dữ liệu cụ thể.

NỘI DUNG:

GIỚI THIỆU MÔN HỌC :................................................................................................................................................................. 3

CHƯƠNG I : PHÂN TÍCH & ĐÁNH GIÁ GIẢI THUẬT :

I. MỞ ĐẦU :...................................................................................................................................................... 4

II. ĐÁNH GIÁ THỜI GIAN CHẠY CỦA CHƯƠNG TRÌNH :................................4

III. KÝ HIỆU O(n) VÀ (n) :.................................................................................................................. 4

IV. CÁCH TÍNH THỜI GIAN CHẠY CHƯƠNG TRÌNH :...........................................5

Qui tắc tính thời gian chạy :............................................................................................................... 5

V. SỰ PHÂN LỚP CÁC THUẬT TOÁN :..................................................................................6

CHƯƠNG II : ĐỆ QUI

I. KHÁI NIỆM :............................................................................................................................................. 9

II. HÀM ĐỆ QUI VÀ STACK :......................................................................................................... 10

III. VÍ DỤ :........................................................................................................................................................... 11

IV. THUẬT TOÁN LẦN NGƯỢC :............................................................................................... 13

BÀI TẬP :................................................................................................................................................................ 26

CHƯƠNG III : DANH SÁCH TUYẾN TÍNH

KHÁI NIỆM :.......................................................................................................................................... 27

I. ĐỊNH NGHĨA :........................................................................................................................................ 27

II. CÁC PHÉP TOÁN TRÊN DANH SÁCH TUYẾN TÍNH :..................................28

III. STACK (CHỒNG) :............................................................................................................................... 35

III.1. Khái niệm :.................................................................................................................................... 35

III.2. Các phép toán trên stack :................................................................................................... 36

III.3. Ví dụ :................................................................................................................................................. 37

IV. QUEUE (HÀNG ĐỢI) :.................................................................................................................... 41

IV.1. Khái niệm :.................................................................................................................................... 41

IV.2. Các phép toán trên hàng đợi:............................................................................................ 42

a. Phép thêm vào :................................................................................................................... 42

b. Phép loại bỏ :......................................................................................................................... 43

IV.3. Ví dụ :............................................................................................................................................... 43

BÀI TẬP :................................................................................................................................................................ 46

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

CHƯƠNG IV : DANH SÁCH LIÊN KẾT (LINKED LIST)

I. KHÁI NIỆM :............................................................................................................................................ 47

II. CÁC PHÉP TOÁN TRÊN DANH SÁCH LIÊN KẾT :...........................................49

II.1. Tạo danh sách :.............................................................................................................................. 49

a. Khởi tạo danh sách (Initialize) :................................................................................. 49

b. Cấp phát vùng nhớ (New_Node) :........................................................................... 49

c. Thêm vào đầu danh sách (Insert_first) :.............................................................. 49

d. Thêm nút mới vào sau nút có địa chỉ p (Insert_after) :.............................50

II.2. Tìm kiếm (Search_info) :...................................................................................................... 50

II.3. Cập nhật danh sách :.................................................................................................................. 51

a. Giải phóng vùng nhớ :...................................................................................................... 51

b. Kiểm tra danh sách liên kết rỗng hay không (Empty) :............................51

c. Xóa phần tử đầu của danh sách (Delete_First) :............................................ 51

d. Xóa phần tử đứng sau nút có địa chỉ p (Delete_after) :.............................52

e. Xóa phần tử theo nội dung (Delete_info) :.....................................................52

f. Xóa toàn bộ danh sách (Clearlist) :......................................................................... 52

II.4. Duyệt danh sách :........................................................................................................................ 53

II.5. Sắp xếp (Selection_Sort) :.................................................................................................... 53

III. CÁC PHÉP TOÁN TRÊN DANH SÁCH LIÊN KẾT CÓ THỨ TỰ :.........54

III.1. Phép thêm vào :.......................................................................................................................... 54

III.2. Phép trộn :....................................................................................................................................... 55

IV. DANH SÁCH LIÊN KẾT VÒNG :........................................................................................ 66

IV.1. Khái niệm :................................................................................................................................... 66

IV.2. Các phép toán trên danh sách liên kết vòng :....................................................... 67

IV.2.1.Tạo danh sách :........................................................................................................... 67

IV.2.2. Duyệt danh sách :................................................................................................... 68

IV.2.3. Phép loại bỏ :............................................................................................................... 69

IV.2.4. Tìm kiếm (Srch_info) :....................................................................................... 71

IV.2.5. Sắp xếp (Selection_Sort) :................................................................................ 72

V. DANH SÁCH LIÊN KẾT KÉP (Doubly Linked List) :........................81

V.1. Khái niệm :...................................................................................................................................... 81

V.2. Các phép toán trên danh sách liên kết kép :.............................................................. 81

V.2.1.Tạo danh sách :............................................................................................................... 81

V.2.2. Duyệt danh sách :........................................................................................................ 83

V.2.3. Phép loại bỏ:.................................................................................................................... 84

V.2.4. Tìm kiếm (Search_info) :...................................................................................... 86

VI. STACK & QUEUE TRÊN DANH SÁCH LIÊN KẾT :..........................................98

VI.1 Stack :............................................................................................................................................... 98

VI.1.1. Khái niệm :................................................................................................................. 98

VI.1.2. Các phép toán trên Stack :............................................................................... 99

a. Phép thêm vào (push) :................................................................................ 99

b. Phép loại bỏ (pop) :....................................................................................... 99

VI.2. Queue :........................................................................................................................................... 100

VI.2.1. Khái niệm :............................................................................................................... 100

VI.2.2. Các phép toán trên Queue :.......................................................................... 100

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

a. Phép thêm vào :............................................................................................... 100

b. Phép loại bỏ :................................................................................................... 101

BÀI TẬP :............................................................................................................................................................. 104

CHƯƠNG V : CÂY (TREE)

I. ĐỊNH NGHĨA VÀ KHÁI NIỆM :.......................................................................................... 107

I.1. Một số khái niệm cơ bản :..................................................................................................... 107

I.2. Cách biểu diễn cây :................................................................................................................. 109

I.3. Biểu diễn thứ tự các nút trong cây :............................................................................... 109

II. CÂY NHỊ PHÂN (BINARY TREE) :.................................................................................. 110

II.1. Định nghĩa :.................................................................................................................................... 110

1. Cây nhị phân :........................................................................................................................ 110

2. Các cây nhị phân đặc biệt :............................................................................................ 110

3. Các phép duyệt cây (Traverse) :............................................................................... 112

II.2. Các phép toán trên cây nhị phân :.................................................................................. 113

II.2.1. Tạo cây :............................................................................................................................ 113

a. Khởi tạo cây (Initialize) :................................................................................ 113

b. Tạo cây BST (Create_Tree) :...................................................................... 113

II.2.2. Cập nhật cây :................................................................................................................ 114

a. Giải phóng vùng nhớ :.................................................................................... 114

b. Kiểm tra cây nhị phân rỗng hay không (Empty) :.......................114

c. Hủy bỏ một nút trong cây nhị phân BST (Remove) :...............114

d. Tìm kiếm trên BST (Search) :.................................................................... 117

II.2.3. Các phép duyệt cây :................................................................................................ 117

a. Duyệt cây theo thứ tự NLR (Preorder) :...............................................117

b. Duyệt cây theo thứ tự LNR (Inorder) :.................................................118

c. Duyệt cây theo thứ tự LRN (Posorder) :..............................................119

d. Duyệt cây theo mức :........................................................................................ 120

III. CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG (AVL) :...............................................122

III.1. Định nghĩa :................................................................................................................................ 122

III.2. Các phép toán trên cây AVL :......................................................................................... 123

III.2.1. Thêm nút :................................................................................................................. 124

III.2.2. Cập nhật cây :.......................................................................................................... 131

1. Tìm kiếm (Search) :.................................................................................... 131

2. Xóa nút : Remove (root, x) :................................................................. 131

III.2.3. Các phép duyệt cây :........................................................................................... 132

BÀI TẬP :............................................................................................................................................................. 133

CHƯƠNG VI : SẮP XẾP VÀ TÌM KIẾM

I. MỘT SỐ PHƯƠNG PHÁP SẮP XẾP ĐƠN GIẢN :...............................................134

I.1. Sắp xếp theo phương pháp Bubble_Sort (phương pháp nổi bọt) :..........134

I.2. Insertion Sort (Phương pháp xen vào) :..................................................................... 136

I.3. Selection Sort (Phương pháp lựa chọn) :................................................................... 137

II. QUICK_SORT : (Sắp xếp theo phương pháp phân đoạn) :..................................138

1. Nội dung :............................................................................................................................................. 138

2. Giải thuật :........................................................................................................................................... 139

a. Giải thuật không đệ quy :.................................................................................................. 139

Downloaded by EBOOKBKMT VMTC (nguyenphihung1009@gmail.com)

lOMoARcPSD|2935381

b. Giải thuật Quick Sort đệ qui :........................................................................................ 141

3. Phân tích :............................................................................................................................................. 141

III. HEAP SORT (Sắp xếp kiểu vun đống) :............................................................................. 143

III.1. Định nghĩa Heap :.................................................................................................................. 143

III.2. Thuật toán Heap Sort :......................................................................................................... 143

IV. MERGE SORT (Sắp xếp kiểu trộn) :.................................................................................... 151

V. TÌM KIẾM :............................................................................................................................................. 153

V.1. Khái niệm :..................................................................................................................................... 153

V.2. Tìm kiếm tuần tự :.................................................................................................................... 153

V.3. Tìm kiếm nhị phân :............................................................................................................... 153

V.4. Phép tìm kiếm nhị phân đệ qui :..................................................................................... 154

BÀI TẬP :............................................................................................................................................................. 155

CHƯƠNG VII : ĐỒ THỊ (GRAPH)

I. CẤU TRÚC DỮ LIỆU CHO ĐỒ THỊ :............................................................................ 156

I.1. Định nghĩa đồ thị :...................................................................................................................... 156

I.2. Các khái niệm trên đồ thị :................................................................................................... 157

I.3. Tổ chức dữ liệu cho đồ thị :................................................................................................. 158

a. Ma trận kề (mảng 2 chiều) :.......................................................................................... 158

b. Danh sách kề (mảng 1 chiều kết hợp với danh sáchliên kết) :...........158

II. DUYỆT ĐỒ THỊ :............................................................................................................................... 159

II.1. Duyệt theo chiều sâu (Depth-First Travelsal) :................................................... 160

II.2. Duyệt theo độ rộng (Breadth First Travelsal) :....................................................161

III. BÀI TOÁN BAO ĐÓNG TRUYỀN ỨNG :................................................................. 163

III.1. Khái niệm :.................................................................................................................................. 163

III.2. Thuật toán WarShall :........................................................................................................... 164

IV. GIẢI THUẬT TÌM ĐƯỜNG ĐI NGẮN NHẤT :.................................................... 167

V. SẮP THỨ TỰ TOPO :.................................................................................................................... 170

V.1. Khái niệm :.................................................................................................................................... 170

V.2. Thuật toán :..................................................................................................................................... 170

V.3. Cài đặt :............................................................................................................................................ 173

BÀI TẬP :............................................................................................................................................................. 177

TÀI LIỆU THAM KHẢO..

LINK 1 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 2 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 3 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 4 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK DOWNLOAD