哈夫曼编码译码毕业论文

class HaffmanNode //哈夫曼树的结点类{ int weight; //权值 int parent,left,right; //父母结点和左右孩子下标 public HaffmanNode(int weight) { this.weight = weight; this.parent=-1; this.left=-1; this.right=-1; } public HaffmanNode() { this(0); } public String toString() { return this.weight+", "+this.parent+", "+this.left+", "+this.right; } return code; } public static void main(String[] args) { int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合 HaffmanTree htree = new HaffmanTree(weight); System.out.println("哈夫曼树的结点数组:\n"+htree.toString()); String[] code = htree.haffmanCode(); System.out.println("哈夫曼编码:"); for (int i=0; i

程序实现c语言实现:费诺编码

//D:\2010 代码\haffman\haffman\Node_statement.h#define MAXVALUE 1000//定义最大权值#define MAXBIT 100//定义哈夫曼树中叶子结点个数typedef struct{ char data;//字符值 int num;//某个值的字符出现的次数}TotalNode;//统计结点，包括字符种类和出现次数typedef struct{ TotalNode tot[300];//统计结点数组 int num;//统计数组中含有的字符个数}Total; //统计结构体，包括统计数组和字符种类数typedef struct{ char mes[300];//字符数组 int num;//总字符数}Message;//信息结构体，包括字符数组和总字符数typedef struct{ int locked[500];//密码数组 int num;//密码总数}Locking;//哈夫曼编码后的密文信息typedef struct{ char data;//字符 int weight;//权值 int parent;//双亲结点在数组HuffNode[]中的序号 int lchild;//左孩子结点在数组HuffNode[]中的序号 int rchild;//右孩子结点在数组HuffNode[]中的序号}HNodetype;//哈夫曼树结点类型，包括左右孩子，权值和信息typedef struct{ int bit[MAXBIT]; int start;}HCodetype;//哈夫曼编码结构体，包括编码数组和起始位void reading_file(Message *message);//从文件中读取信息int writing_file(Message *message);//将信息写进文件void total_message(Message *message,Total *total);//统计信息中各字符的次数void HaffmanTree(Total *total,HNodetype HuffNode[]);//构建哈夫曼树void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼编码void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//将编码规则写进文件void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//给文件信息加密编码void writing_lock(Locking *locking);//将已编码信息写进文件void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);void display(Total *total,HNodetype HuffNode[]);void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//将已编码信息翻译过来并写进文//D:\2010 代码\haffman\haffman\function_mian.cpp#include"Node_statement.h"#include#include#include "cstdlib"using namespace std;int main(){ int i,j,choice,mark=0;//mark标记文件信息是否读入到内存中 HNodetype HuffNode[500];//保存哈夫曼树中各结点信息 HCodetype HuffCode[300]; Locking *locking; Total *total; Message *message; locking=new Locking; locking->num=0; total=new Total; total->num=0; message=new Message; message->num=0; //初始化变量 printf("┏ ┓\n"); printf("┣ haffman_code system ┫ \n"); printf("┗ ┛\n"); printf("\n\n"); choice=0; while(choice!=7 ){ printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n "); printf(" 0:go \n"); printf("※********** 1：从文件读取信息**********************※\n"); printf(" *********** 2：显示编码规则 ********************* \n"); printf(" ********** 3：将原文件信息写进文件 ************ \n"); printf(" ********* 4：将编码规则写进文件 ************ \n"); printf(" ********** 5：将编码后的信息写进文件 ********** \n"); printf(" *********** 6：将译码后的信息写进文件 *********\n"); printf("※***********7：退出 *****************************※\n"); printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n "); printf(" please input the choice "); cin>>choice; switch(choice) { case 1: reading_file(message);//从文件中读取信息 mark=1; break; case 2://显示编码规则 if(mark==0)cout<<"请先从文件中读取信息!"<num;i++)//显示编码规则 { cout<tot[i].data<<" "; for(j=HuffCode[i].start+1;jnum;j++) cout<num-1;i++) { printf("data weight lchild rchild parent \n"); printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent); } }void reading_file(Message *message) /** 绝对路径下读取a_test.txt file message 中的num记录suoyou字符总数 ，放在nes【】中 equal to the buffer **/{ int i=0; char ch; ifstream infile("a_test.txt",ios::in | ios::out); if(!infile)//打开失败则结束 { cout<<"打开a_test.txt文件失败"<mes[i]=ch; i++; } message->num=i;//记录总字符数 infile.close();//关闭文件}int writing_file(Message *message) /** 把从数组message 的信息write to disk，a_test1.txt to save **/{ /* int i; ifstream outfile("a_test1.txt",ios::in ); //打开文件 if( !outfile )//打开失败则结束 { cout<<"打开a_test1.txt文件失败"<num;i++)//写文件 outfile.put(message->mes[i]); cout<<"信息写进文件成功"<num;i++) fprintf(fp1,"%d ",message->mes[i]); printf("文件写入成功!\n"); i=fclose(fp1); if(i==0) printf("文件关闭成功!\n");else printf("文件关闭失败!\n");}void total_message(Message *message,Total *total) /** 统计message中不同字符 的个数，和相同字符重复的次数，重复字符用mark标记， total.tot[] 放不同字符，TotalNode 类型（char，num） total.num 统计不同字符个数 使total这块内存空间有数据， **/{ int i,j,mark; for(i=0;inum;i++)//遍历message中的所有字符信息 { if(message->mes[i]!=' ')//字符不为空格时 { mark=0; for(j=0;jnum;j++)//在total中搜索当前字符 if(total->tot[j].data==message->mes[i])//搜索到，则此字符次数加1，mark标志为1 { total->tot[j].num++; mark=1; break; } if(mark==0)//未搜索到，新建字符种类，保存进total中，字符类加1 { total->tot[total->num].data=message->mes[i]; total->tot[total->num].num=1; total->num++; } } }}void HaffmanTree(Total *total,HNodetype HuffNode[]) /**create the haffman tree 不同字符个数为叶子节点个数对应书上的n， 相同字符的个数为其权值weight； get HuffNode to store the tree **/{ int i,j,min1,min2,x1,x2; for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼树并存入叶子结点权值和信息 { if(i<=total->num-1) HuffNode[i].data=total->tot[i].data; HuffNode[i].weight=total->tot[i].num; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for(i=0;inum-1;i++) { min1=min2=MAXVALUE; x1=x2=0; for(j=0;jnum+i;j++)//选取最小x1和次小x2的两权值 { if(HuffNode[j].parent==-1&&HuffNode[j].weightnum+i;//修改亲人结点位置 HuffNode[x2].parent=total->num+i; HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[total->num+i].lchild=x1;//左孩子比右孩子权值小 HuffNode[total->num+i].rchild=x2; }}void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total) /*** haffman to code (0,10,110,) 得到每个不同字符（叶子）的编码， 存贮在数组HuffCode【】中,bit[] store the char,start store the loction **/{ int i,j,c,p; HCodetype cd; for(i=0;inum;i++)//建立叶子结点个数的编码 { cd.start=total->num-1;//起始位初始化 p=HuffNode[i].parent; c=i; while(p!=-1)//从叶结点向上爬直到到达根结点 { if(HuffNode[p].lchild==c)//左分支则为0 cd.bit[cd.start]=0; else cd.bit[cd.start]=1;//右分支则为1 cd.start--;//起始位向前移动 c=p; p=HuffNode[p].parent; } for(j=cd.start+1;jnum;j++)//保存求出的每个叶结点编码和起始位 HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start; }}void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total) /** HuffNode[]to input the leaf HuffCode[]to input the code all is to the a_test2.txt ,save the code **/{ /*打开HCode文件，失败则结束。将信息写进文件*/ int i,j; FILE *fp2=NULL; if((fp2 = fopen("a_test2.txt","at"))==NULL) { printf("can't open the file\n"); exit(0); } for(i=0;inum;i++) {fprintf(fp2,"%d ",HuffNode[i].data); printf(" "); for(j=HuffCode[i].start+1;jnum;j++) fprintf(fp2,"%d ",HuffCode[i].bit[j]); } printf("编码规则写进文件成功!\n"); i=fclose(fp2); if(i==0) printf("文件关闭成功!\n");else printf("文件关闭失败!\n"); }void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)/***对messag操作，对所有字符加密，结果存贮在数组locked[]中，locking 记录已经加密后的密文**/{ int i,j,m; for(i=0;inum;i++)//把相同的不同的字符全部 遍历 { if(message->mes[i]==' ')//碰到空格则以-1形式保存进locked数组中 { locking->locked[locking->num]=-1; locking->num++; } else for(j=0;jnum;j++)//从total中找到对应的字符 { if(HuffNode[j].data==message->mes[i]) //找到在HuffNode 中对应字符，找到下标j // 在HuffCode for(m=HuffCode[j].start+1;mnum;m++)///////// ! { locking->locked[locking->num]=HuffCode[j].bit[m];//加密 locking->num++; } } }}void writing_lock(Locking *locking) /* 将密文写到a_test3.txt */{ int i; FILE *fp3=NULL; if((fp3= fopen("a_test3.txt","at"))==NULL) { printf("can't open the file\n"); exit(0); } for(i=0;inum;i++) { if(locking->locked[i]==-1) printf(" "); else fprintf(fp3,"%d ",locking->locked[i]); } printf("已编码信息写进文件成功!\n"); i=fclose(fp3); if(i==0) printf("文件关闭成功!\n");else printf("文件关闭失败!\n");}void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total) /** 密文翻译成明文，然后存到文件 a_test4.txt **/{int i,j,mark[100],start[100],min,max; FILE *fp4=NULL; if((fp4 = fopen("a_test4.txt","at"))==NULL) { printf("can't open the file\n"); exit(0); } for(i=0;inum;i++)//start数组初始化 { start[i]=HuffCode[i].start+1;//。。。。 } for(i=0;inum;i++)//mark数组初始化 { mark[i]=1; } min=0;for(max=0;maxnum;max++)//写文件 { if(locking->locked[max]==-1)//碰到空格信息则直接输出空格 { printf(" ");//把空格写到文件 min++; } else { for(i=min;i<=max;i++)//查找从min开始到max的编码对应的信息 { for(j=0;jnum;j++) { if(start[j] == total->num+1) mark[j]=0; //对应编码比所给编码短则不在比较 if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]]) start[j]++; else mark[j]=0; } } for(i=0;inum;i++)//找到对应信息，则写进文件 { if(mark[i]==1&&start[i]==total->num) { fprintf(fp4,"%d ",HuffNode[i].data);//写到文件outfile break; } } if(i!=total->num) min=max+1; for(i=0;inum;i++)//start数组初始化 { start[i]=HuffCode[i].start+1; } for(i=0;inum;i++)//mark数组初始化 { mark[i]=1; } } } printf("文件写入成功!\n"); i=fclose(fp4); if(i==0) printf("文件关闭成功!\n");else printf("文件关闭失败!\n");}void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message){ total_message(message,total);//统计信息中各字符的出现次数 HaffmanTree(total,HuffNode);//构建哈夫曼树 HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码 }

(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. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 本文来源【学网】网站链接是