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

HUFFMAN树及编码需求分析随机输入一篇英文文章(或读一个TXT文件)，生成并显示HUFFMAN树，输出每个字母的HUFFMAN编码，判断ASCII编码与HUFFMAN编码对本篇报文长度节省效果。输入的形式为键盘随机输入，输入的字符串长度在10000以内；输出HUFFMAN树的存储结构；程序功能为输入英文文章中每个字母的HUFFMAN编码，以及与ASCLL码编码长度的比较结果；测试数据：正确的输入一篇英文文章，会输出各个字母的HUFFMAN编码。错误的输入即其输出输入错误。概要设计首先统计英文文章中各个字母的个数作为权值，再统计出现的字母的个数，以决定所构造赫夫曼树的节点个数，之后便开始构造赫夫曼树，再构造每个节点的哈夫曼编码。所设计的抽象数据类型如下：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)输出赫夫曼树的存储结构。详细设计intmin(HuffmanTreeHT,inti){intj,flag=1;unsignedintk=10000;for(j=1;j<=i;j++){if(HT[j].weight<k&&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(s1>s2){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("->待构造的赫夫曼树共有2X%d-1=%d个结点\n",n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申请赫夫曼树结点占用的内存空间,0号单元不用{exit(OVERFLOW);}//if一 printf("->赫夫曼树共分配了％d个结点空间，其中包含一个不用的0号单元\叶,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;i<len;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,再函数，此函数又会调用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)函数，而此函数又会调用intmin(HuffmanTreeHT,inti)函数，构造完成后便调用PrintHT(HT,n)函数输出赫夫曼树的存储结构。Intmain()主函数调用HuffmanCoding(HT,HC,w,n)调用voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)调用”intmin(HuffmanTreeHT,inti)PrintHT(HT,n)点PrintHT(HT,n)点调用输入界面:请随札输入英文文命

ITC:\Users\ZHANG\Pegkto|p网g绪构课程设计湍夫是风编码.exeip随|FL输入英父文K；：IhereisnodoubtthatInternethaschangedonrlifegreatlyltmake;asr..or71imeatidiDiakefrierdsfroma11overtAewor1dWhi1eon;r..eotherhandtherauchattenTi(facetofacecoounmiicationManyyearsagobe:orethepopulari^yofccunputerpeaplegottakispaperButnowadayspeaplecanjustreadtheinstantnewsontrieInternetandgett/e^firsth;二zonnatiotinakesthemfee1keepingintonchwiththewor1dTheworidseemssoneartothem输出界面:Cl口\廿缶「sWHANC3\D巳skt^p檄拒结构课程设赫壬慎御缉回一以巳-＞待构造的赫夫曼树共有2X29-1=57个结-＞赫夫曼树共分配了58个结点空间,其中包含-个不用的0号单元-＞您建立的赫夫曼列对应的杯夫昼编码如下］10111100001110101011110011011110101011111010111101111000111011000101101010000110011110011000101011111100111001101110110111011110001110100000010101110nmm ■JC:\Users\ZHANG\De新。p濒据结构课程设计场5夫昌榭犒砖exe54 172 56 49 505521957515256315575354575340□556交章用赫夫曼编码.共需169位1进制数文章用ASCLL玛编玛共需4272位故利用ASCLL码编码出要的位数是林夫曼编码的有一墨倍调试分析调试过程中未设计多种不合理输入的对应输出结果，后加上。算法的时间复杂度为O(n3),StatusHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)函数中的一重for循环调用了select函数，而select函数又调用了min函数，故共有三重for循环，故时间复杂度为O(n3)。通过这次课程设计，让我受益匪浅，使我掌握了二叉树的的存储结构和赫夫曼编码的基本思想。程序中有多处运用了三重循环，这里很多地方可以优化以达到减小时间和空间复杂度。在此次课程设计的最大收获就是让我明白一个道理：无论你做的是多么小的一个程序或软件，都要使用模块化设计，这样使程序实现的功能更清晰明了。用户使用说明直接输入一篇英文文章即可。测试结果a.正确输入：ThereisnodoubtthatInternethaschangedourlifegreatlyItmakestheworldsmallerPeoplecangettoknowtheworldinashorttimeandmakefriendsfromallovertheworldWhileontheotherhandthemuchattentionontheInternetisolatesthedistanceandreducesfacetofacecommunicationManyyearsagobeforethepopularityofcomputerpeoplegottoknowtheworldbylisteningtotheradioorreadingnewspaperButnowadayspeoplecanjustreadtheinstantnewsontheInternetandgetthefirsthandinformationimmediatelyThefastwaytomasterinformationmakesthemfeelkeepingintouchwiththeworldTheworldseemssoneartothem结果:UC:\LHer氾HANG\D已sktop俊扼结构课程设计海夫旻挪-)赫夫曼树共分配了5&个结点空间，其中包含-〉您建立的赫夫曼树对应的赫夫曼编码如S：1011110000111010101111001101111010101111101011110111100011101100010110101000011001111001100010101111110011100110111011011101111000111010000001010111010111111100111b.错误的输入BC^UsersVHAN小盹如叩典堤融课程设计遍夫旻瓣码.exe请I灼"输入蛆文文直：12222222222222641234152985146656314566666656184641651498461846814高入错误!7.测试情况：测试情况如设计的一致，首先输出各字母及在文章出现的次数，再输出各字母的赫夫曼编码，最后输出ASCLL码与赫夫曼编码的差异。TOC\o"1-5"\h\z55 | 219 | 57 | 51 | 52 1 1 十I 56 | 315 | 57 | 53 | 54 |H F —rl 1 —rl-I 57 | 534 | 0 | 55 | 56 |T 1 1 1 —F文章用'赫夫曼编码共需L69位:过制数文章用ASCLL码嘛码共启2地位故利IJASCLL码编码芯要的位数是林夫曼编码的25.找倍Processreturned0(0x0)execuTiontime:14.728sPressanykeytocontinue.附程序源代码：#include<stdio.h>#include<stdlib.h>#include<string.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].weight<k&&HT[j].parent==0)(k=HT[j].weight,flag=j;}//if}1；HT[flag].parent=returnflag;1；}voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)(intj;s1=min(HT,i);s2=min(HT,i);if(s1>s2)(j=s1;s1=s2;s2=j;}}voidPrintHT(HuffmanTreeHT,intn)(intm=2*n—1;printf("\n+ +\n〃)；printf("| 赫夫曼树HT的存储结构l\n〃)；printf("+ + + + + —+\n〃);printf("|结点编号|weight|parent|leftchildrightchild|\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");}}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("->待构造的赫夫曼树共有2X%d-1=%d个结点\n”,n,m);if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))//申请赫夫曼树结点占用的内存空间,0号单元不用(exit(OVERFLOW);}//ifprintf(〃->赫夫曼树共分配了％d个结点空间，其中包含一个不用的0号单元\/,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;//因为si比s2先选，所以si总是小于等于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;}//HuffmanCodingintmain()(HuffmanTreeHT;HuffmanCodeHC;int*w;charstr[10005];inta[150],b[60];memset(a,0,sizeof(int)*150);printf("请随机输入英文文章：")；scanf("%s",str);intlen=strlen(str);for(inti=0;i<len;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]++;elseif(str[i]=='O')a[79]++;elseif(str[i]=='P')a[80]++;elseif(str[i]=='Q')a[81]++;elseif(str[i]=='R')a[82]++;elseif(str[i]=='S')a[83]++;elseif(str[i]=='T')a[84]++;elseif(str[i]=='U')a[85]++;elseif(str[i]=='V')a[86]++;elseif(str[i]=='W')a[87]++;elseif(str[i]=='X')a[88]++;elseif(str[i]=='Y')a[89]++;elseif(str[i]=='Z')a[90]++;elseif(str[i]=='a')a[97]++;elseif(str[i]=='b')a[98]++;elseif(str[i]=='c')a[99]++;elseif(str[i]=='d')a[100]++;elseif(str[i]=='e')a[101]++;elseif(str[i]=='f')a[102]++;elseif(str[i]=='g')a[103]++;elseif(str[i]=='h')a[104]++;elseif(str[i]==5i)a[105]++;elseif(str[i]=='j')a[106]++;elseif(str[i]=='k')a[107]++;elseif(str[i]==T')a[108]++;elseif(str[i]==