数据结构哈弗曼编译码———c语言

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构课程设计报告课设题目：哈夫曼（Huffman）编/译码器专业：计算机科学与技术（嵌入式）班级：计算机143姓名：王龙完成日期：2016年1月21日指导教师：魏本昌1、题目的内容及要求【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工 信道（即可以双向传输信息的信道） ，每端都需要一个完整的编 / 译码系统。试为这样的信息收发站写一个 哈夫曼码的编 / 译码系统。

2、【任务要求】 一个完整的系统应具有以下功能：1）I:初始化（Initialization ）。从终端读入字符集大小 n,以及n个字符和n个权值，建立哈夫曼树， 并将它存于文件 hfmTree 中。2）E：编码（Encoding ）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件 CodeFile中。3）D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile中的代码进行译码，结果存入文件 TextFile 中。4）P:印代码文件（Print ）。将文件CodeFile以紧凑格式显示在终端上，每行 5

3、0个代码。同时将此 字符形式的编码文件写入文件 CodePrin 中。5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。2、需求分析利用哈夫曼树（Huffman）编/译码（一）、初始化哈夫曼树（二）、建立哈夫曼树（三）、对哈夫曼树进行编码（四）、输出对应字符的编码（五）、译码过程（六）、输出哈夫曼树3、概要设计（包括选择什么数据结构？数据结构采用哪种存储方式？选择 的原因？设计哪些操作？这些操作之间的调用关系等等）选择了线性数据结构, 数据结构采用顺序存储方式, 选择的原因

4、： 结构简单, 可以方便调用任何一个 数组,无需为结点间的逻辑关系而增加额外的空间。设计初始化哈夫曼树、编码、译码、输出哈夫曼 树等操作。这些操作之间的调用关系：通过主函数逐个完成,执行译码、编码、输出前,必须先建立哈夫曼树。4、详细设计(包括数据结构的类型定义，每个操作的算法描述)定义两个结构体变量 HuffNode 和 HuffCodeint HuffmanCteate (HuffNode * ht) 函数：已知有 n 个节点，则哈夫曼树构建需要有 2N-1 个节点，先输入元素个数 n ，然后输入结点值和权重，存 储在 ht 数组的前 n 个数组元素中。 然后将 2n-1 个节点的双亲和左

5、右孩子置0；然后在所有节点中， 选取双亲为0、权重最小的两个节点m1,m2 ;用p1p2表示这两个节点在数组中的位置。将根为 htp1和htp2的两节点合并，成为新节点hti的左右孩子，hti的权重为两个最小权重m1,m2之和；htp1和htp2的双亲指向i;最后一直重复2的步骤，进行n-1次，形成哈夫曼树，当进行 n-1次后，产生n-1个节点，依次放 入 ht 数组中。void Encoding (HuffNode ht, HuffCode hcd, int n) 函数 ：从哈夫曼树的结点 hti出发，通过双亲找到双亲 hti，通过htf的左右孩子，可知 hti是htf的左孩子还 是右孩子，

6、若是左孩子，编码置 0；若是右孩子，编码置 1，编码存放在数组 cdstart 中；然后把 htf 作为 出发点， 重复上面过程， 直到找到根节点。 因为所生产的编码与要求的编码是相反的， 先把编码存入第 n 个 位置，在生产的存入 n-1个位置，重复；用start指向编码在数组 cd中的起始位置，start初始值为n,生产 一个编码后。 start 减一。void Decoding (HuffNode ht, HuffCode hcd, int n) 函数：首先输入电文,存放在 cd 中,以 #号表示结束。然后,将电文和编码比较,如果为 0,转到左孩子,如果 为1，转到右孩子，直到叶节点结束

7、，同时输出叶节点的data。最后，继续重复译码，直到电文结束。void scanf (HuffNode ht, HuffCode hcd, int n) 函数：首先输入需要翻译的译文,存放在 cd 中,以 #号表示结束。然后,将译文和结点值比较,如果为相同,输 出结点值的编码,继续重复翻译,直到译文结束为止。void print(HuffNode ht, HuffCode hcd, int n) 函数： 通过记录每个权重的编码个数,然后通过循环,输出哈夫曼树。void showmenu( ) 函数： 通过 printf( ) 函数显示提示信息。int main () 函数：先定义四个变量、两个

8、结构体数组，通过while ()函数一直循环，通过switch ()函数输入需要执行的项目，然后再所输入的项目中调用相关函数。5、源代码# include # include # include typedef char DataType;# define MAXNUM 50typedef structDataType data;int weight;int parent;int left;int right;HuffNode;typedef structDataType cd MAXNUM;int start;HuffCode;int HuffmanCteate (HuffNode * ht

9、)int i, k, n, m1, m2, p1, p2;printf ( 请输入元素个数： ); scanf (%d, &n);for (i=1; int 结点值： , i); scanf (%c, &hti.data);printf (t 权 重： );scanf (%d, &hti.weight);for (i=1; i=2*n-1; i+)hti.parent = hti.left = hti.right = 0;for (i=n+1; i=(2*n-1); i+)m1 = m2 = 32767;p1 = p2 = 1;for (k=1; k=i-1; k+)if (htk.paren

10、t = 0) if (htk.weight m1) m2 = m1; p2 = p1;m1 = htk.weight; p1 = k;else if (htk.weight m2) m2 = htk.weight ; p2 = k;htp1.parent = i; htp2.parent = i; hti.weight = m1 + m2; hti.left = p1;hti.right = p2;return n;void Encoding (HuffNode ht, HuffCode hcd, int n) HuffCode d;int i, k, f, c;for (i=1; i=n;

11、i+)d.start = n+1;c = i;f = hti.parent;while (f != 0)if (htf.left = c)d.cd-d.start = 0; elsed.cd-d.start = 1;c = f;f = htf.parent;hcdi = d;printf ( 输出哈弗曼编码： n);for (i=1; i=n; i+)printf (%c :, hti.data);for (k=hcdi.start; k=n; k+)printf (%c, hcdi.cdk); printf (n);void Decoding (HuffNode ht, HuffCode h

12、cd, int n)int f, m, k;DataType c, ch200;printf ( 请输入电文( 0 or 1) ,以#为结束标志： n); c = getchar ();k =1;while (c != #)chk = c;c = getchar();k = k + 1; m = k; f = 2 * n - 1;k =1;printf （ 输出哈弗曼译码： n）;while (k m)while (htf.left != 0)if (chk = 0)f = htf.left ;if (chk = 1)f = htf.right ; k+;printf (%c, htf.dat

13、a );f = 2 * n - 1;printf (n);void showmenu()*n);printf ( printf （* 计算机 143 王龙 王牌 冯静 *n）;*n);printf ( printf (n* 欢迎使用本软件 *n);printf (n1 建立哈弗曼树 n);printf (2 编码 n);printf (3 译码 n);printf (4 印哈夫曼树 n);printf (5 译文 n);printf (6 退出系统 nn);printf （ 请输入功能序号（请输入 15 数组 ） :）; void print(HuffNode ht, HuffCode hcd

14、, int n)int i, k, x, y;printf ( 输出哈弗曼树为： n);for (i=1; i=n; i+)x = 0;for (k=hcdi.start; k=n; k+)x+;for (y=0; yx; y+)printf ( );printf (%c, hti.data);printf (n);void scan (HuffNode ht, HuffCode hcd, int n)int f, m, k, i=1;DataType c, ch200;printf ( 请输入译文 ,以 #为结束标志： n); c = getchar ();k =1;while (c !=

15、#)chk = c;c = getchar();k = k + 1;m = k;k =1;printf ( 输出译文译码： n);for (k=1; km; k+)for (i=1; i=n; i+)if (chk = hti.data)for (f=hcdi.start; f=n; f+) printf (%c, hcdi.cdf);printf (n);int main ()int n, select, flag=0, bug = 0; HuffNode ht2 * MAXNUM; HuffCode hcdMAXNUM;while (1)showmenu();scanf (%d, &sel

16、ect); printf (n);if (select != 1 & select != 5 & flag = 0)printf( 请先建立哈弗曼树再选择其他功能！ nn 编码已经完成，按任意键继 续n);getch();system(cls);continue;flag = 1;switch (select)case 1:n = HuffmanCteate (ht);printf(”哈弗曼树已经完成，按任意键继续n);getch();system(cls);break;case 2:Encoding (ht, hcd, n);bug = 1;printf(编码已经完成，按任意键继续n);ge

17、tch();system(cls); break;case 3:Decoding (ht, hcd, n);n);printf( 译码已经完成，按任意键继续 getch();system(cls);break;case 4:if (bug != 1)printf ( 请先编码。 n 按任意键继续！ n); getch();system(cls);break;print (ht, hcd, n);n);printf(”印哈夫曼树已经完成，按任意键继续getch();system(cls);break;case 5:if (bug != 1)printf (请先编码。n按任意键继续！ n);getch();system(cls);break;Scan (ht, hcd, n);printf(译文已经完成，按任意键继续 n);getch();system(cls); break;case 6:exit (0);break;return 0;6、 运行结果及分析图 1 、程序初始化图 2 、建立哈夫曼树图 3、编码图 4、译码图 5 、打印哈夫曼树图6、译文mai n()neingHuffi()译码Dec()odin打印 print)译文sea()7、收获及体会，总结为期两个星期的课设已经结束了，这次课设时间非常紧迫，任务非常艰巨，但我最后还是完成了。课设的内容难度大，其中哈弗曼树理论特