哈夫曼树实验报告.docx

《哈夫曼树实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、中南大学《数据结构》课程实验实验报告题目hafuman编码学生姓名柯鑫鑫学生学号3901130604专业班级1306需求分析设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：1、根据所提供的字母数据建立一个Huffman树；2、根据生成的Huffman树的结构，显示输出所有字母的Huffman编码。3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。概要设计要结构体存放每个节点的信息，要数组存放字母频率表的信息，节点与节点之间用二叉链表连接。结构体的结构如下structNode

2、{chardate;intweight;Node*parent;Node*lchild;Node*rchild;};date表示存放的字母，weight表示权重。把叶子节点方在前面。叶子节点与总节点的关系为总结点=叶子节点*2-1；（注：可以把常量定义成#defineNUM94//字符数#defineTNUM187//#defineLTH20//编码最大长度好处如下便于程序的升级有利于直观的理解，而不只是数字）初始化各个节点如下for(inti=0;idate=chars[i];node[i]->parent

3、=NULL;node[i]->weight=weight[i];node[i]->lchild=NULL;node[i]->rchild=NULL;}for(inti=NUM;iparent=NULL;node[i]->weight=-1;node[i]->lchild=NULL;node[i]->rchild=NULL;}详细设计找出没有父节点的最小的两个节点for(inti=NUM;i

4、r(;jparent==NULL){if(node[j]->weight<=one){two=one;b=a;one=node[j]->weight;a=j;}elseif(node[j]->weight>one&&node[j]->weight<=two){two=node[j]->weight;b=j;}}}node[j]->lchild=node[a];node[j]->rchild=node[b];node[a]->parent=node[j];node[b]->parent=node[j];nod

5、e[j]->weight=node[a]->weight+node[b]->weight;}定义数组来存储哈夫曼编码并初始化charHT[NUM][LTH];for(inti=0;iparent!=NULL){Node*temp=m->parent;

6、if(m==temp->lchild){HT[i][j]='0';}if(m==temp->rchild){HT[i][j]='1';}m=m->parent;j--;}}输出哈夫曼编码表strings[NUM];for(inti=0;idate<<""<

7、//编码stringcode;for(inti=0;i

8、putt.at(i)<=57)code.append(s[53+inputt.at(i)-'0']);elseif(33<=inputt