huffman编码.docx
- 文档编号:5706364
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:19
- 大小:19.44KB
huffman编码.docx
《huffman编码.docx》由会员分享,可在线阅读,更多相关《huffman编码.docx(19页珍藏版)》请在冰点文库上搜索。
huffman编码
#include
#include
#include
#include
#include
#defineNULL0
typedefstructhuff_code_node//存储编码的链表
{
charch;//编码对应的字符
charcode[100];//字符对应的哈夫曼码
structhuff_code_node*next;
}hnode,*huff;
typedefstructtree_Node//二叉树结点
{
charch;//字符内容
intamount;//字符在字符串中出现的次数
structtree_Node*left,*right;//指向左子树与右子树
}tnode,*bt;
typedefstructlist_node//链表结点
{
charch;//存储字符串中的字符
intamount;//字符在字符串中出现的次数
tnode*son;//链表结点带有二叉子树的根结点指针
structlist_node*next;//指向链表中下一个结点
}Node,*L;
typedefstructstack_node
{
charch;//存储字符
intamount;//出现次数
btson;//指向二叉树的某结点
structstack_node*next;
}snode,*stack;
chart[200],*str,*c;//用于存储和处理输入的字符串
btroot=NULL;//哈夫曼树
Ll,p,q,new_node;//链表结点
huffhlist;//计算得到的编码表
intchar_num;//输入的不同字符数量
intchar_amount;//输入的所有字符数量
intcode_sum;//哈夫曼编码总长
voidinitial()//初始化操作
{
l=(Node*)malloc(sizeof(Node));//建立空链表
l->ch='\0';
l->amount=0;
l->son=NULL;
l->next=NULL;
str=t;//将字符串指针指向字符串的第一个位置//键盘输入字符串
printf("输入字符串进行哈夫曼编码:
\n");
scanf("%s",str);
getchar();
}
voidpull_in_list()
{
intexist;//表示当前字符是否存在于链表中,0为不存在,1为已存在
intn;//计算输入不同字符的数量,计算后赋值给全局变量
char_num;
intm;//计算输入所有字符的数量,计算后赋值给全局变量
char_amount;
c=str;//c指向第一个字符
while(*c!
='\0')//若字符串未读完
{
exist=0;
p=l;//p指向链表头结点//寻找该字符是否已经在链表中
while(p->next!
=NULL)//若链表非空
{
p=p->next;
if(p->ch==*c)//若当前字符已经在链表中
{
exist=1;
p->amount++;//字符出现次数加1
break;
}
}
if(exist==0)//若当前字符不存在于链表中,则分配一个结点入表
{
new_node=(Node*)malloc(sizeof(Node));
new_node->ch=*c;
new_node->amount=1;
new_node->next=NULL;
new_node->son=NULL;
p->next=new_node;
p=new_node;
}
c++;//读下一个字符
}
printf("统计结果:
\n");
p=l;
n=0;
m=0;
while(p->next!
=NULL)
{
n++;
p=p->next;
m+=p->amount;
printf("%c--%d\n",p->ch,p->amount);
}
char_num=n;
char_amount=m;
printf("一共有%d种字符输入,字符总数%d\n",char_num,char_amount);
printf("\n\n\n\n\n\n\n\n\n\n");
}
intlist_element_amount()//计算链表中结点的数量(不包括头结点)
{
Ltemp;//定义临时指针
intn=0;//结点数量
temp=l;
while(temp->next!
=NULL)//后面还有结点
{
n++;
temp=temp->next;
}
returnn;
}
btcreate()//建立最优二叉树
{//这些变量用于寻找最小结点
Lmin1_pos,min2_pos,t,min_pri;
btmin1_son,min2_son;
intmin1,min2;
charmin1_c,min2_c;//这些变量用于构造二叉子树
btleft,right,root;//这些变量用于将二叉子树信息插入链表
Lmade,temp_p;
while(list_element_amount()>=2)//若表中还有两个或以上结点,则归并继续
{//选择次数值最小的两个结点//先寻找第一个小结点
t=l->next;
min1=t->amount;//将第一个结点的次数值赋给min1
min1_pos=t;//将第一个结点的位置指针赋给
min1_pos;
min1_c=t->ch;//将第一个结点的字符赋值给min1_c
min1_son=t->son;//将第一个结点的二叉指针赋值给min1_son
min_pri=l;//min_pri始终指向最小结点的前驱,以方便删除最小结点
while(t->next!
=NULL)
{
t=t->next;
if(min1>t->amount)//发现更小的结点
{
min1=t->amount;//将当前结点的次数值赋给min1
min1_pos=t;//将当前结点的位置指针赋给min1_pos
min1_c=t->ch;//将当前结点的字符赋值给min1_c
min1_son=t->son;//将当前结点的二叉指针赋值给min1_son
}
}//退出本循环时,最小结点的信息找出,将该结点删除
min_pri=l;
while(min_pri->next!
=min1_pos)
min_pri=min_pri->next;//退出循环时min_pri指向min1_pos的前驱
min_pri->next=min1_pos->next;//删除结点min1_pos//寻找第一个小结点完成//先寻找第二个小结点
t=l->next;
min2=t->amount;//将第二个结点的次数值赋给min2
min2_pos=t;//将第二个结点的位置指针赋给min2_pos
min2_c=t->ch;
min2_son=t->son;
min_pri=l;//min_pri始终指向最小结点的前驱,以方便删除最小结点
while(t->next!
=NULL)
{
t=t->next;
if(min2>t->amount)//发现更小的结点
{
min2=t->amount;//将当前结点的次数值赋给min2
min2_pos=t;//将当前结点的位置指针赋给min2_pos
min2_c=t->ch;
min2_son=t->son;
}
}//退出本循环时,最小结点的信息找出,将该结点删除
min_pri=l;
while(min_pri->next!
=min2_pos)
min_pri=min_pri->next;//退出循环时min_pri指向min1_pos的前驱
min_pri->next=min2_pos->next;//删除结点min2_pos//寻找第二个小结点完成//两个最小结点找到,由这对结点级成一个二叉子树,将根结点插入链表中
if(min1_son==NULL)//该结点无二叉子树指针,则须新分配一个二叉树结点
{
left=(bt)malloc(sizeof(tnode));//产生左孩子
left->amount=min1;//次数值复制
left->ch=min1_c;//字符复制
left->left=NULL;
left->right=NULL;
}else//该结点为计算产生的结点,它已指向一个二叉子树
left=min1_son;//left直接指向已经生成的二叉子树的根结点
if(min2_son==NULL)//该结点无二叉子树指针,则须新分配一个二叉树结点
{
right=(bt)malloc(sizeof(tnode));//产生右孩子
right->amount=min2;//次数值复制
right->ch=min2_c;//字符复制
right->left=NULL;
right->right=NULL;
}else
right=min2_son;//left直接指向已经生成的二叉子树的根结点
root=(bt)malloc(sizeof(tnode));
root->amount=min1+min2;
root->ch='\0';//对于计算产生的树结点,字符均为空
root->left=left;
root->right=right;//二叉子树完成//生成一个对应上面已产生二叉子树地址的链表结点
made=(L)malloc(sizeof(Node));
made->amount=root->amount;
made->ch=root->ch;
made->next=NULL;
made->son=root;//将生成的链表结点插入链表中
temp_p=l;
while(temp_p->next!
=NULL)
temp_p=temp_p->next;//退出循环时temp_p指向链表最后一个结点
temp_p->next=made;//将生成的结点插入链表
}
temp_p=l->next;
returntemp_p->son;
}
huffencoding()//根据建立的哈夫曼树编码
{
stackcode,top,temp,readcode;
btr;
hufftemp_huff,hp,hlist;
charhuff[100]="";//用于存储当前字符的哈夫曼编码串
inti,j,n=0;
hlist=(hnode*)malloc(sizeof(hnode));
hlist->ch='\0';
for(i=0;i<100;i++)
hlist->code[i]='\0';
hlist->next=NULL;
hp=hlist;
code=(stack)malloc(sizeof(snode));
code->amount=0;
code->ch='\0';
code->next=NULL;
code->son=NULL;
top=code;//栈的头结点指向树的根结点
r=root;
temp=(stack)malloc(sizeof(snode));//给哈夫曼树的根结点分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;
while(r!
=NULL||top->next!
=code)//当前结点存在
{
while(r->right!
=NULL&&r->left!
=NULL)
{
if(r->left!
=NULL&&r->left->amount!
=-1)//当前结点有左孩子
{
r=r->left;//r转向左孩子
r->amount=-1;
temp=(stack)malloc(sizeof(snode));//给左孩子分配栈结点
temp->amount=r->amount;
temp->ch='0';
temp->next=top;
temp->son=r;
top=temp;
}
else
break;
}
if(top->next!
=code)
{
if(r->left==NULL&&r->right==NULL)//当前结点为叶子结点
{
for(i=0;i<100;i++)//对哈夫曼编码数组初始化
huff[i]='\0';//先输出该叶子结点的编码
printf("字符%c,编码为:
",r->ch);
readcode=top;
i=0;
while(readcode!
=code)
{
huff[i]=readcode->ch;//将栈元素倒置入哈夫曼编码数组中
readcode=readcode->next;
i++;
}
temp_huff=(hnode*)malloc(sizeof(hnode));//为当前字符及其编码创建结点
temp_huff->ch=r->ch;//存储编码的原字符
for(j=0;j<100;j++)//初始化编码串数组
temp_huff->code[j]='\0';
j=0;
for(i=i-2;i>=0;i--)//依次读出哈夫曼编码数组中的编码串
{
printf("%c",huff[i]);
temp_huff->code[j]=huff[i];
j++;
}
temp_huff->next=NULL;
hp->next=temp_huff;
hp=temp_huff;
printf("\t\t");
if(++n%2==0)
printf("\n");
}
top=top->next;
r=top->son;
if(r->right!
=NULL&&r->right->amount!
=-1)//当前结点有右孩子
{
r=r->right;//r转向右孩子
r->amount=-1;
temp=(stack)malloc(sizeof(snode));//给右孩子分配栈结点
temp->amount=r->amount;
temp->ch='1';
temp->next=top;
temp->son=r;
top=temp;
}
}elsebreak;
}
returnhlist;
}
voidcodeoutput(huffhlist)//输出原始字符串的哈夫曼编码串
{
huffhp;
inti;c=str;//c指向原始字符串str的首位置
printf("\n\n原始字符串为:
%s\n哈夫曼编码为:
",c);
code_sum=0;//在编码链表中找寻与c匹配的编码串
while(*c!
='\0')//字符串未读完
{
hp=hlist->next;//hp指向编码链表的第一个字符编码组
while(hp->ch!
=*c&&hp->next!
=NULL)//尚未找到匹配字符且后面还有字符
hp=hp->next;//退出循环的原因可能是找到了匹配字符,也可能是链表读完,需要进一步判断
if(hp->ch==*c)//找到匹配字符
{
i=0;
while(hp->code[i]!
='\0')
printf("%c",hp->code[i++]);
}
code_sum+=i;
c++;
}
printf("\n\n\n\n\n\n\n\n\n\n");
}
voidanalyze()//编码性能分析
{
intn=0;
printf("\t\t\t性能分析中...\n\n");
while(pow(2,n) n++; printf("等长码需要%d位,编码总长%d位,本次哈夫曼编码总长%d,压缩比%g\n",n,n*char_amount,code_sum,(float)code_sum/(n*char_amount)); printf("\n\n\n\n\n\n\n\n\n\n"); } voiddescribe_tree()//交互式显示哈夫曼树 { btt; stacks,top,temp; intchoice; s=(stack)malloc(sizeof(snode)); s->amount=0; s->ch='\0'; s->next=NULL; s->son=NULL; top=s; t=root;//t指向哈夫曼树的根结点 temp=(stack)malloc(sizeof(snode));//分配新栈结点 temp->amount=t->amount; temp->ch=t->ch; temp->next=top;//结点入栈 temp->son=t;//将当前二叉树结点指针给栈顶结点 top=temp;//修改栈顶指针 printf("输入1往左子树,输入2往右子树,输入3返回父结点,输入4退出程序,其它输入无效\n"); scanf("%d",&choice); getchar(); while(choice==1||choice==2||choice==3) { if(choice==1)//往左子树 { if(t->left! =NULL) { t=t->left; temp=(stack)malloc(sizeof(snode));//分配新栈结点//新结点入栈 temp->amount=t->amount; temp->ch=t->ch; temp->next=top;//结点入栈 temp->son=t;//将当前二叉树结点指针给栈顶结点 top=temp;//修改栈顶指针 printf("%c,%d\n",t->ch,t->amount); } else//左子树不存在,当前结点已经是叶子结点 printf("无左孩子! \n"); } elseif(choice==2)//往右子树 { if(t->right! =NULL) { t=t->right; temp=(stack)malloc(sizeof(snode));//分配新栈结点//新结点入栈 temp->amount=t->amount; temp->ch=t->ch; temp->next=top;//结点入栈 temp->son=t;//将当前二叉树结点指针给栈顶结点 top=temp;//修改栈顶指针 printf("%c,%d\n",t->ch,t->amount); }else//右子树不存在,当前结点已经是叶子结点 printf("无右孩子! \n"); }elseif(choice==3)//返回父结点 { if(top->next! =s)//栈非空 { top=top->next; t=top->son; printf("%c,%d\n",t->ch,t->amount); }else printf("已经在根结点了! \n"); }elseif(choice==4)//退出程序 exit(0); scanf("%d",&choice); getchar(); } } voidmain() { huffHlist; intchoice; initial(); pull_in_list(); system("cls"); root=create(); while (1) { if(root! =NULL) { printf("----------------------------------------------------------------"); printf("\n哈夫曼树构造完成,是否查看哈夫曼树,输入\n1.查看哈夫曼树\n2.编码字符串\n3.分析哈夫曼\n4.显示笑细节\n5.退出大系统\n"); printf("-------------------------
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- huffman 编码