#include <stdio.h>
#include <dos.h>
#include <conio.h>
/* File compression - Huffman code */
/* Bil Stefanidis */
void insert(int, int);
void swap(int *, int, int);
void bin(int,int);
int removee(void);
int aa[42] ;
int p[42], info[42];
int N,L;
FILE *fpi, *fpo;
void main(void){
char a[500];
int val[240] , j ,l,x;
int count[44], count2[44],code[44],len[44];
char i ;
int t,k,t1,t2,flag,cout;
int dad[44];
clrscr();
N=0;
for (i=0;i<=43;i++){
code[i]=0;
count[i]=0;
len[i]=0;
dad[i]=0;
aa[i]=0;
}
i=0;
fpi=fopen("input.txt" , "r");
if (fpi==NULL) { printf("The file dont exist\n");}
for(j=0;j<=201;j++){
a[j]='';
}
for(j=0;j<=130;j++){
val[j]=0;
}
j=0;
while ( !feof(fpi) ) {
fscanf(fpi,"%c",&i);
printf("%c",i);
a[j]=i;
j=j+1;
}
printf("\n\n");
for(j=0;j<=200;j++){
printf("%c",a[j]);
}
getch();
getch();
/* Edw metrame poses fores emfanizetai
kathe character se ascII morfh */
for (j=0;j<=200;j++){
printf("a[j]=%d , val[a[j]]=%d \n",a[j],val[a[j]]);
val[a[j]]++;
}
/* Edw arxikopoioume enan counter */
for(j=0;j<=26;j++){
count[j]=0;
}
/* Edw topothetoume tiw metrhseis se enan
counter */
count[0]=val[32];
printf("Oi syxnothtes twn xarakthrwn symfwna me to ASCII
tous\n");
for(j=97;j<=121;j++){
if (val[j]!=0) {
count[j-96]=val[j];
}
printf(" val[%c]=%d \n",j,val[j]);
getch();
}
/* parousiazoume ta apotelesmata gia tous
26 xarakthres */
printf("Oi syxnothtes twn 26 xarakthrwn tou
alfabhtou\n");
for(j=1;j<=26;j++){
printf(" count[%d]=%d \n",j,count[j]);
getch();
}
/* parousiazoume th syxnothta emfanishs tou
space */
printf(" sp is appear ");
for (l=0;l<val[32];l++){
printf("%c",'*');
}
/* ------------------ */
/* parousiazoume th suxnothta emfanishs twn
allwn xarakthrwn */
printf(" %d times , count[%d]=%d\n",l,0,count[0]);
for (j=97;j<=121;j++){
printf(" %c is appear ",j);
for (l=0;l<val[j];l++){
printf("%c",'*');
}
printf(" %d times ,
count[%d]=%d\n",l,j-96,count[j-96]);
getch();
}
/* ------------------ */
fclose(fpi);
l=0;
printf("To count2 periexei th syxnothta emfanishs mono
twn\n");
printf("xarakthrwn pou yparxoun sto keimeno\n");
for (j=0;j<=26;j++){
if (count[j]!=0) {
count2[l]=count[j];
printf("count2[%d]=%d \n",l,count2[l]);
l++;
}
}
getch();
getch();
/* The finish of character counting */
for (i = 0; i <= 26; i++)
if (count[i]){
insert(count[i],i);
}
t1=t2=0;
N=N-1;
L=N-1;
for ( ; !empty(); i++) {
/* ta t1, t2 exoun tis theseis me tis
mikroteres syxnothtes */
t1=removee();
printf("t1=%d \n",t1);
getch();
t2=removee();
printf("t2=%d \n",t2);
getch();
printf("\narxizei h dhmiourgia twn dendrwn\n");
printf("\nDhmiourgia stoixeiou .........%d......(ftanei ws
to 44)\n",i);
dad[i] = 0;
printf("dad[%d]=%d \n",i,dad[i]);
getch();
dad[t1] = i;
printf("dad[%d]=%d \n",t1,dad[t1]);
getch();
dad[t2] = -i;
printf("dad[%d]=%d \n",t2,dad[t2]);
count[i] = count[t1] + count[t2];
printf("\nTo t1 kai t2 einai ta paidia tou dendrou\n
");
printf("To i einai h riza (pateras) tou dendrou\n ");
printf("kai ta count einai oi suxnothtes tous\n");
printf("t1=%d , t2=%d , i=%d , count[%d]=%d , count[%d]=%d ,
count[%d]=%d \n",
t1,t2,i,t1,count[t1],t2,count[t2],i,count[i]);
N=N+2;
if
(N==17){dad[N+1]=0;flag=1;aa[N+1]=aa[N];info[N+1]=info[N];p[N+1]=p[N];}
if (flag){flag=0;aa[N]=aa[N-1];info[N]=info[N-1];p[N]=p[N-1];}
N=N-2;
N=N+1;
if (!empty())
insert(count[i], i);
N=N-1;
if (i>30) printf("\nprosoxh meta to 30 de fainontai ola
ta apotelesmata\n\n");
for (j=0;j<=43;j++){
if (i<30) {
printf("\nO count exei tis syxnothtes olwn twn xarakthrwn
tou alfabhtoy\n");
printf("me 27o to space\n");
printf("O info exei tis xyxnothtes twn xarakthrwn pou den
einai 0\n");
printf("count[%d]=%d , info[%d]=%d ,
aa[%d]=%d\n",j,count[j],j,info[j],j,aa[j]);
getch();
}
}
}
printf("Edw parousiazontai oles oi rizes twn
korufwn\n");
for (i=0;i<=43;i++){
printf("dad[%d]=%d \n",i,dad[i]);
getch();
}
for (k = 0; k <=26 ; k++) {
i = 0;
x = 0;
j = 1;
if (count[k])
for (t=dad[k]; t; t=dad[t], j+=j, i++)
if (t < 0) {
x += j;
t = -t;
}
code[k] = x;
len[k] = i;
}
for (k=0;k<26;k++){
printf("k=%d , code[%d]=%d , len[%d]=%d
\n",k,k,code[k],k,len[k]);
}
/* for (j = 0; j < 26; j++)
for (i = len[index(a[j])]; i > 0; i--) {
cout << ( (code[index(a[j])] >> i-1) & 1);
printf("%b",cout);
} */
printf("\nEdw parousiazetai h telikh kwdikopoihsh\n");
printf("sp 0 ");bin(code[0],len[0]);printf("
%d",len[0]);
printf("\n");
for (j=1;j<=26;j++){
if ( (code[j]) || ( (!code[j]) && (count[j]!=0) ) ){
printf("%c %d
",j+96,j);bin(code[j],len[j]);printf("
%d",len[j]);
printf("\n");
}
}
getch();getch();
}
/* H bin metatrepei se dyadiko */
void bin(x,len){
unsigned int MASK = 0X800 ;
char mas[500];
int ll,i,size;
i=0;
for (;MASK;) {mas[i++]=( (MASK & x ) ? '1' : '0') ; MASK
>>= 1;}
size=i;
ll=size-len;
for (i=ll;i<=size-1;i++){printf("%c",mas[i]);}
getch();
}
int index(char xx) {
if (xx=='') return 0;
else return xx;
}
/* ************************* */
void insert(int x, int v) {
/* aa take the value the position of
element */
/* info take the frequency of element */
printf("x=%d v=%d \n",x,v);
getch();
aa[N] = v;
p[x]= N;
info[N] = x;
/* printf("aa[%d]=%d , p[%d]=%d ,info[%d]=%d
\n",N,aa[N],x,p[x],N,info[N]);
getch(); */
N=N+1;
}
void change(int x, int v) {
aa[p[x]] = v;
}
int search(){
int j;
}
/* remove smallest */
int removee(void){
int j, min = 0,flag;
printf("L=%d, N=%d\n",L,N);
for (j = N-1; j >= 1; j--)
if (info[j] < info[min])
min = j;
swap(aa, min, N);
swap(info, min, N);
p[info[min]] = min;
return aa[N--];
}
int empty() {
return (N <= 0);
}
void swap(int bn[], int ii,int jj){
int temp;
temp=bn[ii];
bn[ii]=bn[jj];
bn[jj]=temp;
}