XXX学院本科
数据结构课程设计总结报告
设计题目：实验一、哈夫曼编/译码器
学生姓名：XXX
系别：XXX
专业：XXX
班级：XXX
学号：XXX
指导教师：XXX XXX
2012年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 设计试验用程序实验赫夫曼树的构造。
三、运行环境（软、硬件环境）
Windows xp sp3，Visual C++ 英文版
四、算法设计的思想
（1）初始化赫夫曼树，输入文件中各字符及其权值，并保存于文件中
（2）编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile 中
（3）D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。
（4）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。
（5）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。
五、流程图
六、算法设计分析
1.赫夫曼树节点的数据类型定义为：
typedef struct{ void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了Select（）函数。void select(HuffmanTree HT,int j,int *x,int *y);从已建好的赫夫曼树中选择parent为0，weight最小的两个结点。
3．利用已建好的哈夫曼树从文件中读入，对文件中的正文进行编码，然后将结果存入文件中。
4. coding
编码功能：对输入字符进行编码
5. Decoding
译码功能：利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。
6. Print() 打印功能函数：输出哈夫曼树以及对应的编码。
七、源代码
arent=i;HT[y].parent=i;
HT[i].lchild=x;HT[i].rchild=y;
HT[i].weight=HT[x].weight+HT[y].weight;
}
}
arent==0)
{*x=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight *x=i; HT[*x].parent=1; arent==0) {*y=i;break;} for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*x)&&(HT[i].weight *y=i; } arent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); } if((fp=fopen("","rb"))==NULL) printf("Open file error!\n"); if((fw=fopen("","wb+"))==NULL) printf("Open file error!\n"); char temp; fscanf(fp,"%c",&temp); h==temp) break; child,m); child,m); child==0&&HT[i].rchild==0) h; child,m); child,m); child,m); child,m); eight; if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild); if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]='\0'; } arent = i; HT[y].parent = i; HT[i].lchild = x; HT[i].rchild = y; HT[i].weight = HT[x].weight + HT[y].weight; } } arent == 0) { *x = i; break; } for (; i <= j; i++) if ((HT[i].parent == 0) && (HT[i].weight *x = i; HT[*x].parent = 1; arent == 0) { *y = i; break; } for (; i <= j; i++) if ((HT[i].parent == 0) && (i != *x) && (HT[i].weight *y = i; } arent; f != 0; c = f, f = HT[f].parent) if (HT[f].lchild == c) cd[--start] = '0'; else cd[--start] = '1'; HC[i] = (char *)malloc((n - start) * sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd); } if ((fp = fopen("", "rb")) == NULL) printf("Open file error!\n"); if ((fw = fopen("", "wb+")) == NULL) printf("Open file error!\n"); char temp; fscanf(fp, "%c", &temp); h == temp) break; child, m); child, m); child == 0 && HT[i].rchild == 0) h; child, m); child, m); child, m); child, m); eight; if (HT[j].lchild) Convert_tree(T, s + 1, i, HT[j].lchild); if (HT[j].rchild) Convert_tree(T, s + 1, i, HT[j].rchild); T[l][++k] = '\0'; } 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include 计算机与信息工程系 《实践环节名称》报告 专业：计算机科学与技术 班级：******** 学号：********* 姓名：杨明英 报告完成日期：2011/6/10 指导教师：*** 评语： 成绩： 批阅教师签名：批阅时间： 目录 1．问题描述 (1) 2．基本要求 (1) 3．数据结构 (1) 4．总体设计 (1) 5．详细设计 (2) 5.1主函数 void main() (2) 5.2建立文件 void jianliwenjian() (3) 5.3输入原文 void luruyuanwen() (4) 5.4创建哈夫曼树 void chuangjian() (5) 5.5编码 void bianma() (6) 5.6对哈夫曼码译码 void yiwen() (7) 5.7保存译文 void baocunyiwen() (8) 5.8输出原文 void duquyuanwen() (9) 5.9输出原文编码void duqubianma() (10) 5.10输出译文 void duquyiwen() (11) 6．测试与调试 (11) 7．源程序清单 (8) 8．实验心得 (28) 1.问题描述 打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。 2.基本要求 以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen 中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。 3.数据结构 char CH[N]; //记录原文字符数组 char YW[N]; //记录译文字符数组 typedef char * Hcode[m+1]; //存放哈夫曼字符编码串的头指针的数组 typedef struct { char a; int num; }dangenode; //记录单个字符的类别和出现的次数 typedef struct { dangenode b[m]; int tag; }jilunode; //统计原文出现的字符种类和数量 typedef struct node //静态三叉的哈夫曼树的定义 { int weight; //结点的权值 int parent; //双亲的下标 int Lchild; //左孩子结点的下标 int Rchild; //右孩子结点的下标 }htnode,hn[M+1]; // hn是结构数组类型，0号单元不用 4.总体设计 功能函数模块划分 void main() //主函数 void jianliwenjian() //建立存储原文的文件yuanwen void luruyuanwen() //通过程序录入原文到文件yuanwen中 void min_2(hn ht,int n,int *tag1,int *tag2) //选择权值较小的两个结点 void chuangjian(jilunode * jilu,hn ht) //建立哈夫曼树 void bianma(jilunode * jilu,hn ht,Hcode hc,int n) //对原文进行编码 void bianmabaocun(Hcode hc,jilunode * jilu) //保存编码在文件yiwen中 void yiwen(Hcode hc,jilunode * jilu) //读取yiwen中的编码，并将其翻译为原文 void baocunyiwen() //将翻译的译文保存到文件textfile中 void duqubianma() //在编码文件yiwen中读取编码 数据结构课程设计评阅书 2011—2012学年第一学期 专业：信息管理与信息系统学号： 1021024016 姓名：万永馨 课程设计名称：数据结构课程设计 设计题目：哈夫曼编码与译码的实现 完成期限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容（可另加附页）： 该设计题目将按以下要求完成： 哈夫曼编码与译码是信息传输中应用的经典算法，运用C或VC++结合数据结构等基础知识，按 以下要求编程实现各种进制的转换。 任务要求：1）阐述设计思想,画出流程图;2）需要对哈夫曼编码/译码的相关原理有所了解，设计数 据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能；3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要 求完成课程设计说明书。 设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的 原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调 用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统 功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精， 写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言， 使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正 确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算 法的时间、空间复杂性分析； 7）编写课程设计报告； 以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入 后续阶段的工作。设计工作结束，经指导老师验收合格后将设计说明书装订，并答辩。 实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include cout<<"输入第"< 安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院 1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data 中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data 及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff 课程论文 题目：哈夫曼树及其应用课程设计报告学号： 201230210115 姓名：黄文宣 班级： 1232101 专业：信息安全 课程名称：数据结构 课程老师：王晓燕 二零一肆年一月 目录 1、课程设计的题目及简介 (3) 2、实验目的 (3) 3、设计说明 (4) 4、总体流图 (4) 5、详细设计 (5) 6、实现部分 (6) 7、测试程序 (9) 8、心得与体会 (10) 一、课程设计题目 哈夫曼树及其应用 数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理 建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。 二、实验目的 1 熟悉树的各种存储结构及其特点。 2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 三、设计说明 建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 四、总体流图 哈夫曼树编码系统 初始化 编码 重新建立哈夫 曼树 译码 打印编码 #include"stdafx.h" #include"stdio.h" #include"conio.h" #include v .. . .. 安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院 1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1)输入的形式和输入值的范围； (2)输出的形式； (3)程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data 及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff { int weight; int parent; int l; int r; }; 哈夫曼编码的存储 struct huff *hufftree; (2)程序模块 选择1到i-1中parent为0且权值最小的两个下标 void Select(struct huff *HT, int n, int &s1, int &s2) 构建哈夫曼树： void huffmancoding(struct huff *ht,int *w,int n) 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器 院（系）：计算机学院 专业：计算机科学与技术 班级：24010102 学号：2012040101082 姓名：尹伟和 指导教师：徐蕾 此页为任务书 目录 1.题目分析 (1) 1.1.题目重述 (1) 1.1.1.系统功能需求分析 (1) 2.程序设计 (2) 2.1.系统功能模块说明 (2) 2.1.1.系统功能模块结构 (2) 2.1.2.系统模块功能说明 (3) 2.2.数据结构说明 (3) 2.2.1.结构体定义说明 (3) 2.2.2.哈夫曼树 (4) 2.2.3.字符-哈夫曼编码对照表 (4) 2.3.函数说明 (4) 3.算法描述 (6) 3.1.哈夫曼树的构建 (6) 3.2.字符-哈夫曼编码对照表 (6) 3.3.编码 (6) 3.4.译码 (7) 4.程序测试 (9) 4.1.字符集输入 (9) 4.2.编码测试 (10) 4.3.译码测试 (11) 参考文献 (13) 附录（程序清单） (14) 沈阳航空航天大学课程设计报告 1.题目分析 1.1.题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。 1.1.1.系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下： 1)读取用户输入的字符集和相应字符出现的频率； 2)根据用户输入构建哈夫曼树； 3)根据哈夫曼树构建字符-哈夫曼编码对照表； 4)根据字符-哈夫曼编码对照表对明文字符串进行编码； 5)根据哈夫曼树对二进制密文进行译码。 中北大学 数据结构 课程设计说明书 学生姓名: 郝晨栋学号： 1021010933 软件学院学院: 软件开发与测试: 专业 哈夫曼编码/目题: 译码器 康珺教指导师 2011年12月20日 目录 1 问题描述.............................................................. 错误！未定义书签。 2 需求分析.............................................................. 错误！未定义书签。 3 概要设计 (1) 3．1抽象数据类型定义 (1) 3．2总体框图以及功能描述 (2) 4 详细设计 (2) 4．1数据类型的定义 (2) 4．2主要模块的算法描述 (3) 5 测试分析................................................................................................ 4 6 课程设计总结 (6) 附录（源程序清单） (7) - 1 - 1 问题描述 1.设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 (1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)； (2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树; (3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码； 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 2 需求分析 编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。比如需传送的电文为“A B A C C D A”假设将A,B,C,D分别编码为00、01、10、11.则上述电文遍为00010010101100，总长度为14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。 对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。 3 概要设计 3．1抽象数据类型定义 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日 课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将 数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日 目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16) huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。 JAVA语言实验报告 学院计算机工程学院班级计算1013 姓名 xxxx 学号 201081xxxx 成绩指导老师 xxxx 2012年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程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 一、设计思想 程序要求： 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。 实现方法： 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。 重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。 哈夫曼编码译码器实验报告(免费) 问题解析与解题方法 问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 （1）从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）； （2）统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码； （4）将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf） （5）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。 根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。 哈夫曼树的理论创建过程如下： 一、构成初始集合 对给定的n个权值 {W1,W2,W3,...,Wi,...,Wn}构成n棵二 叉树的初始集合 F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二 叉树Ti中只有一个权值为Wi的根结 点，它的左右子树均为空。 二、选取左右子树 在F中选取两棵根结点权值最小的树 作为新构造的二叉树的左右子树，新 二叉树的根结点的权值为其左右子树 的根结点的权值之和。 三、删除左右子树 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步， 重复二和三两步，直到集合F中只有一棵二叉树为止。 因此，有如下分析： 1.我们需要一个功能函数对ASCII码的初始 化并需要一个数组来保存它们； 计算机学院信管专业 数据结构课程设计 题目：哈夫曼树的应用班级： 姓名：学号： 同组人姓名： 起迄日期： 课程设计地点: 指导教师： 评阅意见： 成绩评定： 评阅人：日期： 完成日期：2012年12月 目录 一、需求分析 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析和测试结果 (7) 五、心得体会和总结 (10) 六、参考文献 (10) 七、附录 (11) 一、需求分析 （一）实验要求 要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。 要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。 问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。 综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。 （二）实验任务 一个完整的系统应具有以下功能： 功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 （三）实验步骤 分步实施： 1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2）完成最低要求：完成功能1； 3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求： 1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 4) 要提供程序测试方案 5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 通达学院 算法与数据结构程序设计 题目：哈夫曼编码和译码系统 专业 学生姓名 班级学号 指导教师 指导单位 日期 教师评语 同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。 教师签名： 年月日 成绩评定 备注 一、题目要求： 题 目 ：哈夫曼编码和译码系统 基本要求： (1) 能输入字符集和各字符频度建立哈夫曼树； (2) 产生各字符的哈夫曼编码，并进行解码。 提高要求： (1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。 二、需求分析： 2.1基本思想 根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是: (1) 初始化:由给定的n 个权值{w 1, w 2,…, w n }构造n 棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T 1,T 2,…,T n }; (2) 选取与合并:在F 中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和; (3) 删除与加入:在F 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F 中; (4) 重复(2)、(3)两步,当集合F 中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树. 2.2存储结构 在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n 个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示. 图 哈夫曼树的结点结构 其中: weight parent lchild rchild i nf 目录 目录 (2) 1课程设计的目的和意义 (3) 2需求分析 (4) 3概要设计 (4) 4详细设计 (8) ￥ 5调试分析和测试结果 (11) 6总结 (12) 7致谢 (13) 8附录 (13) 参考文献 (20) . | ; 1 课程设计目的与意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 作为计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。 （ 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们 可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 2 需求分析 课题：哈夫曼编码译码器 ) 问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。问题补充：1. 从硬盘的一个文件里读出一段英语文章； 2. 统计这篇文章中的每个字符出现的次数； 3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储 结构的初态和终态进行输出； 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破 译。 具体介绍：在本课题中，我们在硬盘中预先建立一个文档，在里面编辑一篇文章。然后运行程序，调用函数读出该文章，显示在界面；再调用函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用函数构建哈夫曼树；并调用函数将哈夫曼的存储结构的初态和终态进行输出。然后调用函数对哈夫曼树进行编码，调用函数将编码写入文件；再调用对编码进行译码，再输出至界面。至此，整个工作就完成了 3 概要设计。哈夫曼树编码译码实验报告(DOC)
贪心算法构造哈夫曼树
《哈夫曼编码译码课程设计》报告
哈夫曼编码与译码的实现
哈夫曼树的建立与操作
哈夫曼编码译码系统实验报告,数据结构课程设计
哈夫曼树课程设计论文
哈夫曼树的编码和译码
哈夫曼编码译码系统实验报告,数据结构课程设计报告
哈夫曼编码与译码器_数据结构课程设计报告
完整word版哈夫曼编码译码器试验报告
哈夫曼树课程设计报告(DOC)
huffman编码译码实现文件的压缩与解压.
数据结构哈夫曼编码译码器课程设计报告(有源程序)
哈夫曼编码与译码报告
哈夫曼编码译码器实验报告(免费)
数据结构课程设计实验报告哈夫曼树的应用
哈夫曼编码和译码系统
哈夫曼编码译码器---课程设计报告
相关主题
文本预览