Was muss übergeben werden?

[Hans W. (Gast)]

Hi Leute!

Ich hab nun dieses Programm geschrieben. Das soll eine einfach 
verkettete Liste sein.

Nun hab ich auch eine Methode DeleteList implementiert, die mir die 
Liste lsöchen soll.

Wenn ich diese Methode in der main-Fkt. aufrufe, weiß ich nicht was ich 
der Methode übergeben muss!

Kleines Bespiel:

#include<iostream>
#include<time.h>
#include"list.h"
#include"element.h"

int main()
{
  list myList;

  //Hier folgt die Belegung mit Werten

  myList.DeleteList(myList);
//Hier wirft der Compiler Fehler!
//Was muss ich an die Methode übergeben?


return 0;
}

Könnt ihr mir vielleicht weiterhelfen?

[Daniel F. (df311)]

void list::DeleteList(element *first);

[...]
list myList;
myList.DeleteList(myList);

du hast myList als list deklariert und versuchst nun die methode 
DeleteList (die das erste element als parameter erwartet) mit der liste 
aufzurufen.

zwei möglichkeiten:
1. du schreibst dir eine methode "getFirstElement", die dir einen 
pointer auf das erste element liefert
2. du rufst einfach den destruktor auf, da dieser ja auch die list 
löscht.

ob deleteList richtig implementiert ist habe ich jetzt nicht geschaut, 
die punkte sind mir nur auf die schnelle aufgefallen...

[Benjamin U. (utzus)]

In deiner Funktion steht doch, was du ihr übergeben musst.

void list::DeleteList(element *first)

einen Zeiger auf ein element. myList ist aber aber vom typ List.

aus deiner list.h

private:
  element *head;  //Zeiger auf den Anfang

also einfach: myList.head, aber da die ja private sind, brauchst du noch 
eine Funktion, die dir den Zeiger auf head zurück gibt. Irgendwie sowas: 
element* list::GetFirstElement().

Grüße

[Karl H. (kbuchegg)]

Oder aber du machst dir eine 2.te DeleteList Funktion, die genau diesen 
fehlenden Pointer für die arbeitende Funktion ergänzt.

void list::DeleteList()
{
  DeleteList( head );
}

Das wäre meine Wahl. Dann hab ich 2 Funktionen
* die eine die die Liste mit Mann und Maus löscht
* und die andere, der ich angeben kann ab wo sie löschen soll.


PS. Deine arbeitende DeleteList Funktion ist fehlerhaft. Auch nach dem 
Löschen muss die Liste wieder in einem gültigen Zustand sein. Deine head 
und tail Pointer sind es jedenfals nicht. Die zeigen irgendwo hin, was 
besonders gut kommen wird, wenn dann der Destruktor die Liste noch 
einmal löschen wird.

War das eigentlich gefordert, das deleteList rekursiv sein muss? Die 
Rekursion klingt zwar hier verführerisch, aber das Handling des head und 
tail Pointers wird dafür .... Arsch. Als Notlösung: versteck deine 
DeleteList als private Funktion und dokumentier das sie nicht direkt 
aufgerufen werden darf (auch nicht von innerhalb der Klasse ausser von 
dieser speziellen DeleteList Funktion). Und die eigentliche public 
Version schreibst du so

void list::DeleteList()
{
  DeleteList( head );

  head = NULL;
  tail = NULL;
}

dann erfüllt die Klasse wenigstens die Voraussetzung, das sie nach dem 
Aufruf einer public Funktion in sich einen konsistenten Zustand besitzt 
und du hast eine saubere DeleteList Funktion, die du beliebig oft 
aufrufen kannst und die trotzdem immer das richtige tut.

[Klaus W. (mfgkw)]

Daniel F. schrieb:
> 2. du rufst einfach den destruktor auf, da dieser ja auch die list
> löscht.

Hast du da mal ein Codebeispiel?

[Klaus W. (mfgkw)]

Hans Wurst schrieb:
> Ich hab nun dieses Programm geschrieben. Das soll eine einfach
> verkettete Liste sein.

Und warum hast du dann für DeleteList() einen Parameter vorgesehen? 
Welchen Sinn hat der?

BTW: class element geht niemanden etwas an außerhalb der Liste.
Deshalb würde ich das als private Unterklasse in die Liste packen:

class List
{
private:
    class Element
    {
    public:
         ...
    };
public:
  ...
}

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> Daniel F. schrieb:
>> 2. du rufst einfach den destruktor auf, da dieser ja auch die list
>> löscht.
>
> Hast du da mal ein Codebeispiel?

Nitpicking:
Man kann Destruktoren aufrufen. Ist legal.
object.~Klassenname();

Sowas braucht man zb, wenn man mit einer Klasse Chunk-Allokierung 
betreiben will, sich also selbst um die Bereitstellung von Speicher 
kümmert (zb in Form eines entsprechend großen Byte-Arrays), in dem dann 
Objekte ganz normal nach Bedarf konstruiert/destruiert werden und man 
nicht jedesmal durch die teure Speicherverwaltung new/delete durch muss.

  * dezidierter Konstruktor-'Aufruf' mittels placement new
  * Destruktor direkt aufrufen.


Aber: Hier natürlich völlig fehl am Platze. Diese Flause sollte man 
einem Neuling nicht in den Kopf setzen.

[Daniel F. (df311)]

Klaus Wachtler schrieb:
> Daniel F. schrieb:
>> 2. du rufst einfach den destruktor auf, da dieser ja auch die list
>> löscht.
>
> Hast du da mal ein Codebeispiel?

mea culpa, habe übersehen dass du die liste nicht dynamisch erzeugst, 
dann könnte man den destruktor einfach mit delete aufrufen...

[Hans W. (Gast)]

Karl Heinz Buchegger schrieb:
> PS. Deine arbeitende DeleteList Funktion ist fehlerhaft. Auch nach dem
> Löschen muss die Liste wieder in einem gültigen Zustand sein. Deine head
> und tail Pointer sind es jedenfals nicht. Die zeigen irgendwo hin, was
> besonders gut kommen wird, wenn dann der Destruktor die Liste noch
> einmal löschen wird.


Hallo!

Erstmal Danke an eure bisherige ausführliche Hilfe! Hat mir schon mal 
sehr geholfen!

Ich hab mir jetzt mal eine weitere Methode GetFirstElement geschrieben, 
die so aussieht:

element* list::GetFirstElement()
{
return head;
}

Dass die DeleteList-Funktion nicht richtige arbeitet, hab ich grad 
selbst feststellen müssen. Nachdem ich mir eine Liste erstellte hatte, 
sie mir ausgeben ließ und dann löschen wollte, bringt mir das Programm 
einen Laufzeitfehler. Das liegt wohl an den Pointern die ins leere 
Zeigen und somit quasi die Liste "nach dem Löschen" nicht in einem 
gültigen Zustand ist.

Meine DeleteList-Funktion sieht jetzt so aus:

void list::DeleteList(element *first)
{
  if(first != NULL)  //Erstes Element keinen Eintrag?
  {
    if(first->next != NULL)    //Nachfolge-Element auch keinen Eintrag?
    {
      DeleteList(first->next);  //Falls beides zutrifft, dann lösche rekursiv die gesamte Liste
    }

    delete first;
  }

head = NULL;
tail = NULL;
}

Die Rekursion in meinem Programmcode, kommt von Programmteilen, die wir 
hernehmen sollten. Da kann ich also auch nix für. Das es schlecht ist, 
leuchtet ein...

[Karl H. (kbuchegg)]

Hans Wurst schrieb:

> Meine DeleteList-Funktion sieht jetzt so aus:
>
>

> void list::DeleteList(element *first)
> {
>   if(first != NULL)  //Erstes Element keinen Eintrag?
>   {
>     if(first->next != NULL)    //Nachfolge-Element auch keinen Eintrag?
>     {
>       DeleteList(first->next);  //Falls beides zutrifft, dann lösche
> rekursiv die gesamte Liste
>     }
> 
>     delete first;
>   }
> 
> head = NULL;
> tail = NULL;
> }
>

extrem ineffizient.
Wenn deine Liste 200 Elemente lang ist, werden head und tail beim 
Löschen 200 mal auf NULL gesetzt, obwohl es 1 mal auch tun würde.

Normalerweise würde ich mich darüber nicht echoffieren, bei einer 
Hausübung würde ich dir das als Lehrer nicht durchgehen lassen, zumal 
ich dir gezeigt habe, wie du das 'Problem' beheben kannst.

Was passiert eigentlich, wenn ich deine DeleteList nicht mit dem ersten 
Element aufrufe?
Gratulation, du hast soeben ein Memory Leak gebaut. Ganz abgesehen 
davon, dass die Liste dann die Elemente verloren hat, die ich eigentlich 
nicht löschen wollte.

Es ist bei Einsatz von rekursiven Methoden nicht ungewöhnlich, dass man 
2 Funktionen hat. Die eine, die die Rekursion erledigt und die andere, 
die Präprozessing, Starten der Rekursion und Postprocessing macht. Die 
rekursive Funktion ist tief im inneren der Klasse verborgen und geht 
niemanden was an. Die andere, das ist die, die der Benutzer der Liste zu 
benutzen hat.

Und den
     if(first->next != NULL)
würde ich dir auch rausstreichen, wenn auch ohne Punkteabzug. 
Stattdessen würde ich mal eine Stunde zum Thema: "sinnlose, gutgemeinte 
Optimierungen oder warum macht es keinen Sinn 2 Nanosekunden durch den 
Einsatz eines if's einsparen zu wollen, wenn der if doch selber auch 1 
Nanosekunde benötigt und in 99% aller Fälle nichts einsparen kann. Du 
verlangsamst 199 rekursive Aufrufe um jeweils 1 Nanosekunde nur um dann 
bei 1 Aufruf mal 1 Nano einsparen zu können. Unterm Strich ein 
Verlustgeschäft, das immer mehr zu deinen Ungunsten ausfällt, je länger 
die Liste ist. Aus der vermeintlichen Optimierung ist eine Pessimierung 
geworden.

[Hans W. (Gast)]

@Karl-Heinz Buchegger:


Ich hab dir jetzt die meine list.cpp und list.h hochgeladen. Ich hab 
jetzt mal alles so geändert wie du mir das vorgeschlagen hast!

Ich hoffe jetzt passts soweit...

[Hans W. (Gast)]

Nun, bin ich auf ein weiteres Problem gestoßen:

Ich soll nun die Liste mit einem selbst implementierten 
Quicksort-Algorithmus sortieren.

Ich hab den Quicksort-Algorithmus soweit drauf, aber "nur" in Verbindung 
mit einem Array. Ich soll nun den Algo. auf Listen abändern. Ich hab mir 
dazu eine Methode Quicksort gebaut und dabei auf ein Problem gestoßen:

//f=first=erstes Element in der Liste
//l=last=letztes Element in der Liste
void list::Quicksort(element *f, element *l)
{
  int part;  //Was ist das?

  if(f < l)
  {
    PreparePartition(f, l, part);
    Quicksort(f, part-1);
    Quicksort(part+1, l);
  }
}

In den Zeilen mit den rekursiven Aufrufen von Quicksort, rufe ich 
Quicksort mit einer int-Variable auf, was ja nicht geht; Quicksort 
erwartet einen element-Zeiger-Typ... Wie geht das jetzt weiter? Muss ich 
die part-Variable als int-Zeiger deklarieren und dann dementsprechend 
zurückgeben? Hab ich ausprobiert: Geht auch nicht...

[Karl H. (kbuchegg)]

Hans Wurst schrieb:
> Nun, bin ich auf ein weiteres Problem gestoßen:
>
> Ich soll nun die Liste mit einem selbst implementierten
> Quicksort-Algorithmus sortieren.
>
> Ich hab den Quicksort-Algorithmus soweit drauf,

iiiiiiaaaaa

Nicht wirklich.
Du denkst noch zu sehr in Arrays und nicht in allgemeinen 
Datenstrukturen.

Mal dir mal eine Liste mit 5 Elementen auf und dann wende dein Wissen 
über Quicksort an. Beobachte dich selbst: was machst du?


> In den Zeilen mit den rekursiven Aufrufen von Quicksort, rufe ich
> Quicksort mit einer int-Variable auf, was ja nicht geht; Quicksort
> erwartet einen element-Zeiger-Typ... Wie geht das jetzt weiter? Muss ich
> die part-Variable als int-Zeiger deklarieren

wieso int-zeiger?
element pointer.

part zeigt dir, allgemein gesprochen, an, wo die Datenstruktur zu teilen 
ist. Dazu musst du 1 Element der Datenstruktur eindeutig ansprechen 
können. Bei einem Array hattest du zum ansprechen eines Array Elements 
einen Index. Daher war das ein int. Hier wird ein Listenknoten mit einem 
element* identifiziert, daher wird das dann wohl ein .... sein.

Und siehe da, plötzlich passen dann auch die Datentypen bei den 
rekursiven Aufrufen.

 Quicksort(element *f, element *l)

will 2 element Pointer.

     Quicksort(f, part->prev);    // prev ist die Umkehrung zu next
bzw  Quicksort(part->next, l);

sind 2 element Pointer.

[Hans W. (Gast)]

Karl Heinz Buchegger schrieb:
> iiiiiiaaaaa

Kurze Zwischenfrage: Wolltest du mich damit veräppeln?

[Hans W. (Gast)]

Karl Heinz Buchegger schrieb:
> Quicksort(f, part->prev);    // prev ist die Umkehrung zu next

Das würde ja dann Bedeuten, ich muss die Liste als doppelt verkettete 
Liste implementieren, oder? Nur dann macht doch so ein prev Sinn...

void list::Quicksort(element *f, element *l)
{
  element *part;  //Was ist das?

  if(f < l)
  {
    PreparePartition(f, l, part);
    Quicksort(f, part->prev);
    Quicksort(part->next, l);
  }
}

Ich hab nun die element.h mit einem "element *prev;" ergänzt.

[Hans W. (Gast)]

Ich hab dann mal mit bestem Gewissen weitergemacht. Dabei ist das hier 
entstanden:

void Swap(element *a, element *b)
{
  element *temp;

  temp->val = b->val;
  b->val = a->val;
  a->val = temp->val;
}


void list::Quicksort(element *f, element *l)
{
  element *part;  //Was ist das?

  if(f < l)
  {
    PreparePartition(f, l, part);
    Quicksort(f, part->prev);
    Quicksort(part->next, l);
  }
}


void list::PreparePartition(element *f, element *l, element *p)
{
  int pivot = f->val;
  p = p->prev;

  while(f->next != NULL)
  {
    if(f->val <= pivot)
    {
      p = p->prev;
      Swap(f, p);
    }

    f = f->next;
  }

  //Pivot-Element an die richtige Stelle tauschen
  Swap(f, p);
}

Wenn ich nun von der main aus den Quicksort aufrufe, dann bekomm ich vom 
Compiler zwei Fehler und zwei Warnungen:

Die 2 Fehler beziehen sich auf den Linker, die 2 Warnungen beziehen sich 
einmal auf den (anscheinend) uninitialiserten *part-Pointer bzw. auf den 
ebenfalls nicht initialisierten *temp-Pointer aus Swap.

Ich weiß ehrlich gesagt da jetzt wirklich nicht mehr weiter...

[Klaus W. (mfgkw)]

Vielleicht mal die Grundlagen lernen?

[Karl H. (kbuchegg)]

Hans Wurst schrieb:
> Karl Heinz Buchegger schrieb:
>> iiiiiiaaaaa
>
> Kurze Zwischenfrage: Wolltest du mich damit veräppeln?

In gewisser Weise.

Auf der einen Seite sagst du du hättest den Quicksort im Griff, auf der 
anderen Seite scheinen dir aber ein paar wesentliche Dinge nicht 
wirklich klar zu sein.

[Karl H. (kbuchegg)]

Hans Wurst schrieb:
> Karl Heinz Buchegger schrieb:
>> Quicksort(f, part->prev);    // prev ist die Umkehrung zu next
>
> Das würde ja dann Bedeuten, ich muss die Liste als doppelt verkettete
> Liste implementieren, oder?

Sagt wer?

Irgendwie musst du den Vorgänger eines Elements in der Liste ermitteln. 
Wie immer du das auch machst.

> Nur dann macht doch so ein prev Sinn...
Nö. Man kann sich ja zb auch eine Listenfunktion prev() implementieren, 
die von einem Element den Vorgänger bestimmt.

Der springende Punkt ist: Ich will dir nicht jeden Scheiß auf dem 
Silbertablett präsentieren. Wenn du dich an dynamischen Datenstrukturen 
versuchst und damit arbeiten will, solltest du schon über ein wenig 
Erfahrung verfügen, WIE du gewissen Dinge erreichst.
Wenn du eine Wohnung auszumessen hast, muss es genügen, dass ich dir 
sage, dass die Einzelwohnflächen zusammenzählen musst und das der Balkon 
da auch dazugehört. Wenn ich dir auch noch sagen muss, dass du für ein 
rechteckiges Zimmer die Länge mit der Breite multiplizieren musst, dann 
bist du als angehender Architekt im 5. Semester fehl am Platze. Denn das 
hast du bereits als 13 jähriger gelernt.

Und dir sollte auch klar sein, was du da eigentlich zu implementieren 
hast.

Tip: Ein Notizzettel auf dem man sich Dinge aufmalt hilft ungemein.

[Karl H. (kbuchegg)]

>
>

> void Swap(element *a, element *b)
> {
>   element *temp;
> 
>   temp->val = b->val;
>   b->val = a->val;
>   a->val = temp->val;
> }
>

Ich denke, das ist alles noch zu schwer für dich. Entweder das oder dir 
fehlen haufenweise vorhergehende Grundlagen.
Oder aber du denkst nicht über die Dinge nach, die du tust.

Wann immer du einen Pointer hast, musst du dich sofort fragen: Wo zeigt 
der Pointer hin? Wo ist das Element auf das er zeigt? Habe ich dort, wo 
der Pointer hinzeigt überhaupt ein Element, in dem ich Werte speichern 
kann?

Irgendwie hab ich das Gefühl, du verlässt dich viel zu sehr auf den 
Compiler. Gibt es keine Fehlermeldung, dann ist alles korrekt.

Mitnichten! Bis hier her war alles pipifax. Fehlermeldunungen vom 
Compiler sind noch das kleinere Problem. Denn die kann man durchlesen, 
überlegen was das Problem ist und beheben. Jetzt kommen aber immer mehr 
Logikdinge ins Spiel. Und die sagt dir kein COmpiler dieser Welt. Die 
sind ganz alleine dein Bier. Jetzt bist du bei dem angelangt, was man 
dann tatsächlich "programmieren" nennt. "Malen nach Zahlen" war gestern, 
ab jetzt komponierst du die Bilder mit nichts anderem als Leinwand, 
Farben und Pinsel, deiner Kreativität und einer Menge an vorhandenem und 
stetig wachsendem Wissen über Farblehre und Bildkomposition. Und 
natürlich der Fähigkeit des virtuosen Umgangs mit diesen Zutaten.

In gewisser Weise geht es darum, dass du schön langsam mit dem Studium 
der italienischen Grammatik durch bist. Du kommst jetzt immer mehr in 
die Phase, in der du eine kleine Geschichte erzählen sollst. Wenn die 
Grammatik stimmt, ist das schön, ist aber nur 30% der Miete. Die anderen 
70% sind: sinnvolle Sätze bauen und eine kleine Geschichte aufbauen.

[Karl H. (kbuchegg)]

> Ich hab nun die element.h mit einem "element *prev;" ergänzt.

Und?
Hast du auch die Bearbeitungsfunktionen entsprechend ergänzt, so dass 
der Pointer auch immer korrekt auf das Vorgängerelement zeigt?

So wie ich dich Schlamperdatsch mitlerweile kenne, wahrscheinlich nicht.

Aber du brauchst es auch gar nicht. Eine Listenfunktion, die dir einen 
Pointer auf den Prev eines Elements liefert, ist schnell geschrieben.

[Karl H. (kbuchegg)]

Abgesehen vom bisher gesagten, empfinde ich diese Lösungsidee

> void Swap(element *a, element *b)
> {
>   element *temp;
> 
>   temp->val = b->val;
>   b->val = a->val;
>   a->val = temp->val;
> }

als geschummelt. Das geile an linearen Listen ist ja, dass man 
Einfüge/Lösch/ bzw. überhaupt Reihungsoperationen durchführen kann, ohne 
dass die Daten ihren angestammten Speicherplatz verlassen müssen.
Soll heißen: derartige Operationen werden rein durch Manipulation der 
Pointer gemacht.

OK. hier bei einem int im Element ist das noch nicht der große 
Showstopper. Aber wenn da in der Liste 300 JPG Bilder mit jeweils 2MB 
liegen und diese nach Pixelgröße sortiert werden sollen, macht das dann 
schon einen Unterschied, ob ich laufen die Bilder hin und herkopieren 
muss oder ob die Bilder nur anders verpointert werden (nämlich so, dass 
sie sortiert sind).

[Karl H. (kbuchegg)]

Abgesehen vom bisher gesagten, empfinde ich diese Lösungsidee

> void Swap(element *a, element *b)
> {
>   element *temp;
> 
>   temp->val = b->val;
>   b->val = a->val;
>   a->val = temp->val;
> }

als geschummelt. Das geile an linearen Listen ist ja, dass man 
Einfüge/Lösch/ bzw. überhaupt Reihungsoperationen durchführen kann, ohne 
dass die Daten ihren angestammten Speicherplatz verlassen müssen.
Soll heißen: derartige Operationen werden rein durch Manipulation der 
Pointer gemacht.

OK. hier bei einem int im Element ist das noch nicht der große 
Showstopper. Aber wenn da in der Liste 300 JPG Bilder mit jeweils 2MB 
liegen und diese nach Pixelgröße sortiert werden sollen, macht das dann 
schon einen Unterschied, ob ich laufen die Bilder hin und herkopieren 
muss oder ob die Bilder nur anders verpointert werden (nämlich so, dass 
sie sortiert sind).