doppelt verkettete liste

Mr. Blonde

Hallo,

Ich habe ein problem beim löschen in einer doppelt verketteten liste ...

dekl.h

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

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

        Knoten *pFirst;
        int Anzahl;

public:
        Kset();
        ~Kset();

        void show_all();
        void insert_front(int obj);
        void delete_front();
        int anzahlaus();
        void delete_pos(int pos);

};

impl.cpp

#include "dekl5.h"

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

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

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

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

void Kset::delete_front()
{
 if(Anzahl == 0)
 {
  cout<<"Nix da zum loeschen"<<endl;
 }
 if(Anzahl == 1)
 {
  delete pFirst;
  pFirst = NULL;
  Anzahl = 0;
 }

 if(Anzahl > 1)
 {
 Knoten *ptemp = pFirst;
 pFirst = pFirst->pNext;
 delete ptemp;
 Anzahl--;
 }
}

int Kset::anzahlaus()
{
 return Anzahl;
}

void Kset::delete_pos(int pos)
{
 if((Anzahl == 0)||(pos>=Anzahl))
  {
   cout<<"Nichts da zum loeschen"<<endl;
  }
 if(pos==0)
  {
   Knoten *ptemp = pFirst;
   pFirst = pFirst->pNext;
   ptemp->Inhalt = 0;
   Anzahl--;
  }
 else
 {
  Knoten *ptemp = pFirst;
  for(int i; i<pos; i++)
   ptemp = ptemp->pNext;

  ptemp->pLast->pNext = ptemp->pNext;
  if(ptemp->pNext != NULL)
   ptemp->pNext->pLast = ptemp->pLast;

  ptemp->Inhalt = 0;
  delete ptemp;
  Anzahl--;
 }
}

main.cpp

#include "dekl5.h"

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{

Kset k;

k.insert_front(1);
k.insert_front(2);
k.insert_front(3);
k.insert_front(4);
k.insert_front(5);

cout<<"Ausgabe der Liste: "<<endl;
k.show_all();

k.delete_front();
cout<<"\n\nAusgabe der Liste - erstes Element geloescht "<<endl;
k.show_all();

cout<<"\n\nAn Position loeschen "<<endl;
k.delete_pos(1);

k.show_all();

        getch();
        return 0;
}
//---------------------------------------------------------------------------

wenn ich die methode delete_pos() aufrufe und ihr sage, dass sie z.B. den 2. Knoten löschen soll, stürzt das Programm mit einer "EAccess Violation" ab ... wo hab ich den fehler gemacht?

thx

CStoll

Du müsstest im insert_front() auf jeden Fall noch den Vorgänger-Zeiger des alten Front-Elements auf das neue umbiegen, sonst kannst du darauf beim Löschen nicht zugreifen. (schau dir mal die Elemente im Debugger an, dann siehst du, was ich meine)

PS: Wenn es dir nur um das Ergebnis geht, nimm lieber std::list statt etwas eigenes zu basteln.

Mr. Blonde

okay - danke

Aber mal noch ne Frage:
Kann ich bei der doppelt verketteten Liste auch noch nen Zeiger auf den letzten Knoten festlegen ... also so:

class Kset
{
private:
        struct Knoten
        {
         int Inhalt;
         Knoten *pNext;   // Zeiger auf nachfolger
         Knoten *pfront;  // Zeiger auf vorgänger
        };

        Knoten *pFirst;   // Zeiger auf ersten Knoten in Liste
        Knoten *pLast;    // Zeiger auf letzten Knoten in Liste
        int Anzahl;

stat

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

        Knoten *pFirst;
        int Anzahl;

thx im voraus

CStoll

Ja, kannst du - nur solltest du diesen Zeiger bei deinen insert- und remove-Methoden auch mit berücksichtigen.

Mr. Blonde

jup - mach ich

danke