北邮信通院数据结构实验报告三哈夫曼编码器.doc

数据结构实验报告实验名称:实验三树——哈夫曼编/解码器学生姓名:班级:班内序号:学号:日期:。基本要求:初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立赫夫曼树建立编码表(CreateTable):利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出。编码(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出。译码(Decoding):利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。打印(Print):以直观的方式打印赫夫曼树(选作)计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。测试数据:IlovedataStructure,puter。:1、用户界面可以设计为“菜单”方式:能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的字符一律不用编码。,可以构造出不同的二叉树,其中带权路径长度最小的二叉树称为Huffman树,也叫做最优二叉树。weightlchildrchildparent2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weightlchildrchildparent2-1-155-1-156-1-167-1-169-1-17701713238165482967-(1)计算出现字符的权值利用ASCII码统计出现字符的次数,再将未出现的字符进行筛选,将出现的字符及頻数存储在数组a[]中。voidHuffman::Init(){ intnNum[256]={0};//记录每一个字符出现的次数intch=(); inti=0; while((ch!='\r')&&(ch!='\n')) { nNum[ch]++;//统计字符出现的次数 str[i++]=ch;//记录原始字符串 ch=();//读取下一个字符 } str[i]='\0'; n=0;for(i=0;i<256;i++) { if(nNum[i]>0)//若nNum[i]==0,字符未出现{ l[n]=(char)i; a[n]=nNum[i]; n++; } }}时间复杂度为O(1);(2)创建哈夫曼树:算法过程:Huffman树采用顺序存储---数组;数组的前n个结点存储叶子结点,然后是分支结点,最后是根结点;首先初始化叶子结点元素—循环实现;以循环结构,实现分支结点的合成,合成规则按照huffman树构成规则进行。关键点:选择最小和次小结点合成。voidHuffman::CreateHTree(){ HTree=newHNode[2*n-1]; //根据权重数组a[0..n-1]初始化Huffman树 for(intj=0;j<n;j++) { HTree[j].weight=a[j]; HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1; } intx,y; for(inti=n;i<2*n-1;i++) //开始建Huffman树 { SelectMin(HTree,i,x,y); //从1~i中选出两个权值最小的结点 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].RChild=y; HTree[i].parent=-1; }}时间复杂度为O(n2)voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;//找一个比较值的起始值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1){i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}//开始找最小的两个i++;for(;i<n;i++){if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1&&hTree[i