4. Verkettete Liste

Verkettete Liste

  • P

    Hi Leute,

    ich hab heute angefangen mit Pointern zu arbeiten und habe mir überlegt, dass ich ein Übungsprogramm mache, in dem der Benutzter ein Land und die Einwohnerzahl eingibt.

    Diese Daten sollen dann in einer verkettetn Liste gespeichert werden. Länder mit weniger als 100 Mio. Einwohnern sollen am Anfang der Liste, Länder >= 100 Mio. Einwohner am Ende der Liste gespeichert werden. Leider bin ich jetzt an einem Punkt, wo ich nicht mehr weiter komme. So schwer kann das ja nicht sein, aber ich komm total durcheinander mit den Pointern. Ich brauche ja eigentlich noch zwei Pointer mehr, für Anfang und Ende der Liste, aber ich weiß nicht genau, wie ich diese dann benutzen muss.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedf struct
    {
        char Name[30];
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot* Liste;

typedef struct Knot
    {
        Land eintrag;
        Liste vergaenger;
        Liste nachfolger;
    }Knoten;

einfuegen(Land* land, char c, int anzahl){

if(land->)

}

int main(void){

char c;
int anzahl;
Land land;

printf("Geben sie Land und Bevölkerungsgröße ein\n");
scanf("%s %d",c,anzahl);

einfuegen(&land,c,anzahl);

while(s!='ende'|s!='Ende'){

    printf("Geben sie Land und Bevölkerungsgröße ein\n");
    scanf("%s %d",c,anzahl);
    einfuegen(&land,c,anzahl);

}

return 0;
}
    0
  • ?

    Geh das Kapitel mit den (String-)Arrays nochmal durch

    char c; ist ein einzelnes Zeichen.

    Bei scanf("%s %d",c,anzahl); liest du aber mit %s einen Nullterminierten String ein. Das sind mehrere Zeichen.

    Deine Funktion sollte dann so aussehen

    int einfuegen(typedef struct Knot* Liste, char *name, int anzahl)
{
  lege eine Struct Land an
  kopiere die Daten hinein. 

  Suche die richtige Stelle in der Liste (vergaenger->Einwohner < anzahl < nachfolger->Einwohner)

  Besorge Speicher für einen Knoten
     Verweise auf Land,
     Verweise auf vergaenger und nachfolger
     vergaenger->nachfolger und nachfolger->vergaenger auf Konten zeigen lassen

  Bei bedarf Liste->nachfolger oder Liste->vergaenger ändern

  return 0 für OK , !0 für Fehler
}

    Warum ist Einwohner ein double und anzahl ein int?

    Du kannst typedef struct Knot Liste;* erst machen, wenn du struct Knot definiert hast.

    0
  • P

    Vielen Dank, dass Du geantwortet hast! Klar, Anzahl muss ein double sein. Aber das mit c[30] müsste doch gehen, oder? Der Benutzter gibt dann z.B. "Angola" ein und das wird als String ausgelesen.

    Ich komme mit den Pointern einfach noch nicht klar. Aber wenn ich mich hier einmal irgendwie durchquäle, wirds bestimmt besser vom Verständnis her. 🙂

    Ich muss noch im Hauptprogramm Pointer für Anfang und für Ende deklarieren, habe ich mir sagen lassen. Aber ich weiß nicht, warum das im Hauptprogramm sein muss.

    Außerdem ist Liste doch ein Pointer auf einen Knot. Aber im Knot namens Knoten sind wieder Pointer namens Liste. Da ist doch irgendiwe eine Schleife drin, oder? Erstmal verwirrend für mich. Aber diese Bezeichnungen habe ich aus der Aufgabenstellung übernommen.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedf struct
    {
        char Name[30];
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
        Liste anfang
        Liste Ende

    }Knoten;

typedef struct Knot* Liste;

einfuegen(Knoten* liste, char Name, double anzahl){

if(liste->anfang==NULL){
Liste tmp=(Liste) malloc(1*sizeof(Knoten));

}

}

int main(void){

char c[30];
int anzahl;
Knoten liste;

printf("Geben sie Land und Bevölkerungsgröße ein\n");
scanf("%s %d",c,anzahl);

einfuegen(&liste,c,anzahl);

while(s!='ende'|s!='Ende'){

    printf("Geben sie Land und Bevölkerungsgröße ein\n");
    scanf("%s %d",c,anzahl);
    einfuegen(&land,c,anzahl);

}

return 0;
}
    0
  • ?

    psigh schrieb:

    Aber das mit c[30] müsste doch gehen, oder?

    Schauen wir mal:

    Vereinigtes Königreich von Grossbritannien und Nordirland
         1         2         3         4         5         6
123456789012345678901234567890123456789012345678901234567890

    sind schon 57 Buchstaben plus die '\0' am Ende = 58

    In deinem Knoten müssen Zeiger definiert sein.

    typedef struct Knot
    {
        Liste *vorgaenger; // jetzt ist es ein Zeiger
        Liste *nachfolger; // jetzt ist es ein Zeiger
        Land eintrag;

    }Knoten;

    Dann ist im Hauptknoten kein Land eingetragen und vorgaenger zeigt auf das erste Element der Liste und nachfolger auf das Letzte (oder umgekehrt, was besser in die Programmlogik passt).

    Nimm dir mal Zettel und Bleistift und Radiergummi und spiel das mal durch

    0
  • G

    psigh schrieb:

    Klar, Anzahl muss ein double sein.

    Auch wenn die Anzahl an Einwohnern in Deutschland auch irgendwie... "im fließen ist", würde es doch wesentlich mehr Sinn machen, die Anzahl an Einwohnern als Ganzzahl zu deklarieren 😉 So wie du das in der main auch machst. Beim Aufruf von scanf hat sich übrigens noch ein Fehler eingeschlichen... die Anzahl musst du per Adresse einlesen: scanf("%s %d",c, &anzahl);

    Du solltest dir nochmal ganz genau überlegen, wie eine verkettete Liste aufgebaut ist und welche Pointer in welchem Teil benötigt werden. Die Liste selbst braucht einen Zeiger auf das erste Listenelement. Optional kannst du auch einen Zeiger auf das letzte Element hinzufügen. Im Listenelement selbst brauchst du neben den Daten auch einen Zeiger auf das nächste Element bzw. optional auch einen auf das vorherige Element.

    Das sieht dann im pseudocode so aus (zeigernotation hab ich weggelassen):

    listenelement {
  daten;
  nächstes listenelement;
  vorheriges listenelement;
}

liste {
  erstes listenelement;
  letztes listenelement;
}
    0
  • ?

    Ich denke, dass die Anzahl der Einwohner IN MILLIONEN (siehe Kommentar) als double absolut in Ordnung ist. Er gibt dann halt 81.751 für z.B. Deutschland an.

    @DirkB: Er liest die Eingabe über scanf ein. Das ist dann irgendwie immer mit dem Speicher begrenzt (man könnte natürlich z.B. scanf_s (Standard?) nutzen, aber er lernt ja offenbar noch, also kehren wir das mal beiseite). D.h. seine Annahme von char[30] ist m.M.n. völlig in Ordnung, so lange das Land natürlich nicht mehr als 29 Zeichen enthält.

    Des Weiteren müssen in seinem Knoten ( Knot ) keine Zeiger definiert werden: Man schaue nur kurz auf das typedef typedef struct Knot* Liste; (das nichtsdestotrotz aber VOR der struct Knot genutzt werden muss. Denn der Compiler weiß sonst nicht, was Liste sein soll. In dem Fall musst du allerdings struct Knot noch vordeklarieren.)

    Also sähe das so aus:

    struct Knot; /* Forward Decl. */

typedef struct Knot* Liste; /* Sagt dem Compiler, was Liste ist */

struct Knot {
 ...
};

    Noch ein grundsätzlicher Tip: Die Einrückung sollte konsistent sein und dem Lesefluss helfen (die Funktion einfuegen sieht ja grauenhaft aus). Und die unnötigen Newlines sind auch... unnötig 😛 (siehe einfuegen ).

    0
  • P

    Vielen Dank für Eure Hilfe. Ich werde die Sachen jetzt mal ausprobieren.

    0
  • P

    Ich bin etwas weiter, aber so richtig kapiert hab ich es noch nicht. Deswegen sind da oben mit Sicherheit einige Sachen falsch oder es Fehlen Dinge.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Knot* Liste;

typedef struct
    {
        char Name[30];
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
    }Knoten;

typedef struct
    {
        Liste anfang;
        Liste ende;
    }anfang_ende_liste;

einfuegen(anfang_ende_liste* liste, char c, double anzahl){

if(liste->anfang==NULL){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    liste->anfang=tmp;
    liste->ende=tmp;
    liste->anfang->nachfolger=NULL;
    liste->anfang->vorgaenger=NULL;
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
}

if (anzahl<100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->vorgaenger=NULL;
    tmp->nachfolger=liste->anfang;
    liste->anfang=tmp;

}

if (anzahl>=100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->nachfolger=NULL;
    tmp->vorgaenger=liste->ende;
    liste->ende=tmp;

}

}

int main(void){

char c[30];
int anzahl;
anfang_ende_liste liste;

printf("Geben sie Land und Bevölkerungsgröße ein\n");
scanf("%s %d",c,&anzahl);

einfuegen(&liste,c,anzahl);

while(c!='ende'|c!='Ende'){

    printf("Geben sie Land und Bevölkerungsgröße ein\n");
    scanf("%s %d",c,&anzahl);

    einfuegen(&land,c,anzahl);

}

return 0;
}
    0
  • P

    Ich habe noch ein paar Fehler, die mir aufgefallen sind, verbessert.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Knot* Liste;

typedef struct
    {
        char Name[30];
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
    }Knoten;

typedef struct
    {
        Liste anfang;
        Liste ende;
    }anfang_ende_liste;

einfuegen(anfang_ende_liste* liste, char c, double anzahl){

if(liste->anfang==NULL){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    liste->anfang=tmp;
    liste->ende=tmp;
    liste->anfang->nachfolger=NULL;
    liste->anfang->vorgaenger=NULL;
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
}

if (anzahl<100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->vorgaenger=NULL;
    tmp->nachfolger=liste->anfang;
    liste->anfang=tmp;
    tmp->nachfolger->vorgaenger=tmp
}

if (anzahl>=100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->nachfolger=NULL;
    tmp->vorgaenger=liste->ende;
    liste->ende=tmp;
    tmp->vorgaenger->nachfolger=tmp

}

}

int main(void){

char c[30];
int anzahl;
anfang_ende_liste liste;

printf("Geben sie Land und Bevölkerungsgröße ein\n");
scanf("%s %d",c,&anzahl);

einfuegen(&liste,c,anzahl);

while(c!='ende'||c!='Ende'){

    printf("Geben sie Land und Bevölkerungsgröße ein\n");
    scanf("%s %d",c,&anzahl);

    einfuegen(&land,c,anzahl);

}

return 0;
}
    0
  • H

    Und was ist jetzt die Frage? Warum prüfst du auf die Anzahl beim Einfügen? Das ist einfach unnötige Codeduplizierung und der Liste kann es egal sein welcher Inhalt wo liegt. Später kannst du immer noch eine sort-funktion schreiben.

    Es ist genauso schlecht umgesetzt wie die main. Kennst du do while?

    Und das compiliert/funktioniert bei dir?

    0
  • P

    In der main ist doch eine while Schleife, oder?

    Nein, es compiliert nicht. Denn es sind ne menge Fehler drin, die ich gerade zu finde veruche. Ich bin Anfänger und das ist meine erste Liste. Und überhaupt bin ich so ziehmlich am Anfang von allem. Klar, ich würds auch schon direkt gerne mit verbundenen Augen super elegant reintippen können, kann ich aber nicht. 🙂 Deswegen bin ich hier.

    Eine Sache, die ich bisher z.B. noch nicht geschafft habe, ist den String zu übergeben. Außerdem glaube ich auch, dass die Liste zu kpmliziert ist. Das geht bestimmt auch einfacher.

    0
  • H

    Gute Einsicht, aber du kannst dir Zeilen sparen wenn du Do-while verwendest. Um auf ende/Ende zu prüfen musst du strcmp verwenden am beste in der Kombination mit tolower oder toupper.

    Nur als Beispiel gedacht:

    #include <stdio.h>
#include <string.h>
#include <ctype.h>

int main ()
{
	char szKey[] = "ende";
	char szInput[80];
	int i;

	do
	{
		printf ("\"ende\" zum Beenden eingeben: ");
		scanf ("%s", szInput);

		//Groß/Kleinschreibung egal machen
        i = 0;
		while (szInput[i])
		{
			szInput[i] = tolower(szInput[i]);
			i++;
		}
	} while (strcmp (szKey, szInput) != 0);

	printf("Programm beendet!");
	return 0;
}
    0
  • P

    Wenn man diese Sache jetzt mal bei Seite lässt (ich werds im Endeffekt so machen wie Du gesagt hast), wie kann ich dann diesen String in die Funktion einfuegen übergeben? Ich komme nicht drauf.

    0
  • H
     

    #include <stdio.h>

void f(char *str)
{
    printf("%s", str);
}

int main ()
{
    char c[] = "ende";

    f(c);

    return 0;
}

    Achtung: Ich übergebe keine Größe noch prüfe ich auf Gültigkeit oder Länge des Zeigers. In der Regel musst du dieses machen.

    void f(char *str, int size)
    0

  • psigh schrieb:

    Außerdem glaube ich auch, dass die Liste zu kpmliziert ist. Das geht bestimmt auch einfacher.

    Super Einsicht. Nimm für den Anfang ein Array mit einer max. Anzahl Elemente und mitlaufendem Elementezähler. Das lässt sich auch sehr einfach sortieren.

    0
  • P

    Super, vielen vieln Dank. Jetzt ist der Fehler schonmal weg. Ich verstehe nur einfach nicht genau warum ich *c schreiben muss. Ich dachte wenn man sowas wie char c schreibt, dann IST c schon ein Pointer auf den ersten Buchstaben. Deswegen schreibt man doch auch immer scanf("%s", c) und nicht scanf("%s", &c).

    Außerdem sagt er in Zeile 54 und 64 (habe ich daneben geschrieben) "assignment makes integer from pointer without a cast."

    Das dritte Problem ist, dass der ganze Editor beim Ausführen abstürzt, was mir aber erstmal egal ist. Compilieren ist momentan erstmal mein Hauptziel.

    Es gibt diverse Programm die in der Uni laufen und bei mir (Windows) komischer Weise nicht.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Knot* Liste;

typedef struct
    {
        char Name;
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
    }Knoten;

typedef struct
    {
        Liste anfang;
        Liste ende;
    }anfang_ende_liste;

einfuegen(anfang_ende_liste* liste, char *c, double anzahl){

if(liste->anfang==NULL){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    liste->anfang=tmp;                                 
    liste->ende=tmp;                     
    liste->anfang->nachfolger=NULL;
    liste->anfang->vorgaenger=NULL;
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
}

if (anzahl<100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;                             /*54*/
    tmp->eintrag.Einwohner=anzahl;
    tmp->vorgaenger=NULL;
    tmp->nachfolger=liste->anfang;
    liste->anfang=tmp;
    tmp->nachfolger->vorgaenger=tmp;
}

if (anzahl>=100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;                              /*64*/
    tmp->eintrag.Einwohner=anzahl;
    tmp->nachfolger=NULL;
    tmp->vorgaenger=liste->ende;
    liste->ende=tmp;
    tmp->vorgaenger->nachfolger=tmp;

}

}

int main(void){

char c;
int anzahl;
anfang_ende_liste liste;

printf("Geben sie Land und Bevölkerungsgröße ein\n");
scanf("%s %d",c,&anzahl);

einfuegen(&liste,c,anzahl);

while(c!='ende'||c!='Ende'){

    printf("Geben sie Land und Bevölkerungsgröße ein\n");
    scanf("%s %d",c,&anzahl);

    einfuegen(&liste,c,anzahl);

}

return 0;
}
    0
  • H

    char c ist eine Variable und demnach musst du die Adresse dieser an scanf übergeben. Hast du vergessen daraus einen festen Array zu machen?

    char c[80];

    Und das:

    while(c!='ende'||c!='Ende')

    wird auch weiterhin NICHT kompilieren weil es illegal ist. Du musst strcmp verwenden.

    0
  • P

    Ich habs jetzt mal versucht, es schöner zu machen. Ich habe auch nur noch zwei Warnungen jetzt. "assignment makes integer from pointer without a cast".

    Eben hatte ich ja noch acht Warnungen. Und abschützen tut auch nichst mehr. Ich muss jetzt nur noch versuchen, die Liste auszulesen. Ich weiß ja noch nicht, ob das funktioniert.

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Knot* Liste;

typedef struct
    {
        char Name;
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
    }Knoten;

typedef struct
    {
        Liste anfang;
        Liste ende;
    }anfang_ende_liste;

einfuegen(anfang_ende_liste* liste, char *c, double anzahl){

if(liste->anfang==NULL){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    liste->anfang=tmp;
    liste->ende=tmp;
    liste->anfang->nachfolger=NULL;
    liste->anfang->vorgaenger=NULL;
    tmp->eintrag.Name=*c;
    tmp->eintrag.Einwohner=anzahl;
}

if (anzahl<100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->vorgaenger=NULL;
    tmp->nachfolger=liste->anfang;
    liste->anfang=tmp;
    tmp->nachfolger->vorgaenger=tmp;
}

if (anzahl>=100){
    Liste tmp=(Liste) malloc(1*sizeof(Knoten));
    tmp->eintrag.Name=c;
    tmp->eintrag.Einwohner=anzahl;
    tmp->nachfolger=NULL;
    tmp->vorgaenger=liste->ende;
    liste->ende=tmp;
    tmp->vorgaenger->nachfolger=tmp;

}

}

int main(void){

char c[40];
int anzahl;
anfang_ende_liste liste;
char ende[]="ende";

do{

    printf("Geben sie Land und Bevoelkerungsgroeße ein\n");
    scanf("%s %d",c,&anzahl);

    einfuegen(&liste,c,anzahl);

}
while(strcmp(ende,c) !=0);

return 0;
}
    0
  • H

    Es muss void einfuegen sein Rückgabewert fehlt.

    void einfuegen(....)

    Im struct für Land hast du nur ein Char du brauchst einen Array!

    typedef struct
{
    char Name[100]; //<--- ARRAY
    double Einwohner; /*Einwohner in Millionen*/

}Land;

    Du kannst nicht den Inhalt eines Pointers einem Array zuweisen. Benutze strcpy!

    strcpy(tmp->eintrag.Name, c);

    UND RÜCKE ENDLICH DEINEN TEXT GESCHEIT EIN. Die gesamte Einfuegen Funktion ist nicht gut...

    Bevor du weitermachst eine Liste vergeblich zu implementieren schau dir doch erstmal BITTE die Grundlagen an.

    Edit: Wenn du das Buch "C von A bis Z von J.W." hast, dann tue dir einen Gefallen und wirf es endlich weg. Verbrenne es!

    0
  • P
     

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Knot* Liste;

typedef struct
    {
        char Name[30];
        double Einwohner; /*Einwohner in Millionen*/

    }Land;

typedef struct Knot
    {
        Land eintrag;
        Liste vorgaenger;
        Liste nachfolger;
    }Knoten;

typedef struct
    {
        Liste anfang;
        Liste ende;
    }anfang_ende_liste;

void einfuegen(anfang_ende_liste* liste, char *c, double anzahl){

    if(liste->anfang==NULL){
        Liste tmp=(Liste) malloc(1*sizeof(Knoten));
        liste->anfang=tmp;
        liste->ende=tmp;
        liste->anfang->nachfolger=NULL;
        liste->anfang->vorgaenger=NULL;
        strcpy(tmp->eintrag.Name, c);
        tmp->eintrag.Einwohner=anzahl;
    }

    if (anzahl<100){
        Liste tmp=(Liste) malloc(1*sizeof(Knoten));
        strcpy(tmp->eintrag.Name, c);
        tmp->eintrag.Einwohner=anzahl;
        tmp->vorgaenger=NULL;
        tmp->nachfolger=liste->anfang;
        liste->anfang=tmp;
        tmp->nachfolger->vorgaenger=tmp;
    }

    if (anzahl>=100){
        Liste tmp=(Liste) malloc(1*sizeof(Knoten));
        strcpy(tmp->eintrag.Name, c);
        tmp->eintrag.Einwohner=anzahl;
        tmp->nachfolger=NULL;
        tmp->vorgaenger=liste->ende;
        liste->ende=tmp;
        tmp->vorgaenger->nachfolger=tmp;

    }

}

int main(void){

char c[30];
int anzahl;
anfang_ende_liste liste;
char ende[]="ende";

do{

    printf("Geben sie Land und Bevoelkerungsgroesse ein\n");
    scanf("%s %d",c,&anzahl);

    einfuegen(&liste,c,anzahl);

}
while(strcmp(ende,c) !=0);

return 0;
}

    Ist es jetzt etwas besser eingerückt?

    Das mit dem void hätte ich echt wissen müssen. Klar, ohne Rückgabewert. Das mit char ist mir nicht klar. Ich meine mir ist klar, dass oben im Struct ein Array stehen sollte. Hab ich ja jetzt auch. Aber den Rest durchblicke ich noch nicht so ganz. Ich kenne die Befehle aus der Stringbibliothek auch noch nicht. Aber ok...man lernt. Ich hab strcmp vielleicht auch falsch eingesetzt. Denn jetzt habe ich zwar keine Warnung mehr, aber wieder einen Absturz

    0
Anmelden zum Antworten