Kiến trúc máy tính - Bài 6

CấutrúcdữliệuVector List Stack Queue Tree HashTable Dictionary Véctơ(Vector) Cấu trúc tuyến tínhCấutrúctuyếntínhlàmột cấutrúctrongđócácphần
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - Bài 6 CấutrúcdữliệuVectorListStackQueueTreeHashTableDictionary 1 Bài6Véctơ(Vector) 2 Cấu trúc tuyến tínhCấutrúctuyếntínhlàmộtcấutrúctrongđócácphần Cấutrúctửnằmtrênmộtđường tuyếntínhkhôngcónhánh,vàcácphầntửliêntiếpnhau.Mộtsốvídụ: Cấutrúcphi tuyến Danhsách(lists)  Vector,chuỗi(vectors  sequences) Danhsáchkiểungănxếp,  danhsáchkiểuhàngđợi (stack,queue) 3Vector 4 KiểudữliệutrừutượngVector (VectorADT) KiểudữliệutrừutượngVectorlàsựmởrộngcủakhái niệmmảng.Vectorlàmộtmảnglưutrữmộtdãycác đốitượngvớisốlượngtùyý. V 012 n Mộtphầntửcóthểđượctruycập,chènthêmhoặcloạibỏđikhibiếtchỉsốcủanó. Khithựchiệncácthaotáctrêncóthểxảyralỗinếuchỉsốcủaphầntửkhôngchínhxác(Vd,chỉsốâm) 5CácthaotáctrênVector CácthaotácchínhtrênVector: intgetAtRank(integerr,object&o):Trảlạiphầntửcóchỉsốr,  nhưngkhôngloạibỏnó intreplaceAtRank(integerr,objecto,object&o1):Thaythếphần  tửcóchỉsốrbằngphầntửovàtrảlạiphầntửbịthaythế intinsertAtRank(integerr,objecto):Chènphầntửovàovịtrír  intremoveAtRank(integerr,object&o):loạibỏphầntửtạivịtrír,  vàtrảlạiphầntửbịloạibỏ Thêmvàođólà2phéptoán: intsize()chobiếtkíchthướccủaVector  và intisEmpty()chobiếtVectorcórỗnghaykhông?  6CàiđặtVectorbằngmảng SửdụngmảngVcókíchthướcN Mộtbiếnnlưutrữkíchthướccủavector(sốphầntử đượclưutrữ) PhéptoángetAtRank(r,o)đượcthựchiệntrongthời gianO(1)bằngviệctrảlạiV[r] V 012 n r 7Chènthêmphầntử PhéptoáninsertAtRank(r, o),Chúngtacầntạomộtômới cóchỉsốrbằngcáchđẩynrphầntửtừV[r], …, V[n − 1] về sau1vịtrí Trongtrườnghợpxấunhất(r = 0),phéptoánthựchiện trongthờigianO(n) V 012 n r V 012 n r V o 012 n r 8Loạibỏphầntử PhéptoánremoveAtRank(r,o),chúngtacầnđẩyn − r − 1phầntửtừV[r + 1], …, V[n − 1] về trước một vị trí Trongtrườnghợpxấunhất(r = 0),phéptoánthực hiệntrongthờigianO(n) V o 012 n r V 012 n r V 012 n r 9CácứngdụngcủaVector Ứngdụngtrựctiếp Lưutrữtậphợpcácđốitượng(cơsởdữliệu  đơngiản) Ứngdụnggiántiếp Cấutrúcdữliệubổtrợchocácthuậttoán  Thànhphầncủacáccấutrúcdữliệukhác  10Tómlại CàiđặtVectorbằngmảng: KhônggiansửchocấutrúcdữliệulàO(n)  Các phép toán size,isEmpty,getAtRankvàreplaceAtRankchạy  trongthờigianO(1) insertAtRankvàremoveAtRankchạytrongthờigianO(n)  Nếuchúngtasửdụngmộtmảngquayvòngthìphép toán, insertAtRank(0)vàremoveAtRank(0)chạytrong thờigianlàO(1) VớiphéptoáninsertAtRank,khimảngđầysẽdẫnđến ngoạilệ,đểtránhtrườnghợpnàychúngtathaymạng hiệntạibằngmảnglớnhơn 11Pháttriểnmảng Khithựchiệnphéptoán.Nếumảngđầy sẽdẫnđếnxảyralỗi.Đểcóthểthêm phầntửđóvàotaphảimởrộngmảng. Làmthếnàođểmởrộngmảng? Chiếnlượcpháttriểntheohằngsố:Tăngthêm  kíchthướcmảngtheomộthằngsốc Chiếnlượcgấpđôi:Tănggấpđôisốphầntửhiện  cócủamảng 12ThêmphầntửvàocuốiAlgorithm push( o) if n = V.N − 1 then A ← Tạo mảng mới có kích thước … for i ← 0 to n-1 do A[i] ← V[i] V ←A o V[n] ← n ← n+ 1 13Sosánhhaichiếnlược Tasosánhchiếnl ...