#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 10
typedef struct
{
char elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,HuffmanTree;
typedef char HuffmanCode;
typedef struct _Weight
{
char elem;
unsigned int m_weight;
}Weight;
void Print_Menu();
int Initialize(HuffmanTree&, HuffmanCode&);
void HuffmanCoding(HuffmanTree&,HuffmanCode&,Weight,int);
void Coding(HuffmanTree& HT,HuffmanCode& HC,int n);
void Select(HuffmanTree&,int,int,int);
void OutputHuffman(HuffmanTree,HuffmanCode,int);
int Write_hfmTree_to_file(HuffmanTree,HuffmanCode,int );
int Encoding(HuffmanTree&,HuffmanCode&);
int Findchar(HuffmanTree,char,int);
int Print();
int Decoding(HuffmanTree,int);
void main()
{
char cX;
int n;
HuffmanTree HT = NULL;
HuffmanCode HC = NULL;
while(1)
{
Print_Menu();
scanf(%1s,&cX);
getchar();
if(cX == 'Q')
{
printf(Bye!n);
break;
}
switch(cX)
{
case 'I' n = Initialize(HT,HC); break;
case 'E' n = Encoding(HT,HC); break;
case 'P' Print(); break;
case 'D' Decoding(HT,n); break;
case 'T' OutputHuffman(HT,HC,n); break;
default printf(Input Error!); break;
}
}
}
void Print_Menu()
{
printf(n Huffman Arithmetic Demonstration );
printf(nI---Initialize E---Encoding P---Print);
printf(nT---Tree printing D---Decoding Q---Quit program);
printf(n Codz By EvilCat);
printf(n Huffman Arithmetic Demonstration );
printf(nPlease choose a menu item and press enter to continue.n);
}
int Initialize(HuffmanTree& HT,HuffmanCode &HC)
{
Weight w;
char c;
int i,n;
int wei;
printf(Please input the value of n );
scanf(%d,&n);
w = (Weight)malloc((n+1) sizeof(Weight));
for(i = 1; i = n; i++)
{
printf(Input the element);
scanf(%1s,&c);
printf(Input its weight);
scanf(%d,&wei);
w[i].elem = c;
w[i].m_weight = wei;
}
HuffmanCoding(HT,HC,w,n);
Write_hfmTree_to_file(HT,HC,n);
return n;
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode& HC,Weight w, int n)
{
int m,i,s1,s2;
if(n = 1) return;
m = 2 n - 1;
HT = (HuffmanTree)malloc((m+1) sizeof(HTNode));
for( i = 1; i = n; ++i)
{
HT[i].elem = w[i].elem;
HT[i].m_weight = w[i].m_weight;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for(; i = m; ++i)
{
HT[i].elem = '0';
HT[i].m_weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for( i = n + 1; i = m; ++i)
{
Select(HT,i-1,&s1,&s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].m_weight = HT[s1].m_weight + HT[s2].m_weight;
}
Coding(HT,HC,n);
}
void Coding(HuffmanTree& HT,HuffmanCode& HC,int n)
{
int i,start,c,f;
char cd;
HC = (HuffmanCode)malloc((n + 1) sizeof(char));
cd = (char)malloc(n sizeof(char));
cd[n-1] = '0';
for(i=1;i=n;++i)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild == (unsigned int)c) cd[--start]='0';
else cd[--start]='1';
}
HC[i]=(char )malloc((n-start)sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void Select(HuffmanTree& HT,int n,int s1,int s2)
{
int i;
(s1) = (s2) = 0;
for(i = 1;i = n;i++)
{
if(HT[i].m_weight HT[(s2)].m_weight&&HT[i].parent == 0&&(s2)!=0)
{
if(HT[i].m_weightHT[(s1)].m_weight)
{
(s2) = (s1);
(s1) = i;
}
else (s2) = i;
}
if(((s1) == 0(s2) == 0)&&HT[i].parent == 0)
{
if((s1) == 0) (s1) = i;
else if((s2) == 0)
{
if(HT[i].m_weightHT[(s1)].m_weight)
{
(s2) = (s1);
(s1) = i;
}
else (s2) = i;
}
}
}
if((s1) (s2))
{
i = (s1);
(s1) = (s2);
(s2) = i;
}
return;
}
void OutputHuffman(HuffmanTree HT,HuffmanCode HC,int n)
{
FILE fp;
fp = fopen( TreePrint.txt, w );
if(!HT&&!HC)
{
printf(Please Initialize First!n);
return;
}
int i;
printf(Number--Element--Weight--Parent--Lchild--Rchildn);
fprintf(fp,Number--Element--Weight--Parent--Lchild--Rchildn);
for(i = 1;i = 2 n - 1;i++)
{
printf(%3d%8c%8d%8u%8u%8un,i,HT[i].elem,HT[i].m_weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
fprintf(fp,%3d%8c%8d%8u%8u%8un,i,HT[i].elem,HT[i].m_weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
fclose(fp);
}
int Write_hfmTree_to_file(HuffmanTree HT,HuffmanCode HC,int n)
{
FILE fp;
fp = fopen( hfmTree.txt, w );
fprintf(fp,%dn,n);
for( int i = 1; i 2n; i++)
{
fprintf( fp,
%c %u %u %u %un,
HT[i].elem, HT[i].m_weight, HT[i].parent, HT[i].lchild, HT[i].rchild );
}
fclose( fp );
return 1;
}
int Encoding(HuffmanTree& HT,HuffmanCode& HC)
{
int m,n,c;
char x;
FILE tfp,sfp,dfp;
if(!HT&&!HC)
{
if((tfp = fopen( hfmTree.txt, r )) == NULL)
{
printf(cannot open hfmTree.txtn);
return 0;
}
fscanf(tfp,%dn,&n);
m = 2 n - 1;
HT = (HuffmanTree)malloc((m+1)sizeof(HTNode));
for(int i = 1; i 2 n; i++)
{
fscanf(tfp,
%c %u %u %u %un,
&HT[i].elem, &HT[i].m_weight, &HT[i].parent, &HT[i].lchild, &HT[i].rchild );
}
Coding(HT,HC,n);
fclose(tfp);
}
if((tfp = fopen( hfmTree.txt, r )) == NULL)
{
printf(cannot open hfmTree.txtn);
return 0;
}
fscanf(tfp,%dn,&n);
if((sfp = fopen( ToBeTran.txt, r )) == NULL)
{
printf(cannot open ToBeTran.txtn);
return 0;
}
dfp = fopen( CodeFile.txt, w );
while((x = fgetc(sfp)) != -1)
{
c = Findchar(HT,x,n);
fputs(HC[c],dfp);
}
fclose(tfp);
fclose(sfp);
fclose(dfp);
return n;
}
int Findchar(HuffmanTree HT,char x,int n)
{
int i = 1;
while( x != HT[i].elem && i = n )
{
i++;
}
if( i n ) return 0;
else return i;
}
int Print()
{
char x;
int counter = 0;
FILE sfp,dfp;
if((sfp = fopen( CodeFile.txt, r )) == NULL)
{
printf(cannot open CodeFile.txtn);
return 0;
}
dfp = fopen( CodePrin.txt, w );
while((x = fgetc(sfp)) != -1)
{
if(counter != 0 && counter % MAXLEN == 0)
{
printf(n);
fputc('n',dfp);
}
printf(%c,x);
fputc(x,dfp);
counter++;
}
fclose(sfp);
fclose(dfp);
return 1;
}
int Decoding(HuffmanTree HT,int n)
{
int t = 2 n - 1;
char x;
FILE sfp,dfp;
if(!HT)
{
printf(Please Initialize First!n);
return 0;
}
if((sfp = fopen( CodeFile.txt, r )) == NULL)
{
printf(cannot open CodeFile.txtn);
return 0;
}
dfp = fopen( TextFile.txt, w );
while(1)
{
if(HT[t].lchild!=0)
{
x = fgetc(sfp);
if(x == '0')
t = HT[t].lchild;
else if(x == '1')
t = HT[t].rchild;
else break;
}
else
{
printf(%c,HT[t].elem);
fputc(HT[t].elem,dfp);
t = 2 n-1;
}
}
fclose(sfp);
fclose(dfp);
return 1;
}
