Doppelt verkettete Liste

fischldi

Hallo Communuty!

Ich soll eine doppelt verkettete Liste erstellen, leider bekommt ich mit diesem Quelltext lauter Fehlermeldungen.

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

/* Liste = Zeiger auf einen Knoten */
typedef struct Knot *Liste;

/* Knoten enthaelt eine eingelesene Zahl */
typedefstruct Knot{
			  int k; // gespeicherte Zahl
			  Liste vorg; // Vorgaenger des Knoten
			  Liste nachf; // Nachfolger des Knoten
			  }Knoten;

Liste list = NULL; // leere Liste		

/* Fuegt einen neuen Knoten am Anfang der doppelt verketteten Liste ein */
Liste einfuegen( Liste list, int k)
{
 	  //Speicher fuer neuen Knoten anfordern
 	  Liste node = (Liste) malloc(sizeof(Liste*));
 	  assert(node);

	   // Wert setzen
	   node->k = k;
	   //Nachfolger ist aktueller Anfang der Liste, Vorgaenger ist leer
	   node->nachf = list;
	   node->vorg = NULL;
	   // und andersrum: Neuer Knoten ist Vorgaenger des ersten Knotens der Liste
	   if(list != NULL) list -> vorg = node;
	   return node; 
	   }	  	  

int main()
{
int n_pos=0;
int zahl=0;
int summe=0;

do{
   	printf("Zahlen eingeben :    \n");
   	scanf("%d",&zahl);
   	list=einfuegen(list,zahl);
	summe=summe+zahl; 

	   }while(zahl != 0); // soll abbrechen wenn Zahl 0 ist

	 Liste node = list;
	 Liste letzter = NULL;

	 printf("Zahlen in umgekehrter Reihenfolge: \n");
	 while( node != NULL )
	 {
	  		printf("%d ",node->k);
	  		if(node->nachf != NULL) letzter = node->nachf; // nur merken fuer spaeter
			  node=node->nachf;
			  }   	
	 node=letzter;
	 printf("Zahlen in urspruenglicher Reihenfolge:  \n");
	 while(node != NULL)
	 {
	  			printf("%d ",node->k);
	  			node=node->vorg;
				  }
				  return 0;
	 }

z.b in dieser Zeile

node->k = k;

bekomme ich den Fehler " error: dereferencing pointer to incomplete type". Warum??

Viele Grüsse,

Caro

mngbd

Liegt wohl daran, dass node vom Typ Liste ist. Wahrscheinlich wolltest du stattdessen einen Liste * machen. Wenn du malloc() nicht castest, fällt das sicher noch stärker auf.

fischldi

Danke für Deinen Tipp!

mngbd

Und wenn du jetzt noch free() verwendest, kann man das Ding sogar ohne Sorgen ausführen.

Zunächst einmal Hallo Forum

Ich muss ebenfalls eine doppelt verkette Liste schreiben.

Das ganze ist etwas einfacher, wenn meine Struktur(Knoten) als global deklariert wird. Ich möchte allerdings den Datensatz in main deklarieren, aber dennoch mit malloc in einer Funktion elemenet_einfügen den Speicherplatz reservieren.

int main(void) {

    struct Knoten{..};
}

void element_einfuegen() {

    ptr = (struct Knoten *) malloc(sizeof(struct Knoten));
}

Könnt ihr mir da weiter helfen? Gibt es vielleicht eine Möglichkeit wie ich der element_einfuegen Funktion einfach nur den benötigten Speicherplatz von struct Knoten Mitteile?

greetz DrTurkelten

mngbd

DrTurkelten schrieb:

Ich möchte allerdings den Datensatz in main deklarieren, aber dennoch mit malloc in einer Funktion elemenet_einfügen den Speicherplatz reservieren.

Du willst die Struktur-Definition in der main-Funktion machen? Wenn ja, warum?

Man kann das sicher irgendwie über schreckliche globale Variablen machen, aber ich kann mir gerade keinen Fall vorstellen, in dem man das wollen könnte.

Ja genau, die Struktur-Definition soll in der main - Funktion sein. Ich wüsste nicht wo ich sie sonst machen sollte, außer eben global. Leider setzen sämtliche Programme, die ich bis jetzt gefunden habe zum Thema Listestruktur, alle die globale Lösung ein

In der Zwischenzeit habe noch ein weiteres Problem "entdeckt":
Wie kann ich in der ElementEinfuegen() einen struct Knoten *ptr definieren?
Die Definition der Struktur ist dort ja nicht bekannt.

greetz

mngbd

DrTurkelten schrieb:

Leider setzen sämtliche Programme, die ich bis jetzt gefunden habe zum Thema Listestruktur, alle die globale Lösung ein

Naja, wahrscheinlich wollen die alle den Struktur-Typen in mehreren Funktionen verwenden, und die Definition nicht in jede Funktion kopieren. Warum leider? Sind globale Typen etwas schlechtes?

DrTurkelten schrieb:

Wie kann ich in der ElementEinfuegen() einen struct Knoten *ptr definieren?
Die Definition der Struktur ist dort ja nicht bekannt.

Entweder du kopierst die Definition in jede Funktion, oder du machst es dir einfach und definierst nur einmal global am Anfang.

Hm, du hast recht.
Letztendlich habe ich ja keine globale Variable, sondern nur einen Globalen Typ definiert. Alles Klar, dann mach ich mich mal weiter an die Arbeit.

Vielen Dank erstmal

greetz

Hi, bin nun auf ein Problem gestoßen, welches ich noch nicht erklären kann.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include "Console.h"

#pragma warning(disable:4996)

//Definition Node
typedef struct Node {
	char cName[32],cVorname[32];
	struct Node *ptrPrev, *ptrNext;
}NODE;

NODE* newNode(NODE* ptrHook); //Funktion neuer Knoten
NODE* naviList(NODE* ptrNode); // Navigation durch Liste

int main(void) {
	int iMenue=0;
	NODE* ptrHook = NULL; //soll der Anker werden
	NODE *ptr = NULL; // zeigt auf neue Knoten

	/****Hauptmenue****/
	printf(	"Doppelt verkettete Listen\n\n"
			"(1) Neue Liste"
			"\n(2) Liste laden"
			"\n(3) Beenden");
	do { //Kntrl Menueeingabe
		setCursor(6,0);
		iMenue = getche()-48;
	}while((iMenue!=1)&&(iMenue!=2)&&(iMenue!=3));

	switch(iMenue) {
		case 1: // Neue Liste
				ptr = newNode(ptrHook); //ptr zeigt auf neuen Knoten
				do {					
					ptr = naviList(ptr);
				} while(ptr!=NULL);
		break;
	}

	printf("\n\n\n!!!!!!!!!!ENDE!!!!!!!!!!");
	getch();
	return 0;
}

NODE* newNode(NODE* ptrHook) {

	NODE* ptrTmp = NULL; //Dient um im else Bereich durch die Liste zu navigieren
	char cName[32], cVorname[32];

	//Daten abfragen
	cls();
	printf("Name     : ");
	scanf("%s", cName);
	printf("\nVorname  : ");
	scanf("%s", cVorname);

	//kontrolliert ob in Liste schon ein Knoten ist 
	if (ptrHook == NULL) {
		ptrHook = (NODE*) malloc(sizeof(NODE)); /* ptrHook zeigt auf neuen Knoten, da dieser ja der*/
												/* in diesem Fall (if) der erste ist */

		strcpy(ptrHook->cName,cName);
		strcpy(ptrHook->cVorname,cVorname);
		ptrHook->ptrNext  = NULL;
		ptrHook->ptrPrev  = NULL;

		return ptrHook;
	}
	else { /* Wenn es schon Knoten in der Liste gibt, dann       */ 
		   /* wird das Objekt an der richtigen Stelle eingefuegt */

		NODE* ptrNew = (NODE*) malloc(sizeof(NODE*));

		strcpy(ptrNew->cName,cName);
		strcpy(ptrNew->cVorname,cVorname);

		ptrTmp = ptrHook; //setzt ptrTmp auf Anfang

		while((ptrTmp->ptrNext != NULL)&& (ptrTmp->ptrNext->cName < ptrNew->cName)) 
		{
			ptrTmp = ptrTmp->ptrNext;
		}
		ptrNew->ptrNext             = ptrTmp->ptrNext;
		ptrNew->ptrPrev             = ptrTmp;
		ptrTmp->ptrNext          = ptrNew;
		if(ptrNew->ptrNext!=NULL) 
			ptrNew->ptrNext->ptrPrev    = ptrNew;

		return ptrNew;

	}

}

NODE* naviList(NODE* ptrNode) {
	int iSubMenue = 0,i=0;
	cls();
	//Anzeige Knoten
	printf("Name    : %s\n", ptrNode->cName);
	printf("Vorname : %s\n", ptrNode->cVorname);

	//Anzeige Submenue
	printf("\n\n(N)ext\n(P)revious\n(E)infuegen\n(B)eenden\n\n");

	do {
		fflush(stdin);
		switch(getche()) {

			// Neues Element einfuegen
			case 101: 
			case  69: newNode(ptrNode);
					  return ptrNode;
			break;

			// Next
			case  78:
			case 110: ptrNode = ptrNode->ptrNext;
					  return ptrNode;

			break;

			// Previous
			case  80:
			case 112: ptrNode = ptrNode->ptrPrev;
					  return ptrNode;

			break;

			// Beenden
			case  98: 
			case  66: return ptrNode;
			default : 
						setCursor(9,0);						
			break;
		}
	} while(i==0);
}

Mein Problem kommt in der newNode Funktion bei den Zeilen:

NODE* ptrNew = (NODE*) malloc(sizeof(NODE*));

		strcpy(ptrNew->cName,cName);

Und zwar, bei der dritten Eingabe eines Elementes, gibt mir malloc NULL zurück. Ich frage mich warum das so ist?

Ich hab jetzt den ganzen Code gepostet, damit ihr das compilieren könnt (stand in der ForumFAQ )

ps: beim hauptmenue NeueListe und dann, wenn Option sichtbar, e für Einfuegen

greetz

okok, bin endlich! darauf gekommen. Habe dummerweise als Speichergröße NODE* angegeben anstatt NODE. Trotzdem danke falls sich schon jemand die Mühe gemacht hat, das ganze zu kompilieren.

grreetz