3. Probleme mit virtuellen Funktionen (vorsicht langer Text!!)

Probleme mit virtuellen Funktionen (vorsicht langer Text!!)

  • R

    Hallo,

    ich denk ich beschreib jetzt erst mal was ich überhaupt machen will:

    Ich habe ein Aufgabe zum Komprimieren von Dateien mit dem Huffman-Code, d.h. es wird aus der zu packenden Datei eine Häufigkeitstabelle aufgestellt, daraus wird ein Baum aufgebaut => in den Blättern sind die Zeichen, der Weg ist die Verschlüsselung der Zeichen, häufigere Zeichen bekommen kürzere Weg (Codes).
    In die komprimierte Datei wird erst der Baum geschrieben, anschließend wird jedes Zeichen verschlüsselt und auch weggeschrieben.

    Beim Lesen wird erst der Baum ausgelesen, dann die Zeichen entschlüsselt.

    Der Baum wird folgendermaßen weggeschrieben:
    Der Baum hat innere Knoten und Blätter, die inneren Knoten haben zwei Kinder, die Blätter nur einen Wert (das Zeichen). Der Baum wird durchlaufen, für alle Knoten des Wegs wird eine 0 geschrieben, ist man bei einem Blatt, wird eine 1, dann der Wert des Blattes geschrieben.
    Beispiel:
    0 => A
    1-0 => B
    1-1 => C
    wird so weggeschrieben:
    01A001B001C

    Die Daten werden BIT-weise geschrieben.
    Zum BIT-weisen Lesen gibt es einen "bitifstream is", der mit "is >> b", das "bit b" mit dem nächsten Bit aus der Datei belegt (ONE oder ZERO).

    Mein Problem taucht jetzt beim Lesen des Baumes auf:
    Normalerweise funktioniert alles einwandfrei.
    Aber:
    Bei einer TestDatei, in der die Zeichen (char)-86, (char)0, (char)2 stehen, passiert was sehr komisches:
    Gepackt sieht die Datei BIT-weise so aus (Die "-" Zeichen sind nur zur Übersichtlichkeit, stehen also nicht wirklich in der Datei):
    01-00000000-001-10101001-001-00000010-10011
    Die Funktion BinTrie::read(bitifstream& is) sollte also folgenden Baum aufbauen:
    0 => (char)0
    1-0 => (char)-86
    1-1 => (char)2
    Aus dem Rest des bitifstreams (10011) könnten dann die Zeichen (char)-86, (char)0, (char)2 wieder hergestellt werden.

    Hier mal die Funktionen:

    template <class T, class Key>
bool BinTrie<T, Key>::full(Node* n)
{
	Node* current = n;
	if (!current->getRight())
	{
		if (current->getVal())
		{
			cout << "true 1" << endl;
			return true;
		}
		cout << "false 1" << endl;
		return false;
	}
	else
	{
		while(current->getRight())
		{
			current = current->getRight();
		}
		if (current->getVal())
		{
			cout << "true 2" << endl;
			return true;
		}
		cout << "false 2" << endl;
		return false;
	}
}

template <class T, class Key>
void BinTrie<T, Key>::read(bitifstream& is)
{
	Node* newNode;
	Node* current = root;
	bit b;
	is >> b;

	// Es gibt nur ein Zeichen
	if (b == ONE)
	{
		root = new LeafNode(readChar(is));
	}
	else
	{
		while(!full(root))
		{
			current = root;
			is >> b;
			while(b == ZERO)
			{
				if (current->getLeft())
				{
					if (!full(current->getLeft()))
					{
						current = current->getLeft();
						is >> b;
					}
					else
					{
						if (current->getRight())
						{
							current = current->getRight();
							is >> b;
						}
						else
						{
							newNode = new InnerNode();
							cout << "new InnerNode = " << newNode << endl;
							current->setRight(newNode);
							current = current->getRight();
							is >> b;
						}
					}
				}
				else
				{
					newNode = new InnerNode();
					cout << "new InnerNode = " << newNode << endl;
					current->setLeft(newNode);
					current = current->getLeft();
					is >> b;
				}
			}

			char charFNLN = readChar(is);

			newNode = new LeafNode(charFNLN);
			cout << "new LeafNode = " << newNode << endl;

			if (!current->getLeft())
			{
				current->setLeft(newNode);
			}
			else
			{
				current->setRight(newNode);
			}

			if (!full(root))
			{
				is >> b;
			}
		}
	}

    Die Knoten sind innere Klassen von BinTrie:

    struct Node
{
	public:
		/** @brief Default-Konstruktor
		  */
		Node();

		/** @brief Liefert 0, da Node keine Kinder hat
		  */
		virtual Node* getLeft();

		/** @brief Liefert 0, da Node keine Kinder hat
		  */
		virtual Node* getRight();

		/** @brief Liefert 0, da Node keinen Wert hat
		  */
		virtual T getVal();

		/** @brief Setzt linkes Kind
		  * @param n Linkes Kind
		  * Muss redefiniert werden
		  */
		virtual void setLeft(Node* n);

		/** @brief Setzt rechtes Kind
		  * @param n Rechtes Kind
		  * Muss redefiniert werden
		  */
		virtual void setRight(Node* n);
};

/** @brief Blatt
  */
class LeafNode : public Node
{
	public:
		/** @brief Konstruktor
		  * @param t Wert des Blattes
		  */
		LeafNode(T t);

		/** @brief Liefert den Wert des Blattes
		  * @return Wert des Blattes
		  */
		T getVal();

	private:
		/** @brief Wert des Blattes
		  */
		T val;
};

/** @brief Innerer Knoten
  */
class InnerNode : public Node
{
	public:
		InnerNode();

		/** Konstruktor
		  * @param n1 Linkes Kind
		  * @param n2 Rechtes Kind
		  */
		InnerNode(Node* n1, Node* n2);

		/** @brief Liefert linkes Kind
		  * @return Linkes Kind
		  */
		virtual Node* getLeft();

		/** @brief Liefert rechtes Kind
		  * @return Rechtes Kind
		  */
		virtual Node* getRight();

		virtual void setLeft(Node* n);
		virtual void setRight(Node* n);

	private:
		/** @brief Linkes Kind
		  */
		Node* leftChild;

		/** @brief Rechtes Kind
		  */
		Node* rightChild;
};

//----------------------------------------------------------------------------
// BinTrie<T, Key>::Node
//----------------------------------------------------------------------------

// Node();
template <class T, class Key>
BinTrie<T, Key>::Node::Node()
{
}

// Node* getLeft();
template <class T, class Key>
typename BinTrie<T, Key>::Node* BinTrie<T, Key>::Node::getLeft()
{
	return 0;
}

// Node* getRight();
template <class T, class Key>
typename BinTrie<T, Key>::Node* BinTrie<T, Key>::Node::getRight()
{
	return 0;
}

// T getVal();
template <class T, class Key>
T BinTrie<T, Key>::Node::getVal()
{
	return 0;
}

// void setLeft(Node* n);
template <class T, class Key>
void BinTrie<T, Key>::Node::setLeft(Node* n)
{
	cout << "Node::setLeft()" << endl;
}

// void setRight(Node* n);
template <class T, class Key>
void BinTrie<T, Key>::Node::setRight(Node* n)
{
	cout << "Node::setRight()" << endl;
}

//----------------------------------------------------------------------------
// BinTrie<T, Key>::LeafNode
//----------------------------------------------------------------------------

// LeafNode(T t);
template <class T, class Key>
BinTrie<T, Key>::LeafNode::LeafNode(T t) : val(t)
{
}

// T getVal();
template <class T, class Key>
T BinTrie<T, Key>::LeafNode::getVal()
{
	return val;
}

//----------------------------------------------------------------------------
// BinTrie<T, Key>::InnerNode
//----------------------------------------------------------------------------

// InnerNode();
template <class T, class Key>
BinTrie<T, Key>::InnerNode::InnerNode() : leftChild(0), rightChild(0)
{
}

// InnerNode(Node* n1, Node* n2);
template <class T, class Key>
BinTrie<T, Key>::InnerNode::InnerNode(Node* n1, Node* n2) : leftChild(n1), rightChild(n2)
{
}

// Node* getLeft();
template <class T, class Key>
typename BinTrie<T, Key>::Node* BinTrie<T, Key>::InnerNode::getLeft()
{
	return leftChild;
}

// Node* getRight();
template <class T, class Key>
typename BinTrie<T, Key>::Node* BinTrie<T, Key>::InnerNode::getRight()
{
	return rightChild;
}

// void setLeft(Node* n);
template <class T, class Key>
void BinTrie<T, Key>::InnerNode::setLeft(Node* n)
{
	cout << "InnerNode::setLeft()" << endl;
	leftChild = n;
}

// void setRight(Node* n);
template <class T, class Key>
void BinTrie<T, Key>::InnerNode::setRight(Node* n)
{
	cout << "InnerNode::setRight()" << endl;
	rightChild = n;
}

    root (Wurzel von BinTrie) ist ein InnerNode mit zwei NullPointern.

    Hier kommt aber ein Segmentation-fault. Und zwar deshalb, weil er bei current->setLeft(newNode) die Methode setLeft von Node und nicht von InnerNode verwendet.
    Kann mir jemand sagen warum??? Ich verstehs nicht!
    Ich hab erst ewig gesucht bis ich das gefunden hab, es hilft mir aber leider nicht weiter!!
    Das ganze tritt normalerweise nicht auf, aber bei dieser TestDatei eben schon. Entweder liegt das daran, dass da (char)0 drinsteht, oder an irgendwas anderem, ich weiß es nicht.

    Die Funktion read(...) macht in diesem Beispiel folgende Ausgabe:

    false 1new LeafNode = 0xa0415c0InnerNode::setLeft()false 1false 1false 1new LeafNode = 0xa0415d0Node::setLeft()false 1false 1false 1new LeafNode = 0xa0415e0Node::setLeft()false 1false 1false 1new InnerNode = 0xa0415f0Node::setLeft()new LeafNode = 0xa041600Segmentation fault (core dumped)

    Also am Anfang nimmt er noch das richtigr setLeft(), dann aber nicht mehr.

    An alle, die das bis hier her gelesen haben, ert mal vielen Dank dafür, wenn jmd noch eine Idee haben sollte, wärs super!!

    mfg
    rodo

    0
  • R

    Hallo,

    hab den Fehler gefunden:
    Die Abfrage ob ein Knoten ein LeafNode ist oder nicht, habe ich über getVal() != false gemacht. (Für Nodes liefert getVal() nämlich false).
    Das geht aber nur solang gut, wie in val nicht der Wert 0 steht...

    mfg
    rodo

    0
Anmelden zum Antworten