zum Inhalt springen

verkettete Liste

Links:

http://de.wikipedia.org/wiki/Verkettete_Liste

 

C++ Quellcode

#include <iostream>
using namespace std;


// *****************************
//
// *****************************
class Element
{
public:
    int dat;
    Element *zeiger;
};

// *****************************
//
// *****************************
class Liste
{
public:
    Liste()
    {
        head = new Element;
        tail = new Element;

        head->zeiger = tail;
        tail->zeiger    = head;
    }
    // *********************
    //
    void einfuegen    (int);
    void loeschen      (int);
    void verketten     (Liste*);
    int  suchen          (int);

    void drucken();

    Element *head, *tail, *element;
};

// *****************************
//
// *****************************
void Liste::einfuegen(int x)
{
    Element* neu = new Element;
    neu->dat     = x;

    Element* tmp = head;

    if(head->zeiger == tail)        // leere Liste
    {
        head->zeiger = neu;
        neu->zeiger  = tail;
    }
    else                    // geordnete Liste
    {
        while((tmp->zeiger->dat < neu->dat) && (tmp->zeiger != tail))   
            tmp = tmp->zeiger;
        neu->zeiger   = tmp->zeiger;
        tmp->zeiger   = neu;

        while(tmp->zeiger != tail)    // tail zeigt auf letztes Element
            tmp = tmp->zeiger;
        tail->zeiger = tmp;
    }
}
// *****************************
void Liste::loeschen(int x)
{
    Element* tmp = head;

    while((tmp->zeiger->dat != x) && (tmp->zeiger!=tail))
        tmp = tmp->zeiger;
    if(tmp->zeiger->dat == x)
        tmp->zeiger = tmp->zeiger->zeiger;
}
// *****************************
void Liste::verketten(Liste* L2)
{
    if(L2->head->zeiger != L2->tail)    // Liste L2 nicht leer
        tail->zeiger->zeiger = L2->head->zeiger; // letztes Element zeigt auf erstes L2

    tail = L2->tail;    // tail umbiegen
}
// *****************************
int Liste::suchen(int x)
{
    Element* tmp = head->zeiger;
    while((tmp->dat!=x) && (tmp!=tail))
        tmp = tmp->zeiger;
    if(tmp->dat == x)    return tmp->dat;
    else            return -1;
}
// *****************************
void Liste::drucken()
{
    Element *p=head->zeiger;
    while(p!=tail)
    {
        cout << p->dat << endl;
        p=p->zeiger;
    }
    if(p==tail)
        cout << "-" << endl;
}

// *****************************
//
// *****************************
int main()
{
    Liste L, L2;
    int A[]={4,5,3,9};
    int B[]={1,2,6};

    // Listen erzeugen
    for(int i=0; i<4; i++)
        L.einfuegen(A[i]);
    for(int i=0; i<3; i++)
        L2.einfuegen(B[i]);
    L.drucken();

    // Listen verketten
    L.verketten(&L2);
    L.drucken();

    // aus Listen loeschen
    L.loeschen(3);
    L.drucken();   

    // in Liste suchen
    cout << L.suchen(4) << endl;
}