Verständnisproblem mit einfach verketteter Liste

[eey]

Ja eben, das ist ja was ich nicht verstehe. Wenn ich da aber NULL reinschreibe, dann stürzt der Compiler Wortlos ab.

[DirkB]

Du packst die neuen Elemente immer vor das bestehende.

Dadurch ist allerdings das root=ptr; in newNode nutzlos, da es auf das lokale root wirkt.

[eey]

Oh ok, jetzt ist mir das klar geworden. Ich schreib die neuen Elemente also immer an den Listenanfang.
Naja, eigentlich schwebt mir eher eine Liste vor, bei der ich an das ENDE die neuen Elemente anhänge.
Ich hab es mal so probiert, aber leider funktioniert es nicht wie es soll.

Hier erst mal der Quellcode:

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

typedef struct elem_t elTyp;

struct elem_t 
{
	elTyp *next;
	double Messwert;
	int Anz;
};

elTyp * newNode(elTyp *, double);
int ListAus(elTyp *);
elTyp * GetLast(elTyp *);

int main(void)
{
	char c;
	elTyp *root=NULL;
	elTyp *ptr=NULL;
	double Messwert;

	while(c!='E' && c!='e')
	{
		printf("Waehlen Sie einen Menuepunkt:\n\n");
		printf("(1) Neues Listenelement erstellen\t(2) Liste ausgeben\n");
		printf("(3) Listenelement loeschen\t\t(4) Listenelement bearbeiten\n");
		printf("(5) Mittelwert bilden\t\t\t(E) Exit\n\n");

		printf("Ihre Auswahl: ");
		do
		{
			c=getchar();
		}while(c=='\n');

		switch(c)
		{
		case '1':	printf("Bitte geben Sie einen Wert ein: ");
					scanf("%lf",&Messwert);
					root=GetLast(root);
					root=newNode(root, Messwert);
					system("cls");
					break;
		case '2':	printf("Ihre Liste lautet: \n");
					ListAus(root);
					system("pause");
					system("cls");
					break;
		case '3':	printf("drei\n\n");
					break;
		case '4':	printf("vier\n\n");
					break;
		case '5':	printf("fuenf\n\n");
					break;
		default:	if(c!='E' && c!='e')
						printf("Fehlerhafte Eingabe!\n\n");
					else
						printf("Programm wird beendet.\n\n");
					break;

		}
	}
}

elTyp * newNode(elTyp *root, double Messwert)
{
	elTyp *ptr;

	ptr=malloc(sizeof(elTyp));

	ptr->Messwert=Messwert;
	ptr->next=NULL;

	return ptr;
}

int ListAus(elTyp *root)
{
	if(root!=NULL)
	{
		elTyp *ptr;
		ptr=root;

		while(ptr!=NULL)
		{
			printf("%10.2lf\n",ptr->Messwert);
			ptr=ptr->next;
		}
		printf("\n");

		return 0;
	}
	else
	{
		printf("Fehler! Es wurde noch keine Liste erstellt!\n");
		return -1;
	}
}

elTyp * GetLast(elTyp *root)
{

	if(root==NULL)
	{
		return NULL;
	}
	else
	{

		while(root->next!=NULL)
			root=root->next;
		return root;
	}
}

Ich hab jetzt eben die Funktion GetLast() geschrieben, die mir den Zeiger auf das letzte Element liefern soll.
Dieses letzte Element gebe ich jetzt in newNode(), welches ich jetzt dahingehend modifiziert habe dass der next
Zeiger auf NULL zeigt, da das neue Element ja jetzt am Listenende eingefügt wird.

Problem: Ich bekomme immer nur den zuletzt eingegebenen Wert ausgegeben... Ich kann aber meinen Fehler nicht finden,
stimmt die Funktion GetLast() so oder ist die schon falsch?

[DirkB]

Da fehlt noch ein root->next = ptr; in newNode() (du willst ja verketten )

Wenn du vorher noch ptr->netxt = root->next; und dann erst root->next = ptr; kannst du auch Elemente einfügen.

[eey]

Hm, ok danke schonmal für die Antwort. Hab mein newNode() jetzt so formuliert:

elTyp * newNode(elTyp *root, double Messwert)
{
	elTyp *ptr;

	ptr=malloc(sizeof(elTyp));

	ptr->Messwert=Messwert;
	ptr->next=root->next;
	root->next=ptr;

	return ptr;
}

Leider stürzt der Compiler einfach ab, also irgendwas stimmt noch nicht.
Root->next ist ja durch die Zuweisung in main bereits ptr, deswegen hat man ja so
eine endlos Schleife, oder nicht?

[DirkB]

Sorry, in main hatte ich jetzt nicht geschaut.

root muss immer auf das erste Element der Liste zeigen, sonst hast du den Anfang verloren.
Aus main

case '1':    printf("Bitte geben Sie einen Wert ein: ");
                    scanf("%lf",&Messwert);
                    ptr=GetLast(root);    // root darf nicht mehr verändert werden
                    ptr=newNode(ptr, Messwert);
                    if(root == NULL) root = ptr;  // es sei denn es ist NULL
                    system("cls");
                    break;

und

elTyp * newNode(elTyp *root, double Messwert)
{
    elTyp *ptr;

    ptr=malloc(sizeof(elTyp));

// !! Hier fehlt die Fehlerprüfung ob ptr != NULL !!

    ptr->Messwert=Messwert;
    if(root != NULL) {
      ptr->next=root->next;
      root->next=ptr;
    } else {
      ptr->next= NULL;
    }   

    return ptr;
}

[eey]

Ok, es funktioniert jetzt, aber verstehen tu ich es noch nicht...

Also mal angenommen die Liste hat bereits 3 Elemente und ich will ein viertes hinzufügen. Dann läuft
das doch nach dem Code folgendermaßen ab:

1.) In ptr wird das letzte Element der Liste, also das dritte gespeichert.
2.) Ptr zeigt per Funktionsaufruf newNode() auf das nächste Element, also das vierte.
3.) In newNode() wird das vierte Element per malloc() erschaffen, das dritte zeigt auf es.
4.) Da root!=NULL (sprich: Es sind bereits Listenelemente vorhanden) ist werden in newNode
folgende Zuweisungen durchgeführt:
5.) Das vierte Element soll auf root->next zeigen, also auf das erste Element. Warum das??
Es sollte doch auf NULL zeigen, oder?
6.) Root->next soll auf ptr zeigen, also auf das 4te Element, auch das versteh ich nicht,
root soll doch immer auf das erste Element zeigen, oder?

Puh, ganz schön kompliziert das alles

EDIT: Vor allem diese Zeile versteh ich nicht:

root->next=ptr;

Wozu brauch ich das? Denn ich gebe doch ptr zurück und nicht root, wieso hat das überhaupt eine Auswirkung?

[D-U-D-E]

Jap, deine letzten beiden Punkte sind berechigte Einwände. Aber das waren deine Codeänderungen wenn ich mich nicht irre.

Prinzipiell sollte der Ablauf ungefähr so sein.
Einfügen:
1. Wenn die Liste noch leer ist, erstelle neues Element und setze es als root.
2. Ist die Liste nicht leer, erstelle ein Element und hänge es hinten dran. Also
a) Such das letzte Element der Liste
b) Erstell ein neues Element (setze den Nachfolger richtig!)
c) Biege den Nachfolger des letzten Elements auf das neue um.

Ach, und vergiss nicht das free() irgendwann einzupacken

eey schrieb:

EDIT: Vor allem diese Zeile versteh ich nicht:

root->next=ptr;

Wozu brauch ich das? Denn ich gebe doch ptr zurück und nicht root, wieso hat das überhaupt eine Auswirkung?

Weil der Nachfolger des übergebenen Knotens (der hier bei dir root heisst) auf den neuen Knoten (ptr) zeigen soll, oder? Dadurch entsteht ja erst die verkettete Liste.

eey schrieb:

6.) Root->next soll auf ptr zeigen, also auf das 4te Element, auch das versteh ich nicht,
root soll doch immer auf das erste Element zeigen, oder?

root ist hier der Name des übergebenen Knotens an den der neue Knoten drangehängt werden soll. Der Name ist unglücklich gewählt, node oder element wären mit Sicherheit nicht so irreführend.

eey schrieb:

5.) Das vierte Element soll auf root->next zeigen, also auf das erste Element. Warum das??
Es sollte doch auf NULL zeigen, oder?

Du kannst auf diese Art Elemente einfügen (mitten in der Liste) und nicht nur an das Ende der Liste dranhängen. Was passiert in dieser Zeile genau? Der neue Knoten übernimmt den Nachfolger von root als seinen eigenen Nachfolger, während root den neuen Knoten als Nachfolger nimmt. Mal dir am besten auf Papier auf, was da genau passiert.

[DirkB]

Du verwechselst das root aus main mit dem root aus newNode(). Die haben nichts miteinander zu tun. Benenne das root aus newNode() doch in wurzel um.

1.) In ptr wird das letzte Element der Liste, also das dritte gespeichert.
2.) Ptr zeigt nach Funktionsaufruf newNode() auf das nächste Element, also das vierte.
3.) In newNode() wird das vierte Element per malloc() erschaffen, das dritte zeigt auf es. noch nicht
4.) Da root!=NULL root ist in diesem Fall der Zeiger auf das dritte Element(sprich: Es sind bereits Listenelemente vorhanden) ist werden in newNode folgende Zuweisungen durchgeführt:
5.) Das vierte Element soll auf root->next zeigen, also auf das erste Element. Warum das?? Es sollte doch auf NULL zeigen, oder? wenn root das bisherige letzte Elemnt war, ist root->next == NULL
6.) Root->next soll auf ptr zeigen, also auf das 4te Element, auch das versteh ich nicht, root soll doch immer auf das erste Element zeigen, oder?
**root aus main ja, root aus newNode() zeigt auf das Element nach dem das neue angehängt wird
**

[eey]

Oh mann genial, ich habs kapiert!

Vielen lieben Dank , allein hätt ich das wohl nicht hingekriegt.

Ja, die Namen waren allerdings sehr unglücklich gewählt, das hat noch zusätzlich
für Verwirrung gesorgt

Aber jetzt hab ichs ja, hab die auch umbenannt, mein newNode() sieht jetzt so aus:

elTyp * newNode(elTyp *ptr, double Messwert)
{
    elTyp *neu;

    neu=malloc(sizeof(elTyp));

    neu->Messwert=Messwert;
    if(ptr != NULL) 
	{
		neu->next=ptr->next;
		ptr->next=neu;
    } 
	else 
	{
		neu->next= NULL;
    }  

    return neu;
}

Damit dürfte es in Zukunft keine Verwechslungen mehr geben