✔ Wie funktionieren Doppelt verkettete Liste?

[Davicito]

Hallo...

ich bräuchte mal Eure Hilfe in Sachen "Doppelt verkettete Liste". Ich habe mir schon mal ein STruct in meiner Header-Datei angelegt mit Printfunktion und Einfügefunktion.

// Dieses Objekt legt die einzelnen Listenknoten für die doppelt verkettete Liste an
typedef struct 
{
	struct node* right; // Zeiger auf das Nachfolgerelement
	struct node* left;  // Zeiger auf das Vorgängerelement
	void* content;      // Für den Dateninhalt
	
} node;

node* init_Liste();

// Diese Funktion fügt einzelne Stings in die Liste ein
void anhaengen(node* list, void* neuer_String, void* (*get)(void*));

// Ausgabe aller Listenelemente
void print_all(node* list);

...nun will ich in einer weiteren Datei "Liste.c", zum Test ein Wort Hallo einfügen und anschließend ausgeben. Aber um das zu machen, weiß ich nicht, auf was ich die Zeiger in der Funktion "anhaengen" setzen muss. Da fehlt mir noch die passende verstäntliche Anleitung dazu. Im Internet bin ich bisher nicht so fündig geworden, Habe ich evetuell bei der Initialisierung schon Fehler gemacht? -> Compiler zeigt mir in init_Liste(){} und anhaengen(node* list, void* neuer_String, void* (*get)(void*)){} fehler an.

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

#include "Liste.h"

node* init_Liste()
{
	node* n = (node*) malloc(sizeof(node));
	n -> right = NULL;
	n -> left  = NULL;
	n -> content = NULL;
	n -> counter = -1;
	
	return n;
}
//************************************ Listenfunktionen ***********************************
void anhaengen(node* list, void* neuer_String, void* (*get)(void*))
{
	node* neu_Elem = (node*) malloc(sizeof(node)); // Seicher neuen Konoten besorgen 
	// Überprüfen, ob Speicher übergeben worden ist	
	if(neu_Elem == NULL)
	{
		printf("Listenelement konnte nicht angelegt werden, da kein Speicher vorhanden ist!");
		exit(1);
	}
	//String / Wort an die Funktion "copySting" übergeben, um Speicher für den Zeiger "content" zu besorgen
	void* tmp = get(neuer_String);
	//Speicher, in dem nun das Wort liegt, an content anfügen.	
	neu_Elem -> content    = tmp;
	// Zeiger neu setzten	
	neu_Elem -> left       = list -> left;
	neu_Elem -> right      = list -> right;
	list -> right          = NULL;	
	neu_Elem->right->left  = neu_Elem;  //Probleme mit den Zeigern - nicht klar
	neu_Elem -> counter++;

	return neu_Elem;
}

void print_all(node* list)
{
	node* kopf      = list;
	node* aktl_Elem = list; 

	printf("%s", kopf -> content);
	while(kopf != (aktl_Elem = aktl_Elem -> right))
	{
		printf("%s", aktl_Elem -> content);
		printf("\n");
	}
}
//***************************** Funktionen für Funktionsvariablen *************************
void* copyString(void* stringUebergabe)
{
	char* string = (char*) stringUebergabe;
	char* speicher = (char*) malloc(sizeof(strlen(string)+1));
	//Nach Speicher reservierung immer prüfen, ob auch Speicher vorhanden war!!
	if(speicher == NULL)
	{
		printf("Programm wurde beendet, da kein Speicher vorhanden ist!");
		return(EXIT_FAILURE);
	}
	strcpy(speicher, stringUebergabe);
	return speicher;	
}

//************************************** Main-Funktion *************************************
int main(int argc, char** argv[])
{
	node* kopf = init__Liste();
	node* aktl_Elem = kopf; 
	
	anhaengen(aktl_Elem, &"Hallo", copyString);
	print_all(aktl_Elem);
	
	return EXIT_SUCCESS;
}

Also es geht mir nur um das prinzip der Zeigersetzung wenn ich Wörter hinzufüge!

Lieben Dank im Voraus, Davicito.

 

[sheel]

Hi

Zuerst einmal: Zum malloc in der init-Funktion gehört auch irgendwo ein free...wo ist es denn?
Am besten noch eine delelete_Liste-Funktion (oder so ähnlich) machen, die wieder aufräumt.

Dann, die Funktion copyString...ist eigentlich in Ordnung, bis auf das malloc wieder...
Wenn du für jedes Einfügen einen String mit malloc anlegst, sollte dieser irgendwann am Schluss wieder gefreet werden. zB auch in der delelete_Liste-Funktion.

Für das malloc in anhaengen gilt das Gleiche. Jeder Knoten muss irgendwann wieder entfernt werden.

Im printAll solltest du vor dem ersten printf prüfen, ob kopf bzw. kopf->daten nicht NULL sind.
Wenn kopf==NULL: return
Wenn kopf->Daten==NULL: Kein erstes printf.
Die ...->daten==NULL-Prüfung kann auch in der Schleife nicht schaden.

Dann ist die Schleifenbedingung im printAll irgendwie seltsam.
Man sollte dann aufhören, wenn das Rechte NULL ist, und nicht wenn das Rechte gleich dem Aktuellen ist.

Und zum Kernproblem:

neu_Elem -> left       = list -> left;
neu_Elem -> right      = list -> right;
list -> right          = NULL;  
neu_Elem->right->left  = neu_Elem;  //Probleme mit den Zeigern - nicht klar
neu_Elem -> counter++;

Dieser Teil im anhaengen.
Ich vermute, du willst das Neue Element nach dem Übergebenen (list) einfügen?

Dann ist vom neuen Element aus gesehen:
Das Aktuelle links
Das (vorher) Rechte vom Aktuellen jetzt das Rechte vom neuen.

Vom Aktuellen aus ist das Rechte jetzt das Neue
Und vom zuvor Rechts-vom-Aktuellen das Linke ist jetzt nicht mehr das Aktuelle, sondern das Neue.

Verwirrt?
Hier:

neu_Elem -> left = list;
neu_Elem -> right = list -> right;
list -> right -> left = neu_Elem;
list -> right = neu_Elem;

Das ersetzt den obigen Codeteil.

Wozu die Zeile mit counter++ gut war, bin ich mir aber selber nicht ganz sicher...du hast im node doch gar kein counter!
Und wenn man die Elemente schon zählen will, muss man das nicht in jedem node machen.
Ein einziges Mal reicht vollkommen aus.

Gruß

 

[Davicito]

Hi sheel,

vielen lieben dank. Hab mit Deiner guten Hilfeleistung all meine compilerfehler weg bekommen. Ich hab nur noch in Zeile 96 ein Warnhinweiß vom Compiler wegen Typecarst, sodass ich die init_Liste() auf mein struct "node" umgecarstet habe und bekomme jetzt einen letztem Warnhinweiß, mit dem ich leider nichts anfangen kann!

"Liste.c:96:2: warning: implicit declaration of function 'init_Liste' "

Hast Du vielleicht noch eine Ahnung, was das sein kann?

hier nochmal der aktuelle code:

Liste.h

// Dieses Objekt legt die einzelnen Listenknoten für die doppelt verkettete Liste an
typedef struct node
{
	struct node* right; // Zeiger auf das Nachfolgerelement
	struct node* left;  // Zeiger auf das Vorgängerelement
	void* content;      // Für den Dateninhalt	
} node;

node* init_Liste();
// Diese Funktion fügt einzelne Stings in die Liste ein
node* anhaengen(node* list, void* neuer_String, void* (*get)(void*));

// Ausgabe aller Listenelemente
void print_all(node* list);

Liste.c

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

#include "Liste.h"

// Listeninitierung - Liste zeigt auf sich selbst!! (anfang- und ende-Zeiger überflüssig)
node* init_Liste()
{
	node* n = (node*) malloc(sizeof(node));
	n -> right   = n;
	n -> left    = n;
	n -> content = NULL;
		
	return n;
}

/*nodeList* start() 
{
	nodeList* anfang = NULL; 
	nodeList* ende   = NULL;
}*/
//************************************ Listenfunktionen ***********************************
node* anhaengen(node* list, void* neuer_String, void* (*get)(void*))
{
	node* neu_Elem = (node*) malloc(sizeof(node)); // Seicher neuen Konoten besorgen 
	// Überprüfen, ob Speicher übergeben worden ist	
	if(neu_Elem == NULL)
	{
		printf("Listenelement konnte nicht angelegt werden, da kein Speicher vorhanden ist!");
		exit(1);
	}
	//String / Wort an die Funktion "copySting" übergeben, um Speicher für den Zeiger "content" zu besorgen
	void* tmp = get(neuer_String);
	//Speicher, in dem nun das Wort liegt, an content anfügen.	
	neu_Elem -> content    = tmp;
	// Zeiger neu setzten	
	neu_Elem -> left       = list; 
	neu_Elem -> right      = list -> right;		
	list -> right-> left   = neu_Elem;  //Probleme mit den Zeigern - nicht klar
	list -> right          = neu_Elem;
	//neu_Elem -> counter++;
	

	/*if(ende == NULL)
	{
		ende = malloc(sizeof(node));
		if(ende == NULL)
		{	
			printf("Listenelement konnte nicht angelegt werden, da kein Speicher vorhanden ist!");
			exit(1);
		}
	}*/	

	return neu_Elem;
}

void print_all(node* list)
{
	node* kopf      = list;
	node* aktl_Elem = list; 
	
	if(kopf == NULL && kopf -> content == NULL)
	{
		return;
	}	
	else
	{
		printf("%s", (char*) kopf -> content);
		while(kopf != (aktl_Elem = aktl_Elem -> right))
		{
			printf("%s", (char*) aktl_Elem -> content);
			printf("\n");
		}
	}
}
//***************************** Funktionen für Funktionsvariablen *************************
void* copyString(void* stringUebergabe)
{
	char* string = (char*) stringUebergabe;
	char* speicher = (char*) malloc(sizeof(strlen(string)+1));
	//Nach Speicher reservierung immer prüfen, ob auch Speicher vorhanden war!!
	if(speicher == NULL)
	{
		printf("Programm wurde beendet, da kein Speicher vorhanden ist!");
		exit(1);
	}
	strcpy(speicher, stringUebergabe);
	return speicher;	
}

//************************************** Main-Funktion *************************************
int main(int argc, char *argv[])
{
		
	node* kopf = (node*) init__Liste();
	node* aktl_Elem = kopf; 
	
	anhaengen(aktl_Elem, &"Hallo", copyString);
	print_all(aktl_Elem);
	
	return EXIT_SUCCESS;
}

PS. mach Dir keine Sorgen, eine Freefunktion, die den Speicher wieder freigiebt schreibe ich noch... will erstmal eins nach dem Anderen machen ^^. Nach Beendigung räumt das OS sowieso hinter mir auf *g*.

 

[deepthroat]

Hi.

init_Liste
init__Liste

Gruß

PS: Es heißt "casten", nicht "carsten". Und Hinweis schreibt man immer noch mit einem s. Das ist ja schon grausam...

 

[Davicito]

Vielen dank für Deine Hilfe zum Thema Problemstellung, init_Liste.

Ich war wohl blind gewesen, dass ich das nicht gesehen habe *g*.

Den Rest hättest Du Dir sparen können****** Ich weiß nämlich nicht so recht, was Du Dir damit beweisen wolltest. Aber ich danke Dir vielmals für Deine nicht konstruktiven Korrekturen meiner Rechtschreibung. Ich glaube jedoch jeder konnte mich sehr gut verstehen! Vielleicht solltest Du damit Geld verdienen, im Forum eine Rechtschreibprüfung als Serviceleistung anzubieten, dann komme ich noch mal darauf zurück, deepthroat.

Liebe Grüße, Davicito.