C语言 Huffman编码

在双工通讯中利用哈夫曼编码和译码。功能： 1） 初始化：从键盘读入字符集大小n，以及n个字符和相应的权值，建立哈夫曼树，并存入文件A中。 2） 编码：利用已经建好的哈夫曼树，对文件B中的正文进行编码，然后将结果存入文件C中。 3） 译码：利用已经建好的哈夫曼树将文件C中的代码进行译码，结果存入文件D中。

#include  
#include  
#include  
#include  
#include  

//typedef int TElemType; 
const int UINT_MAX=1000; 
char str[50]; 

typedef struct 
{ 
int weightK; 
int parentlchildrchild; 
}HTNode* HuffmanTree; 

typedef char **HuffmanCode; 

//-----------全局变量----------------------- 
HuffmanTree HT; 
HuffmanCode HC; 
int w[50]ijn; 
char z[50]; 
int flag=0; 
int numb=0; 

// -----------------求赫夫曼编码----------------------- 
struct cou{ 
char data; 
int count; 
}cou[50]; 

int min（HuffmanTree tint i） 
{ // 函数void select（）调用 
int jflag; 
int k=UINT_MAX; // 取k为不小于可能的值即k为最大的权值1000 
for（j=1;j<=i;j++） 
if（t[j].weightk=t[j].weightflag=j; 
t[flag].parent=1; 
return flag; 
} 

//--------------------slect函数---------------------- 
void select（HuffmanTree tint iint &s1int &s2） 
{ // s1为最小的两个值中序号小的那个 
int j; 
s1=min（ti）; 
s2=min（ti）; 
if（s1>s2） 
{ 
j=s1; 
s1=s2; 
s2=j; 
} 
} 
void HuffmanCoding（HuffmanTree &HTHuffmanCode &HCint *wint n） 
{ // w存放n个字符的权值（均>0）构造赫夫曼树HT并求出n个字符的赫夫曼编码HC 
int mis1s2start; 
//unsigned cf; 
int cf; 
HuffmanTree p; 
char *cd; 
if（n<=1） 
return;//检测结点数是否可以构成树 
m=2*n-1; 
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））; // 0号单元未用 
for（p=HT+1i=1;i<=n;++i++p++w） 
{ 
p->weight=*w; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
} 
for（;i<=m;++i++p） 
p->parent=0; 
for（i=n+1;i<=m;++i） // 建赫夫曼树 
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点其序号分别为s1和s2 
select（HTi-1s1s2）; 
HT[s1].parent=HT[s2].parent=i; 
HT[i].lchild=s1; 
HT[i].rchild=s2; 
HT[i].weight=HT[s1].weight+HT[s2].weight; 
} 
// 从叶子到根逆向求每个字符的赫夫曼编码 
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））; 
// 分配n个字符编码的头指针向量（[0]不用） 
cd=（char*）malloc（n*sizeof（char））; // 分配求编码的工作空间 
cd[n-1]=‘\0‘; // 编码结束符 
for（i=1;i<=n;i++） 
{ // 逐个字符求赫夫曼编码 
start=n-1; // 编码结束符位置 
for（c=if=HT[i].parent;f!=0;c=ff=HT[f].parent） 
// 从叶子到根逆向求编码 
if（HT[f].lchild==c） 
cd[--start]=‘0‘; 
else 
cd[--start]=‘1‘; 
HC[i]=（char*）malloc（（n-start）*sizeof（char））; 
// 为第i个字符编码分配空间 
strcpy（HC[i]&cd[start]）; // 从cd复制编码（串）到HC 
} 
free（cd）; // 释放工作空间 
} 
//---------------------获取报文并写入文件--------------------------------- 
int InputCode（） 
{ 
//printf（“请输入你想要编码的字符“）; 
FILE *tobetran; 

if（（tobetran=fopen（“tobetran.txt““w“））==NULL） 
{ 
printf（“不能打开文件“）; 
return 0; 
} 
printf（“请输入你想要编码的字符“）; 
scanf（“%s“str）;
fputs（strtobetran）; 
printf（“获取报文成功“）; 
fclose（tobetran）; 
return strlen（str）; 
} 



//--------------初始化赫夫曼链表--------------------------------- 
void Initialization（） 
{ int akflaglen; 
a=0; 
len=InputCode（）; 
for（i=0;i{k=0;flag=1; 
cou[i-a].data=str[i]; 
cou[i-a].count=1; 
while（i>k） 
{ 
if（str[i]==str[k]） 
{ 
a++; 
flag=0; 
} 
k++; 
if（flag==0） 
break; 

} 

if（flag） 
{ 
for（j=i+1;j{if（str[i]==str[j]） 
++cou[i-a].count;} 
} 

} 
n=len-a; 
for（i=0;i{ printf（“%c的出

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       8718  2009-01-07 11:08  huffman\huffman.cpp

     文件     198656  2009-01-07 18:00  huffman\图画\1 main.edd

     文件     171008  2009-01-07 18:02  huffman\图画\1i.edd

     文件      16005  2009-01-07 18:02  huffman\图画\1i.jpg

     文件      19905  2009-01-07 18:00  huffman\图画\1main.jpg

     文件     174592  2009-01-07 18:03  huffman\图画\2e.edd

     文件      17931  2009-01-07 18:04  huffman\图画\2e.jpg

     文件     174592  2009-01-07 18:10  huffman\图画\3d.edd

     文件      19309  2009-01-07 18:10  huffman\图画\3d.jpg

     文件     169472  2009-01-07 18:12  huffman\图画\4p.edd

     文件      18064  2009-01-07 18:12  huffman\图画\4p.jpg

     文件     173568  2009-01-07 18:13  huffman\图画\5t.edd

     文件      17193  2009-01-07 18:13  huffman\图画\5t.jpg

     文件     173568  2009-01-07 18:14  huffman\图画\6y.edd

     文件      17367  2009-01-07 18:14  huffman\图画\6y.jpg

     目录          0  2009-03-01 23:17  huffman\图画

     目录          0  2009-04-22 16:34  huffman

----------- ---------  ---------- -----  ----

              1369948                    17