数据结构实验三实验报告.doc

《数据结构实验三实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、三题目：哈夫曼编/译码器班级：姓名：学号：完成日期：15.11.14一、题目要求描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.输入：输入表示字符集大小为n（n<=100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）；输入串长小于或等于100的目标报文。输出：经过编码后的二进制码，占一行；以及对应解码后的报文，占一行；最后输出一个回车符。输入样例：5abcde124015825bbbaddeccbbb输出样例：0000bbbaddeccb

2、bb提示：利用编码前缀性质。二、概要设计1.设计需要的数据结构：树型结构2.需要的抽象数据类型：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,„,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H;(3)对应于D

3、-{root}的划分，H-{,„,}有唯一的一个划分H1，H2,„,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。｝三、详细设计算法设计1.设计

4、一个存储数据的数组结构体typedefstruct{charcd[200];//最大的数据intstart;}HuffmanCode;2.设计一个结构体数组：在表示哈夫曼树时，用如下的结构体保存哈夫曼树中个结构体的信息，根据二叉树的性质可知，具有N个节点的哈夫曼树共有2n-1个节点。typedefstruct{intweight;chardata;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;3.设置全局变量HTNodeht[2*200];HuffmanCodehcd[200],d;inti,k,f,l,r,n,c,s1

5、,s2;chara;4.创建输入函数voidcreatsz(){for(i=1;i<=n;i++){cin>>ht[i].data;//输入数据}for(i=1;i<=n;i++){cin>>ht[i].weight;//输入数据的权重}}5.创建构造哈夫曼树的伪代码算法voidcreattree(){for(i=n+1;i<=2*n-1;i++){s1=s2=;l=r=0;for(k=1;k<=i-1;k++)//建立哈夫曼树{if(ht[k].parent==0){if(ht[k].weight

6、f(ht[k].weight

7、--d.start]='0';}else{d.cd[--d.start]='1';}c=f;f=ht[f].parent;}hcd[i]=d;}}7.主函数intmain(){intj=0;charh[100];cin>>n;//输入要求的数据个数creatsz();creattree();creatlist();a=getchar();cin>>h;for(j=0;h[j]!='';j++){for(i=1;;i++){if(ht[i].data==h[j])break;}