noname

本代码是算法设计课程里的哈夫曼树的查找及绘图实验

Received: from [218.12.100.43] by web15214.mail.cnb.yahoo.com via HTTP; Tue, 01 Jun 2004 22:24:21 CST
Date: Tue, 1 Jun 2004 22:24:20 +0800 (CST)
From: 
    =?gb2312?q?=FFffffc0=FFffffee=20=FFffffd1=FFffffde=FFffffc8=FFffffe3?= <[e-mail]>
Subject: 哈夫曼树作业（改）李艳茹
To: [e-mail]
MIME-Version: 1.0
Content-Type: text/plain; charset=gb2312
Content-Transfer-Encoding: 8bit
Content-Length: 1694


/*This progrm is changed a little,may be it is clear
for others!  liyanru  024093044*/
 #include "math.h"
 #include "stdarg.h"
 #include "graphics.h"
 #include "stdlib.h"
 #include "stdio.h"
 #include "string.h"
 #define X 320.0
 #define Y 25.0
 #define r 10.0
 #define d 60.0
 #define MAX 50
 #define MAXVALUE 1000
 #define MAXLEAF 30
 #define MAXNODE MAXLEAF*2-1
 #define MAXBIT 10
 #define NULL 0

 int n;
   typedef struct {
		  int weight;
		  int parent;
		  int lchild;
		  int rchild;
		  char name;
		  }HNodeType;

typedef struct {
		int weight;
		int bit[MAXBIT];
		int start;
		char name;
	       }HCodeType;
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;

void HaffmanTree()
{
 int i,j,m1,m2, x1,x2;

printf("\n_______________________________________\n");
 printf("\nInput the total number of the leaves:");
 scanf("%d",&n);
 for (i=0;i<2*n-1;i++)
     { HuffNode[i].weight=0;
       HuffNode[i].parent=-1;
       HuffNode[i].lchild=-1;
       HuffNode[i].rchild=-1;
      }

printf("\n_______________________________________\n");
 printf("\nInput the leave and their weights:\n");
 printf("Input the name,then
press'enter',inputweight,press'enter':\n");
 for (i=0;i<n;i++)
   {flushall();
    scanf("%c",&HuffNode[i].name);
    scanf("%d",&HuffNode[i].weight);
   }
 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==-1)
	    {
	     m2=m1; x2=x1;
	     m1=HuffNode[j].weight; x1=j;
	     }
	   else
if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
	    { 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 i,j, c,p;
 HaffmanTree();

printf("\n________________________________________\n");
 for (i=0;i<n;i++)
   {cd.start=n-1;
    c=i;
    p=HuffNode[c].parent;
    while(p!=-1)
      {
       if (HuffNode[p].lchild==c)
	 cd.bit[cd.start]=0;
       else
	 cd.bit[cd.start]=1;
       cd.start--;
       c=p;
       p=HuffNode[c].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 made code of %c
is:",HuffNode[i].name);
    for (j=HuffCode[i].start+1;j<n;j++)
      {
       printf("%d",HuffCode[i].bit[j]);
      }
   printf("\n");
   }
}

void TranslateCode()
{int i;
 char *string=NULL;

printf("\n_______________________________________\n");
 printf("\nInput the code you want to translate,then
press 'enter':\n");
 flushall();
 scanf("%s",string);
 i=2*n-2;
 printf("\nThis is the translated code:");
 while(*string!='\0')
   {
    while(HuffNode[i].rchild!=-1)
     {if(*string=='1')
	i=HuffNode[i].rchild;
     else
	i=HuffNode[i].lchild;
     string++;
    }
 printf("%c",HuffNode[i].name);
 i=2*n-2;
 /* getch();*/
 }

printf("\n_______________________________________\n");
 printf("Press 'enter' you will see the tree!!!\n");
 printf("After seeing the tree,if you want to go
back,press'enter',too!!!\n");
 getch();
 }

DrawTree()
{int i,j,k, x1,x2,y1,y2;
 int str1[30];
 char str2[30];
 int GraphDriver;
 int GraphMode;
 GraphDriver=DETECT;
 initgraph(&GraphDriver,&GraphMode,"C:");
 setbkcolor(YELLOW);
 setcolor(GREEN);
 for(i=0;i<n;i++)
    {
     k=0;x1=X;y1=Y;
    /* getch();*/
     circle(x1,y1,r);
    /* getch();*/
     for(j=HuffCode[i].start+1;j<n;j++)
       {if(HuffCode[i].bit[j]==1)
	 {x2=x1+d/(k+1);
	  y2=y1+d;
	  circle(x2,y2,r);
	  outtextxy((x1+x2)/2,(y1+y2)/2,"1");
	 line(x1,y1,x2,y2);
	 /* getch();*/
	  }
	else
	  {x2=x1-d/(k+1);
	   y2=y1+d;
	   circle(x2,y2,r);
	   outtextxy((x1+x2)/2,(y1+y2)/2,"0");
	  line(x1,y1,x2,y2);
	  /* getch();*/
	   }
      /* if(HuffCode[i].bit[j]==1)
	  { line(x1,y1,x2,y2);
	  getch();
	  }
       else
	 { line(x1,y1,x2,y2);
	  getch();
	 }*/
       x1=x2;y1=y2;k++;

      }
    itoa(HuffNode[i].weight,str2,10);
    outtextxy(x1,y1,str2);
    *str1=HuffNode[i].name;
    outtextxy(x1+r,y1+r,str1);
  }
 getch();
 closegraph();
}

main()
{
 clrscr();
 HaffmanCode();
 TranslateCode();
 DrawTree();
}

_________________________________________________________
Do You Yahoo!? 
嫌邮箱太小？雅虎电邮自助扩容！
http://cn.rd.yahoo.com/mail_cn/tag/10m/*http://cn.mail.yahoo.com/event/10m.html