用哈夫曼编码C语言实现文件压缩
《用哈夫曼编码实现文件压缩》
实验报告
课程名称数据结构B 实验学期 2012 至 2013 学年第一学期
学生所在系部计算机学院
年级 2011 专业班级信管B111 学生姓名学号
任课教师兰芸
实验成绩
用哈夫曼编码实现文件压缩
1、了解文件的概念。
2、掌握线性链表的插入、删除等算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。
微型计算机、Windows 系列操作系统、Visual C++6.0软件
根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。
（1）构造Hufffman树的方法—Hufffman算法
构造Huffman树步骤：
I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，
令起权值为wj。
II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。
III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。
IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。
（2）Huffman编码：数据通信用的二进制编码
思想：根据字符出现频率编码，使电文总长最短
编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。
(3) 解压
根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。
压缩的代码
#include
#include
#include
#include
struct head
{
unsigned char b; /*the charactor*/
long count; /*the frequency*/
long parent,lch,rch; /*make a tree*/
char bits[256]; /*the haffuman code*/
}
header[512],tmp;
void yasuo() /*压缩*/
{
char filename[255],outputfile[255],buf[512];
unsigned char c; char wenjianming[255];
long i,j,m,n,f;
long min1,pt1,flength;
FILE *ifp,*ofp;
printf("输入文件地址及文件名:");
gets(filename);
ifp=fopen(filename,"rb"); /*打开源文件*/
while(ifp==NULL)
{ printf("打开文件出错\n");
printf("重新输入文件地址及文件名");
gets(filename);
ifp=fopen(filename,"rb");
}
printf("输入压缩后的文件地址和文件名及后缀:");
gets(wenjianming);
ofp=fopen(wenjianming,"wb"); /*创建并打开目的文件*/ while(ofp==NULL)
{printf("重新输入压缩后的文件地址和文件名及后缀:");
ofp=fopen(wenjianming,"wb");
}
flength=0;
while(!feof(ifp)) /*读取ifp文件*/
{
fread(&c,1,1,ifp); /*按位读取*/
header[c].count++;
flength++;
}
flength-1;
header[c].count-1; /*读取文件结束*/
for(i=0;i<512;i++) /*构造哈弗曼树*/
{
if(header[i].count!=0)
header[i].b=(unsigned char)i;
else
header[i].b=0;
header[i].parent=-1;
header[i].lch=header[i].rch=-1;
}
for(i=0;i<256;i++)
{
for(j=i+1;j<256;j++)
{
if(header[i].count { tmp=header[i]; header[i]=header[j]; header[j]=tmp; } } } for(i=0;i<256;i++) if(header[i].count==0) break; n=i; m=2*n-1; for(i=n;i { min1=999999999; for(j=0;j { if(header[j].parent!=-1) continue; if(min1>header[j].count) { pt1=j; min1=header[j].count; continue; } } header[i].count=header[pt1].count; header[pt1].parent=i; header[i].lch=pt1; min1=999999999; for(j=0;j { if(header[j].parent!=-1) continue; if(min1>header[j].count) { pt1=j; min1=header[j].count; continue; } } header[i].count+=header[pt1].count; header[i].rch=pt1; header[pt1].parent=i; } for(i=0;i { f=i; header[i].bits[0]=0; while(header[f].parent!=-1) { j=f; f=header[f].parent; if(header[f].lch==j) { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='0'; } else { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='1'; } } } /*哈弗曼构造结束*/ fseek(ifp,0,SEEK_SET); /*把文件指针指向文件的开头*/ fwrite(&flength,sizeof(int),1,ofp); //把哈弗曼代码写入ofp文件fseek(ofp,8,SEEK_SET); buf[0]=0; f=0; pt1=8; while(!feof(ifp)) { c=fgetc(ifp); //从流中读取一个字符，并增加文件指针的位置f++; for(i=0;i { if(c==header[i].b) break; } strcat(buf,header[i].bits); //把header[i].bits所指字符串添加到buf结尾处 j=strlen(buf); //计算字符串buf的长度 c=0; while(j>=8) { for(i=0;i<8;i++) { if(buf[i]=='1') c=(c<<1)|1; else c=c<<1; } fwrite(&c,1,1,ofp); pt1++; strcpy(buf,buf+8); j=strlen(buf); } if(f==flength) break; } if(j>0) { strcat(buf,"00000000"); for(i=0;i<8;i++) { if(buf[i]=='1') c=(c<<1)|1; else c=c<<1; } fwrite(&c,1,1,ofp); pt1++; } fseek(ofp,4,SEEK_SET); /*fseek 用于二进制方式打开的文件,移动文件读写指针位置.第一个是文件流,第3个是指针零点位置,第2个是把指针移动到的地点. */ fwrite(&pt1,sizeof(long),1,ofp); /*是要输出数据的地址,每次写入的位数,数据项的个数，目标文件地址*/ fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;i { fwrite(&(header[i].b),1,1,ofp); c=strlen(header[i].bits); fwrite(&c,1,1,ofp); j=strlen(header[i].bits); if(j%8!=0) /*按八位读取*/ { for(f=j%8;f<8;f++) strcat(header[i].bits,"0"); } while(header[i].bits[0]!=0) { c=0; for(j=0;j<8;j++) { if(header[i].bits[j]=='1') c=(c<<1)|1; else c=c<<1; } strcpy(header[i].bits,header[i].bits+8); /*把从header[i].bits+8地址开始且含有NULL结束符的字符串赋值到以header[i].bits开始的地址空间*/ fwrite(&c,1,1,ofp); } } fclose(ifp); fclose(ofp); printf("压缩成功\n"); } void main() /*主函数*/ {printf("输入a开始压缩\n"); printf("输入b结束压缩\n"); while(1) { char c; c=getch(); if(c=='a') yasuo(); else { if(c=='b') return;} } } 压缩的图解 解压的代码 #include #include #include #include struct head { unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tree*/ char bits[256]; /*the haffuman code*/ } header[512],tmp; void jieya() /*解压*/ { char filename[255],outputfile[255],buf[255],bx[255]; unsigned char c; char wenjianming[255]; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf("要解压的文件："); gets(filename); ifp=fopen(filename,"rb"); /*打开源文件*/ while(ifp==NULL) { printf("打开文件出错\n"); printf("重新输入文件地址及文件名"); gets(filename); ifp=fopen(filename,"rb"); } printf("输入解压后的文件地址和文件名及后缀:"); gets(wenjianming); ofp=fopen(wenjianming,"wb"); /*创建并打开目的文件*/ while(ofp==NULL) { ofp=fopen("d:\\123\\解压的文件.txt","wb"); } fread(&flength,sizeof(long),1,ifp); fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i { fread(&header[i].b,1,1,ifp); fread(&c,1,1,ifp); p=(long)c; header[i].count=p; header[i].bits[0]=0; if(p%8>0) m=p/8+1; else m=p/8; for(j=0;j { fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l--) { strcat(header[i].bits,"0"); } strcat(header[i].bits,buf); } header[i].bits[p]=0; } for(i=0;i { for(j=i+1;j { if(strlen(header[i].bits)>strlen(header[j].bits)) { tmp=header[i]; header[i]=header[j]; header[j]=tmp; } } } p=strlen(header[n-1].bits); fseek(ifp,8,SEEK_SET); m=0; bx[0]=0; while(1) { while(strlen(bx)<(unsigned int)p) { fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l--) { strcat(bx,"0"); } strcat(bx,buf); } for(i=0;i { if(memcmp(header[i].bits,bx,header[i].count)==0) break; } strcpy(bx,bx+header[i].count); c=header[i].b; fwrite(&c,1,1,ofp); m++; if(m==flength) break; } fclose(ifp); fclose(ofp); printf("解压成功\n"); return; } void main() /*主函数*/ {printf("输入a开始解压\n"); printf("输入b结束解压\n"); while(1) { char c; c=getch(); if(c=='a') jieya(); else { if(c=='b') return;} } } 压缩前的文件夹中的内容 压缩后的文件夹中的内容 解压后文件夹中的内容 数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 131 学号：1308060312 学生姓名：谢进 指导教师：叶洁 2015年7 月12 日 设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 1、熟悉树的二叉树的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100），对这六种字符进行哈夫曼编码。 设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。 #include 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫 #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 摘要：哈夫曼树是带权路径长度（WPL）最小的二叉树，通过对哈夫曼算法的研究，提出一种求取哈夫曼树带权路径长度的计算方法和应用。 关键词：哈夫曼算法、二叉树、WPL、编码 1 引言： 哈夫曼树是一种特殊的二叉树，又称最优二叉树：假设有一组（无序）实数｛w1,w2,w3,w4,…,wm｝，现要构造一棵以wi（i=1，2，3，4…，m）为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。若l表示从根到第i个外部结点的路径长度，m为外部结点的个数，wi 为第i个外部结点的权值，则有WPL=∑wili（0 实验6：哈夫曼树及哈夫曼编码的算法实现 实验所需 学时数 2学时 实验目的1)掌握哈夫曼树的基本概念及其存储结构； 2)掌握哈夫曼树的建立算法； 3)掌握哈夫曼树的应用（哈夫曼编码和译码）。 实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。 实验所需 器材 计算机及VC++ 6.0软件 内容要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树 2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据： 输入字符串“this*program*is*my*favourite”，完成这28个字符的编码和译码。 实验结果 1、演示程序运行结果。 2、说明调试过程中出现的现象 学生实验评价依据： 优：实验认真、刻苦，有钻研精神，不无故缺席。 良：能认真对待实验，不无故缺席。 中：基本能认真对待实验，不无故缺席。 差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。 #include c++数据结构实验哈夫曼树 数据结构实验报告 1．实验要求 i.实验目的: （1）掌握二叉树基本操作的实现方法 （2）掌握二叉树基本操作的实现方法 （3）了解哈夫曼树的思想和相关概念 （4）学习使用二叉树解决实际问题的能力 （5）熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方法。 （6）熟悉设计算法的过程 （7）进一步掌握指针、异常处理的使用 ii.实验内容： 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度 的字符串s进行统计，统计每个字符的频 度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经 建好的赫夫曼树进行编码，并将每个字符 的编码输出。 3、编码(Encoding)：根据编码表对输入 的字符串进行编码，并将编码后的字符串 输出。 4、译码(Decoding)：利用已经建好的赫 夫曼树对编码后的字符串进行译码，并输 出译码结果。 5、打印(Print)：以直观的方式打印赫夫 曼树（选作） 6、计算输入的字符串编码前和编码后的 长度，并进行分析，讨论赫夫曼编码的压 缩效果。 测试数据： I love data Structure, I love Computer.I will try my best to study data structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现 的次数统计频度，对没有出现的 字符一律不用编码。 iii.代码要求： 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析 树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是每个结点最多两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。 2.1 存储结构 1.结点结构的存储方式： 题目：哈夫曼树应用 学生姓名：谢辉 学号： 201317010201 专业班级：计科13102 同组姓名：赵丽娜 指导教师：徐晓蓉 设计时间：2014年下学期第18周 目录 一、需求分析 (3) 1. 分析问题 (3) 2. 确定解决方案 (3) 3. 输入的形式和输入值的范围 (3) 4.输出的形式 (3) 5.程序所能达到的功能 (3) 二、概要设计 (4) 1. 主程序的流程图： (4) 2．程序中数据类型的定义： (5) 3．各程序模块之间的层次(调用)关系： (5) 三、详细设计 (6) 1．哈夫曼树存储及类的定义： (6) 2.哈夫曼树的基本操作: (6) 3.主函数 (6) 四、调试分析和测试结果 (8) 1. 测试数据及其输出结果： (8) 2. 调试过程中遇到的问题及解决办法: (12) 五、总结 (13) 六、参考文献 (13) 七、致谢 (13) 八、附录 (13) 2 一、需求分析 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 （1）I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n 个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P:打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每 3 2009级数据结构实验报告 实验名称：实验三——哈夫曼编/解码器的实现 学生姓名：陈聪捷 日期：2010年11月28日 1．实验要求 一、实验目的： 了解哈夫曼树的思想和相关概念； 二、实验内容： 利用二叉树结构实现哈夫曼编/解码器 1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。 2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2. 程序分析 存储结构 二叉树 template 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)）算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下 标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i 结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结 点的双亲设置为空 4. 根据哈夫曼树创建编码表 源代码： void HuffmanTree::CreateHTree(Node *p,int n) { root= new BiNode 韩山师范学院 数据结构中的哈夫曼树的实现 班级：2015级软工班作者：黄俊聪 #include tag1=p[x].weight; s1=x; } } for(int y=1;y<=j-1;y++) { if(p[y].parent==0&&y!=s1&&p[y].weight 数据结构与算法 课程设计报告书 题目：哈夫曼编码/译码器 班级：11091211 学号：1109121105 姓名：田欢 指导教师：龚丹 周期：2011-12-19至2011-12-23 成绩： 年月日 一、课程设计的目的与要求 （一）课程设计目的与任务（参考已发文档自行编辑，但不少于100字）设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。利用哈夫曼树编码问题基本原理的应用，撑握对树的不同存储结构的定义和算法描述。学会构造哈夫曼树和哈夫曼编码等主要算法。 （二）题目要求 1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2) 分别采用动态和静态存储结构 3) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； 4) 编码：利用建好的哈夫曼树生成哈夫曼编码； 5) 输出编码； 6) 设字符集及频度如下表： 字符空格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）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[30]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。 （2）编写CodeInput(n,ht)函数并在函数中设置一个for(i=0;n;++)循环，首先输入n个字符，再利用函数中的for(i=0; 实验报告 一、实验目的 1.掌握哈夫曼树的基本概念及所用的存储结构。 2.掌握哈夫曼树的建立算法。 3.掌握哈夫曼树的应用（哈夫曼树的编码和译码）。 二、实验内容 给定权值5、29、7、8、14、23、3、11，建立哈夫曼树，输出哈夫曼编码。对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。 三、实验与算法分析 建立哈夫曼树，将哈夫曼树的机构定义为一个结构型的一维数组每个元素含有四项：权值、双亲、左孩子、右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。 要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走编码为1，然后将从根结点到树叶中的所有0,1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码，编码的开始位置，编码所对应的字符三项。 哈夫曼译码，就是将输入的译码还原成对应的字符。 抽象的算法描述：将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的的形式，然后在主函数中调用它们。哈夫曼树的构造：假设有n个权值，则构造出的有n个叶子结点。n个权值分别设为w1,w2,……,wn，则哈夫曼树的构造规则为：（1）将w1,w2,……,wn看成是有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左右子树，且新树的根结点权值为其左右子树的根结点的权值之；（3）从森林中删除选取的两棵树，并将新树加入森林。（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。 四、可执行程序及注释 实验代码 #include 【哈夫曼编/译码器】 任务：建立最优二叉树函数 要求：可以建立函数输入二叉树，并输出其赫夫曼树。 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 [基本要求] 一个完整的系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 （5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 [测试数据] （1）利用下面这道题中的数据调试程序。 某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 （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 16 1 [实现提示] （1）编码结果以文本方式存储在文件CodeFile中。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 （3）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）一、实验目的和要求 构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。 （1）掌握树的有关操作算法 （2）熟悉树的基本存储方法 （3）学习利用树求解实际问题 二、实验内容和原理 定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。 三、实验环境 硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境 软件：（1）Windows XP中文操作系统（2）Turbo C 3.0 四、算法描述及实验步骤 1．算法描述 （1）建立叶子结点——由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和， 所以应该有一个权重域和指向左右孩子的两个指针域； （2）另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点 出发到叶子的不断匹配的过程，所以既需要知道孩子结点的信息， 也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针 域。 （3）构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得 到一个哈夫曼编码值；由于每个叶子结点的哈夫曼编码是从根就诶 点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以 先得到的分枝代码为说求编码的低位码而后得到的为高位码。2．算法流程图 构建哈夫曼树算法流程 哈夫曼编码算法流程 3．代码 #include 中国矿业大学徐海学院计算机系《软件认知实践》报告 姓名：学号： 专业： 设计题目： 指导教师： 2013年12月 目录 第1章题目概述 (1) 第1.1节题目要求 (1) 第1.2节主要难点 (1) 第2章系统流程图 (2) 第3章数据结构和算法 (3) 第4章核心代码分析 (3) 第5章实验小结 (5) 参考文献 (9) 第1章题目概述 设计程序以实现构造哈夫曼树的哈夫曼算法 第1.1节题目要求 （1）可以使用实验工具的有关功能。 （2）要能演示构造过程。 （3）求解出所构造的哈夫曼树的带权路径长度。 第1.2节主要难点 (1)构造哈夫曼树：根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。 (2)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结 点所带权值之积，在将所得之积求和。 第2章系统流程图 第3章数据结构和算法 使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有 Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree 等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。 1.Init huffmantree(&T) 操作结果：构造一个已知结点和权值的huffmantree. 2.Destory huffmantree(&T) 条件：huffmantree已经存在 结果：销毁huffmantree. 3.huffman coding(&T) 条件：huffmantree已经存在 结果：输出huffman code. 4.Visit huffmantree(&T) 条件：huffmantree已经存在 结果：显示 huffman tree. 代码运行结果哈夫曼树及其应用(完美版)
数据结构哈夫曼树的实现
哈夫曼树的实验报告1
哈夫曼树及应用
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼算法的实现及应用
实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
c++数据结构实验哈夫曼树
哈夫曼树的应用数据结构课程设计
北京邮电大学信通院数据结构实验三——哈夫曼树实验报告
用C++实现哈夫曼树的代码
哈夫曼树的课程设计报告
数据结构 哈夫曼树 C++实现
哈夫曼树C++实现
实验二 哈夫曼树及哈夫曼编码译码的实现
课程设计构造哈夫曼树