huffman σε C

takis_tz · 15 Δεκεμβρίου 2007

ψαχνω για υλοποιηση της κωδικοποίησης Huffman σε κώδικα C. Έχει κανείς καμιά ιδέα για το που μπορώ να δω ανάλογους κώδικες; Έψαξα στο google αλλά δεν είδα κάτι σχετικό με αυτό που ψάχνω. Περιληπτικά αυτό που θέλω είναι ένα πρόγραμμα σε C, που θα κάνει τα πιο κάτω:

1-υπολογισμός πιθανοτήτων

2-δημιουργία δένδρου Huffman

3-κωδικοποίηση αρχείου

4-αποκωδικοποίηση αρχείου

bokarinho · 15 Δεκεμβρίου 2007

ψαχνω για υλοποιηση της κωδικοποίησης Huffman σε κώδικα C. Έχει κανείς καμιά ιδέα για το που μπορώ να δω ανάλογους κώδικες; Έψαξα στο google αλλά δεν είδα κάτι σχετικό με αυτό που ψάχνω. Περιληπτικά αυτό που θέλω είναι ένα πρόγραμμα σε C, που θα κάνει τα πιο κάτω:
1-υπολογισμός πιθανοτήτων

2-δημιουργία δένδρου Huffman

3-κωδικοποίηση αρχείου

4-αποκωδικοποίηση αρχείου

Να σε βοηθήσουμε φίλε μου με την άσκηση σου αλλά για βοήθησε με και εσύ. Η βασική λοιπόν ιδέα του Huffman είναι η συμπίεση, το θέμα είναι όμως ότι για να φτάσουμε στο Huffman ο οποίος προφανώς αναφέρεται σε ένα data set θα πρέπει να μιλήσουμε για την εντροπία κάθε συμβόλου που ανήκει στο data set αυτό. Ως εντροπία S ορίζουμε πχ για ένα σύμβολο z το:

Sz = -logPz όπου Pz είναι η πιθανότητα εμφάνισης συμβόλου μέσα στο σύνολο δεδομένων μας ή στο data set μας. Αν έχουμε 32 σύμβολα λοιπόν και το z εμφανίζεται 8 φορές μέσα στα 32 σύμβολα τότε Pz = 8/32 = 1/4 άρα:

Sz = -log(1/4) = 2 bits.

Αυτό πολύ απλά τι σημαίνει και εδώ είναι η όλη φιλοσοφία του Huffman. Ότι αν ισχύει η υπόθεση που έκανα για το z τότε για να εκφράσουμε το z δεν χρειαζόμαστε 8 bits = 1 byte όπως κανονικά χρειαζόμαστε για την αναπαράσταση ενός χαρακτήρα αλλά μόνο 2, τα υπόλοιπα 6 θα ήταν πλεονασμός. Αυτό είναι και η συμπίεση που επιτυγχάνουμε.

Ένα παράδειγμα για να το κατανοήσεις είναι το εξής:

Έστω λοιπόν ότι έχουμε ένα data set το οποίο αποτελείται από 72 χαρακτήρες και περιέχει 5 διαφορετικά σύμβολα, πχ το U,V,X,Y,Z τα οποία εμφανίζονται ανά τυχαίες εμφανίσεις μέσα στο data set.

Έστω ότι το U εμφανίζεται 12 φορές, έχουμε λοιπόν Su = -log(12/72) = 2.5849 bits. Εφόσον εμφανίστηκε 12 φορές τότε η συνολική εντροπία για το U θα είναι 12 * 2.5849 = 31.019 bits για να εκφράσουμε το U και αν ακολουθήσουμε ανάλογα το ίδιο σκεπτικό για τα άλλα 4 γράμματα και προσθέσουμε τις συνολικές εντροπίες του κάθε συμβόλου θα καταλήξουμε ότι τα συνολικά bits που χρειαζόμαστε για την αναπαράσταση του data set θα είναι πολύ λιγότερα από τα

72(chars) * 8(bits/chars) = 576 bits που θα χρειαζόμασταν χωρίς συμπίεση. Αυτή είναι και η λογική του Huffman, να πετύχει συμπίεση στα bits χωρίς να χαθεί η πληροφορία δηλαδή η αναπαράσταση του data set μας.

Τώρα στο προγραμματιστικό κομμάτι:

Θα φτιάξουμε ένα δυαδικό δέντρο το όποιο θα παράγει τους κωδικούς Huffman οι οποίοι είναι οι κωδικοί που αντιστοιχούν στα σύμβολα που θα παράγουν ως αποτέλεσμα την συμπίεση.

Για να χτίσουμε το δέντρο μας, το οποίο χτίζεται ανάποδα δηλαδή από τα φύλλα προς τα επάνω:

1. Αρχικά βάζουμε τα σύμβολα με τις συχνότητες τους, κάθε σύμβολο αναπαριστά και ένα δέντρο.

2. Συγχωνεύουμε τα 2 δέντρα που έχουν τις μικρότερες συχνότητες και σώζουμε το άθροισμα των 2 αυτών συχνοτήτων ως ρίζα στο δέντρο που δημιουργείται.

3.Συνεχίζουμε παίρνοντας τα άλλα δύο επόμενα και εκτελώντας την ίδια διαδικασία σταματάμε όταν μείνει ένα δέντρο δηλαδή το τελικό Huffman δέντρο μας που προκύπτει από τις διαδοχικές συγχωνεύσεις.

Η ρίζα του τελικού δέντρου θα περιέχει το σύνολο από τα σύμβολα που υπάρχουν στο data set πχ 72, και οι κόμβοι φύλλα δηλαδή οι τέρμα κάτω κόμβοι περιέχουν τα σύμβολα και τις συχνότητες εμφάνισης τους.

Όταν μείνει αυτή η δομή που μόλις περιέγραψα όταν κινούμαστε στο δέντρο από την ρίζα για ένα φύλλο πχ το U, βάζουμε 0 όταν πάμε αριστερά και 1 όταν πάμε δεξιά μέχρι να καταλήξουμε στο σύμβολο μας.

Έτσι για το U πχ θα έχουμε:

U: 101

V: 01 κτλ.

Ήταν ένα μικρό tutorial για τους κώδικες Huffman, σκέφτομαι να το επεκτείνω μιας και το θέμα είναι ενδιαφέρον, αν θέλουν οι moderators το κάνουν sticky.

Για αρχή σου παραθέτω ένα τρόπο να υπολογίσεις την συχνότητα των γραμμάτων σε ένα Buffer.

Τελικά εσένα ποιο είναι το data set σου, δεν σας έχει δώσει λεπτομέρειες ο καθηγητής ή όποιος είναι αρμόδιος, τα σύμβολα;

PS: To να φτιάξεις αυτό το πρόγραμμα είναι αρκετά επίπονη διαδικασία, θέλει υψηλή προγραμματιστική ικανότητα και να υλοποιήσεις βασικές δομές όπως τα δυαδικά δέντρα, συναρτήσεις που να δημιουργούν, να καταστρέφουν, να κάνουν ευθύ και αντίστροφο traverse στο δέντρο, εισαγωγή κόμβου, κτλ, επίσης θα πρέπει να παίξουμε με τα bits δηλαδή να φτιάξουμε συναρτήσεις που να παίζουν με bits, πχ XOR, και ίσως και ουρές προτεραιότητας για τις συγχωνεύσεις. Δύσκολα τα πράγματα, σίγουρα δεν σας έχει δώσει κάποια άλλη πορεία;

bokarinho · 15 Δεκεμβρίου 2007

Τρόπος υπολογισμού της συχνότητας των γραμμάτων σε ένα κείμενο που δίνεται από τον χρήστη στη είσοδο:

>
TurboC++ with CodeGuard
Borland

>
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//---------------------------------------------------------------------------

/* Get a Text Buffer. */
char *GetBuffer(int TextSz)
{
char *BufText = NULL;
char *Getz = NULL;
BufText = malloc(TextSz * sizeof(char));
if(BufText)
{
	printf("Enter the text:\n");
	Getz = fgets(BufText, TextSz, stdin);
	if(Getz)
	{
		BufText[strlen(BufText)-1] = '\0';
		return BufText;
	}
	else
	{
		printf("ErrorReporter:Error during Reading Process.\n");
		return NULL;
	}
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return NULL;
}
}

int GetBufferAlt(char **BufferText, int TextSz)
{
char *BuffText = malloc(TextSz * sizeof(char));
if(BuffText)
{
	printf("Enter the text:\n");
	fgets(BuffText, TextSz, stdin);
	BuffText[strlen(BuffText)-1] = '\0';
	*BufferText = BuffText;
	return 0;
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return -1;
}
}
/* Store the Frequences of Each Character in Text. */
int* CountFreq(char *Text)
{
int i;
int TextSz = strlen(Text);
int *Freq = calloc(TextSz,sizeof(int));
if(Freq)
{
	for(i = 0; i < TextSz; i++)
		Freq[Text[i]]++;
	return Freq;
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return NULL;
}
}
int main(int argc, char* argv[])
{
unsigned int i;
int *Fr = NULL;
char *Text = NULL;
Text = GetBuffer(1024);
Fr = CountFreq(Text);
for(i = 0; i < strlen(Text); i++)
	printf("Letter %c: Frequency in Text: %d\n", Text[i], Fr[Text[i]]);
printf("\n");
/* Free Memory. */
free(Fr);
free(Text);
printf("Hit the enter key to end the program....\n");
getchar();
return 0;
}
//---------------------------------------------------------------------------

Τυπωμένα Αποτελέσματα:

Enter the text:

Ares Mares Koykoynares!!

Letter A: Frequency in Text: 1

Letter r: Frequency in Text: 3

Letter e: Frequency in Text: 3

Letter s: Frequency in Text: 3

Letter : Frequency in Text: 2

Letter M: Frequency in Text: 1

Letter a: Frequency in Text: 2

Letter r: Frequency in Text: 3

Letter e: Frequency in Text: 3

Letter s: Frequency in Text: 3

Letter : Frequency in Text: 2

Letter K: Frequency in Text: 1

Letter o: Frequency in Text: 2

Letter y: Frequency in Text: 2

Letter k: Frequency in Text: 1

Letter o: Frequency in Text: 2

Letter y: Frequency in Text: 2

Letter n: Frequency in Text: 1

Letter a: Frequency in Text: 2

Letter r: Frequency in Text: 3

Letter e: Frequency in Text: 3

Letter s: Frequency in Text: 3

Letter !: Frequency in Text: 2

Hit the enter key to end the program....

Φιλικά,

>
Bokarinho

takis_tz · 15 Δεκεμβρίου 2007

επισυνάπτω την εκφώνηση της άσκησης για όποιον θέλει περισσότερες λεπτομερειες

askisi-Huffman.txt

bokarinho · 15 Δεκεμβρίου 2007

Το παρακάτω πρόγραμμα λύνει το πρώτο μέρος της άσκησης σου, δηλαδή δεδομένου οποιουδήποτε dataset όπως αναφέραμε, δηλαδή ενός αρχείου που περιέχει ένα κείμενο με τα σύμβολα που θα χρησιμοποιήσουμε υπολογίζει τις πιθανότητες εμφάνισης κάθε συμβόλου και τις αποθηκεύει σε ένα πίνακα. Κατόπιν δημιουργείται ένα νέο αρχείο με το όνομα probabilities.txt το οποίο περιέχει ένα πίνακα με το κάθε σύμβολο αριστερά και την πιθανότητα εμφάνισης του στην δεξιά στήλη.

>
Compiler:
Borland TurboC++

>
OS:
Windows XP Professional SP2 English

Code:

>
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ASCIITABLESIZE 127
#define AFTERSPACECHAR 32
//---------------------------------------------------------------------------

/* Get a Text Buffer. */
char *GetBuffer(int TextSz)
{
char *BufText = NULL;
char *Getz = NULL;
BufText = malloc(TextSz * sizeof(char));
if(BufText)
{
	printf("Enter the text:\n");
	Getz = fgets(BufText, TextSz, stdin);
	if(Getz)
	{
		BufText[strlen(BufText)-1] = '\0';
		return BufText;
	}
	else
	{
		printf("ErrorReporter:Error during Reading Process.\n");
		return NULL;
	}
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return NULL;
}
}
/* Get A Buffer alternate method, double pointer. */
int GetBufferAlt(char **BufferText, int TextSz)
{
char *BuffText = malloc(TextSz * sizeof(char));
if(BuffText)
{
	printf("Enter the text:\n");
	fgets(BuffText, TextSz, stdin);
	BuffText[strlen(BuffText)-1] = '\0';
	*BufferText = BuffText;
	return 0;
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return -1;
}
}
/* Store the Frequences of Each Character in Text. */
int* StoreFrequencesFromText(char *Text)
{
int i;
int *Freq = calloc(ASCIITABLESIZE,sizeof(int));
if(Freq)
{
	for(i = 0; i < ASCIITABLESIZE; i++)
		Freq[Text[i]]++;
	return Freq;
}
else
{
	printf("ErrorReporter:Error during Memory Access.\n");
	return NULL;
}
}
/* Store Frequences From an input File, and scale them to make probabilities. */
int StoreFrequencesScaledFromFile(const char *filename, float **LetterFreqs)
{
if(!filename)
{
	fprintf(stderr,"ErrorReporter:Error Bad Filename.\n");
	return -1;
}
else
{
	/* Variables. */
	FILE *fptr = NULL;
	float *freQ = NULL;
	char cChar;
	int i,fileSz = 0;
	/* Main Body. */
	if((fptr = fopen(filename, "rt")) == NULL)
	{
		fprintf(stderr,"ErrorReporter:Error Opening '%s' file.\n", filename);
		return -2;
	}
	else
	{

		/* Seek to End. */
		fseek(fptr, 0, SEEK_END);
		/* Get the size. */
		if((fileSz = ftell(fptr)) == -1L)
		{
			fclose(fptr);
			return -3;
		}
		/* Rewind to start of file. */
		rewind(fptr);
		/* Create the Array. */
		if((freQ = calloc(ASCIITABLESIZE, sizeof(float))) == NULL)
		{
			printf("ErrorReporter:Error during Memory Access.\n");
			fclose(fptr);
			return -4;
		}
		while((cChar = fgetc(fptr)) != EOF)
			freQ[cChar]++;
		for(i = 0; i < ASCIITABLESIZE; i++)
			freQ[i] /= fileSz;
		/* Return possibilities for each letter and close file. */
		fclose(fptr);
		/* Save to pointer. */
		*LetterFreqs = freQ;
		/* Return Safely. */
		return 0;
	}
}
}
/* Create A Text file to contain the symbol frequencies of the given dataset. */
int SaveFrequenciesToFile(const char *filename, const float *FreQ)
{
/* Variables. */
FILE *fptr = NULL;
/* Index. */
int i;

if(!filename)
{
	fprintf(stderr, "ErrorReporter:Error, Bad Filename <NULL>.\n");
	return -1;
}
if(!FreQ)
{
	fprintf(stderr, "ErrorReporter:Error, Bad Array Input <NULL>.\n");
	return -2;
}
if((fptr = fopen(filename, "wt")) == NULL)
{
	fprintf(stderr,"Error Opening '%s' file.\n", filename);
	return -3;
}
else
{
	/* Write header title to file. */
	fprintf(fptr,"SUMBOL\t\tFREQUENCY\n");
	for(i = AFTERSPACECHAR; i <= ASCIITABLESIZE; i++)
		fprintf(fptr,"%c\t\t%f\n",i, FreQ[i]);
	/* Return status, close file. */
	fclose(fptr);
	return 0;
}
}
int main(int argc, char* argv[])
{
float *Fr = NULL;
StoreFrequencesScaledFromFile("dataset.txt", &Fr);
SaveFrequenciesToFile("probabilities.txt", Fr);
printf("Hit the enter key to end the program....\n");
getchar();
return 0;
}
//---------------------------------------------------------------------------

Τυπωμένα αποτελέσματα για αρχείο εισόδου dataset.txt με περιεχόμενα:

Hey, hey, hey

Here I go now

Here I go in to new days

Hey, hey, hey

Here I go now

Here I go into new days

Im pain, Im hope, Im suffer

Yeah, hey, hey, hey, yeah

Here I go into new days

Hey, hey, hey

Aint no mercy, aint mercy left for me,

Hey, hey, hey

Aint no mercy, aint mercy left for me,

Im pain, Im hope, Im suffer

Yeah, hey, hey, hey

Aint no mercy, aint no mercy left for me

Do you bury me when Im gone

Do you teach me while Im here

...just as soon as I belong, then its time I disappear

Hey, hey, hey, and I went, and I went on down that road

Hey, hey, hey

And I went on, and I went on down that road

Im pain, Im hope, Im suffer

Hey, hey, hey

Yeah and went on, and I went on down that road

Do you bury me when Im gone

Do you teach me while Im here

...just as soon as I belong, then its time I disappear

Do you bury me when Im gone

Do you teach me while Im here

...just as soon as I belong, then its time I disappear

Do you bury me when Im gone

Do you teach me while Im here

...just as soon as I belong, then its time I disappear

Do you bury me when Im gone

Do you teach me while Im here

...just as soon as I belong, then its time I disappear

...disappear

αρχείο εξόδου probabilities.txt με περιεχόμενο:

>
Bokarinho.

probabilities.txt

takis_tz · 15 Δεκεμβρίου 2007

Όσον αφορά τον υπολογισμό των πιθανοτήτων, είδα το κώδικά σου και τρέχει μια χαρά. Ωστόσο το μεγάλο πρόβλημά μου είναι στο δεύτερο θέμα που θέλει τη δημιουργία του δένδρου Huffman και την εκτύπωση των παραγόμενων κωδικών στην οθόνη και σε αρχείο. Σε προηγούμενο μήνυμα σου μου είχες γράψει ...

"... θέλει υψηλή προγραμματιστική ικανότητα και να υλοποιήσεις βασικές δομές όπως τα δυαδικά δέντρα, συναρτήσεις που να δημιουργούν, να καταστρέφουν, να κάνουν ευθύ και αντίστροφο traverse στο δέντρο, εισαγωγή κόμβου, κτλ, επίσης θα πρέπει να παίξουμε με τα bits δηλαδή να φτιάξουμε συναρτήσεις που να παίζουν με bits, πχ XOR, και ίσως και ουρές προτεραιότητας για τις συγχωνεύσεις."

Με την εκφώνηση που είδες, τί ισχύει από αυτά;

ΥΓ: Δες έναν κώδικα που έχω για τις πιθανότητες. Νομίζω όμως ότι ο δικός σου είναι πιο αποδοτικός.

huffman-com.txt

bokarinho · 15 Δεκεμβρίου 2007

Όσον αφορά τον υπολογισμό των πιθανοτήτων, είδα το κώδικά σου και τρέχει μια χαρά. Ωστόσο το μεγάλο πρόβλημά μου είναι στο δεύτερο θέμα που θέλει τη δημιουργία του δένδρου Huffman και την εκτύπωση των παραγόμενων κωδικών στην οθόνη και σε αρχείο. Σε προηγούμενο μήνυμα σου μου είχες γράψει ...

"... θέλει υψηλή προγραμματιστική ικανότητα και να υλοποιήσεις βασικές δομές όπως τα δυαδικά δέντρα, συναρτήσεις που να δημιουργούν, να καταστρέφουν, να κάνουν ευθύ και αντίστροφο traverse στο δέντρο, εισαγωγή κόμβου, κτλ, επίσης θα πρέπει να παίξουμε με τα bits δηλαδή να φτιάξουμε συναρτήσεις που να παίζουν με bits, πχ XOR, και ίσως και ουρές προτεραιότητας για τις συγχωνεύσεις."

Με την εκφώνηση που είδες, τί ισχύει από αυτά;

ΥΓ: Δες έναν κώδικα που έχω για τις πιθανότητες. Νομίζω όμως ότι ο δικός σου είναι πιο αποδοτικός.

Συγγνώμη που ρωτάω αλλά αυτά τα έχεις κάνει όλα μόνος σου; Αν ναι τότε δεν θα έπρεπε να με ρωτάς τίποτα και να μην βάλεις την εκφώνηση της εργασίας σου στο insomnia. Αν όχι έχεις βρει τότε από κάπου αλλού την λύση στην εργασία σου καθώς υπάρχουν υλοποιημένα όλα αυτά μέσα. Ναι ίσως η δική μου συνάρτηση να διαχειρίζεται ας έλεγα με ένα ομορφότερο loop την κατάσταση αλλά πάνω κάτω η λογική είναι ίδια.

Από την εκφώνηση που είδα ισχύουν όλα αυτά που σου έχω γράψει, πρόσεξε φίλε αν δεν είναι δική σου η άσκηση την αντιγραφή...

takis_tz · 15 Δεκεμβρίου 2007

Εννοείται ότι δεν ειναι δική μου η λύση. Αυτός είναι άλλωστε και ο λόγος που ζητώ να με βοηθήσεις. Δεν είναι το επίπεδό μου στη C τόσο υψηλό. Δεν θα ήθελα όμως να κάνω "κλόπι-πέιστ" και προτιμώ να το παλέψω λίγο και να μάθω κάποια πράγματα.

Όσον αφορά αυτό έχω στείλει, ικανοποιεί πλήρως την εκφώνηση της άσκησης ή όχι. Γιατί έχω την αίσθηση ότι δεν καλύπτομαι...

bokarinho · 15 Δεκεμβρίου 2007

Εννοείται ότι δεν ειναι δική μου η λύση. Αυτός είναι άλλωστε και ο λόγος που ζητώ να με βοηθήσεις. Δεν είναι το επίπεδό μου στη C τόσο υψηλό. Δεν θα ήθελα όμως να κάνω "κλόπι-πέιστ" και προτιμώ να το παλέψω λίγο και να μάθω κάποια πράγματα.
Όσον αφορά αυτό έχω στείλει, ικανοποιεί πλήρως την εκφώνηση της άσκησης ή όχι. Γιατί έχω την αίσθηση ότι δεν καλύπτομαι...

Ωραία, κατανοώ το πρόβλημα σου, εγώ τώρα τι να κάνω, να σου κάνω όλη την εργασία; Σου έκανα μία αρχή, το πρώτο τμήμα είναι ολοκληρωμένο, τώρα για να κατασκευάσουμε την συνάρτηση που θα κάνει build το δέντρο πρέπει να κατασκευάσουμε συναρτήσεις που να δημιουργούν δυαδικό δέντρο, ουρά προτεραιότητας κτλ. Ξεκίνα λοιπόν ως εξής, δημιούργησε την δομή του κόμβου σου, κάθε κόμβος θα είναι ένα γράμμα και η συχνότητα του ορισμένα ως μία δομή, κατόπιν με βάση αυτή την δομή όρισε την δομή του δέντρου σου. Βέβαια εδώ μπαίνουν στο παιχνίδι και οι ουρές προτεραιότητας, θα πρέπει να τα φτιάξεις αυτά.

Στην άσκηση που έχεις τα έχει όλα τώρα δεν ξέρω τι θα κάνεις....

takis_tz · 15 Δεκεμβρίου 2007

Σε ευχαριστώ για την βοήθειά σου. Θα προσπαθήσω να "χτίσω" επάνω στη δική σου αρχή.

gtroza · 16 Δεκεμβρίου 2007

bokarinho bravo !

πλάκα πλάκα, το Insomnia λειτουργεί και σαν ΕΑΠ !

ευχαριστούμε για το γρήγορο "μάθημα" !

επικροτώ να γίνει sticky

bokarinho · 16 Δεκεμβρίου 2007

Όσο μπορώ θα βοηθήσω, ίσως σήμερα να βοηθήσω το φίλο μας με το να του ετοιμάσω το interface για τα δέντρα έτσι ώστε να ξεκινήσει να φτιάξει τον αλγόριθμο συμπίεσης και αποσυμπίεσης. Βέβαια θα χρειαστούμε και ουρές προτεραιότητας που προκύπτουν από τους σωρούς, κάτι μάλλον θα γίνει και για αυτό.

takis_tz · 17 Δεκεμβρίου 2007

προσπαθώ να κάνω το interface για τα δέντρα, αλλά έχω πολλά προβλήματα.

Ερώτηση:

Έχω ορίσει μια μεταβλητή root που είναι δείκτης σε μια ρίζα του δένδρου. Άρα ο τύπος της μεταβλητής είναι struct tree_node. Όμως η μεταβλητή αυτή αποτελεί πεδίο της δομής της συνδεδεμένης λίστας struct list_node.

struct list_node

{

long double probability;

struct list_node *next;

struct tree_node *root;

}*begin_list_node, *new_list_node;

Έβαλα long double probability γιατί ήταν ο μόνος τρόπος να τυπώσω την λίστα για να την δω.

Εάν θέλω κάπου στο πρόγραμμά μου να αναφερθώ σε αυτή την μεταβλητή root θα πρέπει να χρησιμοποιήσω

struct list_node->root και όχι struct tree_node->root σωστά;

Τώρα πως μπορεί αυτή η μεταβλητή να δείχνει στη ρίζα ενός δένδρου. Θέλουμε να δείχνει για παράδειγμα σε ένα χαρακτήρα;

Κάτι σαν new_list_node->root = ρίζα->chr_ASCII;

Προσπαθώ να καταλάβω τι είναι αυτή η ρίζα.

Και όλες αυτές τις ρίζες πως μπορούμε να τις χειριστούμε; Μήπως να φτιάξω έναν πίνακα με όλους αυτούς τους δείκτες προς τις ρίζες;

bokarinho · 17 Δεκεμβρίου 2007

Αυτό που χρειάζεσαι είναι αυτό:

>
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//---------------------------------------------------------------------------

/* Global Structures. */

/* Our Huffman Node Structure. */
typedef struct _Huffnode{
int Freq;
unsigned char symbol;
}Huffnode;

/* Binary Tree Node Structure. */
typedef struct _BiTreeNode{
Huffnode data;
struct _BiTreeNode *left;
struct _BiTreeNode *right;
}BiTreeNode;

/* The Binary Tree. */
typedef struct _BTree{
/* Tree's size. */
int size;
/* Here is the root. */
BiTreeNode *root;
}BTree;


/* Functions for Binary Trees. */

/* Create Tree. */
BTree *CreateBT()
{
BTree *t = malloc(sizeof(BTree));
if(!t)
{
	printf("ErrorReporter:Error Can not get Memory for Building our Tree.\n");
	return NULL;
}
else
{
	/* The Tree is Empty. */
	t->size = 0;
	t->root = NULL;
	/* Return the Tree. */
	return t;
}
}

/* Insert into Tree. */
int InsertLeftTree(BTree *t, BiTreeNode *node, Huffnode data)
{
BiTreeNode *newNode = NULL;
BiTreeNode **position = NULL;
/* Create a new Node. */
newNode = malloc(sizeof(BiTreeNode));
if(!newNode)
	return NULL;
else
{
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
}
if(node == NULL)
{
	if(t->size > 0)
		return -1;
	position = &t->root;
}
else
{
	if(node->left != NULL)
		return -2;
	position = &node->left;
}
/* Get value for the double pointer. */
*position = newNode;
t->size++;
return 0;
}

/* Insert Right. */
int InsertRightTree(BTree *t, BiTreeNode *node, Huffnode data)
{
BiTreeNode *newNode = NULL;
BiTreeNode **position = NULL;
/* Create a new Node. */
newNode = malloc(sizeof(BiTreeNode));
if(!newNode)
	return NULL;
else
{
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
}
if(node == NULL)
{
	if(t->size > 0)
		return -1;
	position = &t->root;
}
else
{
	if(node->right != NULL)
		return -2;
	position = &node->right;
}
/* Get value for the double pointer. */
*position = newNode;
t->size++;
return 0;
}

/* Print Tree. */
/* Traversal means that we visit first the root then left then right. */
void DumpTreeTraversal(BiTreeNode *r)
{
if(r != NULL)
{
	DumpTreeTraversal(r->left);
	printf("%d %c\n", r->data.Freq, r->data.symbol);
	DumpTreeTraversal(r->right);
}
}
int main(int argc, char* argv[])
{
printf("Hit enter to continue....\n");
getchar();
return 0;
}
//---------------------------------------------------------------------------

takis_tz · 17 Δεκεμβρίου 2007

Δεν έχω μελετήσει ακόμη το κώδικά σου, πάντως με πρώτη ματιά μου δείχνει πολύ στρωτός.

Υποθέτω ότι είναι συνέχεια του αρχικού σου, που αφορούσε την δημιουργία πίθανοτήτων.

Πάντως σε ευχαριστώ πολύ, με έχεις βοηθήσει αφάνταστα!!

Σύνδεση

huffman σε C

Προτεινόμενες αναρτήσεις

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Αρχειοθετημένο

Σύνδεση