verkettete Listen

[klicke]

Hi,

ich hab mal wieder ein Problem an dem ich schon seit ein paar Tagen grüble.
Es geht um das Thema: "verkettete Listen"

Folgende Aufgabenstellung gibt es:
Schreiben Sie ein Programm das ein Menü bietet in dem man folgendes auswählen kann:
1.)eine Struktur hinten anhängen
2.)eine Struktur vorne anhängen
3.)eine Struktur löschen
4.)Ausgabe aller Strukturen auf dem Bildschirm

Ich hab mir überlegt,dass ich die einzelnen Teilabschnitte jeweils in einem Unterprogramm realisiere und diese dann im Hauptprogramm ausführe.
Desweiteren ist mir aufgefallen das es für die Punkte 1.) und 2.) jeweils 2 Fälle gibt:
- es besteht bereits eine Struktur
- man legt eine neue Struktur an

Programmierung:

Anmerkung: Ich werde den nachfolgenden Quelltext in ein paar Teilabschnitte zerlegen damit ich die Probleme die auftreten besser erklären kann.



#include<iostream>
using namespace std;
//Struktur wird definiert
struct buch
{
char name[75];
char autor[30];
char preis[7];
buch *next;
};


Das untenstehende Unterprogramm dient der Ausgabe wenn keine Struktur vorhanden ist.
Doch da tritt bereits das erste Problem auf,und zwar wenn ich das Projekt compiliere und ausführe passiert nichts....
Normalerweise sollte doch der start-Pointer wenn kein Element vorhanden ist,Null sein - oder?


void anhaengen(buch **start)
{

buch *p; //Hilfspointer
buch *h; //noch ein Hilfspointer
char auswahl;

if(*start ==NULL) //wenn Liste leer ist
{
*start=h;
cout<<"Name:";
cin>>(*h).name;
cout<<endl<<"Autor:";
cin>>(*h).autor;
cout<<endl<<"Preis:";
cin>>(*h).preis;
cout<<endl;

}

}




//Hauptprogramm
int main()
{
buch *start;

anhaengen(&start);

}


p.s: Ich habe versucht möglichst viel Schnick-Schnack im Quelltext zu entfernen um die Problemstellung so einfach als möglich zu halten.
Die anderen Punkte,wie das Löschen etc. hab ich auch derweil entfernt.

Vielen Dank für jede Hilfe!

mfg klicke

[locus vivendi]

Es geht um das Thema: "verkettete Listen"
Mal vorneweg: Hat euer Lehrer verboten std::list zu verwenden? Wenn nein, benutze es. (Oder hat er es nicht verboten, aber du glaubst es würde trotzdem Punktabzug geben?)


Folgende Aufgabenstellung gibt es:
Schreiben Sie ein Programm das ein Menü bietet in dem man folgendes auswählen kann:
1.)eine Struktur hinten anhängen
2.)eine Struktur vorne anhängen
3.)eine Struktur löschen
4.)Ausgabe aller Strukturen auf dem Bildschirm

Ich hab mir überlegt,dass ich die einzelnen Teilabschnitte jeweils in einem Unterprogramm realisiere und diese dann im Hauptprogramm ausführe.
Desweiteren ist mir aufgefallen das es für die Punkte 1.) und 2.) jeweils 2 Fälle gibt:
- es besteht bereits eine Struktur
- man legt eine neue Struktur an
Zum letzten Punkt lässt sich sagen, dass es auch den Fall gibt "Es besteht bereits eine Struktur und man legt eine neue Struktur an".


Das untenstehende Unterprogramm dient der Ausgabe wenn keine Struktur vorhanden ist.
Doch da tritt bereits das erste Problem auf,und zwar wenn ich das Projekt compiliere und ausführe passiert nichts....
Normalerweise sollte doch der start-Pointer wenn kein Element vorhanden ist,Null sein - oder? [Code weggelassen]
Nein. Pointer die auf dem Stack angelegt werden, werden nicht zwangsläufig automatisch initialisiert. Kleine Frage, hast du ein Buch zum lernen? Das ist eigentlich ein ganz grundlegendes Faktum. Für solche grundlegenden Dinge ist ein Forum eigentlich nicht so gut geeignet, denke ich.

[anda_skoa]

Mal vorneweg: Hat euer Lehrer verboten std::list zu verwenden? Wenn nein, benutze es. (Oder hat er es nicht verboten, aber du glaubst es würde trotzdem Punktabzug geben?)


Bei so etwas geht es immer darum, die Datenstrukturen selbst zu implementieren, damit man die Grundlagen versteht, wenn man mal fertige Container benutzt.



Nein. Pointer die auf dem Stack angelegt werden, werden nicht zwangsläufig automatisch initialisiert.

Korrekt, d.h.


buch* start = 0;


Ciao,
_

[klicke]

Mal vorneweg: Hat euer Lehrer verboten std::list zu verwenden? Wenn nein, benutze es. (Oder hat er es nicht verboten, aber du glaubst es würde trotzdem Punktabzug geben?)

Verboten ist es nicht,ich denke aber es würde Punkteabzug geben.



Zum letzten Punkt lässt sich sagen, dass es auch den Fall gibt "Es besteht bereits eine Struktur und man legt eine neue Struktur an".

Stimmt,den Fall gibt es auch - bin mir aber nicht sicher ob wir den Fall auch berücksichtigen sollen.Werd nächste Woche nachfragen ob der Fall auch zu berücksichtigen ist.



Nein. Pointer die auf dem Stack angelegt werden, werden nicht zwangsläufig automatisch initialisiert. Kleine Frage, hast du ein Buch zum lernen? Das ist eigentlich ein ganz grundlegendes Faktum. Für solche grundlegenden Dinge ist ein Forum eigentlich nicht so gut geeignet, denke ich.

Ich hab hier zwei Bücher,eines das ich von der Schule bekommen habe und eines was ich mir selbst zugelegt habe.

.)C++ Einführung und professionelle Programmierung - Ulrich Breymann
.)C++ Lernen und professionell anwenden Peter Prinz/Ulla Kirch Prinz

Doch in beiden Büchern konnte ich nicht wirklich viel informatives finden das mich auch weiterbringt.
Das Buch >>Lernen und professionell anwenden<< ist so aufgebaut,dass man es von Anfang an durchmacht,und die weiteren Kapitel auf den vorhergehenden aufbaut.zum Beispiel sagen mir die Begriffe "private" und "public" überhaupt nichts..

@anda_skoa:
Irgendwie werde ich nicht schlau,was mir das Nullsetzen des start-Pointers bringt(kann aber auch daran liegen,dass ich einen großen Denkfehler mache).

Der start-Pointer zeigt doch immer auf das erste Element in der Liste,oder?
Wenn ich demnach diesen start Pointer auf Null setze und ich vorher schon eine Liste besitze,dann hab ich doch diese verloren?!

Ich hoffe man versteht meine Problematik.

Ich hänge nochmal einen Code-Schnipsel an,wie ich mir das vorgestellt hätte:


void anhaengen(buch **start)
{

buch *p; //Hilfspointer
buch *h; //Hilfspointer 2
char auswahl;


if(*start !=NULL) //bei bestehender Liste
{
p=*start; //dem Hilfspointer p wird start zugewiesen

while((*p).next !=NULL) //solange bis man am Ende der Liste ist
{
p=(*p).next;
}
do{
h=(buch*)malloc(sizeof(buch)); //dyn. Speicherreservierung
//-------Daten einlesen-----------
cout<<"Name:";
cin>>(*h).name;
cout<<endl<<"Autor:";
cin>>(*h).autor;
cout<<endl<<"Preis:";
cin>>(*h).preis;
cout<<endl;

(*p).next=h;
(*h).next=NULL;
cout<<"Wiederholen(j/n)?";
cin>>auswahl;
cout<<endl;
}while(auswahl=='j');
}


if(*start ==NULL) //wenn Liste leer ist
{
*start=h;
cout<<"Name:";
cin>>(*h).name;
cout<<endl<<"Autor:";
cin>>(*h).autor;
cout<<endl<<"Preis:";
cin>>(*h).preis;
cout<<endl;
}
}

[anda_skoa]

@anda_skoa:
Irgendwie werde ich nicht schlau,was mir das Nullsetzen des start-Pointers bringt

Man nennt das Initialisierung. Das Setzen eines fixen Ausgangszustands.
Du kannst nicht nacher auf 0 abfragen, wenn du vorher nie sichergestellt hast, daß es irgendwann mal 0 war.



Der start-Pointer zeigt doch immer auf das erste Element in der Liste,oder?
Wenn ich demnach diesen start Pointer auf Null setze und ich vorher schon eine Liste besitze,dann hab ich doch diese verloren?!

Wenn du mir erklärst wie du vor der Definition der Variable bereits eine Liste darin unterbringst, d.h. vor der ersten Zeile in main() schon auf eine Variable in main() zugreifen kannst, werd ich mir überlegen, wie man das am besten handhabt.

Allerdings bin ich mir ziemlich sicher, daß zum Zeitpunkt, an dem "start" erzeugt wird, noch keine Liste drinnen sein kann ;)

Ciao,
_

[klicke]

Ahhhh,jetzt weiß ich was du meinst...ist irgendwie logisch...dummer Fehler meinerseits.

Neuer Status:

.) Einfügen am Listenende: funktioniert bereits,sowohl wenn die Liste leer ist als auch wenn bereits etwas drinnen steht.

.)Einfügen am Listenanfang: wenn keine Liste vorhanden ist funktioniert das bereits.Steht bereits etwas in der Liste funktioniert es noch nicht...bevor ich da um Hilfe frage möchte ich selbst noch etwas grübeln,so schwer kann das doch nicht sein.

.)Löschen einer Struktur in der Liste: bin ich gerade dabei



Wenn ich mich nicht irre,dann gibt es beim Löschen einer Struktur drei mögliche Fälle:

1.)Wenn keine Liste vorhanden ist

2.)Wenn man das erste Element aus der Liste löscht

3.)Wenn man ein anderes Element löschen will

Den 1.) Punkt hab ich bereits gelöst,der ist kein Problem - doch beim 2.) Punkt stoße ich auf eine Fehlermeldung des Compilers,die folgendermaßen lautet:


*** glibc detected *** free(): invalid pointer: 0x40260ff4 ***
Abgebrochen

Mein Quelltext:


void loeschen (buch **start);
void loeschen(buch **start)
{
int zahl;
buch *h; //1.Hilfspointer
buch *p; //2.Hilfspointer
cout<<"Welches Element wollen Sie loeschen?";
cin>>zahl; //Anzahl einlesen
if(zahl==1)
{

*start=h; //dem Hilfspointer h wird der start pointer zugewiesen
*start=NULL; //start Pointer wird NULL gesetzt
(*h).next=p; //dem Hilfspointer p wird das nächste Element zugewiesen -->neue Anfang
free(h); //Element wird geloescht-->Speicher wird freigegeben
*start=p; //Liste wird wieder zusammengehaengt

}
}

p.s: Ist es eigentlich normal das Listen schwer verständlich sind oder bin ich da ein Einzelfall und stell mich zu dumm an?

Vielen Dank an anda_skoa und locus vivendi für die bisherigen sehr guten Hilfestellungen

mfg klicke

[anda_skoa]

*start=h; //dem Hilfspointer h wird der start pointer zugewiesen


Sicher?
Nicht vielleicht andersrum? :)



p.s: Ist es eigentlich normal das Listen schwer verständlich sind oder bin ich da ein Einzelfall und stell mich zu dumm an?

Das ist ein Problem dieser low-level Programmierung, irgendwas übersieht man immer. Darum ist es auch wichtig, daß man es mal selber gemacht hat.

Ciao,
_

[klicke]

Hi anda_skoa,

hab die Zeile nun korrigiert und es kommt leider ebenfalls noch der Fehler.
Ich hab mitlwerweile auch im Internet nach verketteten Listen gesucht um dort ein wenig nachzulesen und da hab ich diese Seite (http://www.pronix.de/pronix-827.html) gefunden.
Hab dort ein wenig nachgelesen und dort wurde auch das Thema behandelt und ich konnte keinen Fehler bei mir finden....

Ich bin ratlos...

mfg klicke

[anda_skoa]

Die Zeile


(*h).next = p;

ist auch falsch rum, du willst den Wert von "h next" in p haben, nicht p in "h next"

Ciao,
_

[klicke]

Hab die Zeile nun auch korrigiert,doch der Compiler meldet noch immer den selben Fehler.

Ich hab jetzt nochmal versucht den Quellcode ein wenig zu kürzen um den Fehlerbereich einzugrenzen


p=(**start).next; //dem Hilfspointer p wird das naechste Element zugewiesen(quasi das Element nach dem das gelöscht wird)
free((*start)); //der start Pointer zeigt auf das erste Element und dieses wird gelöscht
*start=NULL; //weiß nicht ob das zwingt notwendig ist,aber schaden kann es (hoffentlich nicht)
*start=p; //dem start Pointer(der Null ist) wird der Hilfspointer p zugewiesen(Liste zusammengeführt)


Ich hoffe diesmal sind meine Überlegungen richtig...

edit: Das Löschen eines beliebigen Elements klappt bereits - nur das Löschen des ersten Elements will nicht so recht..

mfg klicke

[klicke]

Ich habs nun geschafft.

Komischerweise ging es auf dem Compiler in der Schule ohne Probleme...ich will jetzt auch gar nicht weiterforschen,sondern bin einfach nur glücklich das es funktioniert.

Danke an alle (insbesondere an anda_skoa)!

p.s: Wenn Interesse besteht und ich mal Zeit finde werde ich den kompletten Quellcode kommentiert hochladen.

klicke