Vsbendingar um Verkefni 2

Uppbygging tlva, haust 2001

verkefninu a tfra Quick-find aferina fyrir Union-Find verkefni. Vi a er notaur vektorinn id. hverjum tma mun gilda um hann:

Ef id[p] = id[q] eru stkin p og q sama mengi.

Find-agerin verur mjg hravirk, v aeins arf a bera saman innihald tveggja staka vektornum id. Union-agerin er hins vegar mun drari, v a arf a fara gegnum allan vektorinn og uppfra gildi.

Hvert stak vektornum id er tv bti. etta ir a tvfalda verur vsagildi ur en a er lagt vi grunnbendi vektorsins. Vi hfum upphafi a DS:SI bendir id[0] og segjum a BX s vsirinn p forritinu. Til a n id[p] arf fyrst a tvfalda BX, t.d. me hlirun, leggja a san vi SI og loks helminga BX aftur, til a vihalda v sem p. Hr a nean er forritsbtur sem gerir etta:

              ...
           shl     bx, 1             ; Tvfalda BX til a vsa  vektor
           mov     ax, [si+bx]       ; N  A[p]
           shr     bx, 1             ; Breyta BX aftur  p
              ...
Athugi a tlast er til a QF-falli s sjlfsttt, n vvrra breyta. a er v tlast til ess a ekki su skilgreindar breytur gagnasegmenti fyrir QF-falli. A sjlfsgu arf a skilgreina minniplss fyrir vektorinn, en hann er skilgreindur aalforritinu og bendir hann sendur niur falli. Ef i urfi a nota aukaminni fallinu, noti staflann (me push og pop), en i ttu a geta komist af me bara gistu. Nota m gistun, AX, BX, CX (sem er vifang), DX (sem er vifang), DI, SI (sem er vifang) og BP (ath. a ef BP er nota sem bendir arf a setja DS: undan v). Muni bara eftir v a fora eim gistum sem i breyti upphafi fallsins og setji san gildin aftur au lok fallsins.

Hr er mun betra slembitlufall: slembi16.asm, fyrir sem hafa huga slku. etta fall er a vsu aeins hgvirkara og notar bi AX og DX fyrir upphafsgildi (si).


hh (hja) hi.is, 10. oktber, 2001.