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

Der Compiler sagt dir auch wo Tail undeclared ist. Das kannst du ruhig mitteilen.

Ich nehme an das ist in deiner Funktion loeschen(). Denn dort nutzt du eine Variable Namens Tail die aber in der Funktion nicht deklariert ist.

Beachte auch den Unterschiede zwischen **liste und *liste.

IltisvdT

Das mit dem Tail ist sone Sache. Wenn man beispielsweise in der einfuegen_sort struct **liste macht, dann ist Tail undeclared. Wenn man aber stringList *liste hat, dann nicht. Das Problem sind ja die Vorgaben, wie die einzelnen Funktionen aufgebaut sein sollen und das, was wir haben. So richtig ist uns nicht klar wieso man da einen doppelzeiger hat. Worin liegt da der Vorteil? Und worauf zeigt er? Er muss ja ein äquivalent zu stringList *liste sein. Das würde heißen, dass **liste auf stringList *liste zeigt, oder? Wie kriegt man es hin, dass die so aussehen, wie die uns vorgegeben Prototypen?

Einfacher Zeiger:
Wenn du den Inhalt einer Variablen (in einer Funktion) ändern willst brauchst du den Zeiger auf den Speicherplatz.

Doppelzeiger:
Wenn jetzt aber der Zeiger woanders hin zeigen soll, muss die Funktion wissen wo der Zeiger selbst die Adresse ablegt.

Bsp.: double strtod ( const char * str, char ** endptr );

char *zahl = "3.141PI";
char *eptr;
double pi;

pi = strtod(zahl, &eptr); // Der Zeigerwert von eptr wird geändert 

printf("%s gibt %f und %s\n", zahl, pi ,eptr);

Du brauchst das bei deinem globalen *struct stringList liste = NULL;
liste zeigt auf das erste Element deiner Liste. Wenn jetzt aber ein neues erstes Element kommt (beim sortieren) muss auch der Inhalt von liste geändert werden.

Ist erstmal schwierig, aber eigentlich ganz logisch. :xmas2:

Noch eine persönliche Anmerkung:
Ich würde die Struktur andersherum aufbauen:

struct stringList {
  struct stringList *next;
//struct stringList *prev;
  char *zeichen;  // ist so gefordert (wegen malloc)
};

Dann kannst du einmal Funktionen für Listen entwickeln und die dann immer wieder verwenden

Wenn das im ersten Posting dein Quelltext mit Copy&Paste war kann der nicht funktionieren weil einige } fehlen und die ; bei
int suchen (struct stringList **liste, char * zeichenkette);
void loeschen(struct stringList **liste, char * zeichenkette);
zuviel sind.

Eine Zuweisung von struct stringList ** an struct stringList * gibt eine Warnung.
Auch Warnungen muss man beachten.

IltisvdT

Die ; sind geändert.

liste zeigt auf das erste Element deiner Liste. Wenn jetzt aber ein neues erstes Element kommt (beim sortieren) muss auch der Inhalt von liste geändert werden.

Das heißt also dass der **liste immer auf den ersten eintrag der Struct zeigt, egal welcher das ist, und *liste sich ändert, eben beim sortieren. Hab ich das richtig verstanden?

IltisvdT

Ich habe nochmal relativ neu angefangen. Zwar Abschnitte aus dem anderen übernommen, aber manchmal ist es besser neu anzufangen, finde ich. Bin bisher 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

die warning und die note hängen ja miteinander zusammen, denke ich?! Aber wie soll ich denn den void value nicht ignorieren, denn das, was beim sortierten einfügen "rauskommt" muss ich ja unter liste speichern, oder gibts da eine andere möglichkeit?

So, nun zum suchen und löschen. Ich brauche ja für das löschen die suchfunktion, damit ich eben einen bestimmten eintrag löschen kann. Die Suchfunktion hab ich noch nicht. Meine löschenfkt sieht so aus:

void loeschen(struct stringList **liste, char * zeichenkette)
{
int i;
struct stringList *tmp;
struct stringList *Tail;
	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");
}

Beim kompilieren zeigt er mir:

error: expected expression before struct

Was erwartet er denn da?

Danke schonmal

Wenn du

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

schreibst, sagt das void: "Diese Funktion hat keinen Rückagbewert".

Wenn du dann schreibst

liste = sortiert_einfuegen(liste, Neu);

willst du den Rückgabewert von sortiert_einfuegen liste zuweisen.
Der Compiler hat leider keine Rippen aus denen er sich den Wert raus schneiden kann

An die Adresse von liste kommst du auch mit dem Adressoperator &
Da liste ein Zeiger ist (struct stringList macht &liste daraus dann einen struct stringList **

IltisvdT

ok, das sieht nun so aus:

#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;
	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 **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;
  }
  printf("03");
  ausgabe(&liste);
  return(0);
 }

Das Problem ist nun, dass er sich aufhängt, nachdem ich ein element eingegeben habe. Er printet die 02 und stürzt dann ab. Muss also in der while-Schleife hängen. Ne Idee?

Es fehlt ja das 01 (Erstes Element in leere Liste!) Also ist das Problem bei dem
if (liste == NULL). Da sollte liste nie NULL sein, da liste auf den globalen Zeiger verweist.

if (*liste == NULL)
...

IltisvdT schrieb:

sein Compiler schrieb:

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

die warning und die note hängen ja miteinander zusammen, denke ich?! Aber wie soll ich denn den void value nicht ignorieren, denn das, was beim sortierten einfügen "rauskommt" muss ich ja unter liste speichern, oder gibts da eine andere möglichkeit?

Damit du verstehst, was der Doppelzeiger soll:
Normal ist ja folgendes:

+---+---+   +---+---+           +---+---+
| b | *===> | c | *===> ... ==> | z | X |
+---+---+   +---+---+           +---+---+
  ^
  |
  +--- list

Der Knoten b zeigt auf c zeigt auf ... zeigt auf den Endknoten z.
Die Liste ist somit ein Zeiger auf b.

Jetzt fügen wir den Buchstaben a ein (sortiert) und es ergibt sich folgendes:

+---+---+   +---+---+           +---+---+
| a | *===> | b | *===> ... ==> | z | X |
+---+---+   +---+---+           +---+---+
              ^
              |
              +--- list

Problem: Der Zeiger auf die Liste stimmt nicht mehr, er muss verändert werden.
Weil Parameter nicht verändert werden können, benötigen wir den Speicherort des Parameters, den Zeiger auf ihn.

sortiert_einfuegen(&liste, Neu);

Liste ist zwar ein globaler Zeiger, aber ich rate dir dringlichst, das zu ändern, auch weil die Aufgabenstellung sonst auf dessen Übergabe verzichtet hätte.

Danke für die Bilder.

IltisvdT

Bin jetzt relativ weit. Hab ne header Datei erstellt usw und ein Programm geschrieben, dass darauf zugreift usw. Das funktioniert bis aus das folgende: Wenn der zweite eintrag den ich mache größer ist als der erste stürzt er ab. Wenn der zweite größer ist als der dritte is das kein Problem...nur 1. und zweiter machen Probleme. Außerdem sortiert er dahingehend falsch, dass der erste eintrag immer der erste bleibt, egal wie lang er ist. Die anderen werden brav der länge nach sortiert, nur der erste eben nicht. Vermutlich hängen aber beide fehler mit dem selben Fehler im Code zusammen. Anbei mal mein Code für die sortiert einfügen:

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;
  }
}

Dann hab ich noch meine loeschen-Fkt. Die löscht auch zufriedenstellend, allerdings zu viel. Er löscht nämlich alle Eintrage bis einschließlich dem zu löschenden Element eben bis auf den direkten vorgänger. Danach die bleiben unberührt. zB hab ich ne Liste 1 2 3 4 5 6 7 8 und will die 4 löschen, dann bleibt 3 5 6 7 8 über. Das liegt vermutlich daran, dass meine Liste = tmp3 gesetzt wird. Wie ändere ich das ins richtige? Hier mein Code:

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;
	};
	}
	}
	}

Erstmal zu deinem ersten Problem.

Du änderst das globale *liste nur wenn kein Eintrag in der Liste ist.
Schau die nochmal die Bilder von dblptr an, da wo a dazukommt.
Du musst wie beim Fall == NULL noch den globalen Eintrag ändern.

Ich denke auch, dass du besser strcmp statt strlen benutzen solltest.

Beim löschen musst du auch noch den Text mit free freigeben.

IltisvdT

Habe das löschen Problem behoben. Und noch ein free(zeichenkette) eingefügt. Ist das richtig? Also zum textspeicher löschen?!

Bleibt noch das sortier-Problem...:-/ Die Bilder sind echt gut, hab ich gerafft nun, denke ich