程序设计：编写一个哈夫曼编码译码程序。

Question

按词频从小到大的顺序给出各个字符（不超过30个）的词频，根据词频构造哈夫曼树，给出每个字符的哈夫曼编码，并对给出的语句进行译码。
为确保构建的哈夫曼树唯一，本题做如下限定：
（1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
（2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。
生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。
【输入格式】
第一行输入字符个数n；
第二行到第n行输入相应的字符及其词频(可以是整数，与可以是小数）；
最后一行输入需进行译码的串。
【输出格式】
首先按树的先序顺序输出所有字符的编码，每个编码占一行；
最后一行输出需译码的原文，加上original:字样。
输出中均无空格
【样例输入】
3
m1
n1
c2
10110
【样例输出】
c:0
m:10
n:11
original:mnc

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define max 100
const int m=100;
int n,i,top=0,first=0,last=0,first1=0,last1=0;
int s[m],z[m];
typedef struct snodelinked{undefined
int data;
char bianma;
int parent;
struct snodelinked *Rson,*Lson,*next;
}snodelinked,*ptr;
ptr hfcreat(ptr head);
//void bianma(ptr root);
void preorder(ptr root);
void push(int s[],int &top,int x);
void pop(int s[],int &top);
void addq(int s[],int first,int &last,char x);
int delq(int s[],int &first,int last);
ptr hfinition();
void translate(ptr root);
int main(){undefined
ptr head,root;
head=hfinition();
root=hfcreat(head);
preorder(root);
// putchar(’\n’);
getchar();
translate(root);
return 0;
}
ptr hfinition(){undefined
ptr head,p;
scanf("%d",&n);
head=p=(ptr)malloc(sizeof(snodelinked));
head->data=max;
head->bianma=’ ‘;
getchar();
for(i=0;i<n;i++){undefined
p->next=(ptr)malloc(sizeof(snodelinked));
p=p->next;
scanf("%c%1d",&p->bianma,&p->data);
p->Lson=p->Rson=NULL;
p->parent=0;
}
p->next=head;
return head;
}
ptr hfcreat(ptr head){undefined
ptr t1,t2,p,q,r;
for(i=0;i<n-1;i++){undefined
r=(ptr)malloc(sizeof(snodelinked));
t1=head->next;
t2=t1->next;
r->data=t1->data+t2->data;
r->Lson=t1;
r->Rson=t2;
r->bianma=’ ‘;
t1->parent=0;
t2->parent=1;
head->next=t2->next;
p=head;
q=p->next;
while(1){undefined
if(r->data>=q->data){undefined
p=p->next;
q=p->next;
}else{undefined
r->next=q;
p->next=r;
break;
}
}
}
p=head->next;
free(head);
return p;
}
void preorder(ptr root){undefined
if(root->bianma!=’ ‘){undefined
putchar(root->bianma);
printf( “:”);
for(i=1;i<=top;i++){undefined
printf("%d",s[i]);
}
putchar(’\n’);
}
if(root->Lson!=NULL) {undefined
push(s,top,root->Lson->parent);
preorder(root->Lson);
top–;
}
if(root->Rson!=NULL) {undefined
push(s,top,root->Rson->parent);
preorder(root->Rson);
top–;
}
}
void push(int s[],int &top,int x){undefined
s[++top]=x;
}
void pop(int s[],int &top){undefined
printf("%d",s[top–]);
}
void translate(ptr root){undefined
ptr h;
h=root;
int y;
char x;
x=getchar();
printf(“original:”);
while(x!=’\n’){undefined
addq(z,first1,last1,x);
x=getchar();
}
while(first1!=last1){undefined
y=delq(z,first1,last1);
if(y== 0) {undefined
h = h->Lson;
}
else if(y== 1) h=h->Rson;
if(h->bianma!=’ '){undefined
putchar(h->bianma);
h=root;
}
}
}
void addq(int z[],int first,int &last,char x){undefined
if(x==‘0’) z[last]=0;
else if(x==‘1’) z[last]=1;
last=(last+1)%m;
}
int delq(int z[],int &first,int last){undefined
return z[first++];
}