-
2021-05-22 05:52:32
数据结构
课程设计报告
设计题目:哈夫曼树应用
专 业 : 软件工程
班 级 : 软件
学 生 :
学 号 :
指导教师 : 罗作民 / 张翔
起止时间 :2011-07-04—2011-07-08
2011 年 春季 学期
目 录
一.具体任务…..2
1功能……………………………………………………………………………...2
2分步实施………………………………………………………………………...2.
3要求……………………………………………………………………………...2
二.哈夫曼编码2
1问题描述2
2.基本要求3
3实现提示3
三.设计流程图4
1建立哈夫曼树…………………………………………………………………...4
2编码……………………………………………………………………………...5
3译码……………………………………………………………………………...6
4主程序…………………………………………………………………………...7
四.设计概要8
1问题哈夫曼的定义..............................................................................................8..
2所实现的功能函数如下………………………………………………………..8
3功能模块………………………………………………………………………..8
五.源程序9
六.调试分析15
七.心得与体会18
八.参考文献18
一、任务
题目:哈夫曼树应用
1.功能:
1.从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上;
2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行
编码,然后将结果存入文件CodeFile中,并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
3.利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。
2.分步实施:
初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
完成最低要求:完成功能1;
进一步要求:完成功能2和3。有兴趣的同学可以自己扩充系统功能。
3.要求:
1)界面友好,函数功能要划分好
2)总体设计应画一流程图
3)程序要加必要的注释
要提供程序测试方案
程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是没有价值的。
二、哈夫曼编码
1. 问题描述
利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
基本要求
一个完整的系统应具有以下功能:
(1) I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,并将它存于文件hfmTree中。
(2) E:编码(Encoding)。利用已建好的赫夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3) D:译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码,结果存入文件Textfile中。
实现提示
(1) 编码结果以文本方式存储在文件Codefile中。
(2) 用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。
(3) 在程序的一次执行过程中,第一次执行I, D或C命令之后,赫夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为文件hfmTree可能早已建好。
三、设计流程图
更多相关内容 -
哈夫曼树课程设计
2016-12-23 09:16:19有学弟来要我去年做的课程设计,所以把东西整理好了,也给大家参考参考。 -
哈夫曼树课程设计报告
2012-12-18 12:11:17第二章 设计简介及设计方案论述 3 2.1 方案论述 3 第三章 详细设计 4 3.1 结构体的定义 4 3.2 主函数定义 4 3.2 副函数定义 5 第四章 设计结果及分析 11 4.1 设计结果显示 11 4.2 设计结果分析 12 总 结 13 致 谢 -
哈夫曼树 课程设计 实验报告
2010-07-03 22:05:11将任意指定的文本文件中的字符统计后,按Huffman编码方式对文件进行编码,并保存码表及建立的Huffman树;用给定的码表对用Huffman方式编码的文件进行压缩和解压缩。 总体设计 详细设计 测试结果 -
哈夫曼树课程设计报告与代码
2021-01-05 00:20:20用C++实现哈夫曼树的建立生成代码、可用Easy-X简单实现哈夫曼树的图像化、压缩包内附带了Easy-X安装包,运行代码前需安装Easy-X,并有相应课程设计报告,可用于数据结构、密码学、计算机网络等 -
数据结构哈夫曼树课程设计
2018-04-15 19:12:37数据结构哈夫曼树课程设计,完整课程设计,并附有全部代码。 -
c语言哈夫曼树课程设计
2013-01-03 21:28:47老师看过的,得分很高!有详细的代码和流程图!果断下载呀,亲! -
数据结构课程设计 哈夫曼树编码解码 java javafx
2022-05-28 14:54:09利用已建好的哈夫曼树(如不在内存,则从文件 hfmtree 中读入),对文件 tobetrans 中的正文进行编码,然后将结果存入文件 codefile 中。 (3)D:解码(Decoding)。利用已建好的哈夫曼树将文件 codefile 中的代码进行... -
数据结构《哈夫曼树》课程设计
2019-01-13 17:02:09#include<stdio.h> #include&...#define M 2*N-1 //树中结点总数 #include<iostream> using namespace std; typedef struct { char data[5];//结点值 int weight; /...#include<stdio.h> #include<string.h> #define N 50 //叶子结点数 #define M 2*N-1 //树中结点总数 #include<iostream> using namespace std; typedef struct { char data[5];//结点值 int weight; //权重 int parent; //双亲结点 int lchild; //左孩子结点 int rchild; //右孩子节点 }HTNode; typedef struct { char cd[N]; //存放哈夫曼编码 int start; //ch[start..n]存放哈夫曼编码 }HCode; void CreateHT(HTNode ht[],int n) //由ht的叶子结点构造完整的哈夫曼编码 { int i,k,lnode,rnode; int min1,min2; //所有节点的相关域置初值-1 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为最小权重的两个结点位置 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; } } void CreateHCode(HTNode ht[],HCode hcd[],int n) //由哈夫曼树ht构造哈夫曼编码hcd { int i,f,c; HCode hc; for(i=0;i<n;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指向哈夫曼树最开始的字符 hcd[i]=hc; } } void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码 { int i,k; int m=0,j=0; int sum=0; cout<<"输出哈夫曼编码:"<<endl; for(i=0;i<n;i++) { j=0; printf("%s:/t",ht[i].data); cout<<ht[i].data<<endl; for(k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); // cout<<hcd[i].cd[k]<<endl; j++; } m+=ht[i].weight; sum=sum+ht[i].weight*j; } printf("/n平均长度=%g/n",1.0*sum/m); cout<<"平均长度"<<1.0*sum/m<<endl; } int main() { system("color 00a"); int n=15,i; char *str[]={"The","of","a","to ","and","in","that","he","is","at","on","for","His","are","be" }; int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNode ht[M]; HCode hcd[N]; for(i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } CreateHT(ht,n); //创建哈夫曼树 CreateHCode(ht,hcd,n);//构造哈夫曼树 DispHCode(ht,hcd,n); //输出哈夫曼树 return 1; }
-
哈夫曼树课程设计+数据结构
2009-06-15 19:06:08>(1)初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树; (2)编码:利用建好的哈夫曼树生成哈夫曼编码; (3)输出编码; (4)设字符集及频度如下表: 字符 空格 A B C D E F G H I J K L M... -
课程设计哈夫曼树的应用
2011-11-14 01:15:04一、课程设计题目:哈夫曼树应用 二、课程设计要求: 1) 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2) 利用... -
哈夫曼树的应用——课程设计
2016-12-26 13:20:18这个是我去年的课程设计报告,因为有学弟要我就整理了下,功能很简单,就一个加密解密还有求哈夫曼编码,但足够满足老师的要求,现在传给有需要的童鞋参考~ 完整的代码及报告 以下是实验报告内容 哈夫曼树...这个是我去年的课程设计报告,因为有学弟要我就整理了下,功能很简单,就一个加密解密还有求哈夫曼编码,但足够满足老师的要求,现在传给有需要的童鞋参考~
以下是实验报告内容
哈夫曼树的应用——对文件进行解码和译码
一、 需求分析说明
随着信息时代的到来,信息越来越多,如何压缩信息已经是重要课题。特别是多媒体技术的发展,使得信息量大的问题凸显。
哈夫曼编码(Huffman Coding)是一种无损压缩编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称"熵编码法"),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。这种方法是由David.A.Huffman发展起来的。例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去 25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。
当然本软件的目的不在于如何去压缩一个文件信息,而是通过建立哈夫曼树,由哈夫曼树编得二进制码,再译码,来了解哈夫曼树编码实现过程。(庞大的翻译内容会进行报错)
二、 主要功能
1.统计文件中各个字符出现的个数;
2.对文件进行处理得到哈夫曼树编码;
3.对文件进行加密;
4.对文件进行解码
三、 所运用到的知识点
(1)链式存储结构(用来从文件中读取数据,构造哈夫曼编码)
(2)队列的应用(主要用在解码那一块,从文件中逐个读取字符,进入队列,再一个一个判断是否是哪个编码值)
(3)构造最优二叉树,对树的基本操作
(4)对文件的操作(打开文件,读写文件)
四、核心代码实现
(一) 菜单块
while (i != 0) { cout << "***********************欢迎使用译码器(解码器)**************************" << endl; cout << " 1.统计文件中各个字符出现的个数; " << endl; cout << " 2.对文件进行处理得到哈夫曼树编码; " << endl; cout << " 3.对文件进行加密; " << endl; cout << " 4.对文件进行解码 " << endl; cout << " 0.退出 " << endl; switch (i) { case 1: List.creatlist(); List.disp(); List.total(); break; case 2: L.CreateHT(); L.CreateHCode(); L.DispHCode(); break; case 3: L.CreateHT(); L.CreateHCode(); L.Revertext(); break; /* case 0: exit(0);*/ case 4: /*将二进制转化为字母*/ L.CreateHT(); L.CreateHCode(); L.decode(); break; case 0: cout << "欢迎下次使用译码器(解码器)" << endl; break; } cout << "请输入您要进行的操作:"; cin >> i; system("cls"); }
(二) 统计字符
void total() //利用一个数组,统计字母出现次数 { linklist *s; int j = 0; int count[127] = { 0 }; //设置初始化 s = head->next; int num; while (s) { num = s->data; if (num != 32) //不计算空格出现的频度 { count[num - 0]++; } s = s->next; } cout << "统计" << endl; cout << "|---------------------------------------------|" << endl; cout << "| 字母 | 频度 |" << endl; for (int i = 0; i < 127; i++) { if (count[i]) { aa[j].data = i; aa[j].weight = count[i]; j++; cout << "| " << char(i) << " | " << setw(6) << count[i] << " |" << endl; } } Count = j; cout << "|---------------------------------------------|" << endl; cout << "出现的字母种类为:" << Count << "个" << endl; cout << endl; } };
(三) 创建哈夫曼树
void HuffmanClass<T>::CreateHT() //构造哈夫曼树 { int i, k, lnode, rnode; double min1, min2; for (i = 0; i < (2 * no - 1); i++) //所有结点的相关域置初值-1 { ht[i].parent = -1; ht[i].lchild = -1; ht[i].rchild = -1; } for (i = no; i < (2 * no - 1); i++) //构造哈夫曼树,仅求非叶子结点 { min1 = min2 = 32767.0; //初始时置最大权值 lnode = rnode = -1; //lnode和rnode为两个权重最小的节点位置 for (k = 0; k <= (i - 1); k++) //在ht数组中找权值最小的两个结点 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; //把后面的no-1个非叶子结点处理完毕 ht[rnode].parent = i; ht[i].weight = ht[lnode].weight + ht[rnode].weight; ht[i].lchild = lnode; //ht[i]作为双亲结点 ht[i].rchild = rnode; } }
(四) 得到哈夫曼编码
void HuffmanClass<T>::CreateHCode() //根据哈夫曼树求哈夫曼编码 { int i, f, c; for (i = 0; i < no; i++) //遍历下标从0到no-1的叶子结点 { hcd[i].start = no; //从hcd[i].cd[no]开始放置哈夫曼编码 c = i; f = ht[i].parent; //找其双亲结点 while (f != -1) //循环直至无双亲结点即到达树根结点 { if (ht[f].lchild == c) //当前结点是双亲结点的左孩子结点 { hcd[i].cd[hcd[i].start] = '0'; /*cout << hcd[i].cd[hcd[i].start]<<endl;*/ } else { hcd[i].cd[hcd[i].start] = '1'; }//当前结点是双亲结点的右孩子结点 hcd[i].start--; c = f; f = ht[f].parent; //再对双亲进行同样的操作 } hcd[i].start++; //start指向哈夫曼编码最开始字符 } }
(五) 对文件进行加密
void HuffmanClass<T>::Revertext() { SqQueueClass<char> L; L.initQueue(); FILE *fin, *fout; char ch; if ((fin = fopen("D:\\test.txt", "r")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } if ((fout = fopen("D:\\tex.txt", "w")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } ch = fgetc(fin);//一个一个读出来 while (!feof(fin)) { for (int i = 0; i < no; i++) { if (ch == ht[i].data) { for (int j = hcd[i].start; j <= no; j++) { cout << hcd[i].cd[j]; fputc(hcd[i].cd[j], fout); } } } ch = fgetc(fin); //从fin 文件中打开,再次读 } cout << endl << "文件已经读写完毕,这是显示器的输出效果" << endl; fclose(fin); fclose(fout); }
(六) 对文件进行解码
void HuffmanClass<T>::decode()//解码 { cout << "文件解码为:" << endl; int mark = 0;//设置标志 int q, j, ii, jj, k, tt; int kk = 0; char temp[MaxQueue][MaxQueue]; char temp1[MaxQueue][MaxQueue]; SqQueueClass<char> L; L.initQueue(); FILE *fin; char ch; if ((fin = fopen("D:\\test1.txt", "r")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } for (int aa = 0; aa < no; aa++) { for (int bb = hcd[aa].start; bb <= no; bb++) { temp1[aa][(bb - hcd[aa].start)] = hcd[aa].cd[bb]; /*cout << temp1[aa][(bb - hcd[aa].start)] << " ";*/ /*保留*/ } } ch = fgetc(fin);//一个一个读出来 while (!feof(fin)) { mark = 0; L.enQueue(ch);//进队 for (j = 0, q = L.getfront() + 1; q != L.getrear() + 1; j++, q++) //一个个获得临时的01(temp)序列,以便和哈夫曼编码比较 { temp[kk][j] = L.data[q]; } for (ii = 0; ii < no; ii++)//哈弗曼编码放到二维数组里了 { int zz; zz = 0; for (jj = 0; jj <= no - hcd[ii].start; jj++) { if (temp[kk][jj] == temp1[ii][jj])//若两个相等 { zz = zz + 1; } } if (zz == no - hcd[ii].start + 1) { cout << ht[ii].data; mark = 1; break; } } if (mark == 1) { L.destory();//清空队列 /*cout << "清空" << endl;*/ } ch = fgetc(fin); //从fin 文件中打开,再次读 kk = kk + 1; } if (L.getfront() != L.getrear()) { cout << "\n以下二进制串输入有错误:"; for (int j = L.getfront() + 1; j != L.getrear() + 1; j++) cout << L.data[j]; } else cout << endl; cout << endl << "文件已经读写完毕,这是显示器的输出效果" << endl; fclose(fin); }
五、 结果展示
菜单:
计算字符出现的频度:
得到哈夫曼编码:
加密:
解码:
六、 总结
做这个课程设计是熬了两个晚上做出来的,其中有一个如何解密,如何判断从文件读取的数据构成的数组与我的每一个哈夫曼编码值是否相等,因为哈夫曼编码的存储方式是存在数组,且从start元素到no元素才是正确的值,所以非常麻烦。我一直在不停地用循环判断,甚至要重新写我如何得到哈夫曼的编码,因为实在太困难了。索性,学到了一个好方法,就是中断,通过中断可以查看自己的程序走到哪一步了,再跟着步骤和本应该有的步骤进行对比,就很容易发现错误,这一次最大的收获就是学会熟练使用中断。还有可以用到之前学到的知识点,比如这里用了队列进行读取数据,以前从没有想过队列可以这样用。还有要集思广益,不一定去网上找代码就是不好的,因为适合别人的代码不一定适合自己,还是要自己写,主要是学习他们的思路,然后用自己的方法做出来。这个.cpp的功能其实还有缺陷,就是如果我对非常多的‘0’‘1’进行译码是会出现错误,我不知道是什么问题,不过会继续深入,另外还有一个可以提升的地方是对文件的操作应该是让用户自己选择文件而不是固定文件,不过,因为自己的代码太冗余,很难实现这个操作,不过会继续学习如何写出漂亮的代码。
完整的代码:
#include<iostream> #include<fstream> #include<iomanip> #include<string> using namespace std; #include<stdio.h> #include<stdlib.h> #define MaxSize 100 #define MaxQueue 100 struct linklist //单链表结点类型 { char data; linklist *next; }; struct pindu //每个字母出现的频度结点类型 { char data; //字母 int weight; //权值 }; template <typename T> struct HTNode //哈夫曼结点类型 { T data;//结点值 double weight;//权值 int parent;//双亲结点 int lchild;//左孩子结点 int rchild;//右孩子结点 }; struct HCode //哈夫曼编码类型 { char cd[MaxSize]; //存放当前结点的哈夫曼编码 int start; //用cd[start..no]存放哈夫曼编码,包括start和no }; class sqlist { private: linklist *head; int Count; //计算个数 public: pindu aa[100]; //存放频度的信息 sqlist() { head = new linklist[100]; head->next = NULL; Count = 0; } void destorysqlist() //删除单链表,不能用析构,因为随时不用,会对哈夫曼数的构造造成影响 { linklist *pre, *p; pre = head; p = pre->next; while (p != NULL) { delete pre; pre = p; p = p->next; } delete pre; } int getCount() //得到权值个数 { linklist *s; int j = 0; int count[127] = { 0 }; //设置初始化 s = head->next; int num; while (s) { num = s->data; if (num != 32) //不计算空格出现的频度 { count[num - 0]++; } s = s->next; } for (int i = 0; i < 127; i++) { if (count[i]) { aa[j].data = i; aa[j].weight = count[i]; j++; } } Count = j; return Count; } void creatlist() //创建单链表,把文件中的字母写进单链表中 { linklist *s, *r; r = head; FILE *fin; char ch; /*char filename[100] = { 0 }; cout << "请输入文件路径:"; cin >> filename;*/ if ((fin = fopen("H:\\test.txt", "r")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } ch = fgetc(fin); while (!feof(fin)) { s = new linklist; s->data = ch; r->next = s; r = s; ch = fgetc(fin); //从fin 文件中打开 } r->next = NULL; fclose(fin); /* cout << endl; cout << endl;*/ } void disp() //输出单链表内容,即文章内容 { cout << endl << "文件内容打开如下" << endl; linklist *s; s = head->next; int count[257] = { 0 }; while (s) { cout << s->data; s = s->next; } cout << endl; } void total() //利用一个数组,统计字母出现次数 { linklist *s; int j = 0; int count[127] = { 0 }; //设置初始化 s = head->next; int num; while (s) { num = s->data; if (num != 32) //不计算空格出现的频度 { count[num - 0]++; } s = s->next; } cout << "统计" << endl; cout << "|---------------------------------------------|" << endl; cout << "| 字母 | 频度 |" << endl; for (int i = 0; i < 127; i++) { if (count[i]) { aa[j].data = i; aa[j].weight = count[i]; j++; cout << "| " << char(i) << " | " << setw(6) << count[i] << " |" << endl; } } Count = j; cout << "|---------------------------------------------|" << endl; cout << "出现的字母种类为:" << Count << "个" << endl; cout << endl; } }; template <typename T> class SqQueueClass //队列进行解码操作 { private: int front; int rear; public: T data[MaxQueue]; void initQueue()//初始化 { front = rear = 0; } void destory()//清空队列 { initQueue(); } void enQueue(T e)//进队 { //if ((rear + 1) % MaxQueue == front)//队满 // return false; rear = (rear + 1) % MaxQueue; data[rear] = e; } void deQueue(T &e)//出队 { /*if (rear == front) return false;*/ front = (front + 1) % MaxQueue; e = data[front]; } void disp() { for (int i = front + 1; i <= rear; i++) { cout << data[i] << " "; } } int getfront() { return front; } int getrear() { return rear; } }; template <typename T> class HuffmanClass { private: int no; //权值个数 HTNode<T> ht[MaxSize]; //存放哈夫曼树 HCode hcd[MaxSize]; //存放哈夫曼编码 public: HuffmanClass(); //Setvalue设置初值 void CreateHT(); //构造哈夫曼树 void CreateHCode(); //根据哈夫曼树求哈夫曼编码 void DispHCode(); //输出哈夫曼编码 void Revertext(); //将文本转化成二进制代码存入另一个文件中 void decode(); //解码,把二进制转化成文字 }; template <typename T> HuffmanClass<T>::HuffmanClass() //设置初值 { pindu str[100]; sqlist List;// List.creatlist();// for (int i = 0; i < List.getCount(); i++) { str[i].data = List.aa[i].data; str[i].weight = List.aa[i].weight; } no = List.getCount(); //权值个数 for (int i = 0; i <(2 * no - 1); i++) { ht[i].data = str[i].data; ht[i].weight = str[i].weight; } } template <typename T> void HuffmanClass<T>::CreateHT() //构造哈夫曼树 { int i, k, lnode, rnode; double min1, min2; for (i = 0; i < (2 * no - 1); i++) //所有结点的相关域置初值-1 { ht[i].parent = -1; ht[i].lchild = -1; ht[i].rchild = -1; } for (i = no; i < (2 * no - 1); i++) //构造哈夫曼树,仅求非叶子结点 { min1 = min2 = 32767.0; //初始时置最大权值 lnode = rnode = -1; //lnode和rnode为两个权重最小的节点位置 for (k = 0; k <= (i - 1); k++) //在ht数组中找权值最小的两个结点 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; //把后面的no-1个非叶子结点处理完毕 ht[rnode].parent = i; ht[i].weight = ht[lnode].weight + ht[rnode].weight; ht[i].lchild = lnode; //ht[i]作为双亲结点 ht[i].rchild = rnode; } } template <typename T> void HuffmanClass<T>::CreateHCode() //根据哈夫曼树求哈夫曼编码 { int i, f, c; for (i = 0; i < no; i++) //遍历下标从0到no-1的叶子结点 { hcd[i].start = no; //从hcd[i].cd[no]开始放置哈夫曼编码 c = i; f = ht[i].parent; //找其双亲结点 while (f != -1) //循环直至无双亲结点即到达树根结点 { if (ht[f].lchild == c) //当前结点是双亲结点的左孩子结点 { hcd[i].cd[hcd[i].start] = '0'; /*cout << hcd[i].cd[hcd[i].start]<<endl;*/ } else { hcd[i].cd[hcd[i].start] = '1'; }//当前结点是双亲结点的右孩子结点 hcd[i].start--; c = f; f = ht[f].parent; //再对双亲进行同样的操作 } hcd[i].start++; //start指向哈夫曼编码最开始字符 } } template <typename T> void HuffmanClass<T>::DispHCode() { cout << "该文件哈夫曼编码如下" << endl; for (int i = 0; i < no; i++) { cout << ht[i].data << ":"; for (int j = hcd[i].start; j <= no; j++) //因为start一直在变化,一直在减小,存的值是从下往上走的,就是start减小的顺序 { cout << hcd[i].cd[j]; } cout << endl; } } template <typename T> void HuffmanClass<T>::Revertext() { SqQueueClass<char> L; L.initQueue(); FILE *fin, *fout; char ch; if ((fin = fopen("H:\\test.txt", "r")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } if ((fout = fopen("H:\\tex.txt", "w")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } ch = fgetc(fin);//一个一个读出来 while (!feof(fin)) { for (int i = 0; i < no; i++) { if (ch == ht[i].data) { for (int j = hcd[i].start; j <= no; j++) { cout << hcd[i].cd[j]; fputc(hcd[i].cd[j], fout); } } } ch = fgetc(fin); //从fin 文件中打开,再次读 } cout << endl << "文件已经读写完毕,这是显示器的输出效果" << endl; fclose(fin); fclose(fout); } template <typename T> void HuffmanClass<T>::decode()//解码 { cout << "文件解码为:" << endl; int mark = 0;//设置标志 int q, j, ii, jj, k, tt; int kk = 0; char temp[MaxQueue][MaxQueue]; char temp1[MaxQueue][MaxQueue]; SqQueueClass<char> L; L.initQueue(); FILE *fin; char ch; if ((fin = fopen("H:\\test1.txt", "r")) == NULL) { cout << "无法打开此文件" << endl; exit(0); } for (int aa = 0; aa < no; aa++) { for (int bb = hcd[aa].start; bb <= no; bb++) { temp1[aa][(bb - hcd[aa].start)] = hcd[aa].cd[bb]; /*cout << temp1[aa][(bb - hcd[aa].start)] << " ";*/ /*保留*/ } } ch = fgetc(fin);//一个一个读出来 while (!feof(fin)) { mark = 0; L.enQueue(ch);//进队 for (j = 0, q = L.getfront() + 1; q != L.getrear() + 1; j++, q++) //一个个获得临时的01(temp)序列,以便和哈夫曼编码比较 { temp[kk][j] = L.data[q]; } for (ii = 0; ii < no; ii++)//哈弗曼编码放到二维数组里了 { int zz; zz = 0; for (jj = 0; jj <= no - hcd[ii].start; jj++) { if (temp[kk][jj] == temp1[ii][jj])//若两个相等 { zz = zz + 1; } } if (zz == no - hcd[ii].start + 1) { cout << ht[ii].data; mark = 1; break; } } if (mark == 1) { L.destory();//清空队列 /*cout << "清空" << endl;*/ } ch = fgetc(fin); //从fin 文件中打开,再次读 kk = kk + 1; } if (L.getfront() != L.getrear()) { cout << "\n以下二进制串输入有错误:"; for (int j = L.getfront() + 1; j != L.getrear() + 1; j++) cout << L.data[j]; } else cout << endl; cout << endl << "文件已经读写完毕,这是显示器的输出效果" << endl; fclose(fin); } void menu() { HuffmanClass <char>L; sqlist List; int i; cout << "***********************欢迎使用译码器(解码器)**************************" << endl; cout << " 1.统计文件中各个字符出现的个数; " << endl; cout << " 2.对文件进行处理得到哈夫曼树编码; " << endl; cout << " 3.对文件进行加密; " << endl; cout << " 4.对文件进行解码 " << endl; cout << " 0.退出 " << endl; cout << "请输入您要进行的操作:"; cin >> i; while (i != 0) { cout << "***********************欢迎使用译码器(解码器)**************************" << endl; cout << " 1.统计文件中各个字符出现的个数; " << endl; cout << " 2.对文件进行处理得到哈夫曼树编码; " << endl; cout << " 3.对文件进行加密; " << endl; cout << " 4.对文件进行解码 " << endl; cout << " 0.退出 " << endl; switch (i) { case 1: List.creatlist(); List.disp(); List.total(); break; case 2: L.CreateHT(); L.CreateHCode(); L.DispHCode(); break; case 3: L.CreateHT(); L.CreateHCode(); L.Revertext(); break; /* case 0: exit(0);*/ case 4: /*将二进制转化为字母*/ L.CreateHT(); L.CreateHCode(); L.decode(); break; case 0: cout << "欢迎下次使用译码器(解码器)" << endl; break; } cout << "请输入您要进行的操作:"; cin >> i; system("cls"); } } int main() { menu(); system("pause"); return 0; }
代码注意事项:
软件:DEV C++主要功能
1.统计文件中各个字符出现的个数;
2.对文件进行处理得到哈夫曼树编码;
3.对文件进行加密;
4.对文件进行解码1.在H盘上创建一个名为test.txt的文件,存放a-z任意字符;
2.在H盘创建一个名为test1.txt的文件,存放01字符;
3.在H盘创建一个名为tex.txt的文件(可以什么都不放);
(可自行换盘,代码要改)
功能一:求test.txt的各个字符出现的频度;
功能二:求出哈夫曼编码(根据test.txt中的字符);
功能三:对test.txt的文件进行加密(根据求得的哈夫曼编码来),然后把结果存放到tex.txt中;
功能四:是对test1中的01字符进行解码,翻译成对应的字符,将结果输出到屏幕;(就是根据功能二得到的哈夫曼树,对test1.txt的内容进行解码)
-
数据结构课程设计_哈夫曼树
2015-03-07 13:23:192.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 4.训练用系统的观点和软件开发一般规范进行软件开发,巩固、深化... -
数据结构课程设计----哈夫曼树设计
2018-12-21 10:25:38计算哈夫曼树的WPL值 根据给定的n个权值(非负值),计算所构造哈夫曼树的WPL值。 基本要求: (1)根据给定的数据,建立哈夫曼树; (2)输出每个叶子结点的带权路径长度; (3)输出哈夫曼树的WPL值。 ...计算哈夫曼树的WPL值 根据给定的n个权值(非负值),计算所构造哈夫曼树的WPL值。
基本要求:
(1)根据给定的数据,建立哈夫曼树;
(2)输出每个叶子结点的带权路径长度;
(3)输出哈夫曼树的WPL值。
测试数据要求: 输入的n个权值之和应为100,且不允许有负值。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define n 5 //5个英文小写字母(注意,该示例可扩展到所有可显示字符,可自行添加改写),此示例中字符串仅允许包含小写字母 //哈夫曼树相关 //节点定义,使用数组存储链表,指针使用位置索引 typedef struct { int weight; int parent, lchild, rchild; }HTNode, *PHTNode, *HTree; //编码表 typedef char **HCode; //辅助操作,从1到k中选择两个权重最小的节点 void Select(HTree HT, int k, int &s1, int &s2) { int min, smin; min = smin = 100000; for(int i = 1; i <= k; i++){ if(HT[i].parent) continue; //如果已经安排了双亲节点 if(HT[i].weight < min){ s2 = s1; smin = min; s1 = i; min = HT[i].weight; } else if(HT[i].weight < smin){ s2 = i; smin = HT[i].weight; } } //使得s1小于s2,可使编码较规范,尽量以0结束 int temp; if(s1 > s2){ temp = s1; s1 = s2; s2 = temp; } } //根据权重数据构建Huffman树 void ConstructHuffmanTree(HTree &HT, int *w) { int m = 2 * n - 1; //节点数目 HT = (HTree)malloc((m+1) * sizeof(HTNode)); //分配空间,0号位置不使用 //初始化各个节点 int i, s1, s2; for(i = 1; i <= n; i++) { HT[i].weight = w[i]; HT[i].parent = HT[i].lchild = HT[i].rchild = 0; } for(; i <= m; i++) { HT[i].weight = HT[i].parent = HT[i].lchild = HT[i].rchild = 0; } //建立Huffman树 for(i = n + 1; i <= m; i++){ Select(HT, i - 1, s1, s2); HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } } //从Huffman树获取编码表 //从根到叶子(递归),cd保存获取的编码记录 void GetCodeTable(HTree HT, HCode HC, int p, char *cd, int cdlen) { //如果已经到达叶子节点,登记编码 if(p <= n){ HC[p] = (char *)malloc((cdlen + 1) * sizeof(char)); cd[cdlen] = '\0'; strcpy(HC[p], cd); } if(HT[p].lchild){ cd[cdlen] = '0'; GetCodeTable(HT, HC, HT[p].lchild, cd, cdlen + 1); } //向左子树前进 if(HT[p].rchild){ cd[cdlen] = '1'; GetCodeTable(HT, HC, HT[p].rchild, cd, cdlen + 1);} //向右子树前进 } //从叶子到根,教程算法 void GetCodeTable1(HTree HT, HCode &HC) { HC = (HCode)malloc((n+1)*sizeof(char *)); char *cd = (char *)malloc(n * sizeof(char)); cd[n -1] = '\0'; int start, c, f; for(int i = 1; i <= n; i++){ start = n - 1; for(c = i, f = HT[i].parent; f; c = f, f = HT[f].parent){ if(c == HT[f].lchild) cd[--start] = '0'; else cd[--start] = '1'; } HC[i] = (char *)malloc((n - start) * sizeof(char)); strcpy(HC[i], cd + start); } free(cd); } //从根到叶子(非递归),教程算法,这是模拟递归栈的一种典型方法,需注意 void GetCodeTable2(HTree HT, HCode &HC) { HC = (HCode)malloc((n+1) * sizeof(char *)); char *cd = (char *)malloc(n * sizeof(char)); int m = 2 * n - 1, p = m, cdlen = 0; //借用weight做左右子树是否已经遍历的标志,注意会破坏原来的weight数据 for(int i = 1; i <= m; i++) HT[i].weight = 0; while(p){ //左右子树均未访问,访问左子树 if(HT[p].weight == 0){ HT[p].weight = 1; //设置标志左子树已经访问 //如果仍未到达叶子节点,继续向下层进发,同时记录编码 if(HT[p].lchild) { p = HT[p].lchild; cd[cdlen++] = '0'; continue;} //否则如果是叶子节点的话登记字符编码(其实在右子树那边检查也可以),否则会继续遍历右子树 if(!HT[p].rchild){ HC[p] = (char *)malloc((cdlen + 1) * sizeof(char)); cd[cdlen] = '\0'; strcpy(HC[p], cd); } continue; } //如果左子树已经访问过而右子树没有访问过 if(HT[p].weight == 1){ HT[p].weight = 2; //设置左右子树均已经访问过标志 //如果右子树不为空,继续向下层进发,同时记录编码 if(HT[p].rchild) { p = HT[p].rchild; cd[cdlen++] = '1'; continue;} //其实在右子树这边登记也可以 /*else if(!HT[p].lchild){ HC[p] = (char *)malloc((cdlen + 1) * sizeof(char)); cd[cdlen] = '\0'; strcpy(HC[p], cd); }*/ continue; } //如果左右两个子树都已经访问过了,退回到双亲节点(同时重置访问标志,字符记录位置也前移) HT[p].weight = 0; --cdlen; p = HT[p].parent; } } //输出码表 void PrintCodeTable(HCode HC) { printf("\nThe Code Table:\n"); for(int i = 1; i <= n; i++){ printf("路径长度:%d %c : %s\n",strlen(HC[i]), 'a' + i - 1, HC[i]); } } //使用码表对字符串编码 void Encode(HCode HC, char *str, char **code) { *code = (char *)malloc(sizeof(char) * 1024); (*code)[0] = '\0'; int pos = 0; //pos为字符串指针 while(str[pos]){ strcat(*code, HC[str[pos++] - 'a' + 1]); } } //对哈夫曼树进行计算WPL int WPL(HCode HC,int w[]){ int sum=0; //int w[] = { 10,30,20,5,35}; for(int i = 1; i <= n; i++) sum=sum+strlen(HC[i])*w[i]; return sum; } int main() { //5个英文字符的权重(频率统计) int w[] = { 0,5,20,25,5,45}; HTree HT; ConstructHuffmanTree(HT, w); //构建Huffman树 //从树中获取编码表 HCode HC = (HCode)malloc((n+1) * sizeof(char *)); char *cd = (char *)malloc(n * sizeof(char)); int cdlen = 0; GetCodeTable(HT, HC, 2 * n - 1, cd, cdlen); PrintCodeTable(HC); //输出编码表 printf("WPL:%d\n",WPL(HC,w)); return 0; }
-
哈夫曼树_数据结构课程设计.doc
2021-05-20 14:57:14哈夫曼树_数据结构课程设计《 数据结构 》课程设计——赫夫曼编码/译码器设计指导教师:孙树森、周维达班级:09数媒(2)班学号:姓名:林真超数据结构课程设计实验报告一、题目:赫夫曼编码/译码器设计二、目的:1、... -
数据结构与算法(C语言实现) 5.哈夫曼树的设计及实现
2022-04-27 01:35:55数据结构与算法(C语言实现) 实验五:哈夫曼树的设计及实现 -
哈夫曼树总结
2022-04-16 10:27:56当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”。 构造哈夫曼树过程 每次找出权值最小的... -
数据结构课程设计之哈夫曼树的建立(代码和文档))
2018-08-10 12:43:53任务:按给定的数据建立赫夫曼树 要求:可以建立函数输入二叉树,并输出其赫夫曼树。在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果。提供良好的菜单操作界面 -
哈夫曼树的应用 课程设计
2010-03-12 20:54:55一、课程设计题目:哈夫曼树应用 二、课程设计要求: 1) 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2) 利用... -
数据结构课程设计哈夫曼树及编码.docx
2020-11-09 01:06:01数据结构课程设计 哈夫曼树及编码 HUFFMAN树及编码 需求分析 随机输入一篇英文文章(或读一个 TXT文件)生成并显示 HUFFMAN树输出每个字母的 HUFFMAN编码判断 ASCII编码 与HUFFMAN编码对本篇报文长度节省效果 输入的... -
哈夫曼编码课程设计
2015-06-17 10:46:56哈夫曼编码课程设计,我要让所以人都知道写一个哈夫曼编码树便不是难事。 -
C++课程设计——哈夫曼树.txt
2020-04-09 14:11:10设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。 -
Python数据结构之哈夫曼树定义与使用方法示例
2021-01-20 06:23:06本文实例讲述了Python数据结构之哈夫曼树定义与使用方法。分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __... -
哈夫曼树课程设计 数据结构
2009-03-21 12:14:47数据结构,哈夫曼树课程设计 。大二的时候做的。 -
[数据结构]课程设计--哈夫曼树编码与译码
2018-01-01 23:39:03//哈夫曼树最大节点数 const int Max = 10;//哈夫曼树叶子节点数 //树节点 struct HFNode { int weight;//结点权值 int lchild, rchild;//孩子节点下标 int parent;//双亲结点下标 }; //初始叶