CHƯƠNG 5 KIỂU NGĂN XẾP, HÀNG ĐỢI, ĐỆ QUY
GV Th.S. Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế Đối ngoại
Nội dung
• Khái niệm ngăn xếp
• Phương pháp xây dựng stack
• Các thao tác cơ bản trên stack
• Kiểu queue - hàng đợi
• Các thao tác cơ bản trên queue
• Đệ qui và các bài toán đệ qui
1 2 3 4 5 6
GV. Thiều Quang Trung 2
Ngăn xếp - Định nghĩa
• Stack là 1 cấu trúc: – Gồm nhiều phần tử – Hoạt động theo cơ chế “Vào sau – Ra trước”
(LIFO – Last In, First Out)
Đỉnh ngăn xếp
GV. Thiều Quang Trung 3
Thao tác cơ bản trên Stack
Push
Pop
• InitStack: khởi tạo Stack rỗng • IsEmpty: kiểm tra Stack rỗng? • IsFull: kiểm tra Stack đầy? • Push: thêm 1 phần tử vào Stack • Pop: lấy ra 1 phần tử khỏi Stack
GV. Thiều Quang Trung 4
Thao tác thêm - Push vào Stack
H S U P
Top
GV. Thiều Quang Trung 5
Thao tác lấy - Pop khỏi stack
Top
P O P
GV. Thiều Quang Trung 6
Ví dụ thêm và xóa phần tử trong stack
Nhập 1
Nhập 5
Nhập 7
Nhập 3
Cần nhập 4 số vào Ban đầu
3 7
7
5 1
1
5 1
5 1
Lấy ra => 3
Lấy ra => 7
Lấy ra => 5
Lấy ra => 1
Stack đã rỗng Ngừng
7
3 7
5 1
5 1
5 1
1
GV. Thiều Quang Trung 7
Cách xây dựng Stack
Danh sách liên kết Phức tạp khi triển khai
chương trình
Mảng 1 chiều 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
Không bị cố định về số phần tử, phụ thuộc vào bộ 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
GV. Thiều Quang Trung 8
Stack – Sử dụng mảng
Top
6 3 9
Stack
9 0
3 1
6 2
3
4
5
6
7
8
9
GV. Thiều Quang Trung 9
Stack số nguyên – Sử dụng mảng
struct ttStack
{
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
};
typedef struct ttStack STACK;
GV. Thiều Quang Trung 10
Stack số nguyên – Sử dụng mảng
s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return false; s.StkMax = MaxItems; s.StkTop = -1; return true;
bool InitStack(STACK& s, int MaxItems) { }
GV. Thiều Quang Trung 11
Stack số nguyên – Sử dụng mảng
return true;
if (s.StkTop==-1) return false;
bool IsEmpty(const STACK &s) { }
GV. Thiều Quang Trung 12
Stack số nguyên – Sử dụng mảng
return true;
if (s.StkTop==s.StkMax-1) return false;
bool IsFull(const STACK &s) { }
GV. Thiều Quang Trung 13
Stack số nguyên – Sử dụng mảng
return false;
if (IsFull(s)) s.StkTop++; s.StkArray[s.StkTop] = newitem; return true;
bool Push (STACK &s, int newitem) { }
GV. Thiều Quang Trung 14
Stack số nguyên – Sử dụng mảng
if (IsEmpty(s))
s.StkTop--; return true;
bool Pop(STACK &s, int &outitem) { return false; outitem = s.StkArray[s.StkTop]; }
GV. Thiều Quang Trung 15
Bài tập
• Viết hàm nhập và xuất Stack số nguyên • Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là ký tự) • Khai báo cấu trúc và viết hàm tạo Stack từ
chuỗi ký tự str (mỗi phần tử Stack là một từ - từ cách nhau bởi khoảng trắng)
GV. Thiều Quang Trung 16
Stack – Ví dụ ứng dụng
• Kiểm tra sự tương ứng của các cặp ngoặc
?
?
đơn trong một biểu thức
( A + B ) / C)
• ( ( A + B ) / C • Đảo ngược một chuỗi ký tự • Kinh tế Đối ngoại iạogn iốĐ ết hniK
GV. Thiều Quang Trung 17
Stack – Sử dụng DSLK
StkTop
StkCnt N
7 Data
Link
7 9
9 Data
Link
4
4 Data
Link
GV. Thiều Quang Trung 18
Stack – Sử dụng DSLK
• Cấu tạo đầu stack
StkTop
StkCnt
StkCnt
N
• Cấu tạo một phần tử
Data
stack end stack node end node
Data
Link
GV. Thiều Quang Trung 19
Stack số nguyên – Sử dụng DSLK
int Data; tagSTACK_NODE *pNext;
int StkCount; STACK_NODE *StkTop;
typedef struct tagSTACK_NODE { } STACK_NODE; typedef struct STACK { };
GV. Thiều Quang Trung 20
Stack – Sử dụng DSLK
StkTop
StkCnt N
4 7 Data Data
Link Link
• VD: Thực hiện một số thao tác trên stack STACK s; InitStack(s); Push(s, 7); Push(s, 4); Pop(s, x); // x = ?
GV. Thiều Quang Trung 21
Stack số nguyên – Sử dụng DSLK
s.StkTop = NULL; s.StkCount = 0;
void InitStack(STACK &s) { }
GV. Thiều Quang Trung 22
Stack số nguyên – Sử dụng DSLK
if (s.StkTop == NULL) return true; return false;
bool IsEmpty(const STACK &s) { }
GV. Thiều Quang Trung 23
Stack số nguyên – Sử dụng DSLK
STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true; delete temp; return false;
bool IsFull (const STACK s) { }
GV. Thiều Quang Trung 24
Stack số nguyên – Sử dụng DSLK
StkTop
StkCnt N
return false;
if (IsFull(s))
4 7 Data Data
Link Link
s.StkTop = pNew; s.StkCount++; return true;
bool Push(STACK &s, int newitem) { STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; }
GV. Thiều Quang Trung 25
Stack số nguyên – Sử dụng DSLK
StkTop
temp
StkCnt N
return false;
if (IsEmpty(s))
4 Data
Link
s.StkTop = s.StkTop->pNext;
7 Data
Link
bool Pop(STACK &s, int &outitem) { STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; delete temp; s.StkCount--; return true; }
outitem = 4
GV. Thiều Quang Trung 26
Stack – Ứng dụng
• Stack có nhiều ứng dụng: • Lưu vết trong thuật toán “back-tracking” (theo dõi
dấu vết)
• Tính giá trị biểu thức toán học (thuật toán Balan
ngược) • Khử đệ quy • …
GV. Thiều Quang Trung 27
Stack – Quick Sort
• Để khử đệ quy cho Quick Sort, ta sử dụng một stack để lưu lại các partition (phân hoạch) cần tiến hành sắp xếp.
• Ý tưởng:
– Push phân hoạch đầu tiên (0, n-1) vào stack – Trong khi stack chưa rỗng
• Pop một phân hoạch từ stack • Chọn phần tử trục trên phân hoạch này • Điều chỉnh phân hoạch tương ứng với trục • Push 2 phân hoạch bên trái và phải trục vào stack
GV. Thiều Quang Trung 28
Stack – Quick Sort
• Push phân hoạch đầu tiên (0, n-1) vào
stack
• Trong khi stack chưa rỗng
– Pop một phân hoạch từ stack – Chọn phần tử trục trên phân hoạch này – Điều chỉnh phân hoạch tương ứng với trục – Push 2 phân hoạch bên trái và phải trục vào
stack
t
Stack rỗng Stop
4 4 4
3 5 3
5 7 7
7 3 5
1 1 1
(3,4) (0,4) (0,1)
j
i
2 2 2 1 1 1 3 3 3 4 4 4 0 0 0
GV. Thiều Quang Trung 29
Hàng đợi Queue
Phòng vé
GV. Thiều Quang Trung 30
Queue – Định nghĩa
• Hàng đợi là một cấu trúc:
– Gồm nhiều phần tử có thứ tự – Hoạt động theo cơ chế “Vào trước, ra trước”
(FIFO - First In First Out)
GV. Thiều Quang Trung 31
Queue – Định nghĩa
• Các thao tác cơ bản trên hàng đợi:
– 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
GV. Thiều Quang Trung 32
Queue
• Minh họa thao tác EnQueue
• Minh họa thao tác DeQueue
GV. Thiều Quang Trung 33
Cách xây dựng Queue
– Sử dụng mảng một chiều – Sử dụng danh sách liên kết đơn
GV. Thiều Quang Trung 34
Queue – Sử dụng mảng
• Dùng 1 mảng (QArray) để chứa các phần tử. • Dùng 1 số nguyên (QMax)để lưu số phần tử tối
đa trong hàng đợi
• Dùng 2 số nguyên (QFront, QRear) để xác định
vị trí đầu, cuối hàng đợi
• Dùng 1 số nguyên (QNumItems) để lưu số phần
tử hiện có trong hàng đợi
GV. Thiều Quang Trung 35
Queue – Sử dụng mảng
0
2
3
5
6
1 4 37 22 15 3
Qarray QMax = 7 QNumItems = 4 QFront = 1 QRear = 4
GV. Thiều Quang Trung 36
Queue số nguyên – Sử dụng mảng
typedef struct QUEUE
{
int* QArray;
int QMax;
int QNumItems;
int QFront;
int QRear;
};
GV. Thiều Quang Trung 37
Queue số nguyên – Sử dụng mảng
• Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn
0
2
4
1 3 5 37 22 15 3 7
6 9
Qarray
QMax = 7
QNumItems = 6
QFront = 1
QRear = 6
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?
GV. Thiều Quang Trung 38
Queue số nguyên – Sử dụng mảng
2
4
• Xử lý mảng như một danh sách liên kết vòng 6 0 9
1 3 5 37 22 15 3 7
Qarray
QMax = 7
QNumItems = 6
QFront = 1
QRear = 6
GV. Thiều Quang Trung 39
Queue số nguyên – Sử dụng mảng
VD: Cho queue như sau
Chỉ số mảng 0 1 2 3 4 5 6
QArray QMax QNumItems QFront QRear
11 7 19 21 81 7 5 1 5
GV. Thiều Quang Trung 40
Queue số nguyên – Sử dụng mảng
1. Thêm giá trị 123 vào hàng đợi
6 123
Chỉ số mảng 0 1 2 3 4 5 11 7 19 21 81 7 6 1 6
QArray QMax QNumItems QFront QRear
GV. Thiều Quang Trung 41
Queue số nguyên – Sử dụng mảng
2. Lấy một phần tử khỏi hàng đợi
6 123
Chỉ số mảng 0 1 2 3 4 5 11 7 19 21 81 7 5 2 6
QArray QMax QNumItems QFront QRear
GV. Thiều Quang Trung 42
Queue số nguyên – Sử dụng mảng
3. Thêm giá trị 456 vào hàng đợi
Chỉ số mảng
0
6 123
QArray QMax QNumItems QFront QRear
1 2 3 4 5 456 11 7 19 21 81 7 6 2 0
GV. Thiều Quang Trung 43
Queue số nguyên – Sử dụng mảng
q.QArray = new int[MaxItem]; if (q.QArray == NULL) return false; q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return true;
bool InitQueue(QUEUE &q, int MaxItem) { }
GV. Thiều Quang Trung 44
Queue số nguyên – Sử dụng mảng
if (q.QNumItems == 0) return true; return false;
bool IsEmpty(QUEUE q) { }
GV. Thiều Quang Trung 45
Queue số nguyên – Sử dụng mảng
return true;
if (q.QMax == q.QNumItems) return false;
bool IsFull(QUEUE q) { }
GV. Thiều Quang Trung 46
Queue số nguyên – Sử dụng mảng
return false;
q.QRear = 0;
q.QFront = 0;
if (IsFull(q)) q.QRear++; if (q.QRear==q.QMax) q.QArray[q.QRear] = newitem; if (q.QNumItems==0) q.QNumItems++; return true;
bool EnQueue(QUEUE &q, int newitem) { }
GV. Thiều Quang Trung 47
Queue số nguyên – Sử dụng mảng
return false;
q.QFront = 0;
q.QFront = q.QRear = -1;
if (IsEmpty(q)) itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems--; if (q.QFront==q.QMax) if (q.QNumItems==0) return true;
bool DeQueue(QUEUE &q, int &itemout) { }
GV. Thiều Quang Trung 48
Queue số nguyên – Sử dụng mảng
return false;
if (IsEmpty(q)) itemout = q.QArray[q.QFront]; return true;
bool QueueFront(const QUEUE &q, int &itemout) { }
GV. Thiều Quang Trung 49
Queue số nguyên – Sử dụng mảng
bool QueueRear(const QUEUE &q, int
&itemout)
return false;
if (IsEmpty(q)) itemout = q.QArray[q.QRear]; return true;
{ }
GV. Thiều Quang Trung 50
Queue – Ví dụ ứng dụng
• Quản lý việc thực hiện các tác vụ (task) trong môi
trường xử lý song song • Hàng đợi in ấn các tài liệu • Vùng nhớ đệm (buffer) dùng cho bàn phím • Quản lý thang máy
GV. Thiều Quang Trung 51
Queue – Sử dụng DSLK
int data; tagNODE* pNext;
int NumItems; PNODE pFront, pRear;
typedef struct tagNODE { } NODE, *PNODE; typedef struct tagQUEUE { } QUEUE;
GV. Thiều Quang Trung 52
Queue – Sử dụng DSLK
• Các thao tác cơ bản bool InitQueue(QUEUE &q); bool IsEmpty(const QUEUE &q); bool IsFull(const QUEUE &q); bool EnQueue(QUEUE &q, int newitem); bool DeQueue(QUEUE &q, int& itemout);
GV. Thiều Quang Trung 53
Queue – Sử dụng DSLK
q.NumItems = 0; q.pFront = q.pRear = NULL; return true;
bool InitQueue(QUEUE &q) { }
GV. Thiều Quang Trung 54
Queue – Sử dụng DSLK
return (q.NumItems==0);
bool IsEmpty(const QUEUE& q) { }
GV. Thiều Quang Trung 55
Queue – Sử dụng DSLK
return true;
PNODE tmp = new NODE; if (tmp==NULL) delete tmp; return false;
bool IsFull(const QUEUE &q) { }
GV. Thiều Quang Trung 56
Queue – Sử dụng DSLK
return false;
q.pRear->pNext = p; q.pRear = p;
if (IsFull(q)) PNODE p = new NODE; p->data = newitem; p->pNext = NULL; if (q.pFront==NULL && q.pRear==NULL) q.pFront = q.pRear = p; else { } q.NumItems++; return true;
bool EnQueue(QUEUE &q, int newitem) { }
GV. Thiều Quang Trung 57
return false;
if (IsEmpty(q)) PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems--; delete p; if (q.NumItems==0) InitQueue(q); return true;
Queue – Sử dụng DSLK bool DeQueue(QUEUE &q, int &itemout) { }
GV. Thiều Quang Trung 58
Khái niệm đệ qui
• Khái niệm: đệ qui là hình thức có dùng lại chính
nó. – Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân
cho giai thừa của n-1 nếu n > 0 • Quá trình đệ qui gồm 2 phần: – Trường hợp cơ sở (base case) – Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở
• Ví dụ trên:
– Giai thừa của n là 1 nếu n là 0 – Giai thừa của n là n * (giai thừa của n-1) nếu n>0
GV. Thiều Quang Trung 59
Tính giai thừa
• Định nghĩa không đệ qui: – n! = n * (n-1) * … * 1
• Định nghĩa đệ qui:
1 n * (n-1)!
nếu n=0 nếu n>0
n! = • Mã C++:
if (n==0) return 1;
return (n * factorial(n - 1));
int factorial(int n) { else }
GV. Thiều Quang Trung 60
Thi hành hàm tính giai thừa
factorial (3)
n=3
factorial (2)
n=2
factorial (1)
… 3*factorial(2)
6
n=1
2
… 2*factorial(1)
factorial (0)
n=0
… 1*factorial(0)
1
… return 1;
1
GV. Thiều Quang Trung 61
Trạng thái hệ thống khi thi hành hàm tính giai thừa
Stack hệ thống
factorial(0)
factorial(1)
factorial(1)
factorial(1)
factorial(2)
factorial(2)
factorial(2)
factorial(2)
factorial(2)
factorial(3)
factorial(3)
factorial(3)
factorial(3)
factorial(3)
factorial(3)
factorial(3)
t
Thời gian hệ thống
Gọi hàm factorial(3)
Gọi hàm factorial(2)
Gọi hàm factorial(1)
Gọi hàm factorial(0)
Trả về từ hàm factorial(0)
Trả về từ hàm factorial(1)
Trả về từ hàm factorial(2)
Trả về từ hàm factorial(3)
t
GV. Thiều Quang Trung 62
Bài toán Tháp Hà nội
• Luật:
– Di chuyển mỗi lần một đĩa – Không được đặt đĩa lớn lên trên đĩa nhỏ
GV. Thiều Quang Trung 63
Bài toán Tháp Hà nội – Thiết kế hàm
• Hàm đệ qui:
– Chuyển (count-1) đĩa trên đỉnh của cột start sang
cột temp
– Chuyển 1 đĩa (cuối cùng) của cột start sang cột
finish
– Chuyển count-1 đĩa từ cột temp sang cột finish
magic
GV. Thiều Quang Trung 64
Bài toán Tháp Hà nội – Mã C++
void move(int count, int start, int finish, int temp) {
if (count > 0) {
move(count − 1, start, temp, finish); cout << "Move disk " << count << " from " << start << " to " << finish << "." << endl; move(count − 1, temp, finish, start);
}
}
GV. Thiều Quang Trung 65
Bài toán Tháp Hà nội – Thi hành
GV. Thiều Quang Trung 66
Bài toán Tháp Hà nội – Cây đệ qui
GV. Thiều Quang Trung 67
Thiết kế các giải thuật đệ qui
• Tìm bước chính yếu (bước đệ qui) • Tìm qui tắc ngừng • Phác thảo giải thuật
– Dùng câu lệnh if để lựa chọn trường hợp.
• Kiểm tra điều kiện ngừng
– Đảm bảo là giải thuật luôn dừng lại.
• Vẽ cây đệ qui
– Chiều cao cây ảnh hưởng lượng bộ nhớ cần thiết. – Số nút là số lần bước chính yếu được thi hành.
GV. Thiều Quang Trung 68
Đệ qui đuôi (tail recursion)
• Định nghĩa: câu lệnh thực thi cuối cùng là lời
gọi đệ qui đến chính nó. • Khử: chuyển thành vòng lặp.
GV. Thiều Quang Trung 69
Khử đệ qui đuôi hàm giai thừa
• Giải thuật: product=1 for (int count=1; count < n; count++)
product *= count;
GV. Thiều Quang Trung
70
Dãy số Fibonacci
• Định nghĩa: – F0 = 0 – F1 = 1 – Fn = Fn-1 + Fn-2 khi n>2
• Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … • Hàm đệ qui:
int fibonacci (int n) {
if (n<=0) return 0; if (n==1) return 1; else return (fibonacci(n-1) + fibonacci(n-2));
}
GV. Thiều Quang Trung 71
Dãy số Fibonacci – Cây thi hành
Đã tính rồi
GV. Thiều Quang Trung 72
Dãy số Fibonacci – Khử đệ qui
• Nguyên tắc:
– Dùng biến lưu trữ giá trị đã tính của Fn-2 – Dùng biến lưu trữ giá trị đã tính của Fn-1 – Tính Fn = Fn-1 + Fn-2 và lưu lại để dùng cho lần sau
• Giải thuật:
int Fn2=0, Fn1=1, Fn; for (int i = 2; i <= n; i++) { Fn = Fn1 + Fn2; Fn2 = Fn1; Fn1 = Fn; }
GV. Thiều Quang Trung 73
GV: Thiều Quang Trung 74
