下载 >  开发技术 >  其它 > 赫夫曼树的算法,权值,编码,原始码

赫夫曼树的算法,权值,编码,原始码

显示赫夫曼树的权值,原始码,赫夫曼编码,前序、中序、后序遍历的算法
2010-12-27 上传大小:6KB
分享
收藏 举报
根据给定的n个权值构造哈夫曼树。通过遍历此二叉树完成哈夫曼编码

①根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn},其中每棵二叉树Ti中只有一个带树为Ti的根结点; ②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置其根结点的权值为其左右子树权值之和; ③在F中删除这两棵树,同时将新得到的二叉树加入F中; ④重复②、③直到F只含一棵树为止。

立即下载
赫夫曼树的构建及赫夫曼编码(C语言源代码,代码中含详细注释)

C语言实现赫夫曼树的构建及赫夫曼编码的源代码,配合我的CSDN博客:http://blog.csdn.net/ns_code/article/details/19174553中的讲解,帮助你掌握Huffman编码的算法实现

立即下载
赫夫曼树(哈夫曼树) 算法 编码 源代码 源程序 C++ win32

本程序已在visual stdio2008上调试成功。 赫夫曼树的c++win32控制台下的源程序。代码简洁,容易理解。

立即下载
赫夫曼树的建立、编码和译码

赫夫曼树的建立、编码和译码 赫夫曼树的建立、编码和译码 赫夫曼树的建立、编码和译码

立即下载
对给定权值赫夫曼树进行编码

对给定权值的赫夫曼树进行编码,使用01前缀编码的方式避免编码的重复,使译码过程准确进行

立即下载
赫夫曼树C语言代码实现(最小二叉树)

该部分有两个不同的程序,程序根据用户输入的结点值和权重建立哈夫曼树,然后输出哈夫曼编码

立即下载
用户键盘输入若干个整数作为待编码字符的权值,程序建立哈夫曼树并输出各字符的哈夫曼编码

构造一棵哈夫曼树,并根据哈夫曼树求哈夫曼编码的算法

立即下载
《数据结构》实验哈夫曼树

构造一棵哈夫曼树,哈夫曼树它是带权路径长度WPL最小的二叉树,掌握赫夫曼树的构造并能依据所构造赫夫曼树对实际问题进行编码,输出赫夫曼编码,正确调试程序。1、初始化。从键盘读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树。2、编码。利用以建立好的赫夫曼树,并进行编码。3、输出。将每个字符的编码输出。

立即下载
哈夫曼树应用 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上;

从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 3.利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果

立即下载
三元哈夫曼编码 哈夫曼树

详细描述了哈夫曼树的构造方法,同时推广到三元哈夫曼编码,并用C语言于VC++上实现

立即下载
从文件读取字符串建立哈夫曼树并进行哈夫曼编码

利用文件中的字符资源建立哈夫曼树,利用建立的哈夫曼树对给定的字符串进行编码。资源中含有可执行的源代码以及实验报告。

立即下载
赫夫曼树及编码

赫夫曼树及编码

立即下载
C语言编码哈夫曼树

#include<iostream> #include<fstream> #include<iomanip> #include<stdlib.h> using namespace std; # define MaxN 100//初始设定的最大结点数 # define MaxC 1000//最大编码长度 # define ImpossibleWeight 10000//结点不可能达到的权值 # define n 26//字符集的个数 //-----------哈夫曼树的结点结构类型定义----------- typedef struct //定义哈夫曼树各结点 { int weight;//权值 int parent;//双亲结点下标 int lchild;//左孩子结点下标 int rchild;//右孩子结点下标 }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedef char**HuffmanCode;//动态分配数组存储哈夫曼编码表 //-------全局变量-------- HuffmanTree HT; HuffmanCode HC; int *w;//权值数组 //const int n=26;//字符集的个数 char *info;//字符值数组 int flag=0;//初始化标记 //********************************************************************** //初始化函数 //函数功能: 从终端读入字符集大小n , 以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中 //函数参数: //向量HT的前n个分量表示叶子结点,最后一个分量表示根结点,各字符的编码长度不等,所以按实际长度动态分配空间 void Select(HuffmanTree t,int i,int &s1,int &s2) { //s1为最小的两个值中序号最小的那个 int j; int k=ImpossibleWeight;//k的初值为不可能达到的最大权值 for(j=1;j<=i;j++) { if(t[j].weight<k&&t[j].parent==0) {k=t[j].weight; s1=j;} } t[s1].parent=1; k=ImpossibleWeight; for(j=1;j<=i;j++) { if(t[j].weight<k&&t[j].parent==0) {k=t[j].weight; s2=j;} } t[s2].parent=1; } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if(num<=1) return; m=2*num-1;//m为结点数,一棵有n个叶子结点的哈夫曼树共有2n-1个结点,可以存储在一个大小为2n-1的一维数组中 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 //--------初始化哈弗曼树------- for(p=HT+1,i=1;i<=num;i++,p++,w++) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(i=num+1;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } //--------建哈夫曼树------------- for(i=num+1;i<=m;i++) { Select(HT,i-1,s1,s2);//在HT[1...i-1]选择parent为0且weight最小的两个结点,其序号分别为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; } //-------从叶子到根逆向求每个字符的哈弗曼编码-------- HC=(HuffmanCode)malloc((num+1)*sizeof(char *));//指针数组:分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char*));//分配求编码的工作空间 cd[n-1]='\0';//编码结束符 for(i=1;i<=n;i++)//逐个字符求哈弗曼编码 { start=n-1;//编码结束符位置 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到跟逆向求哈弗曼编码 if(HT[f].lchild==c) cd[--start]='0';//判断是左孩子还是右孩子(左为0右为1) else cd[--start]='1'; HC[i]=(char*)malloc((num-start)*sizeof(char*));//按所需长度分配空间 int j,h; strcpy(HC[i],&cd[start]); } free(cd); } //****************初始化函数****************** void Initialization() { flag=1;//标记为已初始化 int i; w=(int*)malloc(n*sizeof(int));//为26个字符权值分配空间 info=(char*)malloc(n*sizeof(char));//为26个字符分配空间 ifstream infile("ABC.txt",ios::in); if(!infile) { cerr<<"打开失败"<<endl; exit(1); } for(i=0;i<n;i++) { infile>>info[i]; infile>>w[i]; } infile.close(); cout<<"读入字符成功!"<<endl; HuffmanCoding(HT,HC,w,n); //------------打印编码----------- cout<<"依次显示各个字符的值,权值或频度,编码如下"<<endl; cout<<"字符"<<setw(6)<<"权值"<<setw(11)<<"编码"<<endl; for(i=0;i<n;i++) { cout<<setw(3)<<info[i]; cout<<setw(6)<<w[i]<<setw(12)<<HC[i+1]<<endl; } //---------将建好的哈夫曼树写入文件------------ cout<<"下面将哈夫曼树写入文件"<<endl; ofstream outfile("hfmTree.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } for(i=0;i<n;i++,w++) { outfile<<info[i]<<" "; outfile<<w[i]<<" "; outfile<<HC[i+1]<<" "; } outfile.close(); cout<<"已经将字符与对应的权值,编码写入根目录下文件hfmTree.txt"<<endl; } //*****************输入待编码字符函数************************* void Input() { char string[100]; ofstream outfile("ToBeTran.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } cout<<"请输入你想要编码的字符串(字符个数应小于100),以#结束"<<endl; cin>>string; for(int i=0;string[i]!='\0';i++) { if(string[i]=='\0') break; outfile<<string[i]; } cout<<"获取报文成功"<<endl; outfile.close(); cout<<"------"<<"已经将报文存入根目录下的ToBeTran.txt文件"<<endl; } //******************编码函数**************** void Encoding() { int i,j; char*string; string=(char*)malloc(MaxN*sizeof(char)); cout<<"下面对根目录下的ToBeTran.txt文件中的字符进行编码"<<endl; ifstream infile("ToBeTran.txt",ios::in); if(!infile) { cerr<<"打开失败"<<endl; exit(1); } for(i=0;i<100;i++) { infile>>string[i]; } for(i=0;i<100;i++) if(string[i]!='#') cout<<string[i]; else break; infile.close(); ofstream outfile("CodeFile.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } for(i=0;string[i]!='#';i++) { for(j=0;j<n;j++) { if(string[i]==info[j]) outfile<<HC[j+1]; } } outfile<<'#'; outfile.close(); free(string); cout<<"编码完成------"; cout<<"编码已写入根目录下的文件CodeFile.txt中"<<endl; } //******************译码函数**************** void Decoding() { int j=0,i; char *code; code=(char*)malloc(MaxC*sizeof(char)); char*string; string=(char*)malloc(MaxN*sizeof(char)); cout<<"下面对根目录下的CodeFile.txt文件中的代码进行译码"<<endl; ifstream infile("CodeFile.txt",ios::in); if(!infile) { cerr<<"打开失败"<<endl; exit(1); } for( i=0;i<MaxC;i++) { infile>>code[i]; if(code[i]!='#') { cout<<code[i]; } else break; } infile.close(); int m=2*n-1; for(i=0;code[i-1]!='#';i++) { if(HT[m].lchild==0) { string[j]=info[m-1]; j++; m=2*n-1; i--; } else if(code[i]=='1') m=HT[m].rchild; else if(code[i]=='0') m=HT[m].lchild; } string[j]='#'; ofstream outfile("TextFile.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } cout<<"的译码为------"<<endl; for( i=0;string[i]!='#';i++) { outfile<<string[i]; cout<<string[i]; } outfile<<'#'; outfile.close(); cout<<"------译码完成------"<<endl; cout<<"译码结果已写入根目录下的文件TextFile.txt中"<<endl; free(code); free(string); } //*************打印编码函数**************** void Code_printing() { int i; char *code; code=(char*)malloc(MaxC*sizeof(char)); cout<<"下面打印根目录下文件CodeFile.txt中的编码"<<endl; ifstream infile("CodeFile.txt",ios::in); if(!infile) { cerr<<"打开失败"<<endl; exit(1); } for( i=0;i<MaxC;i++) { infile>>code[i]; if(code[i]!='#') cout<<code[i]; else break; } infile.close(); cout<<endl; ofstream outfile("CodePrin.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } for(i=0;code[i]!='#';i++) { outfile<<code[i]; } outfile.close(); free(code); cout<<"------打印结束------"<<endl; cout<<"该字符形式的编码文件已写入文件CodePrin.txt中"<<endl; } //*************打印哈夫曼树函数**************** int numb=0; void coprint(HuffmanTree start,HuffmanTree HT) //start=ht+26这是一个递归算法 { if(start!=HT) { ofstream outfile("TreePrint.txt",ios::out); if(!outfile) { cerr<<"打开失败"<<endl; exit(1); } numb++; //number=0 该变量为已被声明为全局变量 coprint(HT+start->rchild,HT); //递归先序遍历 cout<<setw(5*numb)<<start->weight<<endl; //if(start->rchild==0) cout<<info[start-HT-1]<<endl; outfile<<start->weight; coprint(HT+start->lchild,HT); numb--; outfile.close(); } } void Tree_printing(HuffmanTree HT,int num) { HuffmanTree p; p=HT+2*num-1; //p=HT+26 cout<<"下面打印赫夫曼树"<<endl; coprint(p,HT); //p=HT+26 cout<<"打印工作结束"<<endl; } //*************主函数************************** int main() { char choice; do{ cout<<"************哈弗曼编/译码器系统***************"<<endl; cout<<"请选择您所需功能:"<<endl; cout<<"<I>:初始化哈弗曼树"<<endl; cout<<"<W>:输入待编码字符串"<<endl; cout<<"<E>:利用已建好的哈夫曼树进行编码"<<endl; cout<<"<D>:利用已建好的哈夫曼树进行译码"<<endl; cout<<"<P>:打印代码文件"<<endl; cout<<"<T>:打印哈夫曼树"<<endl; cout<<"<Q>:退出"<<endl; if(flag==0) { cout<<"请先初始化哈夫曼树,输入I"<<endl; cout<<"<系统将从根目录下的文件ABC.txt中读出26个字母并对字母进行编码>"<<endl; } cin>>choice; switch(choice) { case 'I':Initialization();break; case 'W':Input();break; case 'E':Encoding();break; case 'D':Decoding();break; case 'P':Code_printing();break; case 'T':Tree_printing(HT,n);break; case 'Q':;break; default:cout<<"输入的命令出错,请重新输入!"<<endl; } }while(choice!='Q'); free(w); free(info); free(HT); free(HC); system("pause"); return 0; }

立即下载
哈夫曼树的建立(根据输入的权值,建立一棵哈夫曼树)

根据输入的权值建立一棵哈夫曼树,并显示该树的结点序号、双亲结点、左/右孩子结点以及各结点所对应的哈夫曼编码。

立即下载
赫夫曼树的建立及编码

基于数据结构中的赫夫曼树的建立以及用赫夫曼树编码

立即下载
数据结构实验-哈夫曼树与哈夫曼编码

一、问题描述 运用哈夫曼算法构造哈夫曼树,并得到哈夫曼编码。 输入格式:10,5,21,18,8,13 二、实验目的 掌握哈夫曼算法。 三、实验内容及要求 1、构造哈夫曼树和哈夫曼编码的存储结构。 2、实现哈夫曼算法,实现哈夫曼树的存储并求出哈夫曼编码。

立即下载
赫夫曼树对英文26个字母的编码译码

26个字母的编码译码 赫夫曼树编码译码

立即下载
数据结构:树与二叉树

涵容二叉树遍历,赫夫曼树编码,树的存储等

立即下载
赫夫曼树和赫夫曼编码的存储表示

赫夫曼树和赫夫曼编码的存储表示,自己搞定的,关键是一些总结。一些风格和数学的重要性,程序风格如HT[s1].parent=HT[s2].parent = i就淫荡的不行了,要分行在VC6下才能运行,数学也很重要,一些纠结的问题的时候,算法就派上用场,之前写的Select函数得不出正确的结果。总结就是很想睡觉。碰到纠结的问题就是要熬,如果不熬,不断的调试,不断的想,那么永远是不可能得出结果来的

立即下载
赫夫曼编码

本代码实现赫夫曼树的编码,生成最优二叉树

立即下载
关闭
img

spring mvc+mybatis+mysql+maven+bootstrap 整合实现增删查改简单实例.zip

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
点击完成任务获取下载码
输入下载码
为了良好体验,不建议使用迅雷下载
img

赫夫曼树的算法,权值,编码,原始码

会员到期时间: 剩余下载个数: 剩余C币: 剩余积分:0
为了良好体验,不建议使用迅雷下载
VIP下载
您今日下载次数已达上限(为了良好下载体验及使用,每位用户24小时之内最多可下载20个资源)

积分不足!

资源所需积分/C币 当前拥有积分
您可以选择
开通VIP
4000万
程序员的必选
600万
绿色安全资源
现在开通
立省522元
或者
购买C币兑换积分 C币抽奖
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
为了良好体验,不建议使用迅雷下载
确认下载
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 0 0
为了良好体验,不建议使用迅雷下载
VIP和C币套餐优惠
img

资源所需积分/C币 当前拥有积分 当前拥有C币
5 4 45
您的积分不足,将扣除 10 C币
为了良好体验,不建议使用迅雷下载
确认下载
下载
您还未下载过该资源
无法举报自己的资源

兑换成功

你当前的下载分为234开始下载资源
你还不是VIP会员
开通VIP会员权限,免积分下载
立即开通

你下载资源过于频繁,请输入验证码

您因违反CSDN下载频道规则而被锁定帐户,如有疑问,请联络:webmaster@csdn.net!

举报

若举报审核通过,可返还被扣除的积分

  • 举报人:
  • 被举报人:
  • *类型:
    • *投诉人姓名:
    • *投诉人联系方式:
    • *版权证明:
  • *详细原因: