3. Suche in Listen

Suche in Listen

  • M

    Hallo, ich habe folgendes Programm:

    dekl.

    #ifndef dekl_h
#define dekl_h

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

class Klasse;

class Klasse
{

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

        Knoten *pFirst;
        Knoten *pLast;
        int Anzahl;
public:
        Klasse();
        Klasse(const Klasse &obj);
        ~Klasse();

        void push_front(int obj);
        void push_place(int obj,int place);
        void push_back(int obj);
        void pop_front();
        void pop_place(int place);
        void pop_back();
        int get_front();
        int get_back();

        friend ostream& operator<<(ostream &os, Klasse &obj);
        friend istream& operator>>(istream &is, Klasse &obj);

        void KlasseAusgeben();
};

#endif

    impl.

    #include "dekl.h"

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

//Kopierkonstruktor
Klasse::Klasse(const Klasse &obj)
{
  this->Anzahl = 0;
  pFirst = pLast = NULL;

  Knoten *ptemp = obj.pFirst;
  for(int anz = obj.Anzahl; anz != 0; anz --)
  {
   this->push_front(ptemp->Inhalt);
   ptemp = ptemp->pNext;
  }
 }

// Dekonsturktor

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

// Einfuegen vorne

void Klasse::push_front(int obj)
{
        if(Anzahl==NULL)         // wenn noch keiner da ist...
        {
                pFirst = new Knoten;      // Zeiger wird auf Speicheradresse festgelegt...
                pFirst->Inhalt = obj;     // wird objekt in speicher geschrieben
                pFirst->pNext = NULL;     // da wir nur 1 Knoten besitzen, wird der Next Zeiger NULL gesetzt
                pLast = pFirst;           // da nur 1, ist der letzte gleich dem ersten
        }
        else                               // wenn die Anzahl nicht 0 ist
        {                                  // Knoten ist die Strucktu innerhalb der Klasse...
                Knoten *pNew = new Knoten; // Erstellen eines neuen Zeigers, und zuweissung des Speichers
                pNew->Inhalt = obj;        // Neuer Knoten wird über Zeiger PNew mit Inhalt gefühlt-->Obj
                pNew->pNext = pFirst;      // Der PNext Zeiger vom vorne einzufügenden Knoten soll den "ehemaligen pFirst "ersten" Konoten zeigen
                pFirst = pNew;             // Der neue Knoten wird der erste Knoten der Liste...
        }
        Anzahl ++;
}

// An Postition einfügen

void Klasse::push_place(int obj, int place)
{
        if(Anzahl==NULL)
        {
                pFirst = new Knoten;
                pFirst->Inhalt = obj;
                pFirst->pNext = NULL;
                pLast = pFirst;
        }

        if(Anzahl<=place && Anzahl!=NULL)
        {
                Knoten *pNew = new Knoten;
                pNew->Inhalt = obj;
                pNew->pNext = NULL;
                pNew->pNext = pNew;
                pLast = pNew;
        }

        if(Anzahl>place && Anzahl!=NULL && place > -1)
        {
                Knoten *pNew = new Knoten;
                pNew->Inhalt = obj;
                pNew->pNext = NULL;

                if(place == 0)
                {
                        pNew->pNext = pFirst;
                        pFirst = pNew;
                }
                else
                {
                        Knoten*ptemp = pFirst;
                        for(; place > 1;place--)
                                ptemp=ptemp->pNext;

                        pNew->pNext = ptemp->pNext;
                        ptemp->pNext = pNew;
                }
        }
        Anzahl++;
}

// hinten hinhaengen

void Klasse::push_back(int obj)
{
        if(Anzahl==NULL)
        {
                pFirst = new Knoten;         // Gleich wie einfuegen vorne...da Anzahl = 0, d.h. nix in Liste...
                pFirst->Inhalt = obj;
                pFirst->pNext = NULL;
                pLast = pFirst;
        }
        else
        {
                Knoten *pNew = new Knoten;    // neuer Speicher für Knoten..zeiger zeigt druff
                pNew->Inhalt = obj;           // Inhalt wird eingefügt
                pNew->pNext = NULL;           // da hinten angefügt, wird der Zeige auf das Nächste 0 gesetzt...
                pLast->pNext = pNew;          //
                pLast = pNew;                 // der neue wird dem letzten zugewiesen
        }
        Anzahl++;
}

// lustiges löschen des ersten Elementes

void Klasse::pop_front()
{
        if(Anzahl == 1)
        {
        cout<<"Erstes Klassenelement "<<pFirst->Inhalt<<" geloescht! "<<endl<<endl;
         delete pFirst;
         pFirst = pLast = NULL;
         Anzahl = 0;
        }
        if (Anzahl > 1)
        {
        cout<<"Erstes Klassenelement "<<pFirst->Inhalt<<" geloescht! "<<endl<<endl;
         Knoten *ptemp = pFirst;
         pFirst = pFirst->pNext;
         delete ptemp;
         Anzahl--;
         }
}

// an genauer Postition löschen

void Klasse::pop_place(int place)
{
  if(Anzahl==NULL)
  {
        cout<<"Klasse ist leer! ";
  }

  if((Anzahl-1) <= place && Anzahl != NULL)
  {
     this->pop_back();
     Anzahl--;
  }

  if((Anzahl -1) > place && Anzahl != NULL && place > -1)
  {
        if(place == 0)
        {
         Knoten * ptemp = pFirst;
         pFirst = pFirst->pNext;
         delete ptemp;
        }
        else
        {
          Knoten *ptempV =pFirst;
          Knoten *ptempL =pFirst;

          for( ; place >1;place--)
          ptempV = ptempV->pNext;

          ptempL = ptempV->pNext;
          ptempV->pNext = ptempV->pNext->pNext;

          delete ptempL;
        }
        Anzahl--;
  }
}

//letztes löschen

void Klasse::pop_back()
{
        if(Anzahl ==1)
        {
        cout<<"Letztes Element "<<pFirst->Inhalt<<" wird gelöscht!"<<endl;
         delete pFirst;
         pFirst= pLast = NULL;
         Anzahl = 0;
        }
        if(Anzahl >1)
        {
        Knoten *ptemp= pFirst;
        while(ptemp->pNext != pLast)
        ptemp = ptemp->pNext;
        cout<<"Letztes Klassenelement "<<pLast->Inhalt<<" geloescht! "<<endl<<endl;

        delete pLast;
        pLast = ptemp;
        Anzahl--;
        }
}

// Zeige Erstes Element

int Klasse::get_front()
 {
 return pFirst->Inhalt;
 }

// letztes Element

int Klasse::get_back()
{
 return pLast->Inhalt;
}

// Klasse Ausgeben

void Klasse::KlasseAusgeben()
 {
  Knoten *ptemp = pFirst;
  cout<<"Ausgabe der Klasse: "<<endl<<endl;
  for(int anz = Anzahl; anz !=0; anz--)
   {
    cout<<ptemp->Inhalt<< "   ";
    ptemp = ptemp->pNext;
    }
 cout<<endl<<endl;
 }

//überladen von was auch immer

ostream& operator<< (ostream &os, Klasse &obj)
{
 {
 if(obj.Anzahl == NULL)
 os<<"Klasse Leer, lala...!"<<endl<<endl;
 }

 os<<"Ausgabe der Klasse mit Operator: "<<endl<<endl;

 Klasse::Knoten *ptemp = obj.pFirst;
 for(int anz = obj.Anzahl; anz !=0; anz--)
  {
   os<<ptemp->Inhalt<<"   ";
   ptemp = ptemp->pNext;
  }
  os<<endl<<endl;
  return os;
};

istream& operator>>(istream &is, Klasse &obj)
{
cout<<"Eingabe: ";
int temp;
is>>temp;
obj.push_back(temp);
return is;
}

    main

    #include "impl.cpp"

int main()
{
        Klasse L;

        L.push_front(33);
        L.push_front(23);
        L.push_front(45);
        L.push_front(66);
        L.push_front(22);
        L.push_front(11);
        L.push_back(44);
        L.push_back(55);
        L.push_back(66);

        cout<<L.get_front()<<endl;
        cout<<L.get_back()<<endl<<endl;
        L.KlasseAusgeben();
        cout<<endl;

        L.pop_front();
        L.KlasseAusgeben();
        cout<<endl;

        L.pop_back();
        L.KlasseAusgeben();
        cout<<endl;

        cout<<L;

        cin>>L;
        fflush(stdin);
        cout<<L;

        L.push_place(000,2);
        L.push_place(333,3);
        L.push_place(999,4);
        cout<<L;

        L.pop_place(0);
        cout<<L;
        L.pop_place(1);
        cout<<L;
        L.pop_place(4);
        cout<<L;

        Klasse L2(L);

        Klasse *pL3 = new Klasse(L2);

        pL3->pop_front();
        pL3->pop_back();
        L2.push_front(0);
        L.pop_front();

        cout<<L;
        cout<<L2;
        cout<<*pL3;

        cout<<"Ende "<<endl;
        getch();
        return 0;
}

    Nun meine Frage:
    wie kann ich eine suche innerhalb der Liste realisieren?

    Danke im voraus 🙂

    0
  • D

    indem du die schleife durchläufst und den wert mit if vergleichst.

    0
  • W

    Mr. Blonde schrieb:

    wie kann ich eine suche innerhalb der Liste realisieren?

    Am besten mit dem Standard-Algorithmus std::find bzw. std::find_if. Das setzt aber die Existenz von Standard-konformen Iteratoren voraus, die über Deine Liste laufen können.

    Zum Beispiel so:

    #include <iterator>     // iterator<>

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

        Knoten *pFirst;
        Knoten *pLast;
        int Anzahl;
public:
    class Iterator;
    friend Iterator;
    class Iterator : public std::iterator< std::forward_iterator_tag, int >
    {
    public:
        explicit Iterator( Knoten* p = 0 ) : m_p( p ) {}
        // --   Inkrement
        Iterator& operator++() 
        {
            m_p = m_p->pNext;
            return *this;
        }
        Iterator operator++( int )
        {
            Iterator tmp( *this );
            this->operator++();
            return tmp;
        }
        // --   Vergleich
        bool operator==( const Iterator& b ) const
        {
            return m_p == b.m_p;
        }
        bool operator!=( const Iterator& b ) const
        {
            return !(*this == b);
        }
        // --   Element Zugriff
        int& operator*() const
        {
            return m_p->Inhalt;
        }
        int* operator->() const
        {
            return &(m_p->Inhalt);
        }
    private:
        Knoten* m_p;
    };
    typedef Iterator iterator;

    Iterator begin() { return Iterator( pFirst ); }
    Iterator end() { return Iterator(); }

        Klasse();
        Klasse(const Klasse &obj);
        ~Klasse();
    // usw. wie gepostet

    Die Anwendung 'Suchen' geht dann wie folgt:

    #include <algorithm>    // std::find
#include <iostream>

int main()
{
    using namespace std;
    Klasse l;
    l.push_back( 9 );
    l.push_back( 7 );
    Klasse::iterator i = std::find( l.begin(), l.end(), 7 );
    if( i != l.end() )
    {
        cout << "Element " << *i << " gefunden" << endl;
    }
    return 0;
}

    Der Vorteil von Iteratoren ist, dass dann auch andere std-Algorithmen wie z.B. find_if, distance, copy, min_element usw. mit Deiner Klasse zusammen arbeiten können.

    Bem.: die Ableitung von std::iterator< std::forward_iterator_tag, .. > ist für die Algorithmen notwendig, wenn sie die Iterator-Kategorie ermitteln müssen; wie z.B. std::distance.

    Gruß
    Werner

    0
Anmelden zum Antworten