数据结构 二叉树应用:赫夫曼编码二
【摘要】 #include <stdio.h>#include <stdlib.h>#include <string.h>#include <malloc.h> #define swap(a,b) {int t; t=a; a=b;b=t;} typedef struct { unsigned int weight; unsigned i...
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
#include <malloc.h>
-
-
#define swap(a,b) {int t; t=a; a=b;b=t;}
-
-
typedef struct
-
{
-
unsigned int weight;
-
unsigned int parent, lchild, rchild;
-
}HTNode, *HuffmanTree;
-
-
typedef char** HuffmanCode;
-
-
void Select(HuffmanTree HT,int n,int &s1,int &s2)
-
{
-
int i,k;
-
int j = 0;
-
int *a = (int*)malloc(n * sizeof(int));
-
for (i=1; i<=n; ++i)
-
{
-
if (HT[i].parent == 0)
-
{
-
a[j++] = HT[i].weight;
-
}
-
}
-
for (i=0; i<j-1; i++)
-
{
-
for (k=j-2; k>=i; k--)
-
{
-
if (a[k] > a[k+1])
-
{
-
swap(a[k],a[k+1]);
-
}
-
}
-
}
-
s1 = a[0];
-
s2 = a[1];
-
for (i=1; i<=n; ++i)
-
{
-
if (s1 ==(int) HT[i].weight && HT[i].parent == 0)
-
{
-
s1 = i;
-
break;
-
}
-
}
-
for (i=1; i<=n; ++i)
-
{
-
if (s2 == (int) HT[i].weight && HT[i].parent == 0)
-
{
-
if (i != s1)
-
{
-
s2 = i;
-
break;
-
}
-
else
-
{
-
continue;
-
}
-
}
-
}
-
free(a);
-
}
-
-
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
-
{
-
HuffmanTree p;
-
int i,m;
-
int s1,s2;
-
char *cd;
-
if (n<=1)
-
{
-
return;
-
}
-
m = 2*n -1;/*n个字符，其赫夫曼树的结点个数为2*n -1*/
-
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); //0号单元未用
-
for (p = HT+1 , i=1; i<=n; ++i,++p,++w)
-
{
-
p->weight = *w;
-
p->lchild = p->parent = p->rchild = 0;
-
}
-
for (;i<=m; ++i,++p)
-
{
-
p->lchild = p->parent = p->rchild = p->weight = 0;
-
}
-
for (i=n+1; i<=m; ++i)
-
{
-
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;
-
}
-
HC = (HuffmanCode)malloc((n+1) * sizeof(char *));
-
cd = (char*)malloc(n*sizeof(char));
-
int q = m,cdlen = 0;
-
for (i=1; i<=m; i++)
-
{
-
HT[i].weight = 0;
-
}
-
while (q)
-
{
-
if (HT[q].weight == 0)
-
{
-
HT[q].weight = 1;
-
if (HT[q].lchild != 0)
-
{
-
q = HT[q].lchild;
-
cd[cdlen++] = '0';
-
}
-
else if (HT[q].rchild == 0)
-
{
-
HC[q] = (char*)malloc((cdlen+1) * sizeof(char));
-
cd[cdlen] = '\0';
-
strcpy(HC[q],cd);
-
}
-
}
-
else if (HT[q].weight == 1)
-
{
-
HT[q].weight = 2;
-
if (HT[q].rchild != 0)
-
{
-
q = HT[q].rchild;
-
cd[cdlen++] = '1';
-
}
-
}
-
else
-
{
-
HT[q].weight = 0;
-
q = HT[q].parent ;
-
--cdlen;
-
}
-
}
-
free(cd);
-
}
-
-
int main()
-
{
-
HuffmanTree HT;
-
HuffmanCode HC;
-
int i;
-
//int a[] = {5,29,7,8,14,23,3,11};
-
//int a[] = {27,8,15,15,30,5};
-
int a[] = {45,13,12,16,9,5};
-
int n = sizeof(a) / sizeof(a[0]);
-
HuffmanCoding(HT,HC,a,n);
-
for (i=1; i<=n; i++)
-
{
-
printf("%d:%s\n",a[i-1],HC[i]);
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17268171
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）