verkettete Listen



  • Hallo,

    ich benötige Hilfe bei der Arbeit mit verketteten Listen.
    Mit folgenen Code definiere ich die Struktur der Elemente :

    struct item {
      struct item * next;
      int daten;
    };
    
    struct list {
    struct item * start;
    struct item * end;
    };
    

    Nun meine Frage dazu: Wenn ich eine Liste und ein Element erstelle, wie kann ich sie dann verbinden?

    list myList;
    item person1;
    

    Würde ich für ein zweites element einfach

    item person2;
    

    nutzen können?

    Mit welchem Befehl weise ich z.B. dem Zeiger von Person1 das neue Element zu?
    Worauf zeigt das eigentlich (welche Datenstruktur)??

    Vielen Dank im Voraus...



  • struct item {
      struct item * next;
      int daten;
    };
    
    struct list {
    struct item * start;
    struct item * end;
    };
    
    void f(void)
    {
      //1 Element
      list myList;
      item person1;
      myList.start = &person1; //erstes elem. ist person1
      myList.end   = &person1; //letztes elem. ist person1
      person1.next = NULL; //kein nachfolger für person1
      // und noch 1 dazu
      item person2;
      myList.end   = &person2; //letztes elem. ist nun person2
      person1.next = &person2; //person1 hat ein nachfolger
      person2.next = NULL; //kein nachfolger für person2
    }
    

    ich empfehle:

    list myList;
    item *personen[1000];
    int index = 0;
    
    void add(int daten)
    {
      personen[index] = new item;
      myList.start = personen[0];
      myList.end = personen[index];
      if (index > 0) personen[index-1]->next = personen[index];
      personen[index]->next = NULL;
      personen[index]->daten = daten;
    }
    
    item get(int nr)
    {
      item* tmp = myList.start;
      for (int i=0;i<nr;i++)
      {
        tmp = tmp->next;
      }
      return *tmp;
    }
    
    //usw...
    //ich will dir hier nicht den ganzen source posten
    //ps: ungetestet!
    


  • Cool, danke für die schnelle Antwort, probier's gleich mal aus. 🙂



  • übrigens: danke für die anregung! ich schreibe gerade meine eigene bibliothek, da passt eine verkettete liste bestens hinenin 🤡



  • Achso, hab noch ne Frage:

    bei einer deklaration von

    typedef struct element* elementzgr;
    
    struct element
    {
    	elementzgr nachfolger;
             .
             .
             .
    };
    
    elementzgr q;
    

    Wofür steht dann foglende Befehlszeile?

    q->nachfolger = 0;
    

    Was heisst denn dieser Pfeil?

    Wird hier für alle Variablen, die vom Typ Element erzeugt werden, der Nachfolger auf NULL gesetzt?



  • Gast_von_heute schrieb:

    Wofür steht dann foglende Befehlszeile?

    q->nachfolger = 0;
    

    der pointer auf den nachfolger von q wird auf "0" gesetzt, sprich er weist ins nirvana

    Gast_von_heute schrieb:

    Was heisst denn dieser Pfeil?

    elementzugriff

    Gast_von_heute schrieb:

    Wird hier für alle Variablen, die vom Typ Element erzeugt werden, der Nachfolger auf NULL gesetzt?

    dadrauf würde ich mich nie verlassen. machs lieber selber.



  • ->
    bedueutet elementzugriff, funktionszugriff, von einem Pointer (Zeiger)



  • FranzL. schrieb:

    ->
    bedueutet elementzugriff, funktionszugriff, von einem Pointer (Zeiger)

    sagte ich doch bereits...
    aber egal. na ja, ich habe jetzt selbst eine klasse geschrieben, die das ganze hier gesagte und nochn bissel mehr zusammenfasst. wenn jemand interessiert ist, kann ich den source gerne posten.



  • Klar, wenn das genau dazu passt, würde ich das gern mal sehn.

    Wusste nur nicht, auf welches Element sich dieser '->' bezieht, da ja keins definiert wurde..nur eine Struktur angelegt.

    würde ich zwei elemente person1 & person2 anlegen, auf welches element würde denn q->nachfolger dann zeigen?

    wenn ich vorher 'q' Speicher zuweise klappt das, z.B.

    q = &person1;
    
    q->nachfolger = 0;   // zählt das nun für person1 ?
    


  • Gast_von_heute schrieb:

    würde ich zwei elemente person1 & person2 anlegen, auf welches element würde denn q->nachfolger dann zeigen?

    darauf, was q->nachfolger zugewiesen wurde.

    Gast_von_heute schrieb:

    wenn ich vorher 'q' Speicher zuweise klappt das, z.B.

    q = &person1;
    
    q->nachfolger = 0;   // zählt das nun für person1 ?
    

    ja.



  • OK, Danke



  • Also habe mit Hilfe dieses Codes ein Modul zum Einfügen von Items gecodet und auch eins zum Auslesen. Diese funktionieren beide wunderbar, allerdings scheitere ich noch am richtigen Löschen. Es wäre super, wenn jmd kurz ein Löschmodul hier anreißen könnte 🙂



  • wenn du bereits einen zeiger hast, nennen wir ihn mal a, welches das element vor dem zu löschenden element ist:

    element *hz = a->next->next;
    delete a->next;
    a->next = hz;
    

    mehr nicht, zumindest für das fachgerechte "entsorgen" der daten. den zeigern start und ende musst du dann schon selbst was zuweisen. und natürlich auf NULL prüfen, das ist dann alles deine angelegenheit. aber ich sollte ja die funktion nur mal anreißen 🙂

    [edit]Korrekturen[/edit]


Log in to reply