verkettete Liste

SideWinder

Die Größe der Liste hast du entweder gespeichert oder du läufst einfach einmal vom head bis zum tail durch und zählst jedesmal i um eins hoch:

// Pseudocode \\
int i = 0;
ptr runner = head;
while(runner != nil)
{
    ++i;
    ++runner;
}

return i;

Item an beliebiger Stelle geht genauso, bloß gibst du nicht den Counter zurück sondern die Position an der Runner steht:

params: int pos

int i = 0;
ptr runner = head;
while(runner != nil)
{
    if(i == pos)
        return *runner;

    ++i;
    ++runner;
}

return notfound;

MfG SideWinder

fluxy

Hallo,

ich habe selbst mal eine verkette Liste als Klasse Programmiert. Am besten machst du das sogar als Klassentemplate, da du sonst nur einen Typ in der Liste speichern kannst.

Im Prinzip brauchst du dafür 2 Hilfsklassen bzw. Strukturen. Die eine Struktur representiert die Liste selbst, also speichert alles, was die Liste selber braucht. Wenn du es wirklich richtig objektorientiert machen willst, verzichtest du auf Strukturen und legst eine Klasse an die so ähnlich aussieht wie die folgende:

class ListInfo
{
	public:
		T* getBeginAddress (void);
		T* getEndingAddress (void);

		void setBeginAddress (T* address) const;
		void setEndAddress (T* address) const;

	private:
		T* ptr_begin;
		T* ptr_end;
	protected:
	};

Dann machst du dir eine zweite Ähnliche Klasse, die folgende Elemente enthällt (habe jetzt keine Lust noch mal alles zu schreiben)

* Zeiger auf vorheriges Element (für das erste Element also NULL)
* Zeiger auf das nächste Element (für das letzte Element also NULL)
* Zeiger bzw. direkte Variable über das Template auf die Daten

Die beiden Klassen instanzierst du in deiner Hauptklasse so, dass im Konstruktor eine ListInfo instanz erzeugt und gefüllt wird. Jedesmal wenn du neue Daten hinzufügst, füllst du eine neue Knoteninstanz (die 2. Klasse mit den beiden pointern und den Daten). Ich habe das damals als Struktur gemacht, sollte aber als Klasse auch gehen.

Gruß Sebastian

Danke für die Hilfe!
Ich werde das mal ausprobieren. Über weitere Hinweise wäre ich natürlich sehr dankbar.

Gruß

sebastian21

fluxy

ja klar ich werde im Laufe des Tages immer wieder mal reinschauen wie es dir geht. Allerdings müsstest du dann auch fragen, allgemeine Hinweise habe ich dir eigentlich gegeben, die Klassenstruktur sollte klar sein. Du musst dann natürlich Methoden definieren fürs einfügen, löschen, auslesen etc.

Gruß Sebastian

Ich habe nun einiges programmiert (mit Hilfe), jedoch kann ich mit der funktion loeschen nicht das erste Element löschen. Das Einfügen an einer beliebigen Stelle habe ich auch noch nicht hinbekommen. Kann mir damit noch jemand helfen?

#include <iostream>
using namespace std;

class Kette {

    private:
    int a,b;
    static int counter;
    static Kette* start;
    static Kette* ende;
    Kette* p;
    //Zeiger auf nächstes Element
    Kette* next;

    public:

    static void listeAusgeben() {
        Kette* p = start;
        while(p != NULL) {
            p->ausgabe();
            p = p->next;
        }
    }
    static void wertAusgeben(int n){
        Kette* p = start;
        while(n != 1) {
            p= p->next;
            n--;
        }
        p->ausgabe();
    }
    static void letztesAusgeben(){
        Kette* p = ende;
        p->ausgabe();
    }

    void ausgabe() {
        cout << "a: " << a << endl;
    }

    static void delAlles(){
    	start = NULL;
	ende = NULL;
	counter = 0;
    }

    static void setCounter() {
        counter++;
    }

    void zaehler() {
        cout << "Anzahl der Objekte: " << counter << endl;
    }

    static void loesche(int index) {
        int i;
        Kette* temp;

        temp = start;
        for (i=0;i<index-1;i++) if (temp->next) temp = temp->next;
        if (temp) {
            temp->next = temp->next->next;
            //temp->next = temp->next->next;
        }
    }

    //Konstruktor
    Kette(int werta) {
        counter++;
        a = werta;
        // Verkettete Liste
        if (start) {
            ende->next = this;
            ende = this;
        }
        else {
            start = this;
            ende = this;
        }
        this->next = NULL;
    }
};

//initialisieren der static Variablen
Kette* Kette::start = NULL;
Kette* Kette::ende = NULL;
int Kette::counter = 0;

int main() {
    int w,b;

    //Liste erstellen
    Kette objekt1(3);
    Kette objekt2(4);
    Kette objekt3(8);

    //komplette Liste ausgeben
    cout << "Liste ausgeben: " << endl;
    Kette::listeAusgeben();

    //Wert vom 1. Objekt ausgeben
    cout<<"Wert des 1. Objektes"<<endl;
    objekt1.ausgabe();

    //Wert eines beliebigen Elementes ausgeben
    cout<<"welches Element ausgeben? "; cin>>w;
    Kette::wertAusgeben(w);

    //letztes Element ausgeben
    cout<<"letztes Element: ";
    Kette::letztesAusgeben();

    //Größe der Liste
    cout << "\nObjekte: ";
    objekt1.zaehler();

    //Element löschen
    cout<<"Welches Element soll gelöscht werden? ";cin>>b;
    cout<<"\nlösche jetzt Element"<<endl;
    Kette::loesche(b);

    //komplette Liste ausgeben
    cout << "Liste ausgeben: " << endl;
    Kette::listeAusgeben();

    //Liste komplett löschen
    Kette::delAlles();
    return 0;
} ;

Alle anderen Funktionen sollten ihre Arbeit erfüllen.

mfg

Sebastian21

truebool

static void delAlles(){
        start = NULL;
    ende = NULL;
    counter = 0;
    }

weiss nicht ob ich mich nicht irre aber sollte man nicht erst den speicher der elemente frei geben ??
dass heisse pointer auf das erste dann druchlaufen und alle elemente löschen und dann die zeiger auf NULL setzten??
Könnte man natürlich dann auch von destruktor aufrufen lassen.

willst du sortiert einfügen oder an einer beliebigen stelle wenn ja unter welchen kreterien also Wo oder durch zufall ??

kann es sein dass du in wertausgabe eine eingabe kleiner 1 nciht abfängst??
mach lieber >=1

otze

wär schon knorke, wenn die elemente gelöscht werden würden

achja, hier eine methode um size in konstanter zeit ausführbar zu machen:
bei jedem einfüge oder löschvorgang wird einfach ein interner counter incremetiert/dekrementiert, und bei size() wird der counter einfach zurückgegeben.

Danke für die Infos, jedoch interessiert mich hauptsächlisch wie ich einzelne Elemente in die Liste an beliebiger Position eingefügt bzw. gelöscht bekomme.
Danke

sebastian21

Hallo,

das mit dem beliebigen löschen in der Liste klappt nun, jedoch das Einfügen am Anfang und an einer beliebigen Stelle funktioniert nicht. Ich kann den Zeiger "this" nicht in einer "static void" Funktion verwenden.
Ich hatte das so gedacht, dass ich den Wert an die Funktion übergebe und diesen dann mit dem "this" Zeiger einbaue. Doch scheitert dies bei mir an der Synthax. Oder bin ich auf dem falschen Weg? Hilfe!!

Gruß

sebastian21

OK Hier ist der relevante Code.
Ich hoffe Ihr könnt mir helfen bzw. zeigen wie ich ein Element eingefügt bekomme!!
Relevant ist die Methode anfangEinf(int wert) und deren Aufruf in main:

#include <iostream>
using namespace std;
class Kette {
  private:
    int a,b,d,e;
    static int counter;
    static Kette* start;
    static Kette* ende;
    Kette* p;
    //Zeiger auf nächstes Element
    Kette* next;
  public:
    static void listeAusgeben();
    static void wertAusgeben(int n);
    static void letztesAusgeben();
    void ausgabe();
    static void setCounter();
    void zaehler();
    static void letztesLoeschen();
    static void erstesLoeschen();
    static void loesche(int index);
    static void delAlles();
    static void anfangEinf(int wert);
    Kette(int werta);
    Kette();
};

void Kette::listeAusgeben() {
    Kette* p = start;
    while(p != NULL) {
        p->ausgabe();
        p = p->next;
    }
}
void Kette::wertAusgeben(int n){
    Kette* p = start;
    while(n != 1) {
        p= p->next;
        n--;
    }
    p->ausgabe();
}
void Kette::letztesAusgeben(){
    Kette* p = ende;
    p->ausgabe();
}
void Kette::ausgabe() {
    cout << "a: " << a << endl;
}
void Kette::setCounter() {
    counter++;
}
void Kette::zaehler() {
    cout << "Anzahl der Objekte: " << counter << endl;
}
void Kette::letztesLoeschen() {
   Kette* p = start;
   while(p->next->next != NULL) {
       p = p->next;};
   p->next = NULL;
   counter = counter-1;
}
void Kette::erstesLoeschen() {
   Kette* p = start;
   start = p->next;
   counter = counter-1;
}
void Kette::loesche(int index) {
    int i=2;
    Kette* p = start;
    if (index == 1) {erstesLoeschen();}
    if (index != 1) {
        while (i != index) {
            p= p->next;
            i++;
        };
        p->next = p->next->next;
    };
    counter = counter -1;
}
void Kette::delAlles(){
    start = NULL;
    ende = NULL;
    counter = 0;
}
void Kette::anfangEinf(int wert) {
    // hier möchte ich einfügen?!?!?!?
    //int* wert_mit_dauerhaftem_speicher = new int;
    //*wert_mit_dauerhaftem_speicher = wert;
    //Problem: habe jetzt int* , brauche aber um Pointer einzubinden Kette* !!
    e = wert;
    if (start) {
        ende->next = this;
        ende = this;
    }
    else {
        start = this;
        ende = this;
    }
    this->next = NULL;
}
Kette::Kette(){}
//Konstruktor
Kette::Kette(int werta) {
    counter++;
    a = werta;
    // Verkettete Liste
    if (start) {
        ende->next = this;
        ende = this;
    }
    else {
        start = this;
        ende = this;
    }
    this->next = NULL;
}

//initialisieren der static Variablen
Kette* Kette::start = NULL;
Kette* Kette::ende = NULL;
int Kette::counter = 0;

int main() {

    int w,b,c,d,x;
// Liste aufbauen---------------------------------------------------
    Kette objekt1(3);
    Kette objekt2(4);
    Kette objekt3(8);
    Kette objekt4(9);
    Kette objekt5(10);
    Kette obj;
// Ausgabe----------------------------------------------------------
    //komplette Liste ausgeben
    cout << "Liste ausgeben: " << endl;
    Kette::listeAusgeben();
    //Wert vom 1. Objekt ausgeben
    cout<<"Wert des 1. Objektes"<<endl;
    objekt1.ausgabe();
    //Wert eines beliebigen Elementes ausgeben
    cout<<"welches Element ausgeben? "; cin>>w;
    Kette::wertAusgeben(w);
    //letztes Element ausgeben
    cout<<"letztes Element: ";
    Kette::letztesAusgeben();
// Größe der Liste--------------------------------------------------
    cout << "\nObjekte: ";
    objekt1.zaehler();
// Werte Einfügen---------------------------------------------------
    // Wert am Ende einfügen
    //cout<<"Bitte Wert des neuen letzten Elementes eingeben ";cin>>c;
    //Kette end(c);
    // Wert am Anfang einfügen...
    cout<<"Bitte Wert des neuen ersten Elementes eingeben ";cin>>d;
    obj.anfangEinf(d);
    //komplette Liste ausgeben
    cout << "Liste ausgeben: " << endl;
    Kette::listeAusgeben();
// Löschen----------------------------------------------------------
    //Element löschen
    cout<<"Welches Element soll gelöscht werden? ";cin>>b;
    cout<<"\nlösche jetzt Element"<<endl;
    Kette::loesche(b);
    //letztes Element löschen
    Kette::letztesLoeschen();
    //erstes Element löschen
    Kette::erstesLoeschen();
    //Liste komplett löschen
    Kette::delAlles();
    return 0;
} ;

Auf Hilfe hoffend
Sebastian