数据结构树哈夫曼树及编码 C语言版

谁践踏了优雅 2022-06-09 04:24 19阅读 0赞

//哈弗曼编码的算法
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 50//叶子结点的最大值
    #define M 2*N-1  //所有结点的最大值
    typedef struct
    {
        int weight;
        int parent;
        int LChild;
        int RChild;
    } HTNode,HuffmanTree[M+1];
    
    void select(HuffmanTree ht,int n,int *s1,int *s2)  //找权值最小的两个结点
    {
        int i;
        int minn=999999;
        int lable1=0,lable2=0;
        for(i=1;i<=n;i++)
        {
            if(ht[i].parent==0 && ht[i].weight<minn)
            {
                minn=ht[i].weight;
                lable1=i;
            }
        }
        *s1=lable1;
        minn=999999;
        for( i=1;i<=n;i++)
        {
            if(ht[i].parent==0 && ht[i].weight<minn && lable1 != i)
            {
                minn=ht[i].weight;
                lable2=i;
            }
        }
        *s2=lable2;
    }
    
    void CrtHuffmanTree(HuffmanTree ht,int w[],int n) //创建哈夫曼树  w[]里面存放n个结点的权值
    {
        int i;
        for(i=1;i<=n;i++)
        {
            ht[i].weight=w[i];
            ht[i].LChild=0;
            ht[i].RChild=0;
            ht[i].parent=0;
        }
        int m=2*n-1;
        for(i=n+1;i<=m;i++)
        {
            ht[i].weight=0;
            ht[i].LChild=0;
            ht[i].RChild=0;
            ht[i].parent=0;
    
        }
        int s1,s2;
        for(i=n+1;i<=m;i++)
        {
            select(ht,i-1,&s1,&s2);
            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;
        }
    }
    
    void CrtHuffmanCode(HuffmanTree ht,int n )
    {
        char cd[n+1][n+1] ;
        int i;int start;
    
        for(i=1;i<=n;i++)
        {
            cd[i][n-1]='\0';   //从右向左存放编码
            start=n-1;
            int c=i; int p=ht[i].parent;
            while(p!=0)
            {
                --start;
                if(ht[p].LChild==c) cd[i][start]='0';
                    else cd[i][start]='1';
                c=p;
                p=ht[p].parent;
            }
            int j;
            for(j=start;cd[i][j]!='\0';j++)
                printf("%c",cd[i][j]);
            printf("\n");
        }
        return ;
    }
    
    int main()
    {
        int n,i,leaf;
        int w[1000];
        HuffmanTree ht;
        printf("请输入叶子结点的个数n 以及其权值\n");
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&leaf);
            w[i]=leaf;
        }
         CrtHuffmanTree(ht,w,n);
         printf("构造的哈夫曼树的结构为：\n");
        for(i=1;i<=2*n-1;i++)
        {
            printf("%d %d %d %d\n",ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
    
        }
        printf("哈夫曼树的编码为：\n");
        CrtHuffmanCode(ht,n);
    
        return 0;
    }