当前位置：文档之家 › 数据结构课程设计哈弗曼编码译码

数据结构课程设计哈弗曼编码译码

  • 格式：doc
  • 大小：61.00 KB
  • 文档页数：8

哈夫曼编码译码一、需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。

哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串二、其主要流程图：三、设计要求：（1）哈夫曼树的建立；（2）哈夫曼编码的生成（3）编码文件的译码四、总结：通过这次的课程设计了解课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。

因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。

回顾起此次课程设计，至今我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。

在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体……通过这次课程设计之后，一定把以前所学过的知识重新温故。

我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！五、源程序：#include <stdio.h>#include <stdlib.h> //要用system函数要调用的头文件#include<conio.h> //用getch()要调用的头文件#include <string.h>#define N 50 //义用N表示50叶节点数#define M 2*N-1 //用M表示节点总数当叶节点数位n时总节点数为2n-1 #define MAXSIZE 100typedef struct{char data; //结点值int weight; //权值int parent; //双亲结点int lchild; //左孩子结点int rchild; //右孩子结点}HTNode;typedef struct{char cd[N]; //存放哈夫曼码int start; //从start开始读cd中的哈夫曼码}HCode;void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n{int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1 for (i=n;i<2*n-1;i++) //构造哈夫曼树{min1=min2=32767; //int的范围是-32768-32767lnode=rnode=-1; //lnode和rnode记录最小权值的两个结点位置for (k=0;k<=i-1;k++){if (ht[k].parent==-1) //只在尚未构造二叉树的结点中查找{if (ht[k].weight<min1) //若权值小于最小的左节点的权值{min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}else if (ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i; //两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight; //两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode; //父节点的左节点和右节点}}void CreateHCode(HTNode ht[],HCode hcd[],int n){int i,f,c;HCode hc;for (i=0;i<n;i++) //根据哈夫曼树求哈夫曼编码{hc.start=n;c=i;f=ht[i].parent;while (f!=-1) //循序直到树根结点结束循环{if (ht[f].lchild==c) //处理左孩子结点hc.cd[hc.start--]='0';else //处理右孩子结点hc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++; //start指向哈夫曼编码hc.cd[]中最开始字符hcd[i]=hc;}}void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表{int i,k;printf(" 输出哈夫曼编码:\n");for (i=0;i<n;i++) //输出data中的所有数据，即A-Z {printf(" %c:\t",ht[i].data);for (k=hcd[i].start;k<=n;k++) //输出所有data中数据的编码{printf("%c",hcd[i].cd[k]);}printf("\n");}}void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数{char string[MAXSIZE];int i,j,k;scanf("%s",string); //把要进行编码的字符串存入string数组中printf("\n输出编码结果:\n");for (i=0;string[i]!='#';i++) //#为终止标志{for (j=0;j<n;j++){if(string[i]==ht[j].data) //循环查找与输入字符相同的编号，相同的就输出这个字符的编码{for (k=hcd[j].start;k<=n;k++){printf("%c",hcd[j].cd[k]);}break; //输出完成后跳出当前for循环}}}}void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数{char code[MAXSIZE];int i,j,l,k,m,x;scanf("%s",code); //把要进行译码的字符串存入code数组中while(code[0]!='#')for (i=0;i<n;i++){m=0; //m为想同编码个数的计数器for (k=hcd[i].start,j=0;k<=n;k++,j++) //j为记录所存储这个字符的编码个数{if(code[j]==hcd[i].cd[k]) //当有相同编码时m值加1m++;}if(m==j) //当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据{printf("%c",ht[i].data);for(x=0;code[x-1]!='#';x++) //把已经使用过的code数组里的字符串删除{code[x]=code[x+j];}}}}void main(){int n=26,i;char orz,back,flag=1;char str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; //初始化int fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16}; //初始化HTNode ht[M]; //建立结构体HCode hcd[N]; //建立结构体for (i=0;i<n;i++) //把初始化的数据存入ht结构体中{ht[i].data=str[i];ht[i].weight=fnum[i];}while (flag) //菜单函数，当flag为0时跳出循环{printf("\n");printf(" **************************************");printf("\n ** A---------------显示编码**");printf("\n ** B---------------进行编码**");printf("\n ** C---------------进行译码**");printf("\n ** D---------------退出**\n");printf(" ****************************************");printf("\n");printf(" 请输入选择的编号:");scanf("%c",&orz);switch(orz){case 'a':case 'A':system("cls"); //清屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'b':case 'B':system("cls");printf("请输入要进行编码的字符串(以#结束):\n");editHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'c':case 'C':system("cls");DispHCode(ht,hcd,n);printf("请输入编码(以#结束):\n");deHCode(ht,hcd,n);printf("\n按任意键返回...");getch();system("cls");break;case 'd':case 'D':flag=0;break;default:system("cls");}}}。

合集下载

数据结构设计课程设计-哈夫曼编译码系统的设计与实现

数据结构设计课程设计-哈夫曼编译码系统的设计与实现

20180902一、需求分析1、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站设计一个哈夫曼编译码系统。

2、基本要求（1）初始化（Initialzation）。

从数据文件DataFile.txt中读入字符及每个字符的权值，建立哈夫曼树HuffTree；（2）编码（EnCoding）。

用已建好的哈夫曼树，对文件ToBeTran.txt 中的文本进行编码形成报文，将报文写在文件Code.txt中；（3）译码（Decoding）。

利用已建好的哈夫曼树，对文件CodeFile.txt 中的代码进行解码形成原文，结果存入文件Textfile.txt中；（4）输出（Output）。

输出DataFile.txt中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.txt及其报文Code.txt；输出CodeFile.txt及其原文Textfile.txt；二、概要设计1.数据结构本程序需要用到以一个结构体HTNode，以及一个二维数组HuffmanCode。

2.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。

系统子程序及功能设计本系统共有七个子程序，分别是：a.int min1(HuffmanTree t,int i)//进行比较b.void select(HuffmanTree t,int i,int *s1,int *s2)//求权值最小的两个数c.void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n)///* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC */d.void Initialzation(HuffmanTree *HT,HuffmanCode *HC)//初始化e.int EnCoding(HuffmanTree *HT,HuffmanCode *HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt 中f.int pipei(char *c,int n,HuffmanCode *HC)//在huffmancode寻找匹配的编码g.void Decoding(HuffmanTree *HT,HuffmanCode *HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中3.各模块之间的调用关系以及算法设计主函数调用Initialzation，EnCoding，Decoding。

哈夫曼编码和译码

哈夫曼编码和译码

11
哈夫曼树的构造算法: 哈夫曼树的构造算法: 个结点的一维数组, (1)初始化哈夫曼树的 )初始化哈夫曼树的2n-1个结点的一维数组, 个结点的一维数组 即将各结点中的各个域均置0; 即将各结点中的各个域均置 ; 个权值存放到一维数组的前n个单元中 (2)读入 个权值存放到一维数组的前 个单元中, )读入n个权值存放到一维数组的前 个单元中, 它们即为初始森林中的n个只含根结点的权值 个只含根结点的权值; 它们即为初始森林中的 个只含根结点的权值; (3)对森林中的二叉树进行合并,产生 个新 )对森林中的二叉树进行合并,产生n-1个新 结点,依次存放到一维数组的第n+1个开始的单元中, 个开始的单元中, 结点,依次存放到一维数组的第 个开始的单元中 在这个过程中要注意对每个结点双亲域, 在这个过程中要注意对每个结点双亲域,左右孩子 域以及权值的修改. 域以及权值的修改.
13
s1=maxval;s2= maxval;/ 设maxval为float类型最大值 ; ;/*设 ;/ 为 类型最大值 */ for(j =1;j<=i;j+ +) ( ; ; ) if (ht[j].parent = =0) /*判断是否为根结点 判断是否为根结点*/ 判断是否为根结点 if (ht[j].weight<s1) { s2=s1;s1= ht[j].weight; p2=p1;p1=j; } ; ; ; ; else if (ht[j].weight <s2) { s2= ht[j].weight; p2=j; } ; ; ht[p1].parent=i;ht[p2].parent=i; ; ; ht[i].lchild =p1;ht[i].rchild=p2; ; ; ht[i].weight= ht[pl].weight+ht[p2].weight; ; } return (ht);} ;
数据结构课程设计：电文编码译码(哈夫曼编码)

数据结构课程设计：电文编码译码(哈夫曼编码)

xx农林大学计算机与信息学院数据结构课程设计设计：xx编译码器姓名：xx专业：2013级计算机科学与技术学号：班级：完成日期：2013.12.28xx编译码器一、需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。

哈夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。

二、设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。

若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。

那么，∑WiLi恰好为二叉树上带权路径长度。

因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。

数据结构课程设计 哈夫曼编码与译码器课程设计

数据结构课程设计 哈夫曼编码与译码器课程设计

数据结构课程设计题目名称：哈夫曼编码与译码器课程设计计算机科学与技术学院1.需求分析(1)熟练掌握哈夫曼编译原理(2)掌握程序设计步骤(3)根据哈夫曼编码原理，设计一个程序，在已知相关字符和字符对应权值（文件中存在或者用户输入）的情况下，根据用户要求对相应内容进行编码、译码等相应操作。

(4)输入的形式和输入值的范围；(5) 输出的形式；(6) 程序所能达到的功能；(7) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果2.概要设计1.写好流程图，设计实验方案。

2.初始化，从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件HuofumanTree中。

3.编码。

利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

4.译码。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

5.印代码文件（Print）将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

6.印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

具体函数如下：1.Initialization()初始化2.Encoding()编码3.Decoding()译码4.Print_file()打印代码文件5.search(k,j,p)搜索二叉树6.Print_tree() 打印二叉树7.menu()主菜单8.main()主函数3.详细设计(1)哈夫曼结点定义类型以一个节点为单位，其中节点中包括他的父亲·左孩子·右孩子，权值(2)存储字符信息(3)用于编码时存取字符长度及起始位置(4)初始化将数据存入文件中void Initialization(){int i,j;FILE* HFM_f;//定义一个指针指向文件HFM_f = fopen("C:/Users/lenovo/Desktop/x.txt","w");//将文件打开，赋值给HFM_fif(HFM_f == NULL){printf("create file error!\n");}printf(" 请输入字符集大小: ");scanf("%d",&leaves);fprintf(HFM_f,"----输入的值-----\n");fprintf(HFM_f," 字符大小%4d\n",leaves);fprintf(HFM_f," 字符权值\n");for(i=0; i<leaves; i++){printf(" 请输入第%d个字符和其权:",i+1);scanf(" %c ",&HFM_num[i].hfstr);scanf("%d",&HFM_num[i].weight);fprintf(HFM_f,"%4c",HFM_num[i].hfstr);fprintf(HFM_f,"%4d\n",HFM_num[i].weight); //存储字符和权值}(5)建立哈夫曼树for(i=0; i<maxsize; i++)//哈夫曼树初始化{HFM_tree[i].parent = -1;HFM_tree[i].lchild = -1;HFM_tree[i].rchild = -1;HFM_tree[i].weight = 0;}for(i=0; i<leaves; i++){HFM_tree[i].weight = HFM_num[i].weight;}for(i=0; i<leaves-1; i++){int m1,m2;int m1_pos,m2_pos;m1=m2=65536;m1_pos=m2_pos=0;for(j=0; j<leaves+i; j++)//选出最小且没被访问的两个数{if(HFM_tree[j].weight<m1&&HFM_tree[j].parent == -1) {m2 = m1;m1 = HFM_tree[j].weight;m2_pos = m1_pos;m1_pos = j;}else{if(HFM_tree[j].weight<m2&&HFM_tree[j].parent == -1){m2 = HFM_tree[j].weight;m2_pos = j;}}}HFM_tree[leaves+i].parent = -1;HFM_tree[leaves+i].lchild = m1_pos;//HFM_tree[leaves+i]为两者的最小和的结点，即他们的父亲HFM_tree[leaves+i].rchild = m2_pos;HFM_tree[m1_pos].parent = leaves+i;HFM_tree[m2_pos].parent = leaves+i;HFM_tree[leaves+i].weight = m2+m1;//将和赋为他们的父亲结点的权值}(6)输出哈夫曼树printf("----------------哈夫曼编码--------------\n");printf(" parent lchild rchild weight\n");fprintf(HFM_f,"-------------哈夫曼编码------------\n");fprintf(HFM_f," parent lchild rchild weight\n");for(i=0; i<leaves*2-1; i++){printf("%8d%8d%8d%8d\n",HFM_tree[i].parent,HFM_tree[i].lchild,HFM_tre e[i].rchild,HFM_tree[i].weight);fprintf(HFM_f,"%8d%8d%8d%8d\n",HFM_tree[i].parent,HFM_tree[i].lchild, HFM_tree[i].rchild,HFM_tree[i].weight);}printf("\n");fclose(HFM_f);//关上文件}(7)编码void Encoding(){int i,j,p,c,k;FILE* HFM_f = fopen("CodeFile.txt","w");//打开文件if(HFM_f == NULL){printf("open file error!\n");}for(i=0; i<leaves; i++){c = i;//当前结点编号p = HFM_tree[i].parent;//父亲结点编号HFM_hf.start = len-1;//单个结点路径长度-1，即循环次数，从0开始算while(p!=-1)//根节点的p=-1，即根结点的父亲值为-1，即为初始化的值，证明根节点没有父亲结点{if(HFM_tree[p].lchild == c)//若左孩子为C，赋值0{HFM_hf.bit[HFM_hf.start] = 0;}else{HFM_hf.bit[HFM_hf.start] = 1;//若右孩子为c，赋值1 }--HFM_hf.start;c = p;//沿着树往上走，将刚才的父亲变为孩子p = HFM_tree[c].parent;//寻找当前结点的父亲，即原节点的爷爷}for(j=HFM_hf.start+1,k=0; j<len; j++,k++){HFM_code[i].bit[k] = HFM_hf.bit[j];}HFM_code[i].length = len-HFM_hf.start-1;HFM_code[i].start = HFM_hf.start+1;}for(i=0; i<leaves; i++){HFM_code[i].hfch = HFM_num[i].hfstr;printf(" character:%c start:%d length:%dCode:",HFM_code[i].hfch,HFM_code[i].start,HFM_code[i].length );for(j=0; j<HFM_code[i].length; j++){printf("%d",HFM_code[i].bit[j]);fprintf(HFM_f,"%d",HFM_code[i].bit[j]);}printf("\n");}printf("\n");fclose(HFM_f);}4.调试结果输入26个字符及其权值26个字母的编码如下：译码如下：打印文件中的内容:打印出的哈夫曼树如下：5.时间复杂度本代码的哈夫曼算法的时间复杂度为O(n^3)。