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

JAVA语言实验报告学院计算机工程学院班级计算1013 姓名 xxxx 学号 201081xxxx成绩指导老师 xxxx2012年09月03日目录目录 (1)1 课程设计的目的和意义 (2)2 需求分析 (3)3 系统（项目）设计 (5)①设计思路及方案 (5)②模块的设计及介绍 (5)③主要模块程序流程图 (8)4 系统实现 (11)①主调函数 (12)②建立HuffmanTree (12)③生成Huffman编码并写入文件 (15)④电文译码 (16)5 系统调试 (17)参考文献 (21)附录源程序 (22)1 课程设计的目的和意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

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

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

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

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

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

作为信息管理专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。

这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。

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

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

要求：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 超过次数限制。

目录目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ (2)1 程的目的和意⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32 需求分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43 概要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4 4⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.85 分析和果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.11 6⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯127致⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯138附⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯13参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..201课程设计目的与意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

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

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

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

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

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

作为计算机专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。

这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试 C 程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师：XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx 姓名xxx主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。

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

（3）P：打印代码文件（Print）。

将文件codefile以紧凑格式显示在终端上，每行50个代码。

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

（4）T：打印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21 日指导教师签名：课程负责人签名：2012年 6月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。

课程设计任务书课程名称数据结构课程设计课题赫夫曼编译码器专业班级网络工程***学生姓名***学号**指导老师审批任务书下达日期：2011 年6 月26 日任务完成日期：2011 年7 月15 日一、设计内容1）问题描述对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。

2）基本要求a.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。

b.编码，利用建好的huffman树生成huffman编码；c.输出编码；d.译码功能；二．设计要求：课程设计报告1)需求分析a.程序的功能。

1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。

2.编码，利用建好的huffman树生成huffman编码；3.输出编码；4.译码功能；b.输入输出的要求。

2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

i.void main()ii.void tohuffmancode(int n)//编码部分iii.void decode(char ch[],huftree tree[],int n)//译码iv.void huffman(huftree tree[],int *w,int n) //生成huffman树v.void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点vi.void huffmancode(huftree tree[],char code[],int n)//输出huffman编码其流程图如下：主函数main 调用其他函数：tohuffmancode(int n)decode(char ch[],huftree tree[],int n)huffman(huftree tree[],int *w,int n)select(huftree tree[],int k)huffmancode(huftree tree[],char code[],int n) 其主流程图如下：(3)主要模块程序流程图下面介绍三个主要的程序模块流程图：①函数流程图：流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。

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

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

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

t xt”1.编码2.译码0.返回上级菜单1.从键盘输入字符集进行编码2.从文件读入字符集进行编码1.从键盘输入编码进行译码2.从文件读入编码进行译码0.返回上级菜单0.返回上级菜单三、代码分解//头文件#include<stdio.h>#include<string.h>#include<stdlib.h>#include <conio.h>#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{char data;int parent;int weight;int lchild;int rchild;}HTNode;typedef struct{char cd[N];int start;}HCode;typedef struct{char s[N];int num;}CHar;CHar ch;HTNode ht[M];HCode hcd[N];//主函数int main(){int xh;while(1){system("color 1f"); //操作菜单背景颜色xh=caidan(); //调用菜单函数switch(xh) //switch语句{case 1:system("cls");creat_cw();break;case 2:system("cls");creatHT(ht,n);break;case 3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case 4:system("cls");bianmayima();break;case 0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感谢使用本系统!\n\n\n\n\n\n\n \t\t\t");exit(0);default:system("cls");putchar('\a');printf("\n\t\t输入有误，请重新输入:\n");break;}}return 0;}//菜单函数int caidan() //菜单函数模块//{int xh;printf("\n\n\n");printf("\t\t 欢迎使用哈夫曼编码译码系统\n");printf("\t\t \n");printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*= =*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 1.建立字符权值=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 2.建立并输出哈夫曼树=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 3.生成并查看哈夫曼编码=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 4.编码与译码=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 0.退出系统=*\n");printf("\t\t*= =*\n");printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\n\t\t请输入序号进行选择:");scanf("%d", &xh);return xh; //返回从键盘接收的选项}void bianmayima(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码与译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianmacaidan();break;case 2:system("cls");yimacaidan();break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误，请重新输入:\n");break;}}}void yimacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 译码\n"); printf("\t\t \n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文件读入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");yima1(ht,hcd,n,bianma);break;case 2:system("cls");yima2(ht,hcd,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误，请重新输入:\n");break;}}}void bianmacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入字符集编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文件读入文章编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误，请重新输入:\n");break;}}}void creat_cw(){int xh2;while(1){printf("\n\n\n\n\n");printf("\t\t 建立字符权值\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.从键盘输入字符集进行统计=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.从文件读入字符集统计=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 3.自定义字符权值=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh2);switch(xh2) //switch语句{case 1:system("cls");input_key(ch);break;case 2:system("cls");input_file(ch);break;case 3:system("cls");input_cw(ht);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误，请重新输入:\n");break;}}}//建立字符权值模块void input_key(CHar &ch){int i,j=0;char st[N];printf("请输入字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&st[i]);if(st[i]=='#'){st[i]='\0';break;}}strcpy(ch.s,st);ch.num=strlen(st);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_file(CHar &ch){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");printf("文件中的字符集为:%s\n",ch.s);fclose(fp);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_cw(HTNode ht[]){int i,w,s,j;char a;printf("要输入的字符总个数是？:");scanf("%d",&s);n=s;printf("请输入字符及其权值:\n");for(i=0;i<s;i++){printf("请输入第%d个字母:",i+1);scanf("%s",&a);ht[i].data=a;printf("请输入其权值:");scanf("%d",&w);ht[i].weight=w;}FILE *fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文件打开失败");return;}printf("\n定义权值成功!\n\n");printf("各字符及其权值为:\n\n");fprintf(fp,"各字符及其权值为:\n");printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<i;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);}printf("\n");printf("\n字符权值已输出至文件“data.txt”！");fclose(fp);printf("输入完成，按任意键返回！");getch();system("cls");return;}//统计字符权值函数void count(CHar &ch,HTNode ht[]){int i,j,m=0;char c[N];int sum[N]={0};for(i=0;ch.s[i]!='\0';i++){for(j=0;j<m;j++)if(ch.s[i]==c[j]||(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j])) break;if(j<m)sum[j]++;else{if(ch.s[i]>='A'&&ch.s[i]<='Z')c[j]=ch.s[i]+32;else c[j]=ch.s[i];sum[j]++;m++;}}for(i=0;i<m;i++){ht[i].data=c[i];ht[i].weight=sum[i];}n=m;FILE *fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文件打开失败");return;}printf("\n统计权值成功!\n\n");printf("各字符及其权值为:\n\n");fprintf(fp,"各字符及其权值为:\n");printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<m;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);}printf("\n");printf("\n字符权值已输出至文件“data.txt”！");fclose(fp);}//构造哈夫曼树void creatHT(HTNode ht[],int n){FILE *fp;if((fp=fopen("哈夫曼树.txt","w"))==0){printf("\n\t\t文件打开失败");return;}int i,j,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for (i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;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;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf("建立huffman树成功!\n");printf("输出huffman树:\n");fprintf(fp,"输出huffman树:\n");printf("\t字符\t权值\t父节点\t 左子节点\t右子节点");fprintf(fp,"\t字符\t权值\t父节点\t 左子节点\t右子节点");for(j=1;j<i;j++){ printf("\n");fprintf(fp,"\n");printf("\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i]. lchild,ht[j].rchild);fprintf(fp,"\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,h t[i].lchild,ht[j].rchild);}printf("\n");printf("哈夫曼树已输出至文件“哈夫曼树.txt”！按任意键返回!");fclose(fp);getch();system("cls");return;}//生成哈夫曼编码void CreateHCode (HTNode ht[],HCode hcd[],int n){int i,f,c,j=0;HCode hc;for(i=0;i<n;i++){hc.start=n;c=i;hc.cd[hc.start--]='0';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++;for(j=0;j<hc.start;j++)hc.cd[j]=' ';hcd[i]=hc;}}void DispHCode(HTNode ht[],HCode hcd[],int n) {FILE *fp;if((fp=fopen("哈夫曼编码.txt","w"))==0){printf("\n\t\t文件打开失败");return;}int i,k;int sum=0,m=0,j;printf("输出字符哈夫曼编码:\n");fputs("输出字符哈夫曼编码:\n",fp);for (i=0;i<n;i++){j=0;printf("%c:\t",ht[i].data);fprintf(fp,"\n%c:\t",ht[i].data);for (k=hcd[i].start;k<=n;k++){printf("%c",hcd[i].cd[k]);j++;fprintf(fp,"%c",hcd[i].cd[k]);}m+=ht[i].weight;sum+=ht[i].weight*j;printf("\n");}printf("\n哈夫曼编码已保存至文件“哈夫曼编码.txt!按任意键返回！”");fclose(fp);getch();system("cls");}//编码函数void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]){int i;char str[N];printf("请输入要编码的字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&str[i]);if(str[i]=='#'){str[i]='\0';break;}}strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");return;}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<MAXcode;i++){scanf("%c",&code[i]);if(code[i]=='#'){code[i]='\0';break;}}strcpy(bianma,code);printyima(ht,hcd,n,bianma);printf("\n译码完成！按任意键返回!");getch();system("cls");return;}void yima2(HTNode ht[],HCode hcd[],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(&bianma[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文件中的编码是:%s\n",bianma);printyima(ht,hcd,n,bianma);printf("\n译码完成！按任意键返回!");getch();system("cls"); }四、调试结果主菜单建立字符权值选择2.从文件读入字符进行统计输入测试文件名“cs.txt”输出个字符权值建立哈夫曼树并输出至文件生成哈夫曼编码并保存至文件编码选择2.从文件读入字符集编码编码结果保存至文件译码选择2.从文件读入编码，读入上一步的编码译码完成，返回！退出系统。

《数据结构》课程设计目录1. 问题描述……………………………………………第 2页2. 系统设计……………………………………………第 2页3. 数据结构与算法描述………………………………第 5页4. 测试结果与分析……………………………………第 6页5. 总结 (10)6. 参考文献 (10)附录程序源代码 (11)课程设计题目1. 问题描述利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

2.1基本要求一个完整的系统应具有以下功能：1）I：初始化（Initialization）。

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

输出哈夫曼树，及各字符对应的编码。

2）W：输入（Input）。

从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。

3）E：编码（Encoding）与译码（Decoding）。

编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

译码（Decoding）。

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

打印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

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

4）T：打印哈夫曼树（Tree Printing）。

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

5）Q：退出程序。