01r295111.cpp

我们数据结构课上的一些作业 包括约瑟夫环和哈夫曼树之类的几个程序

#include <stdio.h>
#include <stdlib.h>
# define MAX 21

typedef struct{
char data;
int weight;
int parent, lchild, rchild;}huffnode;

typedef struct{
 int start;
char cd[MAX];}huffcode;

void main()
{int i,k,l,f,r,m,m1,c,m2,n;
 huffcode hcd[MAX],d;
 huffnode ht[2*MAX];
 printf("please input the number of leave is n:\t");
 scanf("%d",&n); m=2*n-1;

 for(i=1;i<=n;i++){
  getchar();
  printf("the %d number=>\n\t name:",i);
  scanf("%c",&ht[i].data);
  printf("\t weight:");
  scanf("%d",&ht[i].weight);}

 for(i=1;i<=m;i++)
  ht[i].parent=ht[i].lchild=ht[i].rchild=0;

 for(i=n+1;i<=m;i++){
  m1=m2=76798;
  l=r=0;
  for(k=1;k<=i-1;k++)
   if(ht[k].parent==0)
    if(ht[k].weight<m1){
     m2=m1;r=l;m1=ht[k].weight;l=k;}
    else if(ht[k].weight<m2){
     m2=ht[k].weight;r=k;}
    ht[l].parent=i;
    ht[r].parent=i;
    ht[i].weight=ht[l].weight+ht[r].weight;
    ht[i].lchild=l;
    ht[i].rchild=r;}

  for(i=1;i<=n;i++)
   { d.start=n+1;c=i;f=ht[i].parent;
     while(f!=0){
     if(ht[f].lchild==c)
      d.cd[--d.start]='0';
     else
      d.cd[--d.start]='1';
     c=f;f=ht[f].parent;}
     hcd[i]=d;}

   printf("output the huffman bianma:\n");
   for(i=1;i<=n;i++)
   { printf("%c:",ht[i].data);
     for(k=hcd[i].start;k<=n;k++)
     printf("%c",hcd[i].cd[k]);
     printf("\n");}

   printf("please input the mima you want:\t");
   char mc[20]; int j,s,t;    i=0;
   scanf("%s",mc);
   while(mc[i]!='\0')
      i++;
   t=i;
   for(k=0;k<t;k++)
     {j=1;
      while(j<=n)
       {if(mc[k]==ht[j].data)
	  break;
	else j++;}
      if(j<=n)
	{ for(s=hcd[j].start;s<=n;s++)
	    printf("%c",hcd[j].cd[s]);}
      }}