在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
问题描述】 【数据描述】 //- - - - - 赫夫曼树的存储表示 - - - - - typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode; //用顺序存储结构表示赫夫曼树的结点结构定义 //动态分配数组存储Huffman编码表 【算法描述】 1.初始化:从键盘读入n个字符,以及它们的权值,建立Huffman树 【C源程序】 #include <stdio.h> #define N 10 /*待编码字符的个数,即树中叶结点的最大个数*/ #define M 2*N-1 /*树中总的结点数目*/ typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode; /*树中结点的结构*/ typedef struct { char data; /*待编码的字符*/ int weight; /*字符的权值 */ char code[N]; /*字符的编码 */ } HTCode; void Init(HTCode hc[],int *n){ /*初始化,读入待编码字符的个数n,从键盘输入n个字符和n个权值*/ int i; printf("/ninput n="); scanf("%d",&(*n)); printf("/ninput %d character/n",*n); for (i=1;i<=*n;i++) hc[i].data=getch(); printf("/ninput %d weight/n",*n); for (i=1;i<=*n;i++) scanf("%d",&(hc[i].weight)); } void Select(HTNode ht[],int k,int *s1,int *s2){ /*ht[1…k]中选择parent为0,并且weight最小的两个结点 其序号由指针变量s1,s2指向*/ int i; for (i=1;i<=k && ht[i].parent!=0 ;i++); *s1=i; for (i=1;i<=k;i++) if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight) *s1=i; for (i=1; i<=k ; i++) if (ht[i].parent==0 && i!=*s1) break; *s2=i; for (i=1;i<=k;i++) if ( ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight) *s2=i; } void HuffmanCoding(HTNode ht[],HTCode hc[],int n){ /*构造Huffman树ht,并求出n个字符的编码*/ char cd[N]; int i,j,m,c,f,s1,s2,start; m=2*n-1; for (i=1;i<=m;i++){ if (i<=n) ht[i].weight=hc[i].weight; else ht[i].weight=0; ht[i].parent=ht[i].lchild=ht[i].rchild=0; } for (i=n+1;i<=m;i++){ 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; } cd[n-1]='/0'; for (i=1;i<=n;i++) { start=n-1; for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) if (ht[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; strcpy(hc[i].code,&cd[start]); } } main(){ int i,m,n,w[N+1]; HTNode ht[M+1]; HTCode hc[N+1]; Init(hc,&n); /*初始化*/ HuffmanCoding(ht,hc,n);/*构造Huffman树,并形成字符的编码*/ /*输出字符的编码*/ for (i=1;i<=n;i++)printf("/n%c --- %s",hc[i].data,hc[i].code); } 【测试数据】 1. 根据运行提示,依次输入待编码的字符个数和这些字符,以及每个字符的权值: input n=4↙ input 4character abcd↙ input4 weight 7 5 2 4↙ 输出: a --- 0 b --- 10 c --- 110 d --- 111 2.可根据运行提示,自行指定数据,观察程序的运行结果。 【说明】 下面的方法没有说明,不过可以直接运行! #include<stdio.h> typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef struct { char ch; }HuffmanCode; typedef struct { char ch; }sw; typedef struct { HuffmanTree HT; }huf; void select(HTNode * HT,int n,int *n1,int *n2) { int i=1; while(HT[i].parent!=0) i++; *n1=i; i++; while(HT[i].parent!=0) i++; *n2=i; if(HT[*n1].weight<HT[*n2].weight) { n3=*n1;*n1=*n2;*n2=n3;} for(i++;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight<HT[*n1].weight) *n1=i; else if(HT[i].weight<HT[*n2].weight) *n2=i; } } }
{ HuffmanTree p; char *cd;
m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;i++,p++,w++) {p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;} for(;i<=m;i++,p++) {p->weight=0;p->ch='^';p->parent=0;p->lchild=0;p->rchild=0;} for(i=n+1;i<=m;i++) { 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; } HC=(HuffmanCode *)malloc((n+1)*sizeof(char)); 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'; else cd[--start]='1'; HC[i].ch=HT[i].ch; HC[i].chs=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i].chs,&cd[start]); printf("%c %-10s\n",HC[i].ch,HC[i].chs); }
HUF->HC=HC; return HUF; } char * convert(char *chars,char *chars1,HuffmanCode *hc,int n) { char *p=chars; int i; strcpy(chars1,"");
{ i=1; while(hc[i].ch!=*p&&i<=n) i++; strcat(chars1,hc[i].chs); p++; }
return chars1; } void transcode(HuffmanTree ht,char *chars2,char*chars3) { int i=1,p; char *q=chars2;char *r=chars3;
p=i;
{ while(ht[p].lchild!=0 && *q) { if(*q=='0') p=ht[p].lchild; else p=ht[p].rchild; q++; } if(ht[p].lchild==0) {*r=ht[p].ch;r++;} p=i;
printf("the chars are:"); puts(chars3);
void input(int *n,sw *w) { int i; printf("input the count of char:"); /*输入字符的数目*/ scanf("%d",n);
for(i=1;i<=*n;i++,w++) {printf("input the %dth char and weight:",i); /*输入每个节点的字符和出现的次数*/ fflush(stdin); scanf("%c%d",&w->ch,&w->weight); }
void main() {HTNode HT; HuffmanCode HC,*hc; HuffmanTree ht; huf *HUF,huf2; int n; sw w[40]; char ch,inchar[500],outchar[1000]; char *abc; char *p=inchar; input(&n,w); HUF=HuffmanCoding(&HT,&HC,w,n,&huf2); printf("input chars to translate and end with '#':"); fflush(stdin);/*清除流,解决输入干扰*/ ch=getchar(); while(ch!='#') {*p=ch; p++; ch=getchar(); } *p='\0'; hc=HUF->HC; ht=HUF->HT; abc=convert(inchar,outchar,hc,n); transcode(ht,abc,outchar); getchar(); getchar(); } |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论