哈夫曼编/译码器（C语言）

最近国旗班训练强度有些大，平时几乎腾不出时间写题。。
这道题感觉有点难度，看了不少大佬的题解才有些许思路，望大家多多指点。

哈夫曼编码就是构造权重最小的树，我觉得图已经很好了：

编码时从数据开始向上找，判断当前节点是其父节点的左支还是右支，直到当前节点为头结点，再将它反过来就是所求编码。

解码从头结点开始走，0走左支1走右支，直到走到叶节点为止，叶节点中数据就是所求数据。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 30 //叶子结点最大值
#define M 2*N-1 //所有结点最大值

typedef struct{
    char data;
    int weight;
    int parent;
    int Lchild;
    int Rchild;
    int flag;
}HTNode,HuffmanTree[M+1]; //0号单元不用


int select(HuffmanTree ht,int n);
void InitHuffmanTree(HuffmanTree ht,int n);
void crtHuffmanTree(HuffmanTree ht,int n);
void printHuffmanTree(HuffmanTree ht,int n);

void InitHuffmanTree(HuffmanTree ht,int n)//初始哈夫曼树
{
    for(int i=1;i<=n;i++)//初始化叶子节点
    {
        ht[i].data='\0';
        ht[i].Lchild=0;
        ht[i].Rchild=0;
        ht[i].weight=0;
        ht[i].parent=0;
        ht[i].flag=0;
        getchar();//消除空格
        ht[i].data=getchar();
    }
     for(int i=1;i<=n;i++)//初始化叶子节点
    {
        scanf("%d",&ht[i].weight);
    }
    int m=2*n-1;
    for(int i=n+1;i<=m;i++)//初始化非叶子节点
    {
        ht[i].Lchild=0;
        ht[i].Rchild=0;
        ht[i].weight=0;
        ht[i].parent=0;
         ht[i].flag=0;
    }

}

void crtHuffmanTree(HuffmanTree ht,int n)//构建哈夫曼树
{
   for(int i=n+1;i<=(2*n-1);i++)
   {
       int s1=select(ht,i-1);//注意这里的i-1
       int s2=select(ht,i-1);
       ht[i].weight = ht[s1].weight+ht[s2].weight;
       ht[s1].parent=i;
       ht[s2].parent=i;
       ht[i].Lchild=s1;
       ht[i].Rchild=s2;
   }
}

int select(HuffmanTree ht,int n)//选择最小权值的结点下标
{
    int i,temp,min;
    for(i=1;i<=n;i++)//设置初始下标和权值
    {
        if(ht[i].flag==0)
        {
            temp = ht[i].weight;//初始权值
            min=i;//初始下标
            break;
        }
    }
    for(i=1;i<=n;i++)
    {
        if(ht[i].flag==0&&temp>ht[i].weight)
        {
            temp=ht[i].weight;
            min = i;
        }
    }
    ht[min].flag=1;
    return min;
}

int GetCode(int A[],HuffmanTree ht ,int n)//获得编码（从下往上反向）
{
    int length=0,i,j,get;
    char s[100];
    getchar();//清除换行符
    gets(s);
    int m=strlen(s);
    for(i=m-1;i>=0;i--)//注意此处从后往前处理字符串
    {
        for(j=1;j<=n;j++)
        {
            if(s[i]==ht[j].data)
            {
                get = j;
            }
        }
        while(ht[get].parent)
        {
            if(ht[ht[get].parent].Lchild==get)
            {
                A[length]=0;
            }
            else{
                A[length]=1;
            }
            length++;
            get=ht[get].parent;
        }
    }
    return length-1;
}

void printCode(int A[],int length)//打印编码
{
    int i;
    for(i=length;i>=0;i--)
    {
        printf("%d",A[i]);
    }
    printf("\n");
}

int GetreCode(int A[],char B[],HuffmanTree ht,int length1,int n)//解码
{
    int i,length2=0,cur;
    for(i=length1,cur=2*n-1;i>=0;i--)
    {
        if(A[i])
        {
            cur=ht[cur].Rchild;
            if(ht[cur].Rchild==0)
            {
                B[length2]=ht[cur].data;
                length2++;
                cur=2*n-1;
            }
        }
        else{
            cur=ht[cur].Lchild;
            if(ht[cur].Lchild==0)
            {
                B[length2]=ht[cur].data;
                length2++;
                cur=2*n-1;
            }
        }
    }
    return length2-1;
}

void printreCode(char B[],int length2)//解码打印
{
    int i;
    for(i=0;i<=length2;i++)
        printf("%c",B[i]);
    printf("\n");
}

void printHuffmanTree(HuffmanTree ht,int n)//打印哈夫曼树
{   printf("结点  weigh  parent Lchild Rchild\n");
    for(int i=1;i<=n;i++)
    {//\t为补全的意思
        printf("%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].Lchild,ht[i].Rchild);
    }
    printf("\n");
}
int main()
{
    HuffmanTree ht;
    int n;//n为所需的结点数
    int A[100];//存储编码
    char B[100];//存储输出的字符串
    scanf("%d",&n);
     InitHuffmanTree(ht,n);//初始化
     crtHuffmanTree(ht,n);//构建哈夫曼树

    int length = GetCode(A,ht,n);
    printCode(A,length);

    int length2 = GetreCode(A,B,ht,length,n);
    printreCode(B,length2);



     return 0;
}

完事。