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

---------------------------------作者:_____________-----------------------------日期::_____________数据结构实验三哈夫曼树实验报告题目:哈夫曼编/译码器题目要求:写一个哈夫曼码的编/译码系统,要求能对要传输的报文进行编码和解码。构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为1,:数据结构: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(i<n){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); for(i=0;i<n;i++){scanf("%d",&HuffNode[i].weight);}for(i=n;i<2*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;i<n-1;i++){m1=m2=MAXQZ;//m1、m2中存放两个无父结点且结点权值最小的两个结点x1=x2=0;//找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树for(j=0;j<n+i;j++){if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1){m2=m1;//m1中是最小x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weight<m2&&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;}}叶子节点的哈夫曼编码的保存:for(j=+1;j<n;j++)HuffCode[i].bit[j]=[j];HuffCode[i].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;i<n;i++){=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父结点存在*/{if(HuffNode[p].lchild==c)[]=0;[]=1;--;/*求编码的低一位*/c=p;p=HuffNode[c].parent;/*设置下一循环条件*/}/*endwhile*/for(j=+1;j<n;j++)HuffCode[i].bit[j]=[j];HuffCode[i].st