c语言构建哈夫曼树(附运行结果图)_哈夫曼树建立c语言

c语言构建哈夫曼树(附运行结果图)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“哈夫曼树建立c语言”。

#include #include #include

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

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

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

if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;for(j = 1;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){ // 算法6.13

// w存放n个字符的权值(均>0)，构造哈夫曼树HT，// 并求出n个字符的哈夫曼编码HC int i, j;char *cd;int p;int cdlen;

if(n

m = 2 * n-1;

HT =(HuffmanTree)malloc((m+1)* sizeof(HTNode));// 0号单元未用

for(i=1;i

HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;

}

for(i=n+1;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

printf(“n%4d%8d%8d%8d%8d”,i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);for(i=n+1;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=%dn”, s1, s2);printf(“ 结点 weight parent lchild rchild”);for(j=1;j

printf(“n%4d%8d%8d%8d%8d”,j,HT[j].weight, HT[j].parent,HT[j].lchild, HT[j].rchild);

}

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

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

p = m;cdlen = 0;

for(i=1;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] ='';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

HuffmanCoding(HT,HC,w,n);puts(“n各结点的哈夫曼编码:”);for(i = 1;i

printf(“%2d(%4d):%sn”,i,w[i-1],HC[i]);getchar();} 运行结果：