3. Problem mit verketteter liste

Problem mit verketteter liste

  • M

    Hallo,

    ich habe mir eine Template-Klasse geschrieben, in der man Objekte beliebigen Types einfügen etc. kann.

    Außerdem habe ich eine Vaterklasse mit 2 Kindklassen. Beide Kindklassen möchte ich in eine verkettete Liste einfügen. Geht dies? Oder muss ich von jeder KLasse eine extra Liste machen?

    Hier meine template:
    Headerfile:

    // liste.h

/*
Klasse LISTE (verkettete Liste Template)
*/
/*
History:
	25.04.2006
*/

template <class T>class LISTE
{
	private:

   	class ELEMENT
      {
      	private:

         	T 					daten;
            /*
            Daten des Elements
            */
            ELEMENT 	*next;
            /*
            Zeiger auf das nächste Element
            */

         public:

         	ELEMENT( T &uebergabe);
            /*
            Standardkonstruktor der Elemente der Liste
            */
            ~ELEMENT();
            /*
            Destruktor
            */
            // Methoden:
            void setDaten( T &uebergabe);
            /*
           	setzen der Daten
            */
				 T &getDaten();
				/*
            Lesen der Daten
            */
            ELEMENT *getNext();
            /*
            gibt das nächste Element zurück
            */
            void setNext( ELEMENT *next_neu );
            /*
            Setzt den Zeiger auf das nächste Element neu
            */

            ELEMENT *sWert( T &wert );
            /*
            Durchsucht alle Elemente nach einem bestimmten wert
            */

            void dahinter_einf( T &wert);
            /*
            fügt hinter sich ein Element ein
            */
      };
      ELEMENT *start;
      /*
      Zeiger auf das Element start wird deklariert
      */

   public:

      LISTE();
      /*
      Standardkonstruktor der Liste: setzt start auf NULL
      */
      ~LISTE();
      /*
      Destruktor der Liste:  gibt die Elemente der Liste frei
      */
      void hinten_einf( T &wert);
      /*
      Methode zum einfügen eines Elements am Ende der Liste
      */
       T *sucheWert( T &wert );
};

    .cpp file:

    /*liste.cpp*/

/*
Klasse LISTE (verkettete Liste Template)
*/
/*
History:
	01.04.2006
*/
#include <stdio.h>
#include <io.h>
#include <stdlib.h>
#include "makros.h"
#include "liste.h"

template<class T>
LISTE<T>::ELEMENT::ELEMENT( T &uebergabe)
{
   daten = uebergabe;
   next = NULL;
}
/*
Standardkonstruktor der Elemente der Liste
*/
template<class T>
LISTE<T>::ELEMENT:: ~ELEMENT()
{
   delete next;
}
/*
Destruktor
Achtung:
Weil das delete next den Destruktor gleich wieder
für das nächste Element aufruft, in dem wiederum ein delete next
steht, wird rekursiv die gesamte Liste ab dem aktuellen Element
freigegeben!
Wenn man nur ein Element freigeben will, aber nicht das nächste,
dann muß man zuvor sein next zu NULL setzen!
*/
// Methoden:
template<class T>
void setDaten( T &uebergabe)
{
   daten = uebergabe;    //setzt die Daten
}
/*
setzen der Daten
*/
template<class T>
 T &getDaten()
{
   return daten;     //gibt die Daten des Elements zurück
}
/*
Lesen der Daten
*/
template<class T>
ELEMENT LISTE<T>::ELEMENT::*getNext()
{
   return next;     //gibt das nächste Element zurück
}
/*
gibt das nächste Element zurück
*/
template<class T>
void LISTE<T>::ELEMENT::setNext( ELEMENT *next_neu )
{
   next = next_neu;
}
/*
Setzt den Zeiger auf das nächste Element neu
*/
template<class T>
ELEMENT *sWert( T &wert )
{
   // Schleife notfalls über alle Elemente:
   ELEMENT *aktuellesElement = this;
   do
   {
      if( aktuellesElement->getDaten()==wert )
      {
         return aktuellesElement;
      }
      aktuellesElement = aktuellesElement->getNext();
   }
   while( aktuellesElement!=NULL );

   return NULL;
}
/*
Durchsucht alle Elemente nach einem bestimmten wert
*/
template<class T>
void dahinter_einf( T &wert)
{
   ELEMENT *uebernaechster = next;  // bisherigers nächstes Element merken

   next = new ELEMENT( wert );  //neues Element schaffen

   next->setNext( uebernaechster ); //bisheriges nächstes Element dahinter setzen
}
template<class T>
LISTE<T>::LISTE()
{
   start = NULL; //start ist zunächst auch das letzte Element, also Adresse NULL
}
/*
Standardkonstruktor der Liste: setzt start auf NULL
*/

template<class T>
LISTE<T>::~LISTE()
{
   delete start; //gibt die Listen ELemente frei
}
/*
Destruktor der Liste:  gibt die Elemente der Liste frei
*/
template<class T>
void LISTE<T>::hinten_einf( T &wert)
{
   if(start == NULL)    // Wenn liste noch leer dann füge es am anfang ein
   {
      start = new ELEMENT (wert);
   }
   else
   {
      ELEMENT *ende = start;
      // Suche nach dem letzten ELement
      while (ende->getNext() != NULL)
      {
         ende = ende->getNext();
      }
      // letztes Element gefunden => dahinter einfügen
      ende->dahinter_einf(wert);
   }
}
/*
Methode zum einfügen eines Elements am Ende der Liste
*/
template<class T>
LISTE<T>::T *sucheWert( T &wert )
{
   // Ist die Liste leer?
   if( start==NULL )
   {
      return NULL;
   }
   else
   {
      ELEMENT *gefunden = start->sWert( wert );
      if(gefunden != NULL)
      {
         return &(gefunden->getDaten());
      }
      else
      {
         return NULL;
      }
   }
}

    Wie kann ich jetzt in der main eine liste erstellen mit objekten der kindklassen?

    so?

    LISTE<VATERKLASSE> liste;

KINDKLASSE objekt;

liste.hinten_einf(objekt);

    so konnte ich die methoden der kindklasse irgendwie nicht mehr aufrufen, kann das sein oder müsste das normal gehen?

    Bin noch Schüler und brauche unbedingt hilfe...

    Gruß Simon

    0
  • A

    Hallo

    Beide Kindklassen möchte ich in eine verkettete Liste einfügen. Geht dies? Oder muss ich von jeder KLasse eine extra Liste machen?

    Wenn die Liste vom Vatertyp ist, kannst du Instanzen von beiden Kindklassen einfügen.

    so konnte ich die methoden der kindklasse irgendwie nicht mehr aufrufen, kann das sein oder müsste das normal gehen?

    Daraus folgt das du auf die Objekte der Liste ausschließlich über die Member zugreifen kannst, die die vaterklase bereitstellt.
    Deshalb mus die Vaterklasse eben alle notwendigen Funktionen als virtuell definiert haben haben, die dann von den Kinderklassen überschrieben werden.
    Siehe Polymorphie.

    bis bald
    akari

    0
  • L

    Du musst in der Liste Zeiger von T speichern, damit das mit der Polymorphie klappt. Denn Du kannst mit "new Kind1(...)" ein Kind1* erzeugen, aber als Vater* in die Liste legen, kein Problem.

    Dass Du die Methoden der Kindklasse auf einem Vater* nicht aufrufen kannst ist völlig normal, das hätte mit Polymorphie auch nichts zu tun. Bei einem guten Design ist in der Vaterklasse alles (notfalls abstrakt, d.h. rein virtuell) definiert was nötig ist um auf die Daten aller Kinder zuzugreifen (nennt man dann "gutes Interface" 😉 )

    class Vater {
  virtual void tuWas() = 0;
};

class Kind1: Vater {
  virtual void tuWas() { tu_was_1iges(); }
};

class Kind2: Vater {
  virtual void tuWas() { tu_was_2iges(); }
};

/* ... */
Vater *objekt = LISTE.sucheWert(...);
objekt->tuWas(); // tut was 1iges oder auch was 2iges, je nachdem was in der Liste mal gespeichert wurde.

    Deine Such-Methode erschliesst sich mir noch nicht so ganz: Du suchst anhand eines T ein T? (Will heissen: Du brauchst das Objekt, was Du suchst, um nach ihm zu suchen?!)

    0
  • M

    Ok erstmal danke.

    Habe jetzt eine Liste vom typ der vaterklasse angelegt. Dann die die Kindklasse hineingefügt.

    So:

    LISTE<VATER> liste; 

for(iI=0;iI<iAnzK1;iI++)
{
     KIND1 s(iSeriennummer);
     liste.hinten_einf(s);
     iSeriennummer++;
}

for(iI=0;iI<iAnzK2;iI++)
{
     KIND2 s(iSeriennummer);
     liste.hinten_einf(s);
     Seriennummer++;
}

    habe die methoden alle virtual gemacht etc.

    nur jetzt will ich die gesamte Liste durchsuchen mit:

    for(iI=0;iI<bla;iI++)
{
     pZeiger_auf_Objekt = liste.sucheWert(VATER(iI));
     ...

    da es in der vaterklasse natürlich keinen konsruktor gibt der so aussieht, kommt eine fehlermeldung.

    kann man die konsrtuktoren auch virtual machen? bzw. welcher wird zuerst aufgerufen etc.

    wie soll ich dieses problem lösen?

    weil ich ja nur mit suche_wert die liste durchgehen kann...

    0
  • F
     

    LISTE<VATER*> liste; // <---

for (int iI=0;iI<iAnzK1;iI++) // <---
{
     KIND1* s = new KIND1(iSeriennummer); // <---
     liste.hinten_einf(s);
     iSeriennummer++;
}
// dto for KIND2

    matrix444 schrieb:

    wie soll ich dieses problem lösen?

    Lass dich von der STL inspirieren. Stell Iteratoren zur Verfügung und benutze std::find_if (oder bilde es zu Lernzwecken nach, wie auch immer).

    0
Anmelden zum Antworten