Viết chương trình con tìm kiếm và xóa một phần tử trong danh sách có thứ tự

PHẦN TỔNG QUAN


Giới thiệu:
Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên ngành Công
nghệ thông tin. Các cấu trúc dữ liệu và giải thuật được xem như là hai yếu tố quan trọng nhất
trong lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu+
Giải thuật [Programs = Data Structures + Algorithms]. Nắm vững các cấu trúc dữ liệu và giải
thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các
công cụ lập trình hiện đại.
Cấu trúc dữ liệu có thể được xem như là một phương pháp lưu trữ dữ liệu trong máy tính
nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệu một cách có hiệu
quả thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy cấu trúc dữ liệu và giải
thuật là hai yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau. Việc lựa chọn một
cấu trúc dữ liệu có thể sẽ ảnh hưởng lớn đến việc lựa chọn áp dụng giải thuật nào.
Tài liệu cấu trúc dữ liệu và giải thuật bao gồm 4 chương trình bày về các cấu trúc dữ liệu và
giải thuật cơ bản nhất trong tin học.
Chương 1: trình bày tổng quan về cấu trúc dữ liệu và giải thuật như: các bước trong lập trình
để giải quyết một bài toán, trình bày các khái niệm về các kiểu dữ liệu trừu tượng. Thời gian thực
hiện chương trình, cách đánh giá độ phức tạp của giải thuật.
Chương 2: trình bày các thuật toán sắp xếp và tìm kiếm, cách xác định độ phức tạp của từng
thuật toán, phương pháp cài đặt cụ thể từng thuật toán.
Chương 3: trình bày các khái niệm về các kiểu dữ liệu trừu tượng cơ bản như: danh sách,
ngăn xếp, hàng đợi, cách xây dụng các hàm cơ bản của từng kiểu dữ liệu. Cách ứng dụng các
kiểu dữ liệu trừu tượng trong các bài toán thực tế.
Chương 4: trình bày cấu trúc dữ liệu dạng cây. Các khái niệm về cây, cách cài đặt các hàm và
các phép toán trên cây.
II.
Thành phần tham gia biên soạn giáo trình:
Ths. Trương Thanh Tú.
III.

Giới thiệu môn học:
+ Tên môn học: Cấu trúc dữ liệu và giải thuật.
+ Tổng số tiết: 75, số tiết lý thuyết: 15, số tiết thực hành: 60.
IV.
Đối tượng sử dụng:
Giáo trình này được sử dụng cho sinh viên hệ Cao đẳng Khoa CNTT.
V.
Tài liệu tham khảo:
I.

Phụ lục 03
QT KKT 03/ 03

Trang 1/44


PHẦN NỘI DUNG
CHƯƠNG 3: CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN
[BASIC ABSTRACT DATA TYPES]
1. Tóm tắt nội dung:
Chương 3: trình bày các khái niệm về các kiểu dữ liệu trừu tượng cơ bản như: danh sách,
ngăn xếp, hàng đợi, cách xây dụng các hàm cơ bản của từng kiểu dữ liệu. Cách ứng dụng các
kiểu dữ liệu trừu tượng trong các bài toán thực tế.
2. Nội dung học tập, nghiên cứu:
3.1. Kiểu dữ liệu trừu tượng danh sách.
3.1.1. Khái niệm danh sách.
Mô hình toán học của danh sách là một tập hợp hữu hạn các phần tử có cùng một kiểu, mà tổng
quát ta gọi là kiểu phần tử [Elementtype]. Ta biểu diễn danh sách như là một chuỗi các phần tử
của nó: a1, a2, . . ., anvới n 0. Nếu n=0 ta nói danh sách rỗng [empty list]. Nếu n > 0 ta gọi a 1 là
phần tử đầu tiên và an là phần tử cuối cùng của danh sách. Số phần tử của danh sách ta gọi là độ

dài của danh sách.
Một tính chất quan trọng của danh sách là các phần tử của danh sách có thứ tự tuyến tính theo vị
trí [position] xuất hiện của các phần tử. Ta nói a i đứng trước ai+1, với i từ 1 đến n-1; Tương tự ta
nói ailà phần tử đứng sau ai-1, với i từ 2 đến n. Ta cũng nói ai là phần tử tại vị trí thứ i, hay phần
tử thứ i của danh sách.
Ví dụ: Tập hợp họ tên các sinh viên của lớp TINHOC 28 được liệt kê trên giấy như sau:
1. Nguyễn Trung Cang
2. Nguyễn Ngọc Chương
3. Lê Thị Lệ Sương
4. Trịnh Vũ Thành
5. Nguyễn Phú Vĩnh
là một danh sách. Danh sách này gồm có 5 phần tử, mỗi phần tử có một vị trí trong danh sách theo
thứ tự xuất hiện của nó.
3.1.2. Các phép toán trên danh sách.
Để thiết lập kiểu dữ liệu trừu tượng danh sách [hay ngắn gọn là danh sách] ta phải định nghĩa
các phép toán trên danh sách. Và như chúng ta sẽ thấy trong toàn bộ giáo trình, không có một tập
hợp các phép toán nào thích hợp cho mọi ứng dụng [application]. Vì vậy ở đây ta sẽ định nghĩa
một số phép toán cơ bản nhất trên danh sách. Để thuận tiện cho việc định nghĩa ta giả sử rằng
danh sách gồm các phần tử có kiểu là kiểu phần tử [elementType]; vị trí của các phần tử trong
danh sách có kiểu là kiểu vị trí và vị trí sau phần tử cuối cùng trong danh sách L là ENDLIST[L].
Cần nhấn mạnh rằng khái niệm vị trí [position] là do ta định nghĩa, nó không phải là giá trị của
các phần tử trong danh sách. Vị trí có thể là đồng nhất với vị trí lưu trữ phần tử hoặc không.
Các phép toán được định nghĩa trên danh sách là:
INSERT_LIST[x,p,L]: xen phần tử x [ kiểu ElementType ] tại vị trí p [kiểu position] trong
danh sách L. Tức là nếu danh sách là a 1, a2, . , ap-1, ap ,. . , an thì sau khi xen ta có kết quả a1, a2,
. . ., ap-1, x, ap, . . . , an. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được xác
định.
Phụ lục 03
QT KKT 03/ 03


Trang 2/44


LOCATE[x,L] thực hiện việc định vị phần tử có nội dung x đầu tiên trong danh sách L. Locate
trả kết quả là vị trí [kiểu position] của phần tử x trong danh sách. Nếu x không có trong danh sách
thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST[L].
RETRIEVE[p,L] lấy giá trị của phần tử ở vị trí p [kiểu position] của danh sách L; nếu vị trí p
không có trong danh sách thì kết quả không xác định [có thể thông báo lỗi].
DELETE_LIST[p,L] chương trình con thực hiện việc xoá phần tử ở vị trí p [kiểu position] của
danh sách. Nếu vị trí p không có trong danh sách thì phép toán không được định nghĩa và danh
sách L sẽ không thay đổi
NEXT[p,L] cho kết quả là vị trí của phần tử [kiểu position] đi sau phần tử p; nếu p là phần tử
cuối cùng trong danh sách L thì NEXT[p,L] cho kết quả là ENDLIST[L]. Next không xác định
nếu p không phải là vị trí của một phần tử trong danh sách.
PREVIOUS[p,L] cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Nếu p
là phần tử đầu tiên trong danh sách thì Previous[p,L] không xác định. Previous cũng không xác
định trong trường hợp p không phải là vị trí của phần tử nào trong danh sách.
FIRST[L] cho kết quả là vị trí của phần tử đầu tiên trong danh sách. Nếu danh sách rỗng thì
ENDLIST[L] được trả về.
EMPTY_LIST[L] cho kết quả TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE.
MAKENULL_LIST[L] khởi tạo một danh sách L rỗng.
Trong thiết kế các giải thuật sau này chúng ta dùng các phép toán trừu tượng đã được định
nghĩa ở đây như là các phép toán nguyên thủy.
Muốn thêm phần tử vào đầu hay cuối danh sách ta gọi phép toán nào và gọi phép toán đó
như thế nào?
Ví dụ: Dùng các phép toán trừu tượng trên danh sách, viết một chương trình con nhận một
tham số là danh sách rồi sắp xếp danh sách theo thứ tự tăng dần [giả sử các phần tử trong danh
sách thuộc kiểu có thứ tự].
Giả sử SWAP[p,q] thực hiện việc đổi chỗ hai phần tử tại vị trí p và q trong danh sách, chương
trình con sắp xếp được viết như sau:

void SORT[LIST L]{
Position p,q;
//kiểu vị trí của các phần tử trong danh sách
p= FIRST[L];
//vị trí phần tử đầu tiên trong danh sách
while [p!=ENDLIST[L]]{

q=NEXT[p,L];
//vị trí phần tử đứng ngay sau phần tử p
while [q!=ENDLIST[L]]{
if [RETRIEVE[p,L] > RETRIEVE[q,L]]

swap[p,q]; // dịch chuyển nội dung phần tử
q=NEXT[q,L];
}
p=NEXT[p,L];
Phụ lục 03
QT KKT 03/ 03

Trang 3/44


}
}
Tuy nhiên, cần phải nhấn mạnh rằng, đây là các phép toán trừu tượng do chúng ta định nghĩa,
nó chưa được cài đặt trong các ngôn ngữ lập trình. Do đó để cài đặt giải thuật thành một chương
trình chạy được thì ta cũng phải cài đặt các phép toán thành các chương trình con trong chương
trình. Hơn nữa, trong khi cài đặt cụ thể, một số tham số hình thức trong các phép toán trừu tượng
không đóng vai trò gì trong chương trình con cài đặt chúng, do vậy ta có thể bỏ qua nó trong danh
sách tham số của chương trình con. Ví dụ: phép toán trừu tượng INSERT_LIST[x,p,L] có 3 tham

số hình thức: phần tử muốn thêm x, vị trí thêm vào p và danh sách được thêm vào L. Nhưng khi
cài đặt danh sách bằng con trỏ [danh sách liên kết đơn], tham số L là không cần thiết vì với cấu
trúc này chỉ có con trỏ tại vị trí p phải thay đổi để nối kết với ô chứa phần tử mới. Trong bài giảng
này, ta vẫn giữ đúng những tham số trong cách cài đặt để làm cho chương trình đồng nhất và trong
suốt đối với các phương pháp cài đặt của cùng một kiểu dữ liệu trừu tượng.
3.1.3. Cài đặt danh sách.
3.1.3.1. Cài đặt danh sách bằng mảng [danh sách đặc].
Ta có thể cài đặt danh sách bằng mảng như sau: dùng một mảng để lưu giữ liên tiếp các
phần tử của danh sách từ vị trí đầu tiên của mảng. Với cách cài đặt này, dĩ nhiên, ta phải ước
lượng số phần tử của danh sách để khai báo số phần tử của mảng cho thích hợp. Dễ thấy rằng số
phần tử của mảng phải được khai báo không ít hơn số phần tử của danh sách. Nói chung là mảng
còn thừa một số chỗ trống. Mặt khác ta phải lưu giữ độ dài hiện tại của danh sách, độ dài này cho
biết danh sách có bao nhiêu phần tử và cho biết phần nào của mảng còn trống như trong hình
3.1.1. Ta định nghĩa vị trí của một phần tử trong danh sách là chỉ số của mảng tại vị trí lưu trữ
phần tử đó + 1[vì phần tử đầu tiên trong mảng là chỉ số 0].

Hình 3.1.1. Cài đặt danh sách bằng mảng
Với hình ảnh minh họa trên, ta cần các khai báo cần thiết là
#define MaxLength ...

//Số nguyên thích hợp để chỉ độ dài của danh sách
typedef ... ElementType;//kiểu của phần tử trong danh sách
typedef int Position; //kiểu vị trí cuả các phần tử
typedef struct {

ElementType Elements[MaxLength];
//mảng chứa các phần tử của danh sách
Phụ lục 03
QT KKT 03/ 03


Trang 4/44


Position Last; //giữ độ dài danh sách
} List;
Trên đây là sự biểu diễn kiểu dữ liệu trừu trượng danh sách bằng cấu trúc dữ liệu mảng. Phần
tiếp theo là cài đặt các phép toán cơ bản trên danh sách.
Khởi tạo danh sách rỗng
Danh sách rỗng là một danh sách không chứa bất kỳ một phần tử nào [hay độ dài danh sách
bằng 0]. Theo cách khai báo trên, trường Last chỉ vị trí của phần tử cuối cùng trong danh sách và
đó cũng độ dài hiện tại của danh sách, vì vậy để khởi tạo danh sách rỗng ta chỉ việc gán giá trị
trường Last này bằng 0.
void MakeNull_List[List *L]
{ L->Last=0; }
Kiểm tra danh sách rỗng
Danh sách rỗng là một danh sách mà độ dài của nó bằng 0.
int Empty_List[List L]{
return L.Last==0;

}
Xen một phần tử vào danh sách
Khi xen phần tử có nội dung x vào tại vị trí p của danh sách L thì sẽ xuất hiện các khả năng sau:
Mảng đầy: mọi phần tử của mảng đều chứa phần tử của danh sách, tức là phần tử cuối cùng
của danh sách nằm ở vị trí cuối cùng trong mảng. Nói cách khác, độ dài của danh sách bằng chỉ số
tối đa của mảng; Khi đó không còn chỗ cho phần tử mới, vì vậy việc xen là không thể thực hiện
được, chương trình con gặp lỗi.
Ngược lại ta tiếp tục xét:
Nếu p không hợp lệ [p>last+1 hoặc pLast==MaxLength]
printf["Danh sach day"];
else if [[PL->Last+1]]
printf["Vi tri khong hop le"];
else{

Position Q;
Phụ lục 03
QT KKT 03/ 03

Trang 5/44


/*Dời các phần tử từ vị trí p [chỉ số trong mảng là p-1] đến
cuối danh sách sang phải 1 vị trí*/
for[Q=[L->Last-1]+1;Q>P-1;Q--]

L->Elements[Q]=L->Elements[Q-1];
//Đưa x vào vị trí p
L->Elements[P-1]=X;
//Tăng độ dài danh sách lên 1
L->Last++;
}

}
Xóa phần tử ra khỏi danh sách
Xoá một phần tử ở vị trí p ra khỏi danh sách L ta làm công việc ngược lại với xen.
Trước tiên ta kiểm tra vị trí phần tử cần xóa xem có hợp lệ hay chưa. Nếu p>L.last hoặc pLast]]
printf["Vi tri khong hop le"];
else if [EmptyList[*L]]
printf["Danh sach rong!"];
else{

Position Q;
/*Dời các phần tử từ vị trí p+1 [chỉ số trong mảng
là p] đến cuối danh sách sang trái 1 vị trí*/
for[Q=P-1;QLast-1;Q++]

L->Elements[Q]=L->Elements[Q+1];
L->Last--;
}
}
Định vị một phần tử trong danh sách
Để định vị vị trí phần tử đầu tiên có nội dung x trong danh sách L, ta tiến hành dò tìm từ đầu
danh sách. Nếu tìm thấy x thì vị trí của phần tử tìm thấy được trả về, nếu không tìm thấy thì hàm
trả về vị trí sau vị trí của phần tử cuối cùng trong danh sách, tức là ENDLIST[L] [ENDLIST[L]=
L.Last+1]. Trong trường hợp có nhiều phần tử cùng giá trị x trong danh sách thì vị trí của phần tử
được tìm thấy đầu tiên được trả về.
Position Locate[ElementType X, List L]{

Position P;
int Found = 0;
Phụ lục 03
QT KKT 03/ 03

Trang 6/44


P = First[L]; //vị trí phần tử đầu tiên
/*trong khi chưa tìm thấy và chưa kết thúc
danh sách thì xét phần tử kế tiếp*/
while [[P != EndList[L]] && [Found == 0]]
if [Retrieve[P,L] == X] Found = 1;
else P = Next[P, L];
return P;

}
Lưu ý : Các phép toán sau phải thiết kế trước Locate
o First[L]=1
o Retrieve[P,L]=L.Elements[P-1]
o EndList[L]=L.Last+1
o Next[P,L]=P+1

Hãy giải thích tại sao nội dung phần tử tại vị trí P trên danh sách L là L.Elements[P-1]?
Ví dụ : Vận dụng các phép toán trên danh sách đặc để viết chương trình nhập vào một
danh sách các số nguyên và hiển thị danh sách vừa nhập ra màn hình. Thêm phần tử có nội
dung x vào danh sách tại ví trí p [trong đó x và p được nhập từ bàn phím]. Xóa phần tử đầu
tiên có nội dung x [nhập từ bàn phím] ra khỏi danh sách.
Hướng giải quyết :
Giả sử ta đã cài đặt đầy đủ các phép toán cơ bản trên danh sách. Để thực hiện yêu cầu như trên,

ta cần thiết kế thêm một số chương trình con sau :
- Nhập danh sách từ bàn phím [READ_LIST[L]] [Phép toán này chưa có trong kiểu danh
sách]
- Hiển thị danh sách ra màn hình [in danh sách] [PRINT_LIST[L]] [Phép toán này chưa có
trong kiểu danh sách].
Thực ra thì chúng ta chỉ cần sử dụng các phép toán MakeNull_List, Insert_List, Delete_List,
Locate và các chương trình con Read_List, Print_List vừa nói trên là có thể giải quyết được bài
toán. Để đáp ứng yêu cầu đặt ra, ta viết chương trình chính để nối kết những chương trình con lại
với nhau như sau:
int main[]
{
List L;
ElementType X;
Position P;
MakeNull_List[&L]; //Khởi tạo danh sách rỗng
Read_List[&L];
printf["Danh sach vua nhap: "];
Print_List[L]; // In danh sach len man hinh
printf["Phan tu can them: "];scanf["%d",&X];
printf["Vi tri can them: "];scanf["%d",&P];
Phụ lục 03
QT KKT 03/ 03

Trang 7/44


Insert_List[X,P,&L];
printf["Danh sach sau khi them phan tu la: "];
PrintList[L];
printf["Noi dung phan tu can xoa: "];scanf["%d",&X];

P=Locate[X,L];
Delete_List[P,&L];
printf["Danh sach sau khi xoa %d la: ",X];
Print_List[L];
return 0;
}
3.1.3.2. Cài đặt danh sách bằng con trỏ [ danh sách liên kết]
Cách khác để cài đặt danh sách là dùng con trỏ để liên kết các ô chứa các phần tử. Trong cách
cài đặt này các phần tử của danh sách được lưu trữ trong các ô, mỗi ô có thể chỉ đến ô chứa phần
tử kế tiếp trong danh sách. Có thể hình dung cơ chế này qua ví dụ sau:
Giả sử 1 lớp có 4 bạn: Đông, Tây, Nam, Bắc có địa chỉ lần lượt là d,t,n,b. Giả sử: Đông có địa
chỉ của Nam, Tây không có địa chỉ của bạn nào, Bắc giữ địa chỉ của Đông, Nam có địa chỉ của
Tây [xem hình 3.1.2].

Hình 3.1.2. Danh sách liên kết
Như vậy, nếu ta xét thứ tự các phần tử bằng cơ chế chỉ đến này thì ta có một danh sách: Bắc,
Đông, Nam, Tây. Hơn nữa để có danh sách này thì ta cần và chỉ cần giữ địa chỉ của Bắc.
Trong cài đặt, để một ô có thể chỉ đến ô khác ta cài đặt mỗi ô là một mẩu tin [record, struct]
có hai trường: trường Element giữ giá trị của các phần tử trong danh sách; trường next là một con
trỏ giữ địa chỉ của ô kế tiếp.Trường next của phần tử cuối trong danh sách chỉ đến một giá trị đặc
biệt là NULL. Cấu trúc như vậy gọi là danh sách cài đặt bằng con trỏ hay danh sách liên kết đơn
hay ngắn gọn là danh sách liên kết.

Hình 3.1.3. Danh sách liên kết đơn
Phụ lục 03
QT KKT 03/ 03

Trang 8/44



Để quản lý danh sách ta chỉ cần một biến giữ địa chỉ ô chứa phần tử đầu tiên của danh sách, tức
là một con trỏ trỏ đến phần tử đầu tiên trong danh sách. Biến này gọi là chỉ điểm đầu danh sách
[Header] . Để đơn giản hóa vấn đề, trong chi tiết cài đặt, Header là một biến cùng kiểu với các ô
chứa các phần tử của danh sách và nó có thể được cấp phát ô nhớ y như một ô chứa phần tử của
danh sách [hình II.3]. Tuy nhiên Header là một ô đặc biệt nên nó không chứa phần tử nào của
danh sách, trường dữ liệu của ô này là rỗng, chỉ có trường con trỏ Next trỏ tới ô chứa phần tử đầu
tiên thật sự của danh sách. Nếu danh sách rỗng thì Header->next trỏ tới NULL. Việc cấp phát ô nhớ
cho Header như là một ô chứa dữ liệu bình thường nhằm tăng tính đơn giản của các giải thuật
thêm, xoá các phần tử trong danh sách.
Ở đây ta cần phân biệt rõ giá trị của một phần tử và vị trí [position] của nó trong cấu trúc trên.
Ví dụ giá trị của phần tử đầu tiên của danh sách trong hình 3.1.4 là a1, Trong khi vị trí của nó là
địa chỉ của ô chứa nó, tức là giá trị nằm ở trường next của ô Header. Giá trị và vị trí của các phần
tử của danh sách trong hình 3.1.4 như sau:

Hình 3.1.4. Vị trí các phần tử trong danh sách liên kết
Như đã thấy trong bảng trên, vị trí của phần tử thứ i là [i-1], như vậy để biết được vị trí của
phần tử thứ i ta phải truy xuất vào ô thứ [i-1]. Khi thêm hoặc xoá một phần tử trong danh sách liên
kết tại vị trí p, ta phải cập nhật lại con trỏ trỏ tới vị trí này, tức là cập nhật lại [p-1]. Nói cách khác,
để thao tác vào vị trí p ta phải biết con trỏ trỏ vào p mà con trỏ này chính là [p-1]. Do đó ta định
nghĩa p-1 như là vị trí của p. Có thể nói nôm na rằng vị trí của phần tử a i là địa chỉ của ô đứng
ngay phía trước ô chứa ai. Hay chính xác hơn, ta nói, vị trí của phần tử thứ i là con trỏ trỏ tới ô có
trường next trỏ tới ô chứa phần tử a i Như vậy vị trí của phần tử thứ 1 là con trỏ trỏ đến Header, vị
trí phần tử thứ 2 là con trỏ trỏ ô chứa phần tử a 1, vị trí của phần tử thứ 3 là con trỏ trỏ ô a 2, ..., vị
trí phần tử thứ n là con trỏ trỏ ô chứa a n-1. Vậy vị trí sau phần tử cuối trong danh sách, tức là
ENDLIST, chính là con trỏ trỏ ô chứa phần tử an [xem hình II.3].
Theo định nghĩa này ta có, nếu p là vị trí của phần tử thứ p trong danh sách thì giá trị của phần
tử ở vị trí p này nằm trong trường element của ô được trỏ bởi p->next. Nói cách khác p->next>element chứa nội dung của phần tử ở vị trí p trong danh sách.
Các khai báo cần thiết là
typedef ... ElementType; //kiểu của phần tử trong danh sách
Phụ lục 03

QT KKT 03/ 03

Trang 9/44


typedef struct Node{

ElementType Element;//Chứa nội dung của phần tử
Node* Next; /*con trỏ chỉ đến phần tử kế tiếp trong danh
sách*/
};
typedef Node* Position; // Kiểu vị trí
typedef Position List;

Tạo danh sách rỗng
Như đã nói ở phần trên, ta dùng Header như là một biến con trỏ có kiểu giống như kiểu của một
ô chứa một phần tử của danh sách. Tuy nhiên trường Element của Header không bao giờ được
dùng, chỉ có trường Next dùng để trỏ tới ô chứa phần tử đầu tiên của danh sách. Vậy nếu như
danh sách rỗng thì trường ô Header vẫn phải tồn tại và ô này có trường next chỉ đến NULL [do
không có một phần tử nào]. Vì vậy khi khởi tạo danh sách rỗng, ta phải cấp phát ô nhớ cho
HEADER và cho con trỏ trong trường next của nó trỏ tới NULL.
void MakeNull_List[List *Header]{
[*Header]=[Node*]malloc[sizeof[Node]];
[*Header]->Next= NULL;
}
Kiểm tra một danh sách rỗng
Danh sách rỗng nếu như trường next trong ô Header trỏ tới NULL.
int Empty_List[List L]{
return [L->Next==NULL];


}
Xen một phần tử vào danh sách :
Xen một phần tử có giá trị x vào danh sách L tại vị trí p ta phải cấp phát một ô mới để lưu trữ
phần tử mới này và nối kết lại các con trỏ để đưa ô mới này vào vị trí p. Sơ đồ nối kết và thứ tự
các thao tác được cho trong hình 3.1.5.

Hình 3.1.5. Thêm một phần tử vào danh sách tại vị trí P.
void Insert_List[ElementType X, Position P, List *L]{

Position T;
T=[Node*]malloc[sizeof[Node]];
T->Element=X;
Phụ lục 03
QT KKT 03/ 03

Trang 10/44


T->Next=P->Next;
P->Next=T;
}
Xóa phần tử ra khỏi danh sách

Hình 3.1.6. Xóa phần tử tại vị trí P.
Tương tự như khi xen một phần tử vào danh sách liên kết, muốn xóa một phần tử khỏi danh
sách ta cần biết vị trí p của phần tử muốn xóa trong danh sách L. Nối kết lại các con trỏ bằng cách
cho p trỏ tới phần tử đứng sau phần tử thứ p. Trong các ngôn ngữ lập trình không có cơ chế thu
hồi vùng nhớ tự động như ngôn ngữ Pascal, C thì ta phải thu hồi vùng nhớ của ô bị xóa một các
tường minh trong giải thuật. Tuy nhiên vì tính đơn giản của giải thuật cho nên đôi khi chúng ta
không đề cập đến việc thu hồi vùng nhớ cho các ô bị xoá. Chi tiết và trình tự các thao tác để xoá

một phần tử trong danh sách liên kết như trong hình II.5. Chương trình con có thể được cài đặt
như sau:
void Delete_List[Position P, List *L]{
Position T;
if [P->Next!=NULL]{

T=P->Next; /*/giữ ô chứa phần tử bị xoá
để thu hồi vùng nhớ*/
P->Next=T->Next; /*nối kết con trỏ trỏ tới
phần tử thứ p+1*/
free[T]; //thu hồi vùng nhớ
}
}
Định vị một phần tử trong danh sách liên kết
Để định vị phần tử x trong danh sách L ta tiến hành tìm từ đầu danh sách [ô header] nếu tìm
thấy thì vị trí của phần tử đầu tiên được tìm thấy sẽ được trả về nếu không thì ENDLIST[L] được
trả về. Nếu x có trong sách sách và hàm Locate trả về vị trí p mà trong đó ta có x = p->next>element.
Position Locate[ElementType X, List L]{
Position P;
int Found = 0;

P = L;
Phụ lục 03
QT KKT 03/ 03

Trang 11/44


while [[P->Next != NULL] && [Found == 0]]
if [P->Next->Element == X] Found = 1;

else P = P->Next;
return P;

}
Thực chất, khi gọi hàm Locate ở trên ta có thể truyền giá trị cho L là bất kỳ giá trị nào. Nếu L là
Header thì chương trình con sẽ tìm x từ đầu danh sách. Nếu L là một vị trí p bất kỳ trong danh
sách thì chương trình con Locate sẽ tiến hành định vị phần tử x từ vị trí p.
Xác định nội dung phần tử:
Nội dung phần tử đang lưu trữ tại vị trí p trong danh sách L là p->next->Element Do đó, hàm sẽ
trả về giá trị p->next->element nếu phần tử có tồn tại, ngược lại phần tử không tồn tại [p>next=NULL] thì hàm không xác định
ElementType Retrieve[Position P, List L]{
if [P->Next!=NULL]
return P->Next->Element;

}
Hãy thiết kế hàm Locate bằng cách sử dụng các phép toán trừu tượng cơ bản trên danh sách?
3.2. Ngăn xếp [Stack]
3.2.1. Định nghĩa ngăn xếp
Ngăn xếp [Stack] là một danh sách mà ta giới hạn việc thêm vào hoặc loại bỏ một phần tử
chỉ thực hiện tại một đầu của danh sách, đầu này gọi là đỉnh [TOP] của ngăn xếp.
Ta có thể xem hình ảnh trực quan của ngăn xếp bằng một chồng đĩa đặt trên bàn. Muốn
thêm vào chồng đó 1 đĩa ta để đĩa mới trên đỉnh chồng, muốn lấy các đĩa ra khỏi chồng ta cũng
phải lấy đĩa trên trước. Như vậy ngăn xếp là một cấu trúc có tính chất vào sau - ra trước hay
vào trước ra sau [LIFO [last in - first out ] hay FILO [first in last out]].
3.2.2. Các phép toán trên ngăn xếp
MAKENULL_STACK[S]: tạo một ngăn xếp rỗng.
TOP[S] xem như một hàm trả về phần tử tại đỉnh ngăn xếp. Nếu ngăn xếp rỗng thì hàm không
xác định. Lưu ý rằng ở đây ta dùng từ "hàm" để ngụ ý là TOP[S] có trả kết quả ra. Nó có thể
không đồng nhất với khái niệm hàm trong ngôn ngữ lập trình như C chẳng hạn, vì có thể kiểu
phần tử không thể là kiểu kết quả ra của hàm trong C.

POP[S] chương trình con xoá một phần tử tại đỉnh ngăn xếp.
PUSH[x,S] chương trình con thêm một phần tử x vào đầu ngăn xếp.
EMPTY_STACK[S] kiểm tra ngăn xếp rỗng. Hàm cho kết quả 1 [true] nếu ngăn xếp rỗng và
0 [false] trong trường hợp ngược lại.
Như đã nói từ trước, khi thiết kế giải thuật ta có thể dùng các phép toán trừu tượng như là các
"nguyên thủy" mà không cần phải định nghĩa lại hay giải thích thêm. Tuy nhiên để giải thuật đó
thành chương trình chạy được thì ta phải chọn một cấu trúc dữ liệu hợp lí để cài đặt các "nguyên
thủy" này.
Phụ lục 03
QT KKT 03/ 03

Trang 12/44


Ví dụ: Viết chương trình con Edit nhận một chuỗi kí tự từ bàn phím cho đến khi gặp kí tự @ thì
kết thúc việc nhập và in kết quả theo thứ tự ngược lại.
void Edit[]
{
Stack S;
char c;
MakeNull_Stack[&S];
do{// Lưu từng ký tự vào ngăn xếp
c=getche[];
Push[c,&S];
}while [c!='@'];
printf["\nChuoi theo thu tu nguoc lai\n"];
// In ngan xep
while [!Empty_Stack[S]]{
printf["%c\n",Top[S]];
Pop[&S];

}
}
3.3. Cài đặt ngăn xếp.
3.3.1. Cài đặt ngăn xếp bằng danh sách.
Do ngăn xếp là một danh sách đặc biệt nên ta có thể sử dụng kiểu dữ liệu trừu tượng danh sách
để biểu diễn cách cài đặt nó. Như vậy, ta có thể khai báo ngăn xếp như sau:
typedef List Stack;
Khi chúng ta đã dùng danh sách để biểu diễn cho ngăn xếp thì ta nên sử dụng các phép toán
trên danh sách để cài đặt các phép toán trên ngăn xếp. Sau đây là phần cài đặt ngăn xếp bằng danh
sách.
Tạo ngăn xếp rỗng:
void MakeNull_Stack[Stack *S]{

MakeNull_List[S];
}
Kiểm tra ngăn xếp rỗng:
int Empty_Stack[Stack S]{
return Empty_List[S];

}
Thêm phần tử vào ngăn xếp
void Push[Elementtype X, Stack *S]{

Insert_List [x, First [*S], &S];
}
Xóa phần tử ra khỏi ngăn xếp
Phụ lục 03
QT KKT 03/ 03

Trang 13/44



void Pop [Stack *S]{

Delete_List [First [*S], &S];
}
Tuy nhiên để tăng tính hiệu quả của ngăn xếp ta có thể cài đặt ngăn xếp trực tiếp từ các cấu trúc
dữ liệu như các phần sau.
3.3.2. Cài đặt bằng mảng.
Dùng một mảng để lưu trữ liên tiếp các phần tử của ngăn xếp. Các phần tử đưa vào ngăn xếp bắt
đầu từ vị trí có chỉ số cao nhất của mảng, xem hình II.9. Ta còn phải dùng một biến số nguyên
[TOP_IDX] giữ chỉ số của phần tử tại đỉnh ngăn xếp.

Hình 3.2.1. Cài đặt ngăn xếp bằng mảng
Khai báo ngăn xếp
#define MaxLength ... //độ dài của mảng
typedef ... ElementType; //kiểu các phần tử trong ngăn xếp
typedef struct {

ElementType Elements[MaxLength];
//Lưu nội dung của các phần tử
int Top_idx; //giữ vị trí đỉnh ngăn xếp

} Stack;
Tạo ngăn xếp rỗng
Ngăn xếp rỗng là ngăn xếp không chứa bất kỳ một phần tử nào, do đó đỉnh của ngăn xếp không
được phép chỉ đến bất kỳ vị trí nào trong mảng. Để tiện cho quá trình thêm và xóa phần tử ra khỏi
ngăn xếp, khi tạo ngăn xếp rỗng ta cho đỉnh ngăn xếp nằm ở vị trí maxlength.
void MakeNull_Stack[Stack *S]
{ S->Top_idx=MaxLength; }

Kiểm tra ngăn xếp rỗng
int Empty_Stack[Stack S]
Phụ lục 03
QT KKT 03/ 03

Trang 14/44


{ return S.Top_idx==MaxLength; }
Kiểm tra ngăn xếp đầy
int Full_Stack[Stack S]{
return S.Top_idx==0;

}
Lấy nội dung phần tử tại đỉnh của ngăn xếp :
Hàm trả về nội dung phần tử tại đỉnh của ngăn xếp khi ngăn xếp không rỗng. Nếu ngăn xếp
rỗng thì hàm hiển thị câu thông báo lỗi.
ElementType Top[Stack S]{
if [!Empty_Stack[S]]
return S.Elements[S.Top_idx];
else printf["Loi! Ngan xep rong"];

}
Chương trình con xóa phần tử ra khỏi ngăn xếp
Phần tử được xóa ra khỏi ngăn xếp là tại đỉnh của ngăn xếp. Do đó, khi xóa ta chỉ cần dịch
chuyển đỉnh của ngăn xếp xuống 1 vị trí [top_idx tăng 1 đơn vị ]
void Pop[Stack *S]{
if [!Empty_Stack[*S]]

S->Top_idx=S->Top_idx+1;

else printf["Loi! Ngan xep rong!"];

}
Chương trình con thêm phần tử vào ngăn xếp :
Khi thêm phần tử có nội dung x [kiểu ElementType] vào ngăn xếp S [kiểu Stack], trước tiên ta
phải kiểm tra xem ngăn xếp có còn chỗ trống để lưu trữ phần tử mới không. Nếu không còn chỗ
trống [ngăn xếp đầy] thì báo lỗi; Ngược lại, dịch chuyển Top_idx lên trên 1 vị trí và đặt x vào tại
vị trí đỉnh mới.
void Push[ElementType X, Stack *S]{
if [Full_Stack[*S]]
printf["Loi! Ngan xep day!"];
else{

S->Top_idx=S->Top_idx-1;
S->Elements[S->Top_idx]=X;
}
}
Tất nhiên ta cũng có thể cài đặt ngăn xếp bằng con trỏ, trường hợp này xin dành cho bạn đọc xem
như một bài tập nhỏ.
3.2.4. Ứng dụng ngăn xếp loại bỏ đệ quy của chương trình [Sinh viên tự nghiên cứu].
3.3. Hàng đợi [Queue]
Phụ lục 03
QT KKT 03/ 03

Trang 15/44


3.3.1. Định nghĩa hàng đợi
Hàng đợi, hay ngắn gọn là hàng [queue] cũng là một danh sách đặc biệt mà phép thêm vào chỉ
thực hiện tại một đầu của danh sách, gọi là cuối hàng [REAR], còn phép loại bỏ thì thực hiện ở

đầu kia của danh sách, gọi là đầu hàng [FRONT].
Xếp hàng mua vé xem phim là một hình ảnh trực quan của khái niệm trên, người mới đến thêm
vào cuối hàng còn người ở đầu hàng mua vé và ra khỏi hang, vì vậy hàng còn được gọi là cấu trúc
FIFO [first in - first out] hay "vào trước - ra trước".
3.3.2. Các phép toán cơ bản trên hàng đợi.
MAKENULL_QUEUE[Q] khởi tạo một hàng rỗng.
FRONT[Q] hàm trả về phần tử đầu tiên của hàng Q.
ENQUEUE[x,Q] thêm phần tử x vào cuối hàng Q.
DEQUEUE[Q] xoá phần tử tại đầu của hàng Q.
EMPTY_QUEUE[Q] hàm kiểm tra hàng rỗng.
FULL_QUEUE[Q] kiểm tra hàng đầy.

3.3.3. Cài đặt hàng đợi.
Như đã trình bày trong phần ngăn xếp, ta hoàn toàn có thể dùng danh sách để biểu diễn cho
một hàng và dùng các phép toán đã được cài đặt của danh sách để cài đặt các phép toán trên hàng.
Tuy nhiên làm như vậy có khi sẽ không hiệu quả, chẳng hạn dùng danh sách cài đặt bằng mảng ta
thấy lời gọi INSERT_LIST[x,ENDLIST[Q],Q] tốn một hằng thời gian trong khi lời gọi
DELETE_LIST[FIRST[Q],Q] để xoá phần tử đầu hàng [phần tử ở vị trí 0 của mảng] ta phải tốn
thời gian tỉ lệ với số các phần tử trong hàng để thực hiện việc dời toàn bộ hàng lên một vị trí. Để
cài đặt hiệu quả hơn ta phải có một suy nghĩ khác dựa trên tính chất đặc biệt của phép thêm và
loại bỏ một phần tử trong hàng.
3.3.3.1. Cài đặt hàng bằng mảng.
Ta dùng một mảng để chứa các phần tử của hàng, khởi đầu phần tử đầu tiên của hàng được đưa
vào vị trí thứ 1 của mảng, phần tử thứ 2 vào vị trí thứ 2 của mảng... Giả sử hàng có n phần tử, ta
có front=0 và rear=n-1. Khi xoá một phần tử front tăng lên 1, khi thêm một phần tử rear tăng lên
1. Như vậy hàng có khuynh hướng đi xuống, đến một lúc nào đó ta không thể thêm vào hàng được
nữa [rear=maxlength-1] dù mảng còn nhiều chỗ trống [các vị trí trước front] trường hợp này ta gọi
là hàng bị tràn [xem hình II.11].Trong trường hợp toàn bộ mảng đã chứa các phần tử của hàng ta
gọi là hàng bị đầy.
Cách khắc phục hàng bị tràn

Dời toàn bộ hàng lên front -1 vị trí, cách này gọi là di chuyển tịnh tiến. Trong trường hợp
này ta luôn có frontFront=-1;
Q->Rear=-1;
}
Kiểm tra hàng rỗng
Trong quá trình làm việc ta có thể thêm và xóa các phần tử trong hàng. Rõ ràng, nếu ta có đưa
vào hàng một phần tử nào đó thì front>-1. Khi xoá một phần tử ta tăng front lên 1. Hàng rỗng nếu
front>rear. Hơn nữa khi mới khởi tạo hàng, tức là front = -1, thì hàng cũng rỗng. Tuy nhiên để
phép kiểm tra hàng rỗng đơn giản, ta sẽ làm một phép kiểm tra khi xoá một phần tử của hàng, nếu
phần tử bị xoá là phần tử duy nhất trong hàng thì ta đặt lại front=-1. Vậy hàng rỗng khi và chỉ khi
front =-1.
int Empty_Queue[Queue Q]{
return Q.Front==-1;
Phụ lục 03
QT KKT 03/ 03

Trang 17/44


}
Kiểm tra đầy
Hàng đầy nếu số phần tử hiện có trong hàng bằng số phần tử trong mảng.
int Full_Queue[Queue Q]{
return [Q.Rear-Q.Front+1]==MaxLength;

}
Xóa phần tử ra khỏi hàng
Khi xóa một phần tử đầu hàng ta chỉ cần cho front tăng lên 1. Nếu front > rear thì hàng thực

chất là hàng đã rỗng, nên ta sẽ khởi tạo lại hàng rỗng [tức là đặt lại giá trị front = rear =-1].
void DeQueue[Queue *Q]{
if [!Empty_Queue[*Q]]{

Q->Front=Q->Front+1;
if [Q->Front>Q->Rear] MakeNull_Queue[Q];

//Dat lai hang rong
}
else printf["Loi: Hang rong!"];

}
Thêm phần tử vào hàng
Một phần tử khi được thêm vào hàng sẽ nằm kế vị trí Rear cũ của hàng. Khi thêm một phần tử
vào hàng ta phải xét các trường hợp sau:
Nếu hàng đầy thì báo lỗi không thêm được nữa.
Nếu hàng chưa đầy ta phải xét xem hàng có bị tràn không. Nếu hàng bị tràn ta di chuyển tịnh
tiến rồi mới nối thêm phần tử mới vào đuôi hàng [ rear tăng lên 1]. Đặc biệt nếu thêm vào hàng
rỗng thì ta cho front=0 để front trỏ đúng phần tử đầu tiên của hàng.
void EnQueue[ElementType X,Queue *Q]{
if [!Full_Queue[*Q]]{
if [Empty_Queue[*Q]] Q->Front=0;
if [Q->Rear==MaxLength-1]{

//Di chuyen tinh tien ra truoc Front -1 vi tri
for[int i=Q->Front;iRear;i++]

Q->Elements[i-Q->Front]=Q->Elements[i];
//Xac dinh vi tri Rear moi
Q->Rear=MaxLength - Q->Front-1;

Q->Front=0;
}
//Tang Rear de luu noi dung moi
Q->Rear=Q->Rear+1;
Q->Element[Q->Rear]=X;
Phụ lục 03
QT KKT 03/ 03

Trang 18/44


}
else printf["Loi: Hang day!"];

}
3.3.3.2. Cài đặt hàng với mảng xoay vòng

Hình 3.3.2. Cài đặt hàng bằng mảng xoay vòng.
Với phương pháp này, khi hàng bị tràn, tức là rear=maxlength-1, nhưng chưa đầy, tức là
front>0, thì ta thêm phần tử mới vào vị trí 0 của mảng và cứ tiếp tục như vậy vì từ 0 đến front-1 là
các vị trí trống. Vì ta sử dụng mảng một cách xoay vòng như vậy nên phương pháp này gọi là
phương pháp dùng mảng xoay vòng.
Các phần khai báo cấu trúc dữ liệu, tạo hàng rỗng, kiểm tra hàng rỗng giống như phương pháp
di chuyển tịnh tiến.
Khai báo cần thiết
#define MaxLength ... //chiều dài tối đa của mảng
typedef ... ElementType;

//Kiểu dữ liệu của các phần tử trong hàng
typedef struct {


ElementType Elements[MaxLength];
//Lưu trữ nội dung các phần tử
int Front, Rear; //chỉ số đầu và đuôi hàng

} Queue;
Tạo hàng rỗng
Lúc này front và rear không trỏ đến vị trí hợp lệ nào trong mảng vậy ta có thể cho front và 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
Phụ lục 03
QT KKT 03/ 03

Trang 19/44


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 hàng
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;
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!"];
Phụ lục 03
QT KKT 03/ 03

Trang 20/44


}
3.3.3.3. 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 3.3.3. 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
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.
Phụ lục 03
QT KKT 03/ 03

Trang 21/44


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

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 hoặc 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ố.
3. Câu hỏi ôn tập:
4. Bài tập.
1. Viết khai báo và các chương trình con cài đặt danh sách bằng mảng. Dùng các chương trình con
này để viết:
a. Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trong danh sách
theo thứ tự nhập vào.
b. Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trong danh sách

theo thứ tự ngược với thứ tự nhập vào.
Phụ lục 03
QT KKT 03/ 03

Trang 22/44


c. Viết chương trình con in ra màn hình các phần tử trong danh sách theo thứ tự của nó trong danh
sách.
2. Tương tự như bài tập 1. nhưng cài đặt bằng con trỏ.
3. Viết chương trình con sắp xếp một danh sách chứa các số nguyên, trong các trường hợp:
a. Danh sách được cài đặt bằng mảng [danh sách đặc].
b. Danh sách được cài đặt bằng con trỏ [danh sách liên kết].
4. Viết chương trình con thêm một phần tử trong danh sách đã có thứ tự sao cho ta vẫn có một
danh sách có thứ tự bằng cách vận dụng các phép toán cơ bản trên danh sách
5. Viết chương trình con tìm kiếm và xóa một phần tử trong danh sách có thứ tự.
6. Viết chương trình con nhận vào từ bàn phím một dãy số nguyên, lưu trữ nó trong một danh sách
có thứ tự không giảm, theo cách sau: với mỗi phần tử được nhập vào chương trình con phải tìm vị
trí thích hợp để xen nó vào danh sách cho đúng thứ tự. Viết chương trình con trên cho trường hợp
danh sách được cài đặt bằng mảng và cài đặt bằng con trỏ và trong trường hợp tổng quát [dùng
các phép toán cơ bản trên danh sách]
7. Viết chương trình con loại bỏ các phần tử trùng nhau [giữ lại duy nhất 1 phần tử] trong một
danh sách có thứ tự không giãm, trong hai trường hợp: cài đặt bằng mảng và cài đặt bằng con trỏ.
8. Viết chương trình con nhận vào từ bàn phím một dãy số nguyên, lưu trữ nó trong một danh sách
có thứ tự tăng không có hai phần tử trùng nhau, theo cách sau: với mỗi phần tử được nhập vào
chương trình con phải tìm kiếm xem nó có trong danh sách chưa, nếu chưa có thì xen nó vào danh
sách cho đúng thứ tự. Viết chương trình con trên cho trường hợp danh sách được cài đặt bằng
mảng và cài đặt bằng con trỏ.
9. Viết chương trình con trộn hai danh sách liên kết chứa các số nguyên theo thứ tự tăng để được
một danh sách cũng có thứ tự tăng.

10. Viết chương trình con xoá khỏi danh sách lưu trữ các số nguyên các phần tử là số nguyên lẻ,
cũng trong hai trường hợp: cài đặt bằng mảng và bằng con trỏ.
11. Viết chương trình con tách một danh sách chứa các số nguyên thành hai danh sách: một danh
sách gồm các số chẵn còn cái kia chứa các số lẻ.
12. Đa thức P[x]= anxn+ an-1xn-1+... + a1x + a0 được lưu trữ trong máy tính dưới dạng một danh
sách liên kết mà mỗi phần tử của danh sách là một struct có ba trường lưu giữ hệ số, số mũ, và
trưòng NEXT trỏ đến phần tử kế tiếp. Chú ý cách lưu trữ đảm bảo thứ tự giảm dần theo số mũ của
từng hạng tử của đa thức.
Ví dụ: đa thức 5x4 - x + 3 được lưu trữ trong danh sách có 3 phần tử như sau:

a. Hãy viết chương trình thực hiện được sự lưu trữ này.

b. Dựa vào sự cài đặt ở trên, viết chương trình con thực hiện việc cộng hai đa thức.
c. Viết chương trình con lấy đạo hàm của đa thức.

Phụ lục 03
QT KKT 03/ 03

Trang 23/44


13. Để lưu trữ một số nguyên lớn, ta có thể dùng danh sách liên kết chứa các chữ số của nó. Hãy
tìm cách lưu trữ các chữ số của một số nguyên lớn theo ý tưởng trên sao cho việc cộng hai số
nguyên lớn là dễ dàng thực hiện. Viết chương trình con cộng hai số nguyên lớn.
14. Để tiện cho việc truy nhập vào danh sách, người ta tổ chức danh sách liên kết có dạng sau, gọi
là danh sách nối vòng:

Hãy viết khai báo và các chương trình con cơ bản để cài đặt một danh sách nối vòng.
15. Hãy cài đặt một ngăn xếp bằng cách dùng con trỏ.
a. Dùng ngăn xếp để viết chương trình con đổi một số thập phân sang số nhị phân.

b. Viết chương trình con/hàm kiểm tra một chuỗi dấu ngoặc đúng [chuỗi dấu ngoặc đúng là chuỗi
dấu mở đóng khớp nhau như trong biểu thức toán học].
16. Ta có thể cài đặt 2 ngăn xếp vào trong một mảng, gọi là ngăn xếp hai đầu hoạt động của hai
ngăn xếp này như sơ đồ sau:

Phụ lục 03
QT KKT 03/ 03

Trang 24/44


CHƯƠNG 4: KIỂU DỮ LIỆU CÂY
[TREES]
1. Tóm tắt nội dung:
Chương 4: trình bày cấu trúc dữ liệu dạng cây. Các khái niệm về cây, cách cài đặt các hàm và
các phép toán trên cây.
2. Nội dung học tập, nghiên cứu:
4.1. 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:
4.1.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 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 4.1. Cây mục lục một quyển 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 n i 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ừ n 1 đế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
Phụ lục 03
QT KKT 03/ 03

Trang 25/44