Doppelt verkettete Listen
-
mr_unknown schrieb:
Die Sache war die, dass ich für den kontoptr kein Speicher reserviert habe.
Das war mir klar denn
DirkB schrieb:
mr_unknown schrieb:
Konto* kontoptr = &konten[i];Wenn du schon ein Array mit Kontodaten hast, warum dann noch die Liste?
Btw. erhöst du überhaupt i?Das stand bereits in meiner ersten Antwort.
Die Fragen hattest du leider nicht beantwortet, oder nicht richtig gelesen.
-
Ich hänge leider wieder an der Aufgabe, und zwar bei der Sortierung der eingegebenen Namen. In meinen zuvor geposteten Code habe ich da schon einen Ansatz mit strcmp gehabt(), aber das funktioniert natürlich so nicht.
Wie ich jetzt gelesen habe, brauch ich wohl, um eine doppelt verkettete Liste zu sortieren, zwei weitere Zeiger preptr und postptr. Ist es so richtig oder gibt es einen einfacheren Weg? Und wenn ich mit meiner Annahme richtig liege, könnte mir vielleicht jemand einen Ansatz geben wie ich die weiteren Zeiger deklarieren soll?Ich hab schon einiges probiert, krieg es aber leider noch nicht hin.
-
Verkettete Listen sind Akademikerneurosen und u.v.a. nicht für Resortierung geeignet.
-
Die Sortierung soll schon beim Einfügen erfolgen.
Ein Ausschnitt aus der Aufgabe: "Die Kontodaten sind auch in einer doppelt verzeigerten Liste abzuspeichern. Die Liste soll nach Namen sortiert sein. Sie ist einmal in alphabetischer Folge auszugeben und einmal in der Reihenfolge gegen das Alfabet."
Wir sollen die Strings mit strcmp() vergleichen und sortieren. Meine Ansätze brachten mir aber bisher leider keinen Erfolg.
-
mr_unknown schrieb:
Die Sortierung soll schon beim Einfügen erfolgen.
...
Wie ich jetzt gelesen habe, brauch ich wohl, um eine doppelt verkettete Liste zu sortieren, zwei weitere Zeiger preptr und postptr. Ist es so richtig oder gibt es einen einfacheren Weg?ja, mit zwei zeigern geht das, wie die heißen ist wurscht. unser dozent hat die node-strukturen wie rechteckige kisten an die tafel gemalt, die mit den prev- und next-zeigern verbunden sind. in gedanken kann man sich dann durch die liste hangeln, indem man die pre- und nextptr verschiebt und man kann sich überlegen, welches element welche zeiger speichern muss, um ein neues element einzufügen.
+-------+ +-------+ NULL <---|prev |<---|prev | | next |--->| next|---> NULL +-------+ +-------+ ^ ^ | | | | preptr nextptr +-------+ Neuer, eizufuegender Knoten, NULL <---|prev | mit NULL initialisierten Zeigern. | next|---> NULL +-------+ich fand das für die vorstellung ganz hilfreich und meine ersten listen haben nur mit hilfe von stift und zettel geklappt. probier das doch erstmal.
-
[quote="B.B."]
mr_unknown schrieb:
+-------+ +-------+ NULL <---|prev |<---|prev | | next |--->| next|---> NULL +-------+ +-------+ ^ ^ | | | | preptr nextptr +-------+ Neuer, eizufuegender Knoten, NULL <---|prev | mit NULL initialisierten Zeigern. | next|---> NULL +-------+Respekt !
Ich haette es mit Paint gemalt, aber ASCII > mein Zeichenkuenste ; )
-
DerMaddi schrieb:
Respekt !
Ich haette es mit Paint gemalt, aber ASCII > mein Zeichenkuenste ; )ja, bruder, so ist das eben im leben!
-
Musste erstmal über den Kommentar des vorletzten Beitrags lachen.
@B.B.: Danke für die schöne Übersicht, aber auch wenn du es super dargestellt hast, bringt es mich nicht viel weiter. Ich kann das Prinzip verstehen, aber leider enden meine Versuche es in C umzusetzen, mit Abstürzen des Programms. Diese ganzen Zeiger bringen mich durcheinander.
-
du hast doch inzwischen einiges geändert oder? poste das doch mal komplett.
-
Richtig erkannt.
Und deshalb sind verkettete Listen für Alltagsaufgabe wie du sie vorhast denkbar ungeeignet, besonders für Anfänger.
Nimm Arrays wenn deine Elemente gleich groß sind und ein Zeigerarray falls sie es nicht sind.
Da besteht das Sortieren aus einem Einzeiler.
-
@ B.B.: Da sitzt ich aber lieber noch ein paar Stunden dran und poste dann später, wenn ich denke, dass es halbwegs richtig ist.
@Wutz: Ich würd ja nur zu gerne Arrays nehmen, aber die Aufgabe von der Uni lautet es mit doppelt verzeigerten Listen umzusetzen.
-
Listen lassen sich wunderbar sortieren, ganz besonders, wenn Kopien der in ihr enthaltenen Objekte sehr teuer sind. Man kann keinen Quicksort drüber lassen, aber Mergesort ist ja auch O(n * log(n)).
Glücklicherweise ist der damit verbundene Aufwand für diese Aufgabenstellung gar nicht notwendig. Wenn du die Objekte immer so in die Liste einfügst, dass sie nachher sortiert ist, kannst du beim Einfügen davon ausgehen, dass sie sortiert ist. Damit reduziert sich die Problemstellung darauf, das kleinste Objekt in der Liste zu finden, das größer ist als der Neuzugang und den Neuzugang davor einzufügen.
-
Ich habe jetzt das Sortieren beim Hinzufügen von Elementen folgendermaßen gelöst:
Strukturen:
typedef struct { char* name; /* Kontoinhaber */ unsigned int kontoNr; /* Kontonummer */ double kontoStnd; /* Kontostand */ double zinsS; /* Zinssatz */ double annuitaet; /* Annuitaet */ char habenOderDarl; /* Guthaben/Darlehen */ unsigned int laufZt; /* Laufzeit */ } Konto; struct node{ char name[30]; int kntnr; struct node *prev; struct node *next; }; struct node* head = NULL; /* Zeiger auf Anfang der Liste */ struct node* tail = NULL; /* Zeiger auf Ende der Liste */Funktionen:
// hier wird alphabetisch sortiert! void hinzufuegen(Konto* element) { struct node *new; /* Zeiger von dem neuen Element in der Liste new */ new = (struct node*)malloc(sizeof(struct node)); strcpy(new->name, element->name); new->kntnr = element->kontoNr; if(head == NULL) /*Falls die Liste leer ist*/ { new->next = NULL; /*Nächstes Element existiert nicht*/ new->prev = NULL; /*Nächstes Element existiert nicht*/ head = new; /*Element ist Listenbegin*/ tail = new; /*Element ist Listenende*/ } else { struct node* l = head; /* Zwischenspeicher */ while((l != NULL) && (strcmp(new->name, l->name) >= 0)) { l = l->next; /* Zur nächsten Position springen, da Reihenfolge eingehalten werden soll */ } if(l == NULL) /* Wenn größer als erstes Element */ { new->next = NULL; /* Es gibt kein größeres Element als dieses */ new->prev = tail; /* Vorheriges Ende ist jetzt vorletztes El.*/ tail->next = new; /* Zeiger des vorherigen Endes auf neues Element setzen*/ tail = new; /* Neues Element ist ab sofort Listenende */ } else /*Falls Element kleiner als Listenende*/ { if(l == tail) /*Nur ein Element in der Liste*/ { new->next = head; /* Neues Element zeigt auf alten Anfang */ new->prev = NULL; /* Neues Element hat keinen Vorgänger, da nur zwei Elemente in der Liste und der alte Anfang größer als neues Element ist */ head->prev = new; /* Der Prev-Zeiger des alten Anfangs wird nun auf das neue Element gesetzt */ head = new; /* Das neue Element wird allgemein als Listenanfang festgelegt */ } else /*Es existieren mehrere Elemente in der Liste. Man muss das neue mittendrin einfügen*/ { new->next = l; /* neues Element zeigt auf ermittel- ten Nachfolger*/ new->prev = l->prev; /* Vorgänger des neuen Elements ist Vorgänger des alten Elements */ new->next->prev = l; /* Voränger und Nachfolger zeigen jetzt auf neues Element */ new->prev->next = l; /* Vorgänger und Nachfolger zeigen jetzt auf neues Element */ } } } } /* Elemente aus der doppelt verlinkten Liste ausgeben */ void listenAusgabe() { struct node* ptr = head; /* Hilfspointer */ printf("\nAlphabetisch:\n\n"); while(ptr != NULL){ printf("%s, %d\n\n", ptr->name, ptr->kntnr); ptr = ptr->next; /* Schleifenpointer zeigt auf den Next-Zeiger */ } } /* Elemente aus der doppelt verlinkten Liste gegen das Alphabet ausgeben */ void listenAusgebe_gA() { struct node* ptr = tail; /* Hilfspointer */ printf("\nGegen das Alphabet:\n\n"); while(ptr != NULL) { printf("%s, %d\n\n", ptr->name, ptr->kntnr); ptr = ptr->prev; /* Schleifenpointer zeigt auf den Prev-Pointer */ } }Es funktioniert auch solang kein Element zwischen bereits 2 vorhandenen Elementen hinzugefügt werden soll. Das klappt leider nicht, aber ich komme einfach nicht drauf wieso. Sieht vielleicht jemand auf Anhieb den Denkfehler?
-
In Zeile 54 und 56 solltest du die Zeiger von den Nachbarn umbiegen auf das gerade neu eingefügte Element und nicht auf das gefundene "alte" Element.
-
Vielen Dank, CStoll, für die super schnelle Antwort!
-
else /*Es existieren mehrere Elemente in der Liste. Man muss das neue mittendrin einfügen*/ { new->next = l; /* neues Element zeigt auf ermittel- ten Nachfolger */ new->prev = l->prev; /* Vorgänger des neuen Elements ist Vorgänger des alten Elements */ l->next->prev = new; /* Voränger und Nachfolger zeigen jetzt auf neues Element */ l->prev->next = new; /* Vorgänger und Nachfolger zeigen jetzt auf neues Element */Hab es folgendermaßen geändert, aber wenn es schon 2 Elemente gibt und das neue zwischen denen einsortiert werden müsste, wird es nicht gemacht. Hat vielleicht noch jemand einen Tipp?
Irgendetwas ist immernoch falsch, aber ich sitze hier schon über eine Stunde und finde nicht was.
-
Schau dir nochmal die dritte und vierte Zuweisung an.
Ausgangspunkt sollte immer das neue Element sein (also new->... ), andernfalls wird es unübersichtlich, weil die Zuweisungen nicht mehr vertauscht werden können (vorausgesetzt sie sind überhaupt korrekt).
-
Danke, aber bringt alles nichts. Der Fehler ist wohl weiter oben. Ich zerbreche mir seit Tagen den Kopf wie ich die Knoten richtig sortiere, kriege es aber nicht hin.
-
Ein paar Anmerkungen:
Den Fall der leeren Liste kannst du sehr einfach mit dem Fall kombinieren, wenn ans Ende der Liste eingefügt wird (l==NULL). Eine Reduzierung der zu berücksichtigen Fälle ist immer günstig.Die Bedingung (l==tail) ist nicht das, was du benötigst, Eine Sonderbehandlung benötigst du nicht (nur) für Listen mit einem Element, sondern immert dann, wenn du vor dem Anfang einfügst, die Bedingung muss folglich (l==head) lauten.
Und wie schon erwähnt ist der folgende Block auch nicht korrekt was die Anpassung der Links betrifft.
Man kommt übrigens auch ohne jede Fallunterscheidung aus, denn die eigentliche Frage, die zu stellen ist, ist, ob benachtbarte Knoten (zum neuen Knoten) existieren oder nicht.
struct node* l = head; while((l != NULL) && (strcmp(new->name, l->name) >= 0)) { l = l->next; } new->next = l; new->prev = ( l ? l->prev : tail ); ( new->next ? new->next->prev : tail ) = new; ( new->prev ? new->prev->next : head ) = new;
-
Vielen Dank für die Hilfe!
Ich werde gleich versuchen es umzusetzen. Mal sehen, ob ich dieses mal Erfolg habe und endlich dieses Kapital abhacken kann.
