Programm mit verketteten Listen

[Gast]

Hilfe, ich sitz jetzt schon seit drei Tagen (jeden Tag 2 Std.) an einem Programm und bring es net zum laufen.

Angabe:

Schreiben Sie zu einer einfach verketteten generischen (datenunabhängigen) Liste folgende Funktionen:

- Erzeugen einer leeren Liste
- Prüfen, ob die Liste leer ist
- Bestimmen der Länge der Liste (die Länge ergibt sich durch die Anzahl der Knoten, die Länge der leeren Liste ist 0)
- Bestimmen der Adresse des i-ten Knoten, wobei 1<=i<=Länge
- Ersetzen des i-ten Knoten X durch einen anderen Knoten Y, wobei 1<=i<=Länge
- Bestimmen der Nummer (einsbasiert) des ersten Listenknotens, über den bestimmte Vergleichsdaten gespeichert sind
- Löschen des Listenelementes mit Nummer nr

Testen Sie die Funktionen mit Hilfe eines geeigneten Testprogrammes (main).

Das mit der Adresse kann man eigentlich gar net prüfen ob das stimmt, oder?

Hier mein Code:

struct node                                     // Strukturdefinition
{
  void *data;
  struct node *next;
};

void makeList(struct node **proot,struct node **ptail);
int checkList(struct node *root,struct node *tail);
int lenList(struct node *root);
struct node *getAddress(struct node *root,int n);
void delNode(struct node *help,struct node **proot);
void insertNode(struct node *help,struct node *neu,struct node **proot);
int searchData(struct node *akt,const void *data,int (*fcmp)(const void *,const void*));
int vgl(const void *a,const void *b);
int addTail(struct node **proot,struct node **ptail,const void *data);
void showValues(struct node *root,void (*fshow)(const void *));
void show(const void *a);

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
#include<string.h>
#include"hue_2.h"

int main()
{
  struct node *root, *tail, *pnew;
  int n, ok=1;
  char ein[101], *data;

  clrscr();
  makeList(&root,&tail);
  if(checkList(root,tail))
    puts("Liste leer!");
  else
  {
    puts("Liste nicht leer!");
    exit(1);
  }
  while(ok && printf("\nString: ") && gets(ein) && ein[0])
  {
    data = (char *)malloc(strlen(ein)+1);
    strcpy(data,ein);
    ok = addTail(&root,&tail,data);
  }
  printf("\n\nDie Liste: ");
  showValues(root,show);
  printf("\n\nDie L„nge der Liste betr„gt: %d", lenList(root));
  if(lenList(root))
  {
    printf("\n\nAdresse des wievielten Knotens anzeigen --> ");
    fflush(stdin);
    scanf("%d", &n);
    printf("\nAdresse des %d. Knotens: %p", n, getAddress(root,n));
    printf("\nGeben Sie bitte einen String ein --> ");
    fflush(stdin);
    gets(data);
    pnew = (struct node *)malloc(sizeof(struct node));
    pnew->data = (char *)malloc(strlen(data)+1);
    printf("\nDen wievielten Knoten der Liste wollen Sie durch das Datum ersetzen --> ");
    fflush(stdin);
    scanf("%d", &n);
    delNode(getAddress(root,n-1),&root);
    insertNode(getAddress(root,n-1),pnew,&root);
    showValues(root,show);
    printf("\nGeben Sie Vergleichsdaten ein --> ");
    fflush(stdin);
    gets(data);
    printf("\nDie Vergleichsdaten befinden sich im %d. Knoten.", searchData(root,data,vgl));
    printf("\nWelchen Knoten wollen Sie l”schen: "),
    fflush(stdin);
    scanf("%d", &n);
    delNode(getAddress(root,n-1),&root);
    showValues(root,show);
  }
  getch();
  return 1;
}

void makeList(struct node **proot,struct node **ptail)
{
  *proot = *ptail = NULL;            // Anfang und Ende auf NULL setzen
}

int checkList(struct node *root,struct node *tail)
{
  if(!root && !tail) return 1;       // falls Liste leer (1)
  else return 0;                     // falls Liste nicht leer (0)
}

int lenList(struct node *root)
{
  int i=0;

  while(root)                        // solange Listenelemente vorhanden
  {
    root = root->next;               // weiterrcken von root
    i++;                             // Laufvariable inkrementieren
  }
  return i;                          // Anzahl der Listenknoten rckgeben
}

struct node *getAddress(struct node *root,int n)
{
  int i;

  for(i=1;i<=n;i++)                 // solange bis gewnschtes Listenelement
    root = root->next;              // root um ein Listenelement weiterrcken
  return root;                      // Adresse des Listenknotens rckgeben
}

void delNode(struct node *help,struct node **proot)
{
  struct node *del;

  if(!help)                        // falls erstes Listenelement oder einziges
  {
    del = *proot;                  // zu l”schendes Element ist Anfang
    *proot = (*proot)->next;       // weiterrcken von root um eine Position
  }
  else
  {
    del = help->next;              // del zeigt auf das zu l”schende Element
    help->next = help->next->next; // neue Verbindung erstellen
  }
  free(del);                       // Speicherplatz freigeben
}

void insertNode(struct node *help,struct node *neu,struct node **proot)
{
  if(!help)                        // falls erstes Listenelement oder einziges
  {
    neu->next = *proot;            // neuen Knoten an erster Stelle einfgen
    *proot = neu;                  // Anfang ist neues Listenelement
  }
  else
  {
    neu->next = help->next;        // einfgen des neuen Knoten
    help->next = neu;              // Verbindung zwischen Vorg„nger und neu
  }
}

int searchData(struct node *akt,const void *data,int (*fcmp)(const void *,const void*))
{
  int i=0;

  while(akt && fcmp(data,akt->data))
  {
    akt = akt->next;
    i++;
  }
  return i;
}

int vgl(const void *a,const void *b)
{
  const char *e1 = (const char *)a, *e2 = (const char *)b;

  return strcmp(e1,e2);
}

int addTail(struct node **proot,struct node **ptail,const void *data)
{
  struct node *n;

  n = (struct node *)malloc(sizeof(struct node)); // Speicher fr den Knoten anfordern
  if(!n) return 0;                   // falls keinen Speicher erhalten
  n->next = NULL;            // neuen Tail auf NULL setzen
  n->data = (void *)data;
  if(*proot)
  {
    (*ptail)->next = n;
    *ptail = n;
  }
  else *proot = *ptail = n;
  return 1;
}

void showValues(struct node *root,void (*fshow)(const void *a))
{
  while(root)
  {
    fshow(root->data);
    root = root->next;
  }
}

void show(const void *a)
{
  printf("\n\n%s", (char *)a);
}

Wenn mir einer erklären könnte was falsch ist, dann wär das sehr sehr hilfreich. Schon danke im Voraus.

[Gast]

Ich hab mir nicht alles durchgesehen, aber:

Warum bedienst du dich in der Funktion makeList() einer doppelten Indirektion? Das ist gar nicht notwendig...

und was mir noch aufgefallen ist:
in lenList() beispielsweise lässt du dein erstes Element immer auf das nächste zeigen. Das heißt, nach dem Aufruf ist root == tail und du weißt nciht mehr, welches dein root-Element ist. Das Verhalten ist dann bei anderen Funktionen, die davon ausgehen, daß root auf das richtige Element zeigt, undefiniert.
Du musst einen extra Zeiger definieren, den du dann hochiterierst (quasi so, wie du das bei herkömmlichen Schleifen mit i machst)

und noch ein Tip:
bau die Liste so auf, daß du in einem Programm beliebig viele Listen bauen kannst. In deinem Programm gibts nämlich nur eine globale Liste. Ich meine dsa etwa so:

struct list
{
 int* first, *last;
};

void list_init (struct list* l)
{
 first = last = NULL;
}
.
.
.

so fällt es einem viel leichter, die Liste aufzubauen.

[Gast]

Das, dass der root-Zeiger woanders hinzeigt stimmt insofern nicht, da ich meiner Funktion eine Kopie des root-Pointers übergebe und nicht die Adresse, also nicht einen Pointer auf den root-Pointer. Demnach wird dieser auch außerhalb der Funktion nicht verändert

[Gast]

Achja, daher auch die doppelte Indirektion...

ist aber einfacher, wenn du's noch mit einer struct list aufbaust.

[chris152]

Unser Lehrer hat gesagt, dass wir es so machen sollen ...

Nur ich brauch mal Rat was an der Logik falsch ist, warum das Prog nicht das macht was es soll ...

[Gast]

1.) Vermischung von scanf und gets:
Mag mein Compiler aus irgendwelchen Gründen gar nicht.
Nimm anstelle von scanf("%d", &n); für die Eingabe von Zahlen besser überall:
gets(ein);
n = atoi(n) - 1; // Erklärung für -1 folgt gleich
Bei mir rauscht das Programm sonst durch die nächste Eingabe durch.
fflush(stdin) nutzt da gar nichts.

2.) ... eher fflush(stdout), damit der
Anweisungstext auch vor der Eingabe im Bildschirm erscheint, sonst
macht er sich's vielleicht im internen Puffer gemütlich. Also, überall stdin durch stdout ersetzen.

3.) Adresse des Knotens:
wenn der User mit der Zählung bei 1 beginnt (wonach Deine Funktion aussieht),
musst Du in getAdress aus <= nun < machen.
Du bist mit dieser Nummerierung aber inkonsequent!
Deshalb sage ich mal, wir beginnen bei 0 und passen alles darauf an!
In getAddress heisst es dann:
for(i=0; i<n; i++)
Daher subtrahiere ich in der unter 1.) genannten atoi-Zeile gleich 1.

4.) Musst nun aber alle Anzeigetexte entsprechend anpassen!
printf("\nAdresse des %d. Knotens: %p", n+1, getAddress(root,n));
...
printf("\nDie Vergleichsdaten befinden sich im %d. Knoten.", searchData(root,ein,vgl)+1); // auch zu 'ein' gleich eine Erklärung

5.) Eingabe des zu ändernden Strings:
Vorsicht, Du liest nach data ein, das ist nicht Dein Puffer.
Sicherlich hast Du data reserviert, aber was ist, wenn die Eingabe nicht genauso lang ist, wie der alte String?
Du musst auch hier zunächst nach 'ein' lesen:

...
printf("\nGeben Sie bitte einen String ein --> ");
fflush(stdin);
--> gets(ein);
pnew = (struct node *)malloc(sizeof(struct node));
--> pnew->data = (char )malloc(strlen(ein)+1);
--> strcpy((char)pnew->data, ein); // ja, natürlich auch einkopieren
...

So, jetzt liegen die Daten brav im neu angelegten, aber noch unverbundenen Knoten. Jetzt gibt es aber noch ein anderes Problem.
Erinnerst Du Dich an den anderen Thread, wo ich gesagt habe, dass es nicht immer zweckmässig ist, die Daten bei der Knotenlöschung mitzulöschen?
Es kann aber (wie in diesem Fall), durchaus gewünscht sein!
Aus diesem Grund gibt man bei der Knotenlöschung sinnvollerweise den Datenzeiger zurück. Das delNode hat mit dem free den Knoten gelöscht, aber nicht die Daten. Diesen Zeiger können wir deshalb in aller Ruhe zurückgeben,
damit darüber entschieden werden kann, was mit ihm geschieht.

Ändere mal Deinen Header auf:
void delNode(struct node *help,struct node **proot);*

Und die Funktion auf:

[cpp]
**
void *delNode(struct node *help,struct node **proot)
{
struct node del;
void ret;

if(!help) // falls erstes Listenelement oder einziges
{
del = *proot; // zu löschendes Element ist Anfang
*proot = (*proot)->next; // weiterrücken von root um eine Position
}
else
{
del = help->next; // del zeigt auf das zu löschende Element
help->next = help->next->next; // neue Verbindung erstellen
}
if (del)
ret = del->data;
else
ret = NULL;
free(del); // Speicherplatz freigeben
return ret; // Rückgabe des Datenzeigers
}
**[/cpp]

So, und nun kannst Du delNode(...) einfach in free(delNode(...)) umsetzen!!!

getAddress und delNode hast Du hoffentlich angepasst (alles was fett gedruckt ist), dann Dein main-Programm nochmal in der Zusammenfassung:

int main()
{
  struct node *root, *tail, *pnew;
  int n, ok=1;
  char ein[101], *data;

  clrscr();
  makeList(&root,&tail);
  if(checkList(root,tail))
    puts("Liste leer!");
  else
  {
    puts("Liste nicht leer!");
    exit(1);
  }
  while(ok && printf("\nString: ") && gets(ein) && ein[0])
  {
    data = (char *)malloc(strlen(ein)+1);
    strcpy(data,ein);
    ok = addTail(&root,&tail,data);
  }
  printf("\n\nDie Liste: ");
  showValues(root,show);
  printf("\n\nDie Länge der Liste beträgt: %d", lenList(root));
  if(lenList(root))
  {
    printf("\n\nAdresse des wievielten Knotens anzeigen --> ");
    fflush(stdout);
    gets(ein);
    n = atoi(ein)-1;
    printf("\nAdresse des %d. Knotens: %p", n+1, getAddress(root,n));

    printf("\nGeben Sie bitte einen String ein --> ");
    fflush(stdout);
    gets(ein);
    pnew = (struct node *)malloc(sizeof(struct node));
    pnew->data = (char *)malloc(strlen(ein)+1);
    strcpy((char*)pnew->data, ein);
    printf("\nDen wievielten Knoten der Liste wollen Sie durch das Datum ersetzen --> ");
    fflush(stdout);
    gets(ein);
    n=atoi(ein-1);
    free(delNode(getAddress(root,n),&root));
    insertNode(getAddress(root,n),pnew,&root);
    showValues(root,show);

    printf("\nGeben Sie Vergleichsdaten ein --> ");
    fflush(stdout);
    gets(ein);
    printf("\nDie Vergleichsdaten befinden sich im %d. Knoten.", searchData(root,ein,vgl)+1);

    printf("\nWelchen Knoten wollen Sie löschen: "),
    fflush(stdout);
    gets(ein);
    n=atoi(ein)-1;
    free(delNode(getAddress(root,n),&root));
    showValues(root,show);
  }
  getch();
  return 1;
}

[Gast]

ach so, intern zählen Deinen Knoten nun von 0 an, für den User aber ab 1 !

[Gast]

Wie kann ich einen Knoten einfügen?

[Gast]

Ähnlich wie beim Ersetzen, nur ohne Löschen des vorangegangenen. Also insertNode. Je nach Geschmack, am Anfang, am Ende oder wo der User will.

[Gast]

Ok, herzlichen Dank für den Rat