Anfängerproblem FIFO-Queue

[volkard]

schon wieder hausaufgaben für jemanden gemacht?
gut so! fein so!

ich bitte darum, daß ihr als leser und beantworter nicht immer den pädagogischen lümmel heraushängen laßt. der neuling lernt auch, indem er eine hier gelöste aufgabe aufbereitet, um die seinem lehrer/prof vorzustellen. nee, er lernt sogar, wenn er nicht vorstellen muß. er ist ja interessiert am ergebnis. nur ganz ganz ganz selten will der frager die antwort gar nicht selber wissen.

und bitte verzeiht den asozialen in dieser hinsicht (und da gehöre ich auch manchmal dazu, weil ich gar nicht den kern des problems sehe), wenn sie kacke labern. laßt uns an sich, wenn keine weiteren daten über den frager da sind, davon ausgehen, daß er genauso ist wie wir als wir anfingen.

[terraner]

na das sagt ja der richtige.
du löscht doch hier manchmal postings ohne weiteren begründung. wieso fällt es dir da so schwer dann diesen thread hier zu schließen? sei bitte etwas konsequenter, was die handhabung unangebrachter posting und threads angeht, anstatt mich anzuflamen, denn im endeffekt ist es immer noch meine entscheidung, ob ich jemandem antworte oder nicht!

ich habe jetzt erstmal meine lösung vorläufig gelöscht, weil ich nach erneutem lesen des ersten postings auch meine zweifel bekommen habe.

mfg

[volkard]

terraner schrieb:

na das sagt ja der richtige.
du löscht doch hier manchmal postings ohne weiteren begründung.

das der fall.

wieso fällt es dir da so schwer dann diesen thread hier zu schließen?

weil ich es gut finde, daß geholfen wird, weil du keine scheiße laberst, weil die fragestellung nett war.

sei bitte etwas konsequenter, was die handhabung unangebrachter posting und threads angeht,

noch mehr löschen? da werd ich ja arbeitskrank von. nee, ich will nur ein postings pro monat löschen müssen. zur not, indem ich bei gelegenheit ein wenig mehr arbeit investieren, damit sich trolle hier nicht so toll wohlfühlen.
ok, zur zeit sind einige querpostings hier, die in ein anderes subforum gehören. hab viele dagelassen, weil ich vom löschen ganz erschöpft bin.

anstatt mich anzuflamen, denn im endeffekt ist es immer noch meine entscheidung, ob ich jemandem antworte oder nicht!

ah, mißverständnis. ich hab dich gar nicht angeflamed. in dem posting von mir war null ironie. muß wohl in zukunft <keine ironie>-tags setzen, wenn ich mal applaudiere (was zugegebenermaßen zu selten ist). ich wünsche es echt, daß weniger offensichtliche freizeitpädagogik betrieben wird, sondern mehr geholfen. wer jemanden beeinflussen will, muß das eh unter der gürtelline tun, subversiv, schleichend, versteckt, nachhaltig und konsequent. das ist aber auch jedem antworter seine eigene entscheidung, wie weit er es treibt. ein paar leichte funktionen auslassen finde ich gut. oder tippfehler machen. nur ein "denk selber nach!" zu posten finde ich nicht gut. das ärgert den frager nur und bringt keinen weiter.

ich habe jetzt erstmal meine lösung vorläufig gelöscht, weil ich nach erneutem lesen des ersten postings auch meine zweifel bekommen habe.
mfg

supi. daß sie nur vorläufig gelöscht ist. das interpretiere ich so, daß du ne kopie auf platte hast. stell sie bitte wieder rein.

[CS]

Args, der Quellcode dort sieht ja grauenvoll aus. Bist du sicher, daß der (a) ohne Fehlermeldungen compiliert und (b) das richtige macht? Und warum nutzt du, wenn du schon in C++ unterwegs bist, nicht das Klassenkonzept (Init wäre Konstruktor, die übrigen Funktionen Methoden von Stapel)?

[terraner]

CS schrieb:

Args, der Quellcode dort sieht ja grauenvoll aus. Bist du sicher, daß der (a) ohne Fehlermeldungen compiliert und (b) das richtige macht? *(c)*Und warum nutzt du, wenn du schon in C++ unterwegs bist, nicht das Klassenkonzept (Init wäre Konstruktor, die übrigen Funktionen Methoden von Stapel)?

(a) Ja.
(b) Jetzt schon. Ich musste noch einen Bug beseitigen.
(c) Weil er schon mit structs angefangen hat und ich es wichtiger fand erstmal sein Problem im bekannten Stil zu lösen.

fifo.hpp

#ifndef FIFO_HPP
#define FIFO_HPP

// Das gehört in einen Header
struct Header // C-Style-Deklaration gelöscht
{
  int* data; //Zeiger auf Int // schlechter Kommentar. man sieht doch, was das ist.
  //int top, bottom, count, size;
  // wofür brauche ich denn das? ich sehe da nur bedarf für size, top oder count
  int size, top;
};

typedef Header* Stapel; // C-Style-Deklaration gelöscht
// IMO ist es schlecht Zeiger so zu verbergen
// wer denkt jetzt noch daran, dass man den Stapel deleten muss?

Stapel Init    (int size); // variablennamen werden klein geschrieben
void   Push    (Stapel s, int x); // schlechter int-name. was ist x?
int    Pop     (Stapel s);
bool   IsEmpty (Stapel s); // bool. das hier ist nicht prä-ansi c.
void   Dispose (Stapel s);

#endif

fifo.cpp

#include <cstdlib>
#include "fifo.hpp"

Stapel Init(int size)
{
   Stapel s;
   s = new Header; //S = Zeiger auf Header // Böses typedef, wie ich bereits sagte.
   s->data = new int[size];
   s->size = size;
   s->top = 0;
   return s;
}

void Push(Stapel s, int x) // für "x" besser "value" oder soetwas nehmen
{
	// Abfrage, ob Stack voll ist, fehlt
	if(s->top == s->size)
	{
		delete [] s; // hm...
		// ich schmeiss lieber keine exceptions in c-code.
		// aber ich kann auch keine mit dem rückgabe-wert anzeigen...
		s->data[std::rand()] = 0;
	}

   s->data[s->top++] = x; // schön kompakt gelöst
   //s->data[top] = x;
   //top = (top+1)%ize;
}

int Pop(Stapel s)
{
	// hier fehlt eigentlich auch die abfrage
	/* if(top)
	**      return s->data[s->top--];
	** else
	** 		...
	*/
   return s->data[--s->top]; // fast so schön wie die push-funktion.
}

bool IsEmpty (Stapel s)
{
   return (s->top == 0); // Wunderschön.
}

void Dispose (Stapel s)
{
   delete [] s->data;
   //delete s; // warum den zeiger selbst deleten?
}

fifo-main.cpp

#include "fifo.hpp"
#include <cassert>

int main()
{
	Stapel s = Init(20);

	for(int i = 0; i < 20; ++i)
		Push(s, i);

	for(int i = 0; i < 20; ++i)
		Pop(s);

	assert(IsEmpty(s));

	Dispose(s);

	return 0;
}

fifo_class.hpp

#ifndef FIFO_20051013_HPP
#define FIFO_20051013_HPP

#include <cstddef>

class Stack
{
public:
	Stack(size_t size);
	Stack(const Stack& rhs);
	~Stack();

	void push(int value);
	int pop();

	bool isEmpty() { return !numElements_; }

	Stack& operator= (const Stack& rhs);

private:
	size_t size_, numElements_;
	int* pData_;
};

#endif

fifo_class.cpp

#include "fifo_class.hpp"

#include <cstring>
#include <stdexcept>
#include <cassert>

Stack::Stack(size_t size) :
size_(size),
numElements_(0),
pData_(new int[size_])
{
	assert(size_);
}

Stack::Stack(const Stack& rhs) :
size_(rhs.size_),
numElements_(rhs.numElements_),
pData_(new int[size_])
{
	std::memcpy(pData_, rhs.pData_, numElements_ * 4);
}

Stack::~Stack()
{
	delete [] pData_;
}

void Stack::push(int value)
{
	// assert(numElements_ != size)
	if(numElements_ == size_)
		throw std::runtime_error("too many elements");

	pData_[numElements_++] = value;
}

int Stack::pop()
{
	//assert(numElements);
	if(!numElements_)
		throw std::runtime_error("no elements to pop");

	return pData_[--numElements_];
}

Stack& Stack::operator= (const Stack& rhs)
{
	size_ = rhs.size_;
	numElements_ = rhs.numElements_;

	int* tmp = new int[size_];
	std::memcpy(tmp, rhs.pData_, numElements_ * 4);

	delete [] pData_;
	pData_ = tmp;

	return *this;
}

fifo_class-main.cpp

#include "fifo_class.hpp"
#include <exception>
#include <iostream>

#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  	Stack s(20);
	try
	{

		for(int i(0); i < 20; ++i)
			s.push(i);

		assert(!s.isEmpty());

		for(int i(19); i >= 0; --i)
		{
			int ret = s.pop();
			assert(ret == i);
		}
		assert(s.isEmpty());
	}
	catch(exception& e)
	{
		cout << e.what() << endl;
		return 3;
	}
	catch(...)
	{
		cout << "uknown exception!" << endl;
		return 4;
	}

	try
	{
		s.pop();
	}
	catch(exception& e)
	{
		cout << e.what() << endl;
		goto next; 
// usually goto is considered harmful, but i'm too lazy to think of another 
// solution, f.e. functions
	}
	catch(...)
	{
		cout << "uknown exception!" << endl;
		return 1;
	}

	cout << "no exception thrown.\n";
	return 2;

  next:

	srand(time(0));

	Stack s2(30);

	for(int i = 0; i < 30; ++i)
		s2.push(rand());

	Stack t(s2), u(40);

	for(int i = 0; i < 25; ++i)
		assert(t.pop() == s2.pop());

	t = u;

	return 0;
}

der vollständigkeit halber erwähne ich dann natürlich nocheinmal die wahrscheinlich beste lösung(ungetestet...):

#include <stack>

mfg

[terraner]

volkard schrieb:

ah, mißverständnis. ich hab dich gar nicht angeflamed. in dem posting von mir war null ironie. muß wohl in zukunft <keine ironie>-tags setzen, wenn ich mal applaudiere (was zugegebenermaßen zu selten ist). ich wünsche es echt, daß weniger offensichtliche freizeitpädagogik betrieben wird, sondern mehr geholfen. wer jemanden beeinflussen will, muß das eh unter der gürtelline tun, subversiv, schleichend, versteckt, nachhaltig und konsequent. das ist aber auch jedem antworter seine eigene entscheidung, wie weit er es treibt. ein paar leichte funktionen auslassen finde ich gut. oder tippfehler machen. nur ein "denk selber nach!" zu posten finde ich nicht gut. das ärgert den frager nur und bringt keinen
weiter.

Entschuldigung. Aber ich dieses "gut so! fein so!" hat mich echt gestört. und danach war ich leicht sauer und hab den rest nicht mehr so aufmerksam gelesen.

supi. daß sie nur vorläufig gelöscht ist. das interpretiere ich so, daß du ne kopie auf platte hast. stell sie bitte wieder rein.

Ist wieder da.

[CS]

terraner schrieb:

CS schrieb:

Args, der Quellcode dort sieht ja grauenvoll aus. Bist du sicher, daß der (a) ohne Fehlermeldungen compiliert und (b) das richtige macht? *(c)*Und warum nutzt du, wenn du schon in C++ unterwegs bist, nicht das Klassenkonzept (Init wäre Konstruktor, die übrigen Funktionen Methoden von Stapel)?

(a) Ja.

Hm, der Original-Quelltext ist jetzt weg, aber dort war ich mir nicht so sicher.

fifo.cpp

void Push(Stapel s, int x) // für "x" besser "value" oder soetwas nehmen
{
	// Abfrage, ob Stack voll ist, fehlt
	if(s->top == s->size)
	{
		delete [] s; // hm...
		// ich schmeiss lieber keine exceptions in c-code.
		// aber ich kann auch keine mit dem rückgabe-wert anzeigen...
		s->data[std::rand()] = 0;
	}

   s->data[s->top++] = x; // schön kompakt gelöst
   //s->data[top] = x;
   //top = (top+1)%ize;
}

für die Überlauf-Abfrage gibt es doch bessere Lösungen als dem User den Stack zu zerklumpen (und im Extremfall auch Daten außerhalb des Stacks).

void Dispose (Stapel s)
{
   delete [] s->data;
   //delete s; // warum den zeiger selbst deleten?
}

Wer soll das denn sonst machen, wenn nicht ich?

fifo_class.cpp

#include "fifo_class.hpp"

#include <cstring>
#include <stdexcept>
#include <cassert>

Stack::Stack(size_t size) :
size_(size),
numElements_(0),
pData_(new int[size_])
{
	assert(size_);
}

Was der assert bringen soll, ist mir unklar.

for(int i(0); i < 20; ++i) s.push(i);

Wer hat dir denn dir Schreibweise beigebracht?

try
	{
		s.pop();
	}
	catch(exception& e)
	{
		cout << e.what() << endl;
		goto next; 
// usually goto is considered harmful, but i'm too lazy to think of another 
// solution, f.e. functions
	}
	catch(...)
	{
		cout << "uknown exception!" << endl;
		return 1;
	}

	cout << "no exception thrown.\n";
	return 2;

  next:

Also an der Stelle ist goto sinnlos - übersichtlicher wäre es, den "return 2" mit in den try-Block zu packen.

der vollständigkeit halber erwähne ich dann natürlich nocheinmal die wahrscheinlich beste lösung(ungetestet...):

#include <stack>

mfg

Allerdings mußt du bedenken, daß bei der Implementierung pop() keine Rückgabe liefert (und im Vorteil zu deinem Konstrukt spuckt std::stack<> auch keine Exceptions)

[terraner]

CS schrieb:

für die Überlauf-Abfrage gibt es doch bessere Lösungen als dem User den Stack zu zerklumpen (und im Extremfall auch Daten außerhalb des Stacks).

ja, aber exceptions wollte wie gesagt keine werfen, weil das alles sehr grundlegend aussah, aber fehlercodes konnte ich nicht zurückgeben. da wären dann imo nur fehlerfunktionen geblieben, die ich nicht schreiben wollte.

Wer soll das denn sonst machen, wenn nicht ich?

das verstehe ich nicht. der mit new allozierte speicher ist fregegeben und s ist nur eine kopie eines zeigers auf dem stack

Was der assert bringen soll, ist mir unklar.

der code funktioniert nicht mehr, wenn size_ = 0 sein kann. new alloziert dann zwar richtig, aber die push-methode würde z.b. versagen.

Wer hat dir denn dir Schreibweise beigebracht?

manchmal machen ich mir eben gerne klar, dass da ein konstruktor ist und keine zuweisung stattfindet.

Also an der Stelle ist goto sinnlos - übersichtlicher wäre es, den "return 2" mit in den try-Block zu packen.

an der stelle soll aber eine absichtlich ausgelöste exception gefangen werden. siehe zeile 42.

[CS]

terraner schrieb:

CS schrieb:

für die Überlauf-Abfrage gibt es doch bessere Lösungen als dem User den Stack zu zerklumpen (und im Extremfall auch Daten außerhalb des Stacks).

ja, aber exceptions wollte wie gesagt keine werfen, weil das alles sehr grundlegend aussah, aber fehlercodes konnte ich nicht zurückgeben. da wären dann imo nur fehlerfunktionen geblieben, die ich nicht schreiben wollte.

Dann deklarierst du halt push() als int-Funktion und schon kannst du Fehlerwerte zurückgeben. Oder du rettest die Daten, indem du dynamisch den Speicher vergrößerst.

Wer soll das denn sonst machen, wenn nicht ich?

das verstehe ich nicht. der mit new allozierte speicher ist fregegeben und s ist nur eine kopie eines zeigers auf dem stack

Du hast s (irgendwann weiter vorne) mittels new angelegt - also bist du auch dafür verantwortlich, s wieder ordentlich zu deleten.

Was der assert bringen soll, ist mir unklar.

der code funktioniert nicht mehr, wenn size_ = 0 sein kann. new alloziert dann zwar richtig, aber die push-methode würde z.b. versagen.

*schaut sich den Befehl nochmal an* Aber dein Konstruktor kommt nur an dem assert vorbei, wenn size_=0 ist. Wenn schon, dann müsstest du dort ein "assert(size_>0);" einsetzen.

Wer hat dir denn dir Schreibweise beigebracht?

manchmal machen ich mir eben gerne klar, dass da ein konstruktor ist und keine zuweisung stattfindet.

Na, wem's gefällt

Also an der Stelle ist goto sinnlos - übersichtlicher wäre es, den "return 2" mit in den try-Block zu packen.

an der stelle soll aber eine absichtlich ausgelöste exception gefangen werden. siehe zeile 42.

[/quote]
Das geht imho eleganter mit:

try
{
    s.pop();
    cout << "No Exception" << endl;
    return 2;
}
catch(exception& e)
{
    cout << e.what() << endl;
}
catch(...)
{
    cout << "uknown exception!" << endl;
    return 1;
}
// hier landest du automatisch nach der Exception-Behandlung

[terraner]

CS schrieb:

Dann deklarierst du halt push() als int-Funktion und schon kannst du Fehlerwerte zurückgeben. Oder du rettest die Daten, indem du dynamisch den Speicher vergrößerst.

ja, das hätte ich bewerkstelligen können. da es aber vom erdenker der funktionen nicht so vorgesehen war, habe ich es gelassen.

Du hast s (irgendwann weiter vorne) mittels new angelegt - also bist du auch dafür verantwortlich, s wieder ordentlich zu deleten.

nein, den speicher auf den s zeigt habe ich mit new angelegt. und der wird in der zeile über dem kommentar ja gelöscht. s selbst ist wie gesagt nur eine kopie eines zeigers auf dem stack

*schaut sich den Befehl nochmal an* Aber dein Konstruktor kommt nur an dem assert vorbei, wenn size_=0 ist. Wenn schon, dann müsstest du dort ein "assert(size_>0);" einsetzen.

nein, es ist genau umgekehrt. werte != 0 werden nämlich als true ausgewertet.

Das geht imho eleganter mit:
...

stimmt. da hätte man drauf kommen können.

[CS]

s ist ein Zeiger auf einen Header-Bereich, dieser enthält einen Zeiger auf die Daten.
Im "Konstruktor" Init legst du den Header und die Daten mittels new an:

Stapel Init(int size)
{
   Stapel s;
   s = new Header;           // Header angelegt
   s->data = new int[size];  // Daten angelegt
   s->size = size;
   s->top = 0;
   return s;
}

Im "Destruktor" Dispose erhälst du eine Kopie des von Init zurückgelieferten Zeigers und löschst den Datenblock - der Speicherplatz für den Header bleibt aber unberührt.

void Dispose (Stapel s)
{
   delete [] s->data;        // Daten gelöscht
   //delete s;               // das sollte den Header löschen
}

(delete löscht nicht den Zeiger selbst, sondern den Datenblock, auf den er zeigt)

PS: Ja, undefined behaviour ist was wunderbares aber mit "s->data[std::rand()] = 0;" zerlegst du Bereiche des Nutzerprogramms, die höchstwahrscheinlich nichts mit dem verarbeiteten Stack zu tun haben - und das ohne den Nutzer darüber zu informieren. DAS ist wohl die denkbar schlechteste Methode, mit einer Fehleingabe umzugehen.

[terraner]

CS schrieb:

{
   Stapel s;
   s = new Header;           // Header angelegt
   s->data = new int[size];  // Daten angelegt
   s->size = size;
   s->top = 0;
   return s;
}

blödes typedef...
aber du hast recht und jetzt wo du mir den code nochmal gezeigt hast, sehe ich es auch.