首页天道酬勤数据结构哈夫曼树编码(霍夫曼树编码与译码)

数据结构哈夫曼树编码(霍夫曼树编码与译码)

admin 05-26 22:14 127次浏览
#include<iostream>#include<stdlib.h>#include<cstring>using namespace std;typedef struct hftree{int might;int parent,lch,rch;char data; }*tree,node;typedef char** treecode;int length;//字符串长度; void chushi(tree &hf,int n)//初始话 {hf=new node[2*n];for(int i=1;i<=2*n-1;i++){hf[i].data='\0';hf[i].might=0;hf[i].lch=0;hf[i].rch=0;hf[i].parent=0;}} void select(tree T,int n,int &s1,int &s2)//找出权值最小的两个; { int k,m;k=m=1000000; for(int j=1;j<=n;j++){if(m>T[j].might&&T[j].parent==0){m=T[j].might;s1=j;} } for(int i=1;i<=n;i++){ if(i!=s1&&k>T[i].might&&T[i].parent==0){k=T[i].might;s2=i;}}} void hftree(tree &hf,int n)//创建gtdyb树 {int s1,s2;if(n<=1) return;int m=2*n-1; for(int i=n+1;i<=m;++i){select(hf,i-1,s1,s2);hf[s1].parent=i;hf[s2].parent=i;if(s1<=s2){ hf[i].lch=s1; hf[i].rch=s2;}else{hf[i].lch=s2; hf[i].rch=s1;}hf[i].might=hf[s1].might+hf[s2].might;}}void codetree(tree hf,treecode &hc,int n)//获取字符的编码值 { int m,p; hc=new char*[n+1]; //指针数组; char *cd=new char[n];//存放编码 cd[n-1]='\0'; for(int i=1;i<=n;i++) { int start=n-1; m=i;p=hf[i].parent; while(p!=0) { --start; if(hf[p].lch==m) { cd[start]='0';}else cd[start]='1';m=p; p=hf[p].parent; }hc[i]=new char[n-start]; strcpy(hc[i],&cd[start]); }delete []cd;}void input(tree &hf,int &n,char *date)//输入字符串 { char *a=date;int length_1;int num[256]={0};int b[256];int c[256];cout<<"输入字符串:"; getchar();gets(a);length_1=strlen(a);for(int i=0;i<length_1;i++){num[(int)a[i]]++;//统计每个字符的权值 }n=0;for(int i=0;i<256;i++){if(num[i]!=0){ b[n]=num[i]; c[n]=(char)i; ++n;}}hf=new node[2*n];for(int i=1;i<=2*n-1;i++){hf[i].data='\0';hf[i].might=0;hf[i].lch=0;hf[i].rch=0;hf[i].parent=0;}for(int i=1;i<=n;i++){hf[i].might=b[i-1];hf[i].data=c[i-1];}} int weizhi(tree hf,char *q,int n) //获取字符在树中的位置 {char *date=q; for(int j=1;j<=n;++j) { if(*date==hf[j].data) return j;} }void bianmachar(tree hf,char *q,treecode &result,int n)//对字符串编码 {char *date=q;char *cd; int m,p;result=new char * [length+1];//存放每个字符的编码值; cd=new char[n]; cd[n-1]='\0'; for(int i=0;i<length;++i) { m=weizhi(hf,&date[i],n);//获取每个字符在树中的位置 int start=n-1; p=hf[m].parent; while(p!=0) { --start; if(hf[p].lch==m) { cd[start]='0';}else cd[start]='1';m=p; p=hf[p].parent; }result[i+1]=new char[n-start];strcpy(result[i+1],&cd[start]); }delete cd;}void chu(tree hf,treecode hc,treecode result,int n)//输出编码 {int m=2*n-1;cout<<"每个字符在树中的位置"<<endl; for(int i=1;i<=m;i++){cout<<i<<" "<<hf[i].data<<" "<<hf[i].might<<" "<<hf[i].parent<<" "<<hf[i].lch<<" "<<hf[i].rch<<endl;}cout<<"每个字符的编码"<<endl; for(int i=1;i<=n;i++){cout<<hf[i].data<<" "<<hc[i]<<endl;} cout<<"对字符串的编码:";for(int j=1;j<=length;j++){cout<<result[j];}}void input_(tree &hf,int &n) //输入每个字符和对应的权值{cout<<"输入字符和对应的权值"<<endl; for(int i=1;i<=n;i++){cin>>hf[i].data;cin>>hf[i].might;}} void Decodehf(tree hf,char *m,int n)//译码 {char*date=m;//编码字符串int LL=strlen(date);//编码字符串长度 char data[100];//解码字符串; int p=2*n-1;//获取根节点的位置; int j=0;//头指针 for(int i=0;i<length;i++){if(date[i]=='0') p=hf[p].lch;else if(date[i]=='1')p=hf[p].rch;if(hf[p].lch==0&&hf[p].rch==0){data[j]=hf[p].data;p=2*n-1;++j;} }cout<<"对应编码:"; for(int k=0;k<j;k++){cout<<data[k];}cout<<endl; } void Xmb()//界面 {cout<<"\t\t\t------------------------------------------"<<endl; cout<<"\t\t\t|************gtdyb编码译码**************|"<<endl; cout<<"\t\t\t|----------------------------------------|"<<endl; cout<<"\t\t\t|********1.对字符串进行编码译码**********|"<<endl; cout<<"\t\t\t|----------------------------------------|"<<endl; cout<<"\t\t\t|********2.输入字符的权值编码译码********|"<<endl; cout<<"\t\t\t------------------------------------------"<<endl;}int main(){char a;char date_1[100];//输入字符串统计权值 char date_2[100];//需要要编码的字符串 char date_3[100];//存储译码的字符串tree hf; //hfm树 treecode hc;//存储每个字符的译码 treecode result;//存放译码的字符串 int n;//拥有权值的字符个数 while(1){Xmb();cout<<"输入相应命令:"; cin>>a;switch(a){case '1':input(hf,n,date_1); hftree(hf,n);//创建gtdyb树 codetree(hf,hc,n);//每个字符的编码 cout<<"输入需要编码的字符串:";gets(date_2);length=strlen(date_2);bianmachar(hf,date_2,result,n);//字符串的编码 chu(hf,hc,result,n);cout<<endl;cout<<"输入需要译码的编码:" ; gets(date_3);Decodehf(hf,date_3,n);break;case '2':cout<<"输入字符个数:";cin>>n;chushi(hf,n);//对gtdyb树初始化 input_(hf,n);//输入字符和对应的权值 hftree(hf,n);codetree(hf,hc,n);cout<<"输入需要编码的字符串:";getchar();gets(date_2);length=strlen(date_2);bianmachar(hf,date_2,result,n);chu(hf,hc,result,n);cout<<endl;cout<<"输入需要译码的编码:" ; gets(date_3);Decodehf(hf,date_3,n);break;case '0':exit(0);}}}


分布式版Redis架构 云内存 UMem Redis黑马程序员JVM笔记04-内存模型SSH的​SpringMVC注解怎么使用
哈夫曼树平均码长(霍夫曼树) huffman树的特点(霍夫曼树-原理、代码实现与应用)
相关内容