哈夫曼编码 c语言 求改正
发布网友
发布时间：2022-10-23 02:40
共2个回答
热心网友
时间：2024-10-30 12:36
#include<stdlib.h>
#include<stdio.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].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))
s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))
s2=j;
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC[], int *w, int n)
{
/* 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;
}
printf("\nHuffman tree construction process as follows:\n");
printf("HT List:\nNumber\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for (i=1; i<=m; i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");
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("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for (j=1; j<=i; j++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
}
/* 无栈非递归遍历哈夫曼树，求哈夫曼编码 */
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;
long int a[100],p,q;
printf("Input the number of nodes:");
scanf("%d",&n);
HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("Enter weight:\n");
for(i=0;i<n;i++)
{
printf("w[%d]=",i+1);
scanf("%d",&w[i]);
}
HuffmanCoding(HT,HC,w,n);
printf("\nEach node of the Huffman coding:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,w[i-1],HC[i]);
system("pause");
}
热心网友
时间：2024-10-30 12:36
