数据结构实验三哈夫曼树实验报告

1题目：哈夫曼编/译码器一、题目要求：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.二、概要设计：数据结构：typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*编码结构体*/typedefstruct{intweight;intparent;intlchild;intrchild;charvalue;}HNode;/*结点结构体*/函数：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn)作用：构造一个哈夫曼树，并循环构建intmain()作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译三、详细设计：哈夫曼树的建立：voidDEMONHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼树数组HuffNode[]中的结点*/while(in){HuffNode[i].weight=0;//权值2HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;scanf(%c,&x);scanf(%c,&HuffNode[i].value);//实际值，可根据情况替换为字母i++;}/*输入n个叶子结点的权值*/scanf(%c,&x);for(i=0;in;i++){scanf(%d,&HuffNode[i].weight);}for(i=n;i2*n-1;i++){HuffNode[i].weight=0;//权值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].value=i;}/*循环构造Huffman树*/for(i=0;in-1;i++){m1=m2=MAXQZ;//m1、m2中存放两个无父结点且结点权值最小的两个结点x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树for(j=0;jn+i;j++){if(HuffNode[j].weightm1&&HuffNode[j].parent==-1){m2=m1;//m1中是最小x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weightm2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}3}/*endfor*//*设置找到的两个子结点x1、x2的父结点信息*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}叶子节点的哈夫曼编码的保存：for(j=cd.start+1;jn;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;主函数展示：intmain(){HNodeHuffNode[MAXNODE];HCodeTypeHuffCode[MAXLEAF],cd;inti,j,c,p,n,k=0;charwen[100];charz;scanf(%d,&n);HuffmanTree(HuffNode,n);for(i=0;in;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父结点存在*/{if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;/*求编码的低一位*/c=p;p=HuffNode[c].parent;/*设置下一循环条件*/}/*endwhile*/4for(j=cd.start+1;jn;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}/*endfor*/z=getchar();z=getchar();for(;z!='\n';z=getchar()){wen[k++]=z;for(i=0;in;i++){if(z==HuffNode[i].value){for(j=HuffCode[i].start+1;jn;j++)printf(%d,HuffCode[i].bit[j]);break;}else;}}printf(\n);for(i=0;ik;i++){printf(%c,wen[i]);}printf(\n);return0;}四、调试分析与心得体会：虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。首先就是哈弗曼树忘记了初始的赋值，导致最后出现了问题。这样的错误还是很容易解决，但是之后就出现了WA的情况。在同学的帮助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的问题，在debug的过程中会耗去大量的时间，这是要注意的。五、用户操作说明：输入表示字符集大小为n（n=100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）；输入串长小于或等于100的目标报文。5六、运行结果：附带自己的算法完成的结果图，可以通过PrtSc和图片编辑器获得；6七、附录：#includestdio.h#includestdlib.h#defineMAXBIT100#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1#defineMAXQZ10000//权值typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*编码结构体*/7typedefstruct{intweight;intparent;intlchild;intrchild;charvalue;}HNode;/*结点结构体*//*构造一颗哈夫曼树*/voidHuffmanTree(HNodeHuffNode[MAXNODE],intn){inti=0,j,m1,m2,x1,x2;charx;/*初始化存放哈夫曼树数组HuffNode[]中的结点*/while(in){HuffNode[i].weight=0;//权值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;scanf(%c,&x);scanf(%c,&HuffNode[i].value);//实际值，可根据情况替换为字母i++;}/*输入n个叶子结点的权值*/scanf(%c,&x);i=0;while(in){scanf(%d,&HuffNode[i].weight);i++;}for(i=n;i2*n-1;i++){HuffNode[i].weight=0;//权值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].value=i;}8/*循环构造Huffman树*/for(i=0;in-1;i++){m1=m2=MAXQZ;//m1、m2中存放两个无父结点且结点权值最小的两个结点x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树for(j=0;jn+i;j++){if(HuffNode[j].weightm1&&HuffNode[j].parent==-1){m2=m1;//m1中是最小x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weightm2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*endfor*//*设置找到的两个子结点x1、x2的父结点信息*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}intmain(){HNodeHuffNode[MAXNODE];/*定义一个结点结构体数组*/HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/inti,j,c,p,n,k=0;charwen[100];charz;scanf(%d,&n);HuffmanTree(HuffNode,n);9for(i=0;in;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父结点存在*/{if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;/*求编码的低一位*/c=p;p=HuffNode[c].parent;/*设置下一循环条件*/}/*endwhile*//*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/for(j=cd.start+1;jn;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}/*endfor*/z=getchar();z=getchar();for(;z!='\n';z=getchar()){wen[k++]=z;for(i=0;in;i++){if(z==HuffNode[i].value){for(j=HuffCode[i].start+1;jn;j++)printf(%d,HuffCode[i].bit[j]);break;}else;}}printf(\n);i=0;while(ik){printf(%c,wen[i]);10i++;}printf(\n);return0;}11上机实习要求：1、认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分；2、独立完成老师布置的题目，上机完成程序并调试正确，课后完成实验报告的编写，将上机程序和实验报告打包后交给辅导老师评定分数，实验报告要求和评分标准见后面；3、提倡创新，可对课本上提供的算法进行改进；4、上机程序必须在程序中提供足够的注释，详细为好。5、实验报告不用写出算法，只要写出对课程设计的见解，如对某一算法的改进思想，算法设计思想，调试算法过程中出现的问题及改进方法，调试程序的体会等。只要是自己编程和调试就会写出相应的报告。考核标准1、机试程序和结果、设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。机试成绩占总成绩60%，设计报告占40%。2、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视上机结果最多60分，抄袭者按0分计，若找不到原创，都按0分计。所以原创同学注意，我们的检查专门针对抄袭情况，一旦发现将严肃处理！！！