huffman.txt

haffuman编码 C语言实现 数据结构实验

#include<stdio.h>
#include"string"
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;


int *Select(HuffmanTree HT,int n,int s[2]){
int i;s[1]=1;
while(HT[s[1]].parent!=0) ++s[1];i=s[1];
for(;i<=n;i++)
{
while(HT[i].parent!=0) ++i;
if(HT[i].parent<HT[s[1]].parent) s[0]=i;}
for(i=s[1];i<=n;i++)
{
while(HT[i].parent!=0||i==s[0]) ++i;
if(HT[i].parent<HT[s[1]].parent) s[1]=i;
}return s;
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n,int*w)
{
int m;int i;int s[2];
char *cd;int start;int c;int f;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=1;i<=n;++i,++p,++w) {p->weight=*w;p->parent=0;p->lchild=0;p->rchild;}
for(;i<=m;++i,++p) {p->weight=0;p->parent=0;p->lchild=0;p->rchild;}
for(i=n+1;i<=m;++i)
{
	Select(HT,i-1,s);
    HT[s[0]].parent=i;
    HT[s[1]].parent=i;
    HT[i].lchild=s[0];
    HT[i].rchild=s[1];
    HT[i].weight=HT[s[0]].weight+HT[s[1]].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,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));
strcpy(HC[i],&cd[start]);
}
free(cd);
}



void main()
{
HuffmanTree HT;HuffmanCode HC;
int n,*w;
int i;                                                    
printf("\nPlease input the leaf num of tree:\n");
scanf("%d",&n);
w=(int*)malloc((n+1)*sizeof(int));
printf("Please input the weight of every leaf:\n");
for(i=1;i<n+1;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,n,w);
printf("The Huffman code are:\n");
for(i=1;i<n+1;i++)
{printf("%d:%s",HT[i].weight,HC[i]);}
}