指针实现的霍夫曼树(Huffman Tree)及输出编码

十月 15, 2017 Potatso％1 $ S

老师在课上偶然提到到CSI第三章的霍夫曼编码，于是自己琢磨了一番：还有很多可以优化的地方，比如说可以用堆来优化队列，之后我在慢慢填坑吧～

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    typedef struct trnode
    {
        int key;
        struct trnode *lchild;
        struct trnode *rchild;
    } Trnode;

    typedef struct tree
    {
        int size;
        Trnode *root;
    } Tree;

    void buildtree(Tree* tree,int *C); 
    Trnode* makeNode(int data);
    Trnode* min_element(Trnode* array[]);
    void insert(Trnode* x,Trnode*  array[]);
    bool isEmpty(Trnode* array[]);

    void quicksort(int *base,int x,int y) //x y数组下标
    {
        int i=x,j=y;
        if(x>y)
            return;
        int temp=base[x]; //temp储存基准数

        while(i<j)
        {
                while(base[j]>=temp&&i<j)
                    j--;
                while(base[i]<=temp&&i<j)
                    i++;
            if(i<j)
            {
                int exc=base[i];
                base[i]=base[j];
                base[j]=exc;
            }
        }
        base[x]=base[i];
        base[i]=temp;
        quicksort(base,x,i-1);
        quicksort(base,i+1,y);
    }

    void Print(Trnode* root,int *base,int i)
    {
        if(root->lchild==NULL&&root->rchild==NULL)
        {
            for(int i=0;i<5&&base[i]!=-1;i++)
                printf("%d",base[i]);
            printf("    ");
        }
        else
        {
            base[i]=0;
            Print(root->lchild,base,i+1);
            base[i]=1;
            Print(root->rchild,base,i+1);
            base[i]=-1;
        }
   }

int main(void)
{
    int A[5]={10,6,3,5,567};
    int C[5];
    for(int i=0;i<5;i++)
        C[i]=A[i];
    quicksort(C,0,4);
    Tree *tree=(Tree*)malloc(sizeof(Tree));
    tree->root=NULL;
    buildtree(tree,C);
    int base[5]={-1,-1,-1,-1,-1};
    int floor=0;
    Print(tree->root,base,floor);
    return 0;
}

void buildtree(Tree *tree,int *C)
{
    Trnode* array[5];
    for(int i=0;i<5;i++)
    {
        array[i]=makeNode(C[i]);
    }
    while(!isEmpty(array))
    {   
        Trnode *x=min_element(array);
        if(isEmpty(array))
        {
            tree->root=x;
            break;
        }
        Trnode *y=min_element(array);
        Trnode *z=(Trnode*)malloc(sizeof(Trnode));
        z->key=x->key+y->key;
        z->lchild=y;
        z->rchild=x;
        if(isEmpty(array))
        {
            tree->root=z;
            break;
        }
        insert(z,array);
    }
}

Trnode* makeNode(int data)
{
    Trnode* x=(Trnode*)malloc(sizeof(Trnode));
    x->key=data;
    x->lchild=NULL;
    x->rchild=NULL;
    return x;
}
Trnode* min_element(Trnode* array[])
{
    Trnode *p=array[0];
    int i;
    for(i=1;i<5;i++)
    {
        if(array[i]->key!=0)
            array[i-1]=array[i];
        else
            break;
    }
    array[i-1]=makeNode(0);
    return p;

}


void insert(Trnode* x,Trnode* array[])
{
    int i=4;
    while(i>=0)
    {
        if(array[i-1]->key!=0)
            array[i]=array[i-1];
        if(array[i]->key!=0&&array[i]->key<x->key)
            break;
        i--;
    }
    array[i]=x; 
}

bool isEmpty(Trnode* p[])
{
    for(int i=0;i<5;i++)
    {
        if(p[i]->key!=0)
        {
            return false;
        }
    }
    return true;
}

2017年10月16日更：
我来填坑啦～
这是用堆优化过的版本

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct trnode
{
    int key;
    struct trnode *lchild;
    struct trnode *rchild;
} Trnode;

typedef struct tree
{
    Trnode *root;
} Tree;

typedef struct queue
{
    Trnode *array[5];
    int size;
} Queue;

void buildtree(Tree* tree,int *C); 
Trnode* makeNode(int data);
Trnode* min_element(Queue *H);
void insert(Trnode* x,Queue *H);
bool isEmpty(Trnode* array[]);
void swap(Trnode *a,Trnode *b)
{
    Trnode temp=*a;
    *a=*b;
    *b=temp;
}

void quicksort(int *base,int x,int y) //x y数组下标
{
    int i=x,j=y;
    if(x>y)
        return;
    int temp=base[x]; //temp储存基准数

    while(i<j)
    {
            while(base[j]>=temp&&i<j)
                j--;
            while(base[i]<=temp&&i<j)
                i++;
        if(i<j)
        {
            int exc=base[i];
            base[i]=base[j];
            base[j]=exc;
        }
    }
    base[x]=base[i];
    base[i]=temp;
    quicksort(base,x,i-1);
    quicksort(base,i+1,y);
}

void Print(Trnode* root,int *base,int i)
{
    if(root->lchild==NULL&&root->rchild==NULL)
    {
        for(int i=0;i<5&&base[i]!=-1;i++)
            printf("%d",base[i]);
        printf("    ");
    }
    else
    {
        base[i]=0;
        Print(root->lchild,base,i+1);
        base[i]=1;
        Print(root->rchild,base,i+1);
        base[i]=-1;
    }
}

int main(void)
{
    int A[5]={10,6,3,5,567};
    int C[5];
    for(int i=0;i<5;i++)
        C[i]=A[i];
    quicksort(C,0,4);
    Tree *tree=(Tree*)malloc(sizeof(Tree));
    tree->root=NULL;
    buildtree(tree,C);
    int base[5]={-1,-1,-1,-1,-1};
    int floor=0;
    Print(tree->root,base,floor);
    return 0;
}

void buildtree(Tree *tree,int *C)
{
    /*if(!isEmpty(C))
    {   
        Trnode *x=makeNode(min_element(C));
        if(tree->root==NULL)
            tree->root=x;
        Trnode *y=makeNode(min_element(C));
        Trnode *z=(Trnode*)malloc(sizeof(Trnode));
        tree->root=z;
        z->key=x->key+y->key;
        z->lchild=y;
        z->rchild=x;
        insert(z->key,C);
    }*/


    Queue *H=(Queue*)malloc(sizeof(Queue));
    H->size=0;
    for(int i=0;i<5;i++)
    {
        H->array[i]=makeNode(C[i]);
        H->size++;
    }
    while(!isEmpty(H->array))
    {   
        Trnode *x=min_element(H);
        Trnode *y=min_element(H);
        Trnode *z=(Trnode*)malloc(sizeof(Trnode));
        z->key=x->key+y->key;
        z->lchild=x;
        z->rchild=y;
        if(isEmpty(H->array))
        {
            tree->root=z;
            break;
        }
        insert(z,H);
    }

}

Trnode* makeNode(int data)
{
    Trnode* x=(Trnode*)malloc(sizeof(Trnode));
    x->key=data;
    x->lchild=NULL;
    x->rchild=NULL;
    return x;
}

Trnode* min_element(Queue *H)
{
    int dad=0;
    int son=2*dad+1;
    Trnode* p=H->array[0];
    H->array[0]=makeNode(0);
    while(son<=H->size-1)
    {
        if(son+1<=H->size-1&&H->array[son+1]->key<H->array[son]->key)
            son++;
        swap(H->array[dad],H->array[son]);
        dad=son;
        son=2*dad+1;
    }
    H->array[dad]=H->array[H->size-1];
    H->array[H->size-1]=makeNode(0);
    H->size--;
    return p;

}


void insert(Trnode* x,Queue *H)
{
    H->array[H->size]=x;
    H->size++;
    int son=H->size-1;
    int dad=(son-1)/2;
    while(dad>=0&&son!=0)
    {
        if(H->array[dad]->key<H->array[son]->key)
            break;
        swap(H->array[dad],H->array[son]);
        son=dad;
        dad=(son-1)/2;
    }
}

bool isEmpty(Trnode* p[])
{
    if(p[0]->key==0)
        return true;
    else
        return false;
}

相关

发表评论取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

%d 博主赞过：