Probleme mit verketteter Liste
-
Hallo zusammen!
Ich beschäftige mich grad mit verketteten Listen und habe hier einen Code aus meinem Script mit dem ich nicht ganz klar komme. Habe mir das was passiert nun schon drei mal aufgezeichnet - verstehe den Vorgang aber immer noch nicht ganz.
Könnt ihr euch mal anschauen, ob der Code eurer Ansicht nach so funktioniert? Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt. Das wird doch nur in der Funktion voidausgeben verwendet...wie also kann das hier verwendet weren?!(Zeile 43)
Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?
[code] <main.cpp> struct Element *anfang; // globaler Zeiger auf Anfang der Liste void ausgeben() { // ausgeben von Anfang bis Ende Element * p = anfang; // p zeigt auf aktuellen Knoten cout << "Liste: "; while (p != NULL) { cout << p->mData << " "; // Infoteil des aktuellen Knotten ausgeben p = p->mNextPtr; // p auf Folgeelement setzen } cout << endl; } void sortiertEinfuegen(int x) { // aufsteigend sortiert einfuegen Element *ptr = new Element; // erzeuge neues Element ptr->mData = x; // mData wird x ptr->mNextPtr = NULL; // next-Wert wird initialisiert mit NULL if (anfang == NULL) { // Leere Liste anfang = ptr; } else { // Liste nicht leer struct Element *ptr1; ptr1 = anfang; if (x < anfang->mData) { // x wird erstes Element da kleiner ptr->mNextPtr = anfang; // bisheriger Anfang wird eingehängt anfang = p; // neues Element am Anfang } else { while (ptr1->mNextPtr != NULL) // suche Einfuegestelle p1 if (ptr1->mNextPtr->mData < x) { ptr1 = ptr1->mNextPtr; //hier } else break; ptr->mNextPtr = ptr1->mNextPtr; // jetzt an der richtigen Stelle, p verketten ptr1->mNextPtr = p; // verketten Vorgaenger } } } <main.cpp> int main() { anfang = NULL; // Leere Liste int eingabe; while (true) { cout << "Integer (Abbruch mit negativem Wert): "; cin >> eingabe; if (eingabe<0) break; // Beende Eingabeaufforderung sortiertEinfuegen(eingabe); } ausgeben(); return(0); }
-
Sorry hab das struct vergessen:
<verketteListe.h> struct Element { int mData; Element * mNextPtr; };
-
RalfZ schrieb:
Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt.
Was sagt denn der Compiler dazu?
RalfZ schrieb:
Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?
Richtig!
Vielleicht wurde der Code schon vor 30 Jahren in einer C-Vorlesung verwendet, da braucht man das struct.
-
RalfZ schrieb:
Hallo zusammen!
Könnt ihr euch mal anschauen, ob der Code eurer Ansicht nach so funktioniert? Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt.Das p kommt von nirgendwo. Das wird daher entweder so nicht funktionieren oder du hast nicht den gesamten Code gezeigt (die #includes fehlen beispielsweise auch).
Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?
Vermutlich weil das von einem C-Entwickler geschrieben wurde, der aus C++ nur "cout" verwendet und sonst nichts. Auch das "NULL" sollte in C++ nicht vorkommen und durch "nullptr" ersetzt sein.
Ansonsten sieht das sortiertEinfuegen doch viel zu kompliziert aus. Habs jetzt nicht ganz durchgelesen, aber ich wette, dass das viel kürzer geht.
-
Hallo,
danke für die Antworten. Ja das p scheint mir auch von nirgendwo zu kommen. Im Script wird nur das <verketteteListe.h> in der main includiert...das hab ich vergessen... ansonsten gibts keine includierungen. Ich vermute dass das p ein Schrfeibfehler ist... nachdem ich nun aber versucht habe den Code nachzuvollziehen, indem ich das p durch ptr oder ptr1 ersetzt habe komme ich immernoch auf keine Lösung.
Das "struct" in Zeile 4 und 27 hab ich weggelassen... das funktioniert.
Ich finde diesen Code extrem kompliziert. Was sagt Ihr... gibts da ne andere Variante?
Noch ne andere Frage - ich verstehe das Prinzip der verketteten Liste immer noch nicht: Werden meine Objekte im Speicher nun sortiert nach "Wert"(z.B. in diesem Fall nach mData) z.b. aufsteigend? Also hab ich z.B. auf Speicherstelle 1000 das struct mit dem Wert 3, auf 1001 das struct mit dem Wert 4 und auf 1002 das struct mit dem Wert 5?
Oder sind meine structs Kreuz und Quer im Heap(dynamische Var) verteilt und die "Sortierung" ist eigentlich nur im Sinne der " mNextPtr " - Zeiger vorhanden?Also z.B. mein struct mit der 3 liegt auf Speicherstelle 500, mein struct mit Wert 4 auf Speicherstelle 12777 und mein struct mit der 5 auf Speicherstelle 2145... ?
-
RalfZ schrieb:
Ich vermute dass das p ein Schrfeibfehler ist...
Ja, denke ich auch.
Ich finde diesen Code extrem kompliziert. Was sagt Ihr... gibts da ne andere Variante?
s.u.
Noch ne andere Frage - ich verstehe das Prinzip der verketteten Liste immer noch nicht: Werden meine Objekte im Speicher nun sortiert nach "Wert"(z.B. in diesem Fall nach mData) z.b. aufsteigend? Also hab ich z.B. auf Speicherstelle 1000 das struct mit dem Wert 3, auf 1001 das struct mit dem Wert 4 und auf 1002 das struct mit dem Wert 5?
Oder sind meine structs Kreuz und Quer im Heap(dynamische Var) verteilt und die "Sortierung" ist eigentlich nur im Sinne der " mNextPtr " - Zeiger vorhanden?Also z.B. mein struct mit der 3 liegt auf Speicherstelle 500, mein struct mit Wert 4 auf Speicherstelle 12777 und mein struct mit der 5 auf Speicherstelle 2145... ?
Letzteres. Wo die Objekte wirklich im Speicher liegen, bestimmt das "new". Das entscheidet nach Gutdünken (bzw. je nach Allocator). Und das new wird ja gemacht, bevor du sortierst. Das ist übrigens auch der riesengroße Nachteil verketteter Listen: die Daten liegen wild verteilt im Speicher rum, was den Zugriff langsam machst. Wenn du willst, dass die Daten hintereinander liegen, dann musst du ein C-Array, ein std::array oder einen std::vector nehmen. Dann kannst du aber nicht mehr mitten in der Liste etwas einfügen bzw. wenn du auf Speicherstelle 42 die 3, auf Stelle 43 die 5 und auf Stelle 44 die 6 gespeichert hast und nun eine 4 einfügen willst, musst du erst Platz machen und die nachfolgenden Elemente verschieben.
Als lauffähigen Ersatz habe ich deinen Code mal schnell umgeschrieben.
Wichtig: Es gibt KEINE globale Variable mehr, sondern stattdessen wird einfach der Listenkopf als Parameter übergeben. Globale Variablen machen das Programm kompliziert, weil die unsichtbare Abhängigkeiten reinbringen, die man nicht so direkt sieht. Außerdem kannst du in deiner ursprünglichen Version nicht 2 unterschiedliche Listen haben, da die alle von dem globalen Anfang abhingen.
Auch noch wichtig:
- du könntest jetzt hieraus eine Klasse "Liste" machen
- es wird hier immer noch kein Speicher freigegeben, du hast also einen Leck (wirst du sicher noch was zu lernen)
- aber es funktioniert und ich hoffe, du verstehst hier besser, wie das Einfügen geht#include <iostream> #include <random> using namespace std; struct Element { int mData; Element* mNextPtr; }; // ausgeben von Anfang bis Ende void ausgeben(const Element *kopf) { cout << "Liste: "; while (kopf) { cout << kopf->mData << " "; kopf = kopf->mNextPtr; } cout << endl; } // aufsteigend sortiert einfuegen void sortiertEinfuegen(Element* &kopf, int x) { Element *neu = new Element; neu->mData = x; // muss das Element ganz vorn eingefügt werden? if (!kopf || x <= kopf->mData) { neu->mNextPtr = kopf; kopf = neu; return; } auto prev = kopf; auto dieses = kopf->mNextPtr; while (dieses && x > dieses->mData) { prev = dieses; dieses = dieses->mNextPtr; } neu->mNextPtr = dieses; prev->mNextPtr = neu; } int main() { Element *kopf = nullptr; sortiertEinfuegen(kopf, 30); sortiertEinfuegen(kopf, 40); ausgeben(kopf); sortiertEinfuegen(kopf, 60); sortiertEinfuegen(kopf, 50); ausgeben(kopf); std::random_device rd; for (int i = 0; i < 15; ++i) { std::uniform_int_distribution<int> d(0,100); sortiertEinfuegen(kopf, d(rd)); } ausgeben(kopf); }
-
Hallo wob, vielen Dank für deinen Beitrag. Ich werde deinen code gleich mal ausprobieren (wollte das ganze eh auch noch als Klasse programmieren). Das hilft mir auf jeden Fall weiter
Derweil hab ich auch den Fehler im Code meines Profs gefunden... das p soll einfach ptr heissen ... also die korrigierte und funktionierende Version seht ihr unten. Ein Problemchen macht das Prog allerdings... nach 10 bis 20 eingegebenen Zahlen bleibt das Programm stehn ... hat jemand eine Idee an was das liegen kann. Es kommt kein Fehler...habe das Gefühl dass es in irgendner Schleife stecken bleibt...
<CsElement.h> struct sElement { int mData; sElement * mnextptr; }; <main.cpp> #include <iostream> #include "CsElement.h" using namespace std; sElement *anfang; void sortierteinfuegen(int x); void ausgeben(); int main() { anfang = 0; int eingabe; cout << "Dateneingabe, ende mit neg wert: "<<endl; while (true) { cin >> eingabe; if (eingabe < 0) break; sortierteinfuegen(eingabe); }; ausgeben(); system("Pause"); return 0; }; void sortierteinfuegen(int x) { cout << "Einfuegefunktion gestartet ... " <<x<<endl; sElement *ptr = new sElement; ptr->mData = x; ptr->mnextptr = 0; if (anfang == 0) //prüfe ob min ein objekt in liste { anfang = ptr; //nein } else //ja ... { sElement * ptr1 = anfang; //Pointervariable ptr1...Sicherung von Anfang if (x < anfang->mData) //neues Element kleiner als erstes Element? { anfang = ptr; ptr->mnextptr = ptr1; } else //neues Element ist größer als erstes { while (ptr1->mnextptr != 0) { if (x>ptr1->mnextptr->mData) ptr1 = ptr1->mnextptr; }; ptr->mnextptr = ptr1->mnextptr; ptr1->mnextptr = ptr; } } } void ausgeben() { sElement *p = anfang; cout << "Liste: "; while (p != 0) { cout << p->mData << " "; p = p->mnextptr; } cout << endl; }
-
Ahoi!
Ich hätte da auch nochmal ne Frage zu der Parameterübergabe an die Funktion sortiertEinfuegen (also bei wobs code). Der Code funktioniert bei mir auch ..und das mesite ist mir auch klar.
Was ich noch nicht ganz verstehe... was für eine Art von Übergabe hat der erste Parameter ...
Also Funktion:
void sortiertEinfuegen(Element* &kopf, int x) { Element *neu = new Element; neu->mData = x; // muss das Element ganz vorn eingefügt werden? if (!kopf || x <= kopf->mData) { neu->mNextPtr = kopf; kopf = neu; return; } auto prev = kopf; auto dieses = kopf->mNextPtr; while (dieses && x > dieses->mData) { prev = dieses; dieses = dieses->mNextPtr; } neu->mNextPtr = dieses; prev->mNextPtr = neu; }
Und der Aufruf in der main:
Element *kopf = nullptr; //Zeigervar Typ Element auf 0; sortiertEinfuegen(kopf, 30);
ich check nicht ganz warum hier der erste Parameter " Element* &kopf " ist... Also ich kenne call-by-reference ... also das man einen Pointer übergibt(z.B. berechneDurchmesser(int * radius) ) oder auch den Referenzparameter (z.B. berechneDurchmesser(int &radius) ) Diese Kombination verwirrt mich etwas ... was geschieht hier?
Vielen Dank schonmal für eure Hilfe
-
Ein Pointer ist auch nur ein Datentyp. Du kannst jeden Datentyp als Value oder als Referenz übergeben.