#include<stdio.h> #include<string.h> #define max 100 #define maxsize 100//哈夫曼编码的最大位数 typedef struct{ char ch;//字符 float weight;//权重值 int lchild,rchild,parent;//左孩子、右孩子，双亲的存储下标 }hufmtree; typedef struct{ char bits[maxsize];//位串 int start; //编码在位串中的起始位置 char ch; //存储的字符是谁？ }codetype; void Select(hufmtree ht[],int n,int *s1,int* s2); //建立哈夫曼树 void huffman(hufmtree *tree,int n) { int i,s1,s2,m = 2*n-1; float f; char c; for(i=0;i<m;i++) //初始化哈夫曼树 { tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; tree[i].weight=0.0; } for(i=0;i<n;i++) //读入前n个结点的字符及权重值 { printf("第%d个元素的=>\n",i+1); printf("\t结点值:"); scanf("%c",&c); getchar(); printf("\t权重:"); scanf("%f",&f); getchar(); tree[i].ch=c; tree[i].weight=f; } for(i=n;i<m;i++){ Select(tree,i,&s1,&s2); tree[i].weight=tree[s1].weight+tree[s2].weight; tree[i].lchild=s1;tree[i].rchild=s2;//i的左右孩子 tree[s1].parent=i ;tree[s2].parent=i; } } void Select(hufmtree *ht,int n,int *s1,int* s2) { //下标从0开始，那么其最后一个元素所在的下标就为n-1 int i,j,flag=1; int sum,t; for(i=0;i<n-1;i++){ for(j=i+1;j<n;j++){//不等于-1说明已经找到了其双亲，那么进行下一轮循环 if(ht[i].parent!=-1) continue; else{ if(ht[j].parent==-1){ if(flag==1){ sum=ht[i].weight+ht[j].weight; flag=0;*s1=i;*s2=j; } else{ if((ht[i].weight+ht[j].weight)<sum){ sum=ht[i].weight+ht[j].weight; *s1=i;*s2=j; } } } } } } //*s1对应的权重大那么交换*s1,*s2中的值，让*s1对应下标的值 //始终对应的是比较中最小的那一部分 if(ht[*s1].weight>ht[*s2].weight){ t=*s1;*s1=*s2;*s2=t; } } 根据哈夫曼树求出哈夫曼编码 void huffmancode(codetype *code,hufmtree tree[],int n) { int i,c,p; codetype cd; for(i=0;i<n;i++) { cd.start=n; cd.ch=tree[i].ch; c=i; //从叶结点出发向上回溯 p=tree[i].parent; //tree[p]是tree[i]的双亲 while(p!=-1) { cd.start--; if(tree[p].lchild==c) cd.bits[cd.start]='0'; //tree[i]是左子树，生成代码'0' else cd.bits[cd.start]='1'; //tree[i]是右子树，生成代码'1' c=p; p=tree[p].parent; } code[i]=cd; //第i+1个字符的编码存入code[i] } } //将编码串译码成相对应的字符序列 int Translate_code(hufmtree *tree,int m)//依次读入电文，根据哈夫曼树译码 { int i,j=0,k=0; char b[maxsize]; char endflag='b'; //电文结束标志取b i=m-1; //从根结点开始往下搜索 getchar(); gets(b); printf("输出哈夫曼译码：\n"); if(b[j]=='b'){ printf("不能只输入结束字符，请输入有效的值"); return 0; } while(b[j]!='b') { if(b[j]=='0') i=tree[i].lchild; //走向左孩子 else if(b[j]=='1') i=tree[i].rchild; //走向右孩子 if(tree[i].lchild==-1) //tree[i]是叶结点 { printf("%c",tree[i].ch); i=m-1; //回到根结点 } j++; } printf("\n"); if(tree[i].lchild!=-1&&b[j]!='b') //电文读完，但尚未到叶子结点 printf("\n请输入合法的编码串\n"); //输入电文有错 } //将字符串进行编码 void Translate_ch(codetype*code,int n){ char b[100]; int i,j=0,k; getchar(); printf("请输入字符串\n"); gets(b); printf("编码结果如下:\n"); for(i=0;i<n;i++){ if(j<=strlen(b)){ if(b[j]==code[i].ch){ for(k=code[i].start;k<n;k++) printf("%c",code[i].bits[k]); j++; i=-1; } } } } //主函数--程序入口 int main(){ int i,j,n,m,choice; hufmtree tree[max]; codetype code[max]; while(1){ printf("\t\t请选择您要实现的功能：（输入1-5数字）\n"); printf("\t1---建立哈夫曼树\n"); printf("\t2---各个字符的编码\n"); printf("\t3---将编码串进行译码\n"); printf("\t4---将字符串进行编码\n"); printf("\t5---退出系统\n"); scanf("%d",&choice); switch(choice){ case 1: printf("请输入元素个数："); scanf("%d",&n); getchar(); huffman(tree,n);//建立哈夫曼树 printf("哈夫曼树已成功建立！\n"); break; case 2: printf("输出哈夫曼编码：\n"); huffmancode(code,tree,n);//根据哈夫曼树求出哈夫曼编码 for(i=0;i<n;i++){ printf("%c: ",code[i].ch); for(j=code[i].start;j<n;j++) printf("%c",code[i].bits[j]); printf("\n"); } break; case 3: m=2*n-1; printf("请输入电文（0 or 1）,以b为结束标志：\n"); Translate_code(tree,m);//依次读入电文，根据哈夫曼树译码 break; case 4: Translate_ch(code,n); break; case 5: break; } } return 0; }
