实习报告题目：哈弗曼编译码器班级：电信系通信工程0902班完成日期：2010.11一、需求分析1、编写哈弗曼编译码器，其主要功能有（1）I：初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。
（2）E：编码（Encoding）。
利用已建好的哈夫曼树），对从终端输入的正文进行编码，然后从终端输出。
（3）D：译码（Decoding )。
利用已建好的哈夫曼树将从终端输入的代码进行译码，结果从终端输出。
（4）P：印哈夫曼树（Print）。
将已编码的的哈夫曼树显示在终端上，同时将此字符形式的哈夫曼树。
2、测试数据：输入的字符={a， b， c， d， e}其对应的权值={5，29，7，8，14}二、概要设计1、二哈弗曼树的抽象数据类型定义为：ADT HuffmanTree{数据对象D:D是具有相同性质的数据元素的集合数据关系R：若D=Φ，则R= Φ，哈弗曼树为空若D≠Φ，则R= {H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱（2）若D-{root}≠Φ，则存在D-{root}={Dl，Dr}。
且Dl∩Dr=Φ（3）若Dl≠Φ，则Dl中存在唯一的数据元素Xl，<root, Xl>属于H，且存在Dl上的关系H1属于H。
若Dr≠Φ，则Dr中存在唯一的数据元素Xr，<root, X>属于H，且存在Dr上的关系Hr属于HH={<root, Xl>，<root, X>，Hl，Hr}；（4）（Dl，{Hl}）是一棵符合本定义的哈弗曼树，称为根的左子树。
（Dr，{Hr}）是一棵符合本定义的哈弗曼树，称为根的右子树。
基本操作：HuffmanCoding（&HT, &HC, &sum)操作结果：建立哈弗曼树并进行编码将编码存放在HC中，并返回字符的个数。
Encoding(HT, HC, sum)操作结果：利用已建立的哈弗曼树对字符进行编码Decoding(HuffmanTree HT,HuffmanCode HC,int sum)操作结果：对输入的密码进行翻译Print(HT, HC, sum)操作结果：打印建立好的哈弗曼树}ADT HuffmanTree三、详细设计（1）哈弗曼树每个节点的定义：typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;char elemt[20];}HTNode,*HuffmanTree;（2）定义指向哈弗曼树的指针，用于动态分配空间typedef char **HuffmanCode;（3）哈弗曼树的基本操作Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ //建立哈弗曼树，求出哈弗曼编码if (n<=1)return;m=2*n-1; //n 个叶子的HuffmanTree共有2n-1个结点HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=0; i<n; ++i,++p,++w)*p={*w,0,0,0};//给前n个单元初始化for(；i<=m; ++i,++p)*p ={0,0,0,0}; //从叶子之后的存储单元清零for(i=n+1;i<=m; ++i){ //建Huffman树(从n个叶子后开始存内结点) Select(HT, i-1, s1, s2);//选择parent为0且weight最小的两个结点，HT[s1].parent=i; HT[s2].parent=i; //给双亲分量赋值HT[i].lchild=s1; HT[i].rchild=s2; //给合并后的内结点赋孩子值HT[i].weight=HT[s1].weight+ HT[s2].weight;} //以上建立了哈弗曼树，以下求哈弗曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量（一维数组）cd=(char*) malloc(n*sizeof(char)); //分配求编码的临时最长空间cd[n-1]=“\0”; //编码结束符（从cd[0]~cd[n-1]为合法空间）for(i=1;i<=n;++i) //逐个字符求Huffman编码{start=n-1; //编码结束符位置for(c=i,f=HT[i].parent; f!=0; c=f, f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c) cd[--start]=“0”;else cd[--start]=“1”;HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间，并以数组形式存放各码串指针strcpy(HC[i],&cd[start]); //从cd复制编码串到HC所指空间}free(cd); //释放临时空间}//HuffmanCodingfor(i=0; i<n; ++i){start=n-1; //编码结束符位置for(c=i, f=HT[i].parent;f!=0;c=f, f=HT[f].parent) {If(HT[f].lchild==c) cd[--start]=“0”;else cd[--start]=“1”;} / /从叶子到根逆向求编码}// HuffmanCodingVoid Encoding(HuffmanTree HT,HuffmanCode HC,int sum) //利用已经建立的哈弗曼树对输入的字符进行哈弗曼编码{for(int i=0;a[i]!='\0';i++)//依次判断字符的对应的哈弗曼编码{for(int n=0;HT[n].elemt[0];n++)//查找a[i]在哈弗曼树中的位置{strcpy(p,HC[n]);p=p+strlen(HC[n]);break;//把编码复制接到code后}}i=0;printf("得到的编码是：\n");while(code[i]!='\0') //输出字符对应的哈弗曼编码{printf("%c",code[i++]);}}// EncodingVoid Decoding(HuffmanTree HT,HuffmanCode HC,int sum) //译码{while(code1[i]!='\0'){if(code1[i]=='0') b=HT[b].lchild;//当遇到0时指向哈弗曼树的左子树else if(code1[i]=='1') b=HT[b].rchild;//当遇到1时指向哈弗曼树的右子树}if(HT[b].lchild==0&&HT[b].rchild==0)//当左右子树均为空时表明已找到对应的字符{a1[n++]=HT[b].elemt[0];b=2*sum-2;//将对应的字符放在数组a1中并重新设置b的值继续翻译 }i++;}// DecodingVoid Print(HuffmanTree HT,HuffmanCode HC,int sum)//打印哈弗曼树{for(int i=0;i<2*sum-1;i++)//从首元素开始，逐个输入哈弗曼树的各项数据{printf("%d%c%d%d%d",i,HT[i].elemt[0],HT[i].parent,HT[i].lch ild,HT[i].rchild);}}// Print四、调试分析1、由于书上有详细的建立哈弗曼树的算法，编码，译码，打印哈弗曼树的算法比较简单，程序的模块比较简单，所以整体的思路比较清晰，但是在将算法，写为C语言的过程中，出现了很多的语法和逻辑上的错误，所以用了很多的时间调试，修改错误。
