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

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。

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

《数据结构》课程设计实验报告题目哈夫曼编码/译码器学院数理与信息学院专业计算机科学与技术班级计科132学生姓名刘海澍 5周弘杰8徐铭瑶 3指导教师编写日期数据结构课程设计目录1 问题描述.................................................................错误!未定义书签。

2 问题分析.................................................................错误!未定义书签。

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

1) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；2) 编码：利用建好的哈夫曼树生成哈夫曼编码；3) 输出编码；4）显示哈夫曼树；5）界面设计的优化；6) 设字符集及频度如下表：字符空格 A B C D E F频度4 9 23 2 17 15字符G H I J K频度1 2 3 3 42.问题分析（1）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[60]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。

数据结构设计性实验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 超过次数限制。

哈夫曼编码与译码学生姓名：指导老师：摘要本课程设计主要解决的是利用哈夫曼树生成的哈夫曼编码进行字符串的加密和解密，并将加密的编码写入文件。

在此课程设计中，系统开发平台为Windows XP，程序设计语言采用面向过程的高级语言C和面向对象的高级语言C++，程序运行平台为Visual C++ 6.0。

在程序设计中，采用了结构化与面向过程两种解决问题的方法。

程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。

关键词哈夫曼树，编码，译码，文件操作，C，C++；1 引言1.1 课题背景随着信息时代的到来，各种信息日益丰富，信息迅速膨胀，对信息管理的工作量也日益增大。

在信息化未到来之前，信息的存储编码也变得尤为重要，公司之间的信息需要编码，用户个人数据需要编码，都需要占用很大的空间，所以一个好的、高效的编码译码算法是十分重要的。

好的加密算法不仅可以降低管理方的工作量和存储量，还可以对用户的信息进行高效的管理，同时使在用中可以避免不必要的麻烦。

数据结构是指相互之间存在一定关系的数据元素的集合。

按照视点的不同，数据结构分为逻辑结构和存储结构。

数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。

所谓逻辑关系是指数据元素之间的关联方式或邻接关系。

根据数据元素之间逻辑关系的不同，数据结构分为四类：集合、线性结构、树结构、图结构。

数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。

为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。

数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。

通常有两种存储结构：顺序存储结构和链接存储结构。

树是一种在实际应用中被广泛使用的数据结构。

它是由同一类型的记录构成的集合。

哈夫曼编码译码器哈夫曼编码译码器a)需求分析：一个完整的系统应具有以下功能：(l)I:初始化。

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

(2)C:编码。

利用已建好的哈夫曼树(如不在内存，则从文件hfmtree 中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

(3)D:编码。

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

(4)P:印代码文件。

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

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

(5)T:印哈夫曼树。

将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中可以根据题目要求把程序划成5个模块，设计成菜单方式，每次执行一个模块后返回菜单。

除了初始化(I)过程外，在每次执行时都经过一次读取磁盘文件数据。

这是为了如果在程序执行后一直没有进行初始化(I)过程，为了能使后面的操作顺利进行，可以通过读取旧的数据来进行工作。

比如：如果程序的工作需要的字符集和权值数据是固定的，只要在安装程序时进行一次初始(I)化操作就可以了。

在再次运行程序时，不管进行那项操作都可以把需要的数据读入到内存。

b)概要设计本程序主要用到了三个算法。

(1)哈夫曼编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。

先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。

(2)串的匹配在编码(D)的过程中间，要对已经编码过的代码译码，可利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显并存入文件。

(3)二叉树的遍历在印哈夫曼树(T)的中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出c）详细设计构造树的方法如下：初始化：每个字符就是一个结点，字符的频度就是结点的权；1、将结点按频度从小到大排序；2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点的权值就是它两个儿子的权值之和；构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；3、如果结点序列里只剩下一个结点，表示构造完毕，退出。

电文的编码和译码简单Huffman编码译码的设计与实现三、题目--赫夫曼编码/译码器1. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

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

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

(2) E：编码（Encoding）。

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

(3) D：译码（Decoding）。

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

以下为选做：(4) P：印代码文件（Print）。

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

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

(5) T：印赫夫曼树（Tree printing）。

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

3.测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。

(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。

字符 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 1四、概要设计1)问题分析哈夫曼树的定义1.哈夫曼树节点的数据类型定义为：typedef struct{ //赫夫曼树的结构体char ch;int weight; //权值int parent,lchild,rchild;}htnode,*hfmtree;2）所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。

课程设计任务书课程名称数据结构课程设计课题赫夫曼编译码器专业班级网络工程***学生姓名***学号**指导老师审批任务书下达日期：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)主要模块程序流程图下面介绍三个主要的程序模块流程图：①函数流程图：流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。

哈夫曼编码译码课程设计报告《数据结构》课程设计——赫夫曼编码/译码器设计指导教师：李文书、周维达班级：10电信实验班学号：Q10600132姓名：王彬彬一、实验目的1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。

2、熟悉掌握一门计算机语言，能够进行数据算法设计。

二、实验原理哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。

在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。

构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。

最简单的二进制编码方式是等长编码。

若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。

哈夫曼树课用于构造使电文的编码总长最短的编码方案。

主要流程图如下：三、实验步骤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() 主菜单9：main() 主函数四、实验结果与分析（1）大致个人测试案例：主界面：。

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

要求：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、运行环境（软、硬件环境）处理器:英特尔酷睿i3物理内存:2G操作系统:Microsoft Windows8开发环境：Microsoft Visual Studio20082、程序所实现的功能对输入的正文进行哈夫曼编码根据哈夫曼编码得到由结点构成的哈夫曼树并以树的形式输出得到哈夫曼编码的0、1密文对得到的密文进行译码，得到译前原始输入的字符串并输出3、程序的输入，包含输入的数据格式和说明输入字符串（可以包含空格，空格视为同一字符）（不包含换行）（输入其他字符亦可）4、程序的输出，程序输出的形式输出每个字符出现次数并该字符输出每个字符的编码并该字符输出整个字符串的编码后密文输出密文译码后的字符串5、测试数据“there are there studens”二、设计说明1、算法设计的思想（用户输入的字符串主要包含两个方面的信息，其一：字符串中每个元素出现的次数，及关键字key，其二：每个结点的顺序信息，存放在链表的List数组中，该部分为public信息。

）<用户输入待编码的字符串>以LinkList存储输入的字符串，其中LinkList每个元素的类型为HuffmanNode类,计算每个字符的出现次数（key），并按照key的大小进行由小到大的排序。

<构造HuffmanTree>对LinkList中的前两个元素按照左小右大构建树，左0右1的原则对tag赋值、完善结点的parent信息，同时得到两个元素之和temp，通过Insert函数，将temp插入LinkList，重复进行上述操作，直至链表尾。

<译码>根据每个元素的tag信息，通过非递归方式，（以Stack存储）依次得到该元素的parent.tag直至parent为空。

<得到密文>将每个结点的编码按链表中的顺序输出。

（存放在队列qu中）<由译文得到正文>根据每个元素的编码对密文逐个翻译并输出。

┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊目录目录 (1)1 课程设计的目的和意义 (2)2 需求分析 (3)3 系统设计 (4)(1)设计思路及方案 (4)(2)模块的设计及介绍 (4)(3)主要模块程序流程图 (6)4 系统实现 (10)(1)主调函数 (10)(2)建立HuffmanTree (10)(3)生成Huffman编码并写入文件 (13)(4)电文译码 (14)5 系统调试 (16)小结 (18)参考文献 (19)附录源程序 (20)┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1 课程设计的目的和意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

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

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

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

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

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

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

作为软件工程专业的学生，我们应该很好的掌握这门技术。

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

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

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

哈夫曼编码译码器哈夫曼编码译码器a)需求分析：一个完整的系统应具有以下功能：(l)I:初始化。

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

(2)C:编码。

利用已建好的哈夫曼树(如不在内存，则从文件hfmtree 中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

(3)D:编码。

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

(4)P:印代码文件。

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

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

(5)T:印哈夫曼树。

将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中可以根据题目要求把程序划成5个模块，设计成菜单方式，每次执行一个模块后返回菜单。

除了初始化(I)过程外，在每次执行时都经过一次读取磁盘文件数据。

这是为了如果在程序执行后一直没有进行初始化(I)过程，为了能使后面的操作顺利进行，可以通过读取旧的数据来进行工作。

比如：如果程序的工作需要的字符集和权值数据是固定的，只要在安装程序时进行一次初始(I)化操作就可以了。

在再次运行程序时，不管进行那项操作都可以把需要的数据读入到内存。

b)概要设计本程序主要用到了三个算法。

(1)哈夫曼编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。

先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。

(2)串的匹配在编码(D)的过程中间，要对已经编码过的代码译码，可利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较，如果相等就回显并存入文件。

(3)二叉树的遍历在印哈夫曼树(T)的中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出c）详细设计构造树的方法如下：初始化：每个字符就是一个结点，字符的频度就是结点的权；1、将结点按频度从小到大排序；2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点的权值就是它两个儿子的权值之和；构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；3、如果结点序列里只剩下一个结点，表示构造完毕，退出。

题目一: 哈夫曼编码与译码一、任务设计一个运用哈夫曼算法的编码和译码系统, 反复地显示并解决以下项目, 直到选择退出为止。

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

二、流程图三、代码分解 //头文献 #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);字符集记录符集记录权值 权值 至文献“哈夫曼树。

t xt” 菜单1.从键盘输入字符集进行编码2.从文献读入字符集进行编码1.从键盘输入编码进行译码2.从文献读入编码进行译码0.返回上级菜单 0.返回上级菜单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);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);}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");}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);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.从文献读入编码, 读入上一步的编码译码完毕, 返回！退出系统。

数据结构课程设计报告实验二哈夫曼编码目录一．问题描述及分析p11．问题描述p12．需求分析p1 二．功能模块及数据结构描述p11．数据结构描述 p1 2．模块描述 p2三．主要算法流程描述p21．编码流程图 p3 2．译码流程图 p4四．使用说明p5 五．调试分析说明p6一．问题描述及分析1．问题描述设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（后缀名.cod）；反过来，可将一个编码文件还原为一个文本文件(.txt)。

2．需求分析（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）；（3）输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；（4）显示指定的编码文件和文本文件；3．运行要求.Windows xp/2003.VC++6.0(或以上)运行库二．功能模块及数据结构描述1．数据结构描述typedef struct{long weight;long lchild,rchild,parent;}hfmt;hfmt t[2*256-1];存放哈夫曼树结构体，weight为节点权值，lchild，rchild为节点的左右孩子在向量中的下标(为叶节点时，两值为：-1)，parent为节点的双亲在向量中的下标(用来区别根与非根节点，值为-1与非-1)。

typedef struct{char bits[256];long s;}hfmcc;hfmcc cc[256];存放哈夫曼编码结构体，s用来指示编码在位串bits[n]中的起始位置。

2．模块描述图2.1 系统函数copy函数：根据s的值在位串bits[n]中提取有效编码位数。

HFM函数：对读入的节点权值，生成哈夫曼树。

HFMBM函数：对生成的哈夫曼树进行零一编码，对应于原文件字符。

三．主要算法流程描述1．编码流程图图2.2 编码流程图2．译码流程图图2.3 译码流程图四．使用说明图2.4 生成的文件本软件默认生成的编码文件名为：a.cod默认生成的译码文件名为：b.txt执行提示：输入所要编码的文本文件。

电文的编码和译码1.问题描述从键盘接受一串电文字符，输出对应的哈夫曼编码；同时能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。

2.设计要求(1)构造一棵哈夫曼树。

(2)实现哈夫曼编码，并用哈夫曼编码生成的代码进行译码。

(3)程序中字符和权值是可变的，实现程序的灵活性。

3.数据结构本课程设计采用结构体数组作为数据结构，来储存哈夫曼树及其编码。

4.分析与实现在电报通信中，电文是以二进制代码传送的。

在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化成对应的字符序列，即译码。

字符被使用的频率是非均匀的。

在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的字符编码长度尽可能短。

因此，若对某字符集进行不定长编码设计，则要求任一一个字符编码都不能使其他字符编码的前缀，这种编码称作前缀编码。

由哈弗曼树求得的编码是最优前缀码，也称哈夫曼编码。

给出字符集和各个字符的概率分布，构造哈弗曼树，将哈夫曼树中每个分支结点的左分支标0，右分支标1，从根到每个叶子的路径上的标号连起来就是给叶子所代表字符的编码。

(1)构造哈夫曼树根据哈弗曼算法，若已知n个叶结点，则构造的哈弗曼树有2n-1个结点。

第一步：先输入字符集中的n个字符（叶结点）和表示其概率分布的权值，储存在ht （HuffNode型）数组的前n个数组元素中。

然后将2n-1个结点的双亲和孩子结点均置为0。

第二步：在所有的结点中，选取双亲为零且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置。

将根为ht[p1]和ht[p2]的两棵树合并，使其成为新结点ht[i]的左右孩子，ht[i]的权值为最小权值m1和次小权值m2之和；ht[p1]和ht[p2]的双亲指向i。

共进行n-1次合并，产生n-1个结点，依次放入ht数组中数组下标从n+1到2n-1。

这样就构成了一棵哈夫曼树。

(2)编码基本思想是：从哈弗曼树的叶结点ht[i] (1≤i≤n)出发，通过双亲parent找到其双亲ht[f]，通过ht[f]的域left和right，可知ht[i]是ht[f]的左分支还是右分支，若是左分支，生成的代码0；若是右分支，生成代码1。