Liste => erste Versuche



  • Hallo Jungs,

    wie schon angekündigt /angedroht ( 🙂 ) fang ich jetzt mal mit dem Listen-Thema an.
    Hab mich jetzt nicht sooo viel eingelesen , eigentlich gar nicht, hab´s versucht mir wie bei der Rekursion selbst herzuleiten.

    Problem ist jetzt das ich mir in V1 mit dem free nicht wirklich sicher ist ob das so passt.
    Generell: Man sollte wohl die "Funktionen" zum erstellen , anzeigen usw. usw. nicht in eine Funktion packen, aber das sind wirklich nur mal "Gehversuche", das kommt dann noch. Ein typedef wäre wohl für die Struct auch angebracht..

    Programm stürzt nicht ab bei mir, hab die Liste mal Testweise auf 200 Elemente erweitert... Aber ob es wirklich richtig ist...=>Letztes mal war's auch falsch und ist nicht abgestürzt ... Wie schon geschrieben, vor allem das Free...(Kann sein das der Kommentar total falsch ist...)
    Naja, mal sehen.

    V1.c

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define nl puts("\n")
    
    struct mix{
               int v1;
               char c1;
               struct mix *next;
               };
    
    void v1 (void){
    struct mix List, *ptr=&List, *del=NULL;
    int anlegen=4, run, v=2, lctr=1;
    char c=65; 
    
    List.next=NULL;
    
    for(run=0; run<anlegen; run++){
    
               ptr->next==NULL ? puts("List-End Found!!") : puts(" List Element added!!");
               ptr->v1=v;
               ptr->c1=c;
               v+=2;
               c++;
               ptr->next=malloc(sizeof(List));
               ptr=ptr->next;
         }
    ptr->next=NULL;   
    
    ptr=&List;
    
    while (ptr->next !=NULL){
    
               printf("Liste [%d] ::::\t%d\t%c\n", lctr++, ptr->v1, ptr->c1);
               ptr=ptr->next;
               ptr->next == NULL ? puts("End Found") : puts("=>next");
          }
    
    //Free...........
    ptr=&List;
    while(ptr->next !=NULL){
            del=ptr->next;       // next ist nicht Null, also zeifer auf nächstes Element wegspeichern
            free(ptr->next);   // nächstes Element (Free)        
            ptr->next=del;      // Zeiger auf nächstes Element zurückspeichern, Liste quasi wieder verketten??
            ptr=ptr->next;
         }       // Zeiger auf nächstes Element "erhöhen" 
    
    }//END
    

    ???Ist der Speicher nun wieder freigegeben ? Free gibt ja nix zurück. Das Freigeben dem Löschen gleichkommt sehe ich richtig oder? Also wenn ich später ne Funktion zum "Löschen" schreibe reicht ja auch free(element); ?


  • Mod

    Die Freigabe ist absolut nicht richtig! Du gibst erst ptr->next frei (Zeile 45), dann benutzt du fröhlich das freigegebene Element (Zeile 47 und dann Zeile 45 beim nächsten Durchlauf).

    Üblicherweise wird man sich erst das nächste Element holen und sich dabei das aktuelle Element merken. Dann gibt man das aktuelle Element frei. Bei dir funktioniert dies aber nicht, weil bei dir der erste Knoten auf dem Stack liegt. Das ist in zweierlei Hinsicht ein Problem. Erstens, wegen des genannten Problems bei der Freigabe. Zweitens kann deine Liste gar nicht leer sein, was ein doofes Design ist!



  • beginner88888 schrieb:

    Generell: Man sollte wohl die "Funktionen" zum erstellen , anzeigen usw. usw. nicht in eine Funktion packen, aber das sind wirklich nur mal "Gehversuche",

    Meinst du das wirklich so?

    Bei deiner Ausgabe wird das letzte Element nicht ausgegeben
    Deiner Freigabe ist völlig konfus.

    del=ptr->next;       
      free(ptr->next); //das ist wie free(del)
    

    del ist somit ungültig.

    Beim Anlegen:
    - besorge dir Speicher mit malloc , überprüfe den Erfolg.
    - befülle den Speicher mit Werten (auch next (NULL))
    - binde das Element in die Liste ein.

    Bei der Ausgabe:

    ptr=&List;
    while (ptr !=NULL){ // scheun ob das aktuell Element NULL ist
               printf("Liste [%d] ::::\t%d\t%c\n", lctr++, ptr->v1, ptr->c1);
               ptr=ptr->next;
               ptr == NULL ? puts("End Found") : puts("=>next");
          }
    

    Beim Löschen ähnlich, nur musst du dir ptr->next vor der Freigabe von ptr merken.



  • Weiß nicht ob ich heut noch ne überarbeitung schaffe....

    Beim Anlegen:
    - besorge dir Speicher mit malloc, überprüfe den Erfolg.
    - befülle den Speicher mit Werten (auch next (NULL))
    - binde das Element in die Liste ein.

    Speicher -hab ich
    befüllen - ok das letzte nicht
    binde das Element in die Liste ein... => Das passt aber oder? Also es ist ne verkettete Liste geworden. Einiges Falsch, aber Speicher besorgen, füllen und verketten passt doch vom "Grundablauf" ??

    Generell: Man sollte wohl die "Funktionen" zum erstellen , anzeigen usw. usw. nicht in eine Funktion packen, aber das sind wirklich nur mal "Gehversuche",
    Meinst du das wirklich so?

    😕 😮 Ähmm..nö. Aber ich glaube du weißt wie ich´s meinte.


  • Mod

    beginner_offl schrieb:

    Speicher -hab ich
    befüllen - ok das letzte nicht
    binde das Element in die Liste ein... => Das passt aber oder? Also es ist ne verkettete Liste geworden. Einiges Falsch, aber Speicher besorgen, füllen und verketten passt doch vom "Grundablauf" ??

    Nein, es passt nicht vom Design her. Ein bisschen falsch ist immer noch falsch. Du nimmst dir derzeit ein leeres Element, füllst dies mit Inhalt, legst danach ein leeres Element an. Das ist falsch herum gedacht. Der zugrunde liegende Designfehler ist wieder der, den ich schon in der ersten Antwort erwähnt hatte.

    Trenn in deiner Programmlogik mal das Konzept des "Knotens" von dem Konzept der "Liste". Derzeit ist bei dir alles das selbe. Sollte es aber nicht sein. Eine Liste besteht aus Knoten (bzw. sie besitzt mehrere Knoten), sie ist kein Knoten.



  • Ich glaub ich weiß jetzt was du meinst.
    Angesichts dessen ist der Code von V1 aber totaler Schrott. Also er macht schon das was ich wollte(abgesehen vom free), aber das ist keine "Liste".

    Werde das komplett neu machen. Aber kaum noch heute.
    Danke derweilen



  • Bei der Version hab ich jetzt nochmehr Bauchschmerzen...

    Ist ne "Schnell"-überarbeitung, glaub es ist aber eher schlechter geworden.

    #include "sys.h"
    
    void erstellen(void){
    
    Liste *first, *ptr, *tmp, *anfang, *show, *del;
    int run, erstellen=0, value=1;
    char letter=65;
    
    puts("How Many Elements to create?:");
    scanf("%d", &erstellen);
    erstellen--;
    first=malloc(sizeof(Liste));  // für "ersten" Eintrag Speicher holen
    ptr=anfang=show=first;
    ptr->v1=value++;           //füllen
    ptr->c1=letter++;
    
    for (run=0; run<erstellen; run++){
            tmp=malloc(sizeof(Liste));       // Speicher anfordern für "neu" Eintrag
              if (!tmp){
                   puts("No Memory mallocated");
                   exit(1);
                }
            tmp->v1=value++;     //füllen
            tmp->c1=letter++;
            tmp->next=NULL;     //der folgende zeiger ist ENDE
            ptr->next=tmp;      // "neu" nach ptr einfügen...
            ptr=tmp;           //nächster durchlauf  "neu_neu" nach "neu_alt" einfügen?
    
         }
    
    int lctr=1;     
    while (show !=NULL){
              printf("Liste %4d=>\t:%4d:\t:%c:\n", lctr++, show->v1, show->c1);
              show=show->next;
          }
    
    del=anfang;    
    while ( del !=NULL){
          tmp=del->next;  // nächsten Zeiger sichern...
          free(del);      //aktuellen "Block" freigeben
          del=tmp;  //??? Falsch wie in 1. Version??? Aber irgendwie muss ich wieder "zusammenknüpfen"... wenn ich vom Eintrag VOR del was wüsste evtl?
          } 
    
    }//END
    

    =>Gut, das mit dem ersten Knoten ist immer noch ein Problem, sehe das mit dem Design schon ein, aber gehen muss es ja auch irgendwie...
    Glaub das wird mir heute zuviel



  • Sieht soweit richtig aus.
    Ja, auch das freigeben.
    Das erste Element braucht immer eine Sonderbehandlung, da ja der Zeiger für die Liste auch darauf Zeigen muss.

    Nimm bitte sinnvollere Variablennamen.

    statt first oder anfang nimm einfach list
    Wenn du schon schreibst // "neu" nach ptr einfügen..., dann nenn doch deine Variable auch neu.
    Alle Elemente in einer Schleife, auch das erste geht ungefähr so:

    list = NULL; // Liste ist leer
    ptr = list; // auf Anfang der Liste zeigen
    for (run=0; run<erstellen; run++){
            neu=malloc(sizeof(Liste));     
              if (!neu){
                   puts("No Memory mallocated");
                   exit(1);
                }
            neu->v1=value++;     
            neu->c1=letter++;
            neu->next=NULL;     
            if (ptr!= NULL) {   // gibt es schon ein Element
              ptr->next=neu;      // Ja, "neu" nach ptr einfügen...
            } else {
              list = neu;       // Nein, dann ist es der erste Eintrag
            }
            ptr=neu;           
    
         }
    

    Jetzt aber alles mal in getrennte Funktionen.



  • Sieht soweit richtig aus.
    Ja, auch das freigeben.

    You make my day :-))

    Jetzt aber alles mal in getrennte Funktionen.

    Ja, das werd ich machen. Dazu aber vorab :

    Ich muss einer Funktion zum "erstellen" , immer einen Zeiger auf das vorgehende Element übergeben, um es dahinter einfügen zu können ?? Oder ist es besser einfach einen Zeiger auf "Listenanfang" zu übergeben und solange die Liste zu durchsuchen bis ich "NULL" gefunden habe, und dann einfügen?
    Generell... wäre es sinnvoll , wenn die Funktion nen Zeiger auf das eingefügte Element zurückgibt?

    Bezüglich des Free nochmal. In einem anderen Thread wurde das schonmal angeschnitten, unter Linux deckt Valgrind wohl Speicherlecks usw. auf.
    Ich benutze haupsächlich Win7 mit DevC++ (geht auf Arbeit nicht anders).... Gibt's da irgendeine möglichkeit da was zu prüfen? =>v1 gab keine Speicher frei, stürzte aber auch nicht ab. Ich war mir hald ziemlich sicher das es NICHT passt, aber eine Prüfung wäre nicht schlecht....

    =>Das verkettete Listen in der Praxis nicht wirklich oft vorkommen wurde schon besprochen... Weiterhin wäre aber noch interssant.. Baumstrukturen usw usw... Nice to know oder essential element??

    ...mir viel das bei dynamsichen Speicherreservierungen schon auf, das ich das für meine "pillepalle" Prog´s wohl nie wirklich sinnvoll nutzen werde, höchstens um in Übung zu bleiben, da ich fast immer weiß wieviel Speiche ich brauche, oder den Puffer groß genug mache. Aber da geht´s ja auch um nix 🙂



  • Elemente werden nicht nur am Ende angehängt sondern auch mal in der Mitte eingefügt.
    Auch kann das neue Element am Anfang der Liste stehen.

    Daher braucht die Funktion zum einfügen beide Informationen. Den Listenanfang und das Element hinter dem eingefügt werden soll.
    Dabei musst du dann darauf achten, dass du den Listenanfang neu setzt, bzw. dass neu->next dann nicht mehr NULL ist.

    beginner_of schrieb:

    Generell... wäre es sinnvoll , wenn die Funktion nen Zeiger auf das eingefügte Element zurückgibt?

    Warum? Die Funktion besorgt ja nicht den Speicher für das neue Element. Die hängt das nur in die Liste ein. Speicher besorgen und mit Werten besetzen macht eine andere Funktion.

    Die Funktion kann den neuen Zeiger auf den Listenanfang zurück geben (dann sparst du dir Doppelzeiger).

    Dein Programm v1 lief zu kurz und hat zu wenig Speicher verbraucht. Durch Speicherlecks verlierst du Speicher. Das System hat irgendwann keinen freien Speicher mehr und/oder muss auslagern.
    Moderne Systeme geben den Speicher beim Beenden eines Programms auch wieder frei.



  • Daher braucht die Funktion zum einfügen beide Informationen. Den Listenanfang und das Element hinter dem eingefügt werden soll.

    ...Sehe ich richtig, das dies dann beim ersten Eintrag, bzw. beim neu erstellen der Liste beides der gleiche Zeiger ist..??
    Aufbau, bzw. sinngemäß so :

    erstellen(element* anfang, element*hier_einfügen)
    

    ???

    Die Funktion kann den neuen Zeiger auf den Listenanfang zurück geben (dann sparst du dir Doppelzeiger).

    ähm... kann=> Ich sag jetzt mal ich hatte nicht vor den Listenanfang zu ändern oder verstehe ich das jetzt falsch?



  • Was machst du, wenn du eine leere Liste hast? Dann zeigt liste auf NULL.
    Was ist, wenn du ein neues Element vor dem Ersten eintragen willst?

    Dann musst du den Zeiger auf den ersten Eintrag ändern.

    beginnger_offl schrieb:

    erstellen(element* anfang, element*hier_einfügen)
    

    Da fehlt was. Zudem solltest du doch erstellen und einfuegen trennen.

    struct liste *erstellen(char c, int v);
    // besorgt Speicher und kopiert die Daten da rein
    
    struct liste *einfuegen(struct liste *list, struct liste *prev, struct liste *neu);
    //list = Zeiger auf den Anfang
    //prev = Zeiger auf das Element hinter das eingefügt werden soll
    //neu  = Zeiger auf das Element, das eingefügt werden soll (bekommst du von erstellen)
    // Zurück geht der Zeiger auf die Liste
    


  • bin noch nicht weiter, hab etwas Stress, werde wohl erst am Montag weitermachen.
    Danke für die "Prototypen", das hat /wird mir schonmal helfen.

    zu:

    // Zurück geht der Zeiger auf die Liste

    ... die eingefügt wurde, oder?



  • beginner_OF schrieb:

    ... die eingefügt wurde, oder?

    Du fügst nur ein Element/Knoten in die Liste ein.
    i.A. wird das der Wert vom ersten Paramter sein. Aber wenn du etws vor dem ersten Knoten einhängst, dann ändert sich der Anfang der Liste.

    Das ist so ähnlich wie bei realloc.

    Mal dir das mal auf ein Platt Papier auf. Da kannst du die Zeiger durch Pfeile zwischen den Knoten darstellen.
    Dann kannst du das einfügen und anhängen durchspielen.



  • WAAAHHHH!!!!
    Leute ich kriegs nicht gebacken mit der ****Liste.
    Ich hab momentan nicht so den Kopf dafür, aber ich komm echt nicht drauf.

    Also erstellen müsste noch passen :

    #include <stdio.h>
    #include <stdlib.h>
    #include "sys.h"
    
    Liste *erstellen(char c, int v){
    
    Liste *tmp;
    
    tmp=malloc(sizeof(Liste)); 
    
    if(!tmp){
          puts("Error Mallocation");
          exit(1);
          getchar();
       }
    
    tmp->ival=v;
    tmp->cval=c;
    tmp->next=NULL;
    
    return tmp;
    
    }//END
    

    Dann hab ich die Funktion "einfügen"
    ... ich glaube festgestellt zu haben (die debugs und Kommentare vernebeln mich mittlerweile...) das das Return falsch ist??

    #include <stdio.h>
    #include <stdlib.h>
    #include "sys.h"
    #define debug
    
    Liste *einf_1(Liste *list,  Liste *neu){
    /* einf_1 fügt ein Element in die Liste "hinten" ein. return Zeiger auf Anfang, *list = Anfang*/
    
    Liste *einf, *tmp=NULL, *start ;
    
    start=list;
    
    if (list == NULL){
             #ifdef debug
             puts("List Empty");    // Liste ist leer  
             #endif       
             list = neu;          // das neue Element ist das 1. Element              
             return list;      // einf_1 verändert den Anfang aber nicht....
        }
    
     //Ende suchen 
    
       einf=list;      
    
      while (einf != NULL){       // ist "nächstes" Element NULL?       <========|
            tmp=einf->next ;      //tmp zeigt auf das element nach einf          |
            #ifdef debug          //                                             |
            puts("here");          //                                            |
            #endif                //                                             |
            einf=tmp;            // jetzt zeigt einf auf das nächstes element    |
            }  
     // ENDE gefunden    einf zeigt auf Null
    
          einf=neu;      // neues "Element" hinten anhängen 
          #ifdef debug
          printf("%c  %d  \n" , einf->cval, einf->ival);
          #endif
          return list;
    
    }//END
    

    das ganze wird so aufgerufen :
    start.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "sys.h"
    #define debug 
    
    void start (void){
    
    Liste *daten=NULL, *tmp=NULL, *anfang=NULL;  // daten ist meine Liste ::  tmp mein Puffer :: anfang wird bei einf_1 noch nicht benötigt  
    char c='A';
    int  v=1, create=0, dummy, i=0;
    
    puts("Welcome to the First Version of Linked List's!!!\n");
    
    do{
        printf("How many Elements to Create?"); 
        dummy=scanf("%d", &create); 
        keyb;   
    }while(dummy!=1);
    
    printf("\nOK, Let's make a List with %d - Elements\n", create);
    
    //debug
    Liste *s1, *t1;
    while (i++ <create){ 
    
             tmp=erstellen(c, v);
             c++; v++;                 
             daten=einf_1(daten, tmp);
             #ifdef debug
              s1=daten; 
              printf("daten c : %c    daten i: %d  \n", s1->cval, s1->ival);
              t1=s1->next;
              s1=t1;          
             #endif  
    
         }
    
    }//END
    

    Tja, was geht noch ab:
    ...In der sys.h ist folgendes

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #define nl puts("\n")
    #define keyb  while(getchar() != '\n'); 
    
    struct mix{
                char cval;
                int ival;
                struct mix *next;
                };
    
    typedef struct mix Liste; 
    
    void start (void);
    
    Liste *erstellen(char c, int v);    
    
    Liste *einf_1(Liste *list,  Liste *neu);        
    
    void show(Liste *ptr);
    

    und die Main ruft einfach nur start() auf;

    Ich glaub ich hab ein riesen Brett vorm Kopf, ich hab's mir schon x - mal aufgezeichnet aber komm nicht drauf....

    Ich hatte die Funktion show schon eingebunde, funktioniert nicht, da die Liste nicht verkettet wird....



  • Wo meinst du denn, dass du die Liste verkettest?

    Überleg dir mal, welcher Knoten auf welchen zeigt.
    Und ob ein Zeiger auf NULL, auf einen gültigen Knoten zeigt.

    Und du kannst mehrere Zeiger auf dasselbe Objekt haben.
    Wenn du einen davon änderst, ändern sich die anderen aber nicht.

    Zeigerwerte (Adressen) kannst du dir mit %p bei printf anzeigen lassen



  • Wo meinst du denn, dass du die Liste verkettest?

    Naja, wohl nirgends, sonst würde es annähernd funktionieren.
    Also auf in die nächste Runde.
    Danke erstma



  • Schau mal bei einf_1 in Zeile 32: // ENDE gefunden einf zeigt auf Null

    Da bist du schon zu weit. Das einf an der Stelle hat keine Verbindung mit dem letzten Knoten.

    Wenn einf->next == NULL bist du mit der Schleife fertig.
    Dann kannst du einf->next=neu; machen.



  • 😡 😡 Ich bräuchte jetzt einen Smiliy der mit dem Kopf auf den Tisch haut. Mehrmals... bis es richtig weh tut.

    Ok: Jetzt siehts besser aus:
    einf_1.c ( Ich will erst mal nur hinten einfügten, für die advanced Version hab ich dann noch ne Frage...)

    #include <stdio.h>
    #include <stdlib.h>
    #include "sys.h"
    //#define debug
    
    Liste *einf_1(Liste *list,  Liste *neu){
    /* einf_1 fügt ein Element in die Liste "hinten" ein. return Zeiger auf Anfang, *list = Anfang*/
    
    Liste *einf, *tmp=NULL  ;
    
    if (list == NULL){
             #ifdef debug
             puts("List Empty");    // Liste ist leer  
             #endif       
             list = neu;          // das neue Element ist das 1. Element              
             return list;      // einf_1 verändert den Anfang aber nicht....
        }
    
     //Ende suchen 
    
       einf=list;      
    
      while (einf->next != NULL){      //Ist das nächste Element "leer"? einf quasi "Such" - Zeiger
            tmp=einf->next ;           // Nein? Zeiger auf nächstes Element speichern
            #ifdef debug                                                        
            puts("here");          
            #endif               
            einf=tmp;                 // und in meinen "Such"-Zeiger laden
            }  
     // ENDE gefunden    einf->next  zeigt auf Null
    
          einf->next=neu;      // neues "Element" hinten anhängen 
          #ifdef debug
          printf("%c  %d  \n" , einf->cval, einf->ival);
          #endif
          return list;
    
    }//END
    

    Anzeigen lass ich mit

    show.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "sys.h"
    
    void show(Liste *ptr){
    
         Liste *tmp, *show;
    
         show=ptr;
    
         while( show != NULL){
                   printf("Char Value :: %3c      Int Value :: %3d\n", show->cval, show->ival);
                   tmp=show->next;
                   show=tmp;
              }
    
    }//END
    

    An den anderen Files hab ich nicht´s geändert. Also es funktioniert jetzt . Ich denke das das "hinten" anfügen jetzt stimmt??



  • Also wenn die Version so passt, bezw. nicht's mehr "grob fahrlässig" ist... ???

    Nur eine Frage...

    while (i++ <create){
    
             tmp=erstellen(c, v);
             c++; v++;                
             daten=einf_1(daten, tmp);
    

    Meine Funktion Einf_1 ändert ja den anfang der Liste "daten" nicht... würde dann nicht :

    tmp=erstellen(c++, v++)
    einf_1(daten, tmp)
    

    ..reichen? Muss ich unbedingt wenn ich einen Wert zurückgebe, diesen auch benutzen in diesem Fall? Nicht oder?

    Frage zu Advanced: (Prototyp ist jetzt nicht gaaanz auf meinem Mist gewachsen 😉 )

    List *einf_adv(List *list, List *insert, List *neu);
    //*list= Zeiger auf Anfang, 
    //*insert = "dahinter" wird eingefügt
    //*neu = mein neues Element
    //und Zurück geht wieder Zeiger auf die Liste, bzw. den Anfang
    

    ==> *insert was muss ich beachten? Also sagen wir mal ich will nach C :: 3 einfügen ( Meine Elements sind ja ein Char und ein int), also schreib ich mir erstmal eine Suchfunktion, um das Element mit diesem Inhalt zu finden.
    Dannk kann ich den Zeiger auf das "gefundene" Element en meine Funktion einf_adv übergeben.
    Die Vorgehensweise passt so, oder würdet Ihr das anders machen??


Log in to reply