Doppelt verkettete Listen

[Cherrycoke]

DVListe dvlist;
 
Knoten* k1 = malloc(sizeof(Knoten));
Knoten* k2 = malloc(sizeof(Knoten));
Knoten* k3 = malloc(sizeof(Knoten));
Knoten* k4 = malloc(sizeof(Knoten));
 
k1->nachf = k2;
k2->nachf = k3;
k3->nachf = k4;
 
k4->vorg = k3;
k3->vorg = k2;
k2->vorg = k1;
 
k1->vorg = NULL; // Knoten 1 hat keinen Vorgänger.
k4->nachf = NULL; // Knoten 3 hat keinen Nachfolger.
 
dvlist.anfang = k1;
dvlist.ende = k4;	
return 0;

Ich habe es nun mal so gelöst. Hoffentlich ist das richtig.

Was ich mit meinem letzten Beitrag gemeint hatte, ist diese Stelle hier:

Knoten* k1 = malloc(sizeof(Knoten));
Knoten* k2 = malloc(sizeof(Knoten));
Knoten* k3 = malloc(sizeof(Knoten));
Knoten* k4 = malloc(sizeof(Knoten));

Also brauche ich in diesem Fall Speicherplatz für 4 x die Größe des Types Knoten?

 

[deepthroat]

DVListe dvlist;
 
Knoten* k1 = malloc(sizeof(Knoten));
Knoten* k2 = malloc(sizeof(Knoten));
Knoten* k3 = malloc(sizeof(Knoten));
Knoten* k4 = malloc(sizeof(Knoten));
 
k1->nachf = k2;
k2->nachf = k3;
k3->nachf = k4;
 
k4->vorg = k3;
k3->vorg = k2;
k2->vorg = k1;
 
k1->vorg = NULL; // Knoten 1 hat keinen Vorgänger.
k4->nachf = NULL; // Knoten 3 hat keinen Nachfolger.
 
dvlist.anfang = k1;
dvlist.ende = k4;	
return 0;

Ich habe es nun mal so gelöst. Hoffentlich ist das richtig.

Was ich eigentlich meinte ist: Füge der bestehenden Liste ein Element hinzu - am Ende oder am Anfang.

Was ich mit meinem letzten Beitrag gemeint hatte, ist diese Stelle hier:

Knoten* k1 = malloc(sizeof(Knoten));
Knoten* k2 = malloc(sizeof(Knoten));
Knoten* k3 = malloc(sizeof(Knoten));
Knoten* k4 = malloc(sizeof(Knoten));

Also brauche ich in diesem Fall Speicherplatz für 4 x die Größe des Types Knoten?

Um einen Knoten zur Liste hinzuzufügen brauchst du natürlich einen neuen Knoten und somit natürlich auch Speicherplatz für diesen einen, neuen Knoten.

Gruß

 

[Vereth]

Habe ich es nun richtig verstanden, dass für "struct Knot" (Die Struktur, wo die Zahlen und die Pointer des Vorgängers und des Nachfolgers, abgespeichert werden) erst einmal für ein Element des Tpys Knot Speicherplatz aus dem Heap reserviert werden muss?

Richtig, und genau das tut malloc/calloc. Und das tust du dann jedesmal, wenn eine neue Zahl eingegeben wurde. Den Zeiger musst du natürlich in einer Zwischenvariablen speichern.
Du solltest dir aber auch die Mühe machen, den Speicherplatz am Ende des Programms mit free wieder freizugeben.

Wenn ich dann eine weitere Zahl zur Liste hinzufüge, muss der Speicherplatz um einmal der Größe Knot anwachsen?

Auch richtig. Du machst dir mit malloc einen neuen Knoten, und dadurch wächst automatisch der Speicher, den dein Programm zur Datenspeicherung verwenden kann, um genau den Betrag, den du benötigst.

Und die so erstellten Knoten kann ich dann untereinander verschachteln?

Ich glaube, du meinst das richtige, aber Verschachteln ist das falsche Wort. Verketten nent man das. Das tust du, nachdem du im Knoten die Eingabe gespeichert hast. Du hängst dann den Knoten an den Anfang oder das Ende der Liste. Wie das gemacht wird, hat deepthroat schon geschildert. hier ist noch einmal die stilistisch aufbereitete Version:

Um ein Element an den Anfang der Liste anzuhängen mußt du

1. einen neuen Knoten dynamisch anlegen, nennen wir ihn knt
2. - den Eingabewert in n speichern
3. - den Vorgänger von knt auf 0 setzen
4. - den Nachfolger von knt auf 0 setzen
5. wenn die Liste nicht leer ist, dann
6. - den Vorgänger des ersten Elementes der Liste auf knt setzen.
7. - den Nachfolger von knt auf den Anfang der Liste setzen
8. - den Anfang der Liste auf knt setzen
9. wenn die Liste leer ist, dann
10. - den Anfang der Liste auf knt setzen
11. - das Ende der Liste auf knt setzen

Das Vorgehen kann man noch verfeinern, aber mache es erstmal so, wie es oben beschrieben wurde. Sobald du den Knoten in die Liste eingefügt hast, brauchst du den Wert deiner temporären Zeigervariable nicht mehr, du kannst ihn also im nächsten Schleifendurchlauf überschreiben. Einen Datenverlust brauchst du nicht zu befürchten, weil der Knoten in der Liste hängt. Was du überschreibt, ist nur der Zeiger auf einen Knoten, nicht der Knoten selbst; genau dafür sind Zeigervariablen gemacht worden (unter anderem).

Sobald du das Erstellen der Liste geschaft hast, können wir über den Rest der Aufgabe und die oben erwähnte Verfeinerung reden.

 

[Cherrycoke]

So, ich habe mich jetzt noch einmal an der Aufgabe versucht:

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

typedef struct Knot* KnotPtr;

typedef struct Knot{
	int n;
	KnotPtr vorg;
	KnotPtr nachf;
} Knoten;

typedef struct{
	KnotPtr anfang;
	KnotPtr ende;
} DVListe;

/* Bis hier hin ist das Programm vorgegeben */

int eingabeanzahl, zahl;
int i = 0;

int main (void){

	/* DVListe liste erstellen */
	DVListe liste = {0, 0};

	/* Knoten knt dynamisch anlegen */
	Knoten knt = (*Knoten) malloc(0);
		
	/* Einlesen endet erst wenn eine 0 eingegeben wurde*/
	while (zahl != 0){

	/* Speicherplatz aus dem Heap für eingegebene Zahlen * Groesse knt reservieren */
	knt = (*Knoten) realloc(knt, (sizeof(knt)+sizeof(Knoten)));

		/* Den Eingabewert in n speichern */
		printf("Zahl eingeben (0 fuer Ende): ");
		scanf("%d", &zahl);
		(knt+i)->n = zahl;
		/* Vorgaenger von knt auf 0 setzen */
		(knt+i)->vorg = 0;
		/* Nachfolger von knt auf 0 setzen */
		(knt+i)->nachf = 0;
		
	
		/* wenn die Liste nicht leer ist... */
		if (liste != {0, 0}){
			/* den Vorgaenger des ersten Elementes der Liste auf knt setzen */
			(knt+(i-1))->vorg = knt[i];
			/* den Nachfolger von knt setzen */
			(knt+i)->nachf = knt[i-1]
			
			/* den Anfang der Liste auf knt setzen */
			liste->anfang = knt[i]:
		}
		/* wenn die Liste leer ist... */
		else{
			/* den Anfang der Liste auf knt setzen */
			liste->anfang = knt[i]);
			/* das Ende der Liste auf knt setzen */
			liste->ende = knt[i];
		}

		i += 1;
	}
	
	return 0;
	free(knt);


}

Dieses Programm sollte eigentlich eine Zahl vorne an die Liste anhängen. Leider kann ich es im Moment nicht kompilieren. Bin erst wieder heute Abend an meinem Rechner. Hoffentlich liege ich nun nicht all zu falsch mit dem Programm.

 

[deepthroat]

Hi.

So, ich habe mich jetzt noch einmal an der Aufgabe versucht:

Leider wieder nicht wirklich mit Erfolg. :-(

	/* Knoten knt dynamisch anlegen */
	Knoten knt = (*Knoten) malloc(0);

Was soll das? Das hatten wir doch x-mal besprochen wie das aussehen muss? Erstens passen die Typen nicht - du kannst nicht einen Zeiger an einen Nicht-Zeiger zuweisen, und wieso versuchst du 0 Byte zu allozieren?

Knoten* knt = malloc(sizeof(Knoten));

	/* Speicherplatz aus dem Heap für eingegebene Zahlen * Groesse knt reservieren */
	knt = (*Knoten) realloc(knt, (sizeof(knt)+sizeof(Knoten)));

Warum?

Vergiss doch mal deine Arrays und streiche das Wort realloc aus deinem Wortschatz.

Du mußt doch wirklich nur einen neuen Knoten erstellen und diesen dann an die Liste hängen. Die Knoten mußt du nicht in einem Array verwalten!

Schreibe dir dazu am besten Funktionen. Wenn du alles in die Hauptfunktion klatschst siehst du nicht mehr durch.

Um zu prüfen ob die Liste leer ist, schreibe dir eine Funktion!

int dvlist_is_empty(DVListe* liste) {
  ... // gibt TRUE zurück, wenn liste leer ist, FALSE anderenfalls.
}

Eine Liste ist leer, wenn sie keine Knoten enthält, also wenn anfang == NULL bzw. Ende == NULL ist.

Dieses ganze (knt+i) und knt[i+1] Zeug kannst du komplett streichen.

Gruß

 

[Cherrycoke]

Hi.
Leider wieder nicht wirklich mit Erfolg. :-(

Hmm, so langsam glaube ich einfach, dass ich zu doof für diese Sache bin.

Was soll das? Das hatten wir doch x-mal besprochen wie das aussehen muss? Erstens passen die Typen nicht - du kannst nicht einen Zeiger an einen Nicht-Zeiger zuweisen, und wieso versuchst du 0 Byte zu allozieren?

Knoten* knt = malloc(sizeof(Knoten));

Warum?

Okay, es sah merkwürdig aus. Aber ich habe erst mal 0 Byte alloziert, damit ich innerhalb der Schleife die Funktion realloc ausführen kann. Aber ich beginne jetzt noch einmal von ganz vorne. Damit ihr versteht, warum ich denke, dass hier ein Array her müsste.

Ich gebe in meinem Programm eine Zahl ein. Diese muss dann in einem Knoten (mit int n, vorg, und nachf) gespeichert werden. Sobald ich eine Zahl eingebe, brauche ich einen Knoten. Gebe ich eine zweite Zahl ein, brauche ich einen zweiten Knoten. Du hast dazu ja auch geschrieben:

Um einen Knoten zur Liste hinzuzufügen brauchst du natürlich einen neuen Knoten und somit natürlich auch Speicherplatz für diesen einen, neuen Knoten.

Macht denn ein Array nicht genau das? Ich brauche doch immer wieder einen neuen Knoten. Ob ich bei zwei Zahlen zwei Knoten die Knotan a und Knoten b habe, oder einen Array mit Knoten[0] und Knoten[1], dürfte doch egal sein. Was habe ich hier falsch verstanden?

Vergiss doch mal deine Arrays und streiche das Wort realloc aus deinem Wortschatz.

Geht klar! Bei unseren alten Prüfungen, die ich momentan durcharbeite, wird die dynamische Speicherverwaltung immer genau vor den doppelt verketteten Listen abgefragt. Von daher vermische ich das wohl gerne.

Du mußt doch wirklich nur einen neuen Knoten erstellen und diesen dann an die Liste hängen. Die Knoten mußt du nicht in einem Array verwalten!

Okay, ich habe zwar nicht verstanden, wo der Unterschied dazu liegt, ob ich hundert einzelne Knoten habe, oder einen Array, der hundert Knoten beinhaltet, aber ich glaube es dir jetzt einfach einmal. Aber ich habe es richtig verstanden, dass bei 100 eingegebene Zahlen, ich auch hundert Knoten habe, oder?

Ich werde mich gleich nochmal an einen neuen Versuch wagen. Danke für deine Geduld mit mir! :-D

 

[deepthroat]

Okay, es sah merkwürdig aus. Aber ich habe erst mal 0 Byte alloziert, damit ich innerhalb der Schleife die Funktion realloc ausführen kann.

Was du aber auch einfach durch

Knoten* knt = NULL;

hättest erreichen können.

Ich gebe in meinem Programm eine Zahl ein. Diese muss dann in einem Knoten (mit int n, vorg, und nachf) gespeichert werden. Sobald ich eine Zahl eingebe, brauche ich einen Knoten. Gebe ich eine zweite Zahl ein, brauche ich einen zweiten Knoten. Du hast dazu ja auch geschrieben:

Um einen Knoten zur Liste hinzuzufügen brauchst du natürlich einen neuen Knoten und somit natürlich auch Speicherplatz für diesen einen, neuen Knoten.

Ja, allerdings hatte ich auch extra betont, das du nur Speicher für 1 Knoten zusätzlich allozieren mußt, und nicht irgendwie Speicher für n Knoten (re)allozieren mußt.

Macht denn ein Array nicht genau das?

Wenn du damit ein Array der Länge 1 meinst, dann ja. Ansonsten: nein.

Ich brauche doch immer wieder einen neuen Knoten. Ob ich bei zwei Zahlen zwei Knoten die Knotan a und Knoten b habe, oder einen Array mit Knoten[0] und Knoten[1], dürfte doch egal sein. Was habe ich hier falsch verstanden?

Arrays und Listen sind beides Datenstrukturen die sich im Grunde gegenseitig ausschließen. Wenn man ein Array hat, braucht man keine Liste und umgekehrt. Ein Array ist für diese Aufgabe eben nicht geeignet weil man nicht weiß wieviele Elemente eingeben werden und es ineffizient ist Elemente an ein Array anzuhängen.

Okay, ich habe zwar nicht verstanden, wo der Unterschied dazu liegt, ob ich hundert einzelne Knoten habe, oder einen Array, der hundert Knoten beinhaltet, aber ich glaube es dir jetzt einfach einmal. Aber ich habe es richtig verstanden, dass bei 100 eingegebene Zahlen, ich auch hundert Knoten habe, oder?

Ja, natürlich.

Gruß

 

[Cherrycoke]

Ok, nun ist mir so langsam ein Licht aufgegangen und ich denke, dass ich den Dreh heraus habe. Ich habe jetzt erst einmal ein Programm geschrieben, dass eine eingegebene Zahl vorne an eine Liste anhängt. Das ist dabei herum gekommen:

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

typedef struct Knot* KnotPtr;

typedef struct Knot{
	int n;
	KnotPtr vorg;
	KnotPtr nachf;
} Knoten;

typedef struct{
	KnotPtr anfang;
	KnotPtr ende;
} DVListe;

/* Bis hier hin ist das Programm vorgegeben */

/* Gibt 1 (true) zurück, wenn liste leer ist, 0 (false) anderenfalls. */
int dvlist_is_empty(DVListe* liste) {
  if (liste->anfang == NULL && liste->ende == NULL){
  	return 1;
  }
  else{
  	return 0;
  } 
}

/* Gibt eine Liste aus */
void print_all(DVListe* liste){
	KnotPtr anfang = liste->anfang;
	while (anfang != NULL){
		printf("%d ", anfang->n);
		anfang = anfang->nachf;
	}

}



int main (void){

	/* Variablendeklertaion */
	int eingabe = 1;
	DVListe liste = {0, 0};
	KnotPtr node;
	
	while (eingabe != 0){
		/* Ein- und Ausgabe */
		printf("Bitte eine Zahl eingeben (0 zum beenden): ");
		scanf("%d", &eingabe);
		if (eingabe == 0){
			break;
		}

		/* Einen neuen Knoten node anlegen */
		node = malloc(sizeof(Knoten));
		/* Den Eingabewert in n speichern */
		node->n = eingabe;
		/* Den Vorgänger von node auf 0 setzen */
		node->vorg = 0;
		/* Den Nachfolger von knt auf 0 setzen */
		node->nachf = 0;
	
		if (dvlist_is_empty(&liste)){
			/* Die Liste ist leer */
			/* den Anfang der Liste auf node setzen */
			liste.anfang = node;
			/* Das Ender der Liste auf node setzen */
			liste.ende = node;
		}
		else{
			/* Die Liste ist nicht leer */
			Knoten* erstes_element = liste.anfang;
			/* Den Vorgaenger des ersten Elementes der Liste auf node setzen. */
			erstes_element->vorg = node;
			/* Den Nachfolger von node auf den Anfang der Liste setzen */
			node->nachf = liste.anfang;
			/* Den Anfang der Liste auf node setzen */
			liste.anfang = node;
		}
	}

	print_all(&liste);
}

Hat jemand noch Verbesserungsvorschläge? Stimmt das denn nun? Das Programm gibt immerhin das aus, was es soll.

Ich danke euch noch einmal für eure Geduld mit mir!

 

[deepthroat]

Hi.

Hat jemand noch Verbesserungsvorschläge?

Nur ein paar kleine...

Warum nicht einfach so:

* Gibt true zurück, wenn liste leer ist, false anderenfalls. */
int dvlist_is_empty(DVListe* liste) {
  return (liste->anfang == NULL); // wenn die Liste keinen Anfang hat, hat sie auch kein Ende
}

Und man kann - egal ob die Liste nun leer ist oder nicht - den Nachfolger des neuen Knotens immer auf liste.anfang setzen.

Stimmt das denn nun? Das Programm gibt immerhin das aus, was es soll.

Ja, das sieht jetzt schon sehr gut aus. Und es war doch eigentlich viel einfacher als du es anfangs mit den Arrays irgendwie implementieren wolltest, oder?!

Gruß