Dotaz: Dvojite spojity kruhovy seznam v C

[tomes.io]

Ahoj,

resim syntaxi propojeni posledniho pridaneho prvku s prvnim do kruhu, aby vznikl kruhove spojovy seznam tak, aby jej slo tisknout jak zepredu, tak zezadu. Asi jsem se ztratil a zamotal v tom. Teoreticky snad chapu, co s cim mam spojit (novy.next musi odkazovat na posledni, posledni.previous odkazuje na prvni). Rozkreslil jsem si to, ale pri implementaci se nejak nedari.

Nasledujici kod mi vypise postupne seznam od prvniho po posledniho, ale u obraceneho vypisu vypise jen posledni prvek a pak skonci. Potreboval bych nakopnout, urcite to bude nejaka blbost :}

struct cllnode {
char name[30];
struct cllnode *next, *prev;
};
//The circular linked list tail pointer.
struct cllnode *tail = NULL;

void addNode(struct cllnode *newnode) {

if (tail == NULL) {
  tail = newnode;
  newnode->next = tail;
  newnode->prev = tail;
} else {

  newnode->next = tail->next;
  newnode->prev = tail;
  tail->prev = newnode;
  tail->next = newnode;
  
  tail = newnode;
 }

}
int main() {
int value = 0;
char student[30];

//node pro traverzovani
struct cllnode *current;

printf("Zadej jmena studentu:\n");
do{
  
  struct cllnode *newnode;
  newnode = (struct cllnode *)malloc(sizeof(struct cllnode));
  scanf("%s", student);
  strcpy(newnode->name, student);
  addNode(newnode);
  value++;
}while(strcmp(student, "NA") != 0);

//print
current = tail->next;
do {
    printf("%s\n", current->name);
    current = current->next;
} while (current != tail->next);

//print reverse

current = tail->prev;
do {
    printf("%s\n", current->name);
    current = current->prev;
} while (current != tail->prev);


  printf("Celkovy pocet studentu: %d\n", value - 1);
  
  //Clean up current.
  current = NULL;

return 0;
}

Predem diky.

---

---

Odpovědi

[Michal Kubeček]

Nechce se mi to zkoumat moc podrobně, takže tam možná bude víc chyb, ale hlavní problém je asi tady:

--- list.c.orig 2012-04-09 21:44:55.485782284 +0200
+++ list.c      2012-04-09 21:45:32.457339644 +0200
@@ -16,7 +16,7 @@ if (tail == NULL) {
 
   newnode->next = tail->next;
   newnode->prev = tail;
-  tail->prev = newnode;
+  tail->next->prev = newnode;
   tail->next = newnode;
   
   tail = newnode;

[tomes.io]

No, to vim taky ze bude nekde tady, ale kde :)

[tomes.io]

Mozna ale uvazuji blbe. Vychazim z nasledujiciho "algoritmu" pro pridani na konec seznamu a propojeni s prvnim prvkem.

prvni.dalsiodkazuje na novy prvni.predesly odkazuje na novy novy.dalsi odkazuje na posledni

Ovsem je jasne, ze pri kruhovem seznamu nejde moc mluvit o "prvnim" a "poslednim". Pri traverzovani ze urci nejaky vychozi node. Jenze poradm i nedochazi, jak to naimplementovat poradne z vyse uvedeneho kodu... at to zkousim jak to zkousim, porad mi nedochazi co s cim propojit syntakticky.

[tomes.io]

Michale, jsem slepy, nevsiml jsem si, ze v tom kodu mi pises reseni :) Ted to fakci jak ma a muzu se konecne osunout kupredu. Diky moc"

[l4m4]

Upřímně, přestal jsem to číst, když jsem zjistil, že tail je jakási globální proměnná. Proč?

Seznam je buď NULL, pak neobsahuje žádné prvky, nebo není, pak přidávání nepotřebuje žádné tail, ale dvě věci: nový prvek a místo, kam se má přidat.

Má-li seznam mít speciální místo, kam se mají přidávat prvky, je otázka, zda ho vůbec implementovat jako cyklický (u cyklických senzamů bych většinou čekal, že prvky se přidávají na různá místa podle nějakého kritéria). K projití prvků oběma směry stačí mít k disposici head a tail, což znamená, nebude-li se to takhle procházet často, mít libovolný prvek a na head či tail při vypisování dojet od toho prvku.

Je-li třeba, aby kruhový seznam měl nějaký speciání prvek, tak je zapotřebí ho zahrnout do protokolu/datové struktury, tedy asi vždy předávat seznam ukazetelem na tento speciální prvek (a z funkcí, které mohou seznam modifikovat, ukazatel na nový speciální prvek vracet).

[tomes.io]

Kod je puvodne dvojite spojity seznam, s head a tail. Snazim se ho modifikovat na kruhove spojity, protoze v dalsi fazi bude treba cyklicky seznam a budu potrebovat vkladat a mazat prvky dle parametru. K tomu jsem se ale jeste nepropracoval. Potrebuju ted mit nejakou kostru programu, cyklicky spojeny seznam, kterym jde rotovat tam a zpet. Pak muzu jit dal...

[Bluebear]

Pamatuj: průměrní se inspirují, ti nejlepší kradou. Najdi na netu nějakou knihovnu, kde to je (přednostně takovou, kde je to už odladěné) a sprostě to opiš

(Pozor na Wikipedii a méně používané knihovny - spousta jich to má skoro dobře, až na pár speciálních případů.)

[tomes.io]

To jsem samozrejme zkusil a hledal vsudemozne, ale nasel jsem maximalne jen jednostranne spojity kruhovy seznam..

[tomes.io]

Navic ja tomu chci opravdu porozumet, ne jen tupe opisovat ;)

[Bluebear]

Neříkal jsem opisovat tupě. Z korektní implementace se to pochopí lépe než z nuly

[tomes.io]

A nejaky tip kde hledat. Mozna blbe googlim, ale proste nic kloudnyho jsem nenasel...

[Bluebear]

Hm... musím přiznat, že tady jsi mě dostal... taky nic moc nemám; jen školní zadání v Javě, kde patrně učitel nachází zvrhlé potěšení v tom, jak se studenti v těch objektech topěj. Plus pár otázek "mně to taky nechodí".

A wikipedii, ale to jsi určitě viděl taky.

[martin-ux]

tiez nevidim nic zle, ked sa clovek inspiruje cudzim kodom, resp. ked sa od neho uci.

ak si na linuxe, tak sa mozes pozriet do zdrojakov kernelu, napr. include/linux/list.h.