Chương 3
Danh sách đặc (Mảng)
3.1. Định nghĩa
• Mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là
một tập hợp có thứ tự các giá trị có cùng cấu trúc
được lưu trữ liên tiếp nhau trong bộ nhớ.
• Mảng có thể một chiều hay nhiều chiều.
• Mảng hai chiều có thể coi là mảng một chiều trong
đó mỗi phần tử của nó là 1 mảng một chiều.
16/11/2008
Cấu trúc dữ liệu 1
2
3.1. Định nghĩa
• Mảng 1 chiều được khai báo như sau:
[];
VD:
int
a[100];
Hoặc vừa khai báo vừa gán giá trị khởi động cho mảng:
int a[5] = {1, 7, -2, 8, 19};
Hoặc:
int a[]= {1, 7, -2, 8, 19};
16/11/2008
Cấu trúc dữ liệu 1
3
3.1. Định nghĩa
Tương tự, có thể khai báo mảng 2 chiều hay nhiều
chiều như sau:
[][]...;
VD:
int
a[100][150];
Hoặc:
int
a[][] = {{1, 7, -3, 8, 19},
{4, 5, 2, 8, 9},
{21, 7, -45, -3, 4}};
16/11/2008
Cấu trúc dữ liệu 1
4
3.2. Các phép toán trên mảng
3.2.1. Khởi tạo mảng
khoi_tao(int a[], int &n)
void {
”;
int i;
cout<<“Cho biet so phan tu cua danh sach
cin>>n;
for(i=0;i
cout<<“Nhap phan tu thu ”<>a[i];
}
}
16/11/2008
Cấu trúc dữ liệu 1
5
3.2. Các phép toán trên mảng
3.2.2. Xuất mảng
void xuat(int a[],int n)
{
for(int i=0;i
cout<
cout<
}
16/11/2008
Cấu trúc dữ liệu 1
6
3.2. Các phép toán trên mảng
3.2.3. Chèn một phần tử vào mảng
Khi thêm một phần tử vào vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển ra sau một vị trí
chen(int a[], int &n)
void
{
int i,k,x;
cout<<“Nhap phan tu can chen ”;cin>>x;
cout<<“Nhap vi tri can chen ”;cin>>k;
for(i=n-1;i>=k-1;i--)
a[i+1]=a[i];
a[k-1]=x;
n++;
}
16/11/2008
Cấu trúc dữ liệu 1
7
3.2. Các phép toán trên mảng
3.2.4. Xóa một phần tử của mảng
Khi xóa một phần tử tại vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển về trước một vị trí
xoa(int a[], int &n)
void
{
int i,k;
cout<<“Nhap vi tri can xoa ”;cin>>k;
for(i=k;i
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước
khi sử dụng ⇒không phù hợp với các bài toán
chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một
phần tử bất kỳ trong mảng. Nếu bài toán mà
việc chèn phần tử và xóa phần tử diễn ra liên
tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước.
(cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt
mà phép thêm vào (PUSH) và phép lấy ra (POP)
đều thực hiện ở cùng một đầu gọi là đỉnh (TOP)
của stack. Do đó stack hoạt động theo nguyên tắc
“vào sau ra trước” LIFO. Stack có thể rỗng hoặc
chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Biểu diễn stack bằng mô hình mảng với các hàm:
- Push theo chế độ tăng trước
- Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt
struct
{
int data[100];
int top;
};
void Initial(Stack &s)
{
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int isEmpty(Stack s)
{
return (s.top==-1);
}
int isFull(Stack s)
{
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
void Push(Stack &s,int k)
{
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int Pop(Stack &s)
{
if (isEmpty(s))
return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Cú pháp của biểu thức: có 3 dạng
1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm:
- Chỉ dùng được cho các phép toán có hai toán hạng
- Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán
+ Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy
định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải
sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng
được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách
các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix):
giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh
sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép
toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD:
(*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại
bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất
kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh
mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như
dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách
các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong
biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu
thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc
biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giải thuật
Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt
đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy
theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau:
- Ký tự bắt đầu “$” luôn được đẩy vào stack
- Các ký tự là biến luôn được ghi ra, không cất vào stack
- Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ
được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký
tự
tại
đỉnh
stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Các tác vụ có mã số là:
1. Push
2. Pop và ghi ra
3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra
5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện
giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký
tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì
đạt được kết quả.
Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng
hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau.
Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự
mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được
đọc
Ký tự
đang đọc
Ký tự ở
đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt
đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một
khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải
thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức
được định giá
c
Toán
tử cự
trái
Toán
hạng
bên trái
Toán
hạng
bên phải
Kết quả
phép
toán
sau khi thực hiện
phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6
16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán
tử. Thực hiện lần lượt các bước sau:
B1: Đặt k=1
B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack
- Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai
toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái),
thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push
10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push
18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc
biệt mà phép thêm vào (PUSH) ở cuối danh
sách, qua con trỏ First, và phép lấy ra (POP) ở
đầu danh sách, qua con trỏ Last. Do đó, hàng đợi
hoạt động theo nguyên tắc “vào trước ra trước”
FIFO (First in – First out). Hàng đợi có thể rỗng
hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Biểu diễn queue bằng mảng với các biến first (đầu hàng
đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc
sau:
Khi first < last thì queue rỗng
- Hàm thêm một phần tử vào queue: Push với biến last
theo chế độ tăng trước.
- Hàm lấy một phần tử ra khỏi queue: Pop với biến first
theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt
struct
{
int data[100];
int first, last;
};
void Initial(Queue &q)
{
q.first = 0;
q.last=-1;
}
16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int isEmpty(Queue q)
{
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
cout<<“Nhap phan tu thu ”<>a[i];
}
}
16/11/2008
Cấu trúc dữ liệu 1
5
3.2. Các phép toán trên mảng
3.2.2. Xuất mảng
void xuat(int a[],int n)
{
for(int i=0;i
cout<
cout<
}
16/11/2008
Cấu trúc dữ liệu 1
6
3.2. Các phép toán trên mảng
3.2.3. Chèn một phần tử vào mảng
Khi thêm một phần tử vào vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển ra sau một vị trí
chen(int a[], int &n)
void
{
int i,k,x;
cout<<“Nhap phan tu can chen ”;cin>>x;
cout<<“Nhap vi tri can chen ”;cin>>k;
for(i=n-1;i>=k-1;i--)
a[i+1]=a[i];
a[k-1]=x;
n++;
}
16/11/2008
Cấu trúc dữ liệu 1
7
3.2. Các phép toán trên mảng
3.2.4. Xóa một phần tử của mảng
Khi xóa một phần tử tại vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển về trước một vị trí
xoa(int a[], int &n)
void
{
int i,k;
cout<<“Nhap vi tri can xoa ”;cin>>k;
for(i=k;i
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước
khi sử dụng ⇒không phù hợp với các bài toán
chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một
phần tử bất kỳ trong mảng. Nếu bài toán mà
việc chèn phần tử và xóa phần tử diễn ra liên
tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước.
(cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt
mà phép thêm vào (PUSH) và phép lấy ra (POP)
đều thực hiện ở cùng một đầu gọi là đỉnh (TOP)
của stack. Do đó stack hoạt động theo nguyên tắc
“vào sau ra trước” LIFO. Stack có thể rỗng hoặc
chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Biểu diễn stack bằng mô hình mảng với các hàm:
- Push theo chế độ tăng trước
- Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt
struct
{
int data[100];
int top;
};
void Initial(Stack &s)
{
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int isEmpty(Stack s)
{
return (s.top==-1);
}
int isFull(Stack s)
{
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
void Push(Stack &s,int k)
{
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int Pop(Stack &s)
{
if (isEmpty(s))
return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Cú pháp của biểu thức: có 3 dạng
1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm:
- Chỉ dùng được cho các phép toán có hai toán hạng
- Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán
+ Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy
định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải
sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng
được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách
các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix):
giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh
sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép
toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD:
(*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại
bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất
kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh
mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như
dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách
các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong
biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu
thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc
biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giải thuật
Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt
đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy
theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau:
- Ký tự bắt đầu “$” luôn được đẩy vào stack
- Các ký tự là biến luôn được ghi ra, không cất vào stack
- Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ
được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký
tự
tại
đỉnh
stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Các tác vụ có mã số là:
1. Push
2. Pop và ghi ra
3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra
5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện
giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký
tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì
đạt được kết quả.
Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng
hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau.
Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự
mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được
đọc
Ký tự
đang đọc
Ký tự ở
đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt
đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một
khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải
thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức
được định giá
c
Toán
tử cự
trái
Toán
hạng
bên trái
Toán
hạng
bên phải
Kết quả
phép
toán
sau khi thực hiện
phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6
16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán
tử. Thực hiện lần lượt các bước sau:
B1: Đặt k=1
B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack
- Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai
toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái),
thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push
10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push
18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc
biệt mà phép thêm vào (PUSH) ở cuối danh
sách, qua con trỏ First, và phép lấy ra (POP) ở
đầu danh sách, qua con trỏ Last. Do đó, hàng đợi
hoạt động theo nguyên tắc “vào trước ra trước”
FIFO (First in – First out). Hàng đợi có thể rỗng
hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Biểu diễn queue bằng mảng với các biến first (đầu hàng
đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc
sau:
Khi first < last thì queue rỗng
- Hàm thêm một phần tử vào queue: Push với biến last
theo chế độ tăng trước.
- Hàm lấy một phần tử ra khỏi queue: Pop với biến first
theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt
struct
{
int data[100];
int first, last;
};
void Initial(Queue &q)
{
q.first = 0;
q.last=-1;
}
16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int isEmpty(Queue q)
{
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
cout<
cout<
}
16/11/2008
Cấu trúc dữ liệu 1
6
3.2. Các phép toán trên mảng
3.2.3. Chèn một phần tử vào mảng
Khi thêm một phần tử vào vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển ra sau một vị trí
chen(int a[], int &n)
void
{
int i,k,x;
cout<<“Nhap phan tu can chen ”;cin>>x;
cout<<“Nhap vi tri can chen ”;cin>>k;
for(i=n-1;i>=k-1;i--)
a[i+1]=a[i];
a[k-1]=x;
n++;
}
16/11/2008
Cấu trúc dữ liệu 1
7
3.2. Các phép toán trên mảng
3.2.4. Xóa một phần tử của mảng
Khi xóa một phần tử tại vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển về trước một vị trí
xoa(int a[], int &n)
void
{
int i,k;
cout<<“Nhap vi tri can xoa ”;cin>>k;
for(i=k;i
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước
khi sử dụng ⇒không phù hợp với các bài toán
chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một
phần tử bất kỳ trong mảng. Nếu bài toán mà
việc chèn phần tử và xóa phần tử diễn ra liên
tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước.
(cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt
mà phép thêm vào (PUSH) và phép lấy ra (POP)
đều thực hiện ở cùng một đầu gọi là đỉnh (TOP)
của stack. Do đó stack hoạt động theo nguyên tắc
“vào sau ra trước” LIFO. Stack có thể rỗng hoặc
chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Biểu diễn stack bằng mô hình mảng với các hàm:
- Push theo chế độ tăng trước
- Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt
struct
{
int data[100];
int top;
};
void Initial(Stack &s)
{
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int isEmpty(Stack s)
{
return (s.top==-1);
}
int isFull(Stack s)
{
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
void Push(Stack &s,int k)
{
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int Pop(Stack &s)
{
if (isEmpty(s))
return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Cú pháp của biểu thức: có 3 dạng
1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm:
- Chỉ dùng được cho các phép toán có hai toán hạng
- Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán
+ Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy
định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải
sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng
được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách
các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix):
giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh
sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép
toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD:
(*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại
bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất
kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh
mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như
dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách
các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong
biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu
thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc
biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giải thuật
Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt
đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy
theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau:
- Ký tự bắt đầu “$” luôn được đẩy vào stack
- Các ký tự là biến luôn được ghi ra, không cất vào stack
- Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ
được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký
tự
tại
đỉnh
stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Các tác vụ có mã số là:
1. Push
2. Pop và ghi ra
3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra
5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện
giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký
tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì
đạt được kết quả.
Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng
hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau.
Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự
mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được
đọc
Ký tự
đang đọc
Ký tự ở
đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt
đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một
khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải
thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức
được định giá
c
Toán
tử cự
trái
Toán
hạng
bên trái
Toán
hạng
bên phải
Kết quả
phép
toán
sau khi thực hiện
phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6
16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán
tử. Thực hiện lần lượt các bước sau:
B1: Đặt k=1
B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack
- Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai
toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái),
thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push
10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push
18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc
biệt mà phép thêm vào (PUSH) ở cuối danh
sách, qua con trỏ First, và phép lấy ra (POP) ở
đầu danh sách, qua con trỏ Last. Do đó, hàng đợi
hoạt động theo nguyên tắc “vào trước ra trước”
FIFO (First in – First out). Hàng đợi có thể rỗng
hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Biểu diễn queue bằng mảng với các biến first (đầu hàng
đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc
sau:
Khi first < last thì queue rỗng
- Hàm thêm một phần tử vào queue: Push với biến last
theo chế độ tăng trước.
- Hàm lấy một phần tử ra khỏi queue: Pop với biến first
theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt
struct
{
int data[100];
int first, last;
};
void Initial(Queue &q)
{
q.first = 0;
q.last=-1;
}
16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int isEmpty(Queue q)
{
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
cout<
}
16/11/2008
Cấu trúc dữ liệu 1
6
3.2. Các phép toán trên mảng
3.2.3. Chèn một phần tử vào mảng
Khi thêm một phần tử vào vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển ra sau một vị trí
chen(int a[], int &n)
void
{
int i,k,x;
cout<<“Nhap phan tu can chen ”;cin>>x;
cout<<“Nhap vi tri can chen ”;cin>>k;
for(i=n-1;i>=k-1;i--)
a[i+1]=a[i];
a[k-1]=x;
n++;
}
16/11/2008
Cấu trúc dữ liệu 1
7
3.2. Các phép toán trên mảng
3.2.4. Xóa một phần tử của mảng
Khi xóa một phần tử tại vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển về trước một vị trí
xoa(int a[], int &n)
void
{
int i,k;
cout<<“Nhap vi tri can xoa ”;cin>>k;
for(i=k;i
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước
khi sử dụng ⇒không phù hợp với các bài toán
chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một
phần tử bất kỳ trong mảng. Nếu bài toán mà
việc chèn phần tử và xóa phần tử diễn ra liên
tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước.
(cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt
mà phép thêm vào (PUSH) và phép lấy ra (POP)
đều thực hiện ở cùng một đầu gọi là đỉnh (TOP)
của stack. Do đó stack hoạt động theo nguyên tắc
“vào sau ra trước” LIFO. Stack có thể rỗng hoặc
chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Biểu diễn stack bằng mô hình mảng với các hàm:
- Push theo chế độ tăng trước
- Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt
struct
{
int data[100];
int top;
};
void Initial(Stack &s)
{
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int isEmpty(Stack s)
{
return (s.top==-1);
}
int isFull(Stack s)
{
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
void Push(Stack &s,int k)
{
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int Pop(Stack &s)
{
if (isEmpty(s))
return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Cú pháp của biểu thức: có 3 dạng
1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm:
- Chỉ dùng được cho các phép toán có hai toán hạng
- Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán
+ Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy
định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải
sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng
được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách
các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix):
giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh
sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép
toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD:
(*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại
bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất
kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh
mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như
dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách
các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong
biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu
thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc
biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giải thuật
Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt
đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy
theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau:
- Ký tự bắt đầu “$” luôn được đẩy vào stack
- Các ký tự là biến luôn được ghi ra, không cất vào stack
- Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ
được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký
tự
tại
đỉnh
stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Các tác vụ có mã số là:
1. Push
2. Pop và ghi ra
3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra
5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện
giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký
tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì
đạt được kết quả.
Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng
hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau.
Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự
mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được
đọc
Ký tự
đang đọc
Ký tự ở
đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt
đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một
khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải
thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức
được định giá
c
Toán
tử cự
trái
Toán
hạng
bên trái
Toán
hạng
bên phải
Kết quả
phép
toán
sau khi thực hiện
phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6
16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán
tử. Thực hiện lần lượt các bước sau:
B1: Đặt k=1
B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack
- Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai
toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái),
thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push
10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push
18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc
biệt mà phép thêm vào (PUSH) ở cuối danh
sách, qua con trỏ First, và phép lấy ra (POP) ở
đầu danh sách, qua con trỏ Last. Do đó, hàng đợi
hoạt động theo nguyên tắc “vào trước ra trước”
FIFO (First in – First out). Hàng đợi có thể rỗng
hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Biểu diễn queue bằng mảng với các biến first (đầu hàng
đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc
sau:
Khi first < last thì queue rỗng
- Hàm thêm một phần tử vào queue: Push với biến last
theo chế độ tăng trước.
- Hàm lấy một phần tử ra khỏi queue: Pop với biến first
theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt
struct
{
int data[100];
int first, last;
};
void Initial(Queue &q)
{
q.first = 0;
q.last=-1;
}
16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int isEmpty(Queue q)
{
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
}
16/11/2008
Cấu trúc dữ liệu 1
6
3.2. Các phép toán trên mảng 3.2.3. Chèn một phần tử vào mảng
Khi thêm một phần tử vào vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển ra sau một vị trí
chen(int a[], int &n)
void {
int i,k,x; cout<<“Nhap phan tu can chen ”;cin>>x; cout<<“Nhap vi tri can chen ”;cin>>k; for(i=n-1;i>=k-1;i--)
a[i+1]=a[i];
a[k-1]=x; n++;
} 16/11/2008
Cấu trúc dữ liệu 1
7
3.2. Các phép toán trên mảng 3.2.4. Xóa một phần tử của mảng
Khi xóa một phần tử tại vị trí thứ k (0 ≤k < n) thì các phần tử từ
a[k+1] đến a[n-1] được di chuyển về trước một vị trí
xoa(int a[], int &n)
void {
int i,k;
cout<<“Nhap vi tri can xoa ”;cin>>k;
for(i=k;i
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước
khi sử dụng ⇒không phù hợp với các bài toán
chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một
phần tử bất kỳ trong mảng. Nếu bài toán mà
việc chèn phần tử và xóa phần tử diễn ra liên
tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước.
(cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt
mà phép thêm vào (PUSH) và phép lấy ra (POP)
đều thực hiện ở cùng một đầu gọi là đỉnh (TOP)
của stack. Do đó stack hoạt động theo nguyên tắc
“vào sau ra trước” LIFO. Stack có thể rỗng hoặc
chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Biểu diễn stack bằng mô hình mảng với các hàm:
- Push theo chế độ tăng trước
- Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt
struct
{
int data[100];
int top;
};
void Initial(Stack &s)
{
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int isEmpty(Stack s)
{
return (s.top==-1);
}
int isFull(Stack s)
{
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
void Push(Stack &s,int k)
{
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
int Pop(Stack &s)
{
if (isEmpty(s))
return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Cú pháp của biểu thức: có 3 dạng
1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm:
- Chỉ dùng được cho các phép toán có hai toán hạng
- Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán
+ Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy
định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải
sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng
được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách
các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix):
giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh
sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép
toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD:
(*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại
bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất
kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh
mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như
dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách
các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong
biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu
thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc
biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Giải thuật
Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt
đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy
theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau:
- Ký tự bắt đầu “$” luôn được đẩy vào stack
- Các ký tự là biến luôn được ghi ra, không cất vào stack
- Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ
được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký
tự
tại
đỉnh
stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Các tác vụ có mã số là:
1. Push
2. Pop và ghi ra
3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra
5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện
giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký
tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì
đạt được kết quả.
Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng
hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau.
Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự
mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự
đang đọc
Ký tự ở
đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được
đọc
Ký tự
đang đọc
Ký tự ở
đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba
Lan đảo
Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt
đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một
khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức dạng hậu tố Ba Lan đảo
Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi
kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải
thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức
được định giá
c
Toán
tử cự
trái
Toán
hạng
bên trái
Toán
hạng
bên phải
Kết quả
phép
toán
sau khi thực hiện
phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6
16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán
tử. Thực hiện lần lượt các bước sau:
B1: Đặt k=1
B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack
- Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai
toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái),
thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Giải thuật
B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push
10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push
18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố
Ba Lan
Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack
Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc
biệt mà phép thêm vào (PUSH) ở cuối danh
sách, qua con trỏ First, và phép lấy ra (POP) ở
đầu danh sách, qua con trỏ Last. Do đó, hàng đợi
hoạt động theo nguyên tắc “vào trước ra trước”
FIFO (First in – First out). Hàng đợi có thể rỗng
hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Biểu diễn queue bằng mảng với các biến first (đầu hàng
đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc
sau:
Khi first < last thì queue rỗng
- Hàm thêm một phần tử vào queue: Push với biến last
theo chế độ tăng trước.
- Hàm lấy một phần tử ra khỏi queue: Pop với biến first
theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt
struct
{
int data[100];
int first, last;
};
void Initial(Queue &q)
{
q.first = 0;
q.last=-1;
}
16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int isEmpty(Queue q)
{
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
n--;
}
16/11/2008
Cấu trúc dữ liệu 1
8
3.3. Ưu và khuyết điểm của mảng
3.3.1. Ưu điểm
• Dễ cài đặt và truy nhập các phần tử dữ liệu
• Tốc độ truy nhập đến một vị trí bất kỳ trên
mảng nhanh, hiệu quả
16/11/2008
Cấu trúc dữ liệu 1
9
3.3. Ưu và khuyết điểm của mảng
3.3.2. Khuyết điểm
• Cần phải xác định trước số phần tử mảng trước khi sử dụng ⇒không phù hợp với các bài toán chưa biết trước số lượng các phần tử.
• Khó khăn trong các thao tác chèn và xóa một phần tử bất kỳ trong mảng. Nếu bài toán mà việc chèn phần tử và xóa phần tử diễn ra liên tục ⇒ tốc độ xử lý sẽ rất chậm.
16/11/2008
Cấu trúc dữ liệu 1
10
3.4. Stack và Queue
• Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2
cấu trúc dữ liệu khá phổ biến.
• Chúng thể hiện cách thức lưu trữ và xử lý dữ
liệu theo một trình tự đã được quy ước. (cid:57)Hàng đợi: Nguyên tắc hoạt động: FIFO
(First In First Out)
(cid:57)Ngăn xếp: Nguyên tắc hoạt động: LIFO
(Last In First Out)
16/11/2008
Cấu trúc dữ liệu 1
11
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa
Stack là một kiểu danh sách tuyến tính đặc biệt mà phép thêm vào (PUSH) và phép lấy ra (POP) đều thực hiện ở cùng một đầu gọi là đỉnh (TOP) của stack. Do đó stack hoạt động theo nguyên tắc “vào sau ra trước” LIFO. Stack có thể rỗng hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
12
3.4. Stack và Queue
3.4.1. Stack
Định nghĩa Biểu diễn stack bằng mô hình mảng với các hàm: - Push theo chế độ tăng trước - Pop theo chế độ giảm sau
input output
top
3
2
1
16/11/2008
Cấu trúc dữ liệu 1
13
3.4. Stack và Queue
3.4.1. Stack
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
14
3.4. Stack và Queue
3.4.1. Stack
Stack
Cài đặt struct {
int data[100]; int top;
}; void Initial(Stack &s) {
s.top = -1;
}
16/11/2008
Cấu trúc dữ liệu 1
15
3.4. Stack và Queue
3.4.1. Stack
Cài đặt int isEmpty(Stack s) {
return (s.top==-1);
}
int isFull(Stack s) {
return (s.top>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
16
3.4. Stack và Queue
3.4.1. Stack
Cài đặt void Push(Stack &s,int k) {
if (isFull(s))
return;
s.data[++s.top]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
17
3.4. Stack và Queue
3.4.1. Stack
Cài đặt int Pop(Stack &s) {
if (isEmpty(s)) return -1;
return s.data[s.top--];
}
16/11/2008
Cấu trúc dữ liệu 1
18
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Cú pháp của biểu thức: có 3 dạng 1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán
hạng. VD: (4 + 5)*(8 - (4 – 1))
Khuyết điểm: - Chỉ dùng được cho các phép toán có hai toán hạng - Nếu bỏ các dấu ngoặc tròn thì phải có:
+ Quy định về độ ưu tiên thứ tự thực hiện phép toán + Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải sang trái)
16/11/2008
Cấu trúc dữ liệu 1
19
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách
các toán hạng. Có 3 dạng tiền tố cụ thể:
- Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách các toán hạng. VD: *(+(1,5),-(8,-(4,1)))
- Dạng tiền tố Cambridge Polish (Cambridge Polish prefix): giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD: (*(+1 5)(-8 (-4 1)))
16/11/2008
Cấu trúc dữ liệu 1
20
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 2. Tiền tố (prefix):
- Dạng tiền tố Polish (Polish prefix): các dấu ngoặc tròn được loại bỏ luôn. VD: *+1 5 – 8 - 4 1
Nhận xét:
- Dạng tiền tố không được tự nhiên như dạng trung tố
- Dạng tiền tố có thể dùng cho các phép toán có số lượng toán hạng bất kỳ, như các phép toán một toán hạng (NOT), các phép gọi hàm.
- Dạng tiền tố biểu diễn trực tiếp cơ chế chồng chất hàm nên việc sinh mã thực thi cho biểu thức ở dạng tiền tố cũng dễ dàng hơn dạng trung tố.
16/11/2008
Cấu trúc dữ liệu 1
21
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 3. Hậu tố hay dạng Ba Lan đảo (postfix hay suffix): cũng như dạng tiền tố nhưng ký hiệu phép toán được viết sau danh sách các toán hạng. VD: ((1,5)+,(8,(4,1)-)-)* hay 1 5 + 8 4 1 - - *
Nhận xét:
- Thứ tự xuất hiện từ trái sang phải của các ký hiệu phép toán trong biểu thức chính là thứ tự thực hiện các phép toán đó.
- Dạng hậu tố không phải là dạng biểu diễn cú pháp phổ biến cho biểu thức trong các ngôn ngữ nhưng nó lại có ý nghĩa quan trọng trong việc biểu diễn biểu thức trong thời gian thực thi.
16/11/2008
Cấu trúc dữ liệu 1
22
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo
Giả sử rằng một biểu thức được kết hợp với các ký hiệu sau: các
biến, các phép toán có hai toán hạng (+, -, *, /) và các dấu ngoặc
trái hay phải. Để đánh dấu bắt đầu và kết thúc một biểu thức ta
chèn thêm ký tự “$” trước ký tự đầu tiên và sau ký tự cuối cùng.
16/11/2008
Cấu trúc dữ liệu 1
23
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Giải thuật Ta cho máy đọc từng ký tự một trong biểu thức dạng trung tố, bắt đầu từ bên trái cho tới khi gặp ký tự kết thúc “$” lần thứ 2. Tùy theo ký tự được đọc và ký tự ở đỉnh stack ta có các tác vụ sau: - Ký tự bắt đầu “$” luôn được đẩy vào stack - Các ký tự là biến luôn được ghi ra, không cất vào stack - Các ký tự được đọc +, -, *, /, (, ) và ký tự kết thúc “$” có tác vụ được thực hiện theo mã số tác vụ được mô tả trong bảng sau:
16/11/2008
Cấu trúc dữ liệu 1
24
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo
Ký tự được đọc
-
*
/
(
)
$+
$
4111115
+
2221112
-
2221112
*
2222212
/
2222212
Ký tự tại đỉnh stack
(
5111113
16/11/2008
Cấu trúc dữ liệu 1
25
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Các tác vụ có mã số là: 1. Push 2. Pop và ghi ra 3. Xóa ký tự đang đọc và xóa ký tự trong stack (pop nhưng không
ghi ra)
4. Giải thuật kết thúc. Kết quả biểu thức được ghi ra 5. Giải thuật dừng. Thông báo có một lỗi xuất hiện. Biểu thức gốc
không được cân đối đúng.
16/11/2008
Cấu trúc dữ liệu 1
26
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Sau mỗi tác vụ được lấy, một phép so sánh mới được thực hiện giữa ký tự đang đọc, nó có thể là ký tự ởl ần so sánh trước hay ký tự kế, với ký tự ở đỉnh stack. Quá trình tiếp tục cho đến bước 4 thì đạt được kết quả. Thứ tự của các biến là như nhau trong cả hai dạng trung tố và dạng hậu tố Ba Lan đảo. Tuy nhiên, thứ tự của các toán tử là khác nhau. Các toán tử xuất hiện trong dạng hậu tố Ba Lan đảo thì theo thứ tự mà chúng thực sự được thực thi trong việc định giá biểu thức.
16/11/2008
Cấu trúc dữ liệu 1
27
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự đang đọc
Ký tự ở đỉnh stack
1 $(8+2*5)/(1+3*2-4)$ $ Push
2 (8+2*5)/(1+3*2-4)$ ( $ Push
3 8+2*5)/(1+3*2-4)$ 8 ( 8
4 +2*5)/(1+3*2-4)$ + ( Push
5 2*5)/(1+3*2-4)$ 2 + 82
16/11/2008
Cấu trúc dữ liệu 1
28
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự đang đọc
Ký tự ở đỉnh stack
*5)/(1+3*2-4)$ * 6 + Push
5)/(1+3*2-4)$ 5 7 * 825
)/(1+3*2-4)$ ) 8 * Pop và ghi ra 825*
9 + Pop và ghi ra 825*+
10 ( Pop và xóa
16/11/2008
Cấu trúc dữ liệu 1
29
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự đang đọc
Ký tự ở đỉnh stack
11 /(1+3*2-4)$ / $ Push
12 (1+3*2-4)$ ( / Push
13 1+3*2-4)$ 1 ( 825*+1
14 +3*2-4)$ + ( Push
15 3*2-4)$ 3 + 825*+13
16/11/2008
Cấu trúc dữ liệu 1
30
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step Biểu thức được đọcKý t
ự đang đọc
Ký tự ở đỉnh stack
*2-4)$ 16 * + Push
2-4)$ 17 2 * 825*+132
-4)$ 18 - * Pop 825*+132*
19 + Pop 825*+132*+
20 ( Push
16/11/2008
Cấu trúc dữ liệu 1
31
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Ví dụ: Xét biểu thức dạng trung tố: (8+2*5)/(1+3*2-4)
Tác vụ
Kết quả
Step
Biểu thức được đọc
Ký tự đang đọc
Ký tự ở đỉnh stack
4)$ 21 4 - 825*+132*+4
)$ 22 ) - Pop 825*+132*+4-
$ 23 $ ( Pop và xóa
24 $ / Pop 825*+132*+4-/
25 $ Stop
16/11/2008
Cấu trúc dữ liệu 1
32
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là:
* *
+ + + + +
( ( ( ( ( ( (
$ $ $ $ $ $ $ $
4 5 7 8 2 3 1 6
16/11/2008
Cấu trúc dữ liệu 1
33
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là:
*
+ + +
( ( ( ( (
/ / / / ( / /
$ $ $ $ $ $ $ $
16 12 13 15 9 11 10 14
16/11/2008
Cấu trúc dữ liệu 1
34
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Giải thuật chuyển đổi từ dạng trung tố sang dạng hậu tố Ba Lan đảo Hoạt động của stack tương ứng là:
*
+ + - -
( ( ( ( ( (
/ / / / / / /
$ $ $ $ $ $ $ $
17 19 18 20 21 23 24 22 25
16/11/2008
Cấu trúc dữ liệu 1
35
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức dạng hậu tố Ba Lan đảo Giải thuật:
B1: Ta xét từng ký tự trong biểu thức dạng hậu tố Ba Lan đảo, bắt đầu từ bên trái cho tới khi gặp một toán tử.
B2: Ghi toán tử và hai toán hạng ngay sát bên trái ra ngoài
B3: Xóa toán tử và hai toán hạng đó trong biểu thức, tạo ra một khoảng trống.
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi kết quả vào khoảng trống.
16/11/2008
Cấu trúc dữ liệu 1
36
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức dạng hậu tố Ba Lan đảo Giải thuật:
B4: Thực hiện phép toán cho bởi toán tử trên hai toán hạng và ghi kết quả vào khoảng trống.
B5: Nếu biểu thức chỉ còn chứa một giá trị thì đó là kết quả và giải thuật kết thúc, ngược lại thì thực hiện lại bước 1.
16/11/2008
Cấu trúc dữ liệu 1
37
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step
Biểu thức mới
Biểu thức được định giá
c
Toán tử cự trái
Toán hạng bên trái
Toán hạng bên phải
Kết quả phép toán
sau khi thực hiện phép toán
1 825*+132*+4-/ * 2 5 10 8 10 + 132*+4-/
2 8 10 + 132*+4-/ + 8 10 18 18 132*+4-/
3 18 132*+4-/ * 3 2 6 18 1 6 +4-/
4 18 1 6 +4-/ + 1 6 7 18 7 4-/
5 18 7 4-/ - 7 4 3 18 3 /
18 3 / / 18 3 6 6
6 16/11/2008
Cấu trúc dữ liệu 1
38
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Giải thuật Cho biểu thức có n ký hiệu, mỗi ký hiệu là một biến hay một toán tử. Thực hiện lần lượt các bước sau: B1: Đặt k=1 B2: Xét ký tự thứ k:
- Nếu ký tự đó là biến, cất vào stack - Nếu ký tự đó là toán tử, lần lượt lấy từ đỉnh của stack hai toán hạng (toán hạng bên phải trước, kế đó là toán hạng bên trái), thực hiện phép toán và đẩy ngược kết quả lên stack.
16/11/2008
Cấu trúc dữ liệu 1
39
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Giải thuật B3: Nếu k=n, giải thuật kết thúc, kết quả nằm trong stack
Ngược lại, k ++, thực hiện lại B2.
Lưu ý:
Con số trên đỉnh stack là toán hạng bên phải, không phải là toán
hạng bên trái. Điều này quan trọng đối với các phép toán trừ và
phép toán chia vì thứ tự của các toán hạng này là có ý nghĩa
(không giống như phép cộng và phép nhân).
16/11/2008
Cấu trúc dữ liệu 1
40
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/ Các bước thực hiện trong tiến trình định giá biểu thức:
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
1 8 2 5*+ 1 3 2*+ 4 -/ Push 8
2 2 5*+ 1 3 2*+ 4 -/ Push 2
3 5*+ 1 3 2*+ 4 -/ Push 5
4 *+ 1 3 2*+ 4 -/
Pop 5, pop 2, nhân 2*5=10, push 10
16/11/2008
Cấu trúc dữ liệu 1
41
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
5 + 1 3 2*+ 4 -/
Pop 10, pop 8, cộng 8+10=18, push 18
6 1 3 2*+ 4 -/ Push 1
7 3 2*+ 4 -/ Push 3
8 2*+ 4 -/ Push 2
9 *+ 4 -/ Pop 2, pop 3, nhân 3*2=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
42
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Ví dụ: Biểu thức dạng trung tố: (8+2*5)/(1+3*2-4) Biểu thức dạng hậu tố Ba Lan đảo tương ứng: 825*+132*+4-/
Step k Dạng biểu thức còn lại sau khi đọcTác v
ụ thực hiện
10 + 4 -/ Pop 6, pop 1, cộng 1+6=7, push 7
11 4 -/ Push 4
12 -/ Pop 4, pop 7, trừ 7-4=3, push 3
13 / Pop 3, pop 18, chia 18/3=6, push 6
16/11/2008
Cấu trúc dữ liệu 1
43
3.4. Stack và Queue
3.4.1. Stack
Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Định giá biểu thức hậu tố Ba Lan đảo trên máy tính với stack Hoạt động của stack tương ứng với các bước của k
- - 2
4 3 3 5 6
7 3 10 1 1 2 2 7 1 1
18 18 8 18 18 8 8 18 8 6 18 18 18
11 12 4 8 7 3 2 10 1 13 5 6 9
16/11/2008
Cấu trúc dữ liệu 1
44
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
Hàng đợi là một kiểu danh sách tuyến tính đặc biệt mà phép thêm vào (PUSH) ở cuối danh sách, qua con trỏ First, và phép lấy ra (POP) ở đầu danh sách, qua con trỏ Last. Do đó, hàng đợi hoạt động theo nguyên tắc “vào trước ra trước” FIFO (First in – First out). Hàng đợi có thể rỗng hoặc chứa một số phần tử.
16/11/2008
Cấu trúc dữ liệu 1
45
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa Biểu diễn queue bằng mảng với các biến first (đầu hàng đợi) và last (cuối hàngđợ i) hoạt động theo nguyên tắc sau: Khi first < last thì queue rỗng - Hàm thêm một phần tử vào queue: Push với biến last theo chế độ tăng trước. - Hàm lấy một phần tử ra khỏi queue: Pop với biến first theo chế độ tăng sau.
16/11/2008
Cấu trúc dữ liệu 1
46
3.4. Stack và Queue
3.4.2. Queue
Định nghĩa
output
first
1
2
3
last
input
16/11/2008
Cấu trúc dữ liệu 1
47
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
Các thao tác chính:
- isEmpty: Kiểm tra rỗng
- isFull:
Kiểm tra đầy
- Push:
Thêm 1 phần tử
- Pop:
Lấy ra 1 phần tử
16/11/2008
Cấu trúc dữ liệu 1
48
3.4. Stack và Queue
3.4.2. Queue
Queue
Cài đặt struct {
int data[100]; int first, last;
}; void Initial(Queue &q) {
q.first = 0; q.last=-1;
} 16/11/2008
Cấu trúc dữ liệu 1
49
3.4. Stack và Queue
3.4.2. Queue
Cài đặt int isEmpty(Queue q) {
return (q.last
}
int isFull(Queue q)
{
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
void Push(Queue &q,int k)
{
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt
int Pop(Queue &q)
{
if (isEmpty(q))
return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
17/11/2008
Cấu trúc dữ liệu 1
53
}
int isFull(Queue q) {
return (q.last>=99);
}
16/11/2008
Cấu trúc dữ liệu 1
50
3.4. Stack và Queue
3.4.2. Queue
Cài đặt void Push(Queue &q,int k) {
if (isFull(q))
return;
q.data[++q.last]=k;
}
16/11/2008
Cấu trúc dữ liệu 1
51
3.4. Stack và Queue
3.4.2. Queue
Cài đặt int Pop(Queue &q) {
if (isEmpty(q)) return -1;
return q.data[q.first++];
}
16/11/2008
Cấu trúc dữ liệu 1
52
3.4. Stack và Queue
3.4.2. Queue
Ứng dụng
Hàng đợi có thể được sử dụng trong một số bài toán:
- Bài toán “sản xuất và tiêu thụ”
- Bộ đệm (VD: Nhấn phím -> Bộ đệm -> CPU xử lý)
- Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều
hành,trình biên dịch), hàng đợi các tiến trình chờ được
xử lý.
