哈夫曼编码课程设计

1湖南科技学院课程设计报告课程名称：数据结构课程设计课程设计题目：哈夫曼编码系：数学与计算科学系专业：信息与计算科学年级、班：信计0901姓名：郭如华学号：200905002145指导教师：牛志毅职称：讲师2011年12月2目录1问题描述…………………………………………32基本要求…………………………………………33测试数据…………………………………………34算法思想…………………………………………35模块划分…………………………………………36数据结构…………………………………………37源程序……………………………………………48测试情况…………………………………………99设计总结…………………………………………910参考资料…………………………………………931问题描述设计一个哈夫曼编码系统，对文档中的报文进行编码，输出这段报文的哈夫曼编码，并且可以对输入的哈夫曼编码进行译码。2基本要求从文档中读取报文（如whatdidyoudothatmadeyousohappy）进行编码输出这段报文的哈夫曼编码。3测试数据whatdidyoudothatmadeyousohappy4算法思想①：从文件中读取lei.txt并到数组z(保存所有字符的种类)，读取data,txt存到数组ch（保存统计频数的一个样本）。②：对数组z和数组ch进行比较统计出每个字符出现的频数，以频数代替权值，并把权值赋值到ht.weight的的数组中。③：利用权值创建哈夫曼树。④：利用哈夫曼树求的哈夫曼编码。把lei.txt的数据赋值到hcd.ch中，把编好的哈夫曼编码赋值到hcd.code，则hcd这个数组就是一个哈夫曼编码的集合，hcd.ch对应的下标就是这个字符所对应的哈夫曼编码。⑤：输入要编码的字符，保存到ch数组，把ch数组的ch[j]元素逐个与hcd[i].ch比较找出下标i，则hcd[i].code为ch[j]元素的哈夫曼编码。⑥：输入要译码的哈夫曼编码lcd，逐个与hcd[i].code比较，找出下标i，则hcd[i].ch为lcd所对应的字符。5模块划分①：voidinithuffmantree(huffmantreeht);/*初始化哈夫曼树*/②：voidtongji(huffmantreeht,huffmancodehcd,char*ch,char*z);/*统计权值*/③：voidselectmin(huffmantreeht,inti,int*p1,int*p2);/*选择最小的权值*/④：voidcreatehuffmantree(huffmantreeht);/*创建哈夫曼树*/⑤：voidhuffmancodes(huffmantreeht,huffmancodehcd,char*z);/*利用哈夫曼树求哈夫曼编码*/⑥：voidbianma(huffmancodehcd);/*对输入的字符进行编码*/⑦：voidyima(huffmancodehcd);/*对输入的哈夫曼编码进行译码*/6数据结构typedefstruct{intweight;intlchild,rchild,parent;}htnode;typedefhtnodehuffmantree[m+1];定义哈夫曼树的结构类型。4typedefstruct{charch;charcode[10];}codenode;typedefcodenodehuffmancode[n+1];定义存储哈夫曼编码的类型。7源程序main.cpp#includeiostream#includeconio.h#includestdlib.h#includehuffman.h#includefstream#includestring.husingnamespacestd;intmain(){charch[200];/*用于存储样本*/charz[54];/*用于存储所有字符类别*/huffmantreeht;/*定义一个数组ht，用于存储哈夫曼树*/huffmancodehcd;/*定义一个数组hcd，用于存储哈夫曼编码*/inithuffmantree(ht);/*初始化哈夫曼树*/ifstreaminfile1(lei.txt);/*lei.txt文件保存了所有字符的总类*/if(!infile1){cout错误：数据文件不能打开!;}for(inti=0;i54;i++){infile1.get(z[i]);/*把lei.txt的数据读到数组z*/}ifstreaminfile2(data.txt);/*data.txt文件是统计频数的一个样本，以频数代替权值*/if(!infile2){cout错误：数据文件不能打开!;}for(inti=0;i200;i++){infile2.get(ch[i]);/*把data.txt数据读到数组ch*/5}tongji(ht,ch,z);/*统计权值*/createhuffmantree(ht);/*创建哈夫曼树*/huffmancodes(ht,hcd,z);/*求哈夫曼编码*/bianma(hcd);/*对输入的字符求编码*/coutendl;yima(hcd);/*对输入的编码求译码*/}huffman.h#ifndefHUFFMAN_H_INCLUDED#defineHUFFMAN_H_INCLUDED#definen53#definem2*n-1typedefstruct{intweight;intlchild,rchild,parent;}htnode;typedefhtnodehuffmantree[m+1];/*定义数组存储哈夫曼树*/typedefstruct{charch;charcode[10];}codenode;typedefcodenodehuffmancode[n+1];/*定义数组存储哈夫曼编码*/voidinithuffmantree(huffmantreeht);/*初始化哈夫曼树*/voidtongji(huffmantreeht,char*ch,char*z);/*统计权值*/voidselectmin(huffmantreeht,inti,int*p1,int*p2);/*选择最小的权值*/voidcreatehuffmantree(huffmantreeht);/*创建哈夫曼树*/voidhuffmancodes(huffmantreeht,huffmancodehcd,char*z);/*利用哈夫曼树求哈夫曼编码*/voidbianma(huffmancodehcd);/*对输入的字符进行编码*/voidyima(huffmancodehcd);/*对输入的哈夫曼编码进行译码*/#endif//HUFFMAN_H_INCLUDED6huffman.cpp#includestdio.h#includestdlib.h#includestring.h#includeconio.h#includeiostream#includehuffman.husingnamespacestd;voidinithuffmantree(huffmantreeht)/*初始化哈夫曼树*/{for(inti=1;i=m;i++){ht[i].weight=0;ht[i].lchild=0;ht[i].rchild=0;ht[i].parent=0;}}对传入函数的ht进行初始化。voidtongji(huffmantreeht,huffmancodehcd,char*ch,char*z)/*统计权值*/{intl;l=strlen(ch);for(inti=1;i54;i++)for(intj=1;jl;j++)if(z[i]==ch[j])ht[i].weight++;}数组ch是从文件data.txt中读取的数据，数组z是从lei.txt中读取的文件，把数组ch与数组z对比，统计每个字符出现的频数，存到ht.weight数组中。voidselectmin(huffmantreeht,inti,int*p1,int*p2)/*创建哈夫曼树*/{intj,min1,min2;/*min1,min2分别是最小权值和次小权值*/min1=min2=1;*p1=*p2=0;for(j=1;j=i;j++){if(ht[j].parent==0)if(ht[j].weightmin1||min1==1){if(min1!=1){min2=min1;7*p2=*p1;}min1=ht[j].weight;*p1=j;}elseif(ht[j].weightmin2||min2==1){min2=ht[j].weight;*p2=j;}}}在ht[1..i]中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号。voidcreatehuffmantree(huffmantreeht)/*利用哈夫曼树求哈夫曼编码*/{inti,p1,p2;inithuffmantree(ht);for(i=n+1;i=m;i++){selectmin(ht,i-1,&p1,&p2);ht[p1].parent=ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;ht[i].weight=ht[p1].weight+ht[p2].weight;}}在ht[1..i]中选parents为0且weight最小的的两个结点。其序号为p1，p2.voidhuffmancodes(huffmantreeht,huffmancodehcd,char*z)/*根据huffman树ht求huffman编码*/{intc,p,i;charcd[n+1];intstart;cd[n]='\0';for(i=1;i54;i++){hcd[i].ch=z[i];start=n;c=i;while((p=ht[c].parent)!=0){cd[--start]=(ht[p].lchild==c)?'0':'1';c=p;}strcpy(hcd[i].code,&cd[start]);8}coutendl;}数组z是从lei.txt中读取的文件，并把数组lei的值逐个赋给hcd.ch，把编号的哈夫曼编码赋给hcd.code。voidbianma(huffmancodehcd)/*对输入的字符进行编码*/{cout请输入要编码的报文：;charch[100];/*存储输入的字符*/gets(lch);intk=0;cout该报文的编码：;do{for(intj=1;j=n;j++)if(lch[k]==hcd[j].ch)couthcd[j].code'';k++;}while(lch[k]!='\0');coutendl;}数组hcd中保存了所有的哈夫曼编码。数组ch存储输入的字符，把ch中的字符与hcd.ch中的字符对比，找出下标j，则hcd[j].code为ch的哈夫曼编码。voidyima(huffmancodehcd)/*对输入的哈夫曼编码进行译码*/{charlcd[8];/*存储临时哈夫曼编码*/cout请输入要译码的哈夫曼编码结束请按#endl;do{gets(lcd);if(lcd[0]=='#')exit(1);for(intj=1;j=n;j++){if(!strcmp(lcd,hcd[j].code))cout该编码对应的字符为：hcd[j].chendl;}}while(lcd[0]!='#');}数组hcd中保存了所有的哈夫曼编码，lcd存储临时哈夫曼编码，把lcd中的元素与hcd.code进行比较，找到下标j，则hcd[j].ch为lcd所对应的编码。98测试情况该程序运行情况：该程序运行良好,能对输入的字符