当前位置：文档之家 › 哈夫曼编码课设说明书

哈夫曼编码课设说明书

  • 格式：doc
  • 大小：311.00 KB
  • 文档页数：40

******************* 实践教学

*******************

计算机与通信学院 2016年秋季学期

算法与数据结构课程设计 题 目：哈夫曼的编/译码系统 敢死队问题 专业班级： 姓 名： 学 号： 指导教师： 成 绩：_______________ 目录 摘要 .......................................................................................................................... 1 一．哈夫曼码的编/译码系统 ................................................................................. 2 1.采用类语言定义相关的数据类型 ................................................................... 2 2.算法设计 ........................................................................................................... 2 3.函数的调用关系图 ........................................................................................... 5 4.调试分析 ........................................................................................................... 5 5.测试结果 ........................................................................................................... 6 6.源程序（带注释） ........................................................................................... 8

二．敢死队问题 .................................................................................................... 23 1.采用类语言定义相关的数据类型 ................................................................. 23 2.算法设计 ......................................................................................................... 24 3.函数的调用关系图 ......................................................................................... 28 4.调试分析 ......................................................................................................... 28 5.测试结果 ......................................................................................................... 30 6.源程序（带注释） ......................................................................................... 30

总结 ........................................................................................................................ 37 参考文献 ................................................................................................................ 38 致谢 ........................................................................................................................ 38 算法与数据结构课程设计

1 摘要 哈夫曼编译系统是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。因此哈夫曼编译系统能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。 敢死队问题主要是用两种数据结构方法实现敢死队问题。从1到M个数据，采用链表和队列存储，由于是轮回数数，需要循环，因此所用的链表是单向循环链表，所用的队列是循环队列。战士去执行任务，若没有完成任务，则需要把该战士的号码从队列或者链表中删除。由于要求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务，所以程序从1号到M号逐个开始计数，从计数的战士开始的第五个战士去执行任务，若没完成任务，则删除之，从被删除战士下一个号码开始计数，后边的第五个战士接着开始去执行任务，若没完成任务，则删除之，如此循环，直到最后一个战士，若最后一个战士是排长，即1号，则终止循环，记下开始计数的战士的号码即为所求。

关键词： 哈夫曼树；队列；链表；指针 算法与数据结构课程设计

2 一．哈夫曼码的编/译码系统 编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。

1.采用类语言定义相关的数据类型 哈夫曼码的编/译系统主要采用的数据结构为树和链表和数组。其中链表是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，结点可以动态生成。而树是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件： （1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根。 （2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。 （3）K中各结点，对关系N来说可以有m个后继（m>=0） 输入/输出数据： 数据类型： 数据 字符型 权值 浮点型 父结点，左右孩子结点 整型 节点数 整型 开始位置 整型

2.算法设计  构造哈夫曼树的算法 在哈夫曼树中，没有度为1的结点，这类二叉树称为严格二叉树。那么对于一颗含有n个结点的哈弗曼树共有2n-1个结点所以哈夫曼算法可以用一维数组实现。显然每个结点的存储结构都应该有一个域存放权值；构成Huffman树之后，

表A-1主要数据类型 算法与数据结构课程设计 3 为求编码需从叶子结点出发走一条从叶子到根的路径，而为译码需从根出发走一条从根到叶子的路径。对每个结点而言，既需知双亲的消息，又需知孩子结点的消息。因此，可设定一个静态三叉链表来实现。具体算法描述如下： struct hufmtreenode{//定义哈弗曼树结点数据类型 char data; float weight;//结点权值 int parent,lchild,rchild; hufmtree* BuildHuffmanTree(hufmtree *tree){//构建叶子结点已初始化的哈夫曼树 //tree中所有叶子结点已初始化 int i,j,p1,p2,m; float small1,small2; m=2*(tree->n)-1; for (i=tree->n;i{ tree->node[i].parent=-1; tree->node[i].lchild=-1; tree->node[i].rchild=-1; tree->node[i].weight=0.0; } for (i=tree->n;i{ small1=small2=MAXVAL; for (j=0;j<=i-1;j++) { if (tree->node[j].parent==-1 && tree->node[j].weight<=small1 small1=tree->node[j].weight; p1=j; for (j=0;j<=i-1;j++) { if (tree->node[j].parent==-1 && tree->node[j].weight<=small2 &&

合集下载

哈夫曼树编码译码实验报告

哈夫曼树编码译码实验报告

数据结构课程设计设计题目：哈夫曼树编码译码目录第一章需求分析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为根结点到叶结点的路径长度。

数据结构哈夫曼编码实验报告

数据结构哈夫曼编码实验报告

数据结构哈夫曼编码实验报告一、实验目的：通过哈夫曼编、译码算法的实现，巩固二叉树及哈夫曼树相关知识的理解掌握，训练学生运用所学知识，解决实际问题的能力。

二、实验内容：已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。

1、从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

2、打印每一个字符对应的哈夫曼编码。

3、对从终端读入的字符串进行编码，并显示编码结果。

4、对从终端读入的编码串进行译码，并显示译码结果。

三、实验方案设计：（对基本数据类型定义要有注释说明，解决问题的算法思想描述要完整，算法结构和程序功能模块之间的逻辑调用关系要清晰，关键算法要有相应的流程图，对算法的时间复杂度要进行分析）1、算法思想：（1）构造两个结构体分别存储结点的字符及权值、哈夫曼编码值：（2）读取前n个结点的字符及权值，建立哈夫曼树：（3）根据哈夫曼树求出哈夫曼编码：2、算法时间复杂度：（1）建立哈夫曼树时进行n到1次合并，产生n到1个新结点，并选出两个权值最小的根结点：O（n²）；（2）根据哈夫曼树求出哈夫曼编码：O（n²）。

（3）读入电文，根据哈夫曼树译码：O（n）。

四、该程序的功能和运行结果：（至少有三种不同的测试数据和相应的运行结果，充分体现该程序的鲁棒性）1、输入字符A，B，C，D，E，F及其相应权值16、12、9、30、6、3。

2、输入字符F，E，N，G，H，U，I及其相应权值30、12、23、22、12、7、9。

3、输入字符A，B，C，D，E，F，G，H，I，G及其相应权值19、23、25、18、12、67、23、9、32、33。

数字图像实验 哈夫曼编码的方法和实现1234

数字图像实验 哈夫曼编码的方法和实现1234

实验八哈夫曼编码的方法和实现一、实验目的1.掌握哈夫曼编码的基本理论和算法流程；2. 用VC++6.0编程实现图像的哈夫曼编码。

二、实验内容1．画出哈夫曼编码的算法流程；2．用VC++6.0编程实现哈夫曼编码。

三、实验步骤（1）启动VC++6.0，打开Dip工程。

（2）在菜单栏→insert→resouce→dialog→new,在对话框模版的非控制区点击鼠标右键，在弹出的对话框中选properties,设置为ID：IDD_DLG_Huffman,C标题：哈夫曼编码表。

（3）在弹出的对话框中，添加如下的按钮等控件：（4）在ResourceView栏中→Menu→选IDR_DIPTYPE ,如图在图像编码菜单栏下空的一栏中，右键鼠标，在弹出的对话框中选属性properties，在弹出的对话框中，进行如下的设置（5）右击哈夫曼编码表菜单栏，在建立的类向导中进行如下设置（6）在DipDoc.cpp中找到void CDipDoc::OnCodeHuffman()添加如下代码void CDipDoc::OnCodeHuffman(){int imgSize;imgSize = m_pDibObject->GetWidth()*m_pDibObject->GetHeight();//在点处理CPointPro类中创建用来绘制直方图的数据CPointPro PointOperation(m_pDibObject );int *pHistogram = PointOperation.GetHistogram();//生成一个对话框CHistDlg类的实例CDlgHuffman HuffmanDlg;//将绘制直方图的数据传递给CHistDlg对话框类的公有成员变量m_pnHistogramif( pHistogram != NULL ){//设置直方图数据指针HuffmanDlg.m_fFreq = pHistogram;HuffmanDlg.m_iSizeImage = imgSize;if(m_pDibObject->GetNumBits() >= 8)HuffmanDlg.m_iLeafNum=256;elseHuffmanDlg.m_iLeafNum=m_pDibObject->GetNumBits();}//显示对话框if ( HuffmanDlg.DoModal() != IDOK)return;delete [] pHistogram;}（7）在DipDoc.cpp中添加#include "DlgHuffman.h"（8）将DlgHuffman.h、DlgHuffman.cpp文件拷贝到当前工程目录文件里面；并添加到当前工程。

c语言哈夫曼树的构造及编码

c语言哈夫曼树的构造及编码

c语言哈夫曼树的构造及编码一、哈夫曼树概述哈夫曼树是一种特殊的二叉树，它的构建基于贪心算法。

它的主要应用是在数据压缩和编码中，可以将频率高的字符用较短的编码表示，从而减小数据存储和传输时所需的空间和时间。

二、哈夫曼树的构造1. 哈夫曼树的定义哈夫曼树是一棵带权路径长度最短的二叉树。

带权路径长度是指所有叶子节点到根节点之间路径长度与其权值乘积之和。

2. 构造步骤(1) 将待编码字符按照出现频率从小到大排序。

(2) 取出两个权值最小的节点作为左右子节点，构建一棵新的二叉树。

(3) 将新构建的二叉树加入到原来排序后队列中。

(4) 重复上述步骤，直到队列只剩下一个节点，该节点即为哈夫曼树的根节点。

3. C语言代码实现以下代码实现了一个简单版哈夫曼树构造函数：```ctypedef struct TreeNode {int weight; // 权重值struct TreeNode *leftChild; // 左子节点指针struct TreeNode *rightChild; // 右子节点指针} TreeNode;// 构造哈夫曼树函数TreeNode* createHuffmanTree(int* weights, int n) {// 根据权值数组构建节点队列，每个节点都是一棵单独的二叉树TreeNode** nodes = (TreeNode**)malloc(sizeof(TreeNode*) * n);for (int i = 0; i < n; i++) {nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));nodes[i]->weight = weights[i];nodes[i]->leftChild = NULL;nodes[i]->rightChild = NULL;}// 构建哈夫曼树while (n > 1) {int minIndex1 = -1, minIndex2 = -1;for (int i = 0; i < n; i++) {if (nodes[i] != NULL) {if (minIndex1 == -1 || nodes[i]->weight < nodes[minIndex1]->weight) {minIndex2 = minIndex1;minIndex1 = i;} else if (minIndex2 == -1 || nodes[i]->weight < nodes[minIndex2]->weight) {minIndex2 = i;}}}TreeNode* newNode =(TreeNode*)malloc(sizeof(TreeNode));newNode->weight = nodes[minIndex1]->weight + nodes[minIndex2]->weight;newNode->leftChild = nodes[minIndex1];newNode->rightChild = nodes[minIndex2];// 将新构建的二叉树加入到原来排序后队列中nodes[minIndex1] = newNode;nodes[minIndex2] = NULL;n--;}return nodes[minIndex1];}```三、哈夫曼编码1. 哈夫曼编码的定义哈夫曼编码是一种前缀编码方式，它将每个字符的编码表示为二进制串。