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

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

问题 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

#include

#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

{

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

{

tree[i].l_child=-1;

tree[i].r_child=-1;

tree[i].parent=-1;

tree[i].weight=0;

}

for(i=0;i

{

m1=m2=1000000000;//记录权值

x1=x2=0;//记录 节点所在位置

for(j=0;j

{

if(tree[j].weight

{

m2=m1;

x2=x1;

m1=tree[j].weight;

x1=j;

}

else if(tree[j].weight

{

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

{

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

{

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

{

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

{

// 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

#include

#include

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

{

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

{

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

{

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;

}