数据结构赫夫曼编译码器

《数据结构赫夫曼编译码器》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、院系：计算机科学学院专业：计算机科学与技术年级：2008课程名称：学号：姓名：指导教师：2010年6月2日年级 2008班号01 学号专业计算机科学与计术 姓名实验名称哈弗曼编/译码器实验类型设计型综合型创新型√实验目的或要求一个完整的系统应具有以下功能：（1）I:初始化。从终端读入字符集大小n，n个字符和n个权值,建立哈弗曼树,并将它存于文件hfmTree.（2）E:编码。利用已建好的树，对文件ToBeTran中的正文进行编码，然后将结果存入CodeFile中。（3）D:译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P

2、:印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的哈夫曼树写入文件TreePin中。（5）T:印哈弗曼树。将哈夫曼树以直观的方式显示在终端上，同时将此树写入文件TreePrint中。实验原理（算法流程）一．算法流程①建立HuffmanTreevoidHaffmanTree::Haffman(intweight[],HaffmanTreeHT[])a.查找哈夫曼链表中两个权值最小的节点：b.创建哈弗曼树开始初始化哈夫曼链表且有2n-1个节点i=1Iweight=count[i]p=p->nextfor(i=n;i<2*n-1

3、;i++)HT1->Parent=HT2->Parent=pp->LChild=HT1p->RChild=HT2p->weight=HT1->weight+HT2->weight结束②哈夫曼编码和译码voidHaffmanTree::HaffmanCode(HaffmanTreehaffTree[],HaffmanTreeHaffCode[],charch[],strings)开始将字符存入哈夫曼编码结构体数组的字符单元中if(q==q->Parent->LChild)HC[i].code[--HC[i].start]='0'HC[i].code[--HC[i].start]=

4、'1'p=p->nextI=n时结束⑦解码函数：DeCoding(charcode[],HFMTreeHT,charstr[],char[])s开始Root指向根节点P!=rootcode[i]=='0'p=p->LChildp=p->RChildp->LChild==NULL&&p->RChild==NULLs[k++]=str[j]p=root结束二．哈夫曼编码的算法（1）字符集编码的存储结构及其算法描述typedefstruct{charch；//存储字符charbits[n+1]；//存放编码位串}CodeNode；typedefCodeNodeHuffmanCode[

5、n]；voidCharSetHuffmanEncoding(HuffmanTreeT，HuffmanCodeH){//根据哈夫曼树T求哈夫曼编码表Hintc，p，i;//c和p分别指示T中孩子和双亲的位置charcd[n+1]；//临时存放编码intstart；//指示编码在cd中的起始位置cd[n]=''；//编码结束符for(i=0，i=0){//

6、直至上溯到T[c]是树根为止//若T[c]是T[p]的左孩子，则生成代码0；否则生成代码1cd[--start]=(T[p).1child==C)?'0'：'1'；c=p；//继续上溯}strcpy(H[i].bits，&cd[start])；//复制编码位串}//endfor}//CharSetHuffmanEncoding三．文件的编码和解码　有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，若H[i].ch=c，则将字符c转换为H[i].bits中存放的编码串。　对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其

7、过程是：依次读人文件的二进制码，从哈夫曼树的根结点(即T[m-1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发继续译码，直至文件结束。实验结果分析及心得体会测试数据：利用教科书例6-2中的数据调试程序，并设第1到第8个字符为a，b，c，d，e，f，g，h。运行结果图：运行结果分析：通过调试发现该程序满足哈弗曼树，哈弗曼编码与译码的基本要求，满足课程设计任务的基本功能与要求。在以后的学习中希望能将程序进一步优化，