C++ Алгоритм Хаффмана - C++ - Ответ 3723913

// 
 
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h>
 
//---------------------------------------------------------------------------
#define TOTAL_SYM_NUM 109
 
struct NODE
{
        int num;
        struct NODE* left;
        struct NODE* right;
        struct NODE* root;
        bool disabled;
        int length;
        char code[8];
        int code_value;
        
};
 
 
int main(int argc, char* argv[])
{
unsigned char str_file[TOTAL_SYM_NUM] ;
int m[16]; 
int s[255], a[31];
float L; 
struct NODE node[31];
float sum=0;
int i, k, min1, min2, min_ind1, min_ind2,l;
int x=16, len=0, fw,sw, v ;
unsigned char stream_word=0, fell_bits=0;
char z[31]; 
bool b[31];   
int buf; 
char str1[109], simbol[16] ;  //ñòðîêà èç áèíàðíèêà
unsigned char ch;
 
FILE *f_out = fopen("C:\\õàôôìàí.dat","wb"); //îòêðûòü áèíàðíûé ôàéë äëÿ çàïèñè
 
FILE *f = fopen("C:\\õàôôìàí.txt","rt"); //îòêðûòü òåêñòîâûé äëÿ ÷òåíèÿ
 
  if(f != NULL)
{ 
i=0;
 
while(fscanf(f,"%c",&ch) != EOF)
str_file[i++]=ch;
str_file[i] = '\0';
long length = ftell(f);
printf("length = %ld\n",length);
printf("\n");
 
int q=0;
 for (q=0; q<16; q++)
 m[q]=0;
 
int j;                //ïîäñ÷åò êîëèñòâà ñèìâîëîâ
for (j=0; j<TOTAL_SYM_NUM; j++)
  switch (str_file[j]) {
     case ' ':     m[0]=m[0]+1; break;
     case 'î'+256: m[1]=m[1]+1; break; // î
     case 'ê'+256: m[2]=m[2]+1;break; //ê
     case 'ï'+256: m[3]=m[3]+1;break; //ï
     case 'à'+256: m[4]=m[4]+1;break; //à
     case 'â'+256: m[5]=m[5]+1;break; //â
     case 'ë'+256: m[6]=m[6]+1;break; //ë
     case 'í'+256: m[7]=m[7]+1;break; //í
     case 'å'+256: m[8]=m[8]+1;break; //å
     case 'ñ'+256: m[9]=m[9]+1;break; //ñ
     case 'è'+256: m[10]=m[10]+1;break; //è
     case 'ò'+256: m[11]=m[11]+1;break; //ò
     case ','    : m[12]=m[12]+1;break; //,
     case 'ó'+256: m[13]=m[13]+1;break; //ó
     case 'û'+256: m[14]=m[14]+1;break; //û
     case 'õ'+256: m[15]=m[15]+1;break; //õ
     }
 for (j=0; j<16; j++)  //âûâîä êîëè÷åñòâà ñèìâîëîâ
 printf(" %d\n", m[j]);
 
float E ;           // Ýíòðîïèÿ
for(i=0; i<16; i++)
{L=(float)m[i]*(float)log10((double)m[i]);
sum=sum+L; }
E=((float)log10(TOTAL_SYM_NUM)-sum/TOTAL_SYM_NUM)/0.301f;
printf ("Entropia %f\n",E);
 
 
 fclose(f);
 
for(i=0; i<16; i++)
{
    node[i].num = m[i];
    node[i].left = NULL;
    node[i].right = NULL;
    node[i].root = NULL;
    node[i].disabled = true;
}
 
for(i=16; i<31; i++)
{
    node[i].num = 0;
    node[i].left = NULL;
    node[i].right = NULL;
    node[i].disabled =false ;
    node[i].root = NULL;
}
 
 
//---------------------------------------------------------------------------
 
 
while (x!=31)
{
    min1=TOTAL_SYM_NUM;
min2=TOTAL_SYM_NUM;
    for(i=30; i>=0; i--)
    {
        if (min1>node[i].num)
        {
            if (node[i].disabled ==true)
            { min1=node[i].num;
        min_ind1=i; 
            }
        }
        
    }
 node[min_ind1].disabled = false;
 
for(k=30; k>=0; k--)
{
  
  if (min2>node[k].num)
  {
    if (node[k].disabled ==true)
        {min2=node[k].num;
        min_ind2=k;
        } 
    }
 
}
node[min_ind2].disabled = false;
node[x].num = min1+min2;
node[x].left  = &node[min_ind1];
node[x].right = &node[min_ind2];
node[min_ind1].root = &node[x];
node[min_ind2].root = &node[x];
node[x].disabled = true;
x=x+1;
}
}
 
//---------------------------------------------------------------------------
 
k = 0;
char codes[8];
struct NODE* ptr;
int flag = 0;
int length;
for( i =0 ; i < 31; i++ )
    node[i].disabled = true;
 
i = 0;
 
while( i < 16 )
{
    ptr = &node[30];
    length = 0;
    for ( k = 0; k < 8; k++ )
        codes[k] = '0';
    k = 0;
    while( !(ptr->left == NULL && ptr->right == NULL ) )
    {
        if( ptr->right->disabled )
        {
            codes[k] = '0';
            ptr = ptr->right;
        }
        else
        if( ptr->left->disabled )
        {
            codes[k] = '1';
            ptr = ptr->left;
        }
            k++;
            length++;
 
    }
 
    ptr->disabled = false;
    
    ptr->length = length;
    memcpy( ptr->code, codes, length );
    ptr->code[length] = '\0';   
    printf("%s\n", ptr->code);
    while(!ptr->root->left->disabled && !ptr->root->right->disabled && ptr->root!=&node[30])
    {
        ptr->root->disabled=false;
        ptr = ptr->root;
    }
i++;
 
}
 
 
 
//--------------------------------------------------------------------------
for (i=0; i<16; i++)
{node[i].code_value= strtol (node[i].code, NULL, 2);  }
 
s[32]=0;
s['î'+256]=1;
s['ê'+256]=2;
s['ï'+256]=3;
s['à'+256]=4;
s['â'+256]=5;
s['ë'+256]=6;
s['í'+256]=7;
s['å'+256]=8;
s['ñ'+256]=9;
s['è'+256]=10;
s['ò'+256]=11;
s[44]=12;
s['ó'+256]=13;
s['û'+256]=14;
s['õ'+256]=15;
 
 
 
stream_word = 108;
fell_bits = 7;  // ÷èñëî çàïèñàííûõ áèò
 
for (i=0; i<=TOTAL_SYM_NUM-1; i++)  // çàïèñü â áèíàðíûé ôàéë
{    l=str_file[i]; v=s[l];
for(;;) {
            fell_bits=fell_bits+node[v].length;
            if (fell_bits>=8)
            { fw=8-(fell_bits-node[v].length); 
                sw=node[v].length-fw;
                stream_word=stream_word<<fw;
                stream_word = stream_word | ((node[v].code_value >> sw) & ((1<<fw)-1));
                fwrite(&stream_word,1,1,f_out);
            
 
                stream_word=0;
                 if(fell_bits!=8)
                     {stream_word=stream_word<<sw;
                        stream_word = stream_word | (node[v].code_value & ((1<<sw)-1)) ;
                        }
              fell_bits=fell_bits-8;
 
 
            }
 
            else
            {stream_word=stream_word<<node[v].length;
            stream_word=stream_word | node[v].code_value; 
        
            } break;
    
 
    } 
 
} 
 
fclose(f_out);
//--------------------------------------------------------------------------
simbol[0]=' ';
simbol[1]='î';
simbol[2]='ê';
simbol[3]='ï';
simbol[4]='à';
simbol[5]='â';
simbol[6]='ë';
simbol[7]='í';
simbol[8]='å';
simbol[9]='ñ';
simbol[10]='è';
simbol[11]='ò';
simbol[12]=',';
simbol[13]='ó';
simbol[14]='û';
simbol[15]='õ';
 
 
 
 
for (i=0;i<31;i++) {    //äåêîä
        a[i] = 0;
        b[i] = 1;
    }
    v = 0;
    for (i=0;i<16;i++) {             //òàáëèöa äåêîäèðîäâàíèÿ
        k = 0;
        for (int j=0; j<node[i].length; j++) {
            if (node[i].code[j] == '1') k++;
            if (j==(node[i].length-1)) {
                b[k] = 0;
                z[k]=simbol[i];
            }
            else {
                b[k] = 1;
                if (a[k]==0) {
                    v += 2;
                    a[k] = v;
                }
                k = a[k];
            }
        }
    }
 
 
//äåêîäèð
FILE *in_put;
in_put=fopen("C:\\õàôôìàí.dat","rb");
//if(in_put!=NULL)
 
 
FILE  *dec=fopen("C:\\ðàñêîäèðîâêà.txt","wt");
 
buf=0; v=0;int cnt_bit=7;
while(fread(&stream_word,1,1,in_put)!=0)
{   
    int mask = 0x80;
    while(cnt_bit<8)
    {   if(stream_word & mask)buf++;
        cnt_bit++;
        mask=mask>>1;
        while(b[buf]&&(cnt_bit<8))
        {   buf=a[buf];
            if(stream_word & mask)buf++;
            cnt_bit++;
            mask=mask>>1;
 
        }
        if(!b[buf])
        {
            str1[v++]=z[buf];
            buf=0;
        }
        else
            buf=a[buf];
    }
cnt_bit=0;
};
 
 
 str1[109] = '\0';
    for (i=0;i<109;i++) {
        fwrite(&str1[i],1,1,dec);
    }
    fclose(dec);
 
 
 
       return 0; 
}