4. Lineare Listen

Lineare Listen

  • B

    Guten Tag,
    wir nehmen in der Schule gerade das Thema Lineare Listen durch und es versteht einfach keiner aus meiner Klasse ( bis auf zwei).

    deswegen wollte ich mal fragen, wie genau das funktioniert, also ob mir das jemand mal an hand eines Beispiels deutlich machen kann.

    Also bsw. das mit den Pointern *next und *top.
    ^^

    Beiträge wie, bevor du dich damit auseinandersetzt, solltest du erstmal ...
    möchte ich nicht lesen, ich habe mich hier angemeldet, damit mir geholfen werden kann, und nicht um mir dumme sprüche anhören zu müssen.

    Ich hoffe es is alles klar? ^^

    danke im Voraus 😃

    0
  • S

    Mit Sätzen wie

    Beiträge wie, bevor du dich damit auseinandersetzt, solltest du erstmal ...
    möchte ich nicht lesen, ich habe mich hier angemeldet, damit mir geholfen werden kann, und nicht um mir dumme sprüche anhören zu müssen.

    gibst du Stof um dir eben solche Antworten zu geben und machst du dir unnötig unbeliebt. Wir sind kein Supportservice und keiner ist verpflichtet dir zu helfen geschweige dann eine passende Antwort zu geben. Es kommt nur auf deine Art und Weise, wie du dich hier aufführst. Ich mach diesmal eine Ausnahme, weil es dein erster Post ist.

    Du hast eine Basis Struktur, z.b.

    struct intlist
{
  int datum;
  struct intlist *next;
  struct intlist *prev;
};

    Im datum legst du den Wert ab, was du speichern willst. Muss nicht zwingend int sein.

    [0]         [1]           [2]            ... [N-1]

          /-------\      /-------\      /-------\           /-------\
NULL <----| P     | <----| P     | <----| P     | <---- ... | P     |  
          |   D   |      |   D   |      |   D   |           |   D   |  
          |     N |----> |     N |----> |     N |---->  ... |     N |----> NULL
          \-------/      \-------/      \-------/           \-------/

    Das Bild verdeutlich, was das ganze soll. P steht für prev , D für datum und N für next Die Zahlen in den Eckigen Klammern referenzieren, welches Element in der Liste gemeint ist.

    Dann musst du Funktionen schreiben, die auf die Liste Operieren: Daten einfügn, löschen, editieren und und und. Hier schreib nur die Einfüge-Funktion als Bsp:

    /**
 * \param list Eine liste (NULL für leere Liste)
 * \param datum das zu speichernde Datum
 * \returns die (ggf neu erzeugte) Liste bei Erfolg, NULL sonst
**/
struct intlist *intlist_add(struct intlist *list, int datum)
{
  struct intlist *backup = list;
  if(list == NULL)
  {
     /* leere Liste --> Liste Erzeugen */
     list = malloc(sizeof(*list));
     if(list == NULL) return NULL;
     list->datum = datum;
     list->next = list->prev = NULL; /* siehe Grafik oben */
     return list;
  }

  while(list->next)
    list = list->next; /* list zeigt auf das nächste Element */

  list->next = malloc(sizeof(*list));
  if(list->next == NULL)
    return NULL;

  list->next->datum = datum;
  list->next->next = NULL; /* siehe Grafik oben */
  list->next->prev = list; /* dito */

  return backup;   /* edit: hab den Fehler übersehen */
}

    Der erste Block if(list == NULL) sollte eigentlich klar sein, oder?

    Zeile 18 und 19 sind interessant: list->next zeigt auf das nächste Element der Liste. Die while-Schleife ist aktiv, wenn der next Pointer nicht NULL ist. Nur der next Pointer des letzten Listenelements zeigt auf NULL. Auf Deutsch sagt die while Schleife: solange ich nicht am Ende der Liste angekommen bin ...

    Zeile 19 macht list = list->next; , d.h. list zeigt jetzt auf das nächste Element. Wenn die while-Bedingung nicht mehr erfüllt ist, dan zeigt list auf das letzte Element.

    Zeile 25-27 sollten auch klar sein, oder?

    Damit kannst du sowas machen:

    int main(int argc, char **argv)
{
    struct intlist *list, *tmp;
    int i;
    if(argc < 2)
    {
        fprintf(stderr, "usage: %s 1.zahl 2.zahl 3.zahl ...\n", argv[0]);
        return 1;
    }

    list = NULL; /* leere Liste */
    for(i = 1; i < argc; ++i)
    {
        tmp = intlist_add(list, atoi(argv[i]));
        if(tmp == NULL)
            printf("Warnung: Zahl %s kann nicht hinzugefügt werden.\n", argv[i]);
        else list = tmp;
    }

    intlist_print(list);

    intlist_free(list);

    return 0;
}

    So, deine Hausaufgabe wird jetzt sein:
    - schreibe die Funktion void intlist_print(struct intlist *list); , die die gespeicherten Werten der Liste auflistet.
    - schreib die Funktion void intlist_free(struct intlist *list); , die den durch malloc angeforderten Speicher wieder freigibt.

    0
  • B

    Beiträge wie, bevor du dich damit auseinandersetzt, solltest du erstmal ...
    möchte ich nicht lesen, ich habe mich hier angemeldet, damit mir geholfen werden kann, und nicht um mir dumme sprüche anhören zu müssen.

    dies habe ich nur geschrieben, da ich in meinem ersten Thread den ich erstellt habe, gleich eine dumme antwort bekommen habe, ich habe mich ja nicht umsonst hier angemeldet. Ja klar ist es jedem selbst überlassen ob er mir hilft, aber muss man gleich einen dummen Spruch anhören lassen? Wie, bevor du an etwas schwereres rangehst fang mit dem Grundstoff an und und und. Ich weiß ja nicht wie es dir geht, aber mich kotzt sowas an. Entweder man hilft einem oder man lässt es bleiben. Zumal ein Forum dazu da ist um Diskussionen über den Stoff zuführen und Fragen zustellen. Und ich denke mal das hat nichts mit der Art und Weise zutun, wenn ich eine sachliche Frage stelle ...

    danke aufjedenfall für deine Hilfe, ich habe es jetzt einigermaßen verstanden
    deine sogenannten "Hausaufgaben" hatten wir auch schon in der schule, wenn ich mich recht erinnere nging das mit Malloc so:

    ... =(struct inlist *)malloc(sizeof(struct intlist))

    genau weiß ich es nicht mehr, da ich meine Unterlagen nicht dabei hab und unser Code ein bischen anders aussieht.
    Aufjedenfall ist mir jetzt einiges klarer geworden, besonders deine kleine "Zeichnung" hat geholfen 😉

    0
  • N

    Du gibst in "intlist_add" den Node vor dem neu Erzeugten zurück. Ist das Absicht? Willst du den neu erzeugten Node zurückgeben, dann in intlist_add in Zeile 29

    return list->next;

    EDIT: damit verlierst du in deinem Beispiel auch den List-Head-Pointer sobald mehr als 2 Zahlen eingegeben werden und machst dir das Traversen der Liste unnötig schwer.

    0
  • ?

    BraCay1 schrieb:

    wenn ich mich recht erinnere nging das mit Malloc so:

    ... =(struct inlist *)malloc(sizeof(struct intlist))

    genau weiß ich es nicht mehr, da ich meine Unterlagen nicht dabei hab und unser Code ein bischen anders aussieht.

    Nene, supertux macht das schon richtig.

    http://www.c-plusplus.net/forum/viewtopic.php?t=206606

    0
  • S

    BraCay1 schrieb:

    dies habe ich nur geschrieben, da ich in meinem ersten Thread den ich erstellt habe, gleich eine dumme antwort bekommen habe, ich habe mich ja nicht umsonst hier angemeldet. Ja klar ist es jedem selbst überlassen ob er mir hilft, aber muss man gleich einen dummen Spruch anhören lassen? Wie, bevor du an etwas schwereres rangehst fang mit dem Grundstoff an und und und. Ich weiß ja nicht wie es dir geht, aber mich kotzt sowas an. Entweder man hilft einem oder man lässt es bleiben.

    du hast etwas nicht verstanden, und zwar welche deine Rechte hier sind, wenn ich das so ausdrücken darf 😉 "Auf dumme Fragen gibt es nur dumme Antworten", das ist soz. das Gesetzt in den Foren, hier gibt es keine Demoktratie oder sonst was, du willst was von uns, nicht wir was von dir und *das* ist der entscheidende Unterschied.

    Wenn du eine Frage richtig formulierst, wo man merkt, dass du wirklich Hilfe brauchst (wie z.b. du es oben gemacht hast), dann wird die jemand helfen. Wenn man aber sieht, dass deine Frage nicht gut durchdacht ist oder du sozusagen "lustlos" die Frage stellt, dann wird dich keiner ernst nehmen und die dummen Spüche kommen 100%. Es ist halt so, wir sind nicht da, um dir zu helfen und du hast keinerlei Anspruch hier. Wenn jemand sich keine Mühe gibt eine Frage richtig zu stellen, dann wieso soll ich mir die Mühe geben, dir eine gute Antwort zu geben? Es geht hier ums Prinzip.

    BraCay1 schrieb:

    Zumal ein Forum dazu da ist um Diskussionen über den Stoff zuführen und Fragen zustellen. Und ich denke mal das hat nichts mit der Art und Weise zutun, wenn ich eine sachliche Frage stelle ...

    wozu dieses Forum da ist, hast du nicht zu entscheiden, nicht ich, nicht du, nicht NDEBUG, nicht xyz-beliebig. Das Forum bildet sich aus der Gemeinschaft. Und es hat sich sehr viel damit zu tun, wie man sich hier benimmt, d.h. wie man Frage stellt und welche Einstellung man hat. Wie oft habe ich Leute gesehen, die Posten "hey, isch bin totaler n00b hab gehört dass mit sowas wie C/C++ coden kann, ich will ein rollenspiel coden, was mache ich?" und solche beschweren sich, wenn man ihnen sagt "lern erstaml die Grundlagen der programmierung".

    Lies mal das hier duch: Wie man Fragen richtig stellt. Es ist ein langer Text, aber sehr interessant und erklärt einiges, was ich hier geschrieben habe. Dich trifft es vielleicht nicht ganz, aber lies es trotzdem durch und du wirst vermutlich verstehen, worauf ich hianus will.

    ---

    @NDEBUG: du hast einen Fehler entdeckt. Ich wollte die gesamte Liste zurückgeben (also head), aber durch meine Optimierung (hatte ein tmp um durch die Liste zu laufen) habe ich dann vergessen auch das return zu aktualisieren. Hab oben den Bug gefixt 😉

    0
Anmelden zum Antworten