哈夫曼编码报告.doc

聿实验项目::肇利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(解码)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。:肂1)初始化(Initialzation)。读入字符及每个字符的权值,建立哈夫曼树HuffTree;腿2)编码(EnCoding)。用已建好的哈夫曼树,对输入的文本进行编码形成报文,将报文显示出来;蒅3)译码(Decoding)。利用已建好的哈夫曼树,对输入的代码进行解码形成原文,并将结果显示;芆4)输出(Output):输出出现的字符以及各字符出现的频度(或概率);输出各个字符的编码,输出代码译出的原文;:艿理解哈夫曼树的特征及其应用;在对哈夫曼树进行理解的基础上,构造哈夫曼树,并用构造的哈夫曼树进行编码和译码;通过该实验,使学生对数据结构的应用有更深层次的理解。:学院提供公共机房,1台/学生微型计算机。(含实验代码)羁第1次:完成程序的主框架设计,进行调试,验证其正确性;荿第2次:详细设计,进行调试,验证其正确性;芆第3次:进行整体调试,运行程序,对运行结果进行分析,完成实验报告。莅#include<>蝿#include<>葿#include<>蚇#defineMAXWORD100袃typedefstruct螂{unsignedintweight;chardata;蕿unsignedintparent,llchild,rrchild;袄}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树薅typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表薁typedefstructtnode蚈{charch;//字符芅intcount;//出现次数肃structtnode*lchild,*rchild;芀}BTree,*BT;螈inta=0,b=0;ints[MAXWORD];charstr[MAXWORD];蚆voidmain()螅{intn;inti=0;莃HuffmanTreeHT;HuffmanCodeHC;螈voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn);肇voidDispHCode(HuffmanTreeHT,HuffmanCodeHC,intn);膃voidCreatree(BT&p,charc);//Creatree()和InOrderTraverse()肂voidInOrderTraverse(BTp);//利用二叉树统计出现的字符及个数袈voidTTranChar(HuffmanTreeHT,HuffmanCodeHC,intn);蒈voidTran(HuffmanTreeHT,intn);袅printf("请输入要用几种字符:");袁scanf("%d",&n);羈BTroot=NULL;薅printf("\n");莂printf("请输入字符串:\n");蚀scanf("%s",str);肈while(str[i]!='\0')羅{Creatree(root,str[i]);i++;}肄printf("字符及出现次数:\n");蚂InOrderTraverse(root);膈printf("\n");莆HuffmanCoding(HT,HC,n);薂DispHCode(HT,HC,n);蒁Tran(HT,n);芈TTranChar(HT,HC,n);螇}芄voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn)膀{//w放n个权值,构造赫夫曼树HT,n个字符编码HC芇voidselect(HuffmanTreet,inti,int&s1,int&s2);膈intm,i,s1,s2,start;char*cd;unsignedc,f;蚂HuffmanTreep;芃if(n<=1)return;莇m=2*n-1;莅HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));蒄for(p=HT+1,i=1;i<=n;++i,++p)羂{(*p).parent=0;蒇(*p).llchild=0;螆(*p).rrchild=0;膆}螁for(p=HT+1,i=0;i<n;++i,++p)薇{(*p).data=str[i];***(*p).weight=s[i];薄}薀for(;i<=m;