| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 732 人关注过本帖, 2 人收藏
标题:赫夫曼编码(优先队列实现)
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  问题点数:0  回复次数:0   
赫夫曼编码(优先队列实现)
/*
    Name: 赫夫曼编码(优先队列实现)
    Copyright:
    Author: 巧若拙
    Date: 28/09/14 12:17
    Description:
    采用优先队列把一个普通线性表改造成赫夫曼树,再进行赫夫曼编码,得到一个同时记录了明文和对应编码的密码本。
    使用优先队列(最小堆)构造赫夫曼树是一种高效的方法,比每次都遍历整个线性表要快很多。
    我在构造密码本时确保密码本数组递增排序,这样每次插入新结点时可以折半查找插入,效率较高。
    有序的密码本在把明文编码成密文时也可以大大提高查找效率。
*/

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include<time.h>

#define MAXSIZE 300
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef char ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

typedef struct {
    ElemType data;
    int weight;
    int parent;
    int lchild;
    int rchild;
} HNodeType;    //结点结构体

typedef struct {
    ElemType data; //明文信息
    char *code;    //密文信息
} HCodeType;    //编码结构体

void BuildMinHeap(HNodeType Hf[], int n);//将线性表Hf改造成一个最小堆
void MinHeapSiftDown(HNodeType Hf[], int n, int pos);//向下调整二叉堆的第pos个元素,使其满足最小堆的特征
void HuffmanTree (HNodeType Hf[], int n);//将线性表改造成赫夫曼树
void DisplayCodebook(HCodeType Cb[], int n);//显示密码本中的明码和对应密码信息
int InsertCodeLib(HCodeType Cb[], int n, ElemType x, char *s, int len);//将新结点插入到密码本的编码线性表中
int HfCoding(HCodeType Cb[], HNodeType Hf[], int n);//根据赫夫曼树进行赫夫曼编码,生成密码本

int main(void)
{
    HNodeType Hf[MAXSIZE*2];   //赫夫曼树
    HCodeType codebook[MAXSIZE]; //密码本
    int lenHf = 5; //赫夫曼树叶子结点个数
    int lenCb;    //密码本长度(等于lenHf)
    int i;
   
    for (i=0; i<lenHf; i++) //随机产生数据和权值
    {
        Hf[i].data = 'A' + i;
        Hf[i].weight = rand() % 10 + 1;
        printf("%c : %d\n", Hf[i].data, Hf[i].weight);
    }

    HuffmanTree (Hf, lenHf); //将线性表改造成赫夫曼树
   
    lenCb = HfCoding(codebook, Hf, lenHf*2-1);//根据赫夫曼树进行赫夫曼编码,生成密码本
    puts("密码本:");
    DisplayCodebook(codebook, lenCb);//显示密码本中的明码和对应密码信息
   
    return 0;
}

/*
函数功能:将线性表改造成赫夫曼树
初始条件:非递减线性表Hf已经存在
操作结果:先将原线性表改造成最小堆(优先队列),然后按照如下顺序处理该最小堆:
删除权重最小的两个结点,并将他们加入到队列尾部,将该两个最小结点的权值相加,生成一个新结点,并将新结点加入到优先队列。
不断调整该最小堆,直到只剩下一个结点,即得到赫夫曼树。
注意:每次产生新结点时,只需设置新结点的权重及孩子结点信息,双亲结点信息等赫夫曼树构造完毕后再统一计算。  
*/
void HuffmanTree (HNodeType Hf[], int n)
{
    int i;
    int len = 2*n - 1;
    int front = n -1;
    int rear = len - 1;
   
    BuildMinHeap(Hf, n);
   
    for (i=0; i<len; i++) //初始化孩子结点位置
    {
        Hf[i].lchild = Hf[i].rchild = -1;
    }
   
    while (front > 0)
    {
        //删除权重最小的两个结点,并将他们加入到队列尾部
        Hf[rear] = Hf[0];
        Hf[0] = Hf[front];   
        MinHeapSiftDown(Hf, front+1, 1);//向下调整二叉堆的第1个元素,使其满足最小堆的特征
        Hf[rear-1] = Hf[0];
        //设置新结点的权重及孩子结点信息
        Hf[0].weight = Hf[rear].weight + Hf[rear-1].weight;
        Hf[0].lchild = rear;
        Hf[0].rchild = rear - 1;
        MinHeapSiftDown(Hf, front, 1);//向下调整二叉堆的第1个元素,使其满足最小堆的特征
        rear -= 2; //由于有两个结点加入新队列,队尾指示前移2位
        front--;//由于有(2-1 = 1)结点出列,队头指示前移1位  
    }
   
    //计算父亲结点位置
    Hf[0].parent = -1;
    for (i=0; i<len; i++)
    {
        Hf[Hf[i].lchild].parent = Hf[Hf[i].rchild].parent = i;   
    }
}

/*
函数功能:将新结点插入到密码本的编码线性表中
初始条件:每个编码的明文和密文信息分别记录在x和s中,len是字符串s的长度
操作结果:先折半查找插入位置,然后插入新结点,将x和s的信息复制给新结点,注意s中存储的结点编码的路径是从叶子到根,存储到密码本时需要逆序复制 。
*/
int InsertCodeLib(HCodeType Cb[], int n, ElemType x, char *s, int len)//采用二分查找插入排序
{
    int i, mid;
    int left = 0, right = n-1;
   
    while (left <= right)//折半查找插入位置
    {
        mid = (left + right) / 2;
        
        if (x > Cb[mid].data)
        {
            left = mid + 1;
        }
        else
        {
            right = mid -1;
        }
    }
    //新数据,执行插入操作
    for (i=n; i>left; i--)
    {
        Cb[i] = Cb[i-1];
    }
   
    Cb[left].code = (char*)malloc(sizeof(char)*(len+1));
    if (!Cb[left].code)
    {
        printf("Out of space!");
        exit(0);
    }
   
    for (i=len-1; i>=0; i--) //把s的字符串逆序复制到code
    {
        Cb[left].code[len-1-i] = s[i];
    }
    Cb[left].code[len] = '\0';
    Cb[left].data = x;

    return n+1;
}

/*
函数功能:根据赫夫曼树进行赫夫曼编码,生成密码本
初始条件:赫夫曼树Hf已经存在,n是赫夫曼树的长度
操作结果:对赫夫曼树的叶子结点进行编码,并存储到密码本,返回密码本长度。
对密码本中的各个结点采用二分查找插入,构造非递减序列,以便于查找和编码。
*/
int HfCoding(HCodeType Cb[], HNodeType Hf[], int n)
{
    int i, j, k, f;
    int top = 0; //为编码结构体构造一个栈,top指示栈顶
    char str[MAXSIZE]; //存储编码的临时字符串

    for (i=0; i<n; i++)
    {
        if (Hf[i].lchild == -1)//是叶子结点
        {   
            j = i;
            f = Hf[j].parent;
            k = 0;
            
            while (f != -1) //逆序存储该结点的编码,注意结点编码的路径是从叶子到根,存储到密码本时需要逆序复制
            {  
                if (j == Hf[f].lchild)
                {
                    str[k++] = '0';
                }
                else
                {
                    str[k++] = '1';
                }
               
                j = f;
                f = Hf[j].parent;
            }
            str[k] = '\0';
        
            top = InsertCodeLib(Cb, top, Hf[i].data, str, k);//采用二分查找插入排序
        }
    }
   
    return top;
}

/*
函数功能:显示密码本中的明码和对应密码信息
初始条件:密码本已经存在
操作结果:显示密码本中的明码和对应密码信息。
*/
void DisplayCodebook(HCodeType Cb[], int n)
{
    int i, j;
   
    for (i=0; i<n; i++)
    {
        printf("%c: ", Cb[i].data);
        puts(Cb[i].code);
    }
}

/*
函数功能:向下调整二叉堆的第pos个元素,使其满足最小堆的特征
初始条件:最小堆Hf已经存在,只有第pos个元素不满足特征
操作结果:向下调整二叉堆的第pos个元素,使其满足最小堆的特征。
*/
void MinHeapSiftDown(HNodeType Hf[], int n, int pos)
{
    HNodeType temp = Hf[pos-1];
    int child = pos * 2; //指向左孩子
   
    while (child <= n)
    {
        if (child < n && Hf[child-1].weight > Hf[child].weight) //有右孩子,且右孩子更小些,定位其右孩子
            child += 1;
        
        if (Hf[child-1].weight < temp.weight) //通过向上移动孩子结点值的方式,确保双亲大于孩子
        {
            Hf[pos-1] = Hf[child-1];
            pos = child;
            child = pos * 2;
        }
        else
            break;
    }
   
    Hf[pos-1] = temp; //将temp向下调整到适当位置
}

/*
函数功能:将线性表Hf改造成一个最小堆
初始条件:线性表Hf已经存在
操作结果:将线性表Hf改造成一个最小堆
*/
void BuildMinHeap(HNodeType Hf[], int n)
{
    int i;
   
    for (i=n/2; i>0; i--)
    {
        MinHeapSiftDown(Hf, n, i);
    }
}
搜索更多相关主题的帖子: Copyright include 线性表 记录 密码 
2014-09-28 12:31
快速回复:赫夫曼编码(优先队列实现)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.061626 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved