回 帖 发 新 帖 刷新版面

主题:救命呀!!请问谁会编写哈夫曼编解码

谁会哈夫曼编码解码,请赐教,多谢,多谢。

回复列表 (共8个回复)

沙发

我可以编写。你做什么用?

板凳

#include<stdio.h>
#include<stdlib.h>
#define MAXLEN 100
/*///////////////////////////////////////////////////////////////////////////////*/
typedef struct Huffmantree {
    char ch;
    int weight,mark;
    struct Huffmantree *parent,*lchild,*rchild,*next;
}Hftree,*linktree;
/*///////////////////////////////////////////////////////////////////////////////*/
/*整理输入的字符串,合并相同的项,并求出每个字符在数组中出现的次数 */
linktree tidycharacter(char character[])
{
    int i=0;
    linktree tree,ptr,beforeptr,node;
    
    tree=(linktree)malloc(sizeof(Hftree));/*创建单链表的头结点*/
    if(!tree)return NULL;
    tree->next=NULL;
    
    for(i=0;character[i]!='\0'&&character[i]!='\n';i++) {    
        ptr=tree;
        beforeptr=tree;
        
        node=(linktree)malloc(sizeof(Hftree));
        if(!node)return NULL;
        node->next=NULL;
        node->parent=NULL;
        node->lchild=NULL;
        node->rchild=NULL;
        node->mark=0;
        node->ch=character[i];
        node->weight=1;
        
        if(tree->next==NULL)
            tree->next=node;
        else {    
            ptr=tree->next;
            while(ptr&&ptr->ch!=node->ch) {/*将指针移至链表尾*/    
                ptr=ptr->next;
                beforeptr=beforeptr->next;
            }
            if(ptr&&ptr->ch==node->ch) {/*如果链表中某结点的字符与新结点的字符相同*/
                                      /*将该结点的权加一*/    
                ptr->weight=ptr->weight+1;
                free(node);
            }
            else {/*将新结点插入链表后*/    
                node->next=beforeptr->next;
                beforeptr->next=node;
            }
        }
    }
    return tree;
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*将整理完的字符串按出现次数从小到大的顺序排列   */
linktree taxisnode(linktree tree)
{    
    linktree head,ph,pt,beforeph;
    
    head=(linktree)malloc(sizeof(Hftree));/*创建新链表的头结点*/
    if(!head)return NULL;
    head->next=NULL;
    
    ph=head;
    beforeph=head;
    
    while(tree->next) {    
        pt=tree->next;/*取被操作链表的首元结点*/
        tree->next=pt->next;
        pt->next=NULL;
        
        ph=head->next;
        beforeph=head;
        
        if(head->next==NULL)
            head->next=pt;/*创建当前操作链表首元结点*/
        else {
            while(ph&&ph->weight<pt->weight) {/*将被操作结点插入相应位置*/    
                ph=ph->next;
                beforeph=beforeph->next;
            }
            pt->next=beforeph->next;
            beforeph->next=pt;
        }
    }
    free(tree);
    return head;
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*用排完序的字符串建立霍夫曼树  */
linktree createHftree(linktree tree)
{   
    linktree p,q,newnode,beforep;
    
    for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next) {
        tree->next=q->next;
        q->next=NULL;
        p->next=NULL;
        
        newnode=(linktree)malloc(sizeof(Hftree));/*申请新结点作为霍夫曼树的中间结点*/
        if(!newnode)return NULL;
        newnode->next=NULL;
        newnode->mark=0;
        
        newnode->lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/
        newnode->rchild=q;
        p->parent=newnode;
        q->parent=newnode;
        newnode->weight=p->weight+q->weight;
        
        p=tree->next;
        beforep=tree;
        
        if(p!=NULL&&p->weight>=newnode->weight) {/*将新结点插入原链表的相应位置*/
            newnode->next=beforep->next;
            beforep->next=newnode;
        }
        else {
            while(p!=NULL&&p->weight<newnode->weight) {    
                p=p->next;
                beforep=beforep->next;
            }
            newnode->next=beforep->next;
            beforep->next=newnode;
        }
    }
    return (tree->next);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*对霍夫曼树进行编码     */
void Huffmancoding(linktree tree)
{   
    int index=0;
    char *code;
    linktree ptr=tree;
    code=(char *)malloc(10*sizeof(char));/*此数组用于统计霍夫曼编码*/

    printf("字符以及它的相应权数---------霍夫曼编码\n\n");
    if(ptr==NULL) {
        printf("霍夫曼树是空的!\n");
        exit(0);
    }
    else {
        while(ptr->lchild&&ptr->rchild&&ptr->mark==0) {
            while(ptr->lchild&&ptr->lchild->mark==0) {
                code[index++]='0';
                ptr=ptr->lchild;
                if(!ptr->lchild&&!ptr->rchild) {
                    ptr->mark=1;
                    code[index]='\0';
                    printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight);
                    for(index=0;code[index]!='\0';index++)
                        printf("%c",code[index]);
                    printf("\n");
                    ptr=tree;
                    index=0;
                }
            }
            if(ptr->rchild&&ptr->rchild->mark==0) {
                ptr=ptr->rchild;
                code[index++]='1';
            }
            if(!ptr->lchild&&!ptr->rchild) {
                ptr->mark=1;
                code[index++]='\0';
                printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight);
                for(index=0;code[index]!='\0';index++)
                    printf("%c",code[index]);
                printf("\n");
                ptr=tree;
                index=0;
            }
            if(ptr->lchild->mark==1&&ptr->rchild->mark==1)
            {
                ptr->mark=1;
                ptr=tree;
                index=0;
            }
        }
    }
    printf("\n");
    free(code);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*解码 */
void decode(linktree tree,char code[])
{    
    int i=0,j=0;
    char *char0_1;
    linktree ptr=tree;
    char0_1=(char *)malloc(10*sizeof(char));/*此数组用于统计输入的0、1序列*/
    
    printf("霍夫曼编码-----相应字符\n\n");
    for(j=0,ptr=tree;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j=0,ptr=tree) {
        for(j=0;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j++,i++) {
            if(code[i]=='0') {    
                ptr=ptr->lchild;
                char0_1[j]='0';  
            }
            if(code[i]=='1') {
                ptr=ptr->rchild;
                char0_1[j]='1';
            }
        }                        
        if(!ptr->lchild&&!ptr->rchild) {
            char0_1[j]='\0';
            for(j=0;char0_1[j]!='\0';j++)
                printf("%c",char0_1[j]);  
            printf("\t\t%c\n",ptr->ch);
        }
        if(code[i]=='\0'&&ptr->lchild&&ptr->rchild) {    
            char0_1[j]='\0';
            printf("没有与最后的几个0、1序列:%s相匹配的字符!\n",char0_1);
            return;
        }
    }
    free(char0_1);
}
/*///////////////////////////////////////////////////////////////////////////////*/
/*释放霍夫曼树所占用的空间*/
void deletenode(linktree tree)
{    
    linktree ptr=tree;
    if(ptr) {    
        deletenode(ptr->lchild);
        deletenode(ptr->rchild);
        free(ptr);
    }
}
/*///////////////////////////////////////////////////////////////////////////////*/
void main()
{
    char character[MAXLEN],code[MAXLEN];
    linktree temp,ht,htree,ptr=NULL;

    printf("一、编码:\n请输入要测试的字符串:\n\n");
    scanf("%s",character);
    printf("\n");

    temp=tidycharacter(character);

    ht=taxisnode(temp);

    htree=createHftree(ht);    
    
    Huffmancoding(htree);    
    
    printf("二、解码:\n请输入用于解码的0、1序列:\n\n");
    scanf("%s",code);
    printf("\n");

    decode(htree,code);    
    
    deletenode(htree);
}

霍夫曼编解码全在里面了:)

3 楼

给你看一个简单的版本,用数组实现的。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define N 10        //要编码的字符个数

typedef char KeyType;    // 被编码字符的类型,假定为字符
typedef enum{ NONE, LEFT_CHILD, RIGHT_CHILD } WHICH ; //定义节点是双亲的左孩子还是右孩子。
// NONE表示未知

typedef struct node
{
    KeyType key;
    int weight;            //权重或者出现的概率
    int parent;            //我们用数组存储树,这里用下标标是双亲。-1表示没有双亲。
    WHICH sign;            //说明该节点使是左孩子还是右孩子
    char *code;            //对编码采用01串存储,以便输出;也可以在设定一个int,来存储编码
                        //这样解码要快,解码程序比较简单,这里就不写了。
} HuffmanNode;

//定义一个HUFFMAN树类型,数组表示,长度是N+N-1 = 2N-1
typedef HuffmanNode HuffmanTree[N+N-1];

//为了测试方便,这里用随机数的方法初始化一个HUFFMAN树。
void init( HuffmanTree T)
{
    int i;
    char j='A';
    //初始化存储关键字的部分。
    for(i=0; i<N; i++)
    {
        T[i].key = j++;
        T[i].parent = -1 ; //-1表示没有双亲。
        T[i].sign=NONE;
        T[i].weight = (rand() % 100);    //暂不考虑总的概率和为1,用权值代之
    }

    for(;i<N+N-1; i++)
    {
        T[i].parent = -1;
        T[i].sign=NONE;
        T[i].weight=0;
    }
}

//从HT[0]..HT[N+i-1]中找出最小,次小
void SelectMin(HuffmanTree T, int start, int end, int *pmin1, int *pmin2)
{
    int i;
    int min1=INT_MAX;//最小
    int min2;    //次小。
    
    //找出最小
    for(i=start; i<=end; i++)
    {
        if( T[i].sign == NONE && T[i].weight < min1)
        {
            *pmin1 = i;
            min1 = T[i].weight;
        }
    }

    //找次小
    min2=INT_MAX;
    for(i=start; i<=end; i++)
    {
        if( (*pmin1 != i) &&  (T[i].sign == NONE) && (T[i].weight < min2) )
        {
            *pmin2 = i;
            min2 = T[i].weight;
        }
    }
}

// 进行HUFFMAN树构造
void CreateHuffmanTree(HuffmanTree T)
{
    
    int i;
    int min1, min2;    //记录权值最小,次小的两个节点下标


    for(i=N; i<2*N-1; i++)
    {
        SelectMin(T, 0, i-1, &min1, &min2);    //从HT[0]..HT[i-1]中找出最小,次小
        
        T[i].weight = T[min1].weight + T[min2].weight;
        T[min1].parent = i;
        T[min1].sign = LEFT_CHILD;
        T[min2].parent = i;
        T[min2].sign = RIGHT_CHILD;
    }
}

//生成将每个节点的编码,按01字符串的方式生成。
void EncodeHuffman( HuffmanTree T)
{
    char temp[N];        //临时串,树高会大于N。
    int s;
    
    int i, p;
    temp[N-1]='\0';

    //左孩子0,右孩子1
    for(i=0; i<N; i++)
    {
        p = i;
        s = N-1;
        while(T[p].parent != -1)
        {
            if( T[p].sign == LEFT_CHILD )
                temp[--s] = '0';
            else if(T[p].sign == RIGHT_CHILD)
                temp[--s] = '1';
            
            p = T[p].parent;
        }
        T[i].code = (char*)malloc((N-s)*sizeof(char));
        strcpy(T[i].code, temp+s);    //把编码复制道接点域中。
    }
}

//输出每个节点的编码情况。
void ShowCode( HuffmanTree T)
{
    int i;
    printf(" Key    Code    weight\n---------------\n");
    for(i=0; i<N; i++)
        printf("%3c%8s%8d\n",T[i].key,T[i].code,T[i].weight);

}


int main()
{
    HuffmanTree T;
    init(T);    //初始化
    CreateHuffmanTree(T);
    EncodeHuffman(T);
    ShowCode(T);
    return 0;
}

4 楼

多谢各位帮忙,多谢,多谢!

5 楼

请问如何将txt文件内的数据输入再编写哈夫曼编码啊?
例如txt文件是这样的
7
1
0.2 0.19 0.18 0.17 0.15 0.10 0.01
7是信源符号数,1是编码序列长度
求求各位大侠帮帮忙

6 楼

请问怎样输入txt文件入面的数据再编哈夫曼编码啊?
例如一个txt文件
7
1
0.20 0.19 0.18 0.17 0.15 0.10 0.01
7是信源符号数,1是编码序列长度
求求各位大侠帮帮忙啦

7 楼

谢谢!!

8 楼

现在都忘了……

我来回复

您尚未登录,请登录后再回复。点此登录或注册