[NOJ]数据结构实验3.1 哈夫曼编/译码器

#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct HTNode
{int weight;int parent,lchild,rchild;char data;
}HTNode;
typedef struct HCNode
{int bit[200];int start;
}HCNode;HTNode ht[1005];
HCNode hc[200];
int str[1005]={0};
int num=0;void Select(int pos,int *x1,int *x2)  //找两个最小权的无父结点的结点
{    int m1=1000,m2=1000;int j;for(j=1;j<pos;j++)	{if(ht[j].weight<m1&&ht[j].parent==0){ 	m2=m1;*x2=*x1;m1=ht[j].weight;*x1=j;}else if(ht[j].weight<m2&&ht[j].parent==0){	m2=ht[j].weight;*x2=j;}}
}void init(int n)  //树初始化
{int i,j,x1,x2;char c;for(i=1;i<=2*n-1;i++){ht[i].weight=0;ht[i].lchild=0;ht[i].parent=0;ht[i].rchild=0;}for(i=1;i<=n;i++){getchar();scanf("%c",&ht[i].data);}for(i=1;i<=n;i++) scanf("%d",&ht[i].weight);for(i=1;i<n;i++){Select(n+i,&x1,&x2);ht[x1].parent=n+i; ht[x2].parent=n+i;ht[n+i].weight=ht[x1].weight+ht[x2].weight;ht[n+i].lchild=x1;ht[n+i].rchild=x2;}
}void getnum(int n)  //编码
{int i,j;HCNode x;for(i=1;i<=n;i++){x.start=n;int cur=i;int par=ht[cur].parent;while(par!=0){if(ht[par].lchild==cur) x.bit[x.start]=0;else x.bit[x.start]=1;x.start--;cur=par;par=ht[cur].parent;}for(j=x.start+1;j<=n;j++) hc[i].bit[j]=x.bit[j];hc[i].start=x.start+1;}
}void print(int n)  //输出编码
{char code[1000];int i,j,k;scanf("%s",code);for(i=0;i<strlen(code);i++){for(j=1;j<=n;j++){if(code[i]==ht[j].data){for(k=hc[j].start;k<=n;k++){printf("%d",hc[j].bit[k]);str[num]=hc[j].bit[k];num++; }}}}printf("\n");
}void decode(int n)  //译码并输出
{int i=0;int t;while(i<num){t=2*n-1;while(ht[t].lchild!=0&&ht[t].rchild!=0){if(str[i]==0) t=ht[t].lchild;else t=ht[t].rchild;i++;}printf("%c",ht[t].data);}
}int main()
{int n;scanf("%d",&n);init(n);getnum(n);print(n);decode(n);return 0;
}