Verkettete Liste

[IltisvdT]

Hi,

ich brauche erneut eure Hilfe. Geht um folgende Aufgabe

Eine besondere Eigenschaft verketteter Listen ist das einfache Einfügen von Elementen. Dadurch

eignen sie sich besonders gut für sortiertes Einfügen. Man startet hierzu einfach mit

einer leeren Liste und wenn ein Element eingefügt werden soll, so wird es direkt an der richtigen

Stelle eingefügt.

a) Erstellen Sie eine Datei stringList.h in der Sie eine Datenstruktur stringList für ein

Listenelement vom Typ char * deklarieren und Prototypen für folgende Funktionen festlegen:

• struct stringList* neuesElement(char * zeichenkette);

Allokiert Speicher für ein neues Element auf dem „Heap“

Hinweis: Auch der Speicher für die Zeichenkette muss hier allokiert werden.

• void einfuegen_sort(struct stringList **liste, struct stringList *new):

Sortiertes Einfügen des Elements new in die Liste liste.

• void ausgabe(struct stringList **list);

Ausgabe der sortierten Liste.

• int suchen (struct stringList **list, char * zeichenkette);

Suchen eines Elements in der Liste. Der Rückgabewert soll die Position des Elements

sein bzw. -1, wenn kein solches Element existiert.

• void loeschen(struct stringList **liste, char * zeichenkette);

Entfernen eines Elements aus der Liste und Freigeben des Speichers.

Implementieren Sie nun in der Datei stringList.c die gegebenen Funktionen.

Ich habe im Netz folgendes gefunden:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>


struct stringList { 

  char zeichen[80];

  struct stringList *next;

};


struct stringList *liste = NULL;


struct stringList *neuesElement(char *zeichenkette) {   //richtige Form

  struct stringList *Neu;

  Neu = (struct stringList *) malloc(sizeof(struct stringList));

  if (Neu == NULL) {  

    printf("Speicher voll, Abbruch...\n");

    exit (1);

  }

  Neu->next = NULL;

  strcpy(Neu->zeichen,zeichenkette);

  return Neu;

  }


struct stringList *einfuegen_sort(struct stringList *liste, struct stringList *Neu) {

//void sortiert_einfuegen (struct **liste, struct stringList *new)

  struct stringList *Tail;

  if (liste == NULL)

    liste = Neu;

  else {

    Tail = liste;

    while (Tail->next != NULL) 

      Tail = Tail->next;

    Neu->next = Tail->next;

    Tail->next = Neu;

  }

  return liste;

}


void ausgabe(struct stringList *list) { //void ausgabe (struct stringList **list)

  struct stringList *Tail = liste;

  while (Tail != NULL) {

    printf("%s\n", Tail->zeichen);

    Tail = Tail->next;

  }

}



int main (void) { 

  char str[80];

  int z;

  z=5;

  struct stringList *Neu;

  while(1) {

    fgets(str, 30, stdin);

    if (z != 0) {

      Neu = neuesElement(str);

      liste = einfuegen_sort(liste, Neu);

      z--;

    }

    else break;

  }

  printf("\n");

  ausgabe(liste);

  return 0;

}

Das ist ja leider noch nciht ganz das, was ich machen soll. Habe das in das geändert und ergänzt:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>


struct stringList { 

  char zeichen[80];

  struct stringList *next;

};


struct stringList *liste = NULL;


struct stringList *neuesElement(char *zeichenkette) {   //richtige Form

  struct stringList *Neu;

  Neu = (struct stringList *) malloc(sizeof(struct stringList));

  Neu->next = NULL;

  strcpy(Neu->zeichen,zeichenkette);

  return Neu;

  }


struct stringList *einfuegen_sort(struct **liste, struct stringList *Neu) {

//void sortiert_einfuegen (struct **liste, struct stringList *new)

  struct stringList *Tail;

  if (liste == NULL)

    liste = Neu;

  else {

    Tail = liste;

    while (Tail->next != NULL) 

      Tail = Tail->next;

    Neu->next = Tail->next;

    Tail->next = Neu;

  }

  return liste;

}


void ausgabe(struct **list) { //void ausgabe (struct stringList **list)

  struct stringList *Tail = liste;

  while (Tail != NULL) {

    printf("%s\n", Tail->zeichen);

    Tail = Tail->next;

  }

}


int suchen (struct stringList **liste, char * zeichenkette);

    int i=1;

    while(strcmp(Tail->liste,zeichenkette)!=0)

    {    Tail=Tail->next;

        i++;

    }

    if(strcmp(Tail->liste,zeichenkette)==0)

        return(i);

    else

        return(-1);


void loeschen(struct stringList **liste, char * zeichenkette);

int i;

struct stringList tmp;

    if(suchen(struct stringList **liste, char * zeichenkette)!=-1)

    {

        while(suchen(struct stringList **liste, char * zeichenkette)>(i-1))    

        {    Tail=Tail->next;

            i++;

        }

        tmp=Tail->next;

        Tail=Tail->next->next;

        free(tmp);

    }

    else

        (printf("Eintrag ist nicht vorhanden");



int main (void) { 

  char str[80];

  int z;

  z=5;

  struct stringList *Neu;

  while(1) {

    fgets(str, 30, stdin);

    if (z != 0) {

      Neu = neuesElement(str);

      liste = einfuegen_sort(liste, Neu);

      z--;

    }

    else break;

  }

  printf("\n");

  ausgabe(liste);

  return 0;

}

Leider geht nun garnichts mehr. Es ist ja auch noch keine Header-Datei. Aber ich dachte, ich muss es erstmal als Programm zum laufen kriegen, bevor ich daraus ne header-Datei mache. Mich wundert unter anderem, dass er in meiner Version meckert, dass Tail undeclared ist und in der Ursprungsversion nicht.

Vielen Dank schonmal

[Klotzkopp]

Deine Funktionsköpfe stimmen nicht mit denen aus der Aufgabenstellung überein. Und Funktionsrümpfe müssen in geschweiften Klammern stehen. Das solltest du eigentlich wissen.

Ich habe im Netz folgendes gefunden:

Sinn und Zweck dieser Aufgabe ist sicher nicht, dass du irgendwelche Quellcodes aus dem Internet umbaust. Es bringt auch nichts, denn bei deinem Kenntnisstand geht das schief, wie du gemerkt hast. Wenn du nur ziellos herumbastelst, bis der Compiler sich nicht mehr beklagt, lernst du nichts.

Willst du mit jeder weiteren Aufgabe hier ankommen, oder willst du lernen, wie man so etwas selbst löst?

[laubi]

also von mir bekommt du den tipp mal ein buch zu lesen.

Galileo Computing :: C von A bis Z zum beispiel, da du ja den quellcode in c geschrieben hast.

[IltisvdT]

Es ist sicherlich richtig, dass man so weniger lernt. Allerdings ist unsere Vorlesung nicht wirklich hilfreich und die Bücher und Informationem im Internet helfen zwar weiter, reichen aber auch nicht aus um es zum laufen zukriegen. Damit wir aber überhaupt weiterkommen, haben wir uns etwas ähnliches rausgesucht, um nachzuvollziehen (so gut es halt geht), wie die Aufgabe anzugehen ist.

Ich habe es nochmal teilweise neu angefangen und bin soweit

#include <stdio.h> 

#include <stdlib.h> 

#include <string.h> 


struct stringList {  

  struct stringList *next; 

  char zeichen[80]; 

}; 


struct stringList *liste = NULL; 


struct stringList *neuesElement(char *zeichenkette) {   //richtige Form 

  struct stringList *Neu; 

  Neu = (struct stringList *) malloc(sizeof(struct stringList)); 

  Neu->next = NULL; 

  strcpy(Neu->zeichen,zeichenkette); 

  return Neu; 

  } 


void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) { 

//void sortiert_einfuegen (struct stringList **liste, struct stringList *new) 

  struct stringList *Tail; 

  if (liste == NULL) 

    *liste = Neu; 

  else { 

    Tail = *liste; 

    while (Tail->next != NULL)  

      Tail = Tail->next; 

    Neu->next = Tail->next; 

    Tail->next = Neu; 

  } 

} 


void ausgabe(struct stringList **list) { //void ausgabe (struct stringList **list) 

  struct stringList *Tail = liste; 

  while (Tail != NULL) { 

    printf("%s\n", Tail->zeichen); 

    Tail = Tail->next; 

  } 

} 



int main (void) {  

  char str[80]; 

  int z; 

  z=5; 

  struct stringList *Neu; 

  while(1)  

  { 

    fgets(str, 30, stdin); 

    if (z != 0) { 

      Neu = neuesElement(str); 

      z--; 

    } 

    else break; 

  } 

  return(0); 

 }

Das lässt sich kompilieren und macht keine Mucken. Es gehlt jetzt noch die suchen und löschen funktionen. Dazu gleich mehr. Ich kann nun leider in meiner main die zB die sortiert_einfuegen nciht öffnen. In meinem "alten" Programm sah das ja so aus:

liste = sortiert_einfuegen(liste, Neu);

Und das stand im if in der main. wenn ich das mache und kompilieren will sagt er

warning: passing argument 1 of soertiert_einfuegen from incompatible pointer type.

note: expected struct stringlist ** but argument is of type struct stringlist *

error: void valoue not ignored as it ought to be

Sieht denn das ohne den letzten Aufruf halbwegs passabel aus? denn ich denke ich blicke langsam dahinter wie es funktioniert. Nur diese Doppelpointer find ich noch recht schwierig, aber auch da muss es wahrscheinlich erstmal klick machen...

[IltisvdT]

Ich habe es nochmal etwas geändert weil ich gesehen habe, dass da zwei & gefehlt haben.

#include <stdio.h> 

#include <stdlib.h> 

#include <string.h> 


struct stringList {  

  struct stringList *next; 

  char zeichen[80]; 

}; 


struct stringList *liste = NULL; 


struct stringList *neuesElement(char *zeichenkette) {   //richtige Form 

  struct stringList *Neu; 

  Neu = (struct stringList *) malloc(sizeof(struct stringList)); 

  Neu->next = NULL; 

  strcpy(Neu->zeichen,zeichenkette); 

  return Neu; 

  } 


void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) { 

//void sortiert_einfuegen (struct stringList **liste, struct stringList *new) 

  struct stringList *Tail; 

  if (liste == NULL) 

    *liste = Neu; 

  else { 

    Tail = *liste; 

    while (Tail->next != NULL)  

      Tail = Tail->next; 

    Neu->next = Tail->next; 

    Tail->next = Neu; 

  } 

} 


void ausgabe(struct stringList **list) { //void ausgabe (struct stringList **list) 

  struct stringList *Tail = liste; 

  while (Tail != NULL) { 

    printf("%s\n", Tail->zeichen); 

    Tail = Tail->next; 

  } 

} 



int main (void) {  

  char str[80]; 

  int z; 

  z=5; 

  struct stringList *Neu; 

  while(1)  

  { 

    fgets(str, 30, stdin); 

    if (z != 0) { 

      Neu = neuesElement(str); 

      sortiert_einfuegen(&liste, Neu); 

      z--; 

    } 

    else break; 

  } 

  ausgabe(&liste);

  return(0); 

 }

Das lässt sich kompilieren und macht keine Mucken, stürzt aber nach der Eingabe des ersten Elements ab. Habe ein paar printf's eingebaut und so wie es aussieht hängt er in der while-Schleife der sortiert_einfuegen Funktion. Habt ihr da Ideen?

[Klotzkopp]

char zeichen[80];

Laut Aufgabenstellung soll das ein char-Zeiger sein, kein Array.

struct stringList *liste = NULL;

Ganz schnell weg mit der globalen Variablen :eek

Neu = (struct stringList *) malloc(sizeof(struct stringList));

Den Rückgabewert von malloc soll man nicht casten.

In neuesElement fehlt die Speicherreservierung für den Text (siehe oben: Array -> Zeiger)

void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

Die Funktion heißt zwar sortiert_einfuegen, aber irgendwie fügt sie immer am Ende ein. Ist sicher nicht Sinn der Sache.

void ausgabe(struct stringList **list)

Sieht gut aus.

expected struct stringlist ** but argument is of type struct stringlist *

Du musst die Adresse eines stringList-Zeigers reingeben, da die Einfügefunktion den Zeiger gegebenenfalls ändern muss.

[IltisvdT]

Laut Aufgabenstellung soll das ein char-Zeiger sein, kein Array.

statt char zeichen[80] hab ich nun (char *) zeichen

Ganz schnell weg mit der globalen Variablen :eek

Wenn ich die Zeile wegnehme und in die main einfüge sind sie für die anderen Funktionen nicht verfügbar. Wenn ich sie aber in jede Funktion einfüge, kann ich sie auch gleich global lassen?!

Den Rückgabewert von malloc soll man nicht casten.

In neuesElement fehlt die Speicherreservierung für den Text (siehe oben: Array -> Zeiger)

Ich soll ihn nicht casten, soll ich also das: (struct stringList *) ganz weglassen?

Speicherreservierung so? malloc(sizeof(struct stringList)+sizeof(zeichenkette))

Die Funktion heißt zwar sortiert_einfuegen, aber irgendwie fügt sie immer am Ende ein. Ist sicher nicht Sinn der Sache.

Ich glaube aber, dass es darauf hinausläuft. Hab mich in der Aufgabenstellung auch gewundert, wieso die sortiert einfügen heißt. Aber ich denke, da nur das Element und die Liste aus der main an die Funktion übergeben werden, dass das hintendranhängen damit gemeint ist.

Sieht gut aus.

Du musst die Adresse eines stringList-Zeigers reingeben, da die Einfügefunktion den Zeiger gegebenenfalls ändern muss.

Auch schon erledigt durch ausgabe(&liste) und sortiert_einfuegen(&liste, Neu).

Schreibe grade an der Suchen-Funktion...bin mal gespannt was daraus wird...

[Klotzkopp]

Wenn ich die Zeile wegnehme und in die main einfüge sind sie für die anderen Funktionen nicht verfügbar.

In main hast du schon eine Variable, und in sortiert_einfuegen und ausgabe hast du einen Parameter dafür (wobei der in sortiert_einfuegen die globale Variable verdeckt und der in ausgabe nicht benutzt wird).

Wenn ich sie aber in jede Funktion einfüge, kann ich sie auch gleich global lassen?!

Wenn du sie global lässt, sind die Parameter überflüssig, und damit entsprechen deine Funktionen nicht mehr der Aufgabenstellung.

Ich soll ihn nicht casten, soll ich also das: (struct stringList *) ganz weglassen?

Richtig.

Speicherreservierung so? malloc(sizeof(struct stringList)+sizeof(zeichenkette))

Nein. Erstens musst du das mit zwei getrennten malloc-Aufrufen machen. Zweitens ist sizeof(zeichenkette) falsch. Informiere dich darüber, was sizeof tut.

Ich glaube aber, dass es darauf hinausläuft. Hab mich in der Aufgabenstellung auch gewundert, wieso die sortiert einfügen heißt. Aber ich denke, da nur das Element und die Liste aus der main an die Funktion übergeben werden, dass das hintendranhängen damit gemeint ist.

Das glaube ich nicht. Der große Vorteil einer verketteten Liste ist ja, dass man auch mittendrin schnell einfügen kann.

[IltisvdT]

In main hast du schon eine Variable, und in sortiert_einfuegen und ausgabe hast du einen Parameter dafür (wobei der in sortiert_einfuegen die globale Variable verdeckt und der in ausgabe nicht benutzt wird).

Aaaah, ok...ich verstehe was du meinst und sehe es sogar. Kann aber die ausgabe und sortiert_einfuegen so lassen, oder?

Nein. Erstens musst du das mit zwei getrennten malloc-Aufrufen machen. Zweitens ist sizeof(zeichenkette) falsch. Informiere dich darüber, was sizeof tut.

Habs jetzt so: Neu = malloc(sizeof(struct stringList))+malloc(sizeof((char *)zeichenkette));

Da hat er aber Probleme, die beiden void Zeiger zu addieren. Aber Neu soll doch ein Zieger sein, der auf einen Speicherbereich zeigt, in den die Struktur mitsamt der eingabe reinpasst, richtig? Wo ist dann mein Fehler da?

Das glaube ich nicht. Der große Vorteil einer verketteten Liste ist ja, dass man auch mittendrin schnell einfügen kann.

Ja, das stimmt. Habe mit Kommilitonen gesprochen, wir sollen uns eine Ordnung ausdenken (zB Alphabet).

Habe eine suchen-Funktion geschrieben:

int suchen(struct stringList **liste, char *zeichenkette ) {

    int i=1;

    while(strcmp( zeichenkette, *liste->zeichen ) != 0 ) {

       *liste = **liste->next;  

        i++;    

        if( *liste == NULL ) {

          return(-1);                    

       }

    if(strcmp(zeichenkette, *liste->zeichen ) == 0)

        return(i);


    }


}

Beim kompilieren sagt er aber, dass ich den member zeichen (und next und nochmal zeichen) anfordere aus etwas, dass keine structure ist. Aber das gebe ich doch da vor bei int suchen(struct stringList **liste...

[Klotzkopp]

Habs jetzt so: Neu = malloc(sizeof(struct stringList))+malloc(sizeof((char *)zeichenkette));

Da hat er aber Probleme, die beiden void Zeiger zu addieren. Aber Neu soll doch ein Zieger sein, der auf einen Speicherbereich zeigt, in den die Struktur mitsamt der eingabe reinpasst, richtig? Wo ist dann mein Fehler da?

Du brauchst zwei getrennte Speicherreservierungen. Erst eine für Neu, dann eine für Neu->zeichen.

Und sizeof((char *)zeichenkette) ist immer noch falsch. sizeof liefert dir die Größe eines Typs. Der Typ char* ist auf einer 32-Bit-Plattform 4 Bytes groß. Und genau das kommt heraus, wenn du sizeof mit einem char-Zeiger verwendest. Für das zweite malloc darfst du also nicht sizeof benutzen. Du musst die Stringlänge bestimmten. Und vergiss nicht die Nullterminierung.

Deine suchen-Funktion verändert *liste, und macht damit deine Liste beim Suchen kaputt. Du solltest in der Funktion eine Kopie von *liste machen, und damit suchen.

Der zweite strcmp-Aufruf ist unnötig. Stell das return i; einfach hinter die Suchschleife.

Und beachte, dass der Pfeiloperator stärker bindet als der Dereferenzierungsoperator.

*liste->zeichen

ist also gleichbedeutend mit

*(liste->zeichen)

Du willst aber

(*liste)->zeichen

[IltisvdT]

WOW

Vielen Dank schonmal...er kompiliert es ohne Probleme. Leider stürzt das Programm ab.

Sieht so aus:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>


struct stringList { 

  struct stringList *next;

  char *zeichen;

};




struct stringList *neuesElement(char *zeichenkette) {

  struct stringList *Neu;

  Neu = malloc(sizeof(struct stringList));

  Neu->zeichen=malloc(strlen(zeichenkette)+1);

  Neu->next = NULL;

  strcpy(Neu->zeichen,zeichenkette);

  return Neu;

  }


void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

  struct stringList *Tail;

  if (liste == NULL)

    {*liste = Neu;

    printf("01");}

  else {

    Tail = *liste;

    printf("02");

    while (Tail->next != NULL) 

      Tail = Tail->next;

       Neu->next = Tail->next;

    Tail->next = Neu;

  }

}


void ausgabe(struct stringList **liste) { 

  struct stringList *Tail = *liste;

  while (Tail != NULL) {

    printf("%s\n", Tail->zeichen);

    Tail = Tail->next;

  }

}


int suchen(struct stringList **liste, char *zeichenkette ) {

    int i=1;

    struct stringList *tmp = *liste;

    while(strcmp( zeichenkette, tmp->zeichen ) != 0 ) {        //hier meint er, dass liste keine structure sei

        tmp = tmp->next;                                  // und hier

        i++;    

        if( tmp == NULL ) {

            return(-1);

        }

        else

            return(i);

        }

    }


int main (void) { 

  char str[80];

  int z;

  z=5;

  struct stringList *Neu;

  struct stringList *liste=NULL;

  while(1) 

  {

    fgets(str, 30, stdin);

    if (z != 0) {

      Neu = neuesElement(str);

      sortiert_einfuegen(&liste, Neu);

      z--;

    }

    else break;

  }

  printf("03");

  ausgabe(&liste);

  return(0);

 }

 

er printet das 02, nicht aber das 01 und dann is auch Feierabend. Woran könnte das denn wieder liegen?! :'(

[Klotzkopp]

void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

struct stringList *Tail;

if (liste == NULL)

Du musst *liste auf NULL prüfen, nicht liste.

[IltisvdT]

superduper...in der ausgabe hakt er noch...und zwar gibt er den letzten Eintrag nicht aus. Das kann natürlich auch an der eingabe liegen. Aber gott sei dank läuft es schonmal so halbwegs. Dann muss ich morgen eine löschen funktion machen und mich um das sortieren kümmern. Bis hierher schonmal vielen vielen dank

[IltisvdT]

Bin etwas weiter gekommen.. zum Einen hakt es immernoch an der Ausgabe des letzten Elements, finde aber einfach keinen Fehler:/

Habe nun eine Header-Datei draus gemacht und die Funktionen kann ich auch mit einer weiteren Datei aufrufen. Nun wollte ich mich an das loeschen eines Elements machen, nur leider wird immer das darauffolgende Element gelöscht, denke es liegt an der while-Schleife die tmp2 halt einen zuweit setzt, komme aber nicht drauf wie ich das verhindere... habe es mit einem weiteren strcmp in einer if-Funktion versucht, aber das ändert nichts am Problem..

hier mal die beiden Codes:

Header:

#ifndef a_h

#define a_h


#include <stdio.h>

#include <stdlib.h>

#include <string.h>


struct stringList { 

  struct stringList *next;

  char *zeichen;

};




struct stringList *neuesElement(char *zeichenkette) {

  struct stringList *Neu;

  Neu = malloc(sizeof(struct stringList));

  Neu->zeichen=malloc(strlen(zeichenkette)+1);

  Neu->next = NULL;

  strcpy(Neu->zeichen,zeichenkette);

  return Neu;

  }


void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

  struct stringList *Tail;

  if (*liste == NULL)

    {*liste = Neu;

    printf("01");}

  else {

    Tail = *liste;

    printf("02");

    while (Tail->next != NULL) 

      Tail = Tail->next;

       Neu->next = Tail->next;

    Tail->next = Neu;

  }

}


void ausgabe(struct stringList **liste) { 

  struct stringList *Tail = *liste;

  while (Tail != NULL) {

    printf("%s\n", Tail->zeichen);

    Tail = Tail->next;

  }

}


int suchen(struct stringList **liste, char *zeichenkette ) {

    int i=1;

    struct stringList *tmp = *liste;

    while(strcmp( zeichenkette, tmp->zeichen ) != 0 ) {   

        tmp = tmp->next;                                  

        i++;    

        if( tmp == NULL ) {

        printf("nicht vorhanden");

        return(-1);

        }

        }

        printf("sucheingabe war%s i=%d", zeichenkette, i);

        return(i);

    }


void loeschen(struct stringList **liste, char *zeichenkette) {

    struct stringList *loesch;

    struct stringList *tmp2= *liste;

    while(strcmp(zeichenkette, tmp2->zeichen) !=0){

    tmp2=tmp2->next;

    printf("SSSSSSSSSSSSS%s",tmp2->zeichen);

    if(tmp2==NULL)

        printf("nicht vorhanden");

    if(strcmp(zeichenkette, tmp2->zeichen) ==0){

    loesch=tmp2->next;

    tmp2->next=tmp2->next->next;

    free(loesch);

    };    

    }

    }

#endif

und die .c-Datei:

#include "a2.h"


int main (void) { 

  char str[80];

  char such[80]; 

  char loesch[80]; 

  int z;

  z=5;

  struct stringList *Neu;

  struct stringList *liste=NULL;

  while(1) 

  {

    fgets(str, 30, stdin);

    if (z != 0) {

      Neu = neuesElement(str);

      sortiert_einfuegen(&liste, Neu);

      z--;

    }

    else break;

  }

  printf("03");

  ausgabe(&liste);

  //printf("sucheingabe");

  //fgets(such, 30, stdin);

  //suchen(&liste, such);

  printf("loescheingabe");

  fgets(loesch, 30, stdin);

  loeschen(&liste, loesch);

  ausgabe(&liste);

  return(0);

 }

[Klotzkopp]

Bin etwas weiter gekommen.. zum Einen hakt es immernoch an der Ausgabe des letzten Elements, finde aber einfach keinen Fehler:/

Der Fehler ist nicht in der Ausgabe, sondern in der Eingabe.

Deine Eingabeschleife ist ein wenig seltsam. Du liest zuerst von der Tastatur ein, und prüfst dann erst deine Zählvariable und fügst ggf. in die Liste ein. Die sechste Tastatureingabe fügst du gar nicht erst ein.

Warum benutzt du nicht gleich z für die Schleifenbedingung?

Nun wollte ich mich an das loeschen eines Elements machen, nur leider wird immer das darauffolgende Element gelöscht, denke es liegt an der while-Schleife die tmp2 halt einen zuweit setzt, komme aber nicht drauf wie ich das verhindere...

Du wirst nicht drumherum kommen, dir in einer zusätzlichen Variablen den Vorgänger des gerade geprüften Elements zu merken, denn dessen next-Zeiger musst du auch ändern. Außerdem brauchst du eine Sonderfallbehandlung, falls jemand das erste Element löschen will, denn das hat keinen Vorgänger.

[IltisvdT]

Die ausgabe läuft nun sauber, habe das fgets in die if gepackt.

Um das erste Element zu löschen habe ich eine weiter if-Prüfung eingebaut und darin versucht, den Zeiger auf das 2. Element mittels "Hilfsvariable" zu sichern, dann den Speicherplatz des ersten Elements freizugeben und anschließend das erste Element gleich dem 2. zusetzen.

Ähnlich habe ich eine weitere Variable eingefügt um mir den Vorgänger des zulöschenden Elements zu merken.

Ich denke, dass er in beiden Fällen nicht aus der while-Schleife rauskommt, da er kein Ende findet..

Seh ich das Problem richtig? und wenn wie schaffe ich es dass er ein Ende findet?

#ifndef a_h

#define a_h


#include <stdio.h>

#include <stdlib.h>

#include <string.h>


struct stringList { 

  struct stringList *next;

  char *zeichen;

};




struct stringList *neuesElement(char *zeichenkette) {

  struct stringList *Neu;

  Neu = malloc(sizeof(struct stringList));

  Neu->zeichen=malloc(strlen(zeichenkette)+1);

  Neu->next = NULL;

  strcpy(Neu->zeichen,zeichenkette);

  return Neu;

  }


void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

  struct stringList *Tail;

  if (*liste == NULL)

    {*liste = Neu;

    printf("01");}

  else {

    Tail = *liste;

    printf("02");

    while (Tail->next != NULL) 

      Tail = Tail->next;

       Neu->next = Tail->next;

    Tail->next = Neu;

  }

}


void ausgabe(struct stringList **liste) { 

  struct stringList *Tail = *liste;

  while (Tail != NULL) {

    printf("%s\n", Tail->zeichen);

    Tail = Tail->next;

  }

}


int suchen(struct stringList **liste, char *zeichenkette ) {

    int i=1;

    struct stringList *tmp = *liste;

    while(strcmp( zeichenkette, tmp->zeichen ) != 0 ) {   

        tmp = tmp->next;                                  

        i++;    

        if( tmp == NULL ) {

        printf("nicht vorhanden");

		return(-1);

        }

		}

		printf("sucheingabe war%s i=%d", zeichenkette, i);

		return(i);

    }


void loeschen(struct stringList **liste, char *zeichenkette) {

	struct stringList *loesch= *liste; //

	struct stringList *tmp2= *liste;

	struct stringList *tmp3= *liste;

	if (strcmp(zeichenkette, tmp2->zeichen) ==0){

	loesch=tmp2->next;

	free(tmp2);  //

	tmp2=loesch;

	}

	else {

	while(strcmp(zeichenkette, tmp2->zeichen) !=0){

	tmp3=tmp2;

	tmp2=tmp2->next;

	if(tmp2==NULL)

		printf("nicht vorhanden");

	if(strcmp(zeichenkette, tmp2->zeichen) ==0){

	loesch=tmp3->next;

	tmp3->next=tmp3->next->next;

	free(loesch);

	};

	}

	}

	}

#endif

[flashpixx]

Im Normalfall hat man in der Liste zwei Zeiger, einen auf das erste Element (Beginn) und einen für das aktuelle Element. (optional noch einen dritten auf das letzte Element).

Außerdem würde ich innerhalb des Listen Elements nicht die Daten speichern sondern nur einen Zeiger auf den Inhalt, damit fällt dann der malloc und das strcpy weg. Wenn Du ihn als (void*) deklarierst, dann kannst Du "irgendwas" referenzieren. Denn im Moment duplizierst Du den Inhalt und Du musst ihn dann auch wieder löschen.

Bearbeitet 3. Januar 2011 von flashpixx

[IltisvdT]

So, haben unsere loeschen-fkt geändert. Sieht nun so aus:

void loeschen(struct stringList **liste, char *zeichenkette) {

    struct stringList *loesch= *liste; //

    struct stringList *tmp2= *liste;

    struct stringList *tmp3= *liste;

    if (strcmp(zeichenkette, tmp2->zeichen) ==0){

    loesch=tmp2->next;

    free(liste);  //

    *liste=loesch;

    printf("1.");

    }

    else {

    while(strcmp(zeichenkette, tmp2->zeichen) !=0){

    tmp3=tmp2;

    tmp2=tmp2->next;

    if(tmp2==NULL)

        printf("nicht vorhanden");

    if(strcmp(zeichenkette, tmp2->zeichen) ==0){

    loesch=tmp3->next;

    tmp3->next=tmp3->next->next;

    *liste=tmp3;

    free(loesch);

    printf("2.");

    break;

    };

    }

    }

    }

Er löscht auch brav das angegebene element, jedoch löscht er auch alle vorherigen, bis auf den direkten Vorgänger. zB ist die Liste 1 2 3 4 5 und er soll die 4 löschen, dann bleiben 3 und 5 über. Das liegt ja daran, dass wir liste=tmp3 speichern und tmp3 ja erst bei dem direkten Vorgänger beginnt. Wie kann man das lösen?

[Klotzkopp]

Eine Anmerkung am Rande: Tu dir selbst einen Gefallen, und rück deinen Code ordentlich ein. Bei dir ist ja fast der gesamte Code auf derselben Höhe.

Das könnte z.B. so aussehen:

void loeschen(struct stringList **liste, char *zeichenkette) {

    struct stringList *loesch= *liste; //

    struct stringList *tmp2= *liste;

    struct stringList *tmp3= *liste;

    if (strcmp(zeichenkette, tmp2->zeichen) ==0){

        loesch=tmp2->next;

        free(liste);  //

        *liste=loesch;

        printf("1.");

    }

    else {

        while(strcmp(zeichenkette, tmp2->zeichen) !=0){

            tmp3=tmp2;

            tmp2=tmp2->next;

            if(tmp2==NULL)

                printf("nicht vorhanden");

            if(strcmp(zeichenkette, tmp2->zeichen) ==0){

                loesch=tmp3->next;

                tmp3->next=tmp3->next->next;

                *liste=tmp3;

                free(loesch);

                printf("2.");

                break;

            };

        }

    }

}[/code]
Hier kann man viel besser erkennen, wo welcher Block anfängt und aufhört.



Das liegt ja daran, dass wir liste=tmp3 speichern 
Stimmt. Warum tust du das? Der Anfang der Liste ändert sich doch nur, wenn du das erste Element löschst.


Du musst übrigens auch den Speicher für den Text wieder freigeben. Momentan tust du das nicht, das ist ein Speicherleck. Durch wiederholtes Einfügen und Löschen verbraucht dein Programm also immer mehr Speicher.

[IltisvdT]

Habe nun die loeschen fkt geändert. Habe einfach die Zeile mit liste=tmp3 rausgeschmissen und voila, es funktioniert. Den Speicher freigeben mache ich mit free(zeichenkette), oder?

Ich bin so glücklich, weil das Programm so gut wie läuft, nur das sortieren funktioniert nicht. Und zwar stürzt das Programm ab, wenn die zweite eingabe länger ist als die erste, danach ist alles egal. Er printet dann einmal die 02 und dann hängt er, also macht ihm die while-schleife probleme. die dritte kann ruhig länger sein als die zweite und erste usw. Außerdem sortiert er die erste eingabe nicht. Also wenn ich zehn eingaben machen sortiert er die richtig der länge nach, nur die erste bleibt fest. Außerdem tut er sich schwer beim zahlen sortieren, aber das ist nciht so wichtig, denke ich. Vermutlich lassen sich ja die beiden Fehler auf den selben Fehler im Code begründen. Anbei der Code für die sortieren-Fkt:

void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

    struct stringList *Tail;

    if (*liste == NULL)

        {*liste = Neu;

        printf("01\n");

        }

    else {

        printf("02\n");

        while ((strlen((*liste)->zeichen)<strlen(Neu->zeichen)) && (strlen(((*liste)->next)->zeichen)>=strlen(Neu->zeichen))) 

          {printf("06");

          *liste = (*liste)->next;}

        Neu->next = (*liste)->next;

        (*liste)->next = Neu;

  }

}

Und zu dem einrücken: Ich schicke das mit nem Kumpel immer hin und her und scheinbar passen die editoren nciht so gut zusammen und das haut alles durchnander. aber ich gebe mir größte Mühe mich zu bessern.

[Klotzkopp]

Den Speicher freigeben mache ich mit free(zeichenkette), oder?

Du musst das freigeben, was dir malloc geliefert hat.

Was das Einfügen angeht: Benutz nicht *liste zum Durchlaufen der Liste, denn das ist dein Anfangszeiger. Den darfst du nur dann verändern, wenn du vorne einfügst oder löschst. Vorher hast du das mit Tail gemacht, das war besser.

[IltisvdT]

Jetzt hab ichs wieder auf Tail gebaut.

void sortiert_einfuegen(struct stringList **liste, struct stringList *Neu) {

    struct stringList *Tail;

    if (*liste == NULL)

        {*liste = Neu;

        printf("01\n");

        }

    else {

        Tail=*liste;

        printf("02\n");

        while ((strlen((Tail)->zeichen)<strlen(Neu->zeichen)) && (strlen(((Tail)->next)->zeichen)>=strlen(Neu->zeichen))) 

          {printf("06");

          Tail = (Tail)->next;}

        Neu->next = Tail->next;

        Tail->next = Neu;

  }

}

Selbe Problematik...er hängt in der while-Schleife, wenn der 2. Eintrag länger ist als der erste und beim sortieren nimmt er den ersten nicht mit.

Ich hab jetzt den Speicher freigegebn mit free(loesch) und free(loesch->zeichen), das sind ja die beiden, die ich mit malloc angefordert habe, geht das?

[Klotzkopp]

Die Bedingung deiner while-Schleife zeigt den richtigen Ansatz, aber so funktioniert das nicht. Erstens prüfst du nicht, ob du das Ende der Liste erreicht hast, und zweitens konstruierst du dadurch, dass du zwei Elemente gleichzeitig prüfst, einen zusätzlichen Sonderfall am Listenende.

Such, bis du einen Eintrag findest, der "größer" als das einzufügende Element ist. Zusätzlich merkst du dir den Vorgänger, wie beim Löschen. Und auch hier musst du auf den Sonderfall achten, dass du ganz vorne einfügen musst.

Ich hab jetzt den Speicher freigegebn mit free(loesch) und free(loesch->zeichen), das sind ja die beiden, die ich mit malloc angefordert habe, geht das?

Im Prinzip ja, aber du musst auf die Reihenfolge achten. Nachdem du loesch freigegeben hast, darfst du auf loesch->zeichen nicht mehr zugreifen. Das Freigeben erfolgt in umgekehrter Reihenfolge des Reservierens.

[IltisvdT]

so, jetzt hab ichs so:

else {

        Tail=*liste;

        printf("02\n");

        while ((strlen((Tail)->zeichen))<(strlen(Neu->zeichen))) 

          {printf("06\n");

          if(Tail->next==NULL)

            break;

          Tail2=Tail;

          Tail = Tail->next;}

        printf("07\n");

        Neu->next = Tail;

        Neu=Tail2->next;    

Und es geht garnichts mehr...:-/ Die Einträge dürfen nie länger oder kürzer sein als der vorherige und sie werden auch, wenn ich sie ausgeben lasse nicht gespeichert. Es ist also nur der erste da. Und wie ich das am Anfang einfüge weiß ich noch nicht. Würde da ne if-Bedingung machen und die strlen von liste->zeichen mit der neu->zeichen vergleichen und wenn da rauskommt, dass der neue an den anfang muss, ist *liste=Neu und *liste->next der alte Eintrag von liste, den muss ich also auch irgendwo noch speichern. Is das vom Prinzip her richtig?

[Klotzkopp]

Neu=Tail2->next;

Der hier ist falsch herum. Der next-Zeiger des Vorgängers soll auf das neue Element zeigen, nicht andersrum.

Würde da ne if-Bedingung machen und die strlen von liste->zeichen mit der neu->zeichen vergleichen und wenn da rauskommt, dass der neue an den anfang muss, ist *liste=Neu und *liste->next der alte Eintrag von liste, den muss ich also auch irgendwo noch speichern. Is das vom Prinzip her richtig?

Du kannst das auch einfach daran erkennen, dass Tail2 immer noch NULL ist, denn du hast es ja (hoffentlich) mit NULL initialisiert. Wenn wenn du vorn einfügen musst, wird die Schleife ja nie betreten, und damit wird Tail2 nichts anderes zugewiesen.