湖南省科技大学—数据结构（C语言版）算法6.12_huffman编码
湖南科技大学—数据结构（C语言版）算法6.12__huffman编码
提交: 20 解决: 12
[提交][状态][讨论版]
问题 I: 数据结构（C语言版）算法6.12__huffman编码
时间限制: 1 Sec 内存限制: 128 MB提交: 20 解决: 12
[提交][状态][讨论版]
题目描述
w存放n个字符的权值(权值均是大于0的正整数)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。其它未明示之处请参见教材P147页上的相关文字及算法描述。
输入
先输入权值的个数n（n>1）。
然后依次输入n个权值（权值均是大于0的正整数）
输出
与输入的n个权值相对应，依次输出对应的编码。
编码时，左孩子分支编码为0，右孩子分支编码为1。
样例输入
8
5 29 7 8 14 23 3 11
样例输出
0110
10
1110
1111
110
00
0111
010
#include<stdio.h>
#include<string.h>
#define len 100000
struct 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;
}