Doppelt verkettete Liste / Warteschlange!
-
Huhu
das ist mein erster Beitrag also hallo!
super forum so nebenbei doch jetzt hab ich ein problem!ich mache gerade eine ausbildung zum Assis. für Informatik wir haben natürlich auch programmieren!
Sind jetzt bei Dynamischer Speicherverwaltung!
Unsere Dozentin hat uns eine "Hausaufgabe" gegeben, aber uns nicht soo wirklich erklärt was "das" machen soll!Es geht um eine Doppelt verkettete Liste nach dem Pinzip der Warteschlange [queue]
also FIFO [First in First out]Nun sollen wir ein beispiel schreiben wo man was anhängen kann (hinten) und was ausgeben kann und zwar (vorwärts) und (rückwärts)
Nun ich hab im moment nicht wirklich den Plan, wie ich vorgehen soll!
Könntet ihr Profis mir bitte helfen?
vielen Dank
Codeman
-
Die Idee ist, das jedes Element einen Verweis(Pointer) auf seinen Nachfolger in der Kette, und im Falle einer Doppelverkettung auch noch auf den Vorgänger hat. Das Ende der Kette kennzeichnest du mit einem NULL Pointer.
Also etwa so:
struct Kettenglied { void* PointeraufDaten; Kettenglied *vorgängerglied; Kettenglied *nachfolgeglied; };Nun musst du dir nur einen Pointer auf das 1. Glied merken.
Das obere Ende der Kette findest du, indem du dir jweils das nachfolgeglied anschaust, bis der Pointer NULL ist.Neue Sachen kommen hinzu, indem du eine neues Ketteglied mit new erstellst und dann kriegst du ja den Pointer davon und den schreibst du in das 1.Glied als Vorgänger rein. Damit hast du unten/hinten was an die Kette rangehängt.
-
SeppSchrot schrieb:
Also etwa so:
struct Kettenglied { void* PointeraufDaten; Kettenglied *vorgängerglied; Kettenglied *nachfolgeglied; };Templates??
Gruß
-
FireFlow schrieb:
Templates??
Wie meinen?
-
template<class Type> struct Node { Type Data; Node<Type>* prev; Node<Type>* next; };Warum nicht so?
Gruß
-
FireFlow schrieb:
Warum nicht so?
Vielleicht, weil ich davon ausgegangen bin, dass ein Neuling in Sachen dynamischer Speicherverwaltung genug mit dem Pointerverständnis zu tun hat.
Nicht dass die Templates nicht eleganter sind, 'dem Auge wohlgefällig' ;),
aber vielleicht ein bissl viel auf einmal, ne?
-
wow danke für euere hilfe aber das mit dem struct ist mir schon klar mir fehlt aber ein pra. beispiel ich weis net wie ich das anwenden soll!
ach und ja das ohne template ist besser
codeman
-
sry wegen doppelpost
aber ich wollte nochmal draufaufmerksam machen
hat denn niemand ein praktisches beispiel ich kann mir so nichts drunter vorstellen!danke codeman
-
Vielleicht helfen dir die bildchen weiter um dir das besser vorstellen zu könnne
http://www.saar.de/~awa/jlisten.htm
-
Stell dir mal vor du hast ein Array (oder std::vector) in dem du regelmäßig viele Elemente löscht oder einfügst. Dann musst du ständig Speicher neu allokieren und alle Elemente kopieren. Bei so einer Liste reicht es eine Node zu löschen und die Pointer neu zu setzen - beim Einfügen auch.
Gruß
-
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;