programm erzeugt undefiniertes verhalten

otze

seufz, dass an mir auch kein Kelch vorübergeht...
also, ich schreib mir ein programm, welches nach der Huffmann verschlüsselung arbeitet http://www-user.tu-chemnitz.de/~mfie/compproj/2common.htm#huffmann

dazu hab ich eine funktion geschrieben, die einen header mit den zeichenhäufigkeiten erwartet,einen vector der hinterher den Baum enthalten soll, und einen zeiger auf die Wurzel der Knoten(also der Knoten von dem man alle andren erreichen kann)
die Knoten haben folgende struktur:

struct Node{
    bool isNode;
    Node* Node1;
    Node* Node2;
    Node* root;
    char Zeichen;
    int frequenzy;
};

der reihe nach:
boolscher wert der bestimmt ob das ein knoten ist, oder ein endzeichen
Zeiger auf einen untergeordneten Knoten
zeiger auf den 2. untergeordneten Knoten
Zeiger auf den übergeordneten Knoten
Das Zeichen
vorkommen des Knotens

hier die Funktion:

void createtree(header Header,vector<Node> &Knoten,Node* &Wurzel){
    vector<Node*> freqlist;
    for(int i=0;i<511;++i){
        Node Grundknoten={false,NULL,NULL,NULL,(char)(i),Header.zeichen[i]};
        Knoten.push_back(Grundknoten);
        freqlist.push_back(&Knoten[Knoten.size()-1]);
    }
    while(freqlist.size()>1){
        sort(freqlist);
        //jeder abgeleitete Knoten hat die untergeordneten Knotenzeiger auf die Knoten von denen er abgeleitet wurde,hat erstmal noch keinen  übergeordneten Knoten,
        //und seine frequenzy ist die summe der frequenzys seiner untergeordneten Knoten
        Node neuerKnoten={true,freqlist[0],freqlist[1],NULL,0,freqlist[0]->frequenzy+freqlist[1]->frequenzy};
        Knoten.push_back(neuerKnoten);
        //hier werden die root zeiger der untergeordneten Knoten auf den aus ihnen hervorgegangenen Zeiger ausgerichtet
        freqlist[0]->root=&Knoten[Knoten.size()-1];
        freqlist[1]->root=&Knoten[Knoten.size()-1];
        //der neue Knoten braucht in der freqlist auch noch einen Zeiger, damit aus ihm neue Knoten entstehen können
        freqlist.push_back(&Knoten[Knoten.size()-1]);
        //Die Zeiger der Knoten die nun einen neuen übergeordneten haben, werden nichmehr gebraucht, drumw eg mit ihnen
        freqlist.erase(freqlist.begin(),freqlist.begin()+2);
    }
    //der letzte pointer der übrig bleibt muss wohl oder übel der sein, der auf die Wurzel zeigt
    Wurzel=freqlist[0];
    //hier findet der test an, als ergebnis->undefiniertes Verhalten
    for(size_t i=0;i<Knoten.size()-1;++i){
        cout<<Knoten[i].frequenzy<<" ";
    }
}
//die sort funktion
void sort(vector<Node*> &Knoten){
    bool change=true;
    Node* temp;
    while(change==true){
        change=false;
        //sortierschleife, es wird jedes objekt mit seinem nachfolger verglichen
        //Knoten.size()-2 ist dafür da, damit man nich ausversehen ausserhalb des array bereichs landet
        for(size_t i=0;i<Knoten.size()-2;i++){
            if(Knoten[i]->frequenzy>Knoten[i+1]->frequenzy){
                temp=Knoten[i];
                Knoten[i]=Knoten[i+1];
                Knoten[i+1]=temp;
                change=true;
            }
        }
    }
}

Das programm arbeitet nach folgendem prinzip: zuerst wird für jedes der 511 header einträge ein Knoten erstellt.
gleichzeitig wird für jeden Knoten auch ein passender pointer in der freqlist erstellt.
nun werden die pointer nach der frequenzy der objekte auf welche sie zeigen aufsteigend sortiert.
die beiden kleinsten werden immer genommen, und zu einem neuen Knoten mitsamt Pointer zusammengefasst.
Der neue Knoten hat die Summe der frequenzies der Knoten aus welchen er entstanden ist(bsp knoten1=20 Knoten 2=30 neuer Knoten=50).
Desweiteren zeigt der neue Knoten natürlich noch auf die Knoten aus denen er entstanden ist-ein Baum entsteht.
Die Grundknoten erhalten dann einen Zeiger auf den neuen Knoten,und ihre Pointer in der freqlist werden entfernt.
Das Spiel wiederholt sich, bis in der freqlist nurnoch ein pointer ist-der Pointer, welcher auf die Wurzel zeigt(also der Knoten, der alle andren Knoten enthält,und somit auch die summe aller frequenzys besitzt).

Nun zum undefinierten verhalten:
ich geb ja alle Knoten aus,da mein Beispieltext nur aus 26 verchiedenen Zeichen besteht, zeigen die meisten Knoten 0, bis auf 26, welche 1 zeigen.
rein theoretisch müssten danach(nochmal jeden menge 0en)dann 6 4en,dann eine 6,2 8ten eine 10,2*14(usw) bis am ende eine 26 über bleibt.
am amfang stimmts noch, soweit ich das beurteilen kann, vielleicht sind 1-2 zahlen zuviel, aber das konnte ich nicht so schnell erkennen.
aufjedenfall folgt bei mir nach der 16 die 206, dann 600,dann 4826...bis dann der letzte Knoten 302230702 anzeigt-etwas viel.
Die knotenanzahl sollte mit 1021 stimmen,daran sollte es also nicht liegen.
Ich bin schon seit ca ner stunde auf der Suche nach diesem üblen fehler,und weis nichmehr weiter

ich hoffe, die infos reichen für euch, sodass ihr den fehler finden könnt...ich kanns nicht

Krösus

Deine Formatierung ist sehr schwer lesbar.

Der Übersichtlichkeit halber schlage ich folgendes Verfahren vor:

Ich würde die Einzelzeichen zunächst auch einmal in einem Container halten, OK.

Dann würde ich aber einen neuen Container erzeugen, der alle "Waisen" enthält, also alle Knoten wo root == 0. Anfangs werden dazu die Adressen der Knoten aus dem übergebenen Container in den Waisen-Container übernommen. Danach wird Schritt für Schritt aus zwei Waisen-Knoten ein neuer Vater-Knoten gebildet; die beiden ehemaligen Waisen (jetzt besitzen beide den gemeinsamen Vater) verschwinden aus dem Waisen-Container, und der neue Vater wird dort aufgenommen. Dies wiederholt sich solange, bis nur noch ein einziger Knoten im Waisen-Container ist.

Der Waisen-Container wird am Ende der createtree()-Funktion gelöscht, und die Funktion gibt als Wurzel den zuletzt erzeugten Vater-Knoten zurück; von diesem ausgehend kann man ja zu allen "Blättern" (d. h., Node1 != 0, Node2 != 0) gelangen. Alle Knoten mit Verzweigungen sind in der createtree()-Funktion mit new angelegt. Alle Blätter hingegen existierten schon vorher.

Auch würde ich keinen Aufwand darauf verschwenden, den Waisen-Container zu sortieren, sondern stattdessen simpel und einfach von vorne nach hinten durchgehen und den Knoten mit der niedrigsten Frequenz suchen, dann nochmal durchgehen und den Knoten mit der zweitniedrigsten Frequenz suchen. Das ist zwar nicht unbedingt performant, aber dafür sicher und wenig aufwendig, und beim Erstellen des Baumes braucht man nicht besonderen Wert auf Geschwindigkeit zu legen; außerdem kann diese später immer noch gesteigert werden.

Als Waisen-Container schlage ich eine Liste vor. Der ursprüngliche Container, der am Schluß alle Blätter enthalten wird, kann ruhig ein Vektor bleiben. Die Container-Implementierung spielt aber eigentlich keine Rolle.

Man sollte sich auch nicht auf char (8 Bits pro Zeichen) festlegen, sondern flexibel sein. Außerdem schreibst Du etwas von 511 Einträgen, das wären ja 9 Bit!

Code (ohne Gewähr):

class KNOTEN
{ 
    BOOL IstBlatt;
	union
	{
		KNOTEN* Kinder[2];
	    long Zeichen;
	} Data;
	KNOTEN* Vater;
    int Freq;
public:
	static int BitsProZeichen;
	KNOTEN(KNOTEN*, KNOTEN*, int);
	KNOTEN(long, int);
	~KNOTEN();
	int Freqenz() { return Freq; }
	void ErzeugeCode(long*, int*);
};

KNOTEN::KNOTEN(KNOTEN* Kind1, KNOTEN* Kind2, int iFreq)
{
	Freq = iFreq;
	IstBlatt = FALSE;
	Vater = NULL;
	Data.Kinder[0] = Kind1;
	Data.Kinder[1] = Kind2;
	Kind1->Vater = this;
	Kind2->Vater = this;
}

KNOTEN::KNOTEN(long Zeichen, int iFreq)
{
	Freq = iFreq;
	IstBlatt = TRUE;
	Vater = NULL;
	Data.Zeichen = Zeichen;
}

KNOTEN::~KNOTEN()
{
	if(!IstBlatt)
	{
		if(Data.Kinder[0])
			if(!Data.Kinder[0]->IstBlatt)
				delete Data.Kinder[0];
			else
				Data.Kinder[0]->Vater = NULL;
		if(Data.Kinder[1])
			if(!Data.Kinder[1]->IstBlatt)
				delete Data.Kinder[1];
			else
				Data.Kinder[1]->Vater = NULL;
	}
	else if(Vater)
	{
		if(Vater->Data.Kinder[0] == this)
			Vater->Data.Kinder[0] = NULL;
		else if(Vater->Data.Kinder[1] == this)
			Vater->Data.Kinder[1] = NULL;
	}
}

void KNOTEN::ErzeugeCode(long* piBits, int* piAnzBits)
{
	if(IstBlatt)
		*piBits = *piAnzBits = 0;
	if(Vater)
	{
		if(Vater->Data.Kinder[0] == this)
			*piBits |= (1 << *piAnzBits);
		*piAnzBits++;
		Vater->ErzeugeCode(piBits, piAnzBits);
	}
}

//ErzeugeBaum()        : Erzeugt den Huffman-Baum
//KNOTEN* [out]        : Wurzelknoten, von wo aus man zu allen Blaettern gelangen kann
//ZeichenHaeufktn [in] : Container, der alle Einzelzeichen zusammen mit ihren Haeufigkeiten
//                       (Frequenzen) in Form von KNOTEN-Objekten enthaelt; diese
//                       KNOTEN-Objekte wurden mittels new KNOTEN(Zeichen, Freq) erzeugt
KNOTEN* ErzeugeBaum(CONTAINER<KNOTEN*>* ZeichenHaeufktn)
{
	int iIndex1, iIndex2;
	KNOTEN* Kind1, Kind2, Vater;
	CONTAINER<KNOTEN*> AlleWaisen;
	FOR_EACH(ZeichenHaeufktn)
		AlleWaisen.Append(ZeichenHaeufktn->CurrElem());
	END_EACH
	while(AlleWaisen.Size() > 1)
	{
		KleinsteFreq(&AlleWaisen, &iIndex1, &iIndex2); //s. u.
		if(iIndex1 > iIndex2)
		{
			int iTausch = iIndex1;
			iIndex1 = iIndex2;
			iIndex2 = iTausch;
		}
		AlleWaisen.GoTo(iIndex1);
		Kind1 = AlleWaisen.CurrElem();
		AlleWaisen.GoTo(iIndex2);
		Kind2 = AlleWaisen.CurrElem();
		Vater = new KNOTEN(Kind1, Kind2, Kind1->Frequenz() + Kind2->Frequenz()); //s. o.
		//AlleWaisen.GoTo(iIndex2); //Unnoetig, da stehen wir ja schon!
		AlleWaisen.Remove();
		AlleWaisen.GoTo(iIndex1);
		AlleWaisen.Remove();
		AlleWaisen.Append(Vater);
	}
	return Vater;
}

//KleinsteFreq()  : Sucht die beiden Knoten mit den kleinsten Frequenzen
//AlleWaisen [in] : Container mit HKNOTEN
//piIndex1 [out]  : Index des Knotens mit der kleinsten Frequenz
//piIndex2 [out]  : Index des Knotens mit der zweitkleinsten Frequenz
void KleinsteFreq(CONTAINER<KNOTEN*>* AlleWaisen, int* piIndex1, int* piIndex2)
{
	//Durchsuche den Container
	int iFreq, iMinFreq = -1, iIndex = 0;
	FOR_EACH(AlleWaisen)
		iFreq = AlleWaisen->CurrElem()->Freqenz();
		if((iMinFreq < 0) || (iFreq < iMinFreq))
		{
			iMinFreq = iFreq;
			*piIndex1 = iIndex;
		}
		++iIndex;
	END_EACH
	//Durchsuche den Container ein weiteres Mal
	// - Performanz-technisch nicht ideal, aber was soll's?
	iMinFreq = -1;
	iIndex = 0;
	FOR_EACH(AlleWaisen)
		if(iIndex != *piIndex1)
		{
			iFreq = AlleWaisen->CurrElem()->Freqenz();
			if((iMinFreq < 0) || (iFreq < iMinFreq))
			{
				iMinFreq = iFreq;
				*piIndex2 = iIndex;
			}
		}
		++iIndex;
	END_EACH
}

Die CONTAINER-Klasse(n) und die FOR_EACH-Implementation mußt Du Dir noch dazudenken.

otze

erstmal zu den 511->hast recht, hab ausversehen die 0 noch als möglichkeit mit draufadiert^^
Man sollte sich auch nicht auf char (8 Bits pro Zeichen) festlegen, sondern flexibel sein. ->nein,mit 8 Bit blocks zu arbeiten ist schon sehr effektiv, da mit größeren Werten die erstellung des baumes zu langsam wird,und mit kleineren Werten die kompressionsraten zu sehr sinken,
eine flexible Bitanzahl brauch man beim dynamischen LZ78 verfahren.

zum thema sortieren: der bubblesort algorithmus ist erstmal ganz gut, später,wenn ich den dummen fehler hier ausgemerzt hab, werd ich aber eine dynamische sortierung anstreben, wo erst sortiert wird, wenns nötig ist.

denn das ist das schöne am bubblesort:da die einträge aufsteigend sortiert sind,kannst du rein theoretisch einen neuen Knoten erstellen, und von dem die frequenzy speichern.dann baust du solange neue Knoten, bis ein "Weise" die selbe(oder eine höhere) frequenzy wie der Knoten hat, von dem du die frequenzy gespeichert hast,denn erst dann ist es eigentlich wieder nötig zu sortieren.

noch effektiver wäre dann noch ein bubblesort, der nicht von vorne nach hinten, sondern von hinten nach vorne durchläuft,das würde das listensystem um längen hinter sich zurücklassen...

aber darum gehts hier nicht, dass hauptproblem ist, dass
freqlist[0]->frequenzy+freqlist[1]->frequenzy einen abnormalen wert ergibt, der irgendwo im exponentiellen bereich liegt^^

//edit mir fällt da grad was auf^^
Dann würde ich aber einen neuen Container erzeugen, der alle "Waisen" enthält, also alle Knoten wo root == 0. Anfangs werden dazu die Adressen der Knoten aus dem übergebenen Container in den Waisen-Container übernommen. Danach wird Schritt für Schritt aus zwei Waisen-Knoten ein neuer Vater-Knoten gebildet; die beiden ehemaligen Waisen (jetzt besitzen beide den gemeinsamen Vater) verschwinden aus dem Waisen-Container, und der neue Vater wird dort aufgenommen. Dies wiederholt sich solange, bis nur noch ein einziger Knoten im Waisen-Container ist.

ist das gleiche, was ich im moment mache,ich speicher die adressen meiner Knoten in der freqlist, welche ich nach der frequenzy der Knoten auf welche sie zeigen sortiere.
dann pack ich mir immer die kleinsten, machd araus nen neuen Knoten, und speicher seine addresse in der liste, wobei ich die beiden nun nichtmehr verweisten pointer aus der liste kicke^^

otze

hab den fehler gefunden,auch wenn ich nicht weis, was ich dran ändern soll..

//funktioniert
Knoten.push_back(Grundknoten);
//zeiger auf den zuletzt erstellten Knoten richten->funktioniert nicht
freqlist.push_back(&Knoten.back());

wie muss die 2. zeile richtig aussehen?
in meinen Versuchen ist mir nämlich desweiteren aufgefallen, dass direkt nach der erstellung der pointer, zwar jeder Knoten den richtigen wert hat,und manche pointer auch, aber manche pointer zeigen einfach irgendwo hin, und das verwirrt mich..

Bashar

Ich hab den Thread nicht gelesen, aber mal ins blaue ... hast du bedacht, dass ein Vektor eine Kapazität hat? Normalerweise ist er nicht ganz ausgelastet, aber je mehr Elemente du mit push_back anhängst (oder einfügst) desto näher kommst du der Grenze. Wenn sie überschritten wird, fordert der Vektor mehr Speicher an, kopiert alles in den neuen Speicher um und löscht den alten Speicher. Das passiert jedesmal, wenn du an die Kapazitätsgrenze stößt.

Logischerweise hat das zur Folge, dass alle Pointer, die in den alten Speicherblock zeigen, mit so einer Neu-Allokation ungültig werden. Vielleicht solltest du einen Container verwenden, bei dem push_back garantiert keine Elemente verschiebt. In Frage kämen deque und list (bei list bleiben Pointer sogar bei insert gültig).

otze

naargh das kanns natürlich sein...
könnte es da abhilfe schaffen, den vector mit sagen wir mal 510 einheiten zu erstellen?

Bashar

Du kannst die Kapazität mit der Memberfunktion reserve festlegen/erhöhen:

vector<Foo> myvec;
myvec.reserve(100);

Wenn du eine Obergrenze kennst, kannst du das machen und so Neuallokationen vermeiden.

otze

juhu, es klappt, nun muss ich mich nurnoch dransetzen, wiehoch die knotenanzahl im worst case is,will ja nich, dass mein prog mittendrin aufgibt

//edit was red ich fürn quatsch, das sind doch statisch 1019 knoten^^
//edit2 also, vielen dank an alle,ich glaub, wir hätten ewig suchen können, hätte bashar nich diesen grandiosen einfall gehabt