赫夫曼编码译码毕业论文

BTNode hafuNode; public BTNode creatHafuma(int[] a) { ArrayList s = new ArrayList(); for (int i = 0; i < ; i++) { (new BTNode(a[i])); } while (() > 1) { BTNode x = (0); BTNode newNode = new BTNode(); for (int i = 0; i < (); i++) { if ((i).data - () < 0) x = (i); } = x; (x); BTNode y = (0); for (int i = 0; i < (); i++) { if ((i).data - () < 0) y = (i); } = y; (y); = + ; (newNode); } return (0); }

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

#include<> #include<> #include<> #include <> typedef struct{ int weight; int parent,lchild,rchild; char data; }HTNode,*HuffmanTree; //*HuffmanTree既是指针也是数组，用来存放树枝typedef char **HuffmanCode; //存放结点void quanzhi(char *a,int *w,char *d,int &n) //权值计算{ int j=0; for(int i=0;i<100&&a[i]!='\0';i++) { for(int k=0;kdata=d[i-1]; p->lchild=p->parent=p->rchild=0; p->weight=w[i-1]; } for(;i<=m;++i,++p) { p->lchild=p->parent=p->rchild=0; p->weight=0; } for(i=n+1;i<=m;++i){ int s1,s2,u,t; for (u=1;u<=i-1;u++) if(HT[u].parent==0) {s1=u;break;} for(u=u+1;u<=i-1;u++){ if(HT[s1].weight>HT[u].weight&&HT[u].parent==0) s1=u; } for(t=1;t<=i-1;t++) if(HT[t].parent==0&&t!=s1){s2=t;break;} for(t=t+1;t<=i-1;t++){ if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1) s2=t; } 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=new char*[n+1]; char *cd=new char[n]; cd[n-1]='\0'; int start,c,f; 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'; else cd[--start]='1'; HC[i]=new char[n-start]; strcpy(HC[i],&cd[start]); } delete(cd);} void bianma(HuffmanCode HC,char *a,char *d,char *e) //编码{ int m1=0,m2=0; int i=0,j; while(a[i]!='\0'){ j=0; while(d[j]!='\0'){ if(a[i]==d[j]){ m1=0; while(HC[j+1][m1]!='\0') e[m2++]=HC[j+1][m1++]; break; } j++; } i++; } e[m2]='\0';} void yima(HuffmanTree HT,int n,char*e) //译码{ int m=2*n-1; for (int i=0;e[i]!='\0';++i){ if(HT[m].lchild==0){ cout<>o;switch(o){case 1: {cout<>a; while(a[1]=='\0') {cout<<"输入有误，请重新输入："; cin>>a; } for(int oo=0;oo<100;oo++)w[oo]=0; //初始化权值数组，赋值为0 quanzhi(a,w,d,n); //调用权值计算函数 HuffmanCoding(HT,HC,w,n,d); //构造哈弗曼树 cout<>e; yima(HT,n,e); //对输入译文译成原码 } break;case 3: {cout<

#include <>#include <>#include <>typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedef struct { unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/}HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n, int *s1, int *s2){ int i; int min; for(i=1; i<=n; i++) { if((*ht)[i].parent == 0) { min = i; i = n+1; } } for(i=1; i<=n; i++) { if((*ht)[i].parent == 0) { if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s1 = min; for(i=1; i<=n; i++) { if((*ht)[i].parent == 0 && i!=(*s1)) { min = i; i = n+1; } } for(i=1; i<=n; i++) { if((*ht)[i].parent == 0 && i!=(*s1)) { 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) { printf("%d ", HT[m].weight); outputHuffman(HT,HT[m].LChild); outputHuffman(HT,HT[m].RChild); }}void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/{ char *cd; int i; unsigned int c; int start; int p; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]='\0'; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/ { start=n-1; /*初始化编码起始指针*/ for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].LChild == c) cd[--start]='0'; /*左分支标0*/ else cd[--start]='1'; /*右分支标1*/ hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/ strcpy(hc[i],&cd[start]); } free(cd); for(i=1;i<=n;i++) printf("%d编码为%s\n",(*ht)[i].weight,hc[i]);}void main() { HuffmanTree HT; HuffmanCode HC; int *w; int i,n; // the number of elements; int wei; // the weight of a element; int m; printf("input the total number of the Huffman Tree:" ); scanf("%d",&n); w=(int *)malloc((n+1)*sizeof(int)); for(i=1;i<=n;i++) { printf("input the %d element's weight:",i); fflush(stdin); scanf("%d",&wei); w[i]=wei; } CrtHuffmanTree(&HT,w,n); m = 2*n-1; outputHuffman(HT,m); printf("\n"); CrtHuffmanCode(&HT,&HC,n); }

//D:\2010 代码\haffman\haffman\ 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\""#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) /** 绝对路径下读取 file message 中的num记录suoyou字符总数 ，放在nes【】中 equal to the buffer **/{ int i=0; char ch; ifstream infile("",ios::in | ios::out); if(!infile)//打开失败则结束 { cout<<"打开文件失败"<mes[i]=ch; i++; } message->num=i;//记录总字符数 ();//关闭文件}int writing_file(Message *message) /** 把从数组message 的信息write to disk， to save **/{ /* int i; ifstream outfile("",ios::in ); //打开文件 if( !outfile )//打开失败则结束 { cout<<"打开文件失败"<num;i++)//写文件 (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标记， [] 放不同字符，TotalNode 类型（char，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++)//建立叶子结点个数的编码 { >num-1;//起始位初始化 p=HuffNode[i].parent; c=i; while(p!=-1)//从叶结点向上爬直到到达根结点 { if(HuffNode[p].lchild==c)//左分支则为0 []=0; else []=1;//右分支则为1 ;//起始位向前移动 c=p; p=HuffNode[p].parent; } for(j=;jnum;j++)//保存求出的每个叶结点编码和起始位 HuffCode[i].bit[j]=[j]; HuffCode[i].start=; }}void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total) /** HuffNode[]to input the leaf HuffCode[]to input the code all is to the ,save the code **/{ /*打开HCode文件，失败则结束。将信息写进文件*/ int i,j; FILE *fp2=NULL; if((fp2 = fopen("","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) /* 将密文写到 */{ int i; FILE *fp3=NULL; if((fp3= fopen("","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) /** 密文翻译成明文，然后存到文件 **/{int i,j,mark[100],start[100],min,max; FILE *fp4=NULL; if((fp4 = fopen("","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);//建立哈夫曼编码 }