当前位置:文档之家› 哈夫曼编码译码

哈夫曼编码译码

哈夫曼编码译码
哈夫曼编码译码

《数据结构》

课程设计报告

设计题目哈夫曼编码译码

学院名称信息工程学院

专业班级计算机科学与技术2班姓名

学号

摘要

Huffman编码是一种可变长编码方式,是二叉树的一种特殊转化形式。它的原理是:将使用次数多的代码转换成长度较短的编码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。本文根据Huffman编码原理,在详细设计中,根据权值和最小的根本原则,我们输入要编码的字符集及其它的权值,再根据在概要设计中提到的节点Node类,算法SuanFa类以及主类JieMian类,建立哈夫曼树,并进行编码,最后输出哈夫曼编码。

在完成Huffman编码后,我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同,译码过程中,我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较,译出一个字符后,循环比较下一个字符的编码,直到所有二进制码全部译出为止。

在编码和译码的过程中,我们遇到很多问题,诸如算法、语法问题,但我们都通过不断的分析,和调试将这些问题一一解决,最终建立了一个完整的编/译码系统。

关键词:Huffman编码树;最优二叉树;编码;译码

Abstract

Huffman coding is a encoding of variable length and a special transformation form of the binary tree. Its principle is: the code that be used more often will be changed into the code of shorter lengths, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter the character set which will be used to coding and their weights. Secondly, according to the fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class SuanFa,and class JieMian. At last, the computer will output Huffman coding on user interface.

And then, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the character set one by one during the processs of decoding .And then, the cycle of the next character encoding will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.

During the process of coding and decoding, we encounter many problems, such as the problem on arithmetic and grammar. However, we try our best to solve these problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.

Key Words:Huffman coding tree;optimal binary tree;coding;decoding

目录

摘要………………………………………………………………I ABSTRACT…………………………………………………… II 1.绪论……………………………………………………………

1.1设计目的 (1)

1.2问题描述 (1)

1.3设计思想 (1)

2. 概要设计 (2)

3.需求分析 (4)

4.详细设计 (5)

5.测试数据与实验结果 (10)

6.课程设计总结 (14)

参考文献 (15)

附录(源程序代码) (16)

绪论

1.1设计目的

学习数据结构与算法的最终目的是解决实际的应用问题,特别是非数值计算类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析,在完成设计和编程大型作业的过程中,深化对数据结构与算法课程中基本概念、理论和方法的理解;训练综合运用所学知识处理实际问题的能力,使同学的程序设计与调试水平有一个明显的提高。

1.2问题描述

利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。

1.3.设计思想

哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这种方法是由David.A.Huffman发展起来的。例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

2.概要设计总体流程图如下图

2.1 哈夫曼树的建立

赫夫曼树的建立由赫夫曼算法的定义可知,初始森林中共有n棵只含有根结点的二叉树。算法的第二步是:将当前森林中的两棵根结点权值最小的二叉树,合并成一棵新的二叉树;每合并一次,森林中就减少一棵树,产生一个新结点。显然要进行n-1次合并,所以共产生n-1个新结点,它们都是具有两个孩子的分支结点。由此可知,最终求得的赫夫曼树中一共有2n-1个结点,其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储赫夫曼树中的结点。

2.2哈夫曼编码

要求电文的赫夫曼编码,必须先定义赫夫曼编码类型,根据设计要求和实际需要定义的类型如下:

typedet struct {

char ch; // 存放编码的字符

char bits[N+1]; // 存放编码位串

int len; // 编码的长度

}CodeNode; // 编码结构体类型

2.3代码文件的译码

译码的基本思想是:读文件中编码,并与原先生成的赫夫曼编码表比较,遇到相等时,即取出其对应的字符存入一个新串中。

3.需求分析

3.1:初始化(Initialization)。

从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。输出哈夫曼树,及各字符对应的编码。

3.2:编码(Encoding)与译码(Decoding)。

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

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

3.2.3印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中。

3.3:印哈夫曼树(Tree Printing)。

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

4.详细设计

4.1哈夫曼树的存储结构描述

typedef struct

{

unsigned int weight;

unsigned int parent, lchild, rchild;

}HTNode, *HuffmanTree;

4.2 哈弗曼树的算法

void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n

{

int i,k,lnode,rnode;

int min1,min2;

for (i=0;i<2*n-1;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1 for (i=n;i<2*n-1;i++) //构造哈夫曼树

{

min1=min2=32767; //int的范围是-32768—32767

lnode=rnode=-1; //lnode和rnode记录最小权值的两个结点位置

for (k=0;k<=i-1;k++)

{

if (ht[k].parent==-1) //只在尚未构造二叉树的结点中查找

{

if (ht[k].weight

{

min2=min1;rnode=lnode;

min1=ht[k].weight;lnode=k;

}

else if (ht[k].weight

{

min2=ht[k].weight;rnode=k;

}

}

}

ht[lnode].parent=i;ht[rnode].parent=i; //两个最小节点

的父节点是i

ht[i].weight=ht[lnode].weight+ht[rnode].weight; //两个最小节点的父节点权值为两个最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode; //父节点的左节点和右节点

}

}

4.3哈弗曼编码

void CreateHCode(HTNode ht[],HCode hcd[],int n)

{

int i,f,c;

HCode hc;

for (i=0;i

hc.start=n;c=i;

f=ht[i].parent;

while (f!=-1) //循序直到树根结点结束循环{

if (ht[f].lchild==c) //处理左孩子结点

hc.cd[hc.start--]='0';

else //处理右孩子结点

hc.cd[hc.start--]='1';

c=f;f=ht[f].parent;

}

hc.start++; //start指向哈夫曼编码hc.cd[]中最开始字符

hcd[i]=hc;

}

}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表{

int i,k;

printf(" 输出哈夫曼编码:\n");

for (i=0;i

{

printf(" %c:\t",ht[i].data);

for (k=hcd[i].start;k<=n;k++) //输出所有data中数据的编码

{

printf("%c",hcd[i].cd[k]);

}

printf("\n");

}

}

void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数

{

char string[MAXSIZE];

int i,j,k;

scanf("%s",string); //把要进行编码的字符串存入string数组中

printf("\n输出编码结果:\n");

for (i=0;string[i]!='#';i++) //#为终止标志

{

for (j=0;j

{

if(string[i]==ht[j].data) //循环查找与输入字符相同的编号,相同的就输出这个字符的编码

{

for (k=hcd[j].start;k<=n;k++)

{

printf("%c",hcd[j].cd[k]);

}

break; //输出完成后跳出当前for循环}

}

}

}

4.4哈弗曼译码

void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数

{

char code[MAXSIZE];

int i,j,l,k,m,x;

scanf("%s",code); //把要进行译码的字符串存入code数组中

while(code[0]!='#')

for (i=0;i

{

m=0; //m为想同编码个数的计数器

for (k=hcd[i].start,j=0;k<=n;k++,j++) //j为记录所存储这个字符的编码个数

{

if(code[j]==hcd[i].cd[k]) //当有相同编码时m值加1 m++;

}

if(m==j) //当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据

{

printf("%c",ht[i].data);

for(x=0;code[x-1]!='#';x++) //把已经使用过的code数组里的字符串删除

{

code[x]=code[x+j];

}

}

}

}

4.5主函数

void main()

{

int n=26,i;

char orz,back,flag=1;

char

str[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y' ,'Z'}; //初始化

int

fnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16 }; //初始化

HTNode ht[M]; //建立结构体

HCode hcd[N]; //建立结构体

for (i=0;i

{

ht[i].data=str[i];

ht[i].weight=fnum[i];

}

while (flag) //菜单函数,当flag为0时跳出循环

4.6显示部分源程序:

{

printf("\n");

printf(" ********************************");

printf("\n ** 1---------------显示编码**");

printf("\n ** 2---------------进行编码**");

printf("\n ** 3---------------进行译码**");

printf("\n ** 4---------------退出**\n");

printf(" * **********************************");

printf("\n");

printf(" 请输入选择的编号:");

scanf("%c",&orz);

switch(orz)

{

case 'a':

case 'A':

system("cls"); //清屏函数

CreateHT(ht,n);

CreateHCode(ht,hcd,n);

DispHCode(ht,hcd,n);

printf("\n按任意键返回...");

getch();

system("cls");

break;

case 'b':

case 'B':

system("cls");

printf("请输入要进行编码的字符串(以#结束):\n");

editHCode(ht,hcd,n);

printf("\n按任意键返回...");

getch();

system("cls");

break;

case 'c':

case 'C':

system("cls");

DispHCode(ht,hcd,n);

printf("请输入编码(以#结束):\n");

deHCode(ht,hcd,n);

printf("\n按任意键返回...");

getch();

system("cls");

break;

case 'd':

case 'D':

flag=0;

break;

default:

system("cls");

}}}

5.测试数据与实验结果

用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM 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 .

5.1初始化界面截图如下

5.2选A时的显示结果截图如下

5.3选择B时的显示结果截图如下

5.4选C时的显示结果截图如下

6.课程设计总结

其实很多细节,只有在去写的时候才会发现,才会暴露出来,书本上的知识是很少的,很多东西,要靠自己平时多去练习,在练习中产生错误,通过上网查找等途径解决错误,以增长自己的知识点和调试能力。程序这种东西,就是写出来就感觉很简单,想着也不能,但是实现的时候,有时候会有这里那里的小错误阻碍程序的正确运行,很多时候,与其说是写程序不如说是对细节的检测。

在我自己课程设计中,就在编写好源代码后的调试中出现了不少的错误,遇到了很多麻烦

及困难,我的调试及其中的错误和我最终找出错误,修改为正确的能够执行的程序中,通过

分析,我学到了:

在定义头文件时可多不可少,即我们可多写些头文件,肯定不会出错,但是若没有定义

所引用的相关头文件,必定调试不通过;

在执行译码操作时,不知什么原因,总是不能把要编译的二进制数与编译成的字符用连

接号连接起来,而是按顺序直接放在一起,视觉效果不是很好。还有就是,很遗憾的是,我

们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能,这是我们设计的失

败之处。

通过本次数据结构的课程设计,我学习了很多在上课没懂的知识,并对求哈夫曼树及哈

夫曼编码/译码的算法有了更加深刻的了解,更巩固了课堂中学习有关于哈夫曼编码的知识,

真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做,而是首先要先对

它有个大概的了解,接着再详细地分析每一步怎么做,无论自己以前是否有处理过相似的问

题,只要按照以上的步骤,必定会顺利地做出来。

这次课程设计,我在编辑中犯了不应有的错误,设计统计字符和合并时忘记应该怎样保

存数据,对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏,我的程序有了更

高的质量。

参考文献

A:书籍资料

[1] 李春葆《数据结构教程上机实验指导》北京:清华大学出版社

[2] 严蔚敏吴伟民《数据结构(C语言版)》北京:清华大学出版社

[3] 苏仕华《数据结构课程设计》北京:机械工业出版社B:网络资料

[1] 哈夫曼编/译码器(课程设计)

https://www.doczj.com/doc/c99508254.html,/living/blog/item/d302367a65804eed2e73b32b.html [2]哈夫曼编码

https://www.doczj.com/doc/c99508254.html,/hihinet/blog/item/432169091693efce3bc763ab.html

附录(源程序代码)

#include

#include //要用system函数要调用的头文件

#include //用getch()要调用的头文件

#include

#define N 50 //义用N表示50叶节点数

#define M 2*N-1 //用M表示节点总数当叶节点数位n时总节点数为2n-1

#define MAXSIZE 100

typedef struct

{

char data; //结点值

int weight; //权值

int parent; //双亲结点

int lchild; //左孩子结点

int rchild; //右孩子结点

}HTNode;

typedef struct

{

char cd[N]; //存放哈夫曼码

int start; //从start开始读cd中的哈夫曼码

}HCode;

void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n

{

int i,k,lnode,rnode;

int min1,min2;

for (i=0;i<2*n-1;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1 for (i=n;i<2*n-1;i++) //构造哈夫曼树

{

min1=min2=32767; //int的范围是-32768—32767

lnode=rnode=-1; //lnode和rnode记录最小权值的两个结点位置

for (k=0;k<=i-1;k++)

{

if (ht[k].parent==-1) //只在尚未构造二叉树的结点中查找

{

if (ht[k].weight

{

min2=min1;rnode=lnode;

min1=ht[k].weight;lnode=k;

}

else if (ht[k].weight

{

min2=ht[k].weight;rnode=k;

}

}

}

ht[lnode].parent=i;ht[rnode].parent=i; //两个最小节点的父节点是i

ht[i].weight=ht[lnode].weight+ht[rnode].weight; //两个最小节点的父节点权值为两个最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode; //父节点的左节点和右节点

}

}

void CreateHCode(HTNode ht[],HCode hcd[],int n)

{

int i,f,c;

HCode hc;

for (i=0;i

hc.start=n;c=i;

f=ht[i].parent;

while (f!=-1) //循序直到树根结点结束循环{

if (ht[f].lchild==c) //处理左孩子结点

hc.cd[hc.start--]='0';

else //处理右孩子结点

hc.cd[hc.start--]='1';

c=f;f=ht[f].parent;

}

hc.start++; //start指向哈夫曼编码hc.cd[]中最开始字符

hcd[i]=hc;

}

}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表{

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

JAVA语言实验报告 学院计算机工程学院班级计算1013 姓名佐伊伦学号 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程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中,我们不但有自己的独立思考,还借助各种参考文献来帮助我们完成系统。更为重要的是,我们同学之间加强了交流,在对问题的认识方面可以交换不同的意见。同时,师生之间的互动也随之改善,我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节,但是容易忽略实验的总结,忽略实验报告的撰写。通过这次实验让我们明白:作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样,我们的综合素质才会有好的提高。

哈夫曼树编码译码实验报告(DOC)

数据结构课程设计设计题目:哈夫曼树编码译码

目录 第一章需求分析 (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) 编码文件的译码。

《哈夫曼编码译码课程设计》报告

计算机与信息工程系 《实践环节名称》报告 专业:计算机科学与技术 班级:******** 学号:********* 姓名:杨明英 报告完成日期: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中读取编码

哈夫曼编码译码

哈夫曼编码/译码 一、【实验内容】 【问题描述】 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统. 【基本要求】:一个完整的系统应以下功能: (1) I. 初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中. (2) E. 编码(Encoding)。利用已建立好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中. (3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的Cod eFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePri n中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。

测试数据: (1) 利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码:“THIS PROGRAM 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 1 6 1 二、实验目的 树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.

哈夫曼编码译码系统实验报告,数据结构课程设计报告

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)

哈夫曼编码与译码的实现

数据结构课程设计评阅书

2011—2012学年第一学期 专业:信息管理与信息系统学号: 1021024016 姓名:万永馨 课程设计名称:数据结构课程设计 设计题目:哈夫曼编码与译码的实现 完成期限:自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容(可另加附页): 该设计题目将按以下要求完成: 哈夫曼编码与译码是信息传输中应用的经典算法,运用C或VC++结合数据结构等基础知识,按 以下要求编程实现各种进制的转换。 任务要求:1)阐述设计思想,画出流程图;2)需要对哈夫曼编码/译码的相关原理有所了解,设计数 据结构,建立必要的信息数据文件(最好存储成外部文件),并分析完成用户所需的基本操作功能;3)实现给定信息的编码和译码功能;4)应有较好的界面设计,说明程序测试方法;5)按照格式要 求完成课程设计说明书。 设计要求: 1)问题分析和任务定义:根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么?(而不是怎么做?)限制条件是什么?确定问题的输入数据集合。 2)逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的 原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调 用关系图; 3)详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统 功能,使得系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精, 写出数据存储结构的类型定义,写出函数形式的算法框架; 4)程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言, 使程序中逻辑概念清楚; 5)程序调试与测试:能够熟练掌握调试工具的各种功能,设计测试数据确保程序正确。调试正 确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果; 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算 法的时间、空间复杂性分析; 7)编写课程设计报告; 以上要求前三个阶段的任务完成后,将设计说明书的草稿交指导老师面审,审查合格方可进入 后续阶段的工作。设计工作结束,经指导老师验收合格后将设计说明书装订,并答辩。

哈夫曼编码译码系统实验报告,数据结构课程设计

安徽大学 数据结构课程设计报告项目名称:哈弗曼编/译码系统的设计 与实现 姓名:鉏飞祥 学号: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

huffman编码译码实现文件的压缩与解压.

数据结构 课程设计 题目名称: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。

哈夫曼树的编码和译码

#include"stdafx.h" #include"stdio.h" #include"conio.h" #include #include #include using namespace std; #define maxbit 100 #define Maxvalue 2000//最大权值整数常量#define Maxleaf 100//最大叶子结点数 #define size 300//0、串数组的长度 static int n;//实际的叶子结点数 struct HNodeType { int weight; int parent; int lchild; int rchild; int ceng;//结点相应的层数 char ch;//各结点对应的字符 }; struct HCodeType { int bit[maxbit];//存放编码的数组 int start;//编码在数组中的开始位置}; static HNodeType *HuffNode;//定义静态指针HNodeType *init()//初始化静态链表 { HuffNode=new HNodeType[2*n-1]; for(int i=0;i<2*n-1;i++) { HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; HuffNode[i].ceng=-1; HuffNode[i].ch='0'; } return HuffNode; }

哈夫曼编码译码器

哈夫曼编码译码器

哈夫曼编码译码器 学院班级: 信息工程学院软件1501 指导教师: 朱俊武 小组成员: 刘洋蒋佳烨冀若含 本人学号: 151303107 报告书写: 冀若含 学生成绩:

目录 一、总体介绍·····························03-04 二、详细设计·····························04-11 三、运行测试·····························11-12 四、课设总结·····························13-13 五、附录代码·····························13-19

一、总体介绍 1.1任务概述 我们小组做了两个版本,其中一个为文件操作版,另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树,给出各个字符的哈夫曼编码,加密操做,整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据结构》(c语言版)。 其中文件操作版的具体实现为: ○1能够实现对26个小写字母外加空格进行哈夫曼编码,并能够对一整篇文章(有小写字母和空格组成)进行加密,生成密码文件。最后根据生成的密码翻译出原文并存档。 ○2在使用程序时,使用者只需要对ToBetran文件进行原文的输入(使用小写字母或空格),加密和解密功能由程序自主来完成。 ○3程序运行的过程中会输出进行编码的26个小写字母和空格(字符型),并输出其对应的权值(整型)。还输出字符的编码及生成的密文。最后输出解密后的原文。 键盘操作版为: ○1要求从键盘输入字符集和字符的权值,大部分字符均可输入,需要各个字符的权值不能相同。 ○2利用输入的权值建立哈夫曼树,得到每个字符的前缀编码。 ○3输入字符串,程序对其进行加密。 ○4输入密文(1010101……………..)对密文进行解密。

哈夫曼编码译码的设计与实现数据结构课程设计

《数据结构》课程设计题目--哈夫曼编码/译码的设计与实现 班级:13数据库一班 学号:1315925280 姓名:吴松 指导教师:王超

目录 目录 (1) 一、需求分析 (2) 二、设计要求 (2) 三、概要设计 (2) 1、流程图 (2) 2、设计包含的几个部分 (4) 四、详细设计 (2) 五、显示结果………………………………………………9. 六、心得体会 (10) 七、参考文献 (11) 哈夫曼编码译码 一、需求分析

在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。赫夫曼编码的应用很广泛,利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串。 二、设计要求 对输入的一串电文字符实现赫夫曼编码,再对赫夫曼编码生成的代码串进行译码,输出电文字符串。通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度能尽可能短,即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为∑WiLi。若将此对应到二叉树上,Wi为叶结点的权,Li为根结点到叶结点的路径长度。那么,∑WiLi 恰好为二叉树上带权路径长度。因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵赫夫曼树,此构造过程称为赫夫曼编码。设计实现的功能: (1) 赫夫曼树的建立; (2) 赫夫曼编码的生成; (3) 编码文件的译码。 三、概要设计 哈夫曼编\译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。 在数据通信中,经常需要将传送的文字转换成由二进制字符0、1组成的二进制串,称之为编码。构造一棵哈夫曼树,规定哈夫曼树中的左分之代表0,右分支代表1,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。 (1)其主要流程图如图1-1所示。

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

沈阳航空航天大学 课程设计报告 课程设计名称:数据结构课程设计 课程设计题目:实现哈夫曼编码和译码器 院(系):计算机学院 专业:计算机科学与技术 班级: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)根据哈夫曼树对二进制密文进行译码。

完整word版哈夫曼编码译码器试验报告

中北大学 数据结构 课程设计说明书 学生姓名: 郝晨栋学号: 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抽象数据类型定义

哈夫曼编码译码器---课程设计报告

目录 目录 (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 概要设计。

哈夫曼编码和译码系统

通达学院 算法与数据结构程序设计 题目:哈夫曼编码和译码系统 专业 学生姓名 班级学号 指导教师 指导单位 日期

教师评语 同学出勤率(满勤、较高、一般,较低),学习态度(端正、较端正、一般、较差),程序设计基础(好、较好、一般、较差),演示程序(已经、没有)达到了基本要求,算法设计(好、较好、一般),界面友好程度(好、较好、一般),答辩过程中回答问题(准确、较准确、错误率较高),撰写报告格式(规范、一般)、内容(丰满、简单)、表述(清晰、一般、不清楚),(圆满、较好、基本)完成了课题任务。 教师签名: 年月日 成绩评定 备注

一、题目要求: 题 目 :哈夫曼编码和译码系统 基本要求: (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

哈夫曼编码译码器实验报告免费

哈夫曼编码译码器实验报告(免费)

————————————————————————————————作者:————————————————————————————————日期:

问题解析与解题方法 问题分析: 设计一个哈夫曼编码、译码系统。对一个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码的初始化并需要一个数组来保存它们; 2.定义代表森林的数组,在创建哈夫曼树的过程当中保存被选中的字符,即给定报文 中出现的字符,模拟哈夫曼树选取和删除左右子树的过程; 3.自底而上地创建哈夫曼树,保存根的地址和每个叶节点的地址,即字符的地址,然 后自底而上检索,首尾对换调整为哈夫曼树实现哈弗曼编码; 4.从哈弗曼编码文件当中读入字符,根据当前字符为0或者1的状况访问左子树或者 右孩子,实现解码; 5.使用文件读写操作哈夫曼编码和解码结果的写入; 解题方法: 结构体、数组、类的定义: 1.定义结构体类型的signode 作为哈夫曼树的节点,定义结构体类型的hufnode 作为

哈夫曼编码与译码报告

一、设计思想 程序要求: 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成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代码进行翻译,直至文件密文结束为止。于是就得到了原先被加密的那串字符串。

哈夫曼编码译码系统课程设计实验报告(含源代码C++_C语言)

目录 摘要………………………………………………………………………..………………II Abstract …………………………………………………………………………..………... II 第一章课题描述 (1) 1.1 问题描述 (1) 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章设计简介及设计方案论述 (2) 2.1 设计简介 (2) 2.2 设计方案论述 (2) 2.3 概要设计 (2) 第三章详细设计 (4) 3.1 哈夫曼树 (4) 3.2哈夫曼算 法 (4) 3.2.1基本思 想 (4) 3.2.2存储结 构 (4)

3.3 哈夫曼编码 (5) 3.4 文件I/O 流 (6) 3.4.1 文件流 (6) 3.4.2 文件的打开与关闭 (7) 3.4.3 文件的读写 (7) 3..5 C语言文件处理方式…………………………………………………………………… 第四章设计结果及分析 (8) 4.1 设计系统功能 (8) 4.2 进行系统测试 (8) 总结 (13) 致谢 (14) 参考文献 (15) 附录主要程序代码 (16) 摘要 在这个信息高速发展的时代,每时每刻都在进行着大量信息的传递,到处都离不开信息,它贯穿在人们日常的生活生产之中,对人们的影响日趋扩大,而利用哈夫曼编码

进行通信则可以大大提高信道利用率,缩短信息传输时间,降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润,这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性,以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时,培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法,增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统,实现对给定报文的编码和译码,并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序,对将所学到的知识运用到实践中,具有很好的学习和研究价值. 关键词:信息;通讯;编码;译码;程序 Abstract This is a date that information speeding highly development and transmit

相关主题
相关文档 最新文档