›
›

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

pdf 74 trang Đức Chiến 04/01/2024 630
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_5_kieu_ngan_xep_hang_d.pdf

Nội dung text: 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

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