Witam ! Mam problem z napisaniem funkcji ktora tworzy tablice kodowa w kodowaniu huffmana. prosilbym o pomoc. Z gory dzieki !
#include<stdio.h>
#include<stdlib.h>
#define ROZMIAR_BUFORA 1024
#define PLIK_CZ "czestosci.txt"
#define PLIK_TAB "tab.cod"
#define BITY 8
// struktura do przechowywania czestosci znaku
struct el {
char zn; // znak
int cz; // czestosc
struct el *next; // wskazanie na kolejny element
};
// struktuta so przechowywania danych z tabeli kodowej
struct el2 {
unsigned int kod;
int dl; // dlugosc kodu
char symbol;
};
typedef struct el *elPtr;
// DEKLARACJE FUNKCJI
void WyznaczCzestosci(char b[], elPtr *root, int n); // wynzaczanie czestosci
void Zapisz(elPtr *root, FILE *f); // zapisanie czestosci do pliku
int Porownaj(const void *a, const void *b); // porownywanie wartosci (potrzebne do qsorta)
void Wstaw(elPtr *root, char zn, int cz); // wstaw nowy element do listy czestosci
int Sprawdz(elPtr *root, char zn); // sprawdzenie czy dany zn znajduje sie juz na liscie
void Posortuj(elPtr *root); // sortowanie listy
void UtworzTabliceKodowa(int lwz); // utworzenie tablicy kodwej
void Kompresuj(FILE *f, FILE *f_out); // kompresja pliku
void ZapiszPaczke(unsigned int kod, int dl, FILE *f_out); // paczka -> plik (uzywane przy kompresji)
/* moze mozna nie deklarowac ich globalnie? */
char paczka = 0; // paczka (char = 1 bajt = 8 bitów)
int wolne_bity = BITY; // na poczatku wszystkie bity w paczce sa wolne
// GLOWNY PROGRAM
int main(int argc, char *argv[])
{
FILE *file_in, *file_out, *file_cz; // deklaracja uchwytow plikow
char bufor[ROZMIAR_BUFORA]; // bufor (rozmiar = 1024)
int n, czestosc, i, lwz=0; // n - ilosc wczytanych bajtow, lwz - liczba wszystkich znakow
elPtr root = NULL; // wskazanie na strukture, root bedzie korzeniem listy
// sprawdzenie poprwanosci wpisania argumentow
if (argc != 3) {
printf("Podano zla liczbe argumentow!\n");
printf("Skladnia: %s plik_wejsciowy plik_wyjsciowy\n", argv[0]);
return 0;
}
if (file_in = fopen(argv[1], "rb")) { // otworzenie pliku wejsciowego
do {
n = fread(bufor, sizeof(char), ROZMIAR_BUFORA, file_in);
lwz += n;
WyznaczCzestosci(bufor, &root, n); // wyznaczanie czestosci
} while (n);
Posortuj(&root); // sortowanie listy czestosci
if (file_cz = fopen(PLIK_CZ, "w")) { // otworzenie pliku z czestosciami
Zapisz(&root, file_cz); // zapisanie do pliku informacji o ilosci znakow
fclose(file_cz);
} else { printf ("Nie udalo sie otworzyc pliku z czestosciami!\n"); return 1; }
UtworzTabliceKodowa(lwz);
if (file_out = fopen(argv[2], "wb")) { // otworzenie pliku wynikowego do zapisu
Kompresuj(file_in, file_out);
} else { printf ("Nie udalo sie otworzyc pliku wynikowego!\n"); return 1; }
fclose(file_in);
} else { printf("Nie udalo sie otworzyc pliku wejsciowego!\n"); return 1; }
printf("Zakonczono generowanie wyniku.\n");
system("PAUSE");
return EXIT_SUCCESS;
}
// DEFINICJE FUNKCJI
void WyznaczCzestosci(char b[], elPtr *root, int n) {
int i;
for (i=0;i<n;i++)
if (!Sprawdz(root, b[i])) Wstaw(root, b[i], 1);
}
void Zapisz(elPtr *root, FILE *f) {
elPtr tmp;
tmp= *root;
while (tmp) {
fprintf(f, "%c %d\n", tmp->zn, tmp->cz);
tmp = tmp->next;
}
}
int Porownaj(const void *a, const void *b) {
elPtr intOne = *(elPtr*)a;
elPtr intTwo = *(elPtr*)b;
if (intOne->cz < intTwo->cz)
return -1;
if (intOne->cz == intTwo->cz)
return 0;
return 1;
}
void Wstaw(elPtr *root, char zn, int cz) {
elPtr newPtr, tmp;
// ustawienie danych elementarnych nowego elementu
newPtr = (elPtr)malloc(sizeof(struct el));
newPtr->zn = zn;
newPtr->cz = cz;
newPtr->next = NULL;
if (!*root) *root = newPtr;
else {
tmp = *root;
while(tmp->next) tmp = tmp->next;
tmp->next = newPtr;
}
}
// sprawdzenie czy zadany element znajduje sie na liscie
int Sprawdz(elPtr *root, char zn) {
elPtr tmp;
if (!*root) return 0;
else {
tmp = *root;
if (tmp->zn == zn) {
tmp->cz++;
return 1;
}
while (tmp->next) {
tmp = tmp->next;
if (tmp->zn == zn) {
tmp->cz++;
return 1;
}
}
return 0;
}
}
void Posortuj(elPtr *root) {
elPtr tmp;
int n=0; // liczba elementow
int i=0;
// zliczenie elementow
tmp = *root;
while (tmp) {
n++;
tmp = tmp->next;
}
elPtr tab[n]; // tablica przechowujaca pointery do elementow listy
//zapisanie elementow listy do tablicy
tmp = *root;
while (tmp) {
tab[i] = tmp;
i++;
tmp = tmp->next;
}
// posortowanie tablicy
qsort((void*)tab, n, sizeof(elPtr), Porownaj);
// odtworzenie listy w kolejnosci niemalejacej
*root = tab[0];
for (i=0;i<n;i++) {
if (i==n-1) tab[i]->next = NULL;
else tab[i]->next = tab[i+1];
}
}
void UtworzTabliceKodowa(int lwz) { // FUNKCJA DO NAPISANIA!!!!!!!!!!!!!!!
}
void Kompresuj(FILE *f, FILE *f_out) {
FILE *tab_cod;
int le, i, tmp; // le - liczba elemntow w tablicy
tab_cod = fopen(PLIK_TAB, "rb");
le = (int)fgetc(tab_cod);
struct el2 *tab = (struct el2 *)calloc(sizeof(struct el2), le); // dynamiczna alokacja tablicy
for (i=0;i<le;i++) { // uzupelnianie tablicy wartosciami z tabeli kodowej w formacie symbol|dlugosc|kod, pomijanie zer
do{
tmp = fgetc(tab_cod);
} while (tmp == 0);
tab[i].symbol = tmp;
tab[i].dl = (int)fgetc(tab_cod);
tab[i].kod = (unsigned int)fgetc(tab_cod);
}
fclose(tab_cod);
rewind(f); // przewiniecie pliku
do { // czytanie pliku i kompresja w locie :)
tmp = fgetc(f);
for (i=0;i<le;i++) {
if ((tab+i)->symbol == tmp) {
ZapiszPaczke((tab+i)->kod, (tab+i)->dl, f_out);
break;
}
}
} while (tmp != EOF);
}
void ZapiszPaczke(unsigned int kod, int dl, FILE *f_out) {
if (wolne_bity >= dl) {
paczka |= (kod<<(wolne_bity-dl));
wolne_bity -= dl;
if (wolne_bity == 0) {
fprintf(f_out,"%c",paczka);
paczka = 0;
wolne_bity = BITY;
}
} else {
paczka |= (kod>>(dl-wolne_bity));
fprintf(f_out,"%c",paczka);
paczka = 0;
paczka |= (kod<<(BITY-dl+wolne_bity));
wolne_bity += BITY - dl;
}
}