求哈弗曼编码应用源程序，最好有流程图

Question

对输入的一串点文字符实现哈弗曼编码，在对哈弗曼编码生成代码串进行译码，输出电文字符串

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct
{char letter;/*存储字母*/
unsigned weight;/*存储权值*/
unsigned parent,Lchild,Rchild;
}HTNode,*HuffmanTree;

typedef struct
{char letter;/*存储字母*/
unsigned weight;/*存储权值*/
} WeightNode;

typedef char * * HuffmanCode;

void select(HuffmanTree *ht,unsigned i,unsigned *s1,unsigned *s2)/*选择两个权值最小的序号给s1,s2*/
{unsigned j=1,max=65535;
for(j=1;j<i+1;j++)
if((*ht)[j].parent==0&&(*ht)[j].weight<max)
{*s1=j;
max=(*ht)[j].weight;
}
(*ht)[*s1].parent=1;
max=32767;
for(j=1;j<i+1;j++)
if((*ht)[j].parent==0&&(*ht)[j].weight<max)
{*s2=j;
max=(*ht)[j].weight;
}
}

void CrtHuffmanTree(HuffmanTree *ht,WeightNode* w,unsigned n)/*建立哈夫曼树*/
{unsigned i,m,s1,s2;
m=2*n-1;
for(i=1;i<=n;i++)
{(*ht)[i].letter=w[i].letter;
(*ht)[i].weight=w[i].weight;
(*ht)[i].Lchild=(*ht)[i].parent=(*ht)[i].Rchild=0;
}
for(i=n+1;i<=m;i++)
{(*ht)[i].weight=(*ht)[i].Lchild=(*ht)[i].parent=(*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].weight=(*ht)[s1].weight+(*ht)[s2].weight;
} /*哈夫曼树建立完毕*/
printf("\n创建哈夫曼树成功!\n");
}

void IntoCode(HuffmanTree *ht,HuffmanCode *hc,unsigned n)/*根据哈夫曼树求哈夫曼编码*/
{char *cd;/*存储哈夫曼编码*/
unsigned i,p,c,start;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
printf("\n哈夫曼编码为:\n");
for(i=1;i<=n;i++)
{start=n-1;
for(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)
if((*ht)[p].Lchild==c)
cd[--start]='0';
else cd[--start]='1';
(*hc)[i]=(char*)malloc((n-start)*sizeof(char));
strcpy((*hc)[i],&cd[start]);
if((*ht)[i].letter==' '||(*ht)[i].letter=='\n')
(*ht)[i].letter==' '?printf("空格:"):printf("回车:");
else
printf("%c:",(*ht)[i].letter);
printf("%s",(*hc)[i]);
printf("\n");
}
}

void Translate(HuffmanTree *ht,int n) /*编译哈夫曼编码为字母序列*/
{unsigned i;
char hcode;
i=2*n-1;
printf("请输入哈夫曼编码:");
hcode=getchar();
printf("对应的字母序列为:");
while(hcode!='\n')
{if(hcode=='0')
i=(*ht)[i].Lchild;
else if(hcode=='1')
i=(*ht)[i].Rchild;
else
printf("错误编码！\n");
if((*ht)[i].Lchild==0&&(*ht)[i].Rchild==0)
{printf("%c",(*ht)[i].letter);i=2*n-1;}
hcode=getchar();
}
printf("\n");
}

unsigned receive(unsigned array[]) /*接收字符序列*/
{unsigned k=0;
FILE *fp;
char ch,choice;
do
{printf("\n\n选择字符序列接收方式:");
printf("\n\n1.从文件读入字符\n");
printf("2.从键盘输入字符\n");
printf("0.退出\n");
choice=getchar();
getchar();
system("cls");
switch(choice)
{case'1':
if((fp=fopen("编码.txt","r+"))==NULL)
{printf("文件打开失败！\n");
exit(0);
}
while((ch=fgetc(fp))!=EOF)
{array[ch]++;
k++;
}
fclose(fp);
break;
case'2':
printf("请输入字母序列:");
ch=getchar();
while(ch!='\n')
{array[ch]++;
ch=getchar();
k++;
}
break;
case'0':exit(0);
default:printf("输入错误！重新选择!\n");
}
}while(choice!='1'&&choice!='2');
return(k);
}

unsigned numout(unsigned array[],WeightNode*w) /*统计并输出各字符出现的次数*/
{int i,n;
n=1;/*把权值数组的起始下标定在1*/
for(i=0;i<256;i++)
{if(array[i]!=0)
{printf("******************\n");
if(i==' '||i=='\n')
i==' '?printf("空格 "):printf("回车 ");
else
printf("%c ",i);
printf("出现的次数为%d\n",array[i]);
w[n].weight=array[i];
w[n].letter=i;
n++;
}
}
n--;/*n可以表示接收到的字符种数*/
return(n);
}

void main()
{unsigned n,k,array[256]={0},i;
char choice;
HuffmanTree head;
HuffmanCode code;
HuffmanTree *ht;
HuffmanCode *hc;
WeightNode *w;/*w用于权值与字母对应结点指针*/
printf("\n\n*********************** 哈夫曼编码编码译码程序 *****************\n");
printf("****************************************************************\n");
k=receive(array);
w=(WeightNode*)malloc(k*sizeof(WeightNode));
n=numout(array,w);
head=(HuffmanTree)malloc((2*(n-1))*sizeof(HTNode));/*哈夫曼树的头结点*/
ht=&head;
code=(HuffmanCode)malloc(n*sizeof(char*));/*编码序列头结点*/
hc=&code;
CrtHuffmanTree(ht,w,n);
do
{printf("********************");
printf("\n\n请选择操作:\n");
printf("1.编码\n");
printf("2.译码\n");
printf("3.输入新的字符序列\n");
printf("0.退出\n");
choice=getchar();
getchar();
switch(choice)
{case'1':system("cls");IntoCode(ht,hc,n);break;
case'2':Translate(ht,n);break;
case'3':system("cls");
for(i=0;i<256;i++)
array[i]=0;
k=receive(array);
n=numout(array,w);
head=(HuffmanTree)malloc((2*(n-1))*sizeof(HTNode));/*哈夫曼树的头结点*/
ht=&head;
code=(HuffmanCode)malloc(n*sizeof(char*));/*编码序列头结点*/
hc=&code;
CrtHuffmanTree(ht,w,n);break;
case'0':exit(0);
default:printf("输入错误，请重新输入！\n");
}
}while(choice!='0');
}