Doppelt verkettete Liste / Warteschlange!
-
Hallo an das Forum!
auch ich möchte meinen ersten Post dazu nutzen, endlich mal das Thema doppelte Liste zu verstehen. Ich programmiere zum Spass und versuche mich in Info-Stoff reinzuarbeiten.. aber ich scheitere z.Zt. seit 2 Tagen an der logischen Umsetzung für eine doppelt verkettete Liste.Die lineare Liste war recht einfach und verständlich, doch nun komme ich mit der doppelten überhaupt nicht klar.
beim googlen, habe ich zwar unmengen an Seiten gefunden die das Thema behandeln, aber alle diese erklären es für mich zu unverständlich
oder ich habe seit 2 Tagen ein mächtiges Brett vorm Kopf 
Wer von Euch hat den einen Beispielcode, der ganz simpel und unkompliziert eine doppelt verkettete Liste demonstriert...
*seufz wenn es ein Buch Doppelt-Verkettete Listen für Dummies gäbe, wäre ich der erste Käufer
vielen Dank im voraus, und ja ich kann auch meinen source posten..aber ich wollte Eure Augen nicht mit meinem schwachen code kränken
Gruß
Lobosch
-
#include <stdio.h> struct lelement { int wert; lelement *next; //Zeiger auf nächstes Element lelement *prev; //Zeiger auf vorheriges Element }; lelement * init(int neu){ lelement *back = new lelement; //legt neues Element an back->wert = neu; // weist den Wert zu back->next = NULL; back->prev = NULL; return back; } lelement * add(lelement * last, int neu){ lelement * back = init(neu); // neues Element erzeugen back->prev = last; // Das alte letzte Element wird zum vorletzten last->next = back; // vorletzte zeigt auf letztes return back; } void insert(lelement *prev, lelement *neu){ if (prev != NULL && neu != NULL){ neu->next = prev->next; neu->prev = prev; prev->next = neu; } } int main(){ lelement * first = init(5); // erste Element der Liste lelement * akt; int i; printf("first: %d\n", first->wert); akt = first; for (i = 1; i<11; i++){ akt = add(akt, i*20); } while (akt->prev != NULL) { printf("1: %d\n", akt->wert); akt = akt->prev; } printf("1: %d\n", akt->wert); akt = first; for (i = 1; i<5; i++){ akt = akt->next; } insert(akt, init(50)); akt = first; while (akt->next != NULL) { printf("2: %d\n", akt->wert); akt = akt->next; } printf("2: %d\n", akt->wert); return 0; }Ist in C++
Hoffe das reicht dir
-
Du meintest wohl "ist in C".
Ganz schnell zudecken und nicht mehr hingucken. Höchstens als spicker für die objektorientierte implementation.
-
ness schrieb:
Du meintest wohl "ist in C".
Vielleicht hat er es ja auch ironisch gemeint
deswegen auch das [ ] am Ende 
-
Kannst ja mal einen (reinen) C-Compiler drüberjagen, der wird schön meckern.
Ist in C++ wegen new, aber keinem reinen, weil printf.
-
im code von imhotep steckt leider der wurm drin. doppelt verkettete listen können wirklich sehr verwirrend sein. habe damit als anfänger selbst schmerzhafte erfahrung gemacht.
hier mal meine version:
struct node { node *prev,*next; int val; }; struct list { node *first_node; }; void init_list (list *lst) { lst->first_node=0; } node *find_node (list *lst, int pos) { node *nod=lst->first_node; while(pos-->0 && nod) nod=nod->next; return (pos<0 ? nod : 0); } void insert_node (list *lst, node *nod, int val) { node *new_nod=new node; new_nod->val=val; if(nod) { new_node->prev=nod; new_node->next=nod->next; if(nod->next) // if nod isnt the last list entry { nod->next->prev=nod; nod->next=new_node; } } else // insert at top of the list if nod==0 { new_node->prev=0; new_node->next=lst->first_node; if(lst->first_node) // if lst isnt empty lst->first_node->prev=new_node; lst->first_node=new_node; } } void remove_node (list *lst, node *nod) { if(nod->prev) // nod isnt first entry of lst nod->prev->next=nod->next; else lst->first_node=node->next; if(nod->next) // nod isnt last entry of lst nod->next->prev=nod->prev; delete nod; }wichtig ist, daß man nicht vergißt:
-
sowohl die zeiger des vorhergehenden als auch des nachfolgenden knotens anzupassen.
-
die sonderfälle zu berücksichtigen, in denen der knoten keinen vorgänger oder nachfolger hat. das ist der fall, wenn der knoten das erste bzw letzte element der liste ist.
es gäbe auch noch eine trickreiche implementation doppelt verketteter listen, bei der die elemente als ring angeordnet werden und die list-struktur als ein element der liste mißbraucht wird. ich wollte aber erst mal nur die standard-implementation zeigen.
ansonsten bleibt zu hoffen, daß in meinem code nicht auch der wurm steckt
-
-
imhotep schrieb:
Ist in C++ wegen new, aber keinem reinen, weil printf.
Ist auch wegen NULL kein C++.
Sieht aber ansonten gut aus, wobei ich die Vorzüge von Klassen, also Konstruktoren statt init() genutzt hätte.Edit: Das hätte ich dir auch empfohlen, Konfusius.
mfg
-
Hallo an das Forum,
vielen Dank für die Antworten!
ich habe mal nach meinem Verständnis ein kleines prog geschrieben, dass mir beweisen soll, dass eine doppelt verkettete Liste entstanden ist..
ich lasse hier zwei neue elemente zwischen Head und Tail einfügen und die Zeiger jeweils ausgeben..habe ich nach untem stehendem code das Prinzip verstanden ?
class kunde { public: int kdnr; kunde *next; kunde *prev; void zeige(); };class liste { private: kunde *head; kunde *tail; kunde *tmp; kunde *tmp2; public: void push_front(); // void pop_front(); liste(); }; liste::liste() { head=new kunde; tail=new kunde; head->next=tail; tail->prev=head; head->prev=0; tail->next=0; } void liste::push_front() { tmp=head->next; // objekt worauf Head zeigt, speichern head->next=new kunde; // Head.next zeigt auf neues Objekt tmp2=head->next; // neues Objekt wir tmp2 zugewiesen tmp2->next=tmp; // neues Objekt.next zeigt auf vormaliges nächstes objekt von head tmp->prev=tmp2; // altes objekt.prev zeigt auf das neue objekt tmp2->prev=head; // neues objekt.prev zeigt auf head cout << "\n\nNeues objekt eingefügt.\n"; cout << "Adresse des neuen objektes: " << tmp2 << "\n\n";; cout << "Adresse von Head: " << head << endl; cout << "Adresse von Tail: " << tail << "\n\n"; cout << "Head zeigt auf nächstes objekt: " << head->next << endl; cout << "Neues objekt zeigt auf vorheriges objekt: " << tmp2->prev << endl; cout << "Neues objekt zeigt auf naechstes objekt: " << tmp2->next << endl; cout << "Nächstes objekt zeigt auf vorheriges objekt: " << tmp->prev << endl; cout << "Tail zeigt auf vorheriges objekt: " << tail->prev << endl; } int main() { liste neu; neu.push_front(); neu.push_front(); cin.get(); return 0; }habe ich das Thema endlich kapiert ?
thx an alle!
-
uups.. da war ich wohl nicht eingeloggt... sorry
der Text von Krabatt ist von mir
-
Du fügst das neue Objekt zwischen head und tail ein.
Sicherlich übersichtlicher wäre es so.tmp = new kunde; // neues Objekt erzeucgen tmp2 = head->next; // Nachfolger sichern // Neues Objekt einfügen. tmp->next = tmp2; tmp->prev = head; head->next = tmp; tmp2->prev = tmp;
-
imhotep schrieb:
Du fügst das neue Objekt zwischen head und tail ein.
Sicherlich übersichtlicher wäre es so.tmp = new kunde; // neues Objekt erzeucgen tmp2 = head->next; // Nachfolger sichern // Neues Objekt einfügen. tmp->next = tmp2; tmp->prev = head; head->next = tmp; tmp2->prev = tmp;also schliesse ich daraus das ich das Thema endlich verstanden habe
danke für die Hilfe!
lobosch