Đề tài Cấu trúc dữ liệu động
Dùng đề lưu trữ những ñối tượng dữ liệu ñược sử
dụng không có nhu cầu thay ñổi và kích thước, số
lượng . . .
• ðược khai báo tường minh
• Tồn tại trong phạm vi khái báo
• Kích thước không thay ñổi trong suốt quá trình sống
80 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2048 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Đề tài Cấu trúc dữ liệu động, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
13.1. Kiểu dữ liệu con trỏ
3.2. Danh sách liên kết (link list)
3.3. Danh sách liên kết ñơn
3.4. Sắp xếp danh sách
3.5. Các cấu trúc ñặc biệt của danh sách liên kết ñơn
3.5.1. Stack
3.5.2. Hàng ñợi (Queue)
3.6. Bài tập
Chương 3:
CẤU TRÚC DỮ LIỆU ðỘNG
Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net
23.1. Kiểu Dữ Liệu Con Trỏ
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.1.1. Biến không ñộng
3.1.2. Kiểu con trỏ
3.1.3. Biến ñộng
3
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Dùng ñề lưu trữ những ñối tượng dữ liệu ñược sử
dụng không có nhu cầu thay ñổi và kích thước, số
lượng . . .
• ðược khai báo tường minh
• Tồn tại trong phạm vi khái báo
• Kích thước không thay ñổi trong suốt quá trình sống
Ví dụ:
int a;
char b[10];
3.1.1. Biến không ñộng
4
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Kiểu con trỏ là kiểu cơ sở dùng lưu ñịa chỉ của một
ñối tượng dữ liệu khác.
Biến thuộc kiểu con trỏ là biến mà giá trị của nó là
ñịa chỉ một vùng nhớ của một biến hoặc là giá trị Null.
Tùy vào loại con trỏ gần (near pointer) hay con trỏ xa
(far pointer) mà kiểu dữ liệu con trỏ có các kích thước
khác nhau:
+ Con trỏ gần: 2 bytes
+ Con trỏ xa: 4 bytes
3.1.2. Kiểu con trỏ
5
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Cú pháp ñịnh nghĩa một kiểu con trỏ
typedef *;
Ví dụ:
typedef int *intpointer;
inpointer p;
Hay int *p;
Các thao tác:
- Khi 1 biến con trỏ p lưu ñịa chỉ của ñối tượng x, ta
nói “p trỏ x”
- Gán ñịa chỉ của biến cho con trỏ p:
p=&
-Truy xuất nội dung của ñối tượng do p trỏ ñến
*p
6
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
c. Ví dụ:
void main()
{
int a,b,*pa,*pb;
a=2;
b=3;
cout<<"\nGia tri cua bien a="<<a;
cout<<"\nGia tri cua bien b="<<b;
pa=&a;
pb=&b;
cout<<"\nDia chi cua o nho con tro pa tro toi="<<pa;
cout<<"\nDia chi cua o nho con tro pb tro toi="<<pb;
cout<<"\nNoi dung cua o nho con tro pa tro toi="<<*pa;
cout<<"\nNoi dung cua o nho con tro pb tro toi="<<*pb;
*pa=20; /* Thay doi giá tr cua *pa*/
*pb=20; /* Thay doi giá tri cua *pb*/
cout<<"\nGia tri moi cua bien a="<<a;
cout<<"\nGia tri moi cua bien b="<<b;
}
7
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Trong trường hợp, tại thời ñiểm biên dịch không thể xác
ñịnh trước kích thước chính xác của ñối tượng dữ
liệu(do chúng phụ thuộc vào ngữ cảnh). Các ñối tượng
dữ liệu này ñược khai báo như biến ñộng.
Biến ñộng là những biến thỏa:
3.1.3. Biến ñộng
Không ñược khai báo tường minh.
ðược cấp phát/giải phóng bộ nhớ khi yêu cầu.
Các biến này không theo qui tắc phạm vi.
Vùng nhớ của biến ñược cấp phát trong Heap.
Kích thước thay ñổi trong quá trình sống.
8
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Các thao tác trên biến ñộng:
Tạo biến ñộng và cho con trỏ p trỏ ñến:
Các hàm cấp phát bộ nhớ:
void* malloc(size); // trả về con trỏ chỉ ñến một vùng
// nhớ size byte vừa ñược cấp phát.
void* calloc(n,size);// trả về con trỏ chỉ ñến một vùng
// nhớ vừa ñược cấp phát gồm n
//phần tử,mỗi phần tử có kích
//thước size byte
new // hàm cấp phát bộ nhớ trong C++
9
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Hủy một biến ñộng do p chỉ ñến:
Hàm free(p): Huỷ vùng nhớ cấp phát bởi hàm
malloc do p trỏ tới
Hàm delete p: huỷ vùng nhớ cấp phát bởi hàm
new do p trỏ tới
10
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ:
//Trong C
int* p1, p2;
//Cấp phát vùng nhớ cho 1 biến ñộng kiểu int
p1 = (int*)malloc(sizeof(int));
//ðặt giá trị 5 cho biến ñộng p1
p1* = 5;
//Cấp phát biến ñộng kiểu mảng 10 p.tử kiểu int
p2 = (int*)calloc(10, sizeof(int));
//ðặt giá trị 0 cho phần tử thứ 4 của mảng p2
(p2+3)* = 0;
free(p1); free(p2);
//Trong C++
int* p;
p=new int;
delete p;
11
3.2. Danh Sách Liên Kết
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa
3.2.2. Các hình thức tổ chức danh sách
12
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.1. Ðịnh nghĩa
Kiểu danh sách Tx gồm các phần tử thuộc kiểu T
ñược ñịnh nghĩa là:
Tx =
trong ñó:
Vx = {tập hợp có thứ tự các phần tử kiểu T ñược
móc nối với nhau theo trình tự tuyến tính};
Ox = {Tạo danh sách; Tìm 1 phần tử trong danh
sách; Chèn một phần tử vào danh sách; Huỷ một phần
tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh
sách ...}
13
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví du: Hồ sơ các học sinh của một trường ñược tổ
chức thành danh sách gồm nhiều hồ sơ của từng học
sinh; số lượng học sinh trong trường có thể thay ñổi
do vậy cần có các thao tác thêm, hủy một hồ sơ; ñể
phục vụ công tác giáo vụ cần thực hiện các thao tác
tìm hồ sơ của một học sinh, in danh sách hồ sơ ...
14
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.2.2. Các hình thức tổ chức danh sách
Mối liên hệ giữa các phần tử ñược thể hiện ngầm:
Mỗi phần tử trong danh sách ñược ñặc trưng
bằng chỉ số.
Cặp phần tử xi, xi+1 ñược xác ñịnh là kế cận
Với hình thức tổ chức này, các phần tử của danh
sách phải lưu trữ liên tiếp trong bộ nhớ, công thức
xác ñịnh ñịa chỉ phần tử thứ I là.
Cách biểu diễn này cho phép truy xuất ngẫu nhiên,
ñơn giản và nhanh chóng ñến một phần tử bất kỳ
trong danh sách, nhưng lại hạn chế về mặt sử
dụng bộ nhớ bị lãng phí.
15
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Mối liên hệ giữa các phần tử thể hiện tường minh:
Mỗi phần tử ngoài các thông tin còn chứa một liên
kết (ñịa chỉ) ñến phần tử kế trong danh sách nên
còn ñược gọi là danh sách móc nối.
Với hình thức này các phần tử trong danh sách
không cần phải lưu trữ kế cận trong bộ nhớ nên
khắc phục ñược các khuyết ñiểm của hình thức tổ
chức mảng, nhưng việc truy xuất ñến một phần tử
ñòi hỏi phải thực hiện truy xuất qua một số phần tử
khác.
16
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Có các kiểu tổ chức liên kết giữa các phần tử.
Danh sách liên kết ñơn
Danh sách liên kết kép
Danh sách liên kết vòng
17
3.3. Danh Sách Liên Kết ðơn
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết
3.3.2. Các thao tác cơ bản trên danh sách ñơn
18
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết
Mỗi phần tử là một cấu trúc chứa 2 thông tin :
- Thành phần dữ liệu: Lưu trữ các thông tin về bản thân
phần tử .
- Thành phần mối liên kết: lưu trữ ñịa chỉ của phần tử
kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu
là phần tử cuối danh s ách.
Ta có ñịnh nghĩa tổng quát
struct tNode
{
DataType key;
tNode* pNext;
};
19
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ: Ðịnh nghĩa danh sách ñơn lưu trữ hồ sơ SV
struct tSinhVien
{
char Ten[30];
int MaSV;
};
typedef struct tSinhVien Sinhvien;
struct SinhvienNode
{
Sinhvien Info;
SinhvienNode* pNext;
};
typedef struct SinvienNode SVNode;
20
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Nếu biết ñược ñịa chỉ của phần tử ñầu tiên trong danh
sách ñơn thì có thể dựa vào thông tin pNext của nó ñể
truy xuất ñến phần tử thứ 2, thứ 3... ðể quản lý một
xâu ñơn chỉ cần biết ñịa chỉ phần tử ñầu xâu. Con trỏ
Head dùng ñể lưu trữ ñịa chỉ phần tử ñầu xâu
Khai báo:
NODE *pHead;
Ðể tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ
ñịa chỉ phần tử cuối xâu.
Khai báo:
NODE *pTail;
21
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.3.2. Các thao tác cơ bản trên danh sách ñơn
22
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Các ñịnh nghĩa, Khởi tạo danh sách LK ðơn:
struct tNode{
int key;
tNode *pnext;
};
typedef struct tNode *Node;
void Khoitao(List &L){
L.pHead=L.pTail=NULL;
}
struct tList{
node *pHead;
node *pTail;
};
typedef struct tList List;
23
© Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Các hàm con tạo Nút và Huỷ nút :
Node * Taonut(int x){
Node *p;
p=new Node;
p->key=x;
p->pNext=NULL;
return p;
}
void Huy(List &L){
Node *p;
while(L.pHead) {
p=L.pHead;
L.pHead=L.pHead->pNext;
delete p;
}
}
24
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Chèn một phần tử vào ñầu danh sách
Thu
t toán :
Bắt ñầu:
Nếu Danh sách rỗng Thì
B11 : Head = new_elelment;
B12 : Tail = Head;
Ngược lại
B21 : new_ele ->pNext = Head;
B22 : Head = new_ele ;
void Themdau(List &L, Node *p){
if(L.pHead==NULL)
L.pHead=L.pTail=p;
else {
p->pNext=L.pHead;
L.pHead=p;
}
}
25
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void Nhap(List &L)
{
int x;
Node *p;
Khoitao(L);
do
{
cout<<"Nhap gia tri vao danh sach (Nhap 0 ket thuc): ";
cin>>x;
if(x==0)
break;
p=Taonut(x);
Themdau(L,p);
}while(true);
}
26
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void Xuat(List L){
Node *p=L.pHead;
while(p)
{
coutKey<<" ";
p=p->pNext;
}
}
void main()
{
List L;
Nhap(L);
cout<<"\nDanh sach vua nhap: ";
Xuat(l);
Huy(L);
}
27
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Chèn một phần tử vào cuối danh sách
Thu
t toán :
Bắt ñầu :
Nếu Danh sách rỗng Thì
B11 : Head = new_elelment;
B12 : Tail = Head;
Ngược lại
B21 : Tail ->pNext = new_ele;
B22 : Tail = new_ele ;
void Themcuoi(List &L, Node *p){
if(L.pHead==NULL)
L.pHead=L.pTail=p;
else {
L.pTail->pNext=p;
L.pTail=p;
}
}
28
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Chèn một phần tử vào sau phần tử q
Thu
t toán :
Bắt ñầu :
Nếu ( q != NULL) thì
B1: new_ele -> pNext = q->pNext;
B2: q->pNext = new_ele
void Thempsauq(List &L, Node *p, Node *q){
if(q->pNext!=NULL)
p->pNext=q->pNext;
q->pNext=p;
}
29
© Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Tìm một phần tử trong danh sách ñơn
Thuật toán : Áp dụng thuật toán tìm tuyến tính ñể xác ñịnh
phần tử trong xâu có khoá k:
Bước 1:
p = Head; //Cho p trỏ ñến phần tử ñầu danh sách
Bước 2:
Trong khi (p != NULL) và (p->key != k )
p:=p->Next;// Cho p trỏ tới phần tử kế
Bước 3:
Nếu p != NULL thì p trỏ tới phần tử cần tìm
Ngược lại không có phần tử cần tìm.
Node *Search(LIST l, int k){
Node *p; p = l.pHead;
while((p!= NULL)&&(p->key != k))
p = p->pNext;
return p;
}
30
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
NODE *Search(LIST l, Data k)
{
NODE *p;
p = l.pHead;
while((p!= NULL)&&(p->Info != x))
p = p->pNext;
return p;
}
31
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Hủy một phần tử ñầu danh sách ñơn
Thu
t toán :
Bắt ñầu:
Nếu (Head != NULL) thì
B1: p = Head;
B2:
B21 : Head = Head->pNext; // tách p ra khỏi xâu
B22 : free(p); // Hủy biến ñộng do p trỏ ñến
B3: Nếu Head=NULL thì Tail = NULL; //Xâu rỗng.
32
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Data RemoveHead(LIST &l)
{
NODE *p;
Data x = NULLDATA;
if ( l.pHead != NULL)
{
p = l.pHead; x = p->Info;
l.pHead = l.pHead->pNext;
delete p;
if(l.pHead == NULL)
l.pTail = NULL;
}
return x;
}
33
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Hủy một phần tử ñứng sau phần tử q
Thu
t toán :
Bắt ñầu:
Nếu (q!= NULL) thì
B1: p = q->Next; // p là phần tử cần hủy
B2: Nếu (p != NULL) thì // q không phải là cuối xâu
B21 : q->Next = p->Next; // tách p ra khỏi xâu
B22 : free(p); // Hủy biến ñộng do p trỏ ñến
34
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void RemoveAfter (LIST &l, NODE *q)
{
NODE *p;
if ( q != NULL)
{
p = q ->pNext ;
if ( p != NULL)
{
if(p == l.pTail)
l.pTail = q;
q->pNext = p->pNext;
delete p;
}
}
else
RemoveHead(l);
}
35
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Hủy một phần tử có khóa k
Thu
t toán :
Bước 1:
Tìm phần tử p có khóa k và phần tử q ñứng trước nó
Bước 2:
Nếu (p!= NULL) thì // tìm thấy k
Hủy p ra khỏi xâu tương tự hủy phần tử sau q;
Ngược lại
Báo không có k;
36
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
int RemoveNode(LIST &l, Data k) {
NODE *p = l.pHead;
NODE *q = NULL;
while( p != NULL) {
if(p->Info == k) break;
q = p; p = p->pNext;
}
if(p == NULL) return 0; //Không tìm thấy k
if(q != NULL) {
if(p == l.pTail)
l.pTail = q;
q->pNext = p->pNext;
delete p;
}else{
l.pHead = p->pNext;
if(l.pHead == NULL)
l.pTail = NULL;
}
return 1;
}
37
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Duyệt danh sách
Duyệt danh sách là thao tác thường ñược thực
hiện khi có nhu cầu xử lý các phần tử của danh
sách như:
- Ðếm các phần tử của danh sách,
- Tìm tất cả các phần tử thoả ñiều kiện,
- Huỷ toàn bộ danh sách (và giải phóng bộ nhớ)
Thu
t toán :
Bước 1:
p = Head; //Cho p trỏ ñến phần tử ñầu DS
Bước 2:
Trong khi (Danh sách chưa hết) thực hiện
B21 : Xử lý phần tử p;
B22 : p:=p->pNext; // Cho p trỏ tới phần tử kế
38
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void ProcessList (LIST &l)
{
NODE *p;
p = l.pHead;
while (p!= NULL)
{
ProcessNode(p); // xử lý cụ thể tùy ứng dụng
p = p->pNext;
}
}
39
3.4. Sắp Xếp Danh Sách
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.4.1. Các cách tiếp cận
3.4.2. Một số phương pháp sắp xếp trên danh sách
40
3.4.1. Các cách tiếp cận
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
DS có thứ tự là DS mà các phần tử ñược sắp xếp theo
một thứ tự nào ñó dựa trên trường khoá. Ðể sắp xếp
một danh sách, có 2 phương án:
Phương án 1: Hoán vị nội dung các phần tử trong danh sách
Sử dụng các thuật toán sắp xếp như trên mảng, dựa trên việc
hoán vị nội dung của các phần tử
Phương pháp này ñòi hỏi sử dụng vùng nhớ trung gian, số lần
hoán vị có thể lên ñến bậc n2. Làm cho thao tác sắp xếp chậm
không tận dụng ñược các ưu ñiểm của DSLK .
41
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ : Cài ñặt thuật toán sắp xếp Chọn trực tiếp
void ListSelectionSort (LIST &l)
{
NODE *min,*p,*q;
p = l.pHead;
int tam;
while(p != l.pTail) {
q = p->pNext;
min = p;
while(q != NULL){
if(q->KeyKey )
min = q;
q= q->pNext;
}
tam=min->Key;
min->Key=p->Key;
p->Key=tam;
p = p->pNext;
}
}
42
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Phương án 2: Thay ñổi các mối liên kết (trên vùng Next)
Thay ñổi trình tự móc nối của các phần tử sao cho tạo lập nên
ñược thứ tự mong muốn,
Tuy nhiên thao tác trên các mọc nối thường sẽ phức tạp hơn là
thao tác trực tiếp trên dữ liệu.
Bước1: Khởi tạo danh sách mới Result là rỗng;
Bước2: Tìm trong danh sách cũ l phần tử nhỏ nhất;
Bước3: Tách min khỏi danh sách l;
Bước4: Chèn min vào cuối danh sách Result;
Bước5: Lặp lại bước 2 khi chưa hết danh sách Head;
43
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void ListSelectionSort2 (LIST &l){
LIST lRes;
NODE *min; // chỉ ñến phần tử có giá trị nhỏ nhất
NODE *p,*q, minprev;
lRes.pHead = lRes.pTail = NULL; // khởi tạo lRes
while(l.pHead != NULL){
p = l.pHead;
q = p->pNext; min = p; minprev = NULL;
while(q != NULL){
if(q->InfoInfo ) {
min = q; minprev = p
}
p = q; q = q->pNext;
}
if(minprev != NULL)
minprev->pNext = min->pNext;
else
l.pHead = min->pNext;
min->pNext = NULL;
AddTail(lRes, min);
}
l = lRes;
}
44
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.4.2. Một số phương pháp sắp xếp trên danh sách
Thuật toán Quick Sort
Bước 1: Chọn X là phần tử ñầu DS L làm phần tử cầm canh.
Loại X ra khỏi L.
Bước 2: Tách DS L ra làm 2 DS L1 (gồm các phần tử nhỏ hơn
hay bằng X) và L2 (gồm các phần tử lớn hơn X).
Bước 3: Nếu L1 != NULL thì Quick Sort (L1).
Bước 4: Nếu L2 != NULL thì Quick Sort (L2).
Bước 5: Nối L1, X, và L2 theo trình tự ta có DS L ñược sắp xếp.
45
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ví dụ
Chọn X = 4 làm phần tử cầm canh và tách L thành L1, L2:
Sắp xếp L1:
46
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Sắp xếp L2:
Chọn X = 6 làm phần tử cầm canh và tách L2 thanh L21, L22
Nối L12, X2, L22 thành L2:
Nối L1, X, L2 thành L:
47
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
void ListQSort(LIST & l){
NODE *p, *X; // X chỉ ñến phần tử cầm canh
LIST l1, l2;
if(l.pHead == l.pTail)
return;//ñã có thứ tự
l1.pHead == l1.pTail = NULL; //khởi tạo
l2.pHead == l2.pTail = NULL;
X = l.pHead; l.pHead = X->pNext;
while(l.pHead != NULL) //Tách l thành l1, l2;{
p = l.pHead;
l.pHead = p->pNext; p->pNext = NULL;
if (p->Info Info)
AddTail(l1, p);
else
AddTail(l2, p);
}
ListQSort(l1); ListQSort(l2); //Gọi ñệ qui ñể sorl1, sort l2
//Nối l1, X và l2 lại thành l ñã sắp xếp.
if(l1.pHead != NULL) {
l.pHead = l1.pHead; l1.pTail->pNext = X;
}
else
l.pHead = X;
X->pNext = l2;
if(l2.pHead != NULL)
l.pTail = l2.pTail;
else
l.pTail = X;
}
48
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ngoài ra còn một số thuật toán khác như Merge
Sort, Radix Sort
49
3.5. Các Cấu Trúc ðặc Biệt Của Danh Sách Liên Kết ðơn
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.5.1. Stack
3.5.2. Hàng ñợi (Queue)
50
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Stack là một vật chứa (container) làm việc theo cơ
chế LIFO (Last In First Out) "Vào sau ra trước".
Thao tác thêm 1 ñối tượng vào stack gọi là "Push".
Thao tác lấy 1 ñối tượng ra khỏi stack gọi là "Pop".
Stack có nhiều ứng dụng: khử ñệ qui, tổ chức lưu
vết các quá trình tìm kiếm theo chiều sâu, quay lui, vét
cạn, ứng dụng trong tính toán biểu thức, ñồ thị . . .
3.5.1. Stack
Hình ảnh stack
Push Pop
51
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
CTDL Stack hỗ trợ các thao tác:
Push(o): Thêm ñối tượng o vào ñầu stack
Pop(): Lấy ñối tượng ở ñầu stack ra khỏi stack và
trả về giá trị của nó. Nếu stack rỗng thì lỗi sẽ xảy ra.
isEmpty(): Kiểm tra xem stack có rỗng không.
isFull():Kiểm tra xem stack có ñầy không.
StackTop(): Trả về giá trị của phần tử nằm ở ñầu
stack. Nếu stack rỗng thì lỗi sẽ xảy ra.
52
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ðể biểu diễn Stack: Dùng mảng 1 chiều hoặc danh
sách liên kết.
Mảng 1 chiều Danh sách liên kết ñơn
- Viết chương trình dễ dàng,
nhanh chóng
- Bị hạn chế do số lượng phần tử
cố ñịnh
- Tốn chi phí tái cấp phát và sao
chép vùng nhớ nếu sử dụng
mảng ñộng
Phức tạp khi triển khai chương
trình
Không bị cố ñịnh về số phần tử,
phụ thuộc vào bộ nhớ
53
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
// Giả sử Stack chứa các phần tử kiểu nguyên
// Khai báo cấu trúc Stack
typedef struct STACK
{
int* StkArray; // mảng chứa các phần tử
int StkMax; // số phần tử tối ña
int StkTop; // vị trí ñỉnh Stack
};
//Thao tác “Khởi tạo Stack rỗng”
int InitStack(STACK& s, int MaxItems)
{
s.StkArray = new int[MaxItems];
if (s.StkArray == NULL)
return 0; // Không cấp phát ñược bộ nhớ
s.StkMax = MaxItems;
s.StkTop = -1; // chưa có phần tử nào trong Stack
return 1; // khởi tạo thành công
}
Ngăn xếp sử dụng mảng
54
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Kiểm tra Stack rỗng”
int IsEmpty(const STACK &s)
{
if (s.StkTop==-1)
return 1; // Stack rỗng
return 0; // Stack không rỗng
}
//Thao tác “Kiểm tra Stack ñầy”
int IsFull(const STACK &s)
{
if (s.StkTop==s.StkMax-1)
return 1; // Stack ñầy
return 0; // Stack chưa ñầy
}
55
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Push”: thêm một phần tử vào ñỉnh Stack
int Push (STACK& s, int newitem)
{
if (IsFull(s))
return 0; // stack ñầy, không thể thêm
s.StkTop++;
s.StkArray[s.StkTop] = newitem;
return 1; // thêm thành công
}
//Thao tác “Pop”: lấy ra 1 phần tử từ ñỉnh Stack
int Pop(STACK& s, int& outitem)
{
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra ñược
outitem = s.StkArray[s.StkTop];
s.StkTop--;
return 1; // lấy ra thành công
}
56
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//truy xuất 1 phần tử ở ñỉnh Stack, không làm thay ñổi Stack
int StackTop(const STACK s, int& outitem)
{
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra ñược
outitem = s.StkArray[s.StkTop];
return 1; // lấy ra thành công
}
57
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
// Giả sử Stack chứa các phần tử kiểu nguyên
// Khai báo cấu trúc một phần tử trong stack
typedef struct tagSTACK_NODE
{
int Data;
tagSTACK_NODE *pNext;
} STACK_NODE;
// Khai báo cấu trúc stack
typedef struct STACK
{
int StkCount;
STACK_NODE *StkTop;
};
Ngăn xếp sử dụng DSLK
58
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Khởi tạo stack rỗng”:
void InitStack(STACK& s)
{
s.StkTop = NULL;
s.StkCount = 0;
}
//Thao tác “Kiểm tra stack rỗng”
int IsEmpty(const STACK& s)
{
if (s.StkTop == NULL)
return 1; // stack rỗng
return 0; // stack không rỗng
}
59
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Kiểm tra stack ñầy”
int IsFull (const STACK s)
{
// thử tạo mới một phần tử
STACK_NODE* temp = new STACK_NODE;
// nếu không tạo ñược stack ñầy
if (temp == NULL)
return 1; // stack ñầy
delete temp;
return 0; // stack chưa ñầy
}
60
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Push”: thêm 1 phần tử vào ñỉnh stack
int Push(STACK &s, int newitem)
{
if (IsFull(s))
return 0; // Stack ñầy, không thêm vào ñược
STACK_NODE *pNew = new STACK_NODE;
pNew->Data = newitem;
pNew->pNext = s.StkTop;
s.StkTop = pNew;
s.StkCount++;
return 1; // Thêm thành công
}
61
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Pop”: lấy ra 1 phần tử từ ñỉnh stack
int Pop(STACK &s, int& outitem)
{
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra ñược
// lưu lại con trỏ ñến ptử ñầu
STACK_NODE *temp = s.StkTop;
outitem = s.StkTop->Data;
s.StkTop = s.StkTop->pNext;
delete temp;
s.StkCount--;
return 1; // Lấy ra thành công
}
62
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “StackTop”: truy xuất 1 phần tử ở ñỉnh stack
int StackTop(STACK &s, int& outitem)
{
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra ñược
outitem = s.StkTop->Data;
return 1; // Lấy ra thành công
}
63
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
3.5.2. Hàng ñợi (Queue)
Hàng ñợi là một vật chứa (container) các ñối tượng
Làm việc theo cơ chế FIFO (First In First Out) "Vào
trước ra trước".
Phòng vé
Hình ảnh queue
64
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
CTDL Queue hỗ trợ các thao tác:
InitQueue: Khởi tạo hàng ñợi rỗng
IsEmpty: Kiểm tra hàng ñợi rỗng ?
IsFull: Kiểm tra hàng ñợi ñầy ?
EnQueue: Thêm 1 phần tử vào cuối hàng ñợi, có
thể làm hàng ñợi ñầy
DeQueue: Lấy ra 1 phần tử từ ñầu Queue, có thể
làm Queue rỗng
QueueFront: Kiểm tra phần tử ñầu Queue
QueueRear: Kiểm tra phần tử cuối Queue
65
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Ðể biểu diễn Queue: Dùng mảng 1 chiều hoặc danh
sách liên kết.
Mảng 1 chiều Danh sách liên kết ñơn
- Viết chương trình dễ dàng,
nhanh chóng
- Bị hạn chế do số lượng phần tử
cố ñịnh
- Tốn chi phí tái cấp phát và sao
chép vùng nhớ nếu sử dụng
mảng ñộng
Phức tạp khi triển khai chương
trình
Không bị cố ñịnh về số phần tử,
phụ thuộc vào bộ nhớ
66
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Mảng (QArray) ñể chứa các phần tử.
Số nguyên (QMax)ñể lưu số phần tử tối ña
2 số nguyên (Qfront/QRear) ñể xác ñịnh vị trí ñầu/cuối
Số nguyên (QNumItems) ñể lưu số phần tử hiện có
Hàng ñợi sử dụng mảng
0 1 2 3 4 5 6
Qarray 37 22 15 3
QMax = 7
QNumItems = 4
QFront = 1
QRear = 4
67
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
// Giả sử Queue chứa các phần tử kiểu nguyên (int)
// Khai báo cấu trúc Queue
typedef struct QUEUE
{
int* QArray;
int QMax;
int QNumItems;
int QFront;
int QRear;
};
68
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả”
Giải pháp? Nối dài mảng (mảng ñộng) hay sử dụng một mảng vô
cùng lớn?
0 1 2 3 4 5 6
Qarray 37 22 15 3 7 9
QMax = 7
QNumItems = 4
QFront = 1
QRear = 7
69
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Khởi tạo Queue rỗng”:
int InitQueue(QUEUE& q, int MaxItem)
{
q.QArray = new int[MaxItem];
if (q.QArray == NULL)
return 0; // không ñủ bộ nhớ
q.QMax = MaxItem;
q.QNumItems = 0;
q.QFront = q.QRear = -1;
return 1; // thành công
}
70
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác “Kiểm tra Queue rỗng”:
int IsEmpty(QUEUE q)
{
if (q.QNumItems == 0)
return 1; // rỗng
return 0; // không rỗng
}
//Thao tác “Kiểm tra Queue ñầy”:
int IsFull(QUEUE q)
{
if (q.QMax == q.QNumItems)
return 1; // ñầy
return 0; // không ñầy
}
71
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác EnQueue: thêm 1 phần tử vào cuối Queue
int EnQueue(QUEUE &q, int newitem)
{
if (IsFull(q))
return 0; // Queue ñầy, không thêm vào ñược
q.QRear++;
if (q.QRear==q.QMax) // “tràn giả”
q.QRear = 0; // Quay trở về ñầu mảng
q.QArray[q.QRear] = newitem;
// thêm phần tử vào cuối Queue
if (q.QNumItems==0)
q.QFront = 0;
q.QNumItems++;
return 1; // Thêm thành công
}
72
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác DeQueue: lấy ra 1 phần tử ở ñầu Queue
int DeQueue(QUEUE &q, int& itemout)
{
if (IsEmpty(q))
return 0; // Queue rỗng, không lấy ra ñược
itemout = q.QArray[q.QFront]; // lấy phần tử ñầu ra
q.QFront++;
q.QNumItems--;
if (q.QFront==q.QMax) // nếu ñi hết mảng …
q.QFront = 0; // … quay trở về ñầu mảng
if (q.QNumItems==0) // nếu lấy ra phần tử cuối cùng
q.QFront = q.QRear = -1; // khởi tạo lại Queue
return 1; // Lấy ra thành công
}
73
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thao tác QueueFront: Kiểm tra phần tử ở ñầu Queue
int QueueFront(const QUEUE &q, int& itemout)
{
if (IsEmpty(q))
return 0; // Queue rỗng, không kiểm tra
// lấy phần tử ñầu ra
itemout = q.QArray[q.QFront];
return 1;
}
//Thao tác QueueRear: Kiểm tra phần tử ở cuối Queue
int QueueRear(const QUEUE &q, int& itemout)
{
if (IsEmpty(q))
return 0; // Queue rỗng, không kiểm tra
// lấy phần tử cuối ra
itemout = q.QArray[q.QRear];
return 1;
}
74
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Khai báo cấu trúc
typedef struct tagNODE
{
int data;
tagNODE* pNext;
} NODE, *PNODE;
typedef struct tagQUEUE
{
int NumItems;
PNODE pFront, pRear;
} QUEUE;
Hàng ñợi sử dụng DSLK
75
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
Các thao tác cơ bản
int InitQueue(QUEUE& q);
int IsEmpty(const QUEUE& q);
int IsFull(const QUEUE& q);
int EnQueue(QUEUE &q, int newitem);
int DeQueue(QUEUE &q, int& itemout);
int QueueFront(const QUEUE &q, int& itemout);
int QueueRear(const QUEUE &q, int& itemout);
76
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Khởi tạo Queue rỗng
int InitQueue(QUEUE& q)
{
q.NumItems = 0;
q.pFront = q.pRear = NULL;
return 1;
}
77
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Kiểm tra Queue rỗng
int IsEmpty(const QUEUE& q)
{
return (q.NumItems==0);
}
//Kiểm tra Queue ñầy
int IsFull(const QUEUE& q)
{
PNODE tmp = new NODE;
if (tmp==NULL)
return 1;
delete tmp;
return 0;
}
78
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Thêm 1 phần tử vào cuối Queue
int EnQueue(QUEUE &q, int newitem)
{
if (IsFull(q)==1)
return 0;
PNODE p = new NODE;
p->data = newitem;
p->pNext = NULL;
if (q.pFront==NULL && q.pRear==NULL)
q.pFront = q.pRear = p;
else
{
q.pRear->pNext = p;
q.pRear = p;
}
q.NumItems++;
return 1;
}
79
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Lấy ra 1 phần tử ở ñầu Queue
int DeQueue(QUEUE &q, int& itemout)
{
if (IsEmpty(q)==1)
return 0;
PNODE p = q.pFront;
q.pFront = p->pNext;
itemout = p->data;
q.NumItems--;
delete p;
if (q.NumItems==0)
InitQueue(q);
return 1;
}
80
© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương
//Kiểm tra 1 phần tử ở ñầu Queue
int QueueFront(const QUEUE &q, int& itemout)
{
if (IsEmpty(q)==1)
return 0;
itemout = q.pFront->data;
return 1;
}
//Kiểm tra 1 phần tử ở cuối Queue
int QueueRear(const QUEUE &q, int& itemout)
{
if (IsEmpty(q)==1)
return 0;
itemout = q.pRear->data;
return 1;
}
Các file đính kèm theo tài liệu này:
- 04_chuong3_7991.pdf