哈夫曼编码编/译源程序

Question

如题所述

Answer 1

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

#define ok 1
#define error 0

typedef int Status;

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树

typedef char * *HuffmanCode;//动态分配数组存储赫夫曼编码表

Status Select(HuffmanTree HT,int n,int &n1,int &n2)
{//在HT[i-1]中选择parent为0求weight最小的两个节点

int i;
for (i=1;i<=n && HT[i].parent!=0 ;i++);
n1=i;
for (i=1;i<=n;i++)
if (HT[i].parent==0 && HT[i].weight<HT[n1].weight) n1=i;
for (i=1; i<=n ; i++)
if (HT[i].parent==0 && i!=n1) break;
n2=i;
for (i=1;i<=n;i++)
if ( HT[i].parent==0 && i!=n1 && HT[i].weight<HT[ n2].weight) n2=i;
return ok;
}

Status HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{//w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码
int m,s1,s2,i,j,start;
unsigned int c,f;
char *cd;
if(n<=1)return error;
m=2*n-1;//赫夫曼树的总节点数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
//初始化赫夫曼树
for(i=1;i<=n;i++)//1到n号节点
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;i++)//n+1号到m号节点
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;

}
printf("\n哈夫曼树的构造过程如下所示：\n");//输出赫夫曼树初始状态
printf("HT初态:\n节点 weight parent lchild rchild");
for(i=1;i<=m;i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,
HT[i].lchild,HT[i].rchild);

printf("\n按任意键，继续……");
getch();//暂停
for(i=n+1;i<=m;i++)
{//构建赫夫曼树
Select(HT,i-1,s1,s2);//选择weight最小的两个节点是s1，s2
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);//输出选择个两个节点
printf(" 结点 weight parent lchild rchild");//输出赫夫曼树的新状态
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf("\n按任意键，继续 ……");//暂停
getch();

}

//----从叶子节点到根逆向求每个字符的赫夫曼编码----
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
cd=(char *)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;i++)
{//逐个字符求赫夫曼编码
start=n-1;//编码结束位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码（串）到HC
}
free(cd);//释放cd
return ok;

}

void main()
{
printf("请输入字符：");
char a[50];//存储输入字符
char ch;
int i=1,j=0,n,k;
int w[50];//存储权值
HuffmanTree HT;
HuffmanCode HC;
scanf("%c",&ch);
while(ch!='\n')
{
a[i]=ch;
i++;
scanf("%c",&ch);
}
n=i-1;//计算输入字符数
printf("请输入权值:");
for(i=0;i<n;i++)
{
scanf("%d",&k);
w[i]=k;
}
HuffmanCoding(HT,HC,w,n);
printf("\n%d个字符的赫夫曼编码为:\n",n);
for(i=1;i<=n;i++)//输出赫夫曼编码
{
printf("%c(%d):%s\n",a[i],w[i-1],HC[i]);
}
}

Answer 2

#include "stdafx.h"
#include "stdlib.h"

typedef struct BiTNode
{
int data;
char letter;
struct BiTNode *l,*r;
int a[10];
}BiTNode;

int fun(BiTNode *p,int num,int s)
{
int i,k=0,j=0;
int mdate;
int m,n;//m是最小的
while(!(p+j)->data)
{
j++;
if(j==s) break;
}
n=m=j;
if((num-1))
{
for(i=1;i<s;i++)
{
if((p+i)->data)
if((p+m)->data>(p+i)->data)
m=i;
}
if(m==n)
{
while(!(p+k)->data || m==k)
k++;
n=k;
}
for(i=0;i<s;i++)
{
if(i!=m&&(p+i)->data)
if((n+p)->data>(p+i)->data)
n=i;
}
}
else return s;

(p+s)->data=(p+m)->data+(p+n)->data;
(p+s)->l=(p+m);
(p+s)->r=(p+n);
s++;
num--;
(p+n)->data=0;
(p+m)->data=0;
fun(p,num,s);

}

int find(BiTNode *p,int num)
{
int i;
for(i=0;i<num;i++)
if((p+i)->data) return i;
return 0;
}

void display(BiTNode *p,int n,int *b)
{
int k;
if(p!=NULL)
{
if(p->l==NULL && p->r==NULL)
{
for(k=0;k<n;k++)
p->a[k] = b[k];
}
if(p->l!=NULL)
{
b[n++] = 0;
display(p->l,n,b);
}
if(p->r!=NULL)
{
b[n++] = 1;
display(p->r,n,b);
}

}
}

int _tmain(int argc, _TCHAR* argv[])
{
BiTNode *init;
int c[10];
init = (BiTNode*)malloc(sizeof(BiTNode)*100);
char a[]={'a','b','c','d','e','f','g'};
int b[]={4,3,2,7,5,6,1};
int i,k;
for(i = 0;i<7;i++)
{
(init+i)->data=b[i];
(init+i)->letter=a[i];
(init+i)->l=NULL;
(init+i)->r=NULL;
}
i =fun(init,7,7);
i = find(init,i);
init = init+i;
display(init,0,c);
init = init-i;
for(k=0;k<7;k++)
{
for(i=0;(init+k)->a[i]>=0;i++)
{
if(i==0)
printf("%c:",(init+k)->letter);
printf("%d",(init+k)->a[i]);
}
printf("\n");
}
}

typedef struct
{
datatype ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
// 算法6.12
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
unsigned int c, f;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getch();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getch();
}

//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c)
cd[--start] = '0';
else
cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
} // HuffmanCoding