哈夫曼.c

数据结构的全部课程实验

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0

typedef struct huff_code_node    //存储编码的链表
{
    char ch;    //编码对应的字符
    char code[100];        //字符对应的哈夫曼码
    struct huff_code_node *next;    
}hnode,*huff;

typedef struct tree_Node    //二叉树结点
{
    char ch;    //字符内容
    int amount;    //字符在字符串中出现的次数
    struct tree_Node *left,*right;    //指向左子树与右子树
}tnode,*bt;

typedef struct list_node        //链表结点
{
    char ch;    //存储字符串中的字符
    int amount;    //字符在字符串中出现的次数
    tnode *son;    //链表结点带有二叉子树的根结点指针
    struct list_node *next;    //指向链表中下一个结点
}Node,*L;

typedef struct stack_node
{
    char ch;    //存储字符
    int amount;        //出现次数
    bt son;        //指向二叉树的某结点
    struct stack_node *next;
}snode,*stack;


char t[200],*str,*c;    //用于存储和处理输入的字符串
bt root=NULL;        //哈夫曼树
L l,p,q,new_node;    //链表结点
huff hlist;        //计算得到的编码表
int char_num;    //输入的不同字符数量
int char_amount;    //输入的所有字符数量
int code_sum;        //哈夫曼编码总长


void initial()        //初始化操作
{
    l=(Node*)malloc(sizeof(Node));        //建立空链表
    l->ch='\0';
    l->amount=0;
    l->son=NULL;
    l->next=NULL;

    str=t;    //将字符串指针指向字符串的第一个位置
    //键盘输入字符串
    printf("输入字符串进行哈夫曼编码:\n");
    scanf("%s",str);
    getchar();    
}

void pull_in_list()
{
    int exist;    //表示当前字符是否存在于链表中，0为不存在，1为已存在
    int n;    //计算输入不同字符的数量，计算后赋值给全局变量char_num
    int m;    //计算输入所有字符的数量，计算后赋值给全局变量char_amount
    
    c=str;    //c指向第一个字符
    
    while(*c!='\0')        //若字符串未读完
    {
        exist=0;
        p=l;    //p指向链表头结点
        //寻找该字符是否已经在链表中
        while(p->next!=NULL)    //若链表非空
        {
            p=p->next;
            if(p->ch==*c)    //若当前字符已经在链表中
            {
                exist=1;
                p->amount++;    //字符出现次数加1
                break;
            }
        }

        if(exist==0)    //若当前字符不存在于链表中，则分配一个结点入表
        {
            new_node=(Node*)malloc(sizeof(Node));
            new_node->ch=*c;
            new_node->amount=1;
            new_node->next=NULL;
            new_node->son=NULL;
            p->next=new_node;
            p=new_node;
        }
        c++;    //读下一个字符
    }

    printf("统计结果:\n");
    p=l;
    n=0;
    m=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
        m+=p->amount;
        printf("%c--%d\n",p->ch,p->amount);
    }
    char_num=n;
    char_amount=m;
    printf("一共有%d种字符输入，字符总数%d\n",char_num,char_amount);
}

int list_element_amount()        //计算链表中结点的数量（不包括头结点）
{
    L temp;        //定义临时指针
    int n=0;        //结点数量
    temp=l;
    while(temp->next!=NULL)    //后面还有结点
    {
        n++;
        temp=temp->next;
    }
    return n;
}

bt create()    //建立最优二叉树
{
    //=========================================
    //这些变量用于寻找最小结点
    L min1_pos,min2_pos,t,min_pri;
    bt min1_son,min2_son;
    int min1,min2;
    char min1_c,min2_c;
    //=========================================

    //=========================================
    //这些变量用于构造二叉子树
    bt left,right,root;
    //==========================================

    //==========================================
    //这些变量用于将二叉子树信息插入链表
    L made,temp_p;
    //============================================

    while(list_element_amount()>=2)    //若表中还有两个或以上结点，则归并继续
    {
        //选择次数值最小的两个结点

        //============================================================================
        //先寻找第一个小结点
        t=l->next;
        min1=t->amount;        //将第一个结点的次数值赋给min1
        min1_pos=t;            //将第一个结点的位置指针赋给min1_pos
        min1_c=t->ch;        //将第一个结点的字符赋值给min1_c
        min1_son=t->son;    //将第一个结点的二叉指针赋值给min1_son
        min_pri=l;            //min_pri始终指向最小结点的前驱，以方便删除最小结点

        while(t->next!=NULL)
        {
            t=t->next;
            if(min1>t->amount)    //发现更小的结点
            {
                min1=t->amount;        //将当前结点的次数值赋给min1
                min1_pos=t;            //将当前结点的位置指针赋给min1_pos
                min1_c=t->ch;        //将当前结点的字符赋值给min1_c
                min1_son=t->son;    //将当前结点的二叉指针赋值给min1_son
            }
        }//退出本循环时，最小结点的信息找出，将该结点删除

        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min1_pos->next;        //删除结点min1_pos
        //寻找第一个小结点完成
        //=================================================================

        //=================================================================
        //先寻找第二个小结点
        t=l->next;
        min2=t->amount;        //将第二个结点的次数值赋给min2
        min2_pos=t;            //将第二个结点的位置指针赋给min2_pos
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始终指向最小结点的前驱，以方便删除最小结点

        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)    //发现更小的结点
            {
                min2=t->amount;        //将当前结点的次数值赋给min2
                min2_pos=t;            //将当前结点的位置指针赋给min2_pos
                min2_c=t->ch;
                min2_son=t->son;
            }
        }//退出本循环时，最小结点的信息找出，将该结点删除

        min_pri=l;
        while(min_pri->next!=min2_pos)
            min_pri=min_pri->next;
        //退出循环时min_pri指向min1_pos的前驱
        min_pri->next=min2_pos->next;        //删除结点min2_pos
        //寻找第二个小结点完成
        //=================================================================


        //==================================================================
        //两个最小结点找到，由这对结点级成一个二叉子树，将根结点插入链表中
        if(min1_son==NULL)    //该结点无二叉子树指针，则须新分配一个二叉树结点
        {
            left=(bt)malloc(sizeof(tnode));        //产生左孩子
            left->amount=min1;        //次数值复制
            left->ch=min1_c;        //字符复制
            left->left=NULL;
            left->right=NULL;
        }
        else    //该结点为计算产生的结点，它已指向一个二叉子树
            left=min1_son;    //left直接指向已经生成的二叉子树的根结点

        if(min2_son==NULL)    //该结点无二叉子树指针，则须新分配一个二叉树结点
        {
            right=(bt)malloc(sizeof(tnode));        //产生右孩子
            right->amount=min2;        //次数值复制
            right->ch=min2_c;        //字符复制
            right->left=NULL;
            right->right=NULL;
        }
        else
            right=min2_son;    //left直接指向已经生成的二叉子树的根结点

        root=(bt)malloc(sizeof(tnode));
        root->amount=min1+min2;
        root->ch='\0';        //对于计算产生的树结点，字符均为空
        root->left=left;
        root->right=right;
        //二叉子树完成

        //生成一个对应上面已产生二叉子树地址的链表结点
        made=(L)malloc(sizeof(Node));
        made->amount=root->amount;
        made->ch=root->ch;
        made->next=NULL;
        made->son=root;

        //将生成的链表结点插入链表中
        temp_p=l;
        while(temp_p->next!=NULL)
            temp_p=temp_p->next;
        //退出循环时temp_p指向链表最后一个结点
        temp_p->next=made;        //将生成的结点插入链表
    }

    temp_p=l->next;
    return temp_p->son;
}

void encoding()        //根据建立的哈夫曼树编码
{
    stack code,top,temp,readcode;
    bt r;
    huff temp_huff,hp;