Hallo, ich habe aus Interesse angefangen ein kleines Programm zu schreiben, welches .txt Dateien mit dem Huffman-Algorithmus komprimieren soll.
Ich bin soweit, dass ich die Zeichen mit ihrer Häufigkeit in ein Struct Array gespeichert habe. Nun geht es daran den Baum aufzubauen. Wie man einen binären Baum normalerweise aufbaut weiß ich aber bei Huffman muss ich das ganze ja von unten angehen und komm nicht so recht weiter. Hier mal mein bisheriger Quellcode in C++:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <iostream>
#include <windows.h>
#include <fstream>
#include <stdio.h>
using namespace std;
struct knoten
{
int freq; //summe aus häufigkeit der beiden kindknoten
//die beiden kindknoten
knoten *links;
knoten *rechts;
};
struct Freq
{
char ch; //1 Zeichen
int freq; //Häufigkeit des Zeichens
};
int frequency(char **file)
{
Freq freq[256];
ifstream f;
int a = 0;
f.open(file[0], ios_base::in);
if(!f)
cout << "error while opening file " << file[0] << endl;
char buf;
while(!f.eof())
{
f.get(buf);
for(int b = 0; b <= 256; b++)
{
if(buf == freq[b].ch) //Aktuelles Zeichen ist in freq[] schon vorhanden -> Häufigkeit erhöhen
{
freq[b].freq++;
break;
}
else if(b == 256) //Noch nicht vorhanden, neu einfügen
{
freq[a].ch = buf;
freq[a].freq = 1;
a++;
}
}
}
//Ausgabe der Häufigkeiten
for(int b = 0; b <= 256; b++)
{
if(freq[b].freq < 1)
break;
cout << freq[b].ch << "(" << freq[b].freq << ")" << " ";
}
cout << endl;
return 0;
}
int main(int argc, char** argv)
{
int a = 1;
while((argc--)-1)
{
cout << "File: " << argv[a] << endl;
frequency(&argv[a]);
a++;
}
system("PAUSE");
return 0;
}
|
Nun müsste ich Knoten erzeugen. Aber wie geh ich das am besten an? Ich will ja nicht für jedes Element im Freq-Array einen extra Knoten anlegen, also nicht: knoten1, knoten2....
Ich müsste mir ja nun aus meinem Freq Array, 2 Einträge raus suchen mit dem geringsten Auftreten. Dann könnte ich aus der Summe der Beiden einen Knoten anlegen mit den beiden Einträgen als Kindsknoten. Im nächsten Schritt das Gleiche, nur das ich jetzt nicht mehr nur im Freq Array suchen muss sondern auch in dem bereits vorhandenen Knoten.
Ihr seht, mir fehlt die richtige Vorgehensweise, vielleicht kann mir ja jemand ein paar Tips geben. Ich will keine links zu fertigen Lösungen! Ich will das ganze machen weil es mich interessiert und nicht weil ich es wirklich brauche.
Danke schonmal.