theory 2 2
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.2 MB, 29 trang )
CẤU TRÚC DỮ LIỆU
CẤU
TRÚC
DỮ
LIỆU
VÀ GIẢITHUẬT
VÀ
GIẢI
THUẬT
Lý thuyết
Ph
ầ
n2
(
Chươn
g
3
–
ti
ếp
)
(
g
p
)
NgănxếpvàHàngđợi
Ngănxếp
Hàng
đợi
Hàng
đợi
Vũ Anh Dũng - Khoa CNTT 2
Ngănxếp ADT (Stack ADT)
Ngănxếplàmột danh sách đặcbiệtmàthao
tác
thêm
(insert)
và
loại
bỏ
(delete)
chỉ
diễn
tác
thêm
(insert)
và
loại
bỏ
(delete)
chỉ
diễn
ra ở 1 đầu.
Ví
trí
tại
đó
phép
thêm
và
xóa
diễn
ra
luôn
ở
Ví
trí
tại
đó
phép
thêm
và
xóa
diễn
ra
luôn
ở
cuốicủa danh sách và đượcgọilàtop.
Vũ Anh Dũng - Khoa CNTT 3
Ngănxếp ADT (Stack ADT)
Mô hình ngănxếp:
Thêm 1 phầntử : push
Lo
ạ
i
b
ỏ 1
p
h
ầ
nt
ử
:
p
o
p
Vũ Anh Dũng - Khoa CNTT 4
ạ
p
pp
Kiểmtravàtrả về giá trị củaphầntử : top
Ngănxếp ADT (Stack ADT)
Phép thêm và loạibỏ luôn diễnratại top
Vũ Anh Dũng - Khoa CNTT 5
Cài đặtngănxếp
Có thể sử dụng list hoặc vector
Sử
dụng
list vector
:
Sử
dụng
list
,
vector
:
Thao tác push đượcthựchiệnbằng việc
hè
à
ối
dh
áh
c
hè
nv
à
ocu
ối
d
an
h
s
á
c
h
Thao tác pop đượcthựchiệnbằng cách
ầ
ố
xóa
p
h
ầ
ntửở cu
ố
i danh sách
Thao tác top chỉđơnthuầnkiểmtraphần
Vũ Anh Dũng - Khoa CNTT 6
tửở cuối danh sách, và trả về giá trị
Cài đặtngănxếp
Sử dụng list, vector :
L push back
(x);
L
.
push_back
(x);
L.pop_back();
int x= L.back();
Vũ Anh Dũng - Khoa CNTT 7
Cài đặtngănxếp
Sử dụng mảng:
Dùng
thêm
biến
topOfStack
để
điều
khiển
Dùng
thêm
biến
topOfStack
để
điều
khiển
các thao tác vớingănxếp.
topOfStack
=
1
nếu
ngăn
xếp
rỗng
topOfStack
=
-
1
nếu
ngăn
xếp
rỗng
.
ầ
ế
Yêu c
ầ
u: Sinh viên tự vi
ế
t code cho cả 3 cài
đặtsử dụng list, vector và array
Vũ Anh Dũng - Khoa CNTT 8
Mộtsốứng dụng –
Cân bằng ký hiệu (Balancing)
Kiểm tra các dấu ngoặc trong quá trình
kiểm
tra
lỗi
cú
pháp
kiểm
tra
lỗi
cú
pháp
Tạomộtngănxếprỗng.
Đọc các ký tự dấu
Nế
ký
là
ộ
ký
hiệ
ở
đặ
ó
à
ă
ế
Nế
u
ký
t
ự
là
m
ộ
t
ký
hiệ
um
ở
,
đặ
tn
ó
v
à
o trong ng
ă
nx
ế
p.
Nếunólàmộtkýhiệu đóng, thì nếungănxếplàrỗng thì thông báo
mộtlỗi. Ngượclại, lấyrakhỏingănxếp.
ế
ấ
Nế
ukýhiệu đượcl
ấ
y ra không
p
hảilàkýhiệum
ở
tương ứng, thì
thông báo mộtlỗi.
Tạivị trí cuốicủa file, nếungănxếp không rỗng thì thông báo một
ỗ
Vũ Anh Dũng - Khoa CNTT 9
l
ỗ
i.
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Xét biểuthức:
499+599+699*106=
4
.
99
+
5
.
99
+
6
.
99*
1
.
06
=
Nếusử dụng máy tính thông thường để bấm
thì
kết
ả
là
19 05
thì
kết
qu
ả
là
19
.
05
Tuy nhiên, mộtsố máy tính thông minh hơn
ế
sẽ chọn
p
hép nhân ưu tiên trướcvàchok
ế
t
quả là 18.39
Vũ Anh Dũng - Khoa CNTT 10
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Xét biểuthức:
4 99 * 1 06 + 5 99 + 6 99 * 1 06 =
4
.
99
*
1
.
06
+
5
.
99
+
6
.
99
*
1
.
06
=
Có thể sử dụng biểuthức Ba Lan dạng hậu
tố
h
tố
n
h
ư sau :
4.99 1.06 * 5.99 + 6.99 1.06 * +
Vũ Anh Dũng - Khoa CNTT 11
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Ví dụ:
6523
+8*+3+
*
6
5
2
3
+
8
*
+
3
+
*
Ban đầu:
Vũ Anh Dũng - Khoa CNTT 12
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Tiếptheo‘+’ được đọc, do vậy 3 và 2 được
lấy
ra
từ
ngăn
xếp
và
tổng
của
chúng
,5,
lấy
ra
từ
ngăn
xếp
và
tổng
của
chúng
,
5,
được đNyvào.
Vũ Anh Dũng - Khoa CNTT 13
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Tiếptheo8 được đNyvào
Bây giờ ‘*’ được nhìn thấy, do vậy 8 và 5
ấ
N
đượcl
ấy
ra và 5 * 8 = 40 được đ
Ny
vào
Vũ Anh Dũng - Khoa CNTT 14
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
Tiếp theo ‘+’ được nhìn thấy, do vậy 40 và
5 đư
ợ
c lấ
y
ra và 5 + 40 = 45 đư
ợ
c đN
y
vào
ợ y ợ y
N
3 được đ
Ny
vào
Vũ Anh Dũng - Khoa CNTT 15
Mộtsốứng dụng –
Biểuthứchậutố (Postfix Exp)
‘+’ tiếptheolấy ra 3 và 45 và đN y vào 45 +
3 = 48
ố
ấ
Cu
ố
icùn
g
‘*’ được nhìn th
ấy
và 48 và 6
đượclấy ra; 6 * 48 = 288 được đNyvào
Vũ Anh Dũng - Khoa CNTT 16
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Sử dụng mộtngănxếp để chuyểnmộtbiểu
thức ở d
ạ
n
g
chuNn
(
đư
ợ
c
gọ
i theo cách khác
ạ g
(
ợ
gọ
là trung tố - infix) sang dạng hậutố - postfix
Chúng
ta
chỉ
xét
một
bài
toán
nhỏ
với
các
Chúng
ta
chỉ
xét
một
bài
toán
nhỏ
với
các
phép +, *, (, )
Ví
dụ
:
a
+b*c+(d*e+f)*g
Ví
dụ
:
a
+
b
*
c
+
(
d
*
e
+
f
)
*
g
Được chuyển thành a b c * + d e * f + g * +
Vũ Anh Dũng - Khoa CNTT 17
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Mộtsố quy tắc:
Gặp
toán
hạng
:
chuyển
qua
đầu
ra
Gặp
toán
hạng
:
chuyển
qua
đầu
ra
Gặptoántử, hoặcdấumở ngoặc: đưa
vào
stack
vào
stack
Toán tửđược đưarađầu ra sau khi xử lý,
h
dấ
ặ
hì
khô
n
h
ưn
g
dấ
un
g
o
ặ
ct
hì
khô
n
g
Dấu+ ưu tiên thấpnhất, ( là ưu tiên cao
ấ
nh
ấ
t
Vũ Anh Dũng - Khoa CNTT 18
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Đầu tiên, ký hiệu a được đọc, do vậy nó
đư
ợ
c tru
y
ền tới đầu ra.
ợ y
Sau đó + được đọc và được đặt lên trên
ngănxếp
ngăn
xếp
.
Tiếp theo b được đọc và được truyền tới đầu
ra
ra
.
Vũ Anh Dũng - Khoa CNTT 19
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Tiếptheo* được đọc. Mục ở đỉnh củangăn
xế
p
toán tử có
q
u
y
ền ưu tiên thấ
p
hơnso
p
qy
p
với *, do vậy không có gì được đưaravà*
đư
ợ
c đ
ặ
tvàon
g
ănxế
p
. Tiế
p
theo
,
c đư
ợ
c
ợ
ặ
g
p
p
,
ợ
đọcvàđưa ra output
Vũ Anh Dũng - Khoa CNTT 20
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Kí hiệutiếptheolà+. Kiểmtrangănxếp,
chún
g
ta thấ
y
rằn
g
chún
g
ta sẽ lấ
y
ra * và
g
y
g
g
y
đặtnólênđầura; lấyra+ cònlại, nó có
q
u
y
ền ưu tiên khôn
g
thấ
p
hơnnhưn
g
b
ằn
g
,
qy
g
p
g
g
,
trên ngănxếp; và sau đó đN y + vào stack.
Vũ Anh Dũng - Khoa CNTT 21
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Ký hiệu đọctiếptheolà(, đang có quyền ưu
tiên cao nhất
,
đ
ặ
t nó lên trên n
g
ănxế
p
.
,
ặ
g
p
Vũ Anh Dũng - Khoa CNTT 22
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
Bây giờ ta đọc ), do vậy ngăn xếp được làm
rỗng cho tới(
Chúng
ta
đưa
ra
+
rỗng
cho
tới
(
.
Chúng
ta
đưa
ra
+
Vũ Anh Dũng - Khoa CNTT 23
Mộtsốứng dụng –
Chuyểntừ trung tố sang hậutố
C ối
ù
C
u
ối
c
ù
n
g
Vũ Anh Dũng - Khoa CNTT 24
Mộtsốứng dụng –
Lờigọihàm
Các lờigọihàmsử dụng ngănxếp
Có
thể
xem
một
ví
dụ
về
gọi
hàm
đệ
quy
Có
thể
xem
một
ví
dụ
về
gọi
hàm
đệ
quy
Hàm tính n!
Hàm
fibonaci
Hàm
fibonaci
Vũ Anh Dũng - Khoa CNTT 25
![Popular music vol[1] 2 theory and method](https://media.store123doc.com/images/document/14/rc/df/medium_keVOAFxBLn.jpg)
![Matrix quantum mechanics and 2 d string theory [thesis] s alexandrov](https://media.store123doc.com/images/document/14/rc/ya/medium_8kAdgQLKd0.jpg)
