数据结构哈弗曼编译码———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以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的

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

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

5、；用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的左孩子还是右孩子，若是左孩子，编码置0；若是右孩子，编码置1，编码存放在数组cdstart中；然后把htf作为出

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

7、int n) 函数：首先输入需要翻译的译文，存放在cd中，以#号表示结束。然后，将译文和结点值比较，如果为相同，输出结点值的编码，继续重复翻译，直到译文结束为止。void print(HuffNode ht, HuffCode hcd, int n) 函数：通过记录每个权重的编码个数，然后通过循环，输出哈夫曼树。void showmenu( )函数：通过printf( )函数显示提示信息。int main () 函数：先定义四个变量、两个结构体数组，通过while ( )函数一直循环，通过switch（）函数输入需要执行的项目，然后再所输入的项目中调用相关函数。5、 源代码# include

8、<stdio.h># include <stdlib.h># include<conio.h>typedef char DataType;# define MAXNUM 50typedef struct DataType data;int weight;int parent;int left;int right;HuffNode;typedef structDataType cd MAXNUM;int start;HuffCode;int HuffmanCteate (HuffNode * ht)int i, k, n, m1, m2, p1, p2;pri

9、ntf ("请输入元素个数："); scanf ("%d", &n); for (i=1; i<=n; i+) getchar (); printf ("第%d个元素的=>nt结点值：", i);scanf ("%c", &hti.data); printf ("t 权 重：");scanf ("%d", &hti.weight);for (i=1; i<=2*n-1; i+) hti.parent = hti.left = hti.

10、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.parent = 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.

11、right = p2;return n;void Encoding (HuffNode ht, HuffCode hcd, int n)HuffCode d;int i, k, f, c;for (i=1; i<=n; 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"

12、);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 hcd, int n) int f, m, k;DataType c, ch200;printf ("请输入电文（0 or 1）,以#为结束标志：n");c = getchar ();k =1;while

13、(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.data );f = 2 * n - 1;printf ("n");void sho

14、wmenu() printf ("*n");printf ("* 计算机143 王龙 王牌 冯静 *n");printf ("*n");printf ("n* 欢迎使用本软件 *n");printf ("n1-建立哈弗曼树n");printf ("2-编码n");printf ("3-译码n");printf ("4-印哈夫曼树n");printf ("5-译文n");printf ("6-退出系统nn&q

15、uot;);printf ("请输入功能序号（请输入15数组 ）:");void print(HuffNode ht, HuffCode hcd, 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; y<x; y+)printf (" "); printf ("%c", hti.data);printf ("n"

16、;); 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 != '#') chk = c;c = getchar();k = k + 1;m = k;k =1;printf ("输出译文译码：n");for (k=1; k<m; k+)for (i=1; i<=n; i+)if (chk = hti.data

17、)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", &select);printf ("n");if (select != 1 && select != 5 &&

18、; 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&

19、quot;);getch();system("cls");break;case 3:Decoding (ht, hcd, n);printf("译码已经完成，按任意键继续n");getch();system("cls");break;case 4:if (bug != 1)printf ("请先编码。n按任意键继续！n");getch();system("cls");break;print (ht, hcd, n);printf("印哈夫曼树已经完成，按任意键继续n");getch();system("cls");break;case 5:if (bug != 1)printf ("请先编码。n按任意键继续！n&qu