ln14.c

有关数据结构的一些例子。用C语言编写的。非常有价值的程序。对初学者有指导借鉴意义。

#define NULL 0
#define n 7
#define m 2*n-1
#include "stdio.h"
typedef int datatype;
typedef struct
{ datatype weight;
  int lchild,rchild,parent;
} hufmtree;
hufmtree tree[m];

typedef struct
{ char bits[n];
  int start;
  char ch;
} codetype;
codetype code[n];

HUFFCODE(code ,tree)
codetype code[];
hufmtree tree[];
{ int i,c,p;
  codetype cd;
  char x;
  for(i=0;i<n;i++)
  { cd.start=n;
    printf("字符:");
    scanf("%c",&cd.ch);
    scanf("%c",&x);
    c=i+1;
    p=tree[i].parent;
    while(p!=0)
    { cd.start--;
      if(tree[p-1].lchild==c)
	 cd.bits[cd.start]='0';
      else
	 cd.bits[cd.start]='1';
      c=p;
      p=tree[p-1].parent;
    }
      code[i]=cd;      printf("%c",code[i].ch);
  }
}

DECODE(code,tree)
codetype code[];
hufmtree tree[];
{ int i,b;
  int endflag=-1;
  i=m-1;
  printf("请输入0、1密码:\t");
  scanf("%d",&b);
  while(b!=endflag)
  { if(b==0)
      i=tree[i].lchild-1;
    else
      i=tree[i].rchild-1;
    if(tree[i].lchild==0)
	 { printf("%c\t",code[i].ch);
	   i=m-1;
	 }
    scanf("%d",&b);
  }
  if(tree[i].lchild!=0)
    printf("\n错误!\n");
}

HUFFMAN(tree)
hufmtree tree[];
{ int i,j,p1,p2;
  datatype small1,small2,f;
  printf("\n哈夫曼树:\n");
  for(i=0;i<m;i++)
  { tree[i].parent=0;
    tree[i].lchild=0;
    tree[i].rchild=0;
    tree[i].weight=0;
  }
  for(i=0;i<n;i++)
  { printf("权值:\t");
    scanf("%d",&f);
    tree[i].weight=f;
  }
  for(i=n;i<m;i++)
  { p1=0; p2=0;
    small1=100; small2=100;
    for(j=0;j<i;j++)
      if(tree[j].parent==0)
	if(tree[j].weight<small1)
	 { small2=small1;
	   small1=tree[j].weight;
	   p2=p1;
	   p1=j;
	 }
	else
	  if(tree[j].weight<small2)
	   { small2=tree[j].weight;
	     p2=j;
	   }
    tree[p1].parent=i+1;
    tree[p2].parent=i+1;
    tree[i].lchild=p1+1;
    tree[i].rchild=p2+1;
    tree[i].weight=tree[p1].weight+tree[p2].weight;
  }
  printf("weight\tparent\tlchild\trchild\n");
  for(i=0;i<m;i++)
  printf("  %d\t  %d\t  %d\t  %d\n",tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild);
}

main()
{
  HUFFMAN(tree);
  HUFFCODE(code,tree);
  DECODE(code,tree);
}