哈夫曼编码与译码，下面代码哪里有错？

Question

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

#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-]);
}
void translate(ptr rooundefinedt){
ptr h;
h=root;
int y;
char x;
x=getchar();
printf("original:");              undefined
while(x!='\n'){
addq(z,first1,last1,x);
x=getchar();               undefined
}
while(first1!=last1){
y=delq(z,first1,last1);  undefined
if(y== 0) {
h = h->Lson;
}
else if(y== 1) h=h->Rson;
if(h->bianma!=' '){
putchar(h->bianma);
h=root;        undefined
}
}
}
void addq(int z[],intundefined first,int &last,char x){
if(x=='0') z[last]=0;
else if(x==undefined'1') z[last]=1;
last=(last+1)%m;
}
int delq(int z[],int &first,int last){
return z[first++]; undefined
}                                


```_

Answer 1

代码中存在多处语法错误和逻辑错误，下面列出需要修改的地方：

1.在结构体中，数据类型应该是int而不是undefined。

2.在preorder函数中，top-]应该是top--。

3.在translate函数中，rooundefinedt应该是root，undefined应该是单引号而不是双引号。

4.在addq函数中，undefined应该是单引号而不是双引号。

5.在delq函数中，函数体中应该加上return语句。

6.在translate函数中，应该在原文输出之前先输出"original:"。

7.在preorder函数中，应该在遍历左子树之前将左子树的父节点入栈。

8.在preorder函数中，应该在遍历完左子树之后将栈顶元素出栈。

9.在translate函数中，应该在每次找到一个叶子节点的时候将h重新赋值为root。

修改后的代码如下：

#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{
    int data;
    char bianma;
    int parent;
    struct snodelinked *Rson,*Lson,*next;
}snodelinked,*ptr;
ptr hfcreat(ptr head);
void preorder(ptr root);
void push(int s[],int &top,int x);
void pop(int s[],int &top);
void addq(int z[],int first,int &last,char x);
int delq(int z[],int &first,int last);
ptr hfinition();
void translate(ptr root);
int main(){
    ptr head,root;
    head=hfinition();
    root=hfcreat(head);
    preorder(root);
    printf("original:");
    getchar();
    translate(root);
    return 0;
}
ptr hfinition(){
    ptr head,p;
    scanf("%d",&n);
    head=p=(ptr)malloc(sizeof(snodelinked));
    head->data=max;
    head->bianma=' ';
    getchar();
    for(i=0;i<n;i++){
        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){
    ptr t1,t2,p,q,r;
    for(i=0;i<n-1;i++){
        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){
            if(r->data>=q->data){
                p=p->next;
                q=p->next;
            }else{
                r->next=q;
                p->next=r;
                break;
            }
        }
    }
    p=head->next;
    free(head);
    return p;
}
void preorder(ptr root){
    if(root->bianma!=' '){
        putchar(root->bianma);
        printf(":");
        for(i=1;i<=top;i++){
            printf("%d",s[i]);
        }
        putchar('\n');
    }
    if(root->Lson!=NULL) {
        push(s,top,root->parent);
        preorder(root->Lson);
        pop(s,top);
    }
    if(root->Rson!=NULL) {
        push(s,top,root->parent);
        preorder(root->Rson);
        pop(s,top);
    }
}
void translate(ptr root){
    ptr h;
    h=root;
    int y;
    char x;
    x=getchar();
    while(x!='\n'){
        addq(z,first1,last1,x);
        x=getchar();
    }
    while(first1!=last1){
        y=delq(z,first1,last1);
        if(y==0) {
            h = h->Lson;
        }
        else if(y==1) h=h->Rson;
        if(h->bianma!=' '){
            putchar(h->bianma);
            h=root;
        }
    }
}
void addq(int z[],int first,int &last,char x){
    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){
    return z[first++];
}