C in previdno sprehanje

Vse o programiranju na in za PC

Moderatorji: Kroko, tilz0R

C in previdno sprehanje

OdgovorNapisal/-a zanka » 23 Feb 2017, 00:58

Verjetno ste kdaj naprogramirali povezan seznam (linked list) in naleteli na problem brisanja med sprehajanjem.
Tipično se po vozliščih n sprehaja kot
Koda: Izberi vse
for(n = first; n; n = n->next)

ali
Koda: Izberi vse
n = first;
while (n) {
...
n = n->next;
}

Vendar včasih koda znotraj zanke (je pač takšna) zbriše trenutno vozlišče n in nastane problem, saj naslednik (n->next) ne obstaja več. Ena rešitev je naslednja koda
Koda: Izberi vse
for(n = first; n && (m = n->next, 1); n = m)

oziroma za lažje razumevanje
Koda: Izberi vse
n = first;
while (n) {
m = n->next;
...
n = m;
}

Pri tem naslednika, shranimo v m in zato preživi propad vozlišča n.

Poznate še kakšne druge rešitve?
Uporabniški avatar
zanka
 
Prispevkov: 2567
Pridružen: 17 Mar 2016, 01:16
Zahvalil se je: 113 krat
Prejel zahvalo: 254 krat
Uporabnika povabil: DusanK
Število neizkoriščenih povabil: 50

Re: C in previdno sprehanje

OdgovorNapisal/-a gumby » 23 Feb 2017, 07:30

Pred brisanjem vozlišča moraš najprej popraviti pointer v prejšnjem, drugače bo ta kazal na napačen naslov. Recimo da imaš tole:
a -> b -> c -> ...
Pred brisanjem vozlišča b moraš najprej a->next spremeniti v b->next (torej c). V zanki pa gledaš, če obstaja a->next.
my brain hurts
Uporabniški avatar
gumby
 
Prispevkov: 2570
Pridružen: 14 Jan 2015, 19:49
Kraj: Lendava
Zahvalil se je: 108 krat
Prejel zahvalo: 604 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 64

Re: C in previdno sprehanje

OdgovorNapisal/-a zanka » 23 Feb 2017, 12:16

Vozlišča se briše v podfunkcijah (funkcijah katere se kliče med sprehajanjem) in ni deterministično (lahko se, lahko se ne briše), zato mora biti sprehajanje previdno in neodvisno.

Da se ne bi sprehajal po vseh vozliščih, da bi predhodniku nastavili novega naslednika, uporabljam double linked list, v katerem brišem
Koda: Izberi vse
  if ( n->next )
    n->next->prev = n->prev;
  if ( n->prev )
    n->prev->next = n->next;
  if ( n_first == n )
    n_first = n->next;
  if ( n_last == n )
    n_last = n->prev;

Čeprav, kot vidim bi se dalo tole še skrajšati v
Koda: Izberi vse
  if ( n->next )
    n->next->prev = n->prev;
  else
     n_last = n->prev;
  if ( n->prev )
    n->prev->next = n->next;
  else
    n_first = n->next;
   

Vedno dva pogoja in dve prirejanji.

Torej so določene prednosti in slabosti. In zaenkrat nimam mnenj, kdaj in čemu kakšnega uporabiti.
Uporabniški avatar
zanka
 
Prispevkov: 2567
Pridružen: 17 Mar 2016, 01:16
Zahvalil se je: 113 krat
Prejel zahvalo: 254 krat
Uporabnika povabil: DusanK
Število neizkoriščenih povabil: 50


Vrni se na Programski jeziki

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost