Bài ti u lu n môn: C u trúc d li u và gi i thu tể ậ ấ ữ ệ ả ậ
M c l cụ ụ
Ph n I: M đuầ ở ầ
I. Gi i thi u đ tàiớ ệ ề
Trong khoa h c máy tính, c u trúc d li u là cách l u d li u trong máy ọ ấ ữ ệ ư ữ ệ
tính sao cho nó có th đc s d ng m t cách hi u qu . Thông th ng, m t ể ượ ử ụ ộ ệ ả ườ ộ
c u trúc d li u đcấ ữ ệ ượ ch n c n th n s cho phép th c hi n thu t toán hi u quọ ẩ ậ ẽ ự ệ ậ ệ ả
h n. Vi c ch n c u trúc d li uơ ệ ọ ấ ữ ệ th ng b t đu t ch n m t c u trúc d li u ườ ắ ầ ừ ọ ộ ấ ữ ệ
tr u t ng. M t c u trúc d li u đc thi t kừ ượ ộ ấ ữ ệ ượ ế ế t t cho phép th c hi n nhi u ố ự ệ ề
phép toán, s d ng càng ít tài nguyên, th i gian x lý vàử ụ ờ ử không gian b nh càng ộ ớ
t t. Các c u trúc d li u đc tri n khai b ng cách s d ng cácố ấ ữ ệ ượ ể ằ ử ụ ki u d li u, ể ữ ệ
các tham chi u và các phép toán trên đó đc cung c p b i m t ngôn ng ế ượ ấ ở ộ ữ
l pậ trình.
Trong đó n i tr i lên là hai c u trúc d li u đó là Stack (ngăn x p) và ổ ộ ấ ữ ệ ế
Queue (hàng đi). Stack và Queue có ng d ng r t nhi u k c trong thu t toán ợ ứ ụ ấ ề ể ả ậ
l n trong th c t . Hẫ ự ế àng ngày chúng ta th ng xuyên làm vi c và ti p xúc v i ườ ệ ế ớ
các bi u th c, toán h ng, toán t … và máy tính cũng v y. Tuy nhiên máy tính ể ứ ạ ử ậ
không th nào hi u đc ngôn ng và cách vi t c a con ng i, vì v y đ máy ể ể ượ ữ ế ủ ườ ậ ể
tính hi u đc các bi u th c thì chúng ta ph i chuy n chúng v m t d ng mà ể ượ ể ứ ả ể ề ộ ạ
máy tính có th th c hi n đc. ể ự ệ ượ Vì v y em xin ch n đ tài “ ng d ng ngăn x pậ ọ ề Ứ ụ ế
GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ngị ị ự ệ ư 1
Bài ti u lu n môn: C u trúc d li u và gi i thu tể ậ ấ ữ ệ ả ậ
(Stack) và hàng đi (Queue) đ vi t ch ng trình bi n đi bi u th c trung t ợ ể ế ươ ế ổ ể ứ ố
thành ti n t và h u t ” đ làm bài ti u lu n.ề ố ậ ố ể ể ậ
II. M c đích yêu c u c a đ bàiụ ầ ủ ề
1. M c đíchụ
Đ tài này giúp em c ng c , nâng cao ki n th c v môn h c c u trúc d ề ủ ố ế ứ ề ọ ấ ữ
li u và gi i thu t. T đó hi u sâu h n và v n d ng vào trong các bài toán s ệ ả ậ ừ ể ơ ậ ụ ố
li u th c t đng th i thông qua vi c làm đ tài này giúp em bi t đc các ệ ự ế ồ ờ ệ ề ế ượ
ph ng pháp nghiên c u m t v n đ nh nào đó.ươ ứ ộ ấ ề ỏ
2. Yêu c uầ
Dùng ngôn ng l p trình C/C++ đ cài đt ch ng trình. V i d li uữ ậ ể ặ ươ ớ ữ ệ
đc nh p vào t bàn phím.ượ ậ ừ
III. Ph ng pháp nghiên c uươ ứ
+ Tham kh o tài li u: c u trúc d li u và gi i thu t, trên m ng…ả ệ ấ ữ ệ ả ậ ạ
+ Tìm hi u th c ti n, th c t , quy cách, nhu c u c a bài toán.ể ự ễ ự ế ầ ủ
+ Xin ý ki n, h ng d n c a giáo viên h ng d n.ế ướ ẫ ủ ướ ẫ
Ph n II: N i dungầ ộ
I. Ngăn x p (Stack)ế
Ngăn x p (Stack) là m t danh sách có th t mà phép chèn và xóa đc ế ộ ứ ự ượ
th c hi n t i đu cu i c a danh sách và ng i ta g i đu cu i này là ự ệ ạ ầ ố ủ ườ ọ ầ ố
đnh (top) c a stack. ỉ ủ V i nguyên t c vào sau ra tr c, danh sách ki u ớ ắ ướ ể
LIFO (last - in - first - out).
Có 2 cách l u tr Stack:ư ữ
GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ngị ị ự ệ ư 2
Bài ti u lu n môn: C u trúc d li u và gi i thu tể ậ ấ ữ ệ ả ậ
+ B ng m ng.ằ ả
+ B ng danh sách liên k t.ằ ế
Các thao tác c b n trênơ ả Stack:
Push: Đa m t ph n tư ộ ầ ử vào đnh c a ỉ ủ Stack.
Pop: L y t đnh c a Stack m t ph n t .ấ ừ ỉ ủ ộ ầ ử
Peek: Xem đnh c a Stack ch a n i dung là gì?ỉ ủ ứ ộ
M t s ng d ng c a Stack:ộ ố ứ ụ ủ
ng d ng tr c ti p:Ứ ụ ự ế
ng d ng n i b t c a Stack là Stack cho ch ng trình s d ng Stack đ Ứ ụ ổ ậ ủ ươ ử ụ ể
g i hàm.ọ
Trong trình duy t WEB, các trang đã xem đc l u trongệ ượ ư
stack.
Trong trình so n th o văn b n, thao tác Undo đc l uạ ả ả ượ ư
trong stack.
ng d ng gián ti p:Ứ ụ ế
C u trúc d li u b tr cho thu t toán khác.ấ ữ ệ ổ ợ ậ
M t thành ph n c a c u trúc d li u khác.ộ ầ ủ ấ ữ ệ
II. Hàng đi (Queue)ợ
Hàng đi là ki u danh sách tuy n tính mà phép b sung đc th c hi n ợ ể ế ổ ượ ự ệ ở
1 đu, g i là l i sau (rear) và phép lo i b th c hi n 1 đu khác g i là ầ ọ ố ạ ỏ ự ệ ở ầ ọ
l i tr c (front). Nguyên t c vào tr c ra tr c, danh sách ki u FIFO ố ướ ắ ướ ướ ể
(first - in - first - out).
Có 2 cách l u tr t ng t nh Stack:ư ữ ươ ự ư
+ B ng m ng.ằ ả
GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ngị ị ự ệ ư 3
Bài ti u lu n môn: C u trúc d li u và gi i thu tể ậ ấ ữ ệ ả ậ
+ B ng danh sách liên k t.ằ ế
ng d ng c a QueueỨ ụ ủ
ng d ng tỨ ụ r c ti pự ế
Danh sách hàng điợ.
Qu n lý truy c p t i các tài nguyên dùng chung (ví d máy in).ả ậ ớ ụ
Multiprogramming.
ng d ng gián ti pỨ ụ ế
C u trúc d li u ph tr cho các thu t toán.ấ ữ ệ ụ ợ ậ
M t ph n c a CTDL khác.ộ ầ ủ
III. ng d ng c a Stack và Queue trong ký pháp Ba LanỨ ụ ủ
1. Khái ni m:ệ
Prefix: Bi u th c ti n t đc bi u di n b ng cách đt toán t lên tr c ể ứ ề ố ượ ể ễ ằ ặ ử ướ
các toán h ng. Cách bi u di n này còn đc bi t đn v i tên g i “ạ ể ễ ượ ế ế ớ ọ ký pháp Ba
Lan” do nhà toán h c Ba Lan Jan Łukasiewicz phát minh năm 1920. V i cách ọ ớ
bi u di n này, thay vì vi t x + y nh d ng trung t , ta s vi t + x y. Tùy theo để ễ ế ư ạ ố ẽ ế ộ
u tiên c a toán t mà chúng s đc s p x p khác nhau, b n có th xem m t ư ủ ử ẽ ượ ắ ế ạ ể ộ
s ví d phía sau ph n gi i thi u này.ố ụ ở ầ ớ ệ
Postfix: Ng c l i v i cách Prefix, bi u th c h u t t c là các toán t s ượ ạ ớ ể ứ ậ ố ứ ử ẽ
đc đt sau các toán h ng. Cách bi u di n này đc g i là ượ ặ ạ ể ễ ượ ọ “ký pháp ngh ch ị
đo Ba Lanả” ho c đc vi t t t làặ ượ ế ắ RPN(Reverse Polish notation), đc phát ượ
minh vào kho ng gi a th p k 1950 b i m t tri t h c gia và nhà khoa h c máy ả ữ ậ ỷ ở ộ ế ọ ọ
tính Charles Hamblin ng i Úc.ườ
GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ngị ị ự ệ ư 4
Bài ti u lu n môn: C u trúc d li u và gi i thu tể ậ ấ ữ ệ ả ậ
Ví d :ụ
2. Chuyển đổi dạng Infix(trung t ) sang Postfix(h u t )ố ậ ố
Thu t toán: ậ
B c 1:ướ Đc m t thành ph n c a bi u th c E (d ng Infix bi u di nọ ộ ầ ủ ể ứ ạ ể ễ
b ng xâu, đc t trái qua ph i). Gi s thành ph n đc đc là xằ ọ ừ ả ả ử ầ ọ ượ
B c 1.1: ướ N u x là toán h ng thì vi t nó vào bên ph i bi u th c E1 ế ạ ế ả ể ứ
(xâu l uư
k t qu c a Postfix)ế ả ủ
B c 1.2:ướ N u x là d u ‘(’ thì đy nó vào Stack.ế ấ ẩ
B c 1.3:ướ N u x là m t trong các phép toán +, -, *, / thìế ộ
B c 1.3.1:ướ Xét ph n t y đnh Stack.ầ ử ở ỉ
B c 1.3.2:ướ N u Pri(y) >= Pri(x) là m t phép toán thì lo i y ra ế ộ ạ
kh i Stack và vi t y vào bên ph i c a E1 và quay l i b c 1.3.1ỏ ế ả ủ ạ ướ
B c 1.3.3:ướ N u Pri(y) < Pri(x) thì đy x vào Stack.ế ẩ
B c 1.4ướ : N u x là d u ‘)’ thìế ấ
B c 1.4.1:ướ Xét ph n t y đu c a Stack.ầ ử ở ầ ủ
B c 1.4.2:ướ y là phép toán thì lo i y ra kh i Stack, vi t y vào bênạ ỏ ế
ph i E1 và quay tr l i 1.4.1ả ở ạ
B c 1.4.3:ướ N u y là d u ‘(’ lo i y ra kh i Stack.ế ấ ạ ỏ
GVHD: Tr nh Th Phú Sinh vên th c hi n: Hoàng Năng H ngị ị ự ệ ư 5