数据结构大作业.docx

《数据结构大作业.docx》由会员分享，可在线阅读，更多相关《数据结构大作业.docx（13页珍藏版）》请在课桌文档上搜索。

1、预习分 操作分 报告分 总成绩指导老师实验学号姓名实验名称哈夫曼编码器设计班级实验日期一实验报告具体内容普通应包括：一、实验目的和要求;二、实验原理;三、主要仪器设备（软件）;四、实验内容及实验数据记录;五、实验数据处理与分析;六、问题与建议一、实验目的和要求：哈夫曼(HLlffman)树与哈夫曼码1 .输入一个文本，统计各字符浮现的频度，输出结果；2 .使用二叉链表或者三叉链表作存储结构，构造哈夫曼(HUffman)树；3 .确定和输出各字符的哈夫曼码；4 .输入一个由O和1组成的代码序列，翻译并输出与之对应的文本；要求：一个完整的系统应具有以下功能：(1)初始化：从终端读入一段英文字符，统

2、计每一个字符浮现的频率，建立赫夫曼树，并将该树存入某文件；(2)编码：利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中；(3)解码：利用保存的赫夫曼编码，对任意输入的0,1序列能正确解码二、实验思路：对输入的一串字符串，用循环进行浮现频率的统计，浮现频率即为节点的权值。为了方便将叶子节点数定义成为全局变量。创建哈夫曼树时，先给哈夫曼树创建一个节点，挨次对叶子节点和非叶子节点进行初始化。将全部的叶子节点中最小权值的两个节点的权值进行相加即为非叶子节点。进行哈夫曼编码时，从叶子节点到根节点进行编码。而进行解码时，是从根节点到叶子节点，向左为0向右为K由于书上

3、有相关代码，一部份代码直接借用。三、实验代码：#defineMAX50typedefstructintweight;intparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;intn;叶子结点数charaMAX;接受字符串的数组voidselect(HuffmaTree*ht,inti,int*s1,int*s2)(intj=1；for(j=1;j=i;j+)if(*ht)0.parent=O)(*s1=j;break;for(j=1;j=i;j+)(if(j=*s1)continue;else(计(*ht)jpar

4、ent=0)*s2=j;break;)for(j=1;jK(*ht)j.weight(*ht)*s1.weight&(*ht)0.parent=O&(*ht)*s1.weight!=(*ht)*s2.weight)*s1=j;for(j=1;j=i;j+)(if(j=*s1)continue;else(if(*ht)0weight(*ht)*s2.weight&(*ht)0parent=O)*s2=j;)voidCreattree(HuffmanTree*ht,HuffmanCode*hc,int*w)intm,i,s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m

5、+1)*sizeof(HTNode);for(i=1;i=n;i+)数组HUffnOdeU初始化(*ht)i.weight=wi;(*ht)i.parent=O;(*ht)i.lchild=O;(*ht)i.rchild=O;)for(i=n+1;i=m;i+)(*ht)i.weight=O;(*ht)i.parent=O;(*ht)i.lchild=O;(*ht)i.rchild=O;)for(i=n+1;i=m;i+)建立非叶子结点，Huffmantree(select(ht,i-1,&s1,&s2);(*ht)s1.parent=1;(*ht)s2.parent=!;if(*ht)s1.

6、weight(*ht)s2.weight)(*ht)i.lchild=s1;(*ht)i.rchild=s2;else(*ht)i.Ichild=s1;(*ht)i.rchild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight;voidcharge(int*w)i11ti,j,k=1;for(k=1;k=n;k+)wk=1;k=1；if(ai=T)continue;if(ai=aj)(wk+;aO=T;)的频数为k+;)voidcreatnode(HuffmaTree*ht,HuffmanCode*hc)(char*cd;inti,start,c,

7、p;*hc=(HuffmaCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);编码for(i=1;i=n;i+)(start=n-1;for(c=i,p=*ht)i.parent;p!=0;c=p,p=*ht)p.parent)if(*ht)p.lchild=c)cd-start=,O;elsecd-start=1;(*hc)i=(char*)malloc(n-start)*sizeof(char);strcpy(*hc)i,&cdstart);)free(cd);voidtranslate(HuffmaTree*ht,

8、int*w)intp；charsMAX;intm,k,i;m=0;请输入一串01代码p=2*n-1;对应的字符为(if(si=,O)p=(*ht)p.lchild;if(si=,1)p=(*ht)p.rchild;if(*ht)p.lchild=O&(*ht)p.rchild=O)(for(k=1;wk!=(*ht)p.weightjk+)m=m+wk;)四、实验数据put in the namber of the leafs： WSDebug78xeI O12 3 4SinIt打为为为为 1数数数数 JQ k S LuI K*hr(i.pineiitcdtart卜U;cd(t)-r:CbtMwentM)iTcbaEmU。i*tframed):Translate的函数流程图:数据结构实验题目：哈夫曼（HUffman树）与哈夫曼码学院：专业：学号：学生姓名：指导教师：S期：