littledream77
New Member
Download miễn phí Giáo trình Cấu trúc dữ liệu - Đại học Cần Thơ
MỤC LỤC
CHƯƠNG IMỞ ĐẦ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
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
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
Để 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:
ể cho frontvà rear đều bằng -1.
void MakeNull_Queue(Queue *Q){
Q->Front=-1;
Q->Rear=-1;
}
Kiểm tra hàng rỗng
int Empty_Queue(Queue Q){
return Q.Front==-1;
}
Kiểm tra hàng đầy
Hàng đầy nếu toàn bộ các ô trong mảng đang chứa các phần tử của hàng. Với phương
pháp này thì front có thể lớn hơn rear. Ta có hai trường hợp hàng đầy như sau:
- Trường hợp Q.Rear=Maxlength-1 và Q.Front =0
- Trường hợp Q.Front =Q.Rear+1.
Để đơn giản ta có thể gom cả hai trường hợp trên lại theo một công thức như sau:
(Q.rear-Q.front +1) mod Maxlength =0
int Full_Queue(Queue Q){
return (Q.Rear-Q.Front+1) % MaxLength==0;
}
Xóa một phần tử ra khỏi ngăn xếp
Khi xóa một phần tử ra khỏi hàng, ta xóa tại vị trí đầu hàng và có thể xảy ra các trường
hợp sau:
Nếu hàng rỗng thì báo lỗi không xóa;
Ngược lại, nếu hàng chỉ còn 1 phần tử thì khởi tạo lại hàng rỗng;
Trang 58
Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản
Ngược lại, thay đổi giá trị của Q.Front.
(Nếu Q.front != Maxlength-1 thì đặt lại Q.front = q.Front +1;
Ngược lại Q.front=0)
void DeQueue(Queue *Q){
if (!Empty_Queue(*Q)){
//Nếu hàng chỉ chứa một phần tử thì khởi tạo hàng lại
if (Q->Front==Q->Rear) MakeNull_Queue(Q);
else Q->Front=(Q->Front+1) % MaxLength;
//tăng Front lên 1 đơn vị
}
else printf("Loi: Hang rong!");
}
Thêm một phần tử vào hàng
Khi thêm một phần tử vào hàng thì có thể xảy ra các trường hợp sau:
- Trường hợp hàng đầy thì báo lỗi và không thêm;
- Ngược lại, thay đổi giá trị của Q.rear (Nếu Q.rear =maxlength-1 thì đặt lại Q.rear=0;
Ngược lại Q.rear =Q.rear+1) và đặt nội dung vào vị trí Q.rear mới.
void EnQueue(ElementType X,Queue *Q){
if (!Full_Queue(*Q)){
if (Empty_Queue(*Q)) Q->Front=0;
Q->Rear=(Q->Rear+1) % MaxLength;
Q->Elements[Q->Rear]=X;
}
else printf("Loi: Hang day!");
}
Cài đặt hàng bằng mảng vòng có ưu điểm gì so với bằng mảng theo phương
pháp tịnh tiến? Trong ngôn ngữ lập trình có kiểu dữ liệu mảng vòng không?
V
Trang 59
Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản
c. Cài đặt hàng bằng danh sách liên kết (cài đặt bằng con trỏ)
Cách tự nhiên nhất là dùng hai con trỏ front và rear để trỏ tới phần tử đầu và cuối hàng.
Hàng được cài đặt như một danh sách liên kết có Header là một ô thực sự, xem hình II.13.
Khai báo cần thiết
typedef ... ElementType; //kiểu phần tử của hàng
typedef struct Node{
ElementType Element;
Node* Next; //Con trỏ chỉ ô kế tiếp
};
typedef Node* Position;
typedef struct{
Position Front, Rear;
//là hai trường chỉ đến đầu và cuối của hàng
} Queue;
Khởi tạo hàng rỗng
Khi hàng rỗng Front va Rear cùng trỏ về 1 vị trí đó chính là ô header
Hình II.13: Khởi tạo hàng rỗng
void MakeNullQueue(Queue *Q){
Position Header;
Header=(Node*)malloc(sizeof(Node)); //Cấp phát Header
Header->Next=NULL;
Q->Front=Header;
Q->Rear=Header;
}
Kiểm tra hàng rỗng
Trang 60
Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản
Hàng rỗng nếu Front và Rear chỉ cùng một vị trí là ô Header.
int EmptyQueue(Queue Q){
return (Q.Front==Q.Rear);
}
Hình II.14 Hàng sau khi thêm và xóa phần tử
Thêm một phần tử vào hàng
Thêm một phần tử vào hàng ta thêm vào sau Rear (Rear->next ), rồi cho Rear trỏ đến
phần tử mới này, xem hình II.14. Trường next của ô mới này trỏ tới NULL.
void EnQueue(ElementType X, Queue *Q){
Q->Rear->Next=(Node*)malloc(sizeof(Node));
Q->Rear=Q->Rear->Next;
//Dat gia tri vao cho Rear
Q->Rear->Element=X;
Q->Rear->Next=NULL;
}
Xóa một phần tử ra khỏi hàng
Trang 61
Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản
Thực chất là xoá phần tử nằm ở vị trí đầu hàng do đó ta chỉ cần cho front trỏ tới vị trí kế
tiếp của nó trong hàng.
void DeQueue(Queue *Q){
if (!Empty_Queue(Q)){
Position T;
T=Q->Front;
Q->Front=Q->Front->Next;
free(T);
}
else printf(”Loi : Hang rong”);
}
4. Một số ứng dụng của cấu trúc hàng
Hàng đợi là một cấu trúc dữ liệu được dùng khá phổ biến trong thiết kế giải thuật. Bất kỳ
nơi nào ta cần quản lí dữ liệu, quá trình... theo kiểu vào trước-ra trước đều có thể ứng dụng
hàng đợi.
Ví dụ rất dễ thấy là quản lí in trên mạng, nhiều máy tính yêu cầu in đồng thời và ngay cả
một máy tính cũng yêu cầu in nhiều lần. Nói chung có nhiều yêu cầu in dữ liệu, nhưng máy
in không thể đáp ứng tức thời tất cả các yêu cầu đó nên chương trình quản lí in sẽ thiết lập
một hàng đợi để quản lí các yêu cầu. Yêu cầu nào mà chương trình quản lí in nhận trước nó
sẽ giải quyết trước.
Một ví dụ khác là duyệt cây theo mức được trình bày chi tiết trong chương sau. Các giải
thuật duyệt theo chiều rộng một đồ thị có hướng hay vô hướng cũng dùng hàng đợi để quản
lí các nút đồ thị. Các giải thuật đổi biểu thức trung tố thành hậu tố, tiền tố.
IV. DANH SÁCH LIÊN KẾT KÉP (DOUBLE - LISTS)
Một số ứng dụng đòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một cách hiệu
quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trước X và sau X một cách mau chóng.
Trong trường hợp này ta phải dùng hai con trỏ, một con trỏ chỉ đến phần tử đứng sau (next),
một con trỏ chỉ đến phần tử đứng trước (previous). Với cách tổ chức này ta có một danh
sách liên kết kép. Dạng của một danh sách liên kép như sau:
Trang 62
Cấu trúc dữ liệu Chương II: Các kiểu dữ liệu trừu tượng cơ bản
Hình II.15 Hình ảnh một danh sách liên kết kép
Các khai báo cần thiết
typedef ... ElementType;
//kiểu nội dung của các phần tử trong danh sách
typedef struct Node{
ElementType Element; //lưu trữ nội dung phần tử
//Hai con trỏ trỏ tới phần tử trước và sau
Node* Prev;
Node* Next;
};
typedef Node* Position;
typedef Position DoubleList;
Để quản lí một danh sách liên kết kép ta có thể dùng một con trỏ trỏ đến một ô bất kỳ
trong cấu trúc. Hoàn toàn tương tự như trong danh sách liên kết đơn đã trình bày trong phần
trước, con trỏ để quản lí danh sách liên kết kép có thể là một con trỏ có kiểu giống như kiểu
phần tử trong danh sách và nó có thể được cấp phát ô nhớ (tương tự như Header trong danh
sách liên kết đơn) hay không được cấp phát ô nhớ. Ta cũng có thể xem danh sách liên kết
kép như là danh sách liên kết đơn, với một bổ sung duy nhất là có con trỏ previous để nối
kết các ô theo chiều ngược lại. Theo quan điểm này thì chúng ta có thể cài đặt các phép toán
thêm (insert), xoá (delete) một phần tử hoàn toàn tương tự như trong danh sách liên kết đơn
và con trỏ Header cũng cần thiết như trong danh sách liên kết đơn, vì nó chính là vị trí của
phần tử đầu tiên trong danh sách.
Tuy nhiên, nếu tận dụng khả năng duyệt theo cả hai chiều thì ta không cần cấp phát
bộ nhớ cho Header và vị trí (position) của một phần tử trong danh sách có thể định nghĩa
như sau: Vị trí của phần tử ai là con trỏ trỏ tới ô chứa ai, tức là địa chỉ ô nhớ chứa ai. Nói
nôm na, vị trí của ai là ô chứa ai. Theo định nghĩa vị trí như vậy các phép toán trên danh
sách liên kết kép sẽ được cài đặt hơi khác với danh sách liên đơn. Trong cách cài đặt này,
chúng ta không sử dụng ô đầu m...