数据结构赫夫曼编译码器

《数据结构赫夫曼编译码器》由会员分享，可在线阅读，更多相关《数据结构赫夫曼编译码器（18页珍藏版）》请在金锄头文库上搜索。

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

2、CodeFile 中的代码进行译码，结果存入文件 TextFile 中。 （4）P:印代码文件。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时，将此 字符形式的哈夫曼树写入文件 TreePin 中。 （5）T:印哈弗曼树。将哈夫曼树以直观的方式显示在终端上，同时将此树写入文件 TreePrint 中。实 验 原 理 （ 算 法 流 程 ）一算法流程一算法流程建立建立 HuffmanTreeHuffmanTreevoid HaffmanTree:Haffman(int weight,HaffmanTree HT)a.查找哈夫曼链表中两个权值最小的节点： b.创建哈弗曼

3、树开始初始化哈夫曼链表 且有 2n-1 个节点i=1Iweight=counti p=p-nextfor(i=n;iParent=HT2-Parent=p p-LChild=HT1 p-RChild=HT2 p-weight=HT1- weight+HT2-weight结束哈夫曼编码和译码哈夫曼编码和译码voidvoid HaffmanTree:HaffmanCode(HaffmanTreeHaffmanTree:HaffmanCode(HaffmanTree haffTree,haffTree, HaffmanTreeHaffmanTree HaffCode,charHaffCode,cha

4、r ch,stringch,string s)s)开始将字符存入哈夫曼 编码结构体数组的 字符单元中if(q=q-Parent- LChild)HCi.code- HCi.start=0HCi.code- HCi.start=1p=p-nextI=n 时结束解码函数：DeCoding(char code,HFMTree HT,char str,char) s开始 Root 指向根节点P!=rootcodei=0p=p-LChildp=p-RChildp- LChild=NULL/c 和 p 分别指示 T 中孩子和双亲的位置 char cdn+1； /临时存放编码 int start； /指示编

5、码在 cd 中的起始位置 cdn=0； /编码结束符 for(i=0，i=0)/直至上溯到 Tc是树根为止 /若 Tc是 Tp的左孩子，则生成代码 0；否则生成代码 1 cd-start=(Tp).1child=C)?0：1； c=p； /继续上溯 strcpy(Hi.bits，typedef struct int weight; /权值int parent,lchild,rchild; HTNode,* HuffmanTree; /动态分配数组存储赫夫曼树 typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表 /-全局变量- HuffmanTree HT; /

6、w 存放 n 个字符的权值(均0),构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编码 HC. HuffmanCode HC; int *w,n,i,j; char *z; int flag=0; int numb=0; / -求赫夫曼编码- int min(HuffmanTree t,int i) / 函数 void select()调用int j,flag;int k=UINT_MAX; / 取 k 为不小于可能的值for(j=1;js2) j=s1;s1=s2;s2=j; / -算法 6.12- void HuffmanCoding(HuffmanTree int c,f;Huffman

7、Tree p;char *cd;if(nweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iparent=0;for(i=n+1;inum;n=num;w=(int*)malloc(n*sizeof(int);z=(char*)malloc(n*sizeof(char);coutnum2;*(w+i)=num2; HuffmanCoding(HT,HC,w,n); /开始构造对应的赫夫曼树及这 n 个字符的赫 夫曼编码 /-打印编码-coutn)coutrchild,HT);coutweightweight);coprint(HT+start-lc

8、hild,HT);numb-;fclose(TreePrint); void Tree_printing(HuffmanTree HT,int w) HuffmanTree p;p=HT+w;coutchoice;switch(choice)case i: Initialization(); break;case w: InputCode(); break;case e: Encoding(); break;case d: Decoding(); break;case p: Code_printing();break;case t: Tree_printing(HT,2*n-1);break;case q: break;default: cout“input error“endl;free(z);free(w);free(HT);