Doppelt verkettete Listen
-
Das ist eine Aufgabe, die wir im Laufe des Semesters immer wieder erweitert haben. Zuerst sollten wir das ganze mit einem Array lösen, aber in der aktuellen Aufgabe sollen wir das ganze um die doppelt verkettete Liste erweitern.
-
Du schreibst, dass immer nur die selben Daten ausgegeben werden. Welche sind das denn, die ersten oder letzten Eingaben?
Wie besorgst du Speicher für kontoptr (bei insert)?
Warum übergibst du den Pointer current an die Funktionen?
-
DirkB schrieb:
Du schreibst, dass immer nur die selben Daten ausgegeben werden. Welche sind das denn, die ersten oder letzten Eingaben?
Der Name des Kontoinhabers und der Kontostand sind bei allen Knoten halt immer die selben, obwohl ich jedes Mal was anderes eintippe. Es werden dann zwar neue Knoten erstellt, aber der Inhalt ist identisch.
Wie besorgst du Speicher für kontoptr (bei insert)?
/* Knoten erzeugen und ihm ein Konto zuweisen */ struct node* new = (struct node*)malloc(sizeof(struct node)); new->konto = kontoptr;Ich war der Meinung, dass ich es damit tuhe, aber eventuell war es ein Irrglaube
Warum übergibst du den Pointer current an die Funktionen?
Das weiß ich nicht genau, aber es war in einem Online-Tutorial so beschrieben.
-
mr_unknown schrieb:
DirkB schrieb:
Du schreibst, dass immer nur die selben Daten ausgegeben werden. Welche sind das denn, die ersten oder letzten Eingaben?
Der Name des Kontoinhabers und der Kontostand sind bei allen Knoten halt immer die selben, obwohl ich jedes Mal was anderes eintippe. Es werden dann zwar neue Knoten erstellt, aber der Inhalt ist identisch.
Das ist nicht die Antwort auf meine Frage. Die Frage war, welche von den eingegebenen Daten ausgegeben werden. Wann hast du diese Daten eingegeben? Zuerst, zuletzt oder zwischendurch.
mr_unknown schrieb:
Wie besorgst du Speicher für kontoptr (bei insert)?
/* Knoten erzeugen und ihm ein Konto zuweisen */ struct node* new = (struct node*)malloc(sizeof(struct node)); new->konto = kontoptr;Da bekommt kontoptr aber kein Wert oder Speicher zugewiesen.
Wo wird kontoptr ein Wert zugewiesen? (Alsokontoptr = ...;)
Siehe auch zweite Frage in meinem ersten Post.
-
Zu 1: Es werden für alle Knoten die Eingaben übernommen, die ich zuletzt getätigt habe.
Zu 2: Da liegt wohl mein Fehler. Das muss ich mir später noch genauer ansehen und es vermutlich überarbeiten.
Danke dir schomal für deine Hilfe!
-
Du kannst ja erstmal vor insert ein
++i; kontoptr = &konten[i]; insert(...und später( oder auch gleich )
kontoptr = malloc(...); insert(...Nebenbei sehe ich in insert auch nirgendwo ein
return.
-
Genial, vielen Dank! Und schon ist das Problem gelöst.
/* Knoten erzeugen und ihm ein Konto zuweisen */ struct node* new = (struct node*)malloc(sizeof(struct node)); kontoptr = (Konto*)malloc(sizeof(kontoptr)); new->konto = kontoptr;Die Sache war die, dass ich für den kontoptr kein Speicher reserviert habe.
-
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?
