hfmdaima.txt

自适应哈夫曼编码

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define MAXTEXT 100
#define MAXNODE 100
#define MAXCODE 100

typedef struct Node/*树结点*/
{
    struct Node *parent;
    struct Node *lcld;
    struct Node *rcld;
    char c;/*字符*/
    int freq;/*频率*/
    char code[MAXCODE];/*字符的哈夫曼编码*/
}Node;

void GradationVisit();
char text[MAXTEXT];/*记录输入字符串*/
Node *root;
Node* allNode[MAXNODE];/*存储所有结点的地址,大大节约遍历的开销*/
int NodeNum;/*当前树的结点数*/
Node *NEW;

/*输入字符*/
void Input ()
{
    int i = 0;
    char c = 0;
    printf ("Please input the text (end with '$') !\n");
    
    scanf ("%c",&c);
    while (i<MAXTEXT-2 && c!='$')
    {
        text[i] = c; 
        i++;
        scanf ("%c",&c);
    }
    text[i] = '$';
    text[i+1] = '\0';
}

/*找具有频率n的在树root中的最远结点*/
Node* FindFarestNode (int freq)
{
 int i = 0;
    GradationVisit(); 
    while (i < NodeNum)
    {
        /*由于采取了特殊的层次遍历策略，第一次找到的肯定就是最远的*/
        if (allNode[i]->freq == freq)
            return allNode[i];
        i++;
    }
    return NULL;
}

/*查找存储字符c的结点，如果不存在，返回NULL*/
Node* FindNode (char c)
{ 
 int i = 0;
    GradationVisit();
    while (i < NodeNum)
    {
        if (allNode[i]->c==c && allNode[i]!=NEW)
            return allNode[i];
        i++;
    }
    return NULL;
}

/*对树进行层次遍历，保存在allNode里*/
void GradationVisit ()
{
    /*为了方便查找具有频率n的在树root中的最远结点
    采用自顶而下，自右而左的遍历顺序*/
    
    /*至少有一个元素root*/
    int curr = 0;
    int len = 0;
    NodeNum = 1;
    allNode[0] = root;
    allNode[0]->code[0] = '\0';
    
    while (curr < NodeNum)
    {
        if (allNode[curr]->rcld != NULL)
        {
            strcpy(allNode[curr]->rcld->code,allNode[curr]->code);
            len = strlen(allNode[curr]->rcld->code);
            allNode[curr]->rcld->code[len] = '1';
            allNode[curr]->rcld->code[len+1] = '\0';
            allNode[NodeNum] = allNode[curr]->rcld;
            NodeNum++;
        }    
        if (allNode[curr]->lcld != NULL)
        {
            strcpy(allNode[curr]->lcld->code,allNode[curr]->code);
            len = strlen(allNode[curr]->lcld->code);
            allNode[curr]->lcld->code[len] = '0';
            allNode[curr]->lcld->code[len+1] = '\0';
            allNode[NodeNum] = allNode[curr]->lcld;
            NodeNum++;
        }    
        curr++;
    }
}

/*打印结点编码*/
void PrintTree ()
{
 int i = 0;
    GradationVisit();/*相当于对结点进行按层次的排序*/
    printf("\n");
    /*按层次打印结点编码*/
    while (i < NodeNum)
    {
        if (allNode[i]->lcld==NULL && allNode[i]->rcld==NULL && allNode[i]->c!=0)/*叶子结点*/
            printf("c = %c, freq = %d, code = %s\n",allNode[i]->c,allNode[i]->freq,allNode[i]->code);
        i++;
    }
}

/*交换子树*/
void Swap(Node *n1, Node *n2)
{
    /*may be there is error hear*/
    Node *n1Parent = n1->parent;
    Node *n2Parent = n2->parent;
    
    if (n1Parent->lcld == n1)
        n1Parent->lcld = n2;
    else
        n1Parent->rcld = n2;
        
    if (n2Parent->lcld == n2)
        n2Parent->lcld = n1;
    else
        n2Parent->rcld = n1;
        
    n1->parent = n2Parent;
    n2->parent = n1Parent;
}

/*输入一个字符，调整树*/
void AdjustTree (char c)
{
 int freq;
    Node *tempNode1;
    Node *tempNode2;
    Node *newNode; 

    Node *n = FindNode(c);
    if (n == NULL)/*c不在树上*/
    {
        /*新增结点*/
        n = (Node*)malloc(sizeof(Node));
        n->c = c;
        n->freq = 1;
        n->lcld = n->rcld = NULL;
        n->parent = NEW;
        
        newNode = (Node*)malloc(sizeof(Node));/*新的NEW结点*/
        newNode->c = 0;
        newNode->freq = 0;
        newNode->lcld = newNode->rcld = NULL;
        newNode->parent = NEW;
        
        NEW->lcld = newNode;
        NEW->rcld = n;
        
        NEW = newNode;
    }
    else/*c在树上*/
        n->freq++;
    
    /*调整树*/
 freq = n->freq;
    tempNode1 = n;
    tempNode2;
    
    while (tempNode1 != root)
    {
        tempNode2 = FindFarestNode(freq-1);
        if (tempNode2!=tempNode1->parent && tempNode2!=NULL && tempNode2!=NEW)
            Swap(tempNode1,tempNode2);
        tempNode1->parent->freq++;
        tempNode1 = tempNode1->parent;
        freq = tempNode1->freq;
    }
}

/*对文本text进行自适应哈夫曼编码*/
void Encoding ()
{
    int i = 0;
    while (text[i] != '$')/*每次调整一个字符，输出字符编码*/
    {
        AdjustTree(text[i]);
        PrintTree();
        i++;
    }
}

/*销毁树root*/
void Release ()
{
    int i = 0;
    while (i < NodeNum)
    {
        free(allNode[i]);/*allNode存放了所有结点的地址*/
        i++;
    }
}

/*初始化*/
void Init ()
{
 int i = 0;
    root = (Node*)malloc(sizeof(Node));
    root->c = 0;
    root->freq = 0;
    root->lcld = root->rcld = root->parent = NULL;
    NEW = root;
    NodeNum = 0;
      
    while (i < MAXNODE)
    {
        allNode[i] = NULL;
        i++;
    }
}

int main ()
{
    Init();
    Input();
    Encoding();
    Release();
    return 0;
}