数据结构课程设计-哈夫曼树及编码

HUFFMAN树及编码1.需求分析随机输入一篇英文文章（或读一个TXT文件），生成并显示HUFFMAN树，输出每个字母的HUFFMAN编码，判断ASCII编码与HUFFMAN编码对本篇报文长度节省效果。(a)输入的形式为键盘随机输入，输入的字符串长度在10000以内；(b)输出HUFFMAN树的存储结构；(c)程序功能为输入英文文章中每个字母的HUFFMAN编码，以及与ASCLL码编码长度的比较结果；(d)测试数据：正确的输入一篇英文文章，会输出各个字母的HUFFMAN编码。错误的输入即其输出输入错误。2.概要设计首先统计英文文章中各个字母的个数作为权值，再统计出现的字母的个数，以决定所构造赫夫曼树的节点个数，之后便开始构造赫夫曼树，再构造每个节点的哈夫曼编码。所设计的抽象数据类型如下：typedefstruct{unsignedintweight;//权值unsignedintparent,lchild,rchild;//双亲，左孩子，右孩子}HTNode,*HuffmanTree;typedefchar**HuffmanCode;所设计的函数如下：intmin(HuffmanTreeHT,inti)找出所有权值中最小的那个。voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)找出每次最小的两个权值最小的权值。StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)构造赫夫曼树并构造每个字母的赫夫曼编码。voidPrintHT(HuffmanTreeHT,intn)输出赫夫曼树的存储结构。3.详细设计intmin(HuffmanTreeHT,inti){intj,flag=1;unsignedintk=10000;for(j=1;j=i;j++){if(HT[j].weightk&&HT[j].parent==0){k=HT[j].weight,flag=j;}//if}HT[flag].parent=1;returnflag;}voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj;s1=min(HT,i);s2=min(HT,i);if(s1s2){j=s1;s1=s2;s2=j;}}StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){ints1,s2,i,start,f;char*cd;HuffmanTreep=NULL;//p是工作指针，指向赫夫曼树中的结点if(n=1){returnERROR;}intm=2*n-1;//n个字符构造的赫夫曼树共有m=2*n-1个结点printf(-待构造的赫夫曼树共有2×%d-1=%d个结点\n,n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申请赫夫曼树结点占用的内存空间,0号单元不用{exit(OVERFLOW);}//ifprintf(-赫夫曼树共分配了%d个结点空间，其中包含一个不用的0号单元\n,m+1);//printf(-初始化所有叶子节点的权值，父亲和孩子：\n);for(p=HT+1,i=1;i=n;++i,++p,++w){p-weight=*w;p-parent=0;//双亲初始值为0，表示此结点还没有被选择最小的算法选择过p-lchild=0;//左右孩子初始化为0，表示空p-rchild=0;}for(;i=m;i++,p++){p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;}for(i=n+1;i=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;//选出的两个权值最小的结点的双亲就是即将生成的结点HT[s2].parent=i;HT[i].lchild=s1;//即将生成的结点左孩子是s1，右孩子是s2，HT[i].rchild=s2;//因为s1比s2先选，所以s1总是小于等于s2HT[i].weight=HT[s1].weight+HT[s2].weight;//即将生成结点的权值就是两个权值最小的结点的权值之和}if(!(HC=(HuffmanCode)malloc((n+1)*sizeof(char*)))){exit(OVERFLOW);}//ifif(!(cd=(char*)malloc(n*sizeof(char)))){exit(OVERFLOW);}cd[n-1]='\0';for(inti=1;i=n;++i){start=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}//ifelse//叶子结点根结点的右孩子{cd[--start]='1';}//else}if(!(HC[i]=(char*)malloc((n-start)*sizeof(char)))){exit(OVERFLOW);}strcpy(HC[i],&cd[start]);//printf(-叶子节点%d的赫夫曼编码为:%s\n,i,HC[i]);}free(cd);returnOK;}//HuffmanCodingvoidPrintHT(HuffmanTreeHT,intn){intm=2*n-1;printf(\n+-------------------------------------------------------------+\n);printf(|赫夫曼树HT的存储结构|\n);printf(+----------+----------+----------+--------------+-------------+\n);printf(|结点编号|weight|parent|leftchild|rightchild|\n);printf(+----------+----------+----------+--------------+-------------+\n);for(inti=1;i=m;i++){printf(|%4d|%4d|%4d|%4d|%4d|\n,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf(+----------+----------+----------+--------------+-------------+\n);}}for(inti=0;ilen;i++){if(str[i]=='A')a[65]++;elseif(str[i]=='B')a[66]++;elseif(str[i]=='C')a[67]++;elseif(str[i]=='D')a[68]++;elseif(str[i]=='E')a[69]++;elseif(str[i]=='F')a[70]++;elseif(str[i]=='G')a[71]++;elseif(str[i]=='H')a[72]++;elseif(str[i]=='I')a[73]++;elseif(str[i]=='J')a[74]++;elseif(str[i]=='K')a[75]++;elseif(str[i]=='L')a[76]++;elseif(str[i]=='M')a[77]++;elseif(str[i]=='N')a[78]++//部分统计字母代码主程序首先随机输入一篇英文文章，再统计各字母个数，再调用HuffmanCoding(HT,HC,w,n)函数，此函数又会调用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)函数，而此函数又会调用intmin(HuffmanTreeHT,inti)函数，构造完成后便调用PrintHT(HT,n)函数输出赫夫曼树的存储结构。调用调用调用调用输入界面：HuffmanCoding(HT,HC,w,n)voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)intmin(HuffmanTreeHT,inti)Intmain()主函数PrintHT(HT,n)输出界面：4.调试分析(a)调试过程中未设计多种不合理输入的对应输出结果，后加上。(b)算法的时间复杂度为O(n3),StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)函数中的一重for循环调用了select函数，而select函数又调用了min函数，故共有三重for循环，故时间复杂度为O(n3)。(c)通过这次课程设计，让我受益匪浅，使我掌握了二叉树的的存储结构和赫夫曼编码的基本思想。程序中有多处运用了三重循环，这里很多地方可以优化以达到减小时间和空间复杂度。在此次课程设计的最大收获就是让我明白一个道理：无论你做的是多么小的一个程序或软件，都要使用模块化设计，这样使程序实现的功能更清晰明了。5.用户使用说明直接输入一篇英文文章即可。6.测试结果a.正确输入：ThereisnodoubtthatInternethaschangedourlifegreatlyItmakestheworldsmallerPeoplecangettoknowtheworldinashorttimeandmakefriendsfromallovertheworldWhileontheotherhandthemuchattentionontheInternetisolatesthedistanceandreducesfacetofacecommunicationManyyearsagobeforethepopularityofcomputerpeoplegottoknowtheworldbylisteningtotheradioorreadingnewspaperButnowadayspeoplecanjustreadtheinstantnewsontheInternetandgetthefirsthandinformationimmediatelyThefastwaytomasterinformationmakesthemfeelkeepingintouchwiththeworldTheworldseemssoneartothem结果：‘b．错误的输入7.测试情况：测试情况如设计的一致，首先输出各字母及在文章出现的次数，再输出各字母的赫夫曼编码，最后输出ASCLL码与赫夫曼编码的差异。附程序源代码：#includestdio.h#includestdlib.h#includestring.h#defineOVERFLOW-2#defineOK1#defineERROR0typedefintStatus;typedefstruct{unsignedintweight;//权值unsignedintparent,lchild,rchild;//双亲，左孩子，右孩子}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表intmin(HuffmanTreeHT,inti){intj,flag=1;unsignedintk=10000;for(j=1;j=i;j++){if(HT[j].weightk&&HT[j].parent==0){k=HT[j].weight,flag=j;}//if}HT[flag].parent=1;returnflag;}voidSelect(HuffmanTreeHT,inti,i