Doppelt verkettete Listen

[Cherrycoke]

Hallo Community,

da ich mich gerade in einer Prüfungsvorbereitung befinde, versuche ich im Moment verschiedene Programme zu erstellen. Zur Zeit sitze ich an einem Programm zu doppelt verketteten structs.

Die Aufgabestellung lautet:

a ) Schreiben Sie ein vollständiges C-Programm, das ganze Zahlen einliest und das ausgibt, ob gleich viele positive und negative Zahlen eingegeben wurde, bzw welches Vorzeichen überwiegt.
b) Ergänzen Sie ihr Programm so, dass die Zahlen in einer doppelt verketteten Liste abgespeichert werden. Dabei sollen negative Zahlen am Anfang, positive am Ende eingefügt werden.

Der Aufgabenteil a) bereitet mir keine Schwierigkeiten. Zum Aufgabenteil b) ist folgender Quelltextausschnitt bereits vorgegeben.

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

Bei diesem Programm stehe ich leider total auf dem Schlauch. Es hagt bei mir schon in der ersten Zeile:

typedef struct Knot* KnotPtr;

Das bedeutet, dass ich anstelle "struct Knot*" auch "KnotPtr" schreiben könnte, oder? (nur zum Verständnis) Aber was genau macht "struct Knot*"?

Zum generellen Ablauf des Programms habe ich mir folgende Gedanken gemacht. Da ich nicht weiß, wie viele Zahlen eingegeben werden, muss ich den Speicher dynamisch zuweisen. Das heißt, das alle Zahlen in folgender Struktur abgespiechert werden.

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

Dazu erstelle ich erst einmal genügend Speicherplatz. D.h. mein Programm sieht bisher so aus:

int eingabeanzahl, zahl;

int main (void){
	printf("Zahl eingeben (0 fuer Ende):");
	scanf("%d", &zahl);
	eingabeanzahl = eingabeanzahl + 1;

	Knot = (Knoten *) calloc(eingabeanzahl, sizeof(Knoten));

}

Nun wird mir der Fehler ausgegeben, dass "Knot" nicht deklariert wurde.

Warum steht hier:

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

Ich kenne nur die Schreibweise ohne das "Knot". Was genau sagt denn dieser Codeblock aus?

Jedenfalls habe ich jetzt erst einmal mein Programm ergänzt:

int eingabeanzahl, zahl;

int main (void){
	printf("Zahl eingeben (0 fuer Ende):");
	scanf("%d", &zahl);
	eingabeanzahl = eingabeanzahl + 1;
       
       Knoten* Knot;

	Knot = (Knoten *) calloc(eingabeanzahl, sizeof(Knoten));

        Knot->n = zahl;
}

Aber wie geht es denn nun weiter? Ich habe auch noch gar keine Vorstellung, wie ich die negativen Zahlen an den Anfang schreibe. Mit "realloc()" kann ich den Speicherbereich ja vergrößern. Daher ist es auch kein Problem, eine Zahl anzuhängen. Aber wie füge ich negative Zahlen am Anfang hinzu?

So, jetzt habe ich mir meine GEdanken von der Seele geschrieben. Hoffentlich erschlage ich euch nicht damit. Eine kurze Hilfe wäre wirklich super!

Schon mal vielen, vielen Dank!

 

[deepthroat]

Hi.

typedef struct Knot* KnotPtr;

Das bedeutet, dass ich anstelle "struct Knot*" auch "KnotPtr" schreiben könnte, oder? (nur zum Verständnis)

Ja. KnotPtr ist ein Typ-Alias für "struct Knot*".

Aber was genau macht "struct Knot*"?

Es "macht" erstmal gar nichts. Es ist ein Zeiger auf eine Struktur namens Knot.

Dazu erstelle ich erst einmal genügend Speicherplatz.

Warum?
Ein doppelt verkettete Liste läßt sich doch dynamisch erweitern indem man vorne bzw. hinten ein Element dranhängt bzw. mittendrin ein Element einfügt. Da mußt du doch nicht wissen wieviel Elemente benötigt werden. Sonst hättest du ja auch gleich ein Array verwenden können...

D.h. mein Programm sieht bisher so aus:

int eingabeanzahl, zahl;

int main (void){
	printf("Zahl eingeben (0 fuer Ende):");
	scanf("%d", &zahl);
	eingabeanzahl = eingabeanzahl + 1;

	Knot = (Knoten *) calloc(eingabeanzahl, sizeof(Knoten));

}

Nun wird mir der Fehler ausgegeben, dass "Knot" nicht deklariert wurde.

Hast du ja auch nicht. In diesem Kontext müßte Knot eine Variable sein. Allerdings ist Knot so überhaupt nicht bekannt - weder als Typ, noch als Variable.

\edit: Du wolltest vermutlich sowas schreiben:

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

Warum steht hier:

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

Ich kenne nur die Schreibweise ohne das "Knot". Was genau sagt denn dieser Codeblock aus?

Es ist eine kürzere Schreibweise für

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

typedef struct Knot Knoten;

Dann müßtest du natürlich erstmal eine DVListe anlegen...

Gruß

 

[Cherrycoke]

Danke dir deepthroat, du hast mit ein Stück weiter geholfen. Auch was das Verständnis anbelangt. Am Anfang hatte ich die Aufgabe gar nicht verstanden.

Nun stehe ich aber vor folgendem Problem (Kommentare im Quelltext beachten):

/* Es sollen possitive Zahlen der Reihe nach eingelesen werden.
Am Ende soll ausgegeben werden, welche Vorzeichen ueberwiegen (und ob).
Es soll eine doppelt verkette Liste benutzt werden. Bei 0 als Eingabe
terminiert das Programm.*/

#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 main (void){

	/* Einlesen endet erst wenn eine 0 eingegeben wurde*/
	while (zahl != 0){

		/* Benutzereingabe */
		printf("Zahl eingeben (0 fuer Ende):");
		scanf("%d", &zahl);
		eingabeanzahl = eingabeanzahl + 1;

		/* wenn mehr Zahlen hinzukommen, wird realloc() angewand - unfertiger Quelltextabschnitt */
		DVListe* liste;
		liste = (DVListe *) calloc(eingabeanzahl, sizeof(DVListe));

		assert( liste != NULL );


		/* Unterscheiden an welcher Stelle possitive bzw. negative 
		Zahlen abgespeichert werden sollen */
		if (zahl > 0){
		
			/*
			*	Hier ist mein Problem! Die Zahl selbst wird in der Struktur Knot abgespeichert.
			*	Allerdings muss ich dem Programm noch mitteilen, dass es in der doppelt verketteten
			*	Liste positive Zahlen am Ende abspichert (und negative am Anfang).
			*	Ehrlich gesagt verstehe ich nicht ganz, was nun passieren muss.
			* 	Ich möchte in dem struct DVliste einen Wert in den Eintrag "ende" ablegen? 
			*/

		}
		else{
		
		}

	}


}

 

[deepthroat]

Danke dir deepthroat, du hast mit ein Stück weiter geholfen. Auch was das Verständnis anbelangt. Am Anfang hatte ich die Aufgabe gar nicht verstanden.

So ganz anscheinend aber noch nicht.

Warum willst du denn dort ein Array verwenden? Das ist doch unnötig.

void dvliste_prepend(DVListe* listp, int value) {
  // ...
}

int main(void) {
  DVListe liste = { 0, 0 };  // doppelt verkettete Liste -- leer.

  int i = ... // eingelesen

  if (i <  0) {
    dvliste_prepend(&liste, i);
  } else {
    dvliste_append(&liste, i);
  }
}

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

1. einen neuen Knoten dynamisch anlegen, nennen wir ihn n
2. wenn die Liste nicht leer ist, dann den Vorgänger des ersten Elementes der Liste auf n setzen.
3. den Nachfolger von n auf den Anfang der Liste setzen
4. den Vorgänger von n auf 0 setzen
5. wenn die Liste leer ist, den Anfang und das Ende der Liste auf n setzen, sonst nur den Anfang der Liste auf n setzen

Das Anhängen ans Ende der Liste ist analog.

Am besten malst du dir das mal auf wenn du es dir nicht vorstellen kannst.

Gruß

 

[Cherrycoke]

Entschuldigung, wenn ich mich gerade ein bisschen doof stelle, und die Aufgabe einfach nicht verstehen möchte.

einen neuen Knoten dynamisch anlegen, nennen wir ihn n

Ok, habe ich hoffentlich verstanden.

Wäre doch "n = (Knoten*) calloc(anzahlderzahlen, sizeof(Knoten));", oder? Dann hätte ich die Startadresse des Feldes mit der Länge anzahlderzahlen des Typs Knoten in der Variablen n abgespeichert?

wenn die Liste nicht leer ist, dann den Vorgänger des ersten Elementes der Liste auf n setzen.

Hier komme ich wieder nicht weiter. Sagen wir mal die Liste ist nicht leer und beinhaltet drei Elemente. Demnach habe ich zum Beispiel n[0]={1, {0], {&n[1]}}, n[1]={9, &n[0], {&n[2]}} und n[2]={35, {&n[1]}, {0}} belegt. Was wäre denn nun der Vorgänger des ersten Elementes? Ist mit dem ersten Element n[1] aus dem obigen Beispiel gemeint? Ich verstehe es einfach nicht, obwohl ich mir jetzt schon so lange Gedanken darüber gemacht habe. :'(

 

[deepthroat]

Wäre doch "n = (Knoten*) calloc(anzahlderzahlen, sizeof(Knoten));", oder? Dann hätte ich die Startadresse des Feldes mit der Länge anzahlderzahlen des Typs Knoten in der Variablen n abgespeichert?

Nein. Vergiss doch mal deine Felder.

n = malloc(sizeof(Knoten)); // Schritt 1)

Hier komme ich wieder nicht weiter. Sagen wir mal die Liste ist nicht leer und beinhaltet drei Elemente. Demnach habe ich zum Beispiel n[0]={1, {0], {&n[1]}}, n[1]={9, &n[0], {&n[2]}} und n[2]={35, {&n[1]}, {0}} belegt. Was wäre denn nun der Vorgänger des ersten Elementes?

Also deine Notation leuchtet mir jetzt gerade nicht ein.

An das erste Element der Liste kommst du doch über

liste->anfang

Jedes Element bzw. jeder Knoten in der Liste besitzt ja einen Vorgänger und Nachfolger. Für den ersten Knoten in der Liste ist der Vorgänger natürlich NULL.

Knoten* erstes_element = liste->anfang;

erstes_element->vorg = n; // Schritt 2)

Gruß

 

[Cherrycoke]

Hmm, offensichtlich fehlt es mir bei dieser Aufgabe schon am Grundverständnis. Daher habe ich mir mal erlaubt, die vorgegebene Strukturen zu visualisieren. Könnte mir jemand vielleicht sagen, ob ich schon bei diesem Schritt etwas falsch verstanden habe? Ich bin mir nämlich schon hier nicht sicher.

 

[deepthroat]

Hi.

Das sieht nun wieder eher so wie ein Binärbaum aus.

Ich hab versucht das mal auf die Schnelle zu visualisieren...

Gruß

 

[Cherrycoke]

Hey,

ich danke dir! 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? Wenn ich dann eine weitere Zahl zur Liste hinzufüge, muss der Speicherplatz um einmal der Größe Knot anwachsen? Und die so erstellten Knoten kann ich dann untereinander verschachteln?

Hoffentlich liege ich jetzt nicht all zu falsch. Sonst gebe ich es schlichtweg auf. :-(

 

[deepthroat]

Hey,

ich danke dir! 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? Wenn ich dann eine weitere Zahl zur Liste hinzufüge, muss der Speicherplatz um einmal der Größe Knot anwachsen?

Welcher Speicherplatz sollte denn da jetzt wachsen?

Du mußt doch wirklich nur einzelne Knoten erstellen (sprich: allozieren) und miteinander verknüpfen. Damit diese einzelnen Knoten nicht verloren gehen speicherst du dir in der DVListe einmal den Anfang und das Ende der Liste.

DVListe dvlist;

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

k1->nachf = k2;
k2->nachf = k3;

k3->vorg = k2;
k2->vorg = k1;

k1->vorg = NULL; // Knoten 1 hat keinen Vorgänger.
k3->nachf = NULL; // Knoten 3 hat keinen Nachfolger.

dvlist.anfang = k1;
dvlist.ende = k3;

\edit: Übungsaufgabe: Code ergänzen so das ein weiterer Knoten k4 an die Liste drangehängt wird.

Gruß