Bài giảng Cấu trúc dữ liệu: Chương 5 - ThS. Thiều Quang Trung (2018)

CHƯƠNG 5 KIỂU NGĂN XẾP, HÀNG ĐỢI, ĐỆ QUY

GV Th.S. Thiều Quang Trung 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

Nhập 3

Nhập 5

Nhập 7

Nhập 1

Ví dụ thêm và xóa phần tử trong stack Cần nhập 4 số vào Ban đầu

3 7

5 1

Lấy ra => 3

Lấy ra => 7

Lấy ra => 5

Lấy ra => 1

Stack đã rỗng Ngừng

3 7

5 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

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

bool InitStack(STACK& s, int MaxItems) {

s.StkArray = new int[MaxItems]; if (s.StkArray == NULL)

return false;

s.StkMax = MaxItems; s.StkTop = -1; return true;

}

GV. Thiều Quang Trung 11

Stack số nguyên – Sử dụng mảng

bool IsEmpty(const STACK &s) {

if (s.StkTop==-1)

return true;

return false;

}

GV. Thiều Quang Trung 12

Stack số nguyên – Sử dụng mảng

bool IsFull(const STACK &s) {

if (s.StkTop==s.StkMax-1)

return true;

return false;

}

GV. Thiều Quang Trung 13

Stack số nguyên – Sử dụng mảng

bool Push (STACK &s, int newitem) {

if (IsFull(s))

return false;

s.StkTop++; s.StkArray[s.StkTop] = newitem; return true;

}

GV. Thiều Quang Trung 14

Stack số nguyên – Sử dụng mảng

bool Pop(STACK &s, int &outitem) {

if (IsEmpty(s))

return false; outitem = s.StkArray[s.StkTop]; s.StkTop--; return true;

}

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 Data

Link

GV. Thiều Quang Trung 18

Stack – Sử dụng DSLK

• Cấu tạo đầu stack

stack

StkCnt

StkTop

StkCnt StkTop

end stack

node

• Cấu tạo một phần tử

Data Link

end node

Data

Link

GV. Thiều Quang Trung 19

Stack số nguyên – Sử dụng DSLK

typedef struct tagSTACK_NODE {

int Data; tagSTACK_NODE *pNext;

} STACK_NODE; typedef struct STACK {

int StkCount; STACK_NODE *StkTop;

};

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

void InitStack(STACK &s) {

s.StkTop = NULL; s.StkCount = 0;

}

GV. Thiều Quang Trung 22

Stack số nguyên – Sử dụng DSLK

bool IsEmpty(const STACK &s) {

if (s.StkTop == NULL) return true;

return false;

}

GV. Thiều Quang Trung 23

Stack số nguyên – Sử dụng DSLK

bool IsFull (const STACK s) {

STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true;

delete temp; return false;

}

GV. Thiều Quang Trung 24

Stack số nguyên – Sử dụng DSLK

bool Push(STACK &s, int newitem) {

StkTop

if (IsFull(s))

StkCnt N

return false;

4 7 Data Data

Link Link

STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true;

}

GV. Thiều Quang Trung 25

Stack số nguyên – Sử dụng DSLK

bool Pop(STACK &s, int &outitem) {

StkTop

if (IsEmpty(s))

temp

StkCnt N

return false;

4 Data

Link

7 Data

Link

STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; s.StkTop = s.StkTop->pNext; 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

Stack rỗng Stop

4 4 4

3 5 3

5 7 7

7 3 5

1 1 1

2 2 2

1 1 1

3 3 3

4 4 4

0 0 0

(3,4) (0,4) (0,1)

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

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

giả”

0

3

2 1 4 37 22 15 3

5 7

6 9

Qarray

QMax = 7

QNumItems = 6

QFront = 1

QRear = 6

• 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

3 • Xử lý mảng như một danh sách liên kết vòng 6 0 9

1 4 37 22 15 3

Qarray

5 7

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

11 7 19 21 81

QArray QMax QNumItems QFront QRear

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

0 1 2 3

5

6 Chỉ số mảng

4 11 7 19 21 81 123

QArray QMax QNumItems QFront QRear

7 6 1 6

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

0 1 2 3

5

6 Chỉ số mảng

4 11 7 19 21 81 123

QArray QMax QNumItems QFront QRear

7 5 2 6

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

4

6

5 1 2 3

QArray QMax QNumItems QFront QRear

0 456 11 7 19 21 81 123 7 6 2 0

GV. Thiều Quang Trung 43

Queue số nguyên – Sử dụng mảng

bool InitQueue(QUEUE &q, int MaxItem) {

q.QArray = new int[MaxItem]; if (q.QArray == NULL) return false;

q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return true;

}

GV. Thiều Quang Trung 44

Queue số nguyên – Sử dụng mảng

bool IsEmpty(QUEUE q) {

if (q.QNumItems == 0) return true;

return false;

}

GV. Thiều Quang Trung 45

Queue số nguyên – Sử dụng mảng

bool IsFull(QUEUE q) {

if (q.QMax == q.QNumItems)

return true;

return false;

}

GV. Thiều Quang Trung 46

Queue số nguyên – Sử dụng mảng

bool EnQueue(QUEUE &q, int newitem) {

if (IsFull(q))

return false;

q.QRear++; if (q.QRear==q.QMax)

q.QRear = 0;

q.QArray[q.QRear] = newitem; if (q.QNumItems==0)

q.QFront = 0;

q.QNumItems++; return true;

}

GV. Thiều Quang Trung 47

Queue số nguyên – Sử dụng mảng

bool DeQueue(QUEUE &q, int &itemout) {

if (IsEmpty(q))

return false;

itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems--; if (q.QFront==q.QMax)

q.QFront = 0;

if (q.QNumItems==0)

q.QFront = q.QRear = -1;

return true;

}

GV. Thiều Quang Trung 48

Queue số nguyên – Sử dụng mảng

bool QueueFront(const QUEUE &q, int &itemout) {

if (IsEmpty(q))

return false;

itemout = q.QArray[q.QFront]; return true;

}

GV. Thiều Quang Trung 49

Queue số nguyên – Sử dụng mảng

bool QueueRear(const QUEUE &q, int

&itemout)

{

if (IsEmpty(q))

return false;

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

typedef struct tagNODE {

int data; tagNODE* pNext;

} NODE, *PNODE;

typedef struct tagQUEUE {

int NumItems; PNODE pFront, pRear;

} 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

bool InitQueue(QUEUE &q) {

q.NumItems = 0; q.pFront = q.pRear = NULL; return true;

}

GV. Thiều Quang Trung 54

Queue – Sử dụng DSLK

bool IsEmpty(const QUEUE& q) {

return (q.NumItems==0);

}

GV. Thiều Quang Trung 55

Queue – Sử dụng DSLK

bool IsFull(const QUEUE &q) {

PNODE tmp = new NODE; if (tmp==NULL)

return true;

delete tmp; return false;

}

GV. Thiều Quang Trung 56

Queue – Sử dụng DSLK

bool EnQueue(QUEUE &q, int newitem) {

if (IsFull(q))

return false;

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 true;

}

GV. Thiều Quang Trung 57

Queue – Sử dụng DSLK bool DeQueue(QUEUE &q, int &itemout) {

if (IsEmpty(q))

return false;

PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems--; delete p; if (q.NumItems==0) InitQueue(q);

return true;

}

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:

n! =

1 n * (n-1)!

nếu n=0 nếu n>0

• Mã C++:

int factorial(int n) {

if (n==0) return 1; else

return (n * factorial(n - 1));

}

GV. Thiều Quang Trung 60

Thi hành hàm tính giai thừa

factorial (3)

n=3

factorial (2)

…

n=2

3*factorial(2)

…

factorial (1)

n=1

2*factorial(1)

…

factorial (0)

n=0

1*factorial(0)

…

return 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(2)

factorial(3)

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)

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

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