Einfach verkettete Liste



  • Hey Leute,

    ich habe folgendes Programm zur Verwaltung einer einfach verketteten Liste JobList für Aufträge vom Typ Job

    Header.h:

    #pragma once
    #include <iostream>
    using namespace std;
    #include <string>
    #include <sstream>
    
    class Job
    {
    private:
    	long id;
    	string description;
    	static long curID;
    
    public:
    	Job(const string& todo) : id(++curID), description(todo)
    	{}
    
    	unsigned long getID() const { return id; }
    	const string& getDescription() const
    	{
    		return description;
    	}
    
    	void setDescription(const string& d)
    	{
    		description = d;
    	}
    
    	friend ostream& operator << (ostream& os, const Job& obj)
    	{
    		os << obj.getDescription() << endl;
    		os << obj.getID() << endl;
    		return os;
    	}
    };
    
    
    
    class JobList
    {
    private:
    	int count;
    	struct ListEI
    	{
    		Job job;
    		ListEI* next;
    
    		ListEI(const Job& jb) : job(jb), next(NULL) {}
    	};
    	ListEI* ptrfirst, * ptrlast;
    
    public:
    	JobList() : ptrfirst(NULL), ptrlast(NULL), count(0) {}
    
    	~JobList();	
    
    	void pushBack(const Job&);
    	
    	int getCount(void)
    	{
    		return count;
    	}
    
    	void print();
    };
    

    Quelle.cpp:

    #include <iostream>
    using namespace std;
    #include <string>
    #include <sstream>
    #include "Header.h"
    
    long Job::curID = 1000;
    
    JobList::~JobList()
    {
    	ListEI* ptr = ptrfirst, * next;
    	for (; ptr != NULL; ptr = next)
    	{
    		next = ptrfirst->next;
    		delete ptr;
    	}
    }
    
    void JobList::pushBack(const Job& job)
    {
    	ListEI* ptrlisteei = new ListEI(job);
    	if (count == 0)
    	{
    		ptrfirst = ptrlast = ptrlisteei;
    	}
    	else
    	{
    		ptrlast = ptrlisteei;
    		ptrlast->next = ptrlisteei;
    	}
    	count++;
     }
    
    void JobList::print()
    {
    	ListEI* ptrei;
    	for (ptrei = ptrfirst; ptrei != NULL; ptrei = ptrei->next)
    		cout << ptrfirst->job.getDescription() << endl;
    }
    

    Zum Testen des Codes habe ich folgende Funktionen in der Main aufgerufen:

    int main()
    { 
        Job job1("Teller sortieren");
        Job job2("Zimmer aufräumen");
        Job job3("Schlafen");
        JobList myjoblist;
        myjoblist.pushBack(job1);
        myjoblist.pushBack(job2);
        myjoblist.pushBack(job3);    
        myjoblist.print();  // Fehler    
    }
    

    Dabei ist mir aufgefallen, dass beim Ausgeben mittels print() immer nur ein Job (Teller sortieren in dem Fall) ausgegeben wird. Im Schrittbetrieb konnte ich erkennen dass alle 3 Jobs von der Liste aufgenommen wurden, jedoch die in print() befindliche for-Schleife nur einmal durchlaufen wird (ptrei hat im zweiten Durchlauf den Wert NULL). Warum ist so, was ist
    in dem Programm falsch? Vielen Dank für eure Hilfe!



  • Auf die Schnelle würde ich sagen, Du musst Zeile 28 une 29 vertauschen.



  • Dann schau dir noch mal genau deine pushBack-Funktion, bes. der else-Zweig, an (bzw. am besten du benutzt den Debugger und durchläufst deinen Code zeilenweise und schaust dir die Variableninhalte an).

    Und im Destruktor Zeile 14 hast du auch noch einen Fehler.

    PS: Verkettete Listen benutzt man nur noch sehr selten - fast immer wird stattdessen vector<T> benutzt.
    Aber als Übungsaufgabe ist das noch in Ordnung (um Zeiger zu verstehen).



  • Ja, die Zeilen 28 und 29 mussten vertauscht werden. Warum das jetzt den entscheidenden Unterschied macht, ist mir jedoch noch nicht klar. Scheint also hätte ich da was noch nicht gan verstanden...



  • @C-Sepp

    Naja, aktuell steht da im Prinzip:

    ptrlast = ptrlisteei;
    ptrlisteei->next = ptrlisteei;
    

    Du willst aber erst sicherstellen, dass du vom aktuell letzten Element auf das neue letzte Element zeigst, damit du die Kette auch weiter durchgehen kannst. Und dann kannst du den Pointer, der auf das letzte Element zeigt, umbiegen und auf das neue letzte Element zeigen.



  • Okay...danke für die schnelle Hilfe. Bin jetzt gerade dabei mir einen Kopierkonstruktor für eine Liste
    anzulegen. Vom Ansatz her ist es klar, was gemacht werden muss:

    JobList::JobList(const JobList& jbl)
    {
    	//ptrfirst = jbl.ptrfirst;
    	//ptrlast = jbl.ptrlast;
    	//count = jbl.count;
    	ptrfirst = ptrlast = NULL;
    	count = 0;
    
    	for (ListEI* ptr = ptrfirst; ptr != NULL; ptr = ptr->next)
    		pushBack(ptr->job);
    }
    

    Trotzdem ist mir nicht klar, warum die Zeiger auf das letzte und erste Element NULL gesetzt werden müssen.
    Hätte das Argument ptrfirst, ptrlast und den counter aus den Argument übernommen. Wenn ich das mache wird
    die darauffolgende For-Schleife endlos abgearbeitet??



  • @C-Sepp

    In c++ nutzt man heute eigentlich nullptr anstelle von NULL. Der Unterschied ist NULList gleich 0 und nullptr ist ein Keyword, das einen leeren Pointer anzeigt.

    Wenn du die direkt im Header mit nullptr initialisierst, dann benötigst du das im Konstruktor nicht mehr.

    Wenn du ptrfirstund ptrlast aus dem Argument übernimmst, wo drauf zeigen die denn dann? Und, was passiert dann in pushBack?

    P.S.: Wenn du es dir so nicht vorstellen kannst, man kann sowas auch mal auf Papier nachstellen, oder mit einem Debugger rein gucken, was wirklich passiert.



  • @C-Sepp: Bzgl. Kopieren erkundige dich mal nach den beiden Stichwörtern "shallow copy" und "deep copy" - dann verstehst du den Unterschied.



  • Okay...habe ich mich zu shallow copy und deep copy informiert.
    Beim Debuggen habe ich dann auch erkennen können, dass in der pushback-Funktion die Verzweigung
    für count==0 nicht abgearbeitet werden kann, wenn das Argument jbl.count in den Kopierkonstruktor mit
    reingenommen wird. Danke!



  • Mein Programm möchte ich jetzt dahingehend erweitern, dass es ermöglicht wird, mit Iteratoren
    die Job-Liste zu durchlaufen und nach bestimmten Aufträgen zu suchen. Dazu habe in der Klasse JobList
    eine Klasse Iterator mit verschiedenen Operatoren und den Funktionen begin() und end() angelegt:

    class JobList
    {
    private:
    	int count;
    	struct ListEI
    	{
    		Job job;
    		ListEI* next;
    
    		ListEI(const Job& jb) : job(jb), next(NULL) {}
    	};
    	ListEI* ptrfirst, * ptrlast;	
    
    public:
    	JobList() : ptrfirst(NULL), ptrlast(NULL), count(0) {}
    
    	~JobList();
    
    	JobList(const JobList&);   //ohne Referenz Fehler "unzulässiger Kopierkonstruktor: erster Parameter darf nicht "JobList" sein ???		
    
    	void pushBack(const Job&);
    
    	bool popFront(Job&);	
    
    	int getCount(void)
    	{
    		return count;
    	}
    
    	void print();
    
    	class Iterator
    	{
    		private:
    			ListEI* ptrit;
    
    		public:
    			Iterator(ListEI* pti = NULL) : ptrit(pti) {}
    
    			Job& operator* (void)
    			{
    				return ptrit->job;
    			}
    
    			/*ListEI* operator++(void)
    			{
    				ptrit = ptrit->next;
    				return ptrit;
    			}*/
    
    			Iterator& operator++(void)
    			{
    				ptrit = ptrit->next;
    				return *this;
    			}
    
    			bool operator== (const Iterator& it)
    			{
    				return ptrit == it.ptrit;
    			}
    
    			bool operator!= (const Iterator& it)
    			{
    				return ptrit != it.ptrit;
    			}
    	};
    
    	//1. Variante
    	ListEI* begin()
    	{
    		return ptrfirst;
    	}
    
    	//2. Variante
    	/*Iterator begin() const
    	{
    		return Iterator(ptrfirst);
    	}*/
            
            //2. Variante
    	/*Iterator end() const
    	{
    		return Iterator();
    	}*/
    
            //1. Variante
    	ListEI* end()
    	{
    		return NULL;
    	}
    };
    
    

    Damit ist es nun möglich in der main durch die angelegte Liste zu iterieren und den jeweiligen Auftrag mit id und jobdescription über cout auszugeben:

    int main()
    { 
        Job job1("Teller sortieren");
        Job job2("Zimmer aufräumen");
        Job job3("Schlafen");
        JobList myjoblist1;
        myjoblist1.pushBack(job1);
        myjoblist1.pushBack(job2);
        myjoblist1.pushBack(job3);    
        myjoblist1.print(); 
        JobList myjoblist2(myjoblist1);
        myjoblist2.print();
        
        JobList::Iterator iterator = myjoblist2.begin();
        for (; iterator != NULL; ++iterator)
            cout << *iterator << endl;    
    }
    

    Warum/Wie ist die Zuweisung JobList::Iterator iterator = myjoblist2.begin(); möglich? begin liefert doch eigentlich einen
    Zeiger vom Typ ListEI, iterator wiederrum ist eine eigene Klasse Danke :)!



  • Bei

    JobList::Iterator iterator = myjoblist2.begin();
    

    wird implizit der Iterator-Konstruktor Iterator(ListEI* pti) verwendet.
    Ist dasselbe wie bei der Zuweisung von z.B.

    std::string str = "text";
    

    Auch hier wird der Konstruktor std::string(const char *) aufgerufen.
    Maximal eine implizite Konvertierung ist zulässig. Aber auch verhindern läßt sich so etwas, nämlich wenn der Konstruktor mit explicit deklariert wird.

    Trotzdem wäre es besser hier, analog zu den STL-Klassen wie std:.string::begin oder std::vector<...>::begin, direkt den Iterator zurückzugeben.
    Außerdem solltest du dich auch noch über "const-correctness" informieren und es einbauen - dann wäre deine Klasse konform(er) zu den STL-Klassen.



  • Okay...das ist auch gut zu wissen.
    Aufgefallen ist mir auch noch, dass wenn ich das Argument des Kopierkonstruktors nicht als Referenz übergebe,
    immer eine Fehlermeldung erhalte:

    //mit const JobList& jbl keinen Fehler
    JobList::JobList(const JobList jbl)
    {	
    	ptrfirst = ptrlast = nullptr;
    	count = 0;	
    
    	for (ListEI* ptr = jbl.ptrfirst; ptr != NULL; ptr = ptr->next)
    		pushBack(ptr->job);
    }
    

    Fehler:
    error C2558: class "JobList": Kein Kopierkonstruktor verfügbar oder der Kopierkonstruktor is als "explicit" deklariert
    error C2652: "JobList": Unzulässiger Kopierkonstruktor: erster Parameter darf nicht "JobList" sein

    Warum ist das so? Bei jeder anderen Funktion habe ich doch eine Wahlmöglichkeit ob ich den Parameter als Referenz oder als Kopie übergebe. Danke!



  • Das was du da schreibst ist doch der Kopierkonstruktor. Der soll also das Kopieren übernehmen. Bei deiner Argumentenliste soll der Kopierkonstruktor sich also selbst aufrufen?



  • Ich habe es mal ohne Referenz ausprobiert und da sind dann diese Fehler gekommen. Richtig...kopieren von Objekten vom Typ JobList


Log in to reply