欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-04 11:54:20
1. 目标 读取一段字符,生成哈夫曼编码,并输出。如下所示: 2. 代码结构 2.1 统计各个字符出现的次数,并排序; 2.2 根据生成的哈夫曼树,生成哈夫曼编码; 3. 源代码 #in...

1. 目标

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

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

2. 代码结构

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

2.1 统计各个字符出现的次数,并排序;

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

2.2 根据生成的哈夫曼树,生成哈夫曼编码;

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

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;

    }
}