Bài giảng cấu trúc dữ liệu và thuật toán - Chương 4: Stack và Quêu liên kết

Nội dung text: Bài giảng cấu trúc dữ liệu và thuật toán - Chương 4: Stack và Quêu liên kết

1. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 4: Stack và Queue liên kết
2. Con trỏ Chương 4: Stack và Queue liên kết 2
3. Biểu diễn con trỏ bằng C++ n Khai báo biến: ¨ Item * item_ptr1, * item_ptr2; n Tạo mới đối tượng: ¨ item_ptr1 = new Item; n Hủy bỏ đối tượng: ¨ delete item_ptr1; n Sử dụng: ¨ *item_ptr1 = 1378; ¨ cout StudentID; n Con trỏ NULL: ¨ item_ptr2 = NULL; Chương 4: Stack và Queue liên kết 3
4. Sử dụng con trỏ trong C++ n Địa chỉ của biến: ¨ Biến: int_ptr = &x; ¨ Array: arr_ptr = an_array; n Dynamic array: ¨ Trong C++, array có thể được quản lý như một con trỏ và ngược lại ¨ Ví dụ: int arr[3] = {0, 1, 2, 3}; int *arr_ptr = arr; //in ra 0 – 1 – 2 cout << *arr_ptr << “ - ” << *(arr_ptr + 1) << “ - ” << arr_ptr[2]; Chương 4: Stack và Queue liên kết 4
5. Gán con trỏ trong C++ Gán nội dung: bình thường Gán con trỏ: nguy hiểm Chương 4: Stack và Queue liên kết 5
6. Thiết kế node liên kết n Cần: ¨ Dữ liệu ¨ Con trỏ để trỏ đến node sau ¨ Constructor Chương 4: Stack và Queue liên kết 6
7. Thiết kế node liên kết bằng C++ template struct Node { Entry entry; // data members Node *next; Node( ); // constructors Node(Entry item, Node *add on = NULL); }; Chương 4: Stack và Queue liên kết 7
8. Ví dụ với node liên kết Node first_node(‘a’); Node *p0 = &first_node; Node *p1 = new Node (‘b’); p0->next = p1; Node *p2 = new Node (‘c’, p0); p1->next = p2; p1 p2 first_node p0 a b c Chương 4: Stack và Queue liên kết 8
9. Stack liên kết Chương 4: Stack và Queue liên kết 9
10. Khai báo stack liên kết template class Stack { public: Stack( ); bool empty( ) const; Error_code push(const Entry &item); Error_code pop( ); Error_code top(Entry &item) const; Stack(const Stack ©); ~Stack(); void operator=(const Stack ©); protected: Node *top_node; }; Chương 4: Stack và Queue liên kết 10
11. Thêm vào một stack liên kết n Giải thuật ¨ 1. Tạo ra một node mới với giá trị cần thêm vào ¨ 2. Trỏ nó đến đỉnh hiện tại của stack ¨ 3. Trỏ đỉnh của stack vào node mới new_top new node top_node old top middle last Chương 4: Stack và Queue liên kết 11
12. Bỏ đỉnh của một stack liên kết n Giải thuật: ¨ 1. Gán một con trỏ để giữ đỉnh của stack ¨ 2. Trỏ đỉnh của stack vào node ngay sau đỉnh hiện tại ¨ 3. Xóa node cũ đi top_node old top middle old last old_top Chương 4: Stack và Queue liên kết 12
13. Thêm/Bỏ đỉnh của một stack liên kết – Mã C++ template Error_code push(const Entry &item) { Node *new_top = new Node (item, top_node); if (new_top == NULL) return overflow; top_node = new_top; } template Error_code pop( ) { Node *old_top = top_node; if (top_node == NULL) return underflow; top_node = old_top->next; delete old_top; } Chương 4: Stack và Queue liên kết 13
14. Sự không an toàn con trỏ trong C++ n Kết thúc biến stack nhưng bộ nhớ còn lại: ¨ delete stack0; stack0 n Gán hai stack: cả haitop dùng chungmiddle một vùng dữ lastliệu ¨ stack2 = stack1; stack2 top middle last stack1 top middle last Chương 4: Stack và Queue liên kết 14
15. Đảm bảo an toàn con trỏ trong C++ n Destructor: ¨ Sẽ được gọi ngay trước khi đối tượng kết thúc thời gian sống ¨ Dùng xóa hết vùng dữ liệu n Copy constructor: ¨ Sẽ được gọi khi khởi tạo biến lúc khai báo, hoặc truyền dữ liệu bằng tham trị ¨ Sao chép nguồn thành một vùng dữ liệu mới n Assignment operator: ¨ Sẽ được gọi khi gán đối tượng này vào đối tượng khác ¨ Xóa vùng dữ liệu của đích và đồng thời sao chép nguồn thành một vùng dữ liệu mới Chương 4: Stack và Queue liên kết 15
16. Xóa vùng dữ liệu đang có n Giải thuật: 1. Trong khi stack chưa rỗng 1.1. Bỏ đỉnh của stack n Mã C++: while (!empty()) pop(); Chương 4: Stack và Queue liên kết 16
17. Sao chép vùng dữ liệu n Giải thuật: 1. Tạo một đỉnh của danh sách mới với dữ liệu của đỉnh nguồn 2. Giữ một con trỏ đuôi chỉ vào cuối danh sách mới 2. Duyệt qua danh sách nguồn 2.1. Tạo một node mới với dữ liệu từ node nguồn hiện tại 2.2. Nối vào cuối danh sách mới 2.3. Con trỏ đuôi là node mới Chương 4: Stack và Queue liên kết 17
18. Sao chép vùng dữ liệu – Ví dụ copy.top_node a b c copy_node new_copy new_top a b c Chương 4: Stack và Queue liên kết 18
19. Sao chép vùng dữ liệu – Mã C++ Node *new_top, *new_copy, *copy_node = copy.top_node; if (copy_node == NULL) new_top = NULL; else { // Sao chép vùng dữ liệu thành danh sách mới new_copy = new_top = new Node (copy_node->entry); while (copy_node->next != NULL) { copy_node = copy_node->next; new_copy->next = new Node (copy_node->entry); new_copy = new_copy->next; } } clear(); //xóa rỗng dữ liệu hiện tại trước top_node = new_top; // thay thế dữ liệu bằng danh sách mới. Chương 4: Stack và Queue liên kết 19
20. Queue liên kết n Thiết kế: ¨ Dùng hai con trỏ chỉ đến đầu và cuối của danh sách dữ liệu (front và rear) front rear ¨ Khởi tạo rỗngfront: gán cả frontmiddle và rear về NULLlast front rear Chương 4: Stack và Queue liên kết 20
21. Khai báo Queue liên kết template class Queue { public: Queue( ); bool empty( ) const; Error_code append(const Entry &item); Error_code serve( ); Error_code retrieve(Entry &item) const; ~Queue( ); Queue(const Queue &original); void operator = (const Queue &original); protected: Node *front, *rear; }; Chương 4: Stack và Queue liên kết 21
22. Thêm phần tử vào một queue liên kết n Giải thuật: 1. Tạo một node mới với dữ liệu cần thêm vào 2. Nếu queue đang rỗng 2.1. front và rear là node mới 3. Ngược lại new_rear 3.1. Nối node mới vào sau rear 3.2. rear chính là node mới new_last front rear front middle last Chương 4: Stack và Queue liên kết 22
23. Bỏ phần tử khỏi một queue liên kết n Giải thuật: 1. Dùng một con trỏ để giữ lại front hiện tại 2. Nếu queue có một phần tử 2.1. Gán front và rear về NULL 3. Ngược lại 3.1. Trỏ front đến nút kế sau 4. Xóa nút cũ đi rear front front middle last old_front Chương 4: Stack và Queue liên kết 23
24. Thêm/Bỏ phần tử của một queue liên kết – Mã C++ template Error_code append(const Entry &item) { Node *new_rear = new Node (item); if (new_rear == NULL) return overflow; if (rear == NULL) front = rear = new_rear; else { rear->next = new_rear; rear = new_rear; } return success; } template Error_code serve() { if (front == NULL) return underflow; Node *old_front = front; front = old_front->next; if (front == NULL) rear = NULL; delete old_front; return success; } Chương 4: Stack và Queue liên kết 24
25. Kích thước của một queue liên kết n Giải thuật: 1. Khởi tạo biến đếm là 0 2. Duyệt qua danh sách 2.1. Đếm tăng số phần tử lên 1 n Mã C++: Node *window = front; int count = 0; while (window != NULL) { window = window->next; count++; } return count; Chương 4: Stack và Queue liên kết 25
26. Ứng dụng: tính toán đa thức n Dùng lại bài reverse Polish calculator n Thiết kế cấu trúc dữ liệu cho đa thức: ¨ Một bản ghi có thành phần mũ và hệ số ¨ Một danh sách các bản ghi theo thứ tự giảm của số mũ ¨ Có thể dùng queue Chương 4: Stack và Queue liên kết 26
27. Giải thuật cộng hai đa thức 1 Algorithm Equals_sum1 Input: p,q là hai đa thức Output: đa thức tổng 1. Trong khi p và q chưa rỗng 1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term 1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q) 1.3. Ngược lại 1.3.1. Tính hệ số mới cho số hạng này 1.3.2. Đẩy vào kết quả 2. Nếu p (hoặc q) chưa rỗng 2.1. Đẩy toàn bộ p (hoặc q) vào kết quả End Equals_sum1 Chương 4: Stack và Queue liên kết 27
28. Ví dụ cộng hai đa thức bằng giải thuật 1 p = 3x6 – 2x4 + x3 + 4 q = 5x5 + 2x4 + 4x2 + 2x p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4 Chương 4: Stack và Queue liên kết 28
29. Mã C++ cộng hai đa thức 1 Term p_term, q_term; while (!p.empty( ) && !q.empty( )) { p.retrieve(p_term); q.retrieve(q_term); if (p_tem.degree > q_term.degree) { p.serve(); append(p_term); } else if (q_term.degree > p_term.degree) { q.serve(); append(q_term); } else { p.serve(); q.serve(); if (p_term.coefficient + q_term.coefficient != 0) { Term answer_term(p_term.degree, p_term.coefficient + q_term.coefficient); append(answer_term); } } } while (!p.empty()) { p.serve_and_retrieve(p_term); append(p_term); } while (!q.empty()) { q.serve_and_retrieve(q_term); append(q_term); } Chương 4: Stack và Queue liên kết 29
30. Giải thuật cộng hai đa thức 2 Algorithm Equals_sum2 Input: p,q là hai đa thức Output: đa thức tổng Algorithm Bac_da_thuc Input: đa thức 1. Trong khi p hoặc q chưa rỗng 1.1. Nếu bậc của p lớn hơn bậc của q Output: bậc của đa thức 1.1.1. Lấy từ p thành term 1. Nếu đa thức rỗng 1.1.2. Đẩy term vào kết quả 1.1. Trả về -1 1.2. Nếu bậc của q lớn hơn bậc của p 2. Trả về bậc của phần tử đầu 1.2.1. Lấy từ q thành term 1.2.2. Đẩy term vào kết quả 1.3. Ngược lại End Bac_da_thuc 1.3.1. Lấy p_term, q_term từ p và q 1.3.2. Tính tổng hai hệ số 1.3.3. Nếu hệ số kết quả khác không 1.3.3.1. Đẩy vào kết quả End Equals_sum2 Chương 4: Stack và Queue liên kết 30
31. Ví dụ cộng hai đa thức bằng giải thuật 2 p = 3x6 – 2x4 + x3 + 4 degree(p) = 6430-1 q = 5x5 + 2x4 + 4x2 + 2x degree(p) = 521-14 p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4 Chương 4: Stack và Queue liên kết 31
32. Mã C++ cộng hai đa thức 2 while (!p.empty( ) || !q.empty( )) { Term p_term, q_term; if (p.degree( ) > q.degree( )) { p.serve_and_retrieve(p_term); append(p_term); } else if (q.degree( ) > p.degree( )) { q.serve_and_retrieve(q_term); append(q_term); } else { p.serve_and_retrieve(p_term); q.serve_and_retrieve(q_term); if (p_term.coefficient + q_term.coefficient != 0) { Term answer_term(p_term.degree, p_term.coefficient + q_term.coefficient); append(answer_term); } } } Chương 4: Stack và Queue liên kết 32