数据结构大作业.docx
预习分 操作分 报告分 总成绩指导老师实验学号姓名实验名称哈夫曼编码器设计班级实验日期一实验报告具体内容普通应包括：一、实验目的和要求;二、实验原理;三、主要仪器设备（软件）;四、实验内容及实验数据记录;五、实验数据处理与分析;六、问题与建议一、实验目的和要求：哈夫曼(HLlffman)树与哈夫曼码1 .输入一个文本，统计各字符浮现的频度，输出结果；2 .使用二叉链表或者三叉链表作存储结构，构造哈夫曼(HUffman)树；3 .确定和输出各字符的哈夫曼码；4 .输入一个由O和1组成的代码序列，翻译并输出与之对应的文本；要求：一个完整的系统应具有以下功能：(1)初始化：从终端读入一段英文字符，统计每一个字符浮现的频率，建立赫夫曼树，并将该树存入某文件；(2)编码：利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中；(3)解码：利用保存的赫夫曼编码，对任意输入的0,1序列能正确解码二、实验思路：对输入的一串字符串，用循环进行浮现频率的统计，浮现频率即为节点的权值。为了方便将叶子节点数定义成为全局变量。创建哈夫曼树时，先给哈夫曼树创建一个节点，挨次对叶子节点和非叶子节点进行初始化。将全部的叶子节点中最小权值的两个节点的权值进行相加即为非叶子节点。进行哈夫曼编码时，从叶子节点到根节点进行编码。而进行解码时，是从根节点到叶子节点，向左为0向右为K由于书上有相关代码，一部份代码直接借用。三、实验代码：#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)jparent=0)*s2=j;break;)for(j=1;j<=i;j+)选择两个最小权值的结点>K(*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+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.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,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,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：<3J> WSDebug78xe'I O12 3 4SinIt打为为为为 1££数数数数 JQ k' S LuI <O"T K; m SASdf 1110 2til 310 4e输入一轴代称10111010圾瞬符为：sfdressanykeytocontinue五、实验小结：通过这次试验，我学会了如何进行哈夫曼树的创建，哈弗曼编码以及解码。实验中遇到的问题有：如何统计一个字符串中一个字符浮现的次数以及如何将每一个字符浮现的次数保存；如何将一个数组传入到子函数中，在试验中往往浮现数据无法传入子函数中的情况；如何在所有的节点中查找出最小的两个叶子节点；通过这次试验发现自己对子函数的参数的传入，指针的运用十分生疏。C语言的一些内容也有些遗忘。六、流程图Select函数的流程图:Creattree的函数流程图:TCharge的函数流程图:pruMir%的稳t?.Creatnode的函数流程图:HMr«；ilstart-fl-1;c-i4>K*hr>(i.pineiitcdtart卜U;cd(">t)-'r:CbtMwent«M)iTcbaEmU。i*tframed):Translate的函数流程图:数据结构实验题目：哈夫曼（HUffman树）与哈夫曼码学院：专业：学号：学生姓名：指导教师：S期：
