[c]lista dwukierunkowa cykliczna, usuwanie elementu

Witam, piszę na zajęcia program, który wykorzystuje listę dwukierunkową cykliczną. Wszystko szło bezproblemowo, dopóki nie trafiłem na usuwanie elementu, wygląda na to że coś zrobiłem nie tak, jeśli chodzi o wskaźniki na poprzednie elementy. Kod poniżej:

#include <stdlib.h>
#include <stdio.h>

typedef struct str_glowna {
  int id;
  int val;
  struct str_glowna *nxt, *prv;
} Accelerator;

Accelerator *pozycja=NULL; //wskaznik na aktualna pozycje akceleratora

/* AddElement - funkcja dodaje element do listy. Przyjmuje wskaznik na element
 * po którym ma znajdować się nowy element i przechowywaną wartość.
 */
Accelerator * AddElement(Accelerator *where, int wartosc) {
  Accelerator *newlyAdded;
  newlyAdded = malloc(sizeof(Accelerator));
  if (pozycja==NULL) { // lista jest pusta
    newlyAdded->id = 1;
    newlyAdded->val = wartosc;
    newlyAdded->nxt = newlyAdded;
    newlyAdded->prv = newlyAdded;
    pozycja=newlyAdded;
  } else {
    newlyAdded->id = where->id + 1;
    newlyAdded->val = wartosc;
    newlyAdded->nxt = where->nxt;
    where->nxt = newlyAdded;
    newlyAdded->prv = where;
  }
  return newlyAdded;
}

/* DeleteElement - usuwa element z listy. Przyjmuje wskaźnik na element do usunięcia
 * Zwraca 0 w przypadku błedu, 1 w przypadku powodzenia.
 */
int DeleteElement(Accelerator *which) {
  if (pozycja==NULL) // lista jest pusta
    return 0;
  else {
    if (pozycja==which)
      pozycja=which->nxt;
    Accelerator *setprv, *setnxt;
    setprv = which->prv;
    setnxt = which->nxt;
    setprv->nxt = setnxt;
    setnxt->prv = setprv;
    free(which);
    which=NULL;
    return 1;
  }
}

void PrintList() {
  if (pozycja==NULL) { // lista jest pusta
    printf("Lista jest pusta");
  } else {
    Accelerator *print = pozycja;
    int firstid = print->id;
    do {
      printf("%d ", print->val);
      print = print->nxt;
    } while(firstid != print->id);
  }
}

int main(int argc, char** argv) {
  Accelerator *a, *b, *c, *d, *e, *f, *g, *h, *i, *j;
  a = AddElement(pozycja, 11);
  b = AddElement(a, 12);
  c = AddElement(b, 13);
  d = AddElement(b, 14);
  e = AddElement(b, 15);
  f = AddElement(b, 16);
  g = AddElement(c, 17);
  h = AddElement(c, 18);
  i = AddElement(c, 19);
  j = AddElement(c, 20);

  PrintList();
  DeleteElement(c);
  printf("\n");
  PrintList();
  return (EXIT_SUCCESS);
}

Zanim cokolwiek usunę, jest ładnie, lista wygląda, tak jak wyglądać powinna. Wynikiem jest "11 12 16 15 14 13 20 19 18 17". Po usunięciu lista się skraca do "11 12 20 19 18 17". Pół dnia szukam błędu, pomożecie? Co ciekawe, jest w porządku, jeśli elementy dodaje po kolei, po elemencie a następuje b, potem c, d i tak dalej.

namieszales troche. powiedz mi najpierw:

• czym wg Ciebie jest tutaj 'id'
• czym w Twoim zamysle jest 'pozycja' tzn czym jest aktualna pozycja akceleratora

Na początku, dzięki za zainteresowanie tematem. :) Już tłumaczę, id jest wyróżnikiem elementu, stosuje go np. przy wyszukiwaniu elementu. Jako że lista jest cykliczna, wyszukiwanie kończę nie przy napotkaniu nulla (bo takiego nie ma), a wtedy, gdy dojdę do elementu który ma takie id jak ten, od którego zacząłem wyszukiwanie. Widać tą metodę w funkcji PrintList.

Co do pozycji. Jest to wskaźnik na element nad którym aktualnie pracuje. (wybiegam tym trochę wprzód, do implementacji samej listy, prócz samego jej utworzenia jest raczej nieprzydatny)

no niestety id nie jest unikalny w Twojej implementacji. w AddElement w 'else' masz takie cos:
newlyAdded->id = where->id + 1;
tym sposobem od tej chwili juz 2 elementy mają takie samo id: nowy i ten ktory jest bezposrednio po nim.

nie rozumiem tez po co tworzysz
Accelerator *setprv, *setnxt;
w DeleteElement 'else'. zauwaz ze są to lokalne wskazniki wiec zostaną usuniete po wyjsciu z funkcji. ja bym zrobil jakos tak:

Accelerator *tmp_which;
tmp_which = which;
which->prv->nxt = which->nxt;
which->nxt->prv=which->prv; // od tego momentu zeby nie tmp_which = which; mialbys memory leak
free(tmp_which);

O faktycznie, początkowo to (id) miało trochę inaczej wyglądać, chyba zapomniałem to poprawić. No nic jeszcze pomyślę nad tym, nie to jest moim problemem teraz. :) No i racja, głupi jestem, dwa tymczasowe elementy nie są mi potrzebne :)

Nie rozumiem konstrukcji "which->prv->nxt", czy to nie jest równe po prostu which? Ponadto twoje rozwiązanie daje praktycznie ten sam efekt, co moje. (wynik: "11 12 13 20 19 18 17")

Zaobserwowałem też ciekawy efekt. Wrzucając linijkę

printf ("%d", e->prv->val);

tuż po utworzeniu elementów (przy czym e to jeden z omyłkowo usuwanych elementów) okazuje się, że wskazuje on na element o wartości 12, tuż po tym elemencie następuje ten błąd. Nie wiem dlaczego tak jest, czyżby problem leżał w funkcji dodającej element?

eighteenthsecond napisał(a)

Nie wiem dlaczego tak jest, czyżby problem leżał w funkcji dodającej element?

Dokładnie, brakuje Ci

  } else {
    newlyAdded->id = where->id + 1;
    newlyAdded->val = wartosc;
    newlyAdded->nxt = where->nxt;
    where->nxt->prv=newlyAdded;             //tej linijki
    where->nxt = newlyAdded;
    newlyAdded->prv = where;
  }

W wypisywaniu możesz się obejść bez id:

  } else {
    Accelerator *print = pozycja;
    do {
      printf("%d ", print->val);
      print = print->nxt;
    } while(pozycja != print);
  }

wystarczy wykorzystać globalną pozycję.

which to jest caly element. i rozumiesz ze which = x oznacza przypisanie adresu x dla wskaznika which

which->prv->nxt natomiast oznacza pole nxt wewnatrz elementu ktory jest przed which a wiec which->prv->nxt = x oznacza przypisanie adresu x dla pola elementu poprzedzajacego which, nie zmiane calego elementu

mniej wiecej wyglada to tak:

pozycja startowa

a) el 2->prv->nxt = el 3

b) el 2 = el 3

musisz wiedziec jak to wszystko wyglada zeby miec pewnosc ze nie tracisz pamieci

Ok, teraz wszystko jasne. Usuwanie działa świetnie, dzięki wam za pomoc. :)