Doppelt verkettete Listen

mr_unknown

Hallo Leute,

ich habe an der Uni eine Aufgabe bekommen eine dopplet verkettete Liste zu erstellen, deren Elemente Kontodaten der Kunden enthalten sollen.
Nach 2 Tagen hab ich es auch soweit hinbekommen, aber irgendwo ist noch der Wurm drin und ich finde den Fehler nicht. Vermutlich hab ich irgendeinen Pointer falsch gesetzt.
Problem: Ich füge neue Elemente in die Liste ein und gebe verschiedene Namen und Kontostände ein, aber bei der Ausgabe enhalten dann alle Knoten die gleichen Daten. Kann mir einer sagen wo der Logikfehler in meinem Code ist?

Die 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{
       Konto *konto;
       struct node *prev;
       struct node *next;
}

Das Hauptprogramm:

int main(int argc, char *argv[])
{
    int i = 0;
    struct node* head = newlist();       /* Pointer auf die doppelt 
                                            verlinkte Liste */
    struct node* current = head;         /* Das aktuelle Element der Liste */
    Konto* kontoptr = &konten[i];        /* Pointer auf aktuelles Konto */
    ....
}

Die Unterprogramme:

/* Eine neue doppelt verlinkte Liste erzeugen */
struct node* newlist()
{
       /* Platz für Knoten reservieren und verlinken */
       struct node* new = (struct node*)malloc(sizeof(struct node));
       new->konto = NULL;
       new->prev = new;
       new->next = new;
       return new;
}

/* Elemente in die doppelt verlinkte Liste einfügen */
struct node* insert(struct node* head, struct node* current, Konto* kontoptr){

    /* current auf Listenanfang setzen */
    current = head;

    /* Knoten erzeugen und ihm ein Konto zuweisen */   
	struct node* new = (struct node*)malloc(sizeof(struct node));
	new->konto = kontoptr;

	/* So einfügen, wenn die Liste nur ein Element hat */
	if(current->next == current)
	{
          new->prev        = current;
	      new->next        = current;
	      current->next    = new;
	      current->prev    = new;
	      char puffer[100];
          printf("Name des Kontoinhabers: ");     scanf("%99s", &puffer);
          kontoptr->name = (char*)malloc(strlen(puffer)+1);
          strcpy(kontoptr->name, puffer);
          int kontostand;
          printf("G/D Betrag: ");        scanf("%i", &kontostand); 
          kontoptr->kontoStnd = kontostand;
    }
    else
    {
          /* current auf zweites Element setzen, da erstes Element = NULL */ 
          current = head->next;

          /* suche Einzeigerstelle */
             while((strcmp(current->konto->name, new->konto->name) < 0) && 
             (head != (current->next)))
             {  
                       current = current->next;
             }

             new->prev              = current->prev;
             new->next              = current;
             (current->prev)->next  = new;
             current->prev          = new;
             char puffer[100];
             printf("Name des Kontoinhabers: ");     scanf("%99s", &puffer);
             kontoptr->name = (char*)malloc(strlen(puffer)+1);
             strcpy(kontoptr->name, puffer);
             int kontostand;
             printf("G/D Betrag: ");        scanf("%i", &kontostand); 
             kontoptr->kontoStnd = kontostand;
             system("pause");
    }
}  

/* Elemente aus der doppelt verlinkten Liste ausgeben */
void ausgeben(struct node* head, struct node* current){
     current = head->next;

     while(head != (current->next))
     {
             printf("\n\tName: %s \tKontostand: %.2f \n", current->konto->name,
             current->konto->kontoStnd);
             current = current->next;
             system("pause");
     }
}

Vielen Dank schonmal in Voraus!

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?

mr_unknown

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?

mr_unknown

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? (Also kontoptr = ...; )
Siehe auch zweite Frage in meinem ersten Post.

mr_unknown

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 .

mr_unknown

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.

mr_unknown

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.

Wutz

Verkettete Listen sind Akademikerneurosen und u.v.a. nicht für Resortierung geeignet.

mr_unknown

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!

mr_unknown

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.

Wutz

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.

mr_unknown

@ 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.