Giáo trình Cấu trúc dữ liệu và giải thuật - Học viện Công nghệ Bưu chính Viễn thông

 khác với ngăn xếp ở chỗ: phần tử mới được đưa vào hàng đợi sẽ nằm ở phía 
cuối hàng, trong khi phần tử mới đưa vào ngăn xếp lại nằm ở đỉnh ngăn xếp. 
Như vậy, ta có thể định nghĩa hàng đợi là một dạng đặc biệt của danh sách mà việc lấy ra 
một phần tử, get, được thực hiện ở 1 đầu (gọi là đầu hàng), còn việc bổ sung 1 phần tử, put, được 
thực hiện ở đầu còn lại (gọi là cuối hàng). 
- 
* 
- 
* 
 61
Trở lại với ví dụ về việc bổ sung và loại bỏ các phần tử của 1 ngăn xếp các ký tự như ở 
phần trước, ta sẽ xem xét việc bổ sung và loại bỏ tương tự nhưng áp dụng cho hàng đợi các ký tự. 
Giả sử ta có hàng đợi Q lưu trữ các ký tự. Ban đầu Q ở trạng thái rỗng: 
Khi thực hiện lệnh bổ sung phần tử A, put(Q, A), hàng đợi có dạng: 
Tiếp theo là các lệnh put(Q, B), put(Q, C): 
Khi thực hiện lệnh get để lấy ra 1 phần tử từ hàng đợi thì phần tử được lưu trữ lâu nhất 
trong hàng sẽ được lấy ra. Đó là phần tử đầu tiên ở đầu hàng. 
Tiếp theo, thực hiện lệnh put(Q, D) để bổ sung phần tử D. Phần tử này sẽ được bổ sung ở 
phía cuối của hàng. 
Hai lệnh get tiếp theo sẽ lần lượt lấy ra 2 phần tử ở đầu hàng là B và C. 
4.2.2 Cài đặt hàng đợi bằng mảng 
Tương tự như ngăn xếp, hàng đợi có thể được cài đặt bằng mảng hoặc danh sách liên kết. 
Đối với ngăn xếp, việc bổ sung và loại bỏ một phần tử đều được thực hiện ở đỉnh ngăn xếp, do 
vậy ta chỉ cần sử dụng 1 biến top để lưu giữ để đỉnh này. Tuy nhiên, đối với hàng đợi việc bổ sung 
và loại bỏ phần tử được thực hiện ở 2 đầu khác nhau, do vậy ta cần sử dụng 2 biến là head và tail 
để lưu giữ điểm đầu và điểm cuối của hàng đợi. Các phần tử thuộc hàng đợi là các phần tử nằm 
giữa điểm đầu và điểm cuối này. 
 Đầu hàng Cuối hàng
A Đầu hàng Cuối hàng
A B C Đầu hàng Cuối hàng
 B C Đầu hàng Cuối hàng
 B C D Đầu hàng Cuối hàng
 C D Đầu hàng Cuối hàng
 D Đầu hàng Cuối hàng
 62
Hình 4.3 Cài đặt hàng đợi bằng mảng 
Để lấy ra 1 phần tử của hàng, điểm đầu tăng lên 1 và phần tử ở đầu hàng sẽ được lấy ra. Để 
bổ sung 1 phần tử vào hàng đợi, phần tử này sẽ được bổ sung vào cuối hàng và điểm cuối sẽ tăng 
lên 1. 
Ta thấy rằng biến tail luôn tăng khi bổ sung phần tử và cũng không giảm khi loại bỏ phần 
tử. Do đó, sau 1 số hữu hạn thao tác, biến này sẽ tiến đến cuối mảng và cho dù phần đầu mảng có 
thể còn trống do một số phần tử của hàng đợi đã được lấy ra, ta vẫn không thể bổ sung thêm phần 
tử vào hàng đợi. Để giải quyết vấn đề này, ta sử dụng phương pháp quay vòng. Khi biến tail tiến 
đến cuối mảng và phần đầu mảng còn trống thì ta sẽ cho biến này quay trở lại đầu mảng. Tương 
tự vậy, ta cũng cho biến head quay lại đầu mảng khi nó tiến tới cuối mảng. 
Khai báo bằng mảng cho 1 hàng đợi chứa các số nguyên với tối đa 100 phần tử như sau: 
#define MAX 100 
typedef struct { 
 int head, tail, count; 
 int node[MAX]; 
} queue; 
Trong khai báo này, để thuận tiện cho việc kiểm tra hàng đợi đầy hoặc rỗng, ta dùng thêm 1 
biến count để cho biết số phần tử hiện tại của hàng đợi. 
Khi đó, các thao tác trên hàng đợi được cài đặt như sau: 
Thao tác khởi tạo hàng đợi 
Thao tác này thực hiện việc gán giá trị 0 cho biến head, giá trị MAX -1 cho biến tail, và giá 
trị 0 cho biến count, cho biết hàng đợi đang ở trạng thái rỗng. 
void QueueInitialize(queue *q){ 
q-> head = 0; 
q-> tail = MAX-1; 
q-> count = 0; 
return; 
} 
Thao tác kiểm tra hàng đợi rỗng 
Hàng đợi rỗng nếu có số phần tử nhỏ hơn hoặc bằng 0. 
int QueueEmpty(queue q){ 
return (q.count <= 0); 
} 
head tail 
0 max
 63
Thao tác thêm 1 phần tử vào hàng đợi 
void Put(queue *q, int x){ 
 if (q-> count == MAX) 
 printf(“Hang doi day !”); 
 else{ 
if (q->tail == MAX-1 ) 
 q->tail=0; 
else 
 (q->tail)++; 
 q->node[q->tail]=x; 
 q-> count++; 
} 
return; 
} 
Để thêm phần tử vào cuối hàng đợi, điểm cuối tăng lên 1 (nếu điểm cuối đã ở vị trí cuối 
mảng thì quay vòng điểm cuối về 0). Trước khi thêm phần tử vào hàng đợi, cần kiếm tra xem 
hàng đợi đã đầy chưa (hàng đợi đầy khi giá trị biến count = MAX). 
Lấy phần tử ra khỏi hàng đợi 
Để lấy phần tử ra khỏi hàng đợi, tiến hành lấy phần tử tại vị trí điểm đầu và cho điểm đầu 
tăng lên 1 (nếu điểm đầu đã ở vị trí cuối mảng thì quay vòng điểm đầu về 0). Tuy nhiên, trước 
khi làm các thao tác này, ta phải kiểm tra xem hàng đợi có rỗng hay không. 
int Get(queue *q){ 
 int x; 
 if (QueueEmpty(*q)) 
 printf("Hang doi rong !"); 
else{ 
 x = q-> node[q-> head]; 
if (q->head == MAX-1 ) 
 q->head=0; 
else 
 (q->head)++; 
 q-> count--; 
} 
return x; 
} 
4.2.3 Cài đặt hàng đợi bằng danh sách liên kết 
Để cài đặt hàng đợi bằng danh sách liên kết, ta cũng sử dụng 1 danh sách liên kết đơn và 2 
con trỏ head và tail lưu giữ nút đầu và nút cuối của danh sách. Việc bổ sung phần tử mới sẽ được 
tiến hành ở cuối danh sách và việc lấy phần tử ra sẽ được tiến hành ở đầu danh sách. 
 64
Hình 4.4 Cài đặt hàng đợi bằng danh sách liên kết 
Khai báo 1 hàng đợi bằng danh sách liên kết như sau: 
struct node { 
 int item; 
 struct node *next; 
}; 
typedef struct node *queuenode; 
typedef struct { 
 queuenode head; 
 queuenode tail; 
}queue; 
Khai báo tương tự như ngăn xếp, tuy nhiên, hàng đợi sử dụng 2 biến là hea và tail để lưu 
giữ điểm đầu và điểm cuối của hàng. Khi đó, các thao tác trên hàng đợi được cài đặt như sau: 
Thao tác khởi tạo hàng đợi 
Thao tác này thực hiện việc gán giá trị null cho nút đầu và cuối của hàng đợi, cho biết hàng 
đợi đang ở trạng thái rỗng. 
void QueueInitialize(queue *q){ 
 q-> head = q-> tail = NULL; 
 return; 
} 
Thao tác kiểm tra hàng đợi rỗng 
Hàng đợi rỗng nếu nút đầu trỏ đến NULL. 
int QueueEmpty(queue q){ 
 return (q.head == NULL); 
} 
Thao tác thêm 1 phần tử vào hàng đợi 
void Put(queue *q, int x){ 
 queuenode p; 
 p = (queuenode) malloc (sizeof(struct node)); 
 p-> item = x; 
 p-> next = NULL; 
 q-> tail-> next = p; 
 q-> tail = q-> tail-> next; 
NULL
head 
tail 
 65
 if (q-> head == NULL) q-> head = q-> tail; 
 return; 
} 
Để thêm phần tử vào cuối hàng đợi, tạo và cấp phát bộ nhớ cho 1 nút mới. Gán giá trị thích 
hợp cho nút này, sau đó cho con trỏ tiếp của nút cuối hàng đợi trỏ đến nó. Nút này bây giờ trở 
thành nút cuối của hàng đợi. Nếu hàng đợi chưa có phần tử nào thì nó cũng chính là nút đầu của 
hàng đợi. 
Lấy phần tử ra khỏi hàng đợi 
Để lấy phần tử ra khỏi hàng đợi, tiến hành lấy phần tử tại vị trí nút đầu và cho nút đầu 
chuyển về nút kế tiếp. Tuy nhiên, trước khi làm các thao tác này, ta phải kiểm tra xem hàng đợi có 
rỗng hay không. 
int Get(queue *q){ 
 queuenode p; 
 if (QueueEmpty(*q)){ 
 printf("Ngan xep rong !"); 
 return 0; 
 }else{ 
 p = q-> head; 
 q-> head = q-> head-> next; 
 return p->item; 
 } 
} 
4.3 TÓM TẮT CHƯƠNG 4 
- Ngăn xếp là một dạng đặc biệt của danh sách mà việc bổ sung hay loại bỏ một phần tử 
đều được thực hiện ở 1 đầu của danh sách. Ngăn xếp còn được gọi là kiểu dữ liệu có 
nguyên tắc LIFO (Last In First Out - Vào sau ra trước). 
- Ngăn xếp có thể được cài đặt bằng mảng hoặc danh sách liên kết. 
- Các thao tác cơ bản trên ngăn xếp bao gồm: Khởi tạo ngăn xếp, kiểm tra ngăn xếp rỗng 
(đầy), thêm 1 phần tử vào ngăn xếp, loại bỏ 1 phần tử khỏi ngăn xếp. 
- Hàng đợi là một cấu trúc dữ liệu gần giống với ngăn xếp, nhưng phần tử được lấy ra 
khỏi hàng đợi không phải là phần tử mới nhất được đưa vào mà là phần tử đã được lưu 
trong hàng đợi lâu nhất. Quy luật của hàng đợi là vào trước ra trước (FIFO - First In 
First Out). 
- Hàng đợi cũng có thể được cài đặt bằng mảng hoặc danh sách liên kết. Các thao tác cơ 
bản cũng bao gồm: Khởi tạo hàng đợi, kiểm tra hàng đợi rỗng (đầy), thêm 1 phần tử vào 
hàng đợi, loại bỏ 1 phần tử khỏi hàng đợi. 
4.4 CÂU HỎI VÀ BÀI TẬP 
1. Để cài đặt ngăn xếp bằng mảng 1 chiều, ta cần bố trí ngăn xếp trong mảng như thế nào? 
Cần dùng thêm các biến phụ nào? 
2. Hạn chế của cài đặt ngăn xếp bằng mảng so với danh sách liên kết là gì? 
 66
3. Để cài đặt ngăn xếp bằng danh sách liên kết cần bố trí danh sách như thế nào? 
4. Hoàn thiện mã nguồn của chương trình tính biểu thưc dạng hậu tố. 
5. Hoàn thiện mã nguồn chương trình chuyển đổi biểu thức dạng trung tố sang hậu tố. 
6. Viết chương trình đổi 1 số nguyên từ hệ thập phân sang nhị phân sử dụng ngăn xếp. 
7. Sự khác biệt cơ bản giữa hàng đợi và ngăn xếp là gì? 
8. Hoàn thiện mã nguồn của chương trình cài đặt ngăn xếp bằng mảng và danh sách liên 
kết bao gồm khai báo và các thao tác như hướng dẫn trong tài liệu. 
9. Hoàn thiện mã nguồn của chương trình cài đặt hàng đợi bằng mảng và danh sách liên 
kết bao gồm khai báo và các thao tác như hướng dẫn trong tài liệu. 
 67
CHƯƠNG 5 
CẤU TRÚC DỮ LIỆU KIỂU CÂY 
Chương 5 giới thiệu một cấu trúc dữ liệu rất gần gũi và có nhiều ứng dụng trong thực tế, đó 
là cấu trúc dữ liệu kiểu cây. 
Các nội dung chính được trình bày trong chương bao gồm: 
- Định nghĩa và các khái niệm về cây. 
- Cài đặt cây : Cài đặt bằng mảng hoặc danh sách liên kết. 
- Phép duyệt cây: Duyệt thứ tự trước, thứ tự giữa, và thứ tự sau. 
Ngoài ra, chương này còn giới thiệu một loại cây đặc biệt, có nhiều ứng dụng trong thực 
tiễn và nghiên cứu khoa học, đó là cây nhị phân. Loại cây đặc biệt hơn nữa là cây nhị phân tìm 
kiếm sẽ được giới thiệu trong chương 7. 
5.1 KHÁI NIỆM 
Cây là một cấu trúc dữ liệu có vai trò quan trọng trong việc phân tích và thiết kế các thuật 
toán. Lưu trữ và biểu diễn dữ liệu kiểu cây có thể thấy trong nhiều lĩnh vực của cuộc sống. Ví dụ 
một cuốn gia phả lưu trữ thông tin về các thành viên trong một dòng họ, trong đó các thành viên 
thức bậc khác nhau được phân thành các cấp khác nhau trong biểu diễn hình cây của gia phả. Sơ 
đồ tổ chức của 1 đơn vị cũng thường được biểu diễn thông qua cấu trúc cây. Các đơn vị con nằm 
ở cấp dưới đơn vị trực tiếp quản lý. Các đơn vị ngang hàng nằm cùng cấp. Trong lĩnh vực máy 
tính, cách lưu trữ dữ liệu của hệ điều hành cũng áp dụng kiểu l