FIFO mit C++ (Klassen)

[Duff]

Hallo,

ich habe mal wieder Probleme mit einem C++-Programm (Übung).

Es soll ein Programm geschrieben werden, dass das FIFO-Prinzip (First in First out) benutzt.
Nur leider habe ich wohl ein paar Fehler drin, die ich noch nicht gefunden habe.

Code: Alles auswählen

// tfifo.cpp
#include <limits.h>
#include <iostream>
using namespace std;

class tNode {
public:
	int d;
	tNode *next;
};

class tFifo {
public:
	tFifo();
	~tFifo();
	void push(int);
	int pop();
private:
	tNode *Head;
	tNode *Tail;
};

tFifo::tFifo() {
	Head = Tail = 0;
}

tFifo::~tFifo() {
	tNode *last=Head;
	while(Head) {
		last=Head;
		Head=Head->next;
		delete last;
	}
}

void tFifo::push(int d) {
	tNode *node=new tNode;
	node->d=d;
	node->next=0;
	// An das Ende anhängen;
	if(Tail) {
		Tail->next=0;
	}
	if(Head==0) {
		Head=node;
	}
	Tail=node;
}

int tFifo::pop() {
	int inhalt=-1;
	if(Tail==Head)
		Tail=0;
	if(Head) {
		tNode *old=Head;
		Head=Head->next;
		inhalt=old->d;
		delete old;
	}
	return inhalt;
}

int main() {
	tFifo fifo;
	
	fifo.push(2);
	fifo.push(5);
	fifo.push(18);
	
	cout << fifo.pop() << endl;
	cout << fifo.pop() << endl;
	cout << fifo.pop() << endl;
}

Die Ausgabe ergibt:

Code: Alles auswählen

daniel@daniel-laptop:~/scripts/C++/Einstieg_in_C++/Kapitel05$ ./tfifo 
2
-1
-1

[GoKi]

Code: Alles auswählen

void tFifo::push(int d) {
   tNode *node=new tNode;
   node->d=d;
   node->next=0;
   // An das Ende anhängen;
   if(Tail) {
      Tail->next=0;
   }
   if(Head==0) {
      Head=node;
   }
   Tail=node;
}

Da steht zwar als Kommentar, was in dem if passieren soll, nur Du machst was anderes.

Code: Alles auswählen

   // An das Ende anhängen;
   if(Tail) {
      Tail->next=node;
   }

BTW: Großbuchstaben für Variablennamen und kleines t vor Klassen finde ich ja echt mal komisch

[Duff]

Code: Alles auswählen

   // An das Ende anhängen;
   if(Tail) {
      Tail->next=node;
   }

BTW: Großbuchstaben für Variablennamen und kleines t vor Klassen finde ich ja echt mal komisch

Wieso meinst du?
So wird es hier in dem Buch gemacht...

Das if(Tail) überprüft doch, ob der Zeiger Tail auf eine gültige Adresse zeigt, also nicht 0 ist?

Habe da immer wieder so meine Probleme beim Verständnis. Beim Lesen klar, nachher in der Praxis immer wieder mmh...wie war das doch gleich...

[GoKi]

Wieso meinst du?
So wird es hier in dem Buch gemacht...

Jeder kann natürlich seinen Stil benutzen, ich bevorzuge einen anderen.
Siehe, z.B. http://geosoft.no/development/cppstyle.html#Naming Conventions
Wobei ich auch nicht alles befolge, z.B. enden Dateinamen in unseren Projekten auf .cpp

Das if(Tail) überprüft doch, ob der Zeiger Tail auf eine gültige Adresse zeigt, also nicht 0 ist?

Genau. Nur du musst in diesem If, an das derzeitige Ende der Liste das neue Element hängen, wie es auch der Kommentar über dem if andeutet. Ich habe den kompletten Source mal auf NoPaste gestellt.
http://nopaste.debianforum.de/19554
Setzt Du next auf 0 - wie es in deinem Code war - dann endet an dieser Stelle die Liste. Du willst jedoch, dass das neue Element, das neue Ende der Liste wird. Also muss das alte Ende der Liste nun mit next auf das neue Ende der Liste (node die gerade eingefügt wird) zeigen.

[Duff]

Ok, danke.

Aber wofür wird in dem Ausgabe-Block

Code: Alles auswählen

int tFifo::pop() {
        int inhalt=-1;
        if(Tail==Head)
                Tail=0;
        if(Head) {
                tNode *old=Head;
                Head=Head->next;
                inhalt=old->d;
                delete old;
        }
        return inhalt;
}

diese Überprüfung gebraucht?
Man könnte sie doch auch weglassen.

Code: Alles auswählen

        if(Tail==Head)
                Tail=0;

[GoKi]

diese Überprüfung gebraucht?

Wenn das letzte Element aus der FIFO Queue geholt wird, dann greift das if. In diesem Fall ist nach dem pop die Queue leer. Head und Tail müssen dann 0 sein. Das if stellt dies sicher. Um diesen Spezialfall zu testen, kannst Du z.B. folgendes main benutzen:

Code: Alles auswählen

int main() {
   tFifo fifo;
   
   fifo.push(2);
   fifo.push(5);
   fifo.push(18);
   
   cout << fifo.pop() << endl;
   cout << fifo.pop() << endl;
   cout << fifo.pop() << endl; // Queue ist jetzt leer

   fifo.push(42);
   cout << fifo.pop() << endl;
}

Man könnte sie doch auch weglassen.

Kann man schon, nur stürzt das Programm dann mit ziemlicher Sicherheit ab.

[Duff]

Danke für die gute und verständliche Erklärung.

Ja, das Programm stürzt dann ab. Hattest recht.

Code: Alles auswählen

daniel@daniel-laptop:~/scripts/C++/Einstieg_in_C++/Kapitel05$ ./tfifo 
2
5
18
42
*** glibc detected *** ./tfifo: double free or corruption (fasttop): 0x0804a028 ***
======= Backtrace: =========
/lib/i686/cmov/libc.so.6[0xb7d5a624]
/lib/i686/cmov/libc.so.6(cfree+0x96)[0xb7d5c826]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0xb7f332e1]
./tfifo(__gxx_personality_v0+0x1dc)[0x8048838]
./tfifo(__gxx_personality_v0+0x3a3)[0x80489ff]
/lib/i686/cmov/libc.so.6(__libc_start_main+0xe5)[0xb7d02455]
./tfifo(__gxx_personality_v0+0x45)[0x80486a1]
======= Memory map: ========
08048000-08049000 r-xp 00000000 03:03 3761704    /home/daniel/scripts/C++/Einstieg_in_C++/Kapitel05/tfifo
08049000-0804a000 rw-p 00000000 03:03 3761704    /home/daniel/scripts/C++/Einstieg_in_C++/Kapitel05/tfifo
0804a000-0806b000 rw-p 0804a000 00:00 0          [heap]
b7b00000-b7b21000 rw-p b7b00000 00:00 0 
b7b21000-b7c00000 ---p b7b21000 00:00 0 
b7ceb000-b7cec000 rw-p b7ceb000 00:00 0 
b7cec000-b7e41000 r-xp 00000000 03:02 1043382    /lib/i686/cmov/libc-2.7.so
b7e41000-b7e42000 r--p 00155000 03:02 1043382    /lib/i686/cmov/libc-2.7.so
b7e42000-b7e44000 rw-p 00156000 03:02 1043382    /lib/i686/cmov/libc-2.7.so
b7e44000-b7e47000 rw-p b7e44000 00:00 0 
b7e47000-b7e53000 r-xp 00000000 03:02 949231     /lib/libgcc_s.so.1
b7e53000-b7e54000 rw-p 0000b000 03:02 949231     /lib/libgcc_s.so.1
b7e54000-b7e55000 rw-p b7e54000 00:00 0 
b7e55000-b7e79000 r-xp 00000000 03:02 1043387    /lib/i686/cmov/libm-2.7.so
b7e79000-b7e7b000 rw-p 00023000 03:02 1043387    /lib/i686/cmov/libm-2.7.so
b7e7b000-b7f5e000 r-xp 00000000 03:02 228556     /usr/lib/libstdc++.so.6.0.10
b7f5e000-b7f61000 r--p 000e2000 03:02 228556     /usr/lib/libstdc++.so.6.0.10
b7f61000-b7f63000 rw-p 000e5000 03:02 228556     /usr/lib/libstdc++.so.6.0.10
b7f63000-b7f69000 rw-p b7f63000 00:00 0 
b7f84000-b7f87000 rw-p b7f84000 00:00 0 
b7f87000-b7fa1000 r-xp 00000000 03:02 944786     /lib/ld-2.7.so
b7fa1000-b7fa3000 rw-p 0001a000 03:02 944786     /lib/ld-2.7.so
bf88d000-bf8a2000 rw-p bffeb000 00:00 0          [stack]
ffffe000-fffff000 r-xp 00000000 00:00 0          [vdso]
Abgebrochen