Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Kiểu ngăn xếp, hàng đợi, đệ quy - Thiều Quang Trung

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 • Khái niệm ngăn xếp 1 • Phương pháp xây dựng stack 2 • Các thao tác cơ bản trên stack 3 • Kiểu queue - hàng đợi 4 • Các thao tác cơ bản trên queue 5 • Đệ qui và các bài toán đệ qui 6 Nội dung 2 GV. Thiều Quang Trung 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 3 GV. Thiều Quang Trung Thao tác cơ bản trên Stack • 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 Push Pop 4 GV. Thiều Quang Trung Thao tác thêm - Push vào Stack Top P U SH 5 GV. Thiều Quang Trung Thao tác lấy - Pop khỏi stack Top P O P 6 GV. Thiều Quang Trung Ví dụ thêm và xóa phần tử trong stack Cần nhập 4 số vào Ban đầu Nhập 1 1 Nhập 5 1 5 Nhập 7 1 5 7 Nhập 3 1 5 7 3 Lấy ra => 3 1 5 7 3 Lấy ra => 7 1 5 7 Lấy ra => 5 1 5 Lấy ra => 1 1 Stack đã rỗng Ngừng 7 GV. Thiều Quang Trung Cách xây dựng Stack Mảng 1 chiều Danh sách liên kết  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ớ 8 GV. Thiều Quang Trung Stack – Sử dụng mảng 9 3 6 9 3 6 0 1 2 3 4 5 6 7 8 9 Stack Top 9 GV. Thiều Quang Trung 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; 10 GV. Thiều Quang Trung 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; } 11 GV. Thiều Quang Trung Stack số nguyên – Sử dụng mảng bool IsEmpty(const STACK &s) { if (s.StkTop==-1) return true; return false; } 12 GV. Thiều Quang Trung Stack số nguyên – Sử dụng mảng bool IsFull(const STACK &s) { if (s.StkTop==s.StkMax-1) return true; return false; } 13 GV. Thiều Quang Trung 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; } 14 GV. Thiều Quang Trung 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; } 15 GV. Thiều Quang Trung 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) 16 GV. Thiều Quang Trung 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 ? ? 17 GV. Thiều Quang Trung Stack – Sử dụng DSLK 9 7 4  N StkCnt StkTop 7 Data Link 9 Data Link  4 Data Link 18 GV. Thiều Quang Trung Stack – Sử dụng DSLK • Cấu tạo đầu stack • Cấu tạo một phần tử N StkCnt StkTop Data Link stack StkCnt StkTop end stack node Data Link end node 19 GV. Thiều Quang Trung 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; }; 20 GV. Thiều Quang Trung Stack – Sử dụng DSLK • 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 = ? N StkCnt StkTop 7 Data Link 4 21 GV. Thiều Quang Trung Stack số nguyên – Sử dụng DSLK void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } 22 GV. Thiều Quang Trung Stack số nguyên – Sử dụng DSLK bool IsEmpty(const STACK &s) { if (s.StkTop == NULL) return true; return false; } 23 GV. Thiều Quang Trung 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; } 24 GV. Thiều Quang Trung Stack số nguyên – Sử dụng DSLK bool Push(STACK &s, int newitem) { if (IsFull(s)) return false; STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true; } N StkCnt StkTop 7 Data Link 4 25 GV. Thiều Quang Trung Stack số nguyên – Sử dụng DSLK bool Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return false; STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; s.StkTop = s.StkTop->pNext; delete temp; s.StkCount--; return true; } N StkCnt StkTop 7 Data Link 4 Data Link temp outitem = 4 26 GV. Thiều Quang Trung 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 • 27 GV. Thiều Quang Trung 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 28 GV. Thiều Quang Trung 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 (0,4) 1 5 4 7 3 0 1 2 3 4 i j t 3 5 1 (3,4) 5 7 Stack rỗng Stop 29 GV. Thiều Quang Trung Hàng đợi Queue Phòng vé 30 GV. Thiều Quang Trung 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) 31 GV. Thiều Quang Trung 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 32 GV. Thiều Quang Trung Queue • Minh họa thao tác EnQueue • Minh họa thao tác DeQueue 33 GV. Thiều Quang Trung 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 34 GV. Thiều Quang Trung 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 35 GV. Thiều Quang Trung Queue – 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 36 GV. Thiều Quang Trung Queue số nguyên – Sử dụng mảng typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 37 GV. Thiều Quang Trung 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ả” • 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 = 6 QFront = 1 QRear = 6 38 GV. Thiều Quang Trung Queue số nguyên – Sử dụng mảng • Xử lý mảng như một danh sách liên kết vòng 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 39 GV. Thiều Quang Trung Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 QMax 7 QNumItems 5 QFront 1 QRear 5 VD: Cho queue như sau Queue số nguyên – Sử dụng mảng 40 GV. Thiều Quang Trung 1. Thêm giá trị 123 vào hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 1 QRear 6 41 GV. Thiều Quang Trung 2. Lấy một phần tử khỏi hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 5 QFront 2 QRear 6 42 GV. Thiều Quang Trung 3. Thêm giá trị 456 vào hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 456 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 2 QRear 0 43 GV. Thiều Quang Trung 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; } 44 GV. Thiều Quang Trung Queue số nguyên – Sử dụng mảng bool IsEmpty(QUEUE q) { if (q.QNumItems == 0) return true; return false; } 45 GV. Thiều Quang Trung Queue số nguyên – Sử dụng mảng bool IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return true; return false; } 46 GV. Thiều Quang Trung 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; } 47 GV. Thiều Quang Trung 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; } 48 GV. Thiều Quang Trung 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; } 49 GV. Thiều Quang Trung 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; } 50 GV. Thiều Quang Trung 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 51 GV. Thiều Quang Trung Queue – Sử dụng DSLK typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 52 GV. Thiều Quang Trung 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); 53 GV. Thiều Quang Trung Queue – Sử dụng DSLK bool InitQueue(QUEUE &q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return true; } 54 GV. Thiều Quang Trung Queue – Sử dụng DSLK bool IsEmpty(const QUEUE& q) { return (q.NumItems==0); } 55 GV. Thiều Quang Trung Queue – Sử dụng DSLK bool IsFull(const QUEUE &q) { PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false; } 56 GV. Thiều Quang Trung 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; } 57 GV. Thiều Quang Trung 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; } 58 GV. Thiều Quang Trung 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 59 GV. Thiều Quang Trung Tính giai thừa • Định nghĩa không đệ qui: – n! = n * (n-1) * * 1 • Định nghĩa đệ qui: n! = 1 nếu n=0 n * (n-1)! nếu n>0 • Mã C++: int factorial(int n) { if (n==0) return 1; else return (n * factorial(n - 1)); } 60 GV. Thiều Quang Trung Thi hành hàm tính giai thừa n=2 2*factorial(1) factorial (2) n=1 1*factorial(0) factorial (1) n=0 return 1; factorial (0) 1 1 6 2 n=3 3*factorial(2) factorial (3) 61 GV. Thiều Quang Trung Trạng thái hệ thống khi thi hành hàm tính giai thừa factorial(3) factorial(3) factorial(2) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(1) factorial(0) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(3) t 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) Stack hệ thống Thời gian hệ thống t 62 GV. Thiều Quang Trung 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ỏ 63 GV. Thiều Quang Trung 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 64 GV. Thiều Quang Trung 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); } } 65 GV. Thiều Quang Trung Bài toán Tháp Hà nội – Thi hành 66 GV. Thiều Quang Trung Bài toán Tháp Hà nội – Cây đệ qui 67 GV. Thiều Quang Trung 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. 68 GV. Thiều Quang Trung Đệ 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. 69 GV. Thiều Quang Trung Khử đệ qui đuôi hàm giai thừa • Giải thuật: product=1 for (int count=1; count < n; count++) product *= count; 70 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)); } 71 GV. Thiều Quang Trung Dãy số Fibonacci – Cây thi hành Đã tính rồi 72 GV. Thiều Quang Trung 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; } 73 GV. Thiều Quang Trung GV: Thiều Quang Trung 74