Download miễn phí Giáo trình Môn Cấu trúc dữ liệu và giải thuật
MỤC LỤC
Mục Trang
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & GT .3
1.1. Tầm quan trọng của CTDL & GT trong một đề án tin học . 3
1.1.1. Xây dựng cấu trúc dữ liệu . 3
1.1.2. Xây dựng giải thuật . 3
1.1.3. Mối quan hệ giữa cấu trúc dữ liệu vàgiải thuật . 3
1.2. Đánh giá Cấu trúc dữ liệu & Giải thuật . 3
1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu . 3
1.2.2. Đánh giá độ phức tạp của thuật toán . 4
1.3. Kiểu dữ liệu . 4
1.3.1. Khái niệm về kiểu dữ liệu . 4
1.3.2. Các kiểu dữ liệu cơ sở . 4
1.3.3. Các kiểu dữ liệu có cấu trúc. 5
1.3.4. Kiểu dữ liệu con trỏ. 5
1.3.5. Kiểu dữ liệu tập tin. 5
Câu hỏi và bài tập . 6
CHƯƠNG 2: KỸ THUẬT TÌM KIẾM (Searching) .8
2.1. Khái quát về tìm kiếm . 8
2.2. Các giải thuật tìm kiếm nội . 8
2.2.1. Đặt vấn đề . 8
2.2.2. Tìm tuyến tính. 8
2.2.3. Tìm nhị phân. 10
2.3. Các giải thuật tìm kiếm ngoại . 14
2.3.1. Đặt vấn đề . 14
2.3.2. Tìm tuyến tính. 14
2.3.3. Tìm kiếm theo chỉ mục . 16
Câu hỏi và bài tập . 17
CHƯƠNG 3: KỸ THUẬT SẮP XẾP (SORTING) . 19
3.1. Khái quát về sắp xếp . 19
3.2. Các giải thuật sắp xếp nội . 19
3.2.1 Sắp xếp bằng phương pháp đổi chỗ . 20
3.2.2. Sắp xếp bằng phương pháp chọn . 28
3.2.3. Sắp xếp bằng phương pháp chèn . 33
3.2.4. Sắp xếp bằng phương pháp trộn . 40
3.3. Các giải thuật sắp xếp ngoại . 60
3.3.1. Sắp xếp bằng phương pháp trộn . 60
3.3.2. Sắp xếp theo chỉ mục . 79
Câu hỏi và bài tập . 82
CHƯƠNG 4: DANH SÁCH (LIST) . 84
4.1. Khái niệm về danh sách . 84
4.2. Các phép toán trên danh sách . 84
4.3. Danh sách đặc . 85
4.3.1. Định nghĩa . 85
4.3.2. Biểu diễn danh sách đặc. 85
4.3.3. Các thao tác trên danh sách đặc . 85
4.3.4. Ưu nhược điểm và Ứng dụng . 91
4.4. Danh sách liên kết . 92
4.4.1. Định nghĩa . 92
4.4.2. Danh sách liên kết đơn . 92
4.4.3. Danh sách liên kết kép . 111
4.4.4. Ưu nhược điểm của danh sách liên kết . 135
4.5. Danh sách hạn chế . 135
4.5.1. Hàng đợi. 135
4.5.2. Ngăn xếp . 142
4.5.3. Ứng dụng của danh sách hạn chế. 147
Câu hỏi và bài tập . 147
CHƯƠNG 5: CÂY (TREE) . 149
5.1. Khái niệm – Biểu diễn cây. 149
5.1.1. Định nghĩa cây . 149
5.1.2. Một số khái niệm liên quan . 149
5.1.3. Biểu diễn cây . 151
5.2. Cây nhị phân . 152
5.2.1. Định nghĩa . 152
5.2.2. Biểu diễn và Các thao tác . 152
5.2.3. Cây nhị phân tìm kiếm. 163
5.3. Cây cân bằng . 188
5.3.1. Định nghĩa – Cấu trúc dữ liệu. 188
5.3.2. Các thao tác . 189
Câu hỏi và bài tập . 227
ÔN TẬP (REVIEW) . 224
Hệ thống lại các Cấu trúc dữ liệu và cácGiải thuật đã học. 224
Câu hỏi và Bài tập ôn tập tổng hợp . 227
TÀI LIỆU THAM KHẢO . 229
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
tTrang: 97
// Nối các nút kế sau InsNode vào sau NewNode
B4: NewNode->NextNode = InsNode->NextNode
// Chuyển mối liên kết giữa InsNode với nút kế của nó về NewNode
B5: InsNode->NextNode = NewNode
Bkt: Kết thúc
- Minh họa thuật toán:
Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25 vào sau nút có địa chỉ
InsNode như sau: NewData = 25
NewNode 25 NULL
SLList InsNode
15 10 20 18 40 35 NULL
NewNode->NextNode = InsNode->NextNode:
NewNode 25
SLList InsNode
15 10 20 18 40 35 NULL
InsNode->NextNode = NewNode:
NewNode 25
SLList
15 10 20 18 40 35 NULL
InsNode
Kết quả sau khi chèn:
SLList NULL
15 10 20 25 18 40 35
- Cài đặt thuật toán:
Các hàm thêm phần tử tương ứng với các trường hợp có prototype như sau:
SLL_Type SLL_Add_First(SLL_Type &SList, T NewData);
SLL_Type SLL_Add_Last(SLL_Type &SList, T NewData);
SLL_Type SLL_Add_Mid(SLL_Type &SList, T NewData, SLL_Type &InsNode);
Hàm thực hiện việc chèn phần tử có giá trị thành phần dữ liệu NewData vào trong
danh sách liên kết đơn quản lý bởi con trỏ đầu danh sách SList tương ứng với 3
trường hợp: Thêm đầu, thêm cuối, thêm giữa. Các hàm trả về giá trị là địa chỉ của
nút đầu tiên nếu việc thêm thành công. Trong trường hợp ngược lại, các hàm trả
về con trỏ NULL.
Riêng đối với trường hợp thêm giữa, hàm SLL_Add_Mid thực hiện việc thêm vào
ngay sau nút có địa chỉ InsNode. Nội dung của các hàm như sau:
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 98
SLL_Type SLL_Add_First(SLL_Type &SList, T NewData)
{ SLL_Type NewNode = SLL_Create_Node(NewData);
if (NewNode == NULL)
return (NULL);
NewNode->NextNode = SList;
SList = NewNode;
return (SList);
}
//================================================= ================
SLL_Type SLL_Add_Last(SLL_Type &SList, T NewData)
{ SLL_Type NewNode = SLL_Create_Node(NewData);
if (NewNode == NULL)
return (NULL);
if (SList == NULL)
{ SList = NewNode;
return (SList);
}
SLL_Type CurNode = SList;
while (CurNode->NextNode != NULL)
CurNode = CurNode->NextNode;
CurNode->NextNode = NewNode;
return (SList);
}
//================================================= ================
SLL_Type SLL_Add_Mid(SLL_Type &SList, T NewData, SLL_Type &InsNode)
{ SLL_Type NewNode = SLL_Create_Node(NewData);
if (NewNode == NULL)
return (NULL);
if (InsNode->NextNode == NULL)
{ InsNode->NextNode = NewNode;
return (SList);
}
NewNode->NextNode = InsNode->NextNode;
InsNode->NextNode = NewNode;
return (SList);
}
d. Duyệt qua các nút trong danh sách:
Đây là một thao tác thường xuyên xảy ra trên danh sách liên kết đơn nói chung và
các danh sách khác nói riêng để thực hiện t hao tác xử lý các nút hay xử lý dữ liệu
tại các nút. Có nhiều thao tác xử lý tùy t ừng trường hợp và yêu cầu song ở đây đơn
giản chúng ta chỉ duyệt để xem nội dung thành phần dữ liệu trong danh sách.
- Thuật toán:
B1: CurNode = SLList
B2: IF (CurNode = NULL)
Thực hiện Bkt
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 99
B3: OutputData(CurNode->Key) // Xuất giá trị thành phần dữ liệu trong 1 nút
B4: CurNode = CurNode->NextNode
B5: Lặp lại B2
Bkt: Kết thúc
- Cài đặt thuật toán:
Hàm SLL_Travelling có prototype:
void SLL_Travelling(SLL_Type SList);
Hàm duyệt qua các nút trong danh sách liên kết đơn quản lý bởi địa chỉ nút đầu
tiên thông qua SList để xem nội dung thành phần dữ liệu của mỗi nút.
Nội dung của hàm như sau:
void SLL_Travelling (SLL_Type SList)
{ SLL_Type CurNode = SList;
while (CurNode != NULL)
{ OutputData(CurNode->Key);
CurNode = CurNode->NextNode;
}
return;
}
Lưu ý:
Hàm OutputData thực hiện việc xuất nội dung của một biến có kiểu dữ liệu T. Tùy
vào từng trường hợp cụ thể mà chúng ta viết hàm OutputData cho phù hợp.
e. Tìm kiếm một phần tử trong danh sách:
Giả sử chúng ta cần tìm kiếm xem trong danh sách liên kết đơn có tồn tại nút có
thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật
toán tìm tuyến t ính để tìm kiếm.
- Thuật toán:
B1: CurNode = SLList
B2: IF (CurNode = NULL OR CurNode->Key = SearchData)
Thực hiện Bkt
B3: CurNode = CurNode->NextNode
B4: Lặp lại B2
Bkt: Kết thúc
- Cài đặt thuật toán:
Hàm SLL_Searching có prototype:
SLL_Type SLL_Searching(SLL_Type SList, T SearchData);
Hàm thực hiện việc tìm kiếm nút có thành phần dữ liệu là SearchData trên danh
sách liên kết đơn quản lý bởi địa chỉ nút đầu tiên thông qua SList. Hàm trả về địa
chỉ của nút đầu tiên trong danh sách khi tìm thấy, ngược lại hàm trả về con trỏ
NULL.
Nội dung của hàm như sau:
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 100
SLL_Type SLL_Searching(SLL_Type SList, T SearchData)
{ SLL_Type CurNode = SList;
while (CurNode != NULL)
{ if (CurNode->Key == SearchData)
break;
CurNode = CurNode->NextNode;
}
return (CurNode);
}
f. Loại bỏ bớt một phần tử ra khỏi danh sách:
Giả sử chúng ta cần loại bỏ phần tử có giá trị thành phần dữ liệu là DelData trong
danh sách liên kết đơn. Để thực hiện điều này trước tiên chúng ta phải thực hiện
thao tác tìm kiếm địa chỉ của nút có thành phần dữ liệu là DelData, sau đó mới thực
hiện thao tác loại bỏ nếu tìm thấy. Tuy nhiên trong quá trình tìm kiếm, nếu tìm thấy
chúng ta phải ghi nhận địa chỉ của nút đứng ngay trước nút tìm thấy là PreDelNode.
- Thuật toán:
// Tìm kiếm nút có Key là DelData trong danh sách
B1: DelNode = SLList
B2: PreDelNode = NULL
B3: IF (DelNode = NULL)
Thực hiện Bkt
B4: IF (DelNode->Key=DelData)
Thực hiện B8
B5: PreDelNode = DelNode
B6: DelNode = DelNode->NextNode
B7: Lặp lại B3
// Loại bỏ nút tại địa chỉ DelNode ra khỏi danh sách
B8: IF (PreDelNode = NULL) // Loại bỏ nút đầu tiên trong danh sách
B8.1: SLList = SLList->NextNode
B8.2: Thực hiện B10
// Liên kết các nốt sau DelNode về nút PreDelNode
B9: PreDelNode->NextNode = DelNode->Next Node
// Cắt mối liên kết giữa DelNode với các nút còn lại trong danh sách
// và hủy DelNode
B10: DelNode->NextNode = NULL
B11: delete DelNode
Bkt: Kết thúc
- Cài đặt thuật toán:
Hàm SLL_Delete_Node có prototype:
int SLL_Delete_Node (SLL_Type &SList, T DelData);
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 101
Hàm thực hiện việc xóa phần tử có thành phần dữ liệu là DelData t rong danh sách
liên kết quản lý bởi con trỏ đầu SList. Hàm trả về giá trị 1 nếu việc xóa thành
công và ngược lại, hàm trả về giá trị -1. Nội dung của hàm như sau:
int SLL_Delete_Node (SLL_Type &SList, T DelData)
{ SLL_Type DelNode = SList;
SLL_Type PreDelNode = NULL;
while (DelNode != NULL)
{ if (DelNode->Key == DelData)
break;
PreDelNode = DelNode;
DelNode = DelNode->NextNode;
}
if (DelNode == NULL)
return (-1);
if (PreDelNode == NULL)
SList = SList->NextNode;
else
PreDelNode->NextNode = DelNode->NextNode;
DelNode->NextNode = NULL;
delete DelNode;
return (1);
}
- Minh họa thuật toán:
+ Giả sử chúng ta cần hủy nút có thành phần dữ liệu là 25: DelData = 25
SLList NULL
25 10 20 18 40 35 30
DelNode
SLList = SLList->NextNode
DelNode SLList NULL
25 10 20 18 40 35 30
DelNode->NextNode = NULL
DelNode SLList NULL
25 10 20 18 40 35 30
NULL
Kết quả sau khi hủy:
SLList
10 20 18 40 35 30 NULL
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 102
+ Bây giờ giả sử chúng ta cần hủy nút có thành phần dữ liệu là 20: DelData = 20
SLList DelNode NULL
25 10 20 18 40 35 30
PreDelNode
PreDelNode->NextNode = DelNode->Next
SLList DelNode NULL
25 10 20 18 40 35 30
PreDelNode
DelNode->Next = NULL
SLList DelNode NULL NULL
25 10 20 18 40 35 30
PreDelNod...