实验四 哈夫曼树与哈夫曼编码

实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容本次实验提供4个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一、哈夫曼树和哈夫曼编码[问题描述]一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。［测试数据］利用教材P.148例6－2中的数据调试程序(可自己设定测试数据)。[选作内容]1、打印出该哈夫曼树2、若从终端输入任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。提示：如何快速统计不同字符的出现频率3、译码：将上述1的编码结果还原成电文。三、算法设计设计思路设计过程1、程序所需头文件已经预处理宏定义以及变量如下#include<iostream>#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>usingnamespacestd;typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){ linkhufp1,p2; if(root==NULL) root=s; else { p1=NULL; p2=root; while(p2&&p2->data<s->data) { p1=p2; p2=p2->next; } s->next=p2; if(p1==NULL) root=s; else p1->next=s;}returnroot;}2、创建哈夫曼树voidcreatehuffman(linkhuf*root){linkhufs,rl,rr;while(*root&&(*root)->next){ rl=*root; rr=(*root)->next; *root=rr->next; s=(linkhuf)malloc(sizeof(hufnode)); s->next=NULL; s->data=rl->data+rr->data; s->parent=NULL; s->lchild=rl; s->rchild=rr; rl->parent=s; rr->parent=s; rl->next=rr->next=NULL; *root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}3、哈夫曼编码voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;while(temp->parent!=NULL){if(temp->parent->lchild==temp) HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;else HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->lchild,temp,HFcode,leaftop);}}4、输出求得的哈夫曼编码voidOutCoding(tagHFcodeHFcode[],intleaftop){ inti,j=0; for(i=0;i<leaftop;i++) { printf("%d\t",HFcode[i].data); j=HFcode[i].top-1; while(j>=0) { printf("%d",HFcode[i].code[j]); j--; } printf("\n"); } }四、调试与测试输入字符ABCDEFGH进行测试五、心得体会做这次实验，发现在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用，特别是对栈和队列的操作问题。大一的课程以及C语言没掌握好，所以这次做实验，觉得有好多知识不熟悉，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。以后在课余时间里还要多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。六、源代码#include<iostream>#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>usingnamespacestd;typedefstructnode{charch;intdata;structnode*parent;structnode*lchild,*rchild,*next;}hufnode;typedefhufnode*linkhuf;typedefstructHFcode{charch;intdata;intcode[20];inttop;}tagHFcode;linkhufinsert(linkhufroot,linkhufs){ linkhufp1,p2; if(root==NULL) root=s; else { p1=NULL; p2=root; while(p2&&p2->data<s->data) { p1=p2; p2=p2->next; } s->next=p2; if(p1==NULL) root=s; else p1->next=s;}returnroot;}voidcreatehuffman(linkhuf*root){linkhufs,rl,rr;while(*root&&(*root)->next){ rl=*root; rr=(*root)->next; *root=rr->next; s=(linkhuf)malloc(sizeof(hufnode)); s->next=NULL; s->data=rl->data+rr->data; s->parent=NULL; s->lchild=rl; s->rchild=rr; rl->parent=s; rr->parent=s; rl->next=rr->next=NULL; *root=insert(*root,s);}}voidinorder(linkhuft){if(t){inorder(t->lchild);printf("%5d",t->data);inorder(t->rchild);}}voidHFcoding(linkhufroot,linkhuftemp,tagHFcodeHFcode[],int*leaftop){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL){temp=root;HFcode[(*leaftop)].top=0;HFcode[(*leaftop)].ch=root->ch;HFcode[(*leaftop)].data=root->data;while(temp->parent!=NULL){if(temp->parent->lchild==temp) HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;else HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;HFcode[(*leaftop)].top++;temp=temp->parent;}(*leaftop)++;}HFcoding(root->lchild,temp,HFcode,leaftop);HFcoding(root->lchild,temp,HFcode,leaftop);}}//输出求得的哈夫曼编码voidOutCoding(tagHFcodeHFcode[],intleaftop){ inti,j=0; for(i=0;i<leaftop;i++) { printf("%d\t",HFcode[i].data); j=HFcode[i].top-1; while(j>=0) { printf("%d",HFcode[i].code[j]); j--; } printf("\n"); } }intmain(){tagHFcodeHFcode[20];linkhuff=NULL;linkhuftemp=NULL;linkhufp[6];inti;inta[20];charch;intleaftop=0;printf("请输入各节点的节点值和权值：\n");for(i=0;i<7;i++){p[i]=(linkhuf)malloc(sizeof(hufnode));scanf("%c",&(p[i]->ch));getchar();scanf("%d",&p[i]->data);p[i]->lchild=NULL;p[i]->rchild=NULL;p[i]->nex