LÝ THUYẾT VỀ CẤU TRÚC DỮ LIỆU

Một trong những phần quan trọng của quá trình phân tích thiết kế là chia vấn đề thành những vấn đềnhỏ dễ hiểu và chi tiết hơn. Phương pháp phân tích thiết kế hướng đối tượng dựa trên quan điểm này. Vìvậy ta cần định ra các lớp sao cho mỗi lớp sau này sẽ cung cấp các đối tượng có các hành vi đúng nhưchúng ta mong đợi. Lúc đó, việc lập trình giải quyết các bài toán lớn của chúng ta chỉ sẽ được tập trungvào những giải thuật lớn. Các đối tượng sẽ được gọi để thực...
Nội dung trích xuất từ tài liệu:
LÝ THUYẾT VỀ CẤU TRÚC DỮ LIỆU TRUNG TÂM ĐÀO TẠO MÔNHỌC CẤUTRÚCDỮLIỆU BÀI1:GIỚITHIỆU1. Vềphươngphápphântíchthiếtkếhướngđốitượng Mộttrongnhữngphầnquantrọngcủaquátrìnhphântíchthiếtkếlàchiavấnđềthànhnhữngvấnđề nhỏdễhiểuvàchitiếthơn.Phươngphápphântíchthiếtkếhướngđốitượngdựatrênquanđiểmnày.Vì vậytacầnđịnhracáclớpsaochomỗilớpsaunàysẽcungcấpcácđốitượngcócáchànhviđúngnhư chúngtamongđợi.Lúcđó,việclậptrìnhgiảiquyếtcácbàitoánlớncủachúngtachỉsẽđượctậptrung vàonhữnggiảithuậtlớn.Cácđốitượngsẽđượcgọiđểthựchiệncáchànhvicủamìnhvàonhữnglúccần thiết.2. GiớithiệumônhọcCấutrúcdữliệu(CTDL)vàgiảithuật CáclớpCTDLphảithựchiệnmộtsốchứcnăngthôngquacáchànhvicủađốitượngcủanó.Vàmột nhiệmvụquantrọngkháccủalớpCTDLlànắmgiữdữliệusaochocóthểđápứngmỗikhiđượcchương trìnhyêucầutrảvềmộtdữliệucụthểnàođómàchươngtrìnhcầnđến.Nhữngthaotáccơbảnđốivới mộtCTDLthườnglàthêmdữliệumới,xoábỏdữliệuđãcó,tìmkiếmvàtruyxuất.CónhiềuCTDLkhác nhauvềcácthaotácbổsung.Chínhvìvậymàkhithiếtkếnhữnggiảithuậtđểgiảiquyếtcácbàitoánlớn ngườitasẽlựachọnCTDLnàolàthíchhợpnhất. Thếnàolàgiảithuật?Chúngtacầnmộtcấutrúcchươngtrìnhđểxácđịnhtacầnlàmnhữngcông việcgì,việcnàolàmtrước,việcnàolàmsau,việcgìchỉlàmtrongtìnhhuốngđặcbiệtnàođó,việcgì cầnlàmlặplạinhiềulần3. CáchtiếpcậntrongquátrìnhtìmhiểucáclớpCTDL: a) Cácbướctrongquátrìnhphântíchthiếtkếhướngđốitượng: Địnhracáclớpvớicácchứcnăngmàchúngtamongđợi Lựachọncácgiảithuậtchính.Đólàtạoramộtmôitrườngđểcácđốitượngcủalớpnêutrên tươngtáclẫnnhau Hiệnthựcchomỗilớp b) QuátrìnhxâydựngcáclớpCTDL: Xuấtpháttừmộtmôhìnhtoánhọchaydựavàomộtnhucầuthựctếnàođó,chúngtađịnh racácchứcnăngcủalớpCTDLchúngtacầncó ĐặctảđầyđủcáchthứcgiaotiếpgiữalớpCTDLđangđượcthiếtkếvớimôitrường ngoài(cácchươngtrìnhsẽsửdụngnó).Phầngiaotiếpnàyđượcmôtảthôngquađịnhnghĩa cácphươngthứccủalớp.MỗiphươngthứclàmộthànhvicủađốitượngCTDLsaunày, phầnđặctảgồmcácyếutốsau: +Kiểukếtquảmàphươngthứctrảvề. +Cácthôngsốvào/ra +Cácđiềukiệnbanđầutrướckhiphươngthứcđượcgọi(precondition) +Cáckếtquảmàphươngthứclàmđược(postcondition) +Cáclớp,hàmcósửdụngtrongphươngthức(uses) Biên soạn: Nguyễn Thanh Hùng 1 TRUNG TÂM ĐÀO TẠO Thôngquaphầnđặctảnày,cácCTDLhoàntoàncóthểđượcsửdụngtrongviệcxâydựng nênnhữnggiảithuậtlớntrongcácbàitoánlớn.Phầnđặctảnàycóthểxemnhưnhữngcam kếtmàkhôngbaogiờđượcquyềnthayđổi.CónhưvậycácchươngtrìnhcósửdụngCTDL mớikhôngbịthayđổimộtkhisửdụngchúng. TìmhiểucácphươngánhiệnthựccholớpCTDL. Chọnphươngánvàhiệnthựclớp.Trongbướcnàybaogồmcảviệckiểmtrađểhoàntâtlớp CTDLnhưlàmộtlớpđểbổsungvàothưviện,ngườilậptrìnhcóthểsửdụngchúngtrong nhiềuchươngtrìnhsaunày.4. Mộtsốđịnhnghĩacơbản: a. Địnhnghĩakiểudữliệu:Mộtkiểudữliệulàmộttậphợp,cácphântửcủatậphợpnàyđượcgọilà cáctrịcủakiểudữliệu. b. Kiểunguyêntốvàcáckiểucócấutrúc:Cáckiểunhưint,float,charđượcgọilàcáckiểunguyên tố(atomic),chúngtaxemcáctrịcủachúngchỉlàmộtthựcthểđơn,chúngtakhôngcómongmuốn chianhỏchúng.Ngoàira,máytínhcòncungcấpcáccôngcụchophépchúngtaxâdựngcáckiểu dữliệumớigọilàcáckiểucócấutrúc(structuredtypes) c. Chuỗinốitiếpvàdanhsách:Mộtchuỗinốitiếp(sequence)kíchthước0làmộtchuỗirỗng.Một chuỗinốitiếpkíchthướcn>=1cácphầntửcủatậpTlàmộtcặpcóthứtự(Sn1,t).Trongđó,Sn1là mộtchuỗinốitiếpkíchthướcn1cácphầntửcủatậpTvàtlàmộtphầntửcủatậpT.Vậymộtdanh sách(list)cácphầntửthuộckiểuTlàmộtchuỗinốitiếphữuhạncácphầntửkiểuT d. Cáckiểudữliệutrừutượng:CTDL(dataStructure)làmộtsựkếthợpcủacáckiểudữliệunguyên tố,và/hoặccáckiểudữliệucócấutr ...