Witam!
Mam program ktory ma za zadnie kompresowac i dekompresowac pliki z uzyciem kodowanie huffmana. Kompresje jakos udało mi sie napisac zas z dekompresja mam problemy. Wiem ze w sieci istnieje duzo takich tematow ale zaden dla mnie nie byl przydatny.Daltego prosze o pomoc. PLik test.txt jest plikiem wejsciowym w ktorym wprowadzamy dane w pliku czestosci.txt wystepuja czestosci wprowadzonych znakow plik tab.cod w ktorym zapisana jest tablica kodowa plik huffmantest.txt w ktorym zapisane sa zakodowane znaki z pliku test. Program wywolujemy przez konsole np c:\ huffman.exe test.txt huffmantest.txt. Prosilbym o jak najszybsza 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;           
};    

// struktura drzewiasta, niezedna to stworzenia drzewa huffmana
struct huff {
       char zn; // znak
       float prawd; // prawdopodbienstwo wystapienia
       struct huff *left, *right; // okresla lewy i prawy nastepnik  
};

// struktura, ktora bedze przechowywac drzewa prawdopodobienstwa wystapienia znakow
struct huff_list {
       struct huff *node;
       struct huff_list *next;       
};

// definicje typow
typedef struct el *elPtr;
typedef struct huff *huffPtr;
typedef struct huff_list *huff_listPtr;

// 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, elPtr *root); // 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)
void usun(huff_listPtr *root, float sum);
void WyznaczKody(huffPtr root, char c[], int lenc, FILE *f, int lwz);


char paczka = 0; // paczka (char = 1 bajt = 8 bitów)
unsigned int kod = 0;
int wolne_bity = BITY;  // na poczatku wszystkie bity w paczce sa wolne
int n; // do przechowywania ilosci symboli

// 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);
        //printf("%d\n", lwz);
        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
                     UtworzTabliceKodowa(lwz, &root);
                     fclose(file_cz);
        } else { printf ("Nie udalo sie otworzyc pliku z czestosciami!\n"); return 1; }
        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); // zapisanie czestosci znaku jako liczby calkowitej
           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 i=0;
     
     n=0; // liczba elementow
     
     // 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, elPtr *root) {
     FILE *tab_cod; // plik z tablica kodowa
     elPtr tmp; // do poruzania sie po liscie czestosci 
     huff_listPtr newPtr, root_h = NULL, tmp_h; // root_h - koren listy drzew, tmp_h - do poruszania sie po liscie drzew
     float sum; // suma prawdopodobienstw
     char c[32]; // do przechowywania kodu
     
     tmp = *root;
     while (tmp) {
           newPtr = (huff_listPtr)malloc(sizeof(struct huff_list)); // nowy element listy
           newPtr->next = NULL; 
           newPtr->node = (huffPtr)malloc(sizeof(struct huff)); // wskaznik na korzen drzewa (jako element listy)
           newPtr->node->zn = tmp->zn; // przypisanie znaku do wezla
           newPtr->node->prawd = (float)(tmp->cz) / (float)(lwz); // prawd. wystapienia znaku
           newPtr->node->left = newPtr->node->right = NULL; // tylko korzen, wskazniki na potomkow wskazuja na NULL 
           if (!root_h) root_h = newPtr;
           else {
                tmp_h = root_h;
                while(tmp_h->next) tmp_h = tmp_h->next;
                tmp_h->next = newPtr;       
           }
                     
           tmp = tmp->next;      
     }
     
     // w tej chwili lista zapelniona jest korzeniami drzew
     printf ("Wypisanie prawdopodobienstw  \n" );
     tmp_h = root_h;
     while (tmp_h) {
           printf("%f\n", tmp_h->node->prawd);
           tmp_h = tmp_h->next;      
     }
     
     // tworzenie drzewa huffmana
    while (root_h->next) { // dopoki w liscie istnieje wiecej niz jedno drzewo
           tmp_h = root_h;
           sum = tmp_h->node->prawd + tmp_h->next->node->prawd;
           usun(&root_h, sum);             
    }
    
    // w tej chwili jedynym elementem listy jest wskazanie na korzen drzewa Huffmana
     
     tab_cod = fopen(PLIK_TAB, "wb"); // otworzenie pliku z tablcia kodowa do zapisu
     fwrite(&n, sizeof(int), 1, tab_cod);
     WyznaczKody(root_h->node, c, 0, tab_cod, lwz);
     fclose(tab_cod); 
     
     
     /*tmp_h = root_h;
     printf("Wypisanie zawartosci drzew listy: \n");
     while (tmp_h) { // wypisanie zawrotsci drzew listy :-)
           printf("%c - %f\n", tmp_h->node->zn, tmp_h->node->prawd);
           tmp_h = tmp_h->next;      
     }*/
}
     

void Kompresuj(FILE *f, FILE *f_out) { 
     FILE *tab_cod;
     int le, i; // le - liczba elemntow w tablicy
     char tmp;
     
     tab_cod = fopen(PLIK_TAB, "rb");
     fread(&le, sizeof(int), 1, tab_cod); // odczytanie liczby elementow
     printf("%d\n", le);
     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
         fread(&tab[i].symbol, sizeof(char), 1, tab_cod);
         fread(&tab[i].dl, sizeof(int), 1, tab_cod);
         fread(&tab[i].kod, sizeof(unsigned int), 1, tab_cod);
     }
     fclose(tab_cod);
     
     // wypisanie tabeli kodwej 
     printf ("Tabela kodowa: \n");
     for (i=0;i<le;i++) {
         printf("%c-%d-%d\n", tab[i].symbol, tab[i].dl, tab[i].kod);  
     }
     
     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);
     if (wolne_bity != 0) fwrite(&paczka, sizeof(char), 1, f_out); // gdy zostala niepelna paczka                   
}

void ZapiszPaczke(unsigned int kod, int dl, FILE *f_out) {
     //printf("%d - %d\n", dl, kod);
     
     if (wolne_bity >= dl) {
        paczka |= (kod<<(wolne_bity-dl));
        wolne_bity -= dl;
        if (wolne_bity == 0) {
           fwrite(&paczka, sizeof(char), 1, f_out);
           //fprintf(f_out,"%c",paczka);
           paczka = 0;
           wolne_bity = BITY;               
        }                
     } else {
          paczka |= (kod>>(dl-wolne_bity));
          fwrite(&paczka, sizeof(char), 1, f_out);
          //fprintf(f_out,"%c",paczka);
          paczka = 0;
          paczka |= (kod<<(BITY-dl+wolne_bity));
          wolne_bity += BITY - dl;        
     }          
}

void usun(huff_listPtr *root, float sum) {
             huff_listPtr tmp, newPtr;
             
             tmp = *root;
             
             newPtr = (huff_listPtr)malloc(sizeof(struct huff_list)); // stworzenie nowego elementu...
             newPtr->node = (huffPtr)malloc(sizeof(struct huff)); // a w nim nowego wezla
             newPtr->node->prawd = sum; // sumowanie prawdopodobienstw
             newPtr->node->left = tmp->node; // ustanowienie nowego lewego potomka
             newPtr->node->right = tmp->next->node; // ustanowienie nowego prawego potomka
             newPtr->next = tmp->next->next; 
             newPtr->node->zn = 0;
             free(tmp->next);
             free(tmp);
             *root = newPtr;    
}

void WyznaczKody(huffPtr root, char c[], int lenc, FILE *f, int lwz) {
     int i;

     if(!(root->left)) {
                       kod = 0;
                       fwrite(&root->zn, sizeof(char), 1, f);
                       fwrite(&lenc, sizeof(int), 1, f);
                       //printf("%c : ", root->zn);
                       for(i = 0;i<lenc;i++) {
                             //printf("%c", c[i]);
                             if (c[i] == '0') kod |= (0<<i);
                             if (c[i] == '1') kod |= (1<<i);
                       }
                       fwrite(&kod, sizeof(unsigned int), 1, f);
                       //printf("\n");
     }
     else {
          c[lenc] = '0'; WyznaczKody(root->left,c,lenc + 1, f, lwz);
          c[lenc] = '1'; WyznaczKody(root->right,c,lenc + 1, f, lwz);    
     }
}