ððạại Hi Họọc Sư Ph c Sư Phạạm Tp. H m Tp. Hồồ ChChíí MinhMinh

Nội dung

CCẤẤU TRU TRÚÚC DC DỮỮ LILIỆỆU 1 U 1

1. ðịnh nghĩa 2. Các phép toán trên mảng 3. Stack 4. Queue

Chương 3: Danh sách ñặặặặc (Mảảảảng)

2. Các thao tác xử lý cơ bản trên mảng

1. ðịnh nghĩa

• Mảng là tập hợp của các biến cùng kiểu ñược

Bài tập 1: Viết chương trình nhập vào một dãy số nguyên. In dãy số vừa nhập theo thứ tự ngược lại.

xếp liên tiếp nhau trong bộ nhớ trong.

Input : số lượng các phần tử trong dãy (N>0).

• Các loại mảng: – Mảng 1 chiều

N số nguyên.

• tên_mảng [số_phần_tử]

Output: N số nguyên theo thứ tự ngược lại.

– Mản nhiều chiều

• tên_mảng

ðối tượng dữ liệu : int N int a[]

[số_phần_tử_chiều_1][số_phần_tử_chiều_2]…[số_phần _tử_chiều_n]

Thao tác xử lý: Nhập số lượng phần tử

Nhập dãy số Xuất dãy số

2. Các thao tác xử lý cơ bản trên mảng

Bài tập 2: Viết chương trình nhập vào một dãy số nguyên dương. In ra dãy số sau khi chèn một phần tử nguyên dương vào một vị trí cho trước của dãy.

#include int n; int a[100]; void main(){

cout<<“n=”; cin>>n; for (int i=0; i>a[i];

Input : (cid:1) N là số lượng các phần tử. (cid:1) N số nguyên dương (cid:1) X là giá trị cần chèn (cid:1) K là vị trí cần chèn Output: (cid:1) Dãy số sau khi chèn

ðối tượng dữ liệu: (cid:1) int N, X, K (cid:1) int A[] Thao tác xử lý (cid:1) Nhập dãy số (cid:1) Chèn X vào dãy tại vị trí K (cid:1) Xuất dãy số

} for (i = n-1; i >= 0; i--)

cout<

}

2. Các thao tác xử lý cơ bản trên mảng

a) Thao tác chèn 1 phần tử vào mảng

2

3

6

7

Bài tập 3: Viết chương trình nhập vào một dãy số nguyên. In ra dãy số sau khi xóa một phần tử tại một vị trí cho trước của dãy.

K 4 1 1 6 7 3

0 4

N 8 5 ~985

9 ~

i

X

00

for ( i = N - 1; i >= K ; i--)

Input : (cid:1) N là số lượng các phần tử. (cid:1) N số nguyên dương (cid:1) K là vị trí cần xóa Output: (cid:1) Dãy số sau khi xóa

ðối tượng dữ liệu: (cid:1) int N, K (cid:1) int A[] Thao tác xử lý (cid:1) Nhập dãy số (cid:1) Chèn phần tử tại vị trí K (cid:1) Xuất dãy số

a[i+1] = a[i]

Mô tả 1.Dời các phần tử từ vị trí N-1 ñến K về phía sau 1 ô 2.ðặt giá trị X vào vị trí thứ K 3.Tăng số lượng phần tử

a[K] = X; N = N +1

2. Các thao tác xử lý cơ bản trên mảng

b) Thao tác xóa 1 phần tử của mảng

Bài tập 4: Viết chương trình nhập vào một dãy số nguyên. In ra vị trí của giá trị X nhập vào từ bàn phím hoặc thông báo không tìm thấy.

0 4

3 2 1 1 6 7

9 ~

N 8 7 ~9 ~

K 4 6 5 3 5 8 i

for ( i = K; i <= N-2 ; i++)

a[i] = a[i+1];

trí của X hoặc thông

N = N -1;

Input : (cid:1) N là số lượng các phần tử. (cid:1) N số nguyên dương (cid:1) X là giá trị cần tìm Output: (cid:1) Vị báo không tìm thấy.

Mô tả 1.Dời các phần tử từ vị trí K+1 ñến N-1 về phía trước 1 ô 2.Giảm số lượng phần tử ñi 1

ðối tượng dữ liệu: (cid:1) int N, X (cid:1) int A[] Thao tác xử lý (cid:1) Nhập dãy số (cid:1) Tìm giá tri X (cid:1) Xuất thông tin tìm kiếm.

6 5 4 3 5 8

3 2 1 1 6 7

X=3 0 4

9 ~

6 5 4 3 5 8

3 2 1 1 6 7

X=3 0 4

9 ~

c) Thao tác tìm kiếm tuyến tính N 7 8 ~9 ~

c) Thao tác tìm kiếm tuyến tính N 7 8 ~9 ~

int linearSearch(int a[ ], int N, int X){

1. I = 0 (cid:2)(cid:2)(cid:2)(cid:2) N-1

for (int i=0; i

1.1 Nếu A[i] =X thì

– Print I – Dừng

if (a[i] == X) return i

} return -1;

Giải thuật Tiến hành so sánh x lần lượt với phần tử thứ 0, thứ 1,… của mảng cho ñến khi gặp khóa cần tìm, hoặc hết mảng mà không tìm thấy giá trị.

2. Nếu I=N thì print -1

}

6 5 4 3 5 8

3 2 1 1 6 7

X=3 0 4

9 ~

6 5 4 0 5 8

3 2 1 1 6 7

X=3 0 4

9 ~

c) Thao tác tìm kiếm tuyến tính N 8 7 ~9 ~

c) Thao tác tìm kiếm tuyến tính N 8 7 ~9 3

int

linearSearch(int a[],

int N,

int

linearSearch(int a[],

int N,

I =0; A[N] = X

int X) {

int X) {

int i = 0;

int i = 0;

i.

a[N] = X;

while (i

1. 2. Trong khi A[i] !=x thì tăng

While (a[i] != X) i++;

3. Nếu I=N:

//return i==n?-1:i;

if ( i == N ) return -1;

if ( i == N )

Không tìm thấy.

else return i;

return -1;

Ngược lại:

}

else

Tìm thấy tại vị trí I

return i;

}

1. I =0; 2. Trong khi I

c) Thao tác tìm kiếm nhị phân

c) Thao tác tìm kiếm nhị phân

X=5

X=5

L 0 1

3 2 1 3 5 6

R 6 5 4 7 8 9

N 7 8 ~9 ~

L 0 1

3 2 1 3 5 6

R 6 5 4 7 8 9

9 ~

N 7 8 ~9 ~

Bước 1: left = 0; right = N-1; //tìm trên tất cả các phần tử Bước 2: mid = (left + right)/2; //lấy mốc ñể so sánh

So sánh a[mid] với x có 3 khả năng - x=a[mid] : tìm thấy. Dừng - xa[mid] : right = mid -1; //tìm tiếp trong dãy amid+1 …aright

Bước 3: Nếu left <= right. Quay lại bước 2

Ngược lại: Dừng. //ñã xét hết tất cả các phần tử

Giải thuật Tại mỗi bước tiến hành so sánh X với phần tử nằm giữa của dãy tìm kiếm hiện hành. Dựa vào kết quả so sánh này ñể quyết ñịnh giới hạn tìm kiếm ở bước kế tiếp là nữa trên hay nữa dưới của dãy hiện hành.

c) Thao tác tìm kiếm nhị phân

int BinarySearch (int a[],int n, int x) {

X=4

L 0 1

3 2 1 3 5 6

R 6 5 4 7 8 9

N 7 8 ~9 ~

int left = 0; int right = n-1; while(left<=right){

Bước 1: left = 0; right = N-1; //tìm trên tất cả các phần tử Bước 2: mid = (left + right)/2; //lấy mốc ñể so sánh

int mid = (left + right)/2; if (x == a[mid]) return mid; if (x < a[mid]) right = mid - 1; if (x > a[mid]) left = mid + 1;

So sánh a[mid] với x có 3 khả năng - x=a[mid] : tìm thấy. Dừng - xa[mid] : left= mid +1; //tìm tiếp trong dãy amid+1 …aright

} return -1;

Bước 3: Nếu left <= right. Quay lại bước 2

Ngược lại: Dừng. //ñã xét hết tất cả các phần tử

}

Bài tập

Bài tập

1. Viết chương trình tìm phần tử lớn nhất trong một

dãy số nguyên.

5. ðể sắp xếp dãy số nguyên theo tứ tự tăng dần người ta lần lượt tìm giá trị nhỏ nhất ñặt vào ñầu dãy, giá trị nhỏ thứ 2 ñặt vào vị trí thứ 2, và tương tự như thế cho ñến hết dãy. Viết chương trình sắp xếp dãy số nguyên theo ý tưởng trên.

2. Viết chương trình tìm tất cả các số nguyên tố trong một dãy số nguyên dương nhập vào từ bàn phím. 3. Viết chương trình tìm dãy con tăng dần dài nhất

trong dãy số nguyên nhập vào từ bàn phím.

4. Viết chương trình nhập vào một dãy ký tự. In ra số

lần xuất hiện của các ký tự trong dãy.

6. Viết chương trình quản lý danh bạ ñiện thoại với các thông tin : Số thứ tự, họ và tên, số ñiện thoại,ñịa chỉ email. Chương trình ñảm bảo các chức năng sau: a. Nhập thông tin vào danh bạ b. Danh bạ phải ñược sắp tăng dần theo số thứ tự c. Xuất danh bạ d. Tìm kiếm thông tin dựa vào “họ và tên” hoặc “ñịa chỉ

email

5. Một số tự nhiên ñược gọi là Palindrom khi các chữ số của nó ñược viết theo thứ tự ngược lại sẽ tạo thành số mới bằng chính số ñó (ví dụ: 4884, 321123, 15651). Hãy kiểm tra số tự nhiên nhập vào từ bàn phím có phải là số Palindrom không?

e. Xóa thông tin dựa vào số thứ tự cho trước.

3. Stack

Ví dụ về stack

• Stack rỗng:

• ðẩy (push) Q vào:

Q

A

• Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ ñược thực hiện tại một ñầu (gọi là ñỉnh – top của stack).

Q

• ðẩy A vào:

A

Q

• Là một dạng vào sau ra trước – LIFO (Last In First Out)

• Lấy (pop) ra một => ñược A:

Q

• Lấy ra một => ñược Q và stack rỗng:

Ứng dụng: ðảo ngược danh sách

Các phép toán trên ngăn xếp

• Yêu cầu: ðảo ngược một danh sách nhập vào • Giải thuật:

1. Lặp lại n lần

• empty(A): kiểm tra ngăn xếp có rỗng? • length(A): Cho biết số phần tử ngăn xếp. • push(A, x): Thêm phần tử x vào ngăn xếp A. • pop(A): Loại phần tử ở ñỉnh ngăn xếp. • getTop(A): Lấy phần tử ở ñỉnh ngăn xếp.

1.1. Nhập vào một giá trị 1.2. ðẩy nó vào stack 2. Lặp khi stack chưa rỗng

2.1. Lấy một giá trị từ stack 2.2. In ra

ðảo ngược danh sách – Ví dụ

ðảo ngược danh sách – Mã C++

sử dụng STL (Standard Template Library)

khai báo một stack có kiểu dữ liệu của các phân tử bên trong là double

Nhập 1 Nhập 5 Nhập 7 Nhập 3 Cần nhập 4 số vào Ban ñầu #include using namespace std;

3 7 7

ñẩy một số vào trong stack

5 1 5 1 5 1 1

kiểm tra xem stack có khác rỗng không

lấy giá trị trên ñỉnh của stack ra, stack không ñổi

int main( ) { int n; double item; stack numbers; cout << "Bao nhieu so nhap vao? " cin >> n; for (int i = 0; i < n; i++) { Lấy ra => 3 Lấy ra => 7 Lấy ra => 5 Lấy ra => 1 Stack ñã rỗng Ngừng cin >> item; numbers.push(item);

7 3 7 } while (!numbers.empty( )) {

lấy giá trị trên ñỉnh của stack ra khỏi stack, ñỉnh của stack bây giờ là giá trị kế tiếp

cout << numbers.top( ) << " "; numbers.pop( ); 5 1 5 1 5 1 1 } }

Kiểu trừu tượng (abstract data type)

Stack trừu tượng

• ðN1: Một kiểu (type)

• Một stack kiểu T:

– Một dãy hữu hạn kiểu T – Một số tác vụ:

– một tập hợp – mỗi thành phần của tập hợp này là các giá trị (value) – Ví dụ: int, float, char là các kiểu cơ bản

• 1. Khởi tạo stack rỗng (create) • 2. Kiểm tra rỗng (empty) • 3. ðẩy một giá trị vào trên ñỉnh của stack (push) • 4. Bỏ giá trị ñang có trên ñỉnh của stack (pop) • 5. Lấy giá trị trên ñỉnh của stack, stack không ñổi (top)

• ðN2: Một dãy của kiểu T – có chiều dài bằng 0 là rỗng – có chiều dài n (n>=1): bộ thứ tự (Sn-1, t) • Sn-1: dãy có chiều dài n-1 thuộc kiểu T •

t là một giá trị thuộc kiểu T.

Thiết kế stack

Thiết kế các phương thức

enum Error_code {fail, success, overflow, underflow};

template bool Stack::empty() const; Pre: Không có Post: Trả về giá trị true nếu stack hiện tại là rỗng, ngược lại thì trả về false

template class Stack { public:

template Error_code Stack::push(const Entry &item); Pre: Không có Post: Nếu stack hiện tại không ñầy, item sẽ ñược thêm vào ñỉnh của stack.

Ngược lại trả về giá trị overflow của kiểu Error_code và stack không ñổi.

//constructor //kiểm tra rỗng //ñẩy item vào //bỏ phần tử trên ñỉnh //lấy giá trị trên ñỉnh

template Error_code Stack::pop() const; Pre: Không có Post: Nếu stack hiện tại không rỗng, ñỉnh của stack hiện tại sẽ bị hủy bỏ.

Ngược lại trả về giá trị underflow của kiểu Error_code và stack không ñổi.

Stack(); bool empty() const; Error_code push(const Entry &item); Error_code pop(); Error_code top(Entry &item); //khai báo một số phương thức cần thiết khác private: //khai báo dữ liệu và hàm phụ trợ chỗ này };

template Error_code Stack::top(Entry &item) const; Pre: Không có Post: Nếu stack hiện tại không rỗng, ñỉnh của stack hiện tại sẽ ñược chép vào tham

biến item. Ngược lại trả về giá trị fail của kiểu Error_code.

Hiện thực stack liên tục

Khai báo stack liên tục

const int maxstack = 10; //small number for testing

template class Stack { public:

Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item); private:

int count; Entry entry[maxstack]; };

ðẩy một phần tử vào stack

Bỏ phần tử trên ñỉnh stack

• Giải thuật:

• Giải thuật:

1. Nếu còn phần tử trong stack 1.1. Giảm vị trí ñỉnh ñi 1 1.2. Giảm số phần tử ñi 1

1. Nếu còn chỗ trống trong stack 1.1. Tăng vị trí ñỉnh lên 1 1.2. Chứa giá trị vào vị trí ñỉnh của stack 1.3. Tăng số phần tử lên 1

top 7 7 5 top 5 count=2 count=3 1 count=3 count=2 1

Thêm/Bỏ phần tử - Mã C++

Lấy giá trị trên ñỉnh stack

• Giải thuật:

template Error_code Stack:: push(const Entry &item) { if (count >= maxstack)

1. Nếu còn phần tử trong stack

return overflow;

1.1. Trả về giá trị tại vị trí ñỉnh

• Mã C++:

else entry[count++] = item; return success; }

template Error_code Stack:: top(Entry &item) {

if (count == 0)

return underflow;

else

template Error_code Stack:: pop() { if (count == 0) return underflow; else

item = entry[count - 1];

return success;

count--; return success;

}

}

Ký pháp Ba Lan ñảo – Thiết kế chức năng

Ký pháp Ba Lan ñảo

• Mô tả bài toán:

• Tập lệnh:

– Các toán hạng ñược ñọc vào trước và ñẩy vào

stack

– ‘?’: ñọc một giá trị rồi ñẩy vào stack – Toán tử ‘+’, ‘-’, ‘*’, ‘/’: lấy 2 giá trị trong stack,

tính toán và ñẩy kết quả vào stack

– Khi ñọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán với toán tử này, rồi ñẩy kết quả vào stack

• Thiết kế phần mềm:

– Toán tử ‘=’: in ñỉnh của stack ra – ‘q’: kết thúc chương trình

– Cần một stack ñể chứa toán hạng – Cần hàm get_command ñể nhận lệnh từ người

dùng

– Cần hàm do_command ñể thực hiện lệnh

Ký pháp Ba Lan ñảo – Ví dụ

Ký pháp Ba Lan ñảo - Hàm get_command

char get command( ) {

Tính toán biểu thức: 3 5 + 2 * =

char command; bool waiting = true; cout << "Select command and press < Enter > :"; while (waiting) {

5 8 3 3 5 3

ðẩy 8 vào Ban ñầu Toán tử ? Nhập vào 3 Toán tử ? Nhập vào 5

cin >> command; command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || command == ‘−’|| command == ‘*’ || command == ‘/’ || command == ‘q’) waiting = false;

Toán tử + Lấy ra 5 và 3 Tính 3 + 5 => 8

else {

cout << "Please enter a valid command:" << endl << "[?]push to stack [=]print top" <

}

2 8 2 8 16 16 16

ðẩy vào 16 Toán tử ? Nhập vào 2 Toán tử = In ra 16

} return command;

}

Toán tử * Lấy ra 2 và 8 Tính 8 * 2 => 16

Ký pháp Ba Lan ñảo - Giải thuật tính toán

Ký pháp Ba Lan ñảo - Toán tử cộng

Algorithm Op_process if (numbers.top(p) == underflow) cout << "Stack rỗng"; Input: toán tử op, stack chứa các toán hạng Output: stack chứa các toán hạng sau khi tính xong toán tử op else {

1. Nếu stack không rỗng

numbers.pop( ); if (numbers.top(q) == underflow) { cout << "Stack chỉ có 1 trị”; numbers.push(p); 1.1. Lấy ñỉnh stack ra thành p 1.2. Bỏ phần tử trên ñỉnh stack 1.3. Nếu stack rỗng } else { 1.3.1. ðẩy p ngược lại 1.3.2. Báo lỗi và thoát numbers.pop( ); if (numbers.push(q + p) == overflow) cout << "Stack ñầy”; } 1.4. Lấy ñỉnh stack ra thành q 1.5. Bỏ phần tử trên ñỉnh stack 1.6. Tính toán (q op p) 1.7. ðẩy kết quả vào stack }

End Op_process

Ký pháp Ba Lan ñảo - Chương trình chính

Ký pháp Ba Lan ñảo - Hàm do_command

#include "stack.cpp" bool do_command(char command, Stack &numbers) {

double p, q; switch (command) { case '?’:

cout << "Enter a real number: " << flush; cin >> p; if (numbers.push(p) == overflow) //prototype void introduction( ); void instructions( ); char get_command( ); bool do_command(char command, Stack &numbers); cout << "Warning: Stack full, lost number" << endl; break; case '=‘: int main( ) { if (numbers.top(p) == underflow) cout << "Stack empty" << endl; else cout << p << endl; break;

Stack stored_numbers; introduction( ); instructions( ); while (do_command(get_command( ), stored_numbers)); // Add options for further user commands. case ‘q’: cout << "Calculation finished.\n"; return false; }

return true; } } //implementation …

4. Queue

Queue trừu tượng

• Một queue kiểu T:

• Một queue là một cấu trúc dữ liệu mà các phép toán thực hiện ở 2 ñỉnh, một ñỉnh gọi là ñầu hàng, một ñỉnh gọi là cuối hàng.

– Một dãy hữu hạn kiểu T – Một số tác vụ:

• Phần tử vào trước sẽ ra trước – FIFO (First In First

Out)

• 1. Khởi tạo queue rỗng (create) • 2. Kiểm tra rỗng (empty) • 3. Thêm một giá trị vào cuối của queue (append) • 4. Bỏ giá trị ñang có ở ñầu của queue (serve) • 5. Lấy giá trị ở ñầu của queue, queue không ñổi

(retrieve)

Thiết kế queue

Thiết kế các phương thức

enum Error_code {fail, success, overflow, underflow};

template bool Queue::empty() const; Pre: Không có Post: Trả về giá trị true nếu queue hiện tại là rỗng, ngược lại thì trả về false

template class Queue { public:

template Error_code Queue::append(const Entry &item); Pre: Không có Post: Nếu queue hiện tại không ñầy, item sẽ ñược thêm vào cuối của queue.

Ngược lại trả về giá trị overflow của kiểu Error_code và queue không ñổi.

//bỏ 1 phần tử ở ñầu //lấy giá trị ở ñầu

template Error_code Queue::serve() const; Pre: Không có Post: Nếu queue hiện tại không rỗng, ñầu của queue hiện tại sẽ bị hủy bỏ.

Ngược lại trả về giá trị underflow của kiểu Error_code và queue không ñổi.

//constructor Queue(); bool empty() const; //kiểm tra rỗng Error_code append(const Entry &item); //ñẩy item vào Error_code serve(); Error_code retrieve(Entry &item); //khai báo một số phương thức cần thiết khác private: //khai báo dữ liệu và hàm phụ trợ chỗ này };

template Error_code Queue::retrieve(Entry &item) const; Pre: Không có Post: Nếu queue hiện tại không rỗng, ñầu của queue hiện tại sẽ ñược chép vào tham

biến item. Ngược lại trả về giá trị underflow của kiểu Error_code.

Tính thừa hưởng

Mở rộng queue

• Dùng tính thừa hưởng:

– Extended_queue có ñầy ñủ các thành phần của Queue – Thêm vào ñó các thành phần riêng của mình

• Có thêm các tác vụ: – Kiểm tra ñầy (full) – Tính kích thước (size) – Giải phóng queue (clear) – Lấy giá trị ở ñầu và bỏ ra khỏi queue (serve_and_retrieve)

• Mã C++:

template class Extended_queue: public Queue { public:

Có các khả năng public, protected, private

bool full( ) const; int size( ) const; void clear( ); Error_code serve_and_retrieve(Entry &item);

};

Queue là array vòng (circular array)

Queue liên tục

• Dùng một array: Có xu hướng dời về cuối array • Hai cách hiện thực ñầu tiên:

– Khi lấy một phần tử ra thì ñồng thời dời hàng lên một vị

trí.

A B C D B C D B C D E

– Chỉ dời hàng về ñầu khi cuối hàng không còn chỗ

Ban ñầu Thêm vào 1 phần tử Lấy ra 1 phần tử: dời tất cả về trước

A B C D B C D B C D E

Ban ñầu Lấy ra 1 phần tử

Thêm vào 1 phần tử: dời tất cả về trước ñể trống chỗ thêm vào

Array vòng với ngôn ngữ C++

ðiều kiện biên của queue vòng

• Xem array như là một vòng:

– phần tử cuối của array nối với phần tử ñầu của

array

• Tính toán vị trí kề:

– i = ((i + 1) == max) ? 0 : (i + 1); – if ((i + 1) == max)

i = 0; i = i + 1;

else

– i = (i + 1) % max;

Một số cách hiện thực queue liên tục

Hiện thực queue liên tục

• Một array với front là phần tử ñầu và tất cả các phần

const int maxqueue = 10; // small value for testing

tử sẽ ñược dời lên khi lấy ra một phần tử.

• Một array có hai chỉ mục luôn tăng chỉ ñến phần tử

ñầu và cuối.

• Một array vòng có chỉ mục front và rear và một ô

template class Queue { public:

luôn trống.

• Một array vòng có chỉ mục front và rear và một cờ

Queue( ); bool empty( ) const; Error_code serve( ); Error_code append(const Entry &item); Error_code retrieve(Entry &item) const;

(flag) cho biết queue là ñầy (rỗng) chưa.

• Một array vòng với chỉ mục front và rear có các giá

protected:

trị ñặc biệt cho biết queue ñang rỗng.

• Một array vòng với chỉ mục front và rear và một số chứa

số phần tử của queue.

int count; int front, rear; Entry entry[maxqueue]; };

Khởi tạo và kiểm tra rỗng

Thêm một giá trị vào queue

• Khởi tạo:

• Giải thuật:

1. Nếu hàng ñầy

template Queue::Queue( ) {

1.1. Báo lỗi overflow

count = 0; rear = maxqueue − 1; front = 0;

}

2. Tính toán vị trí cuối mới theo array vòng 3. Gán giá trị vào vị trí cuối mới này 4. Tăng số phần tử lên 1 4. Báo success

• Kiểm tra rỗng:

Dùng biến count ñể biết số phần tử trong queue

front rear

template bool Queue::empty( ) const {

return count == 0;

D A B C

}

Loại một giá trị khỏi queue

Thêm/loại một giá trị – Mã C++

• Giải thuật:

1. Nếu hàng rỗng

1.1. Báo lỗi underflow

template Error_code Queue::append(const Entry &item) { if (count >= maxqueue) return overflow; count++; rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); entry[rear] = item; return success;

2. Tính toán vị trí ñầu mới theo array vòng 3. Giảm số phần tử ñi 1 3. Báo success

}

template Error_code Queue::serve() { front rear

A B C D if (count <= 0) return underflow; count−−; front = ((front + 1) == maxqueue) ? 0 : (front + 1); return success; }

Ứng dụng: Giả lập phi trường

Giả lập phi trường – Hàng ñợi

• Mô tả:

enum Runway_activity {idle, land, takeoff};

– 1. Sử dụng hàng ñợi runway cho việc cất và hạ cánh. – 2. Một máy bay có thể cất hoặc hạ cánh trong một ñơn vị

class Runway { public:

thời gian.

– 3. Tại một thời ñiểm, số máy bay ñến là ngẫu nhiên. – 4. Máy bay hạ cánh ñược ưu tiên trước máy bay cất cánh. – 5. Các máy bay chờ cất/hạ cánh ñược chứa vào các hàng

Runway(int limit); Error_code can_land(const Plane ¤t); Error_code can_depart(const Plane ¤t); Runway_activity activity(int time, Plane &moving); void shut_down(int time) const; private:

ñợi tương ứng và với số lượng giới hạn.

Extended queue landing; Extended queue takeoff; int queue_limit; … };

Giả lập phi trường – Hạ cánh

Giả lập phi trường – Xử lý

Error_code Runway :: can_land(const Plane ¤t) { Runway_activity Runway::activity(int time, Plane &moving) {

Error_code result; if (landing.size( ) < queue_limit) Runway_activity in_progress; if (!landing.empty( )) { result = landing.append(current); else result = fail; landing.retrieve(moving); in_progress = land; landing.serve( ); } else if (!takeoff.empty( )) { num_land_requests++; if (result != success) num_land_refused++; else takeoff.retrieve(moving); in_progress = takeoff; takeoff.serve( ); num_land_accepted++; } else return result; in_progress = idle; } return in_progress; }

Giả lập phi trường – Giả lập

Câu hỏi và thảo luận

for (int current_time = 0; current_time < end_time; current_time++) { int number_arrivals = variable.poisson(arrival_rate); for (int i = 0; i < number_arrivals; i++) {

Plane current_plane(flight_number++, current_time, arriving); if (small_airport.can_land(current_plane) != success)

current_plane.refuse( );

} int number_departures = variable.poisson(departure_rate); for (int j = 0; j < number_departures; j++) {

Plane current_plane(flight_number++, current_time, departing); if (small_airport.can_depart(current_plane) != success)

current_plane.refuse( );

} Plane moving_plane; switch (small_airport.activity(current_time, moving_plane)) { case land: moving_plane.land(current_time); break; case takeoff: moving_plane.fly(current_time); break; case idle: run_idle(current_time);

}

}

66