C语言：数据结构、哈夫曼编码、Huffman-源代码

1. 目标

读取一段字符，生成哈夫曼编码，并输出。如下所示：

2. 代码结构

2.1 统计各个字符出现的次数，并排序；

2.2 根据生成的哈夫曼树，生成哈夫曼编码；

3. 源代码

#include 
#include 
#include 
#define title
#define queuesize_max 256 //队列的最大长度
#define code_max 256 //编码的最大长度

/**************************************/
/*定义huffman tree节点                */
/*其中symbol记录节点存储的字符        */
/*left, right指向左右子节点           */
/**************************************/
typedef struct hfmtreenode{
    int symbol;
    struct hfmtreenode *left;
    struct hfmtreenode *right;
} hfmtreenode, *phtreenode;

/**************************************/
/*定义一个指向huffman tree的根节点    */
/**************************************/
typedef struct hhfmtreenode{
    hfmtreenode* rootnode;
} hhfmtreenode;

/**************************************/
/*定义队列的节点                      */
/*ptr是一个指向phtreenode的指针，     */
/*主要是方便后续建立huffman treee     */
/*count记录字符出现的频次，           */
/*next指向下一个节点                  */
/**************************************/
typedef struct queuenode{
    phtreenode ptr;
    int count;
    struct queuenode *next;
} queuenode, *ptrqueue;

/**************************************/
/*定义指向queuenode的头节点           */
/*其中size记录节点的数量              */
/*first指向queuenode的第一个节点      */
/**************************************/
typedef struct hqueuenode{
    int size;
    ptrqueue first;
} hqueuenode;

/**************************************/
/*定义指向记录编码的table节点         */
/*symble为字符，code指向对应的编码    */
/*next用来指向下一个节点              */
/**************************************/
typedef struct tablenode{
    char symbol;
    char* code;
    struct tablenode *next;
} tablenode;

/**************************************/
/*定义指向tablenode的头节点           */
/*first标记第一个节点                 */
/*last指向最后一个节点                */
/**************************************/
typedef struct hdtablenode{
    tablenode *first;
    tablenode *last;
} hdtablenode;

/**************************************/
/*对队列进行初始，添加一个头节点      */
/*其中size记录节点的数量              */
/*first指向queue节点                  */
/**************************************/
void initqueue(hqueuenode** hqueue)
{
    *hqueue=(hqueuenode*)malloc(sizeof(hqueuenode));
    (*hqueue)->size=0;
    (*hqueue)->first=null;
}

void addqueuenode(hqueuenode **hqueue,hfmtreenode *hnode,int count)//新建一个队列节点并按统计的结果从小到大的顺序加入队列
{
    queuenode *qnode=null;

    if((*hqueue)->size==queuesize_max)//队列规模检查，正常情况下不会出现
    {
        printf("\nerr: the queue is full!!!");
    }
    else    //如果正常，则按照从小到大的顺序，寻找正确的位置插入节点
    {
        if(0==(*hqueue)->size)//如果是添加的第一个节点，直接添加即可
        {
            qnode=(queuenode*)malloc(sizeof(queuenode));
            (*hqueue)->first=qnode;
            qnode->count=count;
            qnode->ptr=hnode;
            qnode->next=null;
            (*hqueue)->size++;
        }
        else if(count<(*hqueue)->first->count)//如果要添加的字符的统计数量小于现有最小的，则直接放在第一个节点处
        {
            qnode=(queuenode*)malloc(sizeof(queuenode));
            qnode->next=(*hqueue)->first;
            (*hqueue)->first=qnode;
            qnode->count=count;
            qnode->ptr=hnode;
            (*hqueue)->size++;
        }
        else    //对于第三类情况，则需要遍历队列，直到寻找到合适的位置
        {
            queuenode* p=(*hqueue)->first;
            qnode=(queuenode*)malloc(sizeof(queuenode));
            qnode->count=count;
            qnode->ptr=hnode;
            (*hqueue)->size++;

            while(p->next!=null && count>=p->next->count)
                p=p->next;
            qnode->next=p->next;
            p->next=qnode;
        }
    }
}

hfmtreenode* gethfmtreenode(hqueuenode* hqueue)
{
    hfmtreenode* getnode;
    if(hqueue->size>0)
    {
        getnode=hqueue->first->ptr;
        hqueue->first=hqueue->first->next;
        hqueue->size--;
    }
    else
    {
        printf("\nerr: can't get a node\n");
    }
    return getnode;
}


hhfmtreenode* crthfmtree(hqueuenode** hqueue)
{
    int count=0;
    hfmtreenode *left, *right;

    while((*hqueue)->size>1)
    {
        count=(*hqueue)->first->count+(*hqueue)->first->next->count;
        left=gethfmtreenode(*hqueue);
        right=gethfmtreenode(*hqueue);

        hfmtreenode *newnode=(hfmtreenode*)malloc(sizeof(hfmtreenode));

        newnode->left=left;
        newnode->right=right;

        addqueuenode(hqueue,newnode,count);
    }

    hhfmtreenode* tree=(hhfmtreenode*)malloc(sizeof(hhfmtreenode));
    tree->rootnode=gethfmtreenode(*hqueue);
    return tree;
}

hhfmtreenode* creattree(void)
{
    file *ifile;
    int *countarray;
    char c;
    int i;

    countarray=(int*)malloc(sizeof(int)*256);//分配空间用于存储各字符出现的次数,并初始化为零
    for(i=0;i<256;i++)
    {
        countarray[i]=0;
    }

    ifile=fopen("d://1.txt","r");
    if(!ifile)  //检查文件是否打开成功
        printf("can't open the file\n");
    else
        {
            while((c=getc(ifile))!=eof)
            {
                countarray[(unsigned int)c]++;
                printf("%c", c);
            }
            fclose(ifile);
        }
    hqueuenode *hqueue;
    initqueue(&hqueue);
    for(i=0;i<256;i++)
    {
        if(countarray[i])
        {
            //printf("%c %d\n",i, countarray[i] );
            hfmtreenode *hnode=(hfmtreenode*)malloc(sizeof(hfmtreenode));//创建一个树节点，并初始化（用来对应队列queuenode中的ptr）

            hnode->symbol=(char)i;
            hnode->left=null;
            hnode->right=null;

            addqueuenode(&hqueue,hnode,countarray[i]);//将该节点插入队列中的适当位置（按统计的结果，从小到大排列）
        }
    }
    free(countarray);//释放不用的内存

    queuenode* q=hqueue->first;
    printf("\n");
    do
    {
        printf("\n%c %d",q->ptr->symbol, q->count);
        q=q->next;
    }    while(q!=null);
    //printf("%d",hqueue->size);

    hhfmtreenode *tree=crthfmtree(&hqueue);
    return tree;
}

void traversetree( hdtablenode** table, hfmtreenode* tree, char* code, int k)
{
    if(tree->left==null && tree->right==null)   //递归结束检查，即找到叶子节点
    {
        code[k]='\0';   //添加字符串结束标记
        tablenode *tnode=(tablenode*)malloc(sizeof(tablenode)); //创建一个节点，并将其添加到table链表中
        tnode->code=(char*)malloc(sizeof(char)*256+1);
        strcpy(tnode->code,code);
        tnode->symbol=tree->symbol;
        tnode->next=null;

        if((*table)->first==null)   //如果是第一个节点，直接添加即可， 否则添加到尾部即可
        {
            (*table)->first=tnode;
            (*table)->last=tnode;
        }
        else
        {
            (*table)->last->next=tnode;
            (*table)->last=tnode;
        }
    }

    if(tree->left!=null)    //向左边递归，并记录编码为0
    {
        code[k]='0';
        traversetree(table,tree->left, code, k+1);
    }

    if(tree->right!=null)   //向右边递归，并记录编码为1
    {
        code[k]='1';
        traversetree(table, tree->right, code, k+1);
    }
}

hdtablenode* crttable(hhfmtreenode* hfmtree)
{
    hdtablenode* hdtable=(hdtablenode*)malloc(sizeof(hdtablenode));
    hdtable->first=null;
    hdtable->last=null;

    char code[code_max];
    int k=0; //记录树的层级

    traversetree(&hdtable, hfmtree->rootnode, code, k);
    return hdtable;
}



int main(void)
{
    hhfmtreenode* tree;
    hdtablenode* table;

    printf("%s\n\n\n",title);
    tree=creattree();
    table=crttable(tree);
    int i=0, j=0;
    tablenode* t=table->first;
    char* s=t->code;
    printf("\n\n*************************************************************************************\n");
    printf("the huffman code is:\n");
    while(t!=null)
    {

        for(i=0;i<257;i++)
        {
            if((*s)!='\0')
            {
                printf("%c",*s);
                s++;
            }
        }
            printf("%8c\n",t->symbol);
            t=t->next;
            if(t)
                s=t->code;

    }
}