int n); //编码 void translate(char **hc code *p
int n);//译码
void display(code *p int n
int m); //输出函数 //主函数 void main() {
int i n m;
code *ht;
printf(\字符的数量:\\n(请输入一个大于0的数字 输入多个数字则按第一个数字运行)\\n\ while(scanf(\&n)!=1||n<0||n>9999) {
printf(\重新输入：\\n\ fflush(stdin); }
m=2*n-1; //哈夫曼树中没有度为1的结点 故含有m=2n-1个结点
ht=(code*)malloc((m+1)*sizeof(code));//动态申请内存
for(i=1;i<=n;i++) //对1~n的数进行初始化 {
printf(\输入编码中的字符(请输入一个字母):\\n\ fflush(stdin); scanf(\&ht[i].a);
while(!(ht[i].a>'a'||ht[i].a<'z'||ht[i].a>'A'||ht[i].a<'Z')) {
printf(\重新输入：\\n\ fflush(stdin); scanf(\&ht[i].a);//清空输入缓冲区 往往是确保不影响后面数据的读取 }
printf(\输入字符的权值(请输入一个数字):\\n\ while(scanf(\
&ht[i].w)!=1||ht[i].w<0||ht[i].w>9999) {
printf(\重新输入：\\n\
fflush(stdin); //清空输入缓冲区 往往是确保不影响后面数据的读取 }
ht[i].lchild=0; ht[i].rchild=0; ht[i].parent=0; }
for(i=n+1;i<=m;i++) //对n+1~2n-1的数进行初始化 { ht[i].a='*'; ht[i].w=0;
ht[i].lchild=0; ht[i].rchild=0; ht[i].parent=0; }
creation(ht n m);
printf(\请按回车进入哈夫曼树对应界面\\n\ getchar(); getchar(); system(\ display(ht n m);
printf(\请按回车进入编码对应界面\\n\ getchar(); system(\ coding(ht n);
getchar(); }
void creation(code *ht int n int m) {
int i j m1 m2 t1 t2;
for(i=n+1;i<=m;i++)
{
j=1; //找到第一个最小值（双亲不为0） while(ht[j].parent!=0) //找到表中第一个没有双亲的结点 {
j++; }
t1=ht[j].w; m1=j;
for(j=m1+1;j<=m;j++) {
if(ht[j].parent==0&&ht[j].w!=0)//条件(ht[j].w!=0)是因为n~2n-1的权值初始值为0 {
if(ht[j].w t1=ht[j].w; m1=j; } } } ht[m1].parent=i; //第一个值的双亲为ht[i] ht[i].lchild=m1; //h[i]的的左孩子是最小值的序号 j=1; //剩余中找到第二个最小值（双亲不为0） while(ht[j].parent!=0) { j++; } t2=ht[j].w; m2=j; for(j=m2+1;j<=m;j++) { if(ht[j].parent==0&&ht[j].w!=0) { if(ht[j].w t2=ht[j].w; m2=j; } } } ht[m2].parent=i; //第二个值的双亲为ht[i] ht[i].rchild=m2; //h[i]的的左孩子是最小值的序号 ht[i].w=t1+t2; //h[i]的权值是找到的两个值的权值之和 } } void coding(code *p int n) { int i c f; char **hc; //指针的指针 char *cd; char ch; int start; hc=(char**)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1]='\\0'; //编码结束符 for(i=1;i<=n;i++) { start=n-1; for(c=i f=p[i].parent;f!=0;c=f f=p[f].parent)//从叶子到根逆向求编码 { if(p[f].lchild==c) //左孩子编码为'0' { cd[--start]='0'; } else //右孩子编码为'1' { cd[--start]='1'; } } hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 strcpy(hc[i] &cd[start]); //从cd复制编码（串）到hc &是取地址符 即取首地址 从start位置到'\\0'的编码为止 } free(cd); //释放工作空间 printf(\输出编码后的结果：\\n\ printf(\符号 数码\\n\ for(i=1;i<=n;i++) { printf(\ %s\\n\ p[i].a hc[i]); } printf(\是否进行译码操作 是则译码 否则退出程序！\\n是（输入y/Y）否（输入其他字符）\\n\ scanf(\&ch); if(ch=='y'||ch=='Y') { translate(hc p n); } else exit(0); } void translate(char **hc code *p int n) { char a[10] ch; int i j c; do { printf(\请输入编码：\\n\ scanf(\ a); //回车之后会自动生成'\\0' for(i=1;i<=n;i++) { if(strcmp(a hc[i])==0) //比较两个字符串是否相等 相等则输出0 { for(c=2*n-1 j=0;a[j]!='\\0';j++) //从根出发 按字符'0'或'1'确定找左孩子或右孩子 { if(a[j]=='0') //左孩子 { c=p[c].lchild;