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

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

  • 格式：doc
  • 大小：114.00 KB
  • 文档页数：16

目录1 问题描述 (1)2 需求分析 (1)3 概要设计 (2)3．1抽象数据类型定义 (2)3．2模块划分 (3)4 详细设计 (4)4．1数据类型的定义 (4)4．2主要模块的算法描述 (4)4、3 流程图 (6)5 测试分析 (9)6 课程设计总结 (10)参考文献 (11)附录（源程序清单） (12)1 问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)2)采用静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符空格 A B C D E F G H I J K L M频度186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 12 需求分析（1）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[30]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。

（2）编写CodeInput(n,ht)函数并在函数中设置一个for(i=0;n;++)循环，首先输入n个字符，再利用函数中的for(i=0;<n;++)循环实现对这n个字符的权值的输入。

（3）编写CreateHT(ht,n)函数来构造一棵哈夫曼树，首先用一个for(i=0;<2*n-1;++)循环将所有2n-1个结点的parent、lchild、rchild域均置初值为-1；再用一个for(i=n;<2*n-1;++)循环来构造哈夫曼树，在该循环中首先令lnode 和rnode为最小权值的两个结点位置且其域值均为-1，再用一个for(k=0;<=i-1;k++)循环在数组ht[30]中寻找权值最小的两个结点并且只能在尚未构造二叉树的结点中查找，由于只能在尚未构造二叉树的结点中查找，因此在for(k=0;k<=i-1;k++)循环中加入一个if(ht[k].parent==-1)语句来判断结点lnode和rnode是否已经在二叉树中，如果结点lnode和rnode在二叉树中，则结点lnode和rnode的parent的值为其双亲结点在数组ht[30]中的序号就不会为-1了，在查找到ht[lnode]和ht[rnode]后将他们作为ht[i]的左右子树，ht[lnode]和ht[rnode]的双亲结点置为ht[i]，且ht[i].weight=ht[lnode].weight+ht[rnode].weight。

如此处理下去，直到所有2n-1个结点处理完毕。

（4）编写CreateHCode(ht,hcd,n)函数来求哈夫曼编码，由于求哈夫曼编码只需求叶子结点的哈夫曼编码。

对于当前叶子结点ht[i]，首先将对应的哈夫曼编码hcd[i]的start域值置初值n，找其双亲结点ht[f]，若当前结点是双亲结点的左孩子结点，则在hcd[i]的cd数组中添加0，若当前结点是双亲的右孩子结点，则在hcd[i]的cd数组中添加1，将start域减1。

再对双亲结点进行同样的操作，直到无双亲结点为止，最后让start指向哈夫曼编码最开始字符。

因此在函数中设置一个for(i=0;i<n;i++)循环，在循环中设置一个while(f!=-1)循环语句来判断循环是否到了根结点，再在while(f!=-1)中设置一个if(ht[f].lchild==c)语句来判断该处理左孩子结点还是该处理右孩子结点。

最后用这个for(i=0;i<n;i++)循环来根据哈夫曼树求出哈夫曼编码。

（5）最后编写CodeOutput(n,hcd)函数，首先利用for(i=0;i<n;i++)循环和for(j=hcd[i].start;j<=n;j++)循环来实现所有字符的哈夫曼编码的输出；再利用for(i=0;i<n;i++)循环和for(j=hcd[i].start;j<=n;j++)循环来实现每个字符的序号和哈夫曼编码的输出。

3 概要设计3．1抽象数据类型定义（1）树的抽象数据类型定义ADT Stack{数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0}数据关系：若D为空集，则称为空树。

若D仅为一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：（1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。

（2）若D-{root}<>空集，则存在一个划分D1，D2，···，Dm（m>0）。

（3）对应于D-{root}的划分，H-{<root，X1}，···，<root，Xm>}有唯一的一个划分H1，H2，···，Hm（m>0）。

基本操作：InitTree(&T)操作结果：构造空树T。

DestroyTree(&T)初始条件：树T已存在。

操作结果：树T被销毁。

ClearTree(&T)初始条件：树T已存在。

操作结果：将树T清为空栈。

TreeEmpty(T)初始条件：树T已存在。

操作结果：若树T为空，则返回TRUE，否则FALSE。

TreeDepth(T)初始条件:树T已存在。

操作结果：返回T的深度。

Root（T）初始条件：树T已存在。

操作结果：返回树T的根。

3．2模块划分本程序包括三个模块：（1）主程序模块void main(){初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；}（2）哈夫曼模块——实现哈夫曼树的抽象数据类型（3）求哈夫曼编码模块——实现求哈夫曼编码算法的数据类型4 详细设计4．1数据类型的定义（1）哈夫曼树类型typedef struct{//构造树char data;//结点权值int weight;//权重int parent;//双亲结点int lchild;//左孩子int rchild;//右孩子}HTNode;HTNode ht[30];（2）求哈夫曼编码类型typedef struct{char cd[30];//存放当前结点的哈弗曼编码int start;//cd[start]~cd[n]存放哈弗曼码}HCode;HCode hcd[30];4．2主要模块的算法描述（1）主函数int main(){int n;printf("请输入要输入的字符数量n:");//读入字符的个数while(scanf("%d",&n),n!=-1){//初始化printf("请输入n个字符和n个权值\n");CodeInput(n,ht);//输入数据函数，将读入n个字符和权重CreateHT(ht,n);//构造哈弗曼树CreateHCode(ht,hcd,n);//哈弗曼编码算法CodeOutput(n,hcd);}//打印哈弗曼编码，将打印出编码，和每一个字符的编码return 0;（2）构造哈夫曼树void CreateHT(HTNode ht[],int n)//构造一棵哈夫曼树{int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)//所有结点的相关域置初值-1ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for (i=n;i<2*n-1;i++)//构造哈弗曼树{min1=min2=32767;//lnode和rnode为最小权值的两个结点位置lnode=rnode=-1;for (k=0;k<=i-1; k++)//在ht[]中查找权值的最小的两个结点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;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode; ht[i].rchild=rnode;//ht[]作为双亲结点}}（3）利用哈夫曼编码算法哈夫曼编码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';//处理左孩子结点elsehc.cd[hc.start--]='1';//处理右孩子结点c=f; f=ht[f].parent;}hc.start++;//start指向哈弗曼编码最开始的位置hcd[i]=hc;}}4．3 流程图（1）主函数流程图如图4.3-1（2）哈夫曼编码算法流程图，如图4.3-2（3）构造树函数流程图，如图4.3-3图4.3-2哈夫曼编码算法流程图图4.3-1主函数流程图图4.3-3构造树函数流程图5 测试分析测试数据及结果如下：结果分析：首先确定要输入的字符数量n为8，然后分别输入这8个字符和这8个字符的权值，且输入的这8个字符分别为B、C、D、E、F、G、H、I而这8个字符对应的权值分别为13、22、32、103、21、15、47、57。

其次根据输出的结果可知：所有字符的哈夫曼为0010110010001111110000011。

合集下载

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

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

数据结构课程设计题目名称：哈夫曼编码与译码器课程设计计算机科学与技术学院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)。

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

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

数据结构课程设计题目：哈夫曼编码译码姓名：专业：通信工程学号：指导教师：吴泽晖目录目录 (1)一、需求分析 (2)二、设计要求 (2)三、概要设计 (2)1、流程图 (2)2、设计包含的几个部分 (4)四、详细设计 (2)五、显示结果………………………………………………9.六、心得体会 (10)七、参考文献 (11)哈夫曼编码译码一、需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

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

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

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

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

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

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

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

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

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

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

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

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

数据结构课程设计哈夫曼编码实验

数据结构课程设计哈夫曼编码实验

数据结构设计性实验Huffman编码与译码学号姓名班级设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

二．实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。

2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符四．分析以及算法描述1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。

2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。

②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。

④重复②和③，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。

3)练习通过普通树来构造霍夫曼树。

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

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

数据结构课程设计哈夫曼编码译码器.题目一：哈夫曼编码与译码一、任务设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

要求：1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) ；2)初始化：键盘输入字符集统计字符权值、自定义26个字符和26个权值、统计文件中一篇英文文章中26个字母，建立哈夫曼树；3)编码：利用建好的哈夫曼树生成哈夫曼编码；4)输出编码（首先实现屏幕输出，然后实现文件输出）；5）译码（键盘接收编码进行译码、文件读入编码进行译码）；6)界面优化设计。

二、流程图主菜单1.建立字符权值 2.建立并输出哈夫曼树3.建立并查看哈弗曼编码4.编码与译码0.退出系统1.从键盘输入字符集统计权值2.从文件读入字符集统计权值3.自定义字符及权值0.返回上级菜单输出哈夫曼树并保存至文件“哈夫曼树。

txt”输出哈夫曼编码并保存至文件“哈夫曼编码。

txt1.编码2.译码0.返回上级菜单1.从键盘输入字符集进行编码2.从文件读入字符集进行编码1.从键盘输入编码进行译码 2.从文件读入编码进行译码0.返回上级菜单0.返回上级菜单三、代码分解//头文件#include#include#include#include #define N 1000#define M 2*N-1#define MAXcode 6000//函数声明void count(CHar ch,HTNode ht[]);void editHCode(HTNode ht[],HCode hcd[],CHar ch,int n,char bianma[]); //编码函数void printyima(HTNode ht[],HCode hcd[],int n,char bianma[]); //译码函数void creatHT(HTNode ht[],int n);void CreateHCode (HTNode ht[],HCode hcd[],int n);void DispHCode(HTNode ht[],HCode hcd[],int n);void input_key(CHar ch);void input_file(CHar ch);void input_cw(HTNode ht[]);void bianma1(HTNode ht[],HCode hcd[],CHar ch,int n,char bianma[]);void bianma2(HTNode ht[],HCode hcd[],CHar ch,int n,char bianma[]);void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]);void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan(); //结构体typedef struct-省略部分-;}void bianma2(HTNode ht[],HCode hcd[],CHar ch,int n,char bianma[]){ int i; FILE*fp; char filename[20]; printf("请输入要打开的文件名(*.txt):"); scanf("%s",filename); if((fp=fopen(filename,"r"))==NULL) { printf("\n\t\t文件打开失败!!!"); return; } for(i=0;!feof(fp);i++) { fread(ch.s[i],sizeof(char),1,fp); } ch.num=strlen(ch.s); printf("\n读入成功!\n"); printf("文件中的字符集为:\n%s",ch.s); fclose(fp);editHCode(ht,hcd,ch,n,bianma); getch(); system("cls"); return;}//译码函数void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]){ int i; char code[MAXcode]; printf("请输入编码进行译码（以‘#’结束）:\n"); for(i=0;i四、调试结果主菜单建立字符权值选择2.从文件读入字符进行统计输入测试文件名“cs.txt”输出个字符权值建立哈夫曼树并输出至文件生成哈夫曼编码并保存至文件编码选择2.从文件读入字符集编码编码结果保存至文件译码选择2.从文件读入编码，读入上一步的编码译码完成，返回！退出系统word教育资料div ;i++) 达到当天最大量API KEY 超过次数限制。