Tài liệu Cấu trúc dữ liệu

Tài liệu Cấu trúc dữ liệu sau đây được biên soạn nhằm trang bị cho các bạn những kiến thức tổng quan về cấu trúc dữ liệu và danh sách trong cấu trúc dữ liệu. Mời các bạn tham khảo tài liệu để bổ sung thêm kiến thức về lĩnh vực này.
Nội dung trích xuất từ tài liệu:
Tài liệu Cấu trúc dữ liệu Chương1:TỔNGQUANVỀCẤUTRÚCDỮLIỆU o0o1.1.Kháiniệmvềcấutrúcdữliệu. Cấutrúcdữliệu(CTDL)làmộtcáchtổchứcdữliệucủabàitoán.CTDLcóthểdo ngônngữlậptrìnhđịnhnghĩatrướchoặccóthểdongườisửdụngđịnhnghĩa. Cấutrúcdữ liệutốtthìthuậttoánxử lýbàitoánmớitốiưu.Chínhvìvậy,Niklauswirthđãtổngkết:“Cấutrúcdữliệu+thuậttoán=Chươngtrình”. Cáchbiểudiễntối ưumộtcấutrúcdữ liệutrongbộ nhớ đượcgọilàcấutrúclưutrữ(storagestructure).Cóthểcónhiềucấutrúclưutrữchocùngmộtcấutrúcdữliệu.Cấutrúcdữliệutươngứngvớibộnhớgọilàlưutrữ tronghaytươngứngvớibộnhớngoàigọilàlưutrữngoài. Thôngthườngmộtkiểudữliệuđượcđịnhnghĩanhưsau:MộtkiểudữliệuTlàmộtcặpT=trongđó:V(value):LàmộttậpcáctrịmàmộtbiếncókiểuTnhậnđược.O(Operator):LàtậphợpcácthaotáctrênV.Vídụ:a.T Integer=V={32768,...,32767};O={+,,*,/,mod,div,xor,,...}b.T Boolean=V={True,False};O={And,Or,Xor,Not,,=,…} Mộtcấutrúcdữliệulàmộtkiểudữliệuđượcxâydựngtừ nhữngkiểudữliệuđã biết,trongtrườnghợpnàychotamộtCTDLtươngứngvớimộtkiểudữliệuđãcho.1.2.Cáccấutrúcdữliệucănbản.1.2.1.Cáckiểudữliệucănbản.KiểuInteger(nguyên–2byte,32768..32767).Gồmtậphợpconcácsốnguyên.Tấtcảcácphéptoántrêndữliệuintegerđềutuânthủcácquitắcsốhọc.Cáctoántửchuẩn gồmbốnphéptoánsốhọccơbản:cộng(+),trừ(),nhân(*),chianguyên(div).KiểuReal (thực–6byte,2.9E39..1.7E38).Gồmtậphợpconcủacácsố thực,cáctoántửchuẩngồmbốnphéptoánsốhọccơbảnlà:công(+),trừ(),nhân(/).KiểuBoolean(luậnlý–1bit).Gồmhaigiátrị luânlýtrue(đúng)vàfalse(sai).Cáctoántửluậnlýgồmbaphéptoáncơbản:not(phủđịnh),and(và)vàor(hay). Cácphéptoánsosánhchokếtquả làmộtgiátrị luậnlý.Cácphéptoánsosánh gồm: =bằng 1 khácbằng(khác) =lớnhơnhoặcbằngKiểuchar(kítự–1byte):Gồmtậphợpcáckítựinđược.Cáckítựthườngdùnglà: +Kiểuchargồm26chữLatin((‘A’ VAR:;+Khaibáotrựctiếp: VAR :ARRAY[chỉsố]OF;Chúý:ChỉsốtrongkhaibáođốivớiPascalphảiđượcxácđịnhtrướcở khaibáohằng hoặcghicụthể.*Mảnghaichiều.Cúpháp:+Khaibáogiántiếp: TYPE =ARRAY[chỉsố1,chỉsố2]OF; VAR :;+Khaibáotrựctiếp: VAR :ARRAY[chỉsố1,chỉsố2]OF;Vídụ: TYPE Mangnguyen=Array[1..100]ofInteger; Matrix=Array[1..10,1..10]ofInteger; MangKytu=Array[Byte]ofChar; VAR A:Mangnguyen; M:Matrix; C:MangKytu;Hoặc: VAR A:Array[1..100]ofInteger; C:Array[Byte]ofChar;b.Kiểuxâukýtự. Chúngtagọikiểudữliệucógiátrịlàtậpnhữngkítựlàkiểuxâukítựhaynóimộtcáchngắngọnlàkiểuxâu. Pascalcótừ khoáSTRING để ngườidùngkhaibáochodữ liệucógiátrị làtậpnhữngkítự. VídụtakhaibáobiếnAcókiểulàtậpnhữngkítựnhưsau: VARA:STRING;máydànhchobiếnAcóthểlưugiữđượcmộttậpcókhôngquá255kítự. Hằngvănbảnphảiđểtrongcặpdấunháycao(‘).*Khaibáo.TYPE TênKiểu=STRING[Max]; VAR Tênbiến:TênKiểu;hoặckhaibáobiếntrựctiếp: 3 VAR Tênbiến:STRING[Max];TrongđóMaxlàsốkýtựtốiđacóthểchứatrongchuỗi(Max [0,255]).Nếukhôngcókhaibáo[Max]thìsốkýtựmặmặcđịnhtrongchuỗilà255.Vídụ: Type Hoten=String[30]; St80=String[80]; Var Name:Hoten; Line:St80;St:String;{Stcótốiđalà255kýtự}*Truyxuấtphầntử. CóthểsửdụngcácthủtụcxuấtnhậpWrite,Writeln,ReadlnđểtruyxuấtcácbiếnkiểuString. Đểtruyxuấtđếnkýtựthứkcủaxâukýtự,tasửdụngcúphápsau:Tênbiến[k].*CácthủtụcvàhàmtrênxâukýtựHàmlấychiềudàicủaxâykýtự LENGTH(St:String):Integer;HàmCOPY(St:String;Pos,Num:Byte):String;LấyramộtxâucontừtrongxâuStcóđộdàiNumkýtựbắtđầutừvịtríPos.HàmPOS(SubSt,St:String):Byte;KiểmtraxâuconSubStcónằmtrongxâuSthaykhông?NếuxâuSubStnằmtrongxâu Stthìhàmtrả về vị tríđầutiêncủaxâuconSubSttrongxâuSt,ngượclạihàmtrả vềgiátrị0.ThủtụcDELETE(VarSt:String;Pos,Num:Byte);XoátrongxâuStNumkýtựbắtđầutừvịtríPos.ThủtụcINSERT(SubSt:String;VarSt:String;Pos:Byte);Chè ...