Cấu trúc dữ liệu và giải thuật_ Bài tập lớn

*ADT (Abstract Data Types) – kiểu dữ liệu trừu tượng bao gồm:Tậpcác giá trị (đối tượng)Tậpcác phép toán có thể thực hiện với tất cả các giá trị nàyCáchbiểu diễn dữ liệu được sử dụng chung cho tất cả các giá trị này*Stack (ngăn xếp): là một kiểu dữ liệu trừu tượng, một dạng đặc biệt của danh sách tuyến tính(dãy gồm 0 hoặc nhiều hơn các phần tử cùng kiểu cho trước) trong đó các đối tượng được nạpvào (push) và lấy ra (pop) chỉ từ một đầu gọi là đỉnh (top) của danh sách....
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật_ Bài tập lớnCấu trúc dữ liệu và giải thuật ADT Stack Bàitậplớn CẤUTRÚCDỮLIỆUVÀGIẢITHUẬT Đềtài:ADTStacks[Ngănxếp] -o0o- Mai Xuân Cường - Nguyễn Trung Dũng A - Hoàng Mạnh Hùng Nguyễn Thị Thu Nga - Vũ Thị Quỳnh Trang - Ngô Anh Tuấn - Nguyễn Tuấn *** I.Địnhnghĩa: *ADT(AbstractDataTypes)–kiểudữliệutrừutượngbaogồm: Tậpcácgiátrị(đốitượng) Tậpcácphéptoáncóthểthựchiệnvớitấtcảcácgiátrịnày Cáchbiểudiễndữliệuđượcsửdụngchungchotấtcảcácgiátrịnày *Stack(ngănxếp):làmộtkiểudữliệutrừutượng,mộtdạngđặcbiệtcủadanhsáchtuyếntính(dãygồm0hoặcnhiềuhơncácphầntửcùngkiểuchotrước)trongđócácđốitượngđượcnạpvào(push)vàlấyra(pop)chỉtừmộtđầugọilàđỉnh(top)củadanhsách. nguyêntắc:vàosauratrước(LIFO–lastinfirstout) Đốitượngcấtgiữ: cácphầntửsố(nguyên,thực),kýtự,xâu(string),mảng(array),bảnghi(record),file... Cácphéptoáncơbản: +pushđẩyphầntửvàongănxếp +poplấyphầntửrakhỏingănxếp +isEmptykiểmtrangănxếprỗng +sizetrảvềsốphầntửcủangănxếp +toptrảvềgiátrịcủaphầntửnằmởđầudanhsáchmàkhônglấynórakhỏingănxếp II.Càiđặt: 1Cáccấutrúcdữliệuđểbiểudiễnvàcàiđặtcácphéptoán: a)Mảng: +nạpcácphầntửtheothứtựtừtráisangphải +cóbiếnlưutrữchỉsốcủaphầntửởđầungănxếpStack 3 5 2 …… 6 7 0 1 2 …. n maxn +trongđó: maxn_sốphầntửtốiđaxincấpphátcủangănxếp n_biếndùngđểlưutrữchỉsốphầntửởđầungănxếp +mộthạnchếcủaviệcsửdụngmảnglàphảikhaibáokíchthướctốiđađểdựphòngnêngâylãngphíbộnhớhoặcphảithôngbáotrànbộnhớ(FullStack)khithựchiệnthaotácpush b)Danhsáchmócnối(contrỏ): 1Cấu trúc dữ liệu và giải thuật ADT Stack +mỗinútbaogồm2thànhphầncơbản: elements đểlưutrữnộidungdữliệucủaphầntử,*nextlàcontrỏđếnnúttiếptheotrongngănxếp +thaotácbốsungvàloạibỏluônlàmviệcởnútđầutiênthôngquaviệcsửdụngmộtcontrỏ*toptrỏđếnnútđầutiêntrongngănxếp +việcsửdụngdanhsáchmócnối(haycontrỏ)cómộtưuđiểmlàkhôngphảikhaibáosốphầntửtốiđacủangănxếpđểdựphòngtừđócóthểtiếtkiệmđượcbộnhớkhôngcầnthiết. 7 54 ……. 93 5 NULL*top elements *next 2Chươngtrìnhminhhọa:file:StackPtr.cpp,STACKARR.cpp III.Ứngdụng: 1Phátbiểubàitoán: *Tínhgiátrịbiểuthứcsốhọc: Biểuthứcsốhọcxuấthiệnrấtnhiềutrongcuộcsốngvàviệctínhtoángiátrịcủacácbiểuthứcđólàđiềutấtyếu,quantrọng.Vídụ: Khisửdụngmáytính(calculator),ngườidùngsẽnhậpcácbiểuthứcsốhọccầntínhthôngquacácphímsốvàphéptoáncósẵn.Nhiệmvụcủamáysẽtínhtoánvàhiểnthịkếtquảchínhxácramànhình. Khisửdụngcácbảngtínhđiệntử(nhưExcel,…)đểlậpcácbảngtínhlương,thốngkêviệcthuchicủadoanhnghiệp…,ngườidùngsẽnhậpcácbiểuthứcsốhọcvàocácôtính.Khiđó,chươngtrìnhsẽcónhiệmvụphântíchvàtínhtoánrồiđưarakếtquảtạiôđó. Haytrongcácngônngữlậptrình(nhưC,PASCAL…),tađãkháquenthuộcvớicáclệnhgán X= //Xlàbiến Khithựchiệnchươngtrình,gặpcáclệnhgán,máytínhcầnphảixácđịnhgiátrịcủacácbiểuthứcsốhọcđóvàgánkếtquảchobiếnX. Vìvậy,việcxâydựngmộtchươngtrìnhtínhtoángiátrịcủacácbiểuthứcsốhọclàcầnthiết. Biểuthứcsốhọclàmộtdãycáctoánhạng(hằng(số),biếnhoặchàm)nốivớinhaubởicácphéptoánsốhọc(nhưcộng,trừ,nhân,chia,lũythừa,cănthức,...).Trongcácbiểuthứccóthểchứacácdấungoặctrònđểxácđịnhthứtựưutiên.Khiđócácphéptoántrongngoặcsẽđượcthựchiệntrướccácphéptoánởngoài. Cácphéptoánsốhọcđượcphânralàm2loại: Cácphéptoánhaingôi(+,,*,/,^,…):mỗiphéptoánđượcđặtgiữacáctoánhạng.Vídụ:2+3,56*12,3^8,… Cácphéptoánmộtngôi(căn,logarit,cáchàmlượnggiác:sin,cos,tg,…):mỗiphéptoánđingaytrướctoánhạng.Vídụ:sin4,ln7,… Hơnnữa,khitínhcácbiểuthứcsốhọc,tacầnphảituântheonhữngquytắcsau: Thứtựưutiên:^*,/+, Quytắckếthợp:chobiếtkhicó2phéptoáncócùngthứtựưu ...