[Geschlossen] c: baum erstellen

http://cppgm.blogspot.com/2008/02/huffman-coding.html
http://alexvn.freeservers.com/s1/huffman_template_algorithm.html
http://cprogramminglanguage.net/code-snippets/huffman-coding.aspx
http://www.programmersheaven.com/download/49870/download.aspx

Beim letzten musste ne ZIP downloaden wo der code und das entsprechende Proggi drin sind.

Hab nix davon getestet aber vielleicht hilft's ja

danke danke werds mir anschauen ;-)
sonst frag ich noch mal

im letzen link ist das prog zum downloaden gemacht

1000 zeilen

auch wenn ich nicht alles brauch viel text ist und haufen ausgaben frag ich mich ob das projekt nach 1 semester c angemessen ist

wie auch immer versuch mich durchzukämpfen^^

Also nach einem Semester find ich's auch ganz schön krass. Was studierst Du denn?

Naja versuch Dich mal durchzuackern. Ich schau nachher bestimmt nochmal rein. Wenn noch Fragen sind. Hab auch nich so wirklich den Plan von Huffman, aber ganz kleines bissel von C++.

hier sieht man ganz gut, wie es funktioniert (animierte Graphik)

http://en.wikipedia.org/wiki/Huffman_coding

.

achso wenn mir einer helfen kann und will auch gerne per skype oder icq ;-)

In der Regel definiert man eine Knoten/Node-Klasse (bzw. in C ein struct), dass alles beschreibt, was in einem Knoten steht + dessen Kinder.

Der Baum ist dann durch den Wurzelknoten gegeben (der über die Kinder den Rest des Baums enthält).

Ansonsten:
- beim code posten code tags verwenden (nicht nur versuchen ;))
- bei einem groesseren projekt, was mehr als 10 Zeilen Hack sind aussagekräftige Variablennamen verwenden, insb. wenn jemand anders (der dir evtl. helfen will) das verstehen soll
- Wenn du code postest überleg dir, was jemand damit anfangen soll. Das Beispiel da parst doch nur irgendein file in irgendein struct. Ein File dessen format niemand hier kennt?
- wenn es irgendwie geht typisiert programmieren (alles = void*) ist nicht optimal

- dürft ihr c++ benutzen? Oder zumindest C-like schreiben, aber C++ kompilieren (z.b. für variablendeklarationen)

Ins richtige Forum verschoben

Gruß Alex

hihi

also

- beim code posten code tags verwenden (nicht nur versuchen Augenzwinkern )
was meinst damit genau?
den rest versuch ich mir zu herzen zu nehmen aber werde es jetzt nciht noch mal neu machen
kein C++!! nur c standart bibliotheken

hab noch nen bissel was gemacht:

ich liste mal meine variabeln auf und was sie bedeuten sollen bzw bewirken da kann mir denk ich besser geholfen werden

#define _CRT_SECURE_NO_WARNINGS
#define BUFFER_LEEREN {setvbuf (stdin,NULL,_IONBF,0);\
					setvbuf(stdin,NULL,_IOFBF,BUFSIZ);}
#define WARTEN_AUF_ENTER {getchar();}
#define pfadl  512  // länge das dateipfades
#define komment 512  // länge eines anzuhängenden kommentars
#define max 256  //gibt nur 256 zeichen und ich weiß das es bei der
                               null beginnt

typedef struct
{
	char fst;     //hmm nur abgeschrieben aber zum sortieren
	int snd;      //des arrey nach der häufigkeit hintergrund
} typeA;             //aber nun verstanden

int compare(const void* x , const void* y)
{
	return((typeA*)x)->snd - ((typeA*)y)->snd; // sortieren vom kleinsten
}                                                                           // zum grösten

int baum_code(char pfad[])
{
	int eingabe; // eingfabe für menueschleifen
	int aknoten=0; // anzahl zu erstellenden knoten (zeichenanzahl - 1)
	int i; //einfach zählvariable
	int j,k,l; //jetzt neu eingeführt um immer die kleinsten elemente zufinden
	unsigned int wert; // ja wert halt
	int anzahl[max];
	char datei_komment[komment]={""};
	int komp=1; //noch nicht benuzt
	int zeichenanzahl=0; // nicht benuzt
	typeA xs[max]; // von typedef struct
	FILE* fp; // erklährt sich

hoffe das ist erst mal so ok.

nun habe ich mir gedacht ich muss ja immer erst mal die 2 kleinsten elemente heraussuchen und dann einen knoten bilden
dies wollte ich erst mal so machen:

for(aknoten=0; aknoten-1; aknoten++)
			j=1000;
			k=1000;
			l=1000;
			{
				for(i=0;i<max;i++)
				{
					l = xs[i].snd;
					if((l<j)&&(l>0))
					{
						j=l;
					}
					else if((l<k)&&(l>0))
					{
						k=l;
					}
				}
			}

die 2 ersten und niedrigsten findet es auch und gibt es mir aus

nun die frage...nnnn^^^^

könnte mir einer auf mein programm bezogen ein struct knoten mal schreiben?
wie erstelle ich so einen knoten?
und wenn ich die schlefen danach wieder durchlaufe dürfen ja die ersten beiden elemente nicht wieder auftauchen wie ist da zu verfahren?(löschen wär wo denk ich nicht so gut)

danke schon mal

Original von DamPFwalzE
- beim code posten code tags verwenden (nicht nur versuchen Augenzwinkern )
was meinst damit genau?

genau das, was du jetzt gemacht hast.

kein C++!! nur c standart bibliotheken
tjo, schade drum

	int i; //einfach zählvariable
	int j,k,l; //jetzt neu eingeführt um immer die kleinsten elemente zufinden
	unsigned int wert; // ja wert halt
	FILE* fp; // erklährt sich

Man kann auch zu viel kommentieren, insb. wenn die Kommentare sinnlos sind.
Ich weiß, ich weiß, wie man's macht, macht man's verkehrt

könnte mir einer auf mein programm bezogen ein struct knoten mal schreiben?
wie erstelle ich so einen knoten?
und wenn ich die schlefen danach wieder durchlaufe dürfen ja die ersten beiden elemente nicht wieder auftauchen wie ist da zu verfahren?(löschen wär wo denk ich nicht so gut)

Nun hier liegt der Hund begraben. Abgesehen von der Standard Node-Klasse gibts natürlich ne Menge Methoden Bäume darzustellen und je nach Algorithmus ist das eine oder andere besser.
Ich kennen den Huffman nicht, also würde ich brute-force dumm da dran gehen und einen Baum explizit aufbauen. Evtl. geht das aber auch viel leichter.

So, habe den mal angeschaut. Also was ich meinte mit namen ist (wenn ich richtig rate):

typedef struct {
 	char fst;     //hmm nur abgeschrieben aber zum sortieren
 	int snd;      //des arrey nach der häufigkeit hintergrund 
} typeA;             //aber nun verstanden

->

typedef struct {
  char encodedChar;
  int weight;
} leafNode;

Mit c++ wäre das easy zu implementieren, weil's da passenden Datenstrukturen gibt zumindest der Algo der in wikipedia steht.

Das, was dich hier killt (aufwandsmäßig) ist die Priority-Queue. Allerdings sehe ich dass ihr da einen qsort habt. Wenn's also nicht performant sein soll, könnte man sich drumrumcheaten und einfach in jedem Schritt neu sortieren (horrible performance inside).

Ansonsten, wenn du den wiki link mal anschaust. Dort steht schon beschrieben, was in einer Node drinstehen sollte.

Zu deinem code: Die for-Schleife ist murks. Wozu willst du die beiden kleinsten finden, wenn du vorher sortiert hast. Das sind die beiden ersten ♦

int compare(const void* x , const void* y) {
 	return((typeA*)x)->snd - ((typeA*)y)->snd; // sortieren vom kleinsten }                                                                           // zum grösten

Soll es so sein, dass, wenn x > y der Wert positiv ist? Meistens definiert man den comparator nämlich als <. Das hängt natürlich von dem qsort ab.

baum ist immernoch in arbeit ;-) schon nen bissel sick die ganze sache

andere frage:

muss ja dann die komprimierte datei erstellen und speichern
und in den dateikopf gehören so sachen wie
dateilänge/komprimierungsmethode usw usw
es gibt ein vorgegebenes muster in HEX und reihenfolge...

nur wenn die reihenfolge zb so vorgegeben ist
schreib ich da einfach in die neue datei

dateilänge codewortlänge dateigröße

4H3DB0000

oder gibt es da ein muster wie man das in der datei anzulegen hat?
oder einfach hinterander weg weil ich selber ja weiß was wo steht und wie viele HEX-zeichen das jeweilige beschreiben?

dann noch meine datei hat die neue endung .HZP warum kann ich die mit dem editor öffnen?

ich hoffe die frage war verständlich?!?

wenn es ein vorgegebenes Muster (=format) gibt, dann solltest du eben das beachten.
Also einfach danach hineinschreiben (Groessen sollten vorgegeben sein).

Da die Datei eine hex datei wird, brauchst du einen hexeditor.

also die werte einfach nacheinander hineindonnern

bei mir in die ersten 4 zeilen? weil vorgegebene felder kann man ja in einer datei nicht deffinieren oder?

grüße

Zeilen? Das soll kein Text werden, so wie das aussieht!

So wie mir das aussieht soll das eine Hex-Datei werden.

dateilänge codewortlänge dateigröße

4H3DB0000

Hast du da eine bessere Spezifikation? Das da sind 4.5Bytes. Das wäre ein sehr komischer Dateiheader.

jaja ist ja noch way mehr^^