1.cpp

c语言十字链表源码下载

#include <stdio.h>
#include <stdlib.h>
#define MAXVALUE 1000     /*定义最大权值*/
#define MAXLEAF 30           /*定义哈夫曼树中叶子结点个数*/
#define MAXNODE  MAXLEAF*2-1
#define MAXBIT 10                 /*定义哈夫曼编码的最大长度*/
    
typedef struct {
        int weight;
        int parent;
        int lchild;
        int rchild;
       }HNodeType;

typedef struct {
        int bit[MAXBIT];
        int start;
       }HCodeType;

 void  HaffmanTree(HNodeType HuffNode [ ],int n)
{		/*哈夫曼树的构造算法*/
	int i,j,m1,m2,x1,x2;
	for (i=0;i<2*n-1;i++)         /*数组HuffNode[ ]初始化*/
        { HuffNode[i].weight=0;
          HuffNode[i].parent=0;
          HuffNode[i].lchild=0;
          HuffNode[i].rchild=0;
         }
      for (i=0;i<n;i++)
	  {
		  printf("输入%d个叶子结点的权值:",i+1);
		scanf("%d",&HuffNode[i].weight); 
	  } /*输入n个叶子结点的权值*/
      for (i=0;i<n-1;i++)            /*构造哈夫曼树*/
        { m1=m2=MAXVALUE;
          x1=x2=0;
          for (j=0;j<n+i;j++)
           { if (HuffNode[j].weight<m1 && HuffNode[j].parent==0)
              { m2=m1;     x2=x1;
                m1=HuffNode[j].weight;    x1=j;
              }
		  else if (HuffNode[j].weight<m2 && HuffNode[j].parent==0)
                  { m2=HuffNode[j].weight;
                    x2=j;
                  }
           }
         /*将找出的两棵子树合并为一棵子树*/
         HuffNode[x1].parent=n+i;         HuffNode[x2].parent=n+i; 
         HuffNode[n+i].weight= HuffNode[x1].weight+HuffNode[x2].weight;
         HuffNode[n+i].lchild=x1;  HuffNode[n+i].rchild=x2;     
        }
}


void HaffmanCode (int n )
{ /*生成哈夫曼编码*/
		HNodeType HuffNode[MAXNODE];
		HCodeType HuffCode[MAXLEAF],cd;
		HaffmanTree (HuffNode ,n);		/*建立哈夫曼树*/
		 int i,j, c,p;
		 for (i=0;i<n;i++)                /*求每个叶子结点的哈夫曼编码*/
		 {	
					cd.start=n-1;   c=i;
					p=HuffNode[i].parent;
				while(p!=0)                 /*由叶结点向上直到树根*/
				{
					if (HuffNode[p].lchild==c) cd.bit[cd.start]=0;
					else  cd.bit[cd.start]=1;
					cd.start--;    c=p;
					p=HuffNode[p].parent;
				}
        for (j=cd.start+1;j<n;j++)       /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
			HuffCode[i].bit[j]=cd.bit[j];
			HuffCode[i].start=cd.start;
		 }
			for (i=0;i<n;i++)                /*输出每个叶子结点的哈夫曼编码*/
       {		
				printf("the number:%d's code is:",i+1);
				for (j=HuffCode[i].start+1;j<n;j++)
					printf("%d",HuffCode[i].bit[j]);
					printf("\n");

       }
}

void main()
{
	int n;
	printf("输入字符个数:\n");
	scanf("%d",&n);
	HaffmanCode (n );

}