Einfache Verkettete Liste

Thunaer

Hallo!
Ich bin eig nicht der Typ für solche Anfragen hier, nur interessiert es mich sehr.
Wir wollen bald in der Schule mit verketteten Listen anfangen, also fing ich an zu googlen was man darunter versteht und wie diese wohl aufgebaut sind..
Hier bin ich auf ein Tutorial gestoßen (Link), muss aber zugeben, dass ich das nicht soooo genau verstehe.
Deswegen wollt ich mal fragen, ob hier jemand vllt so nett wäre um mir ein simples Beispiel zu programmieren, aus dem ich es mir am Besten erschliessen könnte (Sinn ist es ja dass ich es verstehe).
Es sollte halt nicht nach einer besonderen Aufgabenstellung gehen, sondern nur so, dass ich es verstehe^^
Habe aus dem Tutoriel mir schon so viel Quellcode zusammengewürfelt:

#include <iostream>
#include <stdlib.h>

using namespace std;

class Element
{
   private:
      int m_wert;
      Element *m_pNeachstesElement;
   public:
        void set (int a)
        {
            m_wert=a;
        }

        int get()
        {
            return m_wert;
        }
};

int main()
{
     Element *pNeuesElement=new Element;
     pNeuesElement->set(4);
     cout<<"Liste 1: "<<pNeuesElement->get()<<endl;
     cin.get();
     return 0;
}

Hi

Also du hast ja schon eine Node-Klasse (bei dir "Element").
Jetzt brauchst du noch eine LinkedList-Klasse.

Diese sollte als Datenmember minedestens einen Front- sowie einen Rear-Pointer enthalten (bei dir wären die also vom Typ Element*), um auf das erste bzw. letzte Element zugreifen zu können. Zusätzlich brauchst du eine enqueue()-Methode welche dir hinten (also jeweils hinter dem Element auf das der Rear-Pointer zeigt) neue Elemente anfügt, meist macht man das mittels new (achtung: wenn Klassen dynamisch Speicher anfordern muss der Destruktor den Speicher wieder freigeben --> delete). Auch gut wäre natürlich eine Methode um z.B. das vorderste Element entfernen zu können, also eine pop()- resp. deque()-Methode.

Wenn du deine linked list so implementierst hast du eine sogenannte Queue.

Solche Datenstrukturen gibt's übrigens auch fertig gebacken in der STL (std::deque ist z.B. eine solche...).

Natürlich kannst du nicht erwarten dass dir hier jemand eine fertige Implementierung gibt....

Falls dir doch jemand eine gibt herzlichen Glückwunsch, der Lerneffekt geht einfach flöten....

Thunaer

Hmm also davon hab ich nicht soo viel verstanden
Ich wollte ja nur ein kleines Beispiel haben, am besten kommentiert, um mich selber durch den Quellcode schlagen zu können, denn das ist der Weg durch den ich irgendwie am meisten lerne....
Aber wenn das hier keiner macht / machen möchte (ist ja auch verständlich), muss ich eben darauf warten, bis wir das Thema Pointer im Unterricht angesprochen haben und irgendwann mal darauf zu sprechen kommen.

Vevusio

wow dieses tutorial beispiel ist auch total beschissen

ka, lies dir mal dieses durch vllt
http://richardbowles.tripod.com/cpp/linklist/linklist.htm

das hat viele grafiken und scheint die einzelnen schritte wie element einfügen und element löschen gut zu erklären

goto anywhere*

Der folgende Code ist ein minimales Lagerverwaltungsprogramm; das einfachste was sich bei mir ausgraben lies.
Mit Klassen und so habe ich nicht gearbeitet (konnte ich ja damals noch nicht ), aber der Code ist so kurz, dass man's vielleicht trotzdem verstehen kann...

#include <iostream>
#include <cstdlib>
#include <string>

void artikel_hinzufuegen(struct artikel neuer_artikel);
void artikel_ausgeben(void);

struct artikel{
	std::string name;
	struct artikel *next;
};

int main(void){
	LOOP:
	system("CLS");
	std::cout
		<<"+-------------------------------------+"<<std::endl
		<<"| < H > - Artikel hinzufuegen         |"<<std::endl
		<<"| < A > - Artikel (sortiert) ausgeben |"<<std::endl
		<<"| < B > - Programm beenden            |"<<std::endl
		<<"+-------------------------------------+"<<std::endl
		<<std::endl<<"Ihre Auswahl: <   >\b\b\b";
	char menue_auswahl;
	std::cin>>menue_auswahl;
	switch(menue_auswahl){
		case 'H':{
			system("CLS");
			std::cout<<"Artikelname: ";
			std::string artikelname;
			std::cin>>artikelname;
			struct artikel a={artikelname};
			artikel_hinzufuegen(a);
			std::cout<<"Der Artikel wurde erfolgreich hinzugefuegt!"<<std::endl;
			system("PAUSE");
			break;
		}
		case 'A':{
			system("CLS");
			artikel_ausgeben();
			system("PAUSE");
			break;
		}
		case 'B':{
			return 0;
		}
		default:{
			std::cerr<<"FEHLER: Ungueltige Eingabe!"<<std::endl;
			system("PAUSE");
		}
	}
	goto LOOP;
}

static struct artikel *erster_artikel=NULL;

void artikel_hinzufuegen(struct artikel neuer_artikel){
	static struct artikel *letzter_artikel=NULL;

	if(erster_artikel!=NULL){
		struct artikel *speicher_fuer_neuen_artikel=new struct artikel;
		speicher_fuer_neuen_artikel->name=neuer_artikel.name;
		speicher_fuer_neuen_artikel->next=NULL;
		letzter_artikel->next=speicher_fuer_neuen_artikel;
		letzter_artikel=speicher_fuer_neuen_artikel;
	}
	else{
		erster_artikel=new struct artikel;
		erster_artikel->name=neuer_artikel.name;
		erster_artikel->next=NULL;
		letzter_artikel=erster_artikel;
	}
}
void artikel_ausgeben(void){
	if(erster_artikel!=NULL){
		struct artikel *aktuell_ausgegebener_artikel=erster_artikel;
		unsigned int cnt=0;
		do{
			std::cout<<++cnt<<"-ter Artikel in Liste: "<<aktuell_ausgegebener_artikel->name<<std::endl;
			aktuell_ausgegebener_artikel=aktuell_ausgegebener_artikel->next;
		}while(aktuell_ausgegebener_artikel!=NULL);
	}
}

Werner Salomon

In diesem Forum gibt es auch eine Menge Threads, die sich mit dem Thema beschäftigen. Schau Dir mal dieses Posting über Listen an und folge auch den angegebenen Links.
Und natürlich Wikipedia hat auch was über Listen.

Hier noch eine Überarbeitung Deines ersten Entwurfs.

#include <iostream>
// #include <stdlib.h> braucht es nicht
using namespace std;

class Element
{
public:
    // get-setter kannst Du hier ausnahmsweise weglassen
    //  wichtiger ist ein Konstruktor
    Element( int wert, Element* naechster )
        : m_wert( wert )
        , m_pNeachstesElement( naechster )
    {}
    int m_wert;
    Element *m_pNeachstesElement;
};

class Liste // die eigentliche Liste mit 'vielen' Element'en
{
public:
    Liste() : m_kopf(0) {} // ganz wichtig; Member im Konstruktor initialisieren
    void push_front( int wert ) // vorne einfügen
    {
        m_kopf = new Element( wert, m_kopf );
    }
    void print( std::ostream& out ) // Ausgabe
    {
        for( Element* p = m_kopf; p; p = p->m_pNeachstesElement )
            out << p->m_wert << " ";
    }
private:
    Element* m_kopf; // Zeiger auf das erste Element
};

int main()
{
    Liste l;
    l.push_front( 4 );
    l.push_front( 5 );
    cout<<"Liste 1: ";
    l.print( cout );
    cout << endl;
    cin.get();
    return 0;
}

Da fehlt natürlich noch einiges - Destruktor, Copy-Konstruktor, Zuweisungsoperator und etliche Listen-Methoden.

Falls Du konkrete Fragen hast, so melde Dich nochmal.

Gruß
Werner

Jester

Vevusio schrieb:

ka, lies dir mal dieses durch vllt
http://richardbowles.tripod.com/cpp/linklist/linklist.htm

das hat viele grafiken und scheint die einzelnen schritte wie element einfügen und element löschen gut zu erklären

ja, aber die implementierung die rauskommt ist leider trotzdem bescheiden.

drakon

goto anywhere schrieb:

struct artikel{
    std::string name;
    struct artikel *next;
};

Doch du hast eine Klasse benutzt. :p

Und dann noch goto für ne Schleife... Schäme dich.

goto anywhere*

drakon schrieb:

goto anywhere schrieb:
struct artikel{
    std::string name;
    struct artikel *next;
};
Doch du hast eine Klasse benutzt. :p

Und dann noch goto für ne Schleife... Schäme dich.

Ich glaube, das einzige was ich unter Benutzerdaten angegeben habe ist, dass ich Elektroniker (in Ausbildung) bin. Ich habe also mit "selber Compiler spielen" und Assembler angefangen..., deshalb wohl bin ich dauernt versucht, so Sachen wie goto und vor allem Pointer in rauen Mengen zu verwenden.

sothis_

Vevusio schrieb:

wow dieses tutorial beispiel ist auch total beschissen

ka, lies dir mal dieses durch vllt
http://richardbowles.tripod.com/cpp/linklist/linklist.htm

das hat viele grafiken und scheint die einzelnen schritte wie element einfügen und element löschen gut zu erklären

diese seite bekommt eine 7/10 auf der augenkrebs-skala von mir

Werner Salomon

goto anywhere; schrieb:

Mit Klassen und so habe ich nicht gearbeitet (konnte ich ja damals noch nicht ), ...

Ich kann jedem Anfänger, der sich in C++ einarbeiten will, nur wärmsten empfehlen: zuerst in Klassen einarbeiten (insbesondere Konstruktor und Destruktor) und danach erst versuchen eine Liste zu programmieren.

Siehe dazu auch meine Verzweifelung am Anfang dieses Beitrags

Gruß
Werner

Thunaer

Dann danke ich euch allen schonmal!
Werde mich heute ein wenig tiefer darin einarbeiten und wenn ich fragen habe stell ich sie hier ^^

mfg