哈夫曼编码函数c语言 哈夫曼算法c语言

求帮忙用C语言写哈夫曼编码

由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n－1个结点，可以用一个大小为2n－1的一维数组存放哈夫曼树的各个结点。在哈夫曼树构造好后，为了求得哈夫曼编码需要走一条从根结点出发到叶子结点的路径，则对每个结点既要知道其双亲还要知道孩子结点的信息。所以一维数组的每个元素包括四个数据项：结点的权值、结点的双亲结点下标号、左右孩子结点下标号。数据类型的定义如下：

我们一直强调成都网站设计、做网站对于企业的重要性,如果您也觉得重要,那么就需要我们慎重对待,选择一个安全靠谱的网站建设公司,企业网站我们建议是要么不做，要么就做好,让网站能真正成为企业发展过程中的有力推手。专业的建站公司不一定是大公司,创新互联公司作为专业的网络公司选择我们就是放心。

typedef struct Node

{

int weight ;

int parent, LChild,RChild ;

} HTNode, * HTree;

typedef char *HuffmanCode ;

创建哈夫曼树并求哈夫曼编码的算法如下：

viod CreatHTree(HTree ht , HuffmanCode hc,int * w, int n)

{ /*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc */

int start;

m=2*n-1;

ht=(HTree)malloc((m+1)*sizeof(HTNode));

for(i=1;i=n;i++)

ht[i] ={ w[i],0,0,0};

for(i=n+1;i=m;i++)(* ht)[i] ={0,0,0,0};/* 初始化*/

for(i=n+1;i=m;i++)

{

select(ht,i-1,s1,s2);

/* 在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回，select函数要求在上机调试使补充定义*/

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;

} /*哈夫曼树建立完毕*/

/*以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程*/

hc=(HuffmanCode)malloc((n+1)*sizeof(char *));

cd=(char * )malloc(n * sizeof(char));

cd[n-1]＝’\0’；

for(i=1;i=n;i++)

{

start=n-1;

for(c=i,p=ht[i].parent; p!=0; c=p,p=ht[p].parent)

if(ht[p].LChild==c) cd[--start]=‘0’;

else cd[--start]=‘1’;

hc[i]=(char *)malloc((n-start)*sizeof(char));

strcpy(hc[i],cd);

}

free(cd);

}

数组ht的前n个单元存放叶子结点的信息，最后一个单元存放的是根结点。

自己写个主程序，把八个字符的频率读入，调用CreatHTree就可以了

哈夫曼编码的C程序怎么写？

去年做的课程设计，有什么不合要求的自己改改

#includestring.h

#includestdlib.h

#includestdio.h

int m,s1,s2;

typedef struct {

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树

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

void Select(HuffmanTree HT,int n) {

int i,j;

for(i = 1;i = n;i++)

if(!HT[i].parent){s1 = i;break;}

for(j = i+1;j = n;j++)

if(!HT[j].parent){s2 = j;break;}

for(i = 1;i = n;i++)

if((HT[s1].weightHT[i].weight)(!HT[i].parent)(s2!=i))s1=i;

for(j = 1;j = n;j++)

if((HT[s2].weightHT[j].weight)(!HT[j].parent)(s1!=j))s2=j;

}

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC[], int *w, int n) {

// 算法6.13

// w存放n个字符的权值(均0)，构造哈夫曼树HT，

// 并求出n个字符的哈夫曼编码HC

int i, j;

char *cd;

int p;

int cdlen;

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;

}

puts("\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(" 按任意键，继续 ...");

getchar();

for (i=n+1; i=m; i++) { // 建哈夫曼树

// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，

// 其序号分别为s1和s2。

Select(HT, i-1);

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(" 按任意键，继续 ...");

getchar();

}

//------无栈非递归遍历哈夫曼树，求哈夫曼编码

cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间

p = m; cdlen = 0;

for (i=1; i=m; ++i) // 遍历哈夫曼树时用作结点状态标志

HT[i].weight = 0;

while (p) {

if (HT[p].weight==0) { // 向左

HT[p].weight = 1;

if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }

else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码

HC[p] = (char *)malloc((cdlen+1) * sizeof(char));

cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)

}

} else if (HT[p].weight==1) { // 向右

HT[p].weight = 2;

if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }

} else { // HT[p].weight==2，退回退到父结点，编码长度减1

HT[p].weight = 0; p = HT[p].parent; --cdlen;

}

}

} // HuffmanCoding

void main() {

HuffmanTree HT;HuffmanCode *HC;int *w,n,i;

puts("输入结点数:");

scanf("%d",n);

HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));

w = (int *)malloc(n*sizeof(int));

printf("输入%d个结点的权值\n",n);

for(i = 0;i n;i++)

scanf("%d",w[i]);

HuffmanCoding(HT,HC,w,n);

puts("\n各结点的哈夫曼编码:");

for(i = 1;i = n;i++)

printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);

getchar();

}

Huffman编码C语言实现

说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。

#pragmaonce

#includestdio.h

#includetchar.h

#includestdlib.h

#define MAX 100

typedefstruct{ //节点

int weight;

int parent, lchild, rchild;

}HTNode, *HuffmanTree;

typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码

void SelectMinNode(HuffmanTree HT, int m, int i1, int i2) //找出权值最小的两个节点对应的数组下标

{

HuffmanTree p = HT;

int s1, s2;

s1 = s2 = MAX;

i1 = i2 = 1;

for(int i=1; i=m; i++)

{

if(!(p+i)-parent)

{

if((p+i)-weight s1)

{

i2 = i;

s1 = (p+i)-weight ;

}

}

}

for(int i=1; i=m; i++)

{

if(!(p+i)-parent i!=i2)

{

if((p+i)-weight s2)

{

i1 = i;

s2 = (p+i)-weight ;

}

}

}

}

void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制

{

char *c1, *c2;

c1 = p;

while(q != '\0')

{

*c1 = q;

c1++;

start++;

}

*c1 = q;//别忘了将‘\n’复制过来

}

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n)

{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数

int i, i1, i2, m;

HuffmanTree p;

if(n=1) return;

m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。

HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间

p = HT + 1;

for(i=1;i=n;++i,++p,++w) //n个叶子节点初始化

{

p-weight = *w;

p-lchild = 0;

p-rchild = 0;

p-parent = 0;

}

for(;i=m;++i,++p) //非叶子节点初始化

{

p-weight = 0;

p-lchild = 0;

p-rchild = 0;

p-parent = 0;

}

for(i=n+1;i=m;++i) //对非叶子节点重新计算

{

SelectMinNode(HT, i-1, i1, i2);

HT[i1].parent = i;

HT[i2].parent = i;

HT[i].lchild = i1;

HT[i].rchild = i2;

HT[i].weight = HT[i1].weight + HT[i2].weight ;

}

///从叶子节点到根节点求赫夫曼编码

char* cd;

int start, c, f;

HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个

cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码

cd[n-1] = '\0';

for(int 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));

StrCopy(HC[i], cd, start); //将存储的编码copy给HC的第i个数组

}

free(cd);

}

void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码

{

HuffmanCode p;

for(int i=1; i=n; i++)

{

p = HC;

printf("The weight %d HuffmanCode is: ", HT[i]);

while(*p[i]!='\0')

{

printf("%c",*p[i]);

p[i]++;

}

printf("\n");

}

}

void main()

{

int n = 8;

HuffmanTree HT;

HuffmanCode HC;

int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1}

HuffmanCoding(HT, HC, a, n);

PrintHuffmanCode(HT, HC, n);

system("pause");}