3. Listenkopf und Sentinel

Listenkopf und Sentinel

  • M

    Hallo,

    ich habe ein problem beim Listekopf und Sentinel ... ich weiß zwar, dass es leere Knoten zur begrenzung der Liste sind - aber nicht wie man sie deklariert bzw. implementiert ...

    dekl

    #include <iostream>
#include <conio.h>

class Kset
{
private:
        struct Knoten
        {
         int Inhalt;
         Knoten *pNext;
        };

        int Anzahl;
        Knoten *pFirst;
        Knoten *pLast;

public:
        Kset();
        Kset(const Kset & obj);
        ~Kset();

        void insert_front(int obj);

    impl

    #include "dekl11.h"

//Konstruktor///////////////////////////////////////////////////////////////////

Kset::Kset()
{
 Anzahl = 0;
 pFirst = pLast = NULL;
}

//Dekonstruktor/////////////////////////////////////////////////////////////////

Kset::~Kset()
{
 Knoten *ptemp = pFirst;
 for(; Anzahl>0;)
 {
  pFirst = pFirst->pNext;
  delete ptemp;
  ptemp = pFirst;
  Anzahl--;
 }
}

//Kopierkonstruktor/////////////////////////////////////////////////////////////

Kset::Kset(const Kset & obj)
{
 this->Anzahl = 0;
 pFirst = pLast = NULL;
 Knoten *ptemp = obj.pFirst;
 for(int anz = obj.Anzahl; anz != 0; anz--)
 {
  this->insert_front(ptemp->Inhalt);
  ptemp = ptemp->pNext;
 }
}

void Kset::insert_front(int obj)
{
 if(Anzahl == 0)
 {
  pFirst = new Knoten;
  pFirst->Inhalt = obj;
  pFirst->pNext = NULL;
  pLast = pFirst;
 }
 else
 {
  Knoten *pNew = new Knoten;
  pNew->Inhalt = obj;
  pNew->pNext = pFirst;
  pFirst = pNew;
 }
Anzahl++;
}

    Wie kann ich dies verwirklichen?

    0
  • G

    Hallo,

    Mr. Blonde schrieb:

    ich habe ein problem beim Listekopf und Sentinel ... ich weiß zwar, dass es leere Knoten zur begrenzung der Liste sind - aber nicht wie man sie deklariert bzw. implementiert ...

    es sind ganz normale Listenelemente. Beim letzten Element ist der next - Zeiger 0, das begrenzt die Liste. Fertig. 🙂

    MfG

    GPC

    0
  • M

    ooookay ^^

    ist das wirklich nicht mehr?

    0
  • C
    Mod

    GPC schrieb:

    Hallo,

    Mr. Blonde schrieb:

    ich habe ein problem beim Listekopf und Sentinel ... ich weiß zwar, dass es leere Knoten zur begrenzung der Liste sind - aber nicht wie man sie deklariert bzw. implementiert ...

    es sind ganz normale Listenelemente. Beim letzten Element ist der next - Zeiger 0, das begrenzt die Liste. Fertig. 🙂

    MfG

    GPC

    ein andere möglichkeit ist eine zirkuläre liste. in dem falle kannst du dein sentinel einfach in das objekt selbst einbetten und verzichtest auf explizite first und last zeiger.

    0
  • M

    Und wie würde die auf mein Beispiel projeziert aussehen?
    Das ist doch, wenn ich einen festen Anfangs- und Endpunkt habe und dann nur zwischen diesen einfüge, oder?

    Oder ist das das gleiche wie eine Ringverkettete Liste?

    0
  • M

    läuft das ungefähr so mit sentinel und listenkopf?

    dekl

    #include <iostream>
#include <conio.h>

class Kset
{
private:
        struct Knoten
        {
         int Inhalt;
         Knoten *pNext;
        };

        Knoten *Kopf;
        Knoten *Sentinel;

        Knoten *pFirst;
        Knoten *pLast;
        int Anzahl;

public:
        Kset();
        ~Kset();

        void insert_front(int obj);
        void display();

};

#include "impl.hpp"

    impl

    //Konstruktor///////////////////////////////////////////////////////////////////

Kset::Kset()
{
 Anzahl = 0;
 Kopf = new Knoten;
 Kopf->Inhalt = 0;
 Sentinel = new Knoten;
 Sentinel->Inhalt = 0;
 Kopf->pNext = Sentinel;
 Sentinel->pNext = NULL;
}

//Dekonstruktor/////////////////////////////////////////////////////////////////

Kset::~Kset()
{
 Knoten *ptemp = pFirst;
 for(; Anzahl>0;)
 {
  pFirst = pFirst->pNext;
  delete ptemp;
  ptemp = pFirst;
  Anzahl--;
 }
}

//insert_front//////////////////////////////////////////////////////////////////

void Kset::insert_front(int obj)
{
 Knoten *pNew = new Knoten;
 pNew = pFirst;
 Kopf->pNext = pNew;
 pNew->Inhalt = obj;
 pNew->pNext = Sentinel;
 Anzahl++;
}

void  Kset::display()
{
 Knoten *pTemp = pFirst;
 for(int anz=Anzahl; anz>0;anz--)
 {
  cout<<pTemp->Inhalt<<" ";
  pTemp = pTemp->pNext;
 }
}
    0
  • J

    Ich würde Listenkopf und sentinel als ein Element machen. Der head *ist* der Sentinel. Außerdem zirkulär implementieren, also

    kopf->next = kopf;

    0

  • Mr. Blonde schrieb:

    Kset::~Kset()
{
 Knoten *ptemp = pFirst;
 for(; Anzahl>0;)
 {
  pFirst = pFirst->pNext;
  delete ptemp;
  ptemp = pFirst;
  Anzahl--;
 }
}

    wird klassisch eher so gemacht:

    Kset::~Kset()
{
    Knoten *ptemp = pFirst;
    Knoten *pcur;
    while( ptemp ) {
        pcur = ptemp;        
        ptemp = ptemp->pNext;        
        delete pcur;
    }
}

    Mr. Blonde schrieb:

    void Kset::insert_front(int obj)
{
 Knoten *pNew = new Knoten;
 pNew = pFirst;
 Kopf->pNext = pNew;
 pNew->Inhalt = obj;
 pNew->pNext = Sentinel;
 Anzahl++;
}

    Hier produzierst du mit

    Knoten *pNew = new Knoten;
pNew = pFirst;

    Memoryleaks ohne ende.

    Greetz, Swordfish

    0
  • ?

    Danke 🙂

    Wie kann ich denn die Memory Leaks vermeiden?

    0

  • Du willst doch nur eine einfach verkettete Liste!?

    zB. so:

    #include <iostream>
#include <fstream>

class list {

    friend std::ostream& operator<<( std::ostream &os, list &d );
    friend std::istream& operator>>( std::istream &is, list &d );

    private:

        struct item {

            int data;
            item *next;

        } *head;

    public:

        list( );
        ~list( );
        void insert_front( int d );
};

std::ostream& operator<<( std::ostream &os, list &d )
{
    list::item *cur_item = d.head;

    for( unsigned long i = 1; cur_item; ++i ) {

        os.width( 3 );
        os.fill( '0' );
        os << i << ": ";
        os << cur_item->data << std::endl;
        cur_item = cur_item->next;
    }

    return os;
}

std::istream& operator>>( std::istream &is, list &d )
{
    int input;

    do {
        std::cout << "Daten: ";
        is >> input;

        if( is.fail( ) ) {

            is.clear( );
            is.ignore( is.rdbuf( )->in_avail( ) );
            std::cout << std::endl << "Falsche eingabe!" << std::endl;

        } else if( input != 0 ) {

            d.insert_front( input );
        }

    } while( input != 0 );

    return is;
}

list::list( ) : head( 0 )
{
}

list::~list( )
{
    item *cur = head;
    item *tmp;

    while( cur ) {

        tmp = cur;
        cur = cur->next;
        delete tmp;
    }
}

void list::insert_front( int d )
{
    item *new_item = new item;
    new_item->data = d;

    if( !head ) {

        new_item->next = 0;
        head = new_item;
        return;
    }

    item *old_head = head;
    head = new_item;
    head->next = old_head;
}

using namespace std;

int main( )
{
    list l;

    cin >> l;
    cout << endl << l << endl;
}

    Greetz, Swordfish

    0
  • M

    Hallo nochmal 🙂

    ich hab das jetzt so gelöst? Ist das halbwegs richtig?

    dekl

    #include <iostream>
#include <conio.h>

class Kset
{
private:
        struct Knoten
        {
         int Inhalt;
         Knoten *pNext;
        };

        Knoten *Kopf;
        Knoten *Sentinel;

        int Anzahl;

public:
        Kset();
        ~Kset();

        void insert_front(int obj);
        void insert_back(int obj);
        void insert_pos(int obj, int pos);
        void delete_front();
        void delete_back();
        void display();

        friend ostream & operator << (ostream &os, Kset & kl);

};

#include "impl.hpp"

    impl

    //Konstruktor///////////////////////////////////////////////////////////////////

Kset::Kset()
{
 Anzahl = 0;
 Kopf = new Knoten;
 Kopf->Inhalt = 0;
 Sentinel = new Knoten;
 Sentinel->Inhalt = 0;
 Kopf->pNext = Sentinel;
 Sentinel->pNext = NULL;
}

//Dekonstruktor/////////////////////////////////////////////////////////////////

Kset::~Kset()
{
 while(Kopf->pNext != Sentinel)
 {
  Knoten *ptemp = Kopf->pNext;
  Kopf->pNext = Kopf->pNext->pNext;
  delete ptemp;
  Anzahl--;
 }
 delete Kopf;
 delete Sentinel;
}

//insert_front//////////////////////////////////////////////////////////////////

void Kset::insert_front(int obj)
{
    {
        Knoten *pNew = new Knoten;
        pNew->Inhalt = obj;
        pNew->pNext = Kopf->pNext;
        Kopf->pNext = pNew;
        Anzahl++;
    }
}

//insert_back///////////////////////////////////////////////////////////////////

void Kset::insert_back(int obj)
{
 Knoten *pNew = new Knoten;
 pNew->Inhalt = obj;
 if(Anzahl == 0)
    {
        pNew->pNext = Kopf->pNext;
        Kopf->pNext = pNew;
    }
 else
    {
 Knoten *pTemp = Kopf->pNext;
 while(pTemp->pNext != Sentinel)
    {
        pTemp = pTemp->pNext;
    }
 pTemp->pNext = pNew;
 pNew->pNext = Sentinel;
    }
 Anzahl++;
}

void Kset::delete_front()
{
 if(Kopf->pNext ==  Sentinel)
    {
        cout<<"Die Liste ist leer"<<endl;
        return;
    }
 if(Anzahl == 1)
    {
        cout<<"Liste ist nun leer"<<endl;
        Knoten *pTemp = Kopf->pNext;
        delete pTemp;
        Kopf->pNext = Sentinel;
        Anzahl = 0;
    }
 else
    {
        Knoten *pTemp = Kopf->pNext;
        cout<<"Der Knoten mit dem Inhalt "<<pTemp->Inhalt<<" wurde geloescht"<<endl;
        Knoten *pHilf = Kopf->pNext->pNext;
        Kopf->pNext = pHilf;
        pTemp->pNext = NULL;
        delete pTemp;
        Anzahl--;
    }
}

void Kset::delete_back()
{
 if(Kopf->pNext ==  Sentinel)
    {
        cout<<"Die Liste ist leer"<<endl;
        return;
    }
 if(Anzahl == 1)
    {
        cout<<"Liste ist nun leer"<<endl;
        Knoten *pTemp = Kopf->pNext;
        delete pTemp;
        Kopf->pNext = Sentinel;
        Anzahl = 0;
    }
 else
    {
        Knoten *pTemp = Kopf->pNext;
        Knoten *pHilf = Kopf->pNext;
        while(pTemp->pNext->pNext != Sentinel)
           {
                pTemp = pTemp->pNext;
           }
        pHilf = pTemp->pNext;
        cout<<"Der Knoten mit dem Inhalt "<<pHilf->Inhalt<<" wurde geloescht"<<endl;
        delete pHilf;
        pTemp->pNext = Sentinel;
        Anzahl--;
    }
}

    Danke für eure Hilfe 🙂

    0

  • Hab's durchgesehen:

    Header:

    #include <iostream>
#include <conio.h>
#include <fstream> // fehlte

class Kset {
    private:
        struct Knoten {
            int Inhalt;
            Knoten *pNext;
        };
        Knoten *Kopf;
        Knoten *Sentinel;
        int Anzahl;
    public:
        Kset();
        ~Kset();

        void insert_front(int obj);
        void insert_back(int obj);
        void insert_pos(int obj, int pos);
        void delete_front();
        void delete_back();
        void display();

    friend std::ostream & operator << (std::ostream &os, Kset & kl);
    //     ^
    // da man in Headerdateien keine Namespaces öffnen sollte, hier mit angeben
    // BTW: wo hast den << denn implementiert!?
};

    Implementation:

    using namespace std; // fehlte

//Konstruktor///////////////////////////////////////////////////////////////////
// ^Kommentar fehlte ;))
Kset::Kset()
{
    Anzahl = 0;
    Kopf = new Knoten; // wieso erstellst du hier schon ein element?
    Kopf->Inhalt = 0;
    Sentinel = new Knoten; // wofür soll dieser "Sentinel" eigentlich gut sein!?
    Sentinel->Inhalt = 0;
    Kopf->pNext = Sentinel;
    Sentinel->pNext = NULL; // NULL == 0
    // so, jetzt hast du eine "leere" Liste mit 2 Elementen ;)
}

//Dekonstruktor/////////////////////////////////////////////////////////////////
// ^ Das Ding heißt Destructor oder kurz d-tor
Kset::~Kset()
{
    while(Kopf->pNext != Sentinel)
    {
        Knoten *ptemp = Kopf->pNext;
        Kopf->pNext = Kopf->pNext->pNext;
        delete ptemp;
        Anzahl--; // kann man sich sparen, da auf Anzahl nach zerstörung der liste
                  // sowieso nicht mehr zugegriffen werden kann.
    }
    delete Kopf;
    delete Sentinel;
}

//insert_front//////////////////////////////////////////////////////////////////

void Kset::insert_front(int obj)
{
    { // wofür die geschweiften Klammern?
        Knoten *pNew = new Knoten;
        pNew->Inhalt = obj;
        pNew->pNext = Kopf->pNext;
        Kopf->pNext = pNew;
        Anzahl++;
    }
}

//insert_back///////////////////////////////////////////////////////////////////

void Kset::insert_back(int obj)
{
    Knoten *pNew = new Knoten;
    pNew->Inhalt = obj;
    if(Anzahl == 0) // entspricht Kopf->pNext == Sentinel
    {
        pNew->pNext = Kopf->pNext; // entspricht pNew->pNext = Sentinel
        Kopf->pNext = pNew;
    }
    else
    {
        Knoten *pTemp = Kopf->pNext;
        while(pTemp->pNext != Sentinel)
        {
            pTemp = pTemp->pNext;
        }
        pTemp->pNext = pNew;
        pNew->pNext = Sentinel;
    }
    Anzahl++;
}

void Kset::delete_front()
{
    if(Kopf->pNext == Sentinel) // witzkeks... entspricht Anzahl == 0
    {
        cout<<"Die Liste ist leer"<<endl;
        return;
    }

    if(Anzahl == 1)
    {
        cout<<"Liste ist nun leer"<<endl;
        /*
        Knoten *pTemp = Kopf->pNext;
        delete pTemp;
        Kopf->pNext = Sentinel;
        */

        // oder einfach:
        delete Kopf->pNext;
        Kopf->pNext = Sentinel;
        // kommt ohne pTemp aus.

        Anzahl = 0;
    }
    else
    {
        Knoten *pTemp = Kopf->pNext;
        cout<<"Der Knoten mit dem Inhalt "<<pTemp->Inhalt<<" wurde geloescht"<<endl;

        /*
        Knoten *pHilf = Kopf->pNext->pNext;
        Kopf->pNext = pHilf;
        */

        // oder einfach:
        Kopf->pNext = Kopf->pNext->pNext;
        // oder auch:
        // Kopf->pNext = pTemp->pNext;

        pTemp->pNext = NULL; // was bring das, wenn du pTemp in der
        delete pTemp;        // nächsten Zeile sowieso löschst?

        Anzahl--;
    }
}

void Kset::delete_back()
{
    if(Kopf->pNext ==  Sentinel)
    {
        cout<<"Die Liste ist leer"<<endl;
        return;
    }

    if(Anzahl == 1)
    {
        /*
        cout<<"Liste ist nun leer"<<endl;
        Knoten *pTemp = Kopf->pNext;
        delete pTemp;
        Kopf->pNext = Sentinel;
        Anzahl = 0;
        */

        // oder einfach:
        delete_front( );
    }
    else
    {
        Knoten *pTemp = Kopf->pNext;

        // Knoten *pHilf = Kopf->pNext; wofür diese Zuweisung?
        /*        
        while(pTemp->pNext->pNext != Sentinel)
        {
            pTemp = pTemp->pNext;
        }
        Knoten *pHilf = pTemp->pNext;
        cout<<"Der Knoten mit dem Inhalt "<<pHilf->Inhalt<<" wurde geloescht"<<endl;
        delete pHilf;
        pTemp->pNext = Sentinel;
        */

        // oder einfacher:
        while( pTemp->pNext->pNext != Sentinel )
            pTemp = pTemp->pNext;
        cout << "DerKnoten mit dem Inhalt " << pTemp->Inhalt << " wurde gelöscht" << endl;
        delete pTemp->pNext;
        pTemp->pNext = Sentinel;

        Anzahl--;
    }
}

    Greetz, Swordfish

    0
  • M
     

    Kset::Kset()
{
    Anzahl = 0;
    Kopf = new Knoten; // wieso erstellst du hier schon ein element?
    Kopf->Inhalt = 0;
    Sentinel = new Knoten; // wofür soll dieser "Sentinel" eigentlich gut sein!?
    Sentinel->Inhalt = 0;
    Kopf->pNext = Sentinel;
    Sentinel->pNext = NULL; // NULL == 0
    // so, jetzt hast du eine "leere" Liste mit 2 Elementen ;)
}

    Danke erstmal 🙂

    aber wie soll ich den Sentinel sonst implementieren?

    0
Log in to reply