verkettete Liste - wie geht das?

baddestpoet

Hallo, ich hab vor einen einfachen Stack zu schreiben, also eine Liste, bei der ich neue Daten hinten anhängen kann und bei Bedarf auch ändern und das letzte Element löschen kann. Bisher bin ich aber nicht über die Initialisierung der Liste hinausgekommen, die Beispiele, die ich mir dazu bisher angesehen hab, entziehen sich bei mir jeglichen Verständnisses.

Bisher hab ich die Liste folgendermaßen initialisiert:

struct stack {
	double value; //Zahl
	struct stack *next; //nächstes Element
};

int main() {
struct stack *neu=NULL;
struct stack *kopf=NULL;
struct stack *aktuell=NULL;
...

Soweit hab ich das glaub ich auch verstanden, ich hab n Zeiger auf ein neues Element und einen für den Kopf, der noch auf NULL verweist - die Liste ist also leer.

Wenn ich jetzt mit folgendem Teil eine Zahl einlesen und diese in die Liste speichern will, wie muss ich dabie vorgehen? Ich verstehe schon, dass ich ein neues Element erstelle, den Zeiger vom Kopf auf dieses Element setze und den next Zeiger vom grad erstellten Element dann auf NULL, weil es das Ende ist. Aber wie schreib ich das??

printf("\n\nEingabe:");
scanf("%lf",z); //Zahl einlesen

if (kopf!=NULL) { //Liste nicht leer

  aktuell=kopf;
  while(aktuell->next!=NULL) {
    aktuell=aktuell->next; //Suche des letzten Elements
  }
  neu=(struct stack *)malloc(sizeof(struct stack));
  aktuell->next=neu; //Zeiger d. letzten Elements auf neues Element
  neu->next=NULL; //Zeiger d. neuen Elements aufs Ende
  aktuell->value=z; //Zahl einfuegen

  } else {
    //Liste leer
  }

Bin für jede Erklärung dankbar, die Sachen, die ich gefunden hab, sind mir einfach schon zu komplex.

EDIT: hab mal eingefügt, wie ich mir das mit dem hinten anhängen erklärt hab sowie einen Zeiger aufs aktuelle Element...

sieht doch schon ganz gut aus?

Nur den Zweck von

if (kopf!=NULL) { //Liste nicht leer

versteh ich nicht, vor dem eintragen der ersten Zahl wird die Liste natürlich immer leer sein...?

http://perlgeek.de/de/artikel/einfach-verkettete-listen
im Prinzip dein Beispiel

baddestpoet

Naja, ich hab das Drumherum weggelassen. Das Ganze kann halt mehrmals ausgeführt werden und je nachdem ob die Liste dann noch leer ist oder schon was drin steht muss halt was Anderes durchgeführt werden.

Mein komplettes Programm sieht momentan so aus:

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

struct stack {
  double value; // Zahl
  struct stack *next; // nächstes Element
};

int main(void) {

  struct stack *neu=NULL;
  struct stack *kopf=NULL;
  struct stack *aktuell=NULL;

  int anz=0; //zaehlt Anzahl der Elemente
  int i=4; //nimmt Art der Eingabe auf
  double z; //Zahleingabe
  char c, s[4]; //ein-/zweistellige Operationen

  printf("UPN RECHNER\n");
  printf("===========\n\n");

  while (i!=0) {
    while(i!=0 && i!=1 && i!=2 && i!=3) {
      printf("\nEingabe: Zahl(1)  einst. Op.(2)  zweist. Op. (3)  Ende(0)");
      scanf("%d", i);
    }

    if (i==1) { //Zahl auf stack packen
      printf("\nEingabe:");
      scanf("%lf",z); //Zahl einlesen

      if (kopf!=NULL) { //Liste nicht leer
        aktuell=kopf;
	while(aktuell->next!=NULL) {
	  aktuell=aktuell->next; //Suche des letzten Elements
        }
	neu=(struct stack *)malloc(sizeof(struct stack));
	aktuell->next=neu; //Zeiger d. letzten Elements auf neues Element
	neu->next=NULL; //Zeiger d. neuen Elements aufs Ende
	aktuell->value=z; //Zahl einfuegen

      } else { //Liste leer
	neu=(struct stack *)malloc(sizeof(struct stack));
	kopf=neu; //Zeiger auf dieses als erstes Element
	neu->next=NULL;	 //gleichzeitig auch letztes Element
	neu->value=z; //Zahl einfuegen
      }

    }

//EINSTELLIGE OPERATIONEN
    if (i==2) { 
      while (s!="abs" && s!="neg" && s!="inv" && s!="sqr" &&s !="sqrt") {
	gets(s);
      }

    if (kopf!=NULL) { //Liste nicht leer
      aktuell=kopf;
      while(aktuell->next!=NULL) {
      aktuell=aktuell->next; //Suche des letzten Elements
    }
    neu=(struct stack *)malloc(sizeof(struct stack));
    aktuell->next=neu; //Zeiger d. letzten Elements auf neues Element
    neu->next=NULL; //Zeiger d. neuen Elements aufs Ende

    if (s=="inv")
      aktuell->value=0-aktuell->value; //negative Zahl
    if (s=="abs")
      aktuell->value=fabs(aktuell->value); //Betrag
    if (s=="sqr")
      aktuell->value=pow(aktuell->value,2); //Quadrat
    if (s=="swrt")
      aktuell->value=sqrt(aktuell->value); //Quadratwurzel

    } else { //Liste leer
      printf("Es wurde noch keine Zahl eingegeben!");
    }			

  }

//ZWEISTELLIGE OPERATIONEN
  if (i==3) {
    while(c!='/' && c!='*' && c!='+' && c!='-') {
      printf("\nEingabe:");
      c=getchar();
    }
  }

  i=4;

  }
return 0;
}

Klappt das so auch für die leere Liste? So langsam hab ich das Gefühl durchzusteigen. Komischerweise krieg ich zwar keine Fehler vom Compiler (bloodshed auf Windows 7) angezeigt, aber nach der Eingabe einer Zahl stürzt das Programm ab!?

Danke für den link, den Artikel habe ich auch schonmal gefunden, aber die ganzen inserts, nodes und tmps haben mich ganz schön verwirrt.

EDIT: Ich hab jetzt mal meinen ganzen Quelltext reingehaun, vielleicht dient das mehr dem Verständnis. Die Menüführung funktioniert auch noch nicht so richtig, wenn jemand da einen Tipp hat, wär ich auch sehr erfreut

Außerdem hab ich noch keine Ahnung, wie ich es später schaffe, die letzten beiden Listenelemente rauszukriegen. Das letzte hat ja den next zeiger auf NULL, aber das vorletzte? Müsste ich da erst den Wert aus dem letzten auslesen, dieses dann löschen und dann nochmal nach dem letzten suchen?

Müsste ich da erst den Wert aus dem letzten auslesen, dieses dann löschen und dann nochmal nach dem letzten suchen?

das würde zwar gehen, würde aber auch deine Liste kaputt nach und nach löschen

um ein bestimmtes Element zu finden, könntest du ja in der

while(aktuell->next!=NULL) {

Schleife eine Zählervariable hochzählen lassen, wie oft du dich schon "weitergehangelt" hast bis du ans Ende gekommen bist.

Und dann die Schleife wieder durchgehen und diesmal zB nach 2 mal aufhören, statt erst wenn du das Ende erreicht hast.
Oder für das vorletzte Element eben Anzahl-1 Durchläufe.

Oder du kannst du dir ja auch in einer Variable merken wie viele Elemente in deiner Liste sind. Also bei jedem neuen Element anzahl++; und wenn du eins löscht dann anzahl--;

Oder du fügst deinem struct noch eine Variable int platz hinzu, die muss natürlich immer angepasst werden...
Oder ein Zeiger der auf das vorherige Element zeigt, das wäre dann eine doppelt verkette Liste.

Abstürzen kann dein Programm wenn Zeiger irgendwo falsch zeigen oder du versuchst in Speicher zu schreiben den du nicht reseviert hast.
Was genau da jetzt falsch ist, weiss ich nicht mir fehlt da gerade der Nerv das genauer zu untersuchen, sorry.
Aber ansich ist das durchaus gängig, dass der Code fehlerfrei kompiliert und das Programm dann crasht. Der Compiler guckt sich ja nur die Syntax an, Division durch 0 fällt so auch erst beim Ausführen auf.

baddestpoet

Ok, danke erstmal das werd ich mal ausprobieren!

Genmutant

while (s!="abs" && s!="neg" && s!="inv" && s!="sqr" &&s !="sqrt")

Sowas solltest du dringend mit strcmp lösen...
Der String "sqrt" würde übrigens nichtmal in dein s-Array passen, da das nur 4 Zeichen fasst.

Hi

Debug das ganze doch mal dan siehst du den Fehler.

greetz

hi

Und das geht schon garnicht !

if (s=="inv")
      aktuell->value=0-aktuell->value; //negative Zahl
    if (s=="abs")
      aktuell->value=fabs(aktuell->value); //Betrag
    if (s=="sqr")
      aktuell->value=pow(aktuell->value,2); //Quadrat
    if (s=="swrt")
      aktuell->value=sqrt(aktuell->value); //Quadratwurzel

vergleiche die strings mit strcmp oder ähnlichen funktionen!
Nach meinem wissen geht so ein verglich nicht in C.

greetz lowbyte

baddestpoet

Ohne Debugger kann ichs gar nich kompilieren, der gibt mir keine Fehler.

Und sqrt sind doch 4 Zeichen oder was??

Die strcmp Funktion kenn ich noch gar nich, danke für den Hinweis.
Wie geh ich denn jetzt vor, wenn ich eine ungültige Eingabe verhindern will? Die Eingabe auf die vier Werte zu überprüfen ist doch tierisch umständlich!?

Genmutant

Nein das sind 5. Du vergisst wohl die terminierende 0, die jeder String hat

baddestpoet

Ah ja, gut zu wissen...

Also die Menüabfrage sieht bei mir jetzt so aus:

while (bol==0) {
  gets(s);

  boo=strcmp (s, "abs");
  if(boo==0) bol=1;
  boo=strcmp(s, "neg");
  if(boo==0) bol=1;
  boo=strcmp(s, "inv");
  if(boo==0) bol=1;
  boo=strcmp(s, "sqr");
  if(boo==0) bol=1;
  boo=strcmp(s, "sqrt");
  if(boo==0) bol=1;
}

Geht das echt nich einfacher? Mit Strings zu arbeiten ist ja n ganz schöner Umstand in C

Genmutant

Wo hast du denn die StringCompare-Funktion her?
ANSI C ist das jedenfalls nicht... da wird wie gesagt die strcmp Funktion genutzt. Und die gibt 0 zurück, falls die Strings gleich sind.
Ausserdem musst du deine Strings, falls du sie direkt eingibst, eben mit "" umfassen.

baddestpoet

Achso, daran hab ich gar nicht gedacht, ich hatte weiter oben extra Strings angelegt, in die ich die Werte gespeichert hatte.

Die Funktion hab ich hier gefunden: http://home.fhtw-berlin.de/~junghans/cref/EXAMPLES/strcmp.c Aber da hab ich wohl das falsche übernommen

EDIT: Mittlerweile sieht es schon ganz gut aus, nur wenn ich zweimal nacheinander eine zweistellige Operation durchführen will, hängt sich das Programm auf... Ich pack mal den kompletten Quellcode hier rein, falls jemand die Muße hat, sich den mal anzugucken wär ich sehr dankbar

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

struct stack {
	double value; // Zahl
	struct stack *next; // nächstes Element
};

int main(void) {

	struct stack *neu=NULL;
	struct stack *kopf=NULL;
	struct stack *aktuell=NULL;

    int i, anz=0, boo=0, bol=0; //nimmt Art der Eingabe auf, Anzahl d. Elemente, StringComparison
	double z, a, erg; //Zahleingabe, zweistellige Operanden, Ergebnis
	char c='a',s[5]; //ein-/zweistellige Operationen

    printf("UPN RECHNER\n");
    printf("===========\n\n");

    while (i!=0) {
        printf("\n%d Elemente",anz); //Anzahl der vorhandenen Elemente

		if(anz!=0) { //Sicherung ob es überhaupt schon Elemente gibt
			aktuell=kopf;
			while(aktuell->next!=NULL) {
				aktuell=aktuell->next; //Suche des letzten Elements
			}
			printf("; aktuell letztes Element: %.3lf", aktuell->value); //Ausgabe des letzten Elements
		}

		while(i!=0 && i!=1 && i!=2 && i!=3) {
            printf("\nZahl(1)  einst. Op(2)  zweist. Op(3) Ende(0)");
            scanf("%d", &i);
		}

        if (i==1) { //Zahl auf stack packen
			printf("\nEingabe:");
			scanf("%lf",&z); //Zahl einlesen

			if (kopf!=NULL) { //Liste nicht leer
				anz=2;
				aktuell=kopf;
				while(aktuell->next!=NULL) {
					aktuell=aktuell->next; //Suche des letzten Elements
					anz++;
				}
				neu=(struct stack *)malloc(sizeof(struct stack));
				aktuell->next=neu; //Zeiger d. letzten Elements auf neues Element
				neu->next=NULL; //Zeiger d. neuen Elements aufs Ende
				neu->value=z; //Zahl einfuegen

			} else { //Liste leer
				neu=(struct stack *)malloc(sizeof(struct stack));
				kopf=neu; //Zeiger auf dieses als erstes Element
				neu->next=NULL;	 //gleichzeitig auch letztes Element
				neu->value=z; //Zahl einfuegen
				anz=1;
			}

		}

	//EINSTELLIGE OPERATIONEN
        if (i==2) { 
			if(anz!=0) {
				while (bol==0) {
					printf("Eingabe:");
					gets(s);

					boo=strcmp (s, "abs");
					if(boo==0) bol=1;
					boo=strcmp(s, "neg");
					if(boo==0) bol=1;
					boo=strcmp(s, "inv");
					if(boo==0) bol=1;
					boo=strcmp(s, "sqr");
					if(boo==0) bol=1;
					boo=strcmp(s, "sqrt");
					if(boo==0) bol=1;
				}
				bol=0;

				if (kopf!=NULL) { //Liste nicht leer
					aktuell=kopf;
					while(aktuell->next!=NULL) {
						aktuell=aktuell->next; //Suche des letzten Elements
					}

					boo = strcmp(s, "neg");
					if (boo==0) {
						aktuell->value=0-aktuell->value; //negative Zahl
					}
					boo = strcmp(s, "abs");
					if (boo==0) {
						aktuell->value=fabs(aktuell->value); //Betrag
					}	
					boo = strcmp(s, "sqr");
					if (boo==0) {
						aktuell->value=pow(aktuell->value,2); //Quadrat
					}
					boo = strcmp(s, "sqrt");
					if (boo==0) {
						aktuell->value=sqrt(aktuell->value); //Quadratwurzel
					}	
					boo = strcmp(s, "inv");
					if (boo==0) {
						aktuell->value=1/(aktuell->value); //Reziproke
					}
				}								
			} else { //Liste leer
				printf("\nEs wurde noch keine Zahl eingegeben!\n");
			}
        }

	//ZWEISTELLIGE OPERATIONEN
        if(i==3) {
			if(anz>1) {
				while(c!='/' && c!='*' && c!='+' && c!='-') {
					printf("\nEingabe:");
					c=getchar();
				} 

				i=1;
				aktuell=kopf;
				while(i!=anz-1) {
					aktuell=aktuell->next; //Suche des vorletzten Elements
					i++;
				}
				a=aktuell->value; //Wertauslesung
				aktuell=aktuell->next; 
				if(c=='/')  //Division
					erg=a/aktuell->value; 
				if(c=='*')  //Multiplikation
					erg=a*aktuell->value; 
				if(c=='-')  //Subtraktion
					erg=a-aktuell->value;
				if(c=='+')  //Addition
					erg=a+aktuell->value; 						
				aktuell=kopf;
				while(i!=anz-1) {
					aktuell=aktuell->next; //Suche des vorletzten Elements
					i++;
				}
				aktuell->value=erg; //Wertzuweisung
				aktuell->next=NULL; //löscht letztes Element
				anz--;
				c='a';
			} else {
				printf("\nEs sind nicht genuegend Elemente vorhanden!\n");
			}
		}

		if(i!=0){
			i=5;
		}
    }
	return 0;
}