Chương 4: Stack và Queue liên kết

Ấ

C U TRÚC D LI U VÀ I THU T GI

Ữ Ệ Ả

Ậ

Ch

ươ

ng 4: Stack và Queue liên k t ế

Con trỏ

ươ

ng 4: Stack và Queue liên k t ế

Bi u di n con tr b ng C++

ỏ ằ

ể

ễ

 Khai báo bi n:ế

ng:

 T o m i đ i t

ớ ố ượ

 H y b đ i t

ng:

 Item * item_ptr1, * item_ptr2; ạ  item_ptr1 = new Item; ỏ ố ượ ủ  delete item_ptr1;  S d ng: ử ụ  *item_ptr1 = 1378;  cout << Student_ptr -> StudentID;

 Con tr NULL: ỏ

 item_ptr2 = NULL;

ươ

ng 4: Stack và Queue liên k t ế

S d ng con tr trong C++

ử ụ

ỏ

ế

 Đ a ch c a bi n: ỉ ủ

ế

ị  Bi n: int_ptr = &x;  Array: arr_ptr = an_array;

 Dynamic array:

 Trong C++, array có th đ

ể ượ

c qu n lý nh m t con tr và ư ộ

ả

ỏ

c l ượ ạ

ng  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];

ươ

ng 4: Stack và Queue liên k t ế

Gán con tr trong C++ ỏ

Gán n i dung: bình th

ộ

ườ

Gán con tr : nguy hi m ỏ

ể

ươ

ng 4: Stack và Queue liên k t ế

Thi

ế ế

t k node liên k t ế

 C n:ầ

ữ ệ

ỏ ể ỏ ế

 D li u  Con tr đ tr đ n node sau  Constructor

ươ

ng 4: Stack và Queue liên k t ế

Thi

t k node liên k t b ng C++

ế ế

ế ằ

template struct Node {

// data members

// constructors

Entry entry; Node *next; Node( ); Node(Entry item, Node *add on = NULL);

ươ

ng 4: Stack và Queue liên k t ế

};

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

ươ

ng 4: Stack và Queue liên k t ế

p0 a b c

Stack liên k tế

ươ

ng 4: Stack và Queue liên k t ế

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;

ươ

ng 4: Stack và Queue liên k t ế

};

Thêm vào m t stack liên k t ế

ộ

 Gi

ả

ị ầ i c a stack ớ ớ ệ ạ ủ

 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 ỉ ế  3. Tr đ nh c a stack vào node m i ớ

i thu t ậ ạ ỏ ỏ ỉ ủ

new_top

new node

top_node

ươ

ng 4: Stack và Queue liên k t ế

old top middle last

B đ nh c a m t stack liên k t ế ộ

ỏ ỉ

ủ

 Gi

i thu t: ả ậ

đ nh c a stack ủ ỏ ể ữ ỉ

 1. Gán m t con tr đ gi ộ  2. Tr đ nh c a stack vào node ngay sau đ nh hi n t ỏ ỉ  3. Xóa node cũ đi

ủ ỉ i ệ ạ

top_node

old top middle old last

ươ

ng 4: Stack và Queue liên k t ế

old_top

ỏ ỉ

ủ

ộ

ế

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;

ươ

ng 4: Stack và Queue liên k t ế

}

S không an toàn con tr trong C++

ự

ỏ

 K t thúc bi n stack nh ng b nh còn l

ư ộ ớ i: ạ ế

ế  delete stack0;

stack0

 stack2 = stack1;

middle top last  Gán hai stack: c hai dùng chung m t vùng d li u ữ ệ ả ộ

stack2

top middle last

stack1

ươ

ng 4: Stack và Queue liên k t ế

top middle last

Đ m b o an toàn con tr trong C++

ỏ

ả

 Destructor:  S đ ọ ẽ ượ  Dùng xóa h t vùng d li u ế

c g i ngay tr c khi đ i t ng k t thúc th i gian s ng ố ượ ế ố ờ

 S đ

ướ ữ ệ

 Copy constructor: ẽ ượ tham trị

 Sao chép ngu n thành m t vùng d li u m i ớ

c g i khi kh i t o bi n lúc khai báo, ho c truy n d li u b ng ọ ở ạ ữ ệ ế ề ặ ằ

ữ ệ ộ ồ

 Assignment operator: ẽ ượ

 S đ ng này vào đ i t  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

c g i khi gán đ i t ố ượ ố ượ

ng khác ồ ọ ữ ệ ủ ờ ộ ồ

ươ

ng 4: Stack và Queue liên k t ế

d li u m i ớ ữ ệ

Xóa vùng d li u đang có ữ ệ

 Gi

ả

ậ

i thu t: 1. Trong khi stack ch a r ng ư ỗ 1.1. B đ nh c a stack

ỏ ỉ

ủ

 Mã C++:

while (!empty())

pop();

ươ

ng 4: Stack và Queue liên k t ế

Sao chép vùng d li u

ữ ệ

 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 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

m t con tr đuôi ch vào cu i danh sách m i ớ ữ ộ ồ ệ ớ ớ ữ ệ ừ

ộ ệ ạ

ạ 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 ớ

ỏ

ươ

ng 4: Stack và Queue liên k t ế

Sao chép vùng d li u – Ví d

ữ ệ

ụ

copy.top_node

a b c

copy_node

new_copy

new_top

ươ

ng 4: Stack và Queue liên k t ế

a b c

Sao chép vùng d li u – Mã C++

ữ ệ

i tr ỗ

ươ

ng 4: Stack và Queue liên k t ế

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(); top_node = new_top; //xóa r ng d li u hi n t c ữ ệ ệ ạ ướ // thay th d li u b ng danh sách m i. ớ ằ ế ữ ệ

Queue liên k tế

 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)

rear front

 Kh i t o r ng: gán c front và rear v NULL ả last

ở ạ ỗ

ề

middle front

ươ

ng 4: Stack và Queue liên k t ế

front rear

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;

ươ

ng 4: Stack và Queue liên k t ế

};

Thêm ph n t

ầ ử

vào m t queue liên k t ế

ộ

 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

i c l ượ ạ ố

ớ

3.1. N i node m i vào sau rear 3.2. rear chính là node m iớ

new_rear

new_last

rear front

ươ

ng 4: Stack và Queue liên k t ế

front middle last

B ph n t

ầ ử ỏ

kh i m t queue liên k t ế

ộ

ỏ

 Gi

i thu t: ả ậ

i front hi n t ộ i ệ ạ

l 1. Dùng m t con tr đ gi ỏ ể ữ ạ 2. N u queue có m t ph n t ầ ử ộ

ề

ế 2.1. Gán front và rear v NULL

3. Ng

3.1. Tr front đ n nút k sau i c l ượ ạ ỏ ế ế

4. Xóa nút cũ đi

rear

front

front middle last

ươ

ng 4: Stack và Queue liên k t ế

old_front

c a m t queue liên k t

ầ ử ủ

ộ

ế

Thêm/B ph n 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;

ươ

ng 4: Stack và Queue liên k t ế

}

Kích th

ướ ủ

c c a m t queue liên k t ế

ộ

 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

ầ ử

ế

ố

 Mã C++:

Node *window = front; int count = 0; while (window != NULL) { window = window->next; count++;

} return count;

ươ

ng 4: Stack và Queue liên k t ế

ng d ng: tính toán đa th c

Ứ

ứ

ụ

 Dùng l  Thi

ứ

ầ

ả

ệ ố ứ ự ả

gi m c a s mũ ủ

ố

i bài reverse Polish calculator ạ 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 ộ  Có th dùng queue

ể

ươ

ng 4: Stack và Queue liên k t ế

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 ứ ổ

front c a p và q thành p_term, q_term ư ỗ ủ

ớ ặ ủ

ỏ ơ ế ặ

ầ ử ầ

ố ạ

ế

1. Trong khi p và q ch a r ng 1.1. L y ph n t ầ ử ấ 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 ẩ ả đ u trong p (hoăc trong q) 1.2.2. B ph n t ỏ 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 ặ ế ả ẩ ộ

ươ

ng 4: Stack và Queue liên k t ế

End Equals_sum1

Ví d c ng hai đa th c b ng gi

ứ ằ

ụ ộ

ả

i thu t 1 ậ

p = 3x6 – 2x4 + x3 + 4

<3.0, 6> < -2.0, 4> <1.0, 3> <4.0, 0>

q = 5x5 + 2x4 + 4x2 + 2x

<5.0, 5> <2.0, 4> <4.0, 2> <2.0, 1>

p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4

<3.0, 6> <5.0, 5> <1.0, 3> <4.0, 2>

ươ

ng 4: Stack và Queue liên k t ế

<2.0, 1> <4.0, 0>

Mã C++ c ng hai đa th c 1

ứ

ộ

ươ

ng 4: Stack và Queue liên k t ế

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); }

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ứ Output: b c c a đa th c ứ ậ ủ

ế ứ ỗ ế ả ậ ế ơ ủ

đ u 1. N u đa th c r ng 1.1. Tr v -1 ả ề 2. Tr v b c c a ph n t ả ề ậ ủ ầ ử ầ ế ả

End Bac_da_thuc p và q ừ

ế ả

ươ

ng 4: Stack và Queue liên k t ế

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 ủ ậ ậ ế 1.1.1. L y t p thành term ấ ừ 1.1.2. Đ y term vào k t qu ẩ 1.2. N u b c c a q l n h n b c c a p ậ ủ ớ q thành term 1.2.1. L y t ấ ừ 1.2.2. Đ y term vào k t qu ẩ i c l 1.3. Ng ượ ạ 1.3.1. L y p_term, q_term t ấ 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

Ví d c ng hai đa th c b ng gi

ứ ằ

ụ ộ

ả

i thu t 2 ậ

-1 6 0 3 4

degree(p) = p = 3x6 – 2x4 + x3 + 4

1-1 degree(p) = 5 2 4

<3.0, 6> < -2.0, 4> <1.0, 3> <4.0, 0>

q = 5x5 + 2x4 + 4x2 + 2x

<5.0, 5> <2.0, 4> <4.0, 2> <2.0, 1>

p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4

<3.0, 6> <5.0, 5> <1.0, 3> <4.0, 2>

ươ

ng 4: Stack và Queue liên k t ế

<2.0, 1> <4.0, 0>

Mã C++ c ng hai đa th c 2

ứ

ộ

ươ

ng 4: Stack và Queue liên k t ế

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); } } }