C++: Verkettete Listen und Kopierkonstruktor???

HubertB

Bandbreitenverschwender
Wie schreibe ich einen Kopierkonstruktor für eine Klasse, die als Datenstruktur eine einfach verkettete Liste enthält? Der Standardkopierkonstruktor macht ja nur eine flache Kopie, ich brauch aber eine tiefe.

Hier meine interf.h
Code:
typedef int T;

class KSet
{
   public:
      //m1) Leere Menge
      KSet();
      //m2) Vereinigung zweier Mengen
      void verein(KSet &M1, KSet &M2);
      //m3) Element x hinzufügen
      void hinzuf(T x);
      //m4) i-tes Element der Menge lesen
      T lesen(int i);
      //m5) Element x löschen
      void loeschen(T x);
      //m6) Anzahl der Elemente
      int anzahl();
      //m7) Ist x Element der Menge?
      bool ist(T x);
      //m8) Anzeigen aller Elemente der Menge (<<)
      friend ostream & operator<<(ostream & out, const KSet & s);
      //m9) Konvertierung von einem Feld des Typs T nach KSet
      void konvert(T* feld);

   private:
      struct node
      {
         T daten;
         node* next;
      };
      node* anker;
      bool isEmpty;
};

Die impl.cpp:
Code:
#include <iostream.h>
#include "interf.h"

//m1) Leere Menge
KSet::KSet()
{
   anker=NULL;
   isEmpty=true;
}

KSet::KSet(const KSet &rhs)
{
   anker = new node;
   *anker = *(rhs.anker);
}

//m3) Element x hinzufügen
void KSet::hinzuf(T x)
{
   if(!ist(x))
   {
      if(isEmpty)
      {
         node* tmp=new node;
         tmp->daten=x;
         tmp->next=NULL;
         anker=tmp;
         isEmpty=false;
      }
      else
      {
         /*
         //Anfügen als 2tes Element
         node* tmp=new node;
         tmp->daten=x;
         tmp->next=anker->next;
         anker->next=tmp;
         */

         //Anfügen als letztes Element
         node* last=anker;
         for(last=anker; last->next!=NULL; last=last->next);
         node* tmp=new node;
         tmp->daten=x;
         tmp->next=NULL;
         last->next=tmp;
      }
   }
}

//m7) Ist x Element der Menge?
bool KSet::ist(T x)
{
   for(node* i=anker; i!=NULL; i=i->next)
   {
      if(i->daten == x)
      {
         return true;
      }
   }
   return false;
}

//m8) Anzeigen aller Elemente der Menge (<<)
ostream & operator<<(ostream & out, const KSet & s)
{
   out << "[";
   for(KSet::node *i=s.anker; i != NULL; i=i->next)
   {
      out << i->daten << " ";
   }
   out << "]";
   return out;
}

Die main.cpp:
Code:
#include <iostream.h>
#include "interf.h"

int main(int argc, char* argv[])
{
   //K4
   KSet M1;
   //K5
   cout << "Alle Elemente von M1: " << M1 << endl;
   //K6
   M1.hinzuf(1);
   M1.hinzuf(4);
   M1.hinzuf(3);
   M1.hinzuf(3);
   //K7
   KSet M2;
   cout << "Alle Elemente von M2: " << M2 << endl;
   //K8
   KSet M3;
   M3.verein(&M1, &M2);
   cout << "Alle Elemente von M3: " << M3 << endl;
   getchar();
   return 0;
}

Danke für eure Hilfe!
 

Kamikaze

Warrior of Sunlight
Geh doch einfach mit einem Iterator durch die Liste und mache flache Kopien von jedem Element.
 

HubertB

Bandbreitenverschwender
Könnte man schon machen, aber wenn ich das so in der Klausur mache dreht mir der Prof den Hals rum.

Bereichte mich gerade für die Klausur "Datenstrukturen und Algorithmen" vor, die STL gibts aber erst ab "Objektorientierter Programmierung".

Ich versuch gerade mittels "void hinzuf(T x)", "T lesen(int i)" und "int anzahl()" was zusammen zu frickeln.
Nachtrag: Hat nicht funktioniert, Lösung siehe unten.
 
Zuletzt bearbeitet:

Kamikaze

Warrior of Sunlight
Dir ist natürlich klar das C++ gar keine objektorientierte Sprache ist sondern blos so tut und im Grunde genommen absolut ungeeignet für solche Dinge?
 

HubertB

Bandbreitenverschwender
[LoN]Kamikaze schrieb:
Dir ist natürlich klar das C++ gar keine objektorientierte Sprache ist sondern blos so tut und im Grunde genommen absolut ungeeignet für solche Dinge?

Ähmm nein?! Die Vorlesung "Objektorientierte Programmierung" basiert auch auf Cpp, Inhalt ist wie schon erwähnt STL, daneben gibts noch Vererbung und etwas GUI-Programmierung. Aber erklär bitte mal genauer was du meinst.

BTW: Ich glaub ich habs hinbekommen.
 

nakal

Anfänger
Es gibt keine objektorientierten Sprachen. Nur objektorientierte Programmierung. Und das kann man sogar mit C (nein, nicht objective C, normales C) machen. Siehe Begriff "Paradigma". Es heißt die Sprache "unterstützt objektorientierte Programmierung". C tut es nicht, C++ unterstützt den Programmierer dabei sehr wohl.
 

HubertB

Bandbreitenverschwender
Heist das man könnte auch in reinem C soetwas wie Vererbung realisieren?

BTW: Hier mein Kopierkonstruktor (geht mit Sicherheit auch noch irgendwie einfacher...):
Code:
KSet::KSet(const KSet &rhs)
{
   anker=NULL; //Eigenen Anker NULL setzen
   node* tmpQuelle=rhs.anker; //Zeiger auf Quellknoten
   node* tmpZiel=NULL; //Zeiger auf Zielknoten
   if(tmpQuelle != NULL) //Quellknoten nicht leer -> Kopieren starten
   {
      anker=new node; //Am eigenen Anker neuen Knoten erstellen
      anker->daten=tmpQuelle->daten; //Datenbereich des neuen Knotens füllen
      anker->next=NULL; //Zeigerbereich des neuen Knotens NULL setzen
      tmpZiel=anker; //Zielknotenzeiger auf Anker setzen
      tmpQuelle=tmpQuelle->next; //Quellknotenzeiger auf nächsten Knoten stetzen
      while(tmpQuelle != NULL) //Quellknoten nicht leer -> Weiter kopieren
      {
         tmpZiel->next=new node; //Neuen eigenen Knoten erstellen
         tmpZiel->next->daten = tmpQuelle->daten; //Datenbereich füllen
         tmpZiel->next->next=NULL; //Zeigerbereich NULL setzen
         tmpQuelle=tmpQuelle->next; //Quellknotenzeiger 1 weiter schieben
         tmpZiel=tmpZiel->next; //Zielknotenzeiger 1 weiter schieben
      }
   }
}
 
Zuletzt bearbeitet:

Kamikaze

Warrior of Sunlight
C++ war die erste objektorientierte Sprache die keinen Garbage Collector hat. C++... kennt sonst jemand irgendeine Sprache bei der es möglich ist Pagefaults zu produzieren? Memory leaks?

Genau das ist das Problem mit C++, es implementiert Strukturen der objektorientierten Programmierung und verzichtet dabei auf all die Vorteile die normalerweise dazugehören. Also eine möchtegern Hochsprache mit den Problemen von Assembler code.
 

HubertB

Bandbreitenverschwender
nakal schrieb:
Schon mal GTK+ gesehen? Vererbung in C. Meiner Meinung nach ist das auch sehr geschickt gemacht.

Ist GTK+ == GTK2? Ich wollte mir das ganze schon länger mal ansehen, bin aber noch nicht wirklich dazu gekommen.

[LoN]Kamikaze schrieb:
C++ war die erste objektorientierte Sprache die keinen Garbage Collector hat. C++... kennt sonst jemand irgendeine Sprache bei der es möglich ist Pagefaults zu produzieren? Memory leaks?

In LISP ging das doch glaub ich mit SETQ sehr schön - allerdings weis ich nicht in wie weit LISP für OOP geeignet ist, das Kapitel hab ich damals nicht gelesen.
 

Kamikaze

Warrior of Sunlight
Man kann mit LISP OO programmieren, aber die Sprache ist nicht explizit dafür ausgelegt. Faktisch sind viele Probleme wie Buffer Overflows und Memory Leaks nur existent, weil damals als C und später C++ entwickelt wurden das ganze konzeptlos zusammengeschustert wurde.

Das ist zumindest in meinen Augen eine historische Tatsache. Viele Programme haben diese Probleme nicht wegen, sondern trotz C/C++ überwunden.
 

nakal

Anfänger
[LoN]Kamikaze schrieb:
C++ war die erste objektorientierte Sprache die keinen Garbage Collector hat.

Empfinde ich nicht unbedingt als schlimm. Ich habe (manchmal) gerne Kontrolle über solche Sachen wie Allokation und Deallaktion.

[LoN]Kamikaze schrieb:
C++... kennt sonst jemand irgendeine Sprache bei der es möglich ist Pagefaults zu produzieren? Memory leaks?

Alle relevanten. Es ist nicht schlimm einen Crash zu haben. Vielleicht mag das für Endbenutzer komisch aussehen. Ich hingegen provoziere einen Crash (FreeBSD übrigens auch, siehe: panic()) wenn auch die kleinste unerwartete Situation eintrifft. Meiner Erfahrung nach kommen da die saubersten Programme bei raus.

Das Problem ist... willst Du nahe an der Maschine arbeiten, also performante Programme machen? Da ist der Prozessor und das Betriebssystem die letzte Instanz, die Dir Fehler meldet. Ist das schlecht? Nein. Ein erfahrener Programmierer schreibt nämlich so, dass er mit den Fehlern was anfangen kann.

Gegen Memory Leaks hilft nichts außer saubere Programmierung. Ein objektorientierter Ansatz hilft hier enorm.

[LoN]Kamikaze schrieb:
Genau das ist das Problem mit C++, es implementiert Strukturen der objektorientierten Programmierung und verzichtet dabei auf all die Vorteile die normalerweise dazugehören. Also eine möchtegern Hochsprache mit den Problemen von Assembler code.

Nichts Schlimmes dabei, finde ich. Ich glaube, dass das die Absicht ist.

(Für mich ist hier Ende des Bikesheds.)
 

dagnu

Well-Known Member
[LoN]Kamikaze schrieb:
Faktisch sind viele Probleme wie Buffer Overflows und Memory Leaks nur existent, weil damals als C und später C++ entwickelt wurden das ganze konzeptlos zusammengeschustert wurde.

Denke mal das u.a. der gute Bjarne Stroustrup's über solche Aussagen nicht
unbedingt erfreut sein wird. Ansonsten sei vieleicht noch erwähnt,
dass C++ nicht vielmehr als eine "C-Erweiterung" ist,
die es gestattet Funktionsverweise in einer Struktur zu speichern,
was dabei rauskommt ist dann die berühmte Klasse :)
Und was dieser kleine Kniff an Möglichkeiten bietet, fasziniert mich heute noch.

mfg dagnu
 

xbit

Well-Known Member
Naja, ein paar mehr Moeglichkeiten bietet C++ schon. Wenn Du Dir "nur" die Moeglichkeiten der Template Programmierung anguckst, hast Du schon erhebliche Vorteile gegenueber C. Und die Moeglichkeiten von Templates bieten auch Java's Generics nicht. ;)
 

HubertB

Bandbreitenverschwender
Neues Problem (Verständnisfrage):

Wenn ich mit int* ptr=new int; mir Speicher hole, muss ich den ja auch irgendwann mal wieder aufräumen, also nen delete ptr; machen.

Aber wie läuft das bei verketteten Listen ab? Reicht es, wenn ich im Destruktor den anker delete oder muss ich explizit vom vorletzten Node aus den letzten löschen, dann wieder den neuen vorletzten Node aufsuchen und dessen Nachfolger löschen usw.??
 

xbit

Well-Known Member
Du holst in einer verketteten Liste ja fuer jeden Knoten Speicher mit new. Diesen musst Du am Ende beim Aufraeumen, z.B. im Destruktor, wieder freigeben. Du musst also nochmal durch die ganze Liste durch und jeden einzelnen Knoten loeschen.
 

Kamikaze

Warrior of Sunlight
Ich programmiere lieber Abstrakt und konzentriere mich auf die Implementierung effizienter Algorithmen. Machinennah heißt für mich plattformabhängig und genau das will ich nicht. Plattformspezifische Optimierungen kann und sollte der Compiler vornehmen.

C/C++ Programme sind nicht effizienter als Programme die in anderen weniger problematischen Sprachen geschrieben sind. Es gibt lediglich mehr davon.

Damit ziehe ich mich aus der Diskussion zurück. Ich denke wenn man damals eine andere Sprache für Unix gewählt hätte wäre die Plattform deutlich weiter.
 

0815Chaot

FreeBSD/sparc64-Tüftler
Was [LoN]Kamikaze schreibt mag ja alles richtig und schön sein; ich kann dem, was Objektorientierung und Abstaktion angeht, grundsätzlich auch zustimmen.

Allerdings: Hinterher ist man immer schlauer! UNIX entstand 1969 in Assembler, und C wurde dann dazu geschaffen, UNIX plattformunabhängig zu machen - das war Anfang der 1970er. Überlege doch mal, was es zu der Zeit sonst noch so an Programmiersprachen gab - das will doch heute auch keiner mehr. Ich habe auf der Uni noch in FORTRAN programmieren gelernt, das war damals einfach die beste Sprache, um mathematische Probleme einigermaßen schnell und effizient in den Kasten zu bekommen. Heute würde ich den Mist nicht mehr anfassen. Trotzdem gibt es noch genug Legacy-Code, sowohl in COBOL und FORTRAN als auch in C und C++.

Du schreibst über Objektorientierung - 1970 war man gerade froh, sich mit prozeduraler Programmierung richtig angefreundet zu haben. Da war C ja eigentlich schon das Beste, was man für UNIX nehmen konnte. Im Laufe der Zeit hat man dann immer mehr drangeflanscht - sowohl an UNIX, als auch an C, bis schließlich einer auch noch ein C mit Klassen auf die Welt loslassen mußte. Heute haben wir einen riesigen Code-Wulst zig unterschiedlicher UNIX-Systeme und du glaubst doch nicht ernsthaft, daß das irgendwer auf eine andere Sprache portieren kann/wird/will. So haben wir eben heute den C-Salat immer noch - und so schnell werden wir den auch nicht los.

[LoN]Kamikaze schrieb:
Ich denke wenn man damals eine andere Sprache für Unix gewählt hätte wäre die Plattform deutlich weiter.
Wenn ... hätte ... wäre - tja, hat man vor 35 Jahren aber eben nicht gemacht, wußte man halt damals auch nicht besser. In 35 Jahren schütteln die Programmierer über unser Objektorientiertes Modell auch den Kopf. Java ist bis dahin sowieso schon längst kaputt gefeatured, denn da wird auch immer munter weiter drangefrickelt...

[LoN]Kamikaze schrieb:
Damit ziehe ich mich aus der Diskussion zurück.
Schade, denn die Gelegenheit wäre jetzt eigentlich günstig, um den VI-vs.-Emacs-Flame noch ins Spiel zu bringen. Ist ja in etwa die gleiche Diskussionsrichtung. :rolleyes:
 

HubertB

Bandbreitenverschwender
Argh, jetzt muss ich hier doch noch mal was drunter setzten: Muss man den Zuweisungsoperator immer einen Wert zurückgeben lassen?

Code:
KSet& KSet::operator=(const KSet b) <- So haben wir es mal gemeinsam programmiert
void KSet::operator=(const KSet& rhs) <- So hab ich das eben gemacht, aber es ist nichts explodiert

Was ist den nun richtig? :confused:
 

xbit

Well-Known Member
Die 1. Variante. Der Zuweisungsoperator liefert immer
Code:
const T &
oder
Code:
T &
zurueck, wobei T Deine Klasse ist.
 

HubertB

Bandbreitenverschwender
Also einfach
Code:
return *this;
nachdem ich die tiefe Kopie erstellt habe?

Macht es eigentlich Sinn, die linke Seite mittels
Code:
this->~KSet();
vorher komplett zu entleeren?
 
Zuletzt bearbeitet:

xbit

Well-Known Member
Du musst, falls es noch um die verkettete Liste geht, Deine Liste loeschen und dann die Liste der rechten Seite kopieren. Wenn Dein Destruktor nur die interne Liste loescht, sollte das so gehen. Allerdings finde ich es etwas weniger verwirrend, nicht den Destruktor an der Stelle aufzurufen, sondern das Loeschen der Liste in eine separate Methode zu packen und diese dann aufzrufen.
 

FierceOne

Kampfmaschine
HubertB schrieb:
Argh, jetzt muss ich hier doch noch mal was drunter setzten: Muss man den Zuweisungsoperator immer einen Wert zurückgeben lassen?

Code:
KSet& KSet::operator=(const KSet b) <- So haben wir es mal gemeinsam programmiert
void KSet::operator=(const KSet& rhs) <- So hab ich das eben gemacht, aber es ist nichts explodiert

Was ist den nun richtig? :confused:
So wie ihr gemeinsam gemacht habt ist es besser. Es erlaubt Konstrukte der Form
Code:
a = b = c = d;
Bei
Code:
a = b;
ist es egal...
 
Oben