ề ươ
Đ c
ng CTDL & GT
Ứ ể ế ụ ế ợ ươ ổ ng d ng ngăn x p (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
ở ầ ầ Ph n I: M đ u
ớ ề 1. 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
ọ ẩ ậ ẽ ả ơ ự ệ ệ ệ ậ ữ ệ ượ 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 d li u đ 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 t k ử 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 . Vì v y em xin ch n đ tài “ ng d ng ngăn x p (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 ”.
ầ ủ ề ụ 2. M c đích yêu c u c a đ tài:
ụ 2.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.2. Yêu c u:ầ
ữ ậ ặ ươ ệ ể C/C++ đ cài đ t ch ng trình. V i ớ dữ li u đ ượ c + Dùng ngôn ng l p trình
ậ ừ nh p vào t bàn phím.
ươ ứ 3. Ph ng pháp nghiên c u:
ữ ệ ấ ả ậ ệ c u trúc d li u và gi i thu t, trên m ng ạ … ả + Tham kh o tài li u:
ự ễ ầ ủ ể + 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 (Satck)
1.
ị + Đ nh nghĩa Stack
ữ ư + Cách l u tr Stack
2.
ệ ầ ế ế ằ Các công vi c c n thi t: (vi ỏ t code b ng con tr )
ế ầ ế ủ + Vi t các khai báo c n thi t c a Stack
ế ở ạ ộ ỗ + Vi t th t c k ủ ụ h i t o m t Stack r ng.
ế ể ỗ + Vi t hàm ki m tra Stack r ng.
ế ầ ử ộ + Vi t th t c t ủ ụ hêm m t ph n t vào Stack.
ế ủ ụ ầ ử ỏ ộ + Vi t th t c xóa m t ph n t kh i Stack.
ươ ủ ấ + Vi t cế h ộ ng trình con l y n i dung c a ph n t ầ ử ạ ỉ t ủ i đ nh c a Stack.
ợ II. Hàng đ i (Queue)
1.
ị + Đ nh nghĩa Queue
ữ ư + Cách l u tr Queue
2.
ệ ầ ế Các công vi c c n thi t:
ế ầ ế ủ + Vi t các khai báo c n thi t c a Queue
ế ở ạ ủ ụ ộ ỗ + Vi t th t c kh i t o m t Queue r ng.
ế ể ỗ + Vi t hàm ki m tra Queue r ng.
ế ầ ử ộ + Vi t th t c t ủ ụ hêm m t ph n t vào Queue.
ế ủ ụ ộ + Vi t th t c xóa m t ph n t ầ ử ỏ Queue. kh i
ươ ủ ấ + Vi t cế h ộ ng trình con l y n i dung c a ph n t ầ ử ạ ỉ t i đ nh c a ủ Queue. (in ra k tế
qu )ả
ứ ố ọ ể III. Bi u th c s h c và ký pháp Ba Lan
ặ ấ ề 1. Đ t v n đ . (Bài toán)
2.
ệ ầ ế Các công vi c c n thi t:
ế ươ ứ ừ ạ ể ố + Vi t ch ổ ng trình con đ i bi u th c t d ng trung t ạ sang d ng ti n t ề ố (in ra k tế .
qu )ả
ế ươ ứ ừ ạ ể ố + Vi t ch ổ ng trình con đ i bi u th c t d ng trung t ạ sang d ng h u t ậ ố (in ra k tế .
qu )ả
ế ươ ị ủ ể ế + Vi t ch ng trình con tính giá tr c a bi u th c ti n t ả ứ ề ố (in ra k t qu ) .
ế ươ ị ủ ể ế + Vi t ch ng trình con tính giá tr c a bi u th c h u t ả ứ ậ ố (in ra k t qu ) .
ế ầ ậ Ph n III: K t lu n
