湖南省科技大学—数据结构（C语言版）算法6.12_huffman编码

湖南科技大学—数据结构（C语言版）算法6.12__huffman编码

问题 I: 数据结构（C语言版）算法6.12__huffman编码#include<stdio.h>#include<string.h>#define len 100000struct haha{ int start; int l[len]; int weight;}code[100],cd;struct xixi{ int weight; int parent; int l_child; int r_child;}tree[100];int a[300];int main(){ int n,k,i,j,m,m1,m2,x1,x2,pare,child; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%d",&k); tree[i].weight=k; tree[i].l_child=-1; tree[i].r_child=-1; tree[i].parent=-1; } m=2*n-1; for(i=n;i<m;i++) { tree[i].l_child=-1; tree[i].r_child=-1; tree[i].parent=-1; tree[i].weight=0; } for(i=0;i<n-1;i++) { m1=m2=1000000000;//记录权值 x1=x2=0;//记录节点所在位置 for(j=0;j<n+i;j++) { if(tree[j].weight<m1&&tree[j].parent==-1) { m2=m1; x2=x1; m1=tree[j].weight; x1=j; } else if(tree[j].weight<m2&&tree[j].parent==-1) { m2=tree[j].weight; x2=j; } } tree[x1].parent=n+i; tree[x2].parent=n+i; tree[n+i].weight=tree[x1].weight+tree[x2].weight; if(x1<x2)//一开始总是和老师的测试数据不一样原来要控制一下左右分支确不能随便连接编号小的在左 { tree[n+i].l_child=x1; tree[n+i].r_child=x2; } else { tree[n+i].l_child=x2; tree[n+i].r_child=x1; } // printf ("%d %d 的父亲是 %d\n",tree[x1].weight,tree[x2].weight,tree[n+i].weight); } for(i=0;i<n;i++) { cd.start=n-1; child=i; pare=tree[child].parent; while(pare!=-1) { if(tree[pare].l_child==child) cd.l[cd.start]=0; else cd.l[cd.start]=1; cd.start--; // printf("cd.start=%d\n",cd.start); child=pare; pare=tree[child].parent; } for(j=cd.start+1;j<n;j++) { code[i].l[j]=cd.l[j]; } code[i].start=cd.start+1; code[i].weight=tree[i].weight; // printf("code[i]=%d d=%d\n",code[i].start,n-code[i].start); } for(i=0;i<n;i++) { // printf ("%d 's Huffman code is: ", i); for (j=code[i].start; j < n; j++) { printf ("%d", code[i].l[j]); } printf("\n"); } } return 0;} #include<stdio.h>#include<string.h>#include<malloc.h>struct haha{int cnt;int id;//标记第几个字符串的防止重复计算防止重复出现某个串比如ababababc ab重复出现了好多次struct haha *next[26];}*root;int ans;struct haha * creat(){int i;struct haha *p;p=(struct haha *)malloc(sizeof(struct haha));p->cnt=1;p->id=-1;for(i=0;i<26;i++)p->next[i]=NULL;return p;}void update(char *s,int id){int d,pos,i;struct haha *p;p=root;d=strlen(s);for(i=0;i<d;i++){ pos=s[i]-'a';if(p->next[pos]==NULL){p->next[pos]=creat();p=p->next[pos];p->id=id;}else{p=p->next[pos];if(p->id!=id)//也就是说这个串的子串没有出现过{p->id=id;p->cnt++;}}} }void query(char *s){struct haha *p;int pos,i,d;p=root;d=strlen(s);for(i=0;i<d;i++){pos=s[i]-'a';if(p->next[pos]==NULL) return ;else{p=p->next[pos];}}ans=p->cnt;}int main(){int i,n,m,k;char s[30];root=creat(); scanf("%d",&n);for(k=0;k<n;k++){scanf("%s",s);for(i=0;s[i]!='\0';i++)update(&s[i],k);}scanf("%d",&m);while(m--){ans=0;scanf("%s",s);query(s);printf("%d\n",ans);}return 0;}

湖南省科技大学数据结构（C语言版）

热点推荐