/*Title:學(xué)生層次聚類查詢系統(tǒng)
 *Author :ZhengNan
 *Date   :2007.5.20
 *class:計算0503
*/
#include<math.h>
#include<string.h>
#include<iostream.h>
#include<malloc.h>
#include<stdio.h>
int T=52;
 struct student
 {
    char na[20];
    float h; // 定義身高
    float l; // 定義頭發(fā)長度
    int nu ;  //給學(xué)生編碼
 } ;

  struct  student stu[52]={{"LiYinglong",170,11,1},{"HanLanju",170,40,2},{"Zhaoyujing",162,40,3},{"HeZhongfei",173,13,4},{"JiaoDujuan",150,25,5},{"LiTao",167,1,6},{"MiaoQing" ,165,45,7},
   {"PangJiwei",176,10,8},{"LiXinghui",170,10,9},{"YuHongru",163,45,10},{"WuZhihao",180,10,11},{"LiuZhongyu",172,9,12},{"LinJinteng",176,5,13},{"LvYaoming",170,5,14},{"LiuJin",170,8,15},{"ZhengNan",158,40,16},
   {"LiuGang",177,8,17},{"ChenYunLong",175,10,18},{"XiaBing",175,9,19},{"XieNan",160,42,20},{"TangYuedong",172,15,21},{"PanGuisheng",180,10,22},{"ZuoShanshan",158,30,23},{"LiZhongyi",171,2,24},
   {"ZhangMeng",174,3,25},{"WangMing",165,15,26},{"LiuJia",float(174.5),7,27},{"LiuWeiwei",183,11,28},{"ChenXiaoping",160,25,29},{"WuMinxia",160,15,30},{"XuYuhan",157,39,31},{"GaoRui",155,37,32},{"QiFengjuan",150,20,33},
   {"ZhangXiaoliang",173,5,34},{"GuoJianqi",178,11,35},{"MuZhaoxi",162,10,36},{"LiuJunjie",174,8,37},{"SunShengjing",168,20,38},{"LiYingjie",155,25,39},{"LinJia",float(170.6),12,40},{"XuWenshi",185,10,41},
   {"ChenWeiping",171,10,42},{"YangJingyu",165,8,43},{"ZhouHaibin",178,12,44},{"ZhangJinhu",174,2.5,45},{"WangZhengyong",175,6,46},{"XieFeng",170,10,47},{"YangYang",170,3,48},{"YangWeiliang",180,7,49},
   {"LiuDeli",179,8,50},{"YuPeipei",160,2,51},{"FuLiang",float(176.7),3,52}};

  struct Leizu
  {
    float hight; //代表此類組的H值
    float length; //代表此類組的L值
    int ab[53]; //此類組包含的學(xué)生號碼
    int o;//記錄數(shù)組元素個數(shù)
  };
struct Leizu lei[53];

void Merge(struct Leizu lei[52])
{   
	float **m;
	m = (float**)malloc((T+1)*sizeof(float*));
	for(int ii = 0; ii < T+1; ii++ )
	{
		m[ii] = (float*)malloc((T+1)*sizeof(float));
	}

      int i,j,i1,j1,st1,st2,p1,p2,p4,p3; //st1，st2為要合并的類別
	  float a,b,c=0,min;
      //建立距離距陣
      for(i=1;i<=T;i++)
      {
        for(j=i;j<=T;j++)
         { 
            a=lei[i].hight -lei[j].hight;
            b=lei[i].length -lei[j].length;
            c=float(sqrt(a*a+b*b));
            m[j][i]=c;
            m[i][j]=c;
         }
      }
      min=m[1][2];
      //查找最小距離類組
      for(i1=1;i1<=T;i1++)
      {
         for(j1=i1+1;j1<=T;j1++)
         {
            if(m[i1][j1]<min)
            {
               min=m[i1][j1];
               st1=i1;
               st2=j1;
            }
         }
      }

     //合并最小距離的類組 
     if(st1>st2)
     {
         p1=st1;
         st2=st1;
         st1=p1;
     }
     p3=lei[st1].o;
     lei[st1].hight=(lei[st1].hight+lei[st2].hight)/2;
     lei[st1].length=(lei[st1].length+lei[st2].length)/2;
     
     
     for(p2=1;p2<=lei[st2].o;p2++)
     {
         p3++;
         lei[st1].ab[p3]=lei[st2].ab[p2];
     }


     lei[st1].o=lei[st1].o+lei[st2].o;
     
	 for(p4=st2;p4<T;p4++) //類組對象調(diào)整，后面留出空位
     {
         lei[p4]=lei[p4+1];
     }
	 
}

void main()
{
   int i,n,j,p,x;
   printf("         ************************************************\n");
   printf("                 歡迎進入學(xué)生層次聚類信息查詢系統(tǒng)\n");
   printf("         ************************************************\n");
   printf("\n請輸入你要分成的類別數(shù):\n");
   scanf("%d",&n);

   //初始化類組 
   int k1;
   for(k1=1;k1<=52;k1++)
   {
      lei[k1].hight=stu[k1-1].h;
      lei[k1].length=stu[k1-1].l;
      lei[k1].ab[1]=k1 ;
      lei[k1].o=1;
   }
   if(n==1)
   {  printf("\n第1個類(52個學(xué)生元素)：\n");
	  for(int u=1;u<=52;u++)
	     printf("%s     ",stu[u-1].na);
   }
  else
  {
	  for(x=1;x<=(52-n);x++)
	  {  
      Merge(lei);
      T=T-1;
	  }
      printf("\n");
   
    //類組元素輸出
    for(i=1;i<=n;i++)
	{
     printf("\n第%d個類(%d個學(xué)生元素)：\n",i,lei[i].o);

      for(j=1;j<=52;j++)
	  {
        p=lei[i].ab[j];
        if(p)
        {
           printf("%s     ",stu[p-1].na);
        }
	  }
	}
  }
  
}