#include  <stdio.h>

#include  <stdlib.h>

#include  <string.h>

#include  <math.h>

int  vectornum;

int  vectorsize;

float  * datafield;

float  * tempcenter;

struct  GROUP

{

	float  * center;//聚類中心坐標
	
	int  groupsize;//聚類包含的樣本個數

} g ,  * group;

int  K;//聚類中心個數



void  initiate ();//讀入數據，初始化聚類中心,參數設定默認值

int  allocate ();//將模式樣本分配給最近的聚類

void  showresult ();//顯示分類結果



float  distance (float  * x , float  * y);//計算兩個向量間的歐氏距離

float  data (int i , int j);//從datafield中讀取指定位置的值

float  * vector (int i);//從datafield中讀取指定的樣本向量

void  write (int i , int j , float data);//向datafield中指定位置寫入值



void  main ()

{

	int  i;
	
	initiate ();
    
	for (i = 1 ; i < 50 ; i++)
	
	{
	
		showresult ();
		
		if (allocate () == 1)break;
	
	}	
	
	showresult ();

	free (datafield);
	
	free (tempcenter);
	
	for (i = 0 ; i < K ; i++)
	
		free (group[i].center);

}



void  initiate ()

{

	int  i , j , size;
	
	float  d;
	
	FILE  * df;
	
	K = 2;
	
	if ((df = fopen ("data.txt" , "r")) == NULL)
	
	{
	
		printf ("Cannot open file\n");
		
		exit (1);
	
	}
	
	fscanf (df , "%5d" , &vectornum);
	
	fscanf (df , "%5d" , &vectorsize);
	
	size = vectornum * (vectorsize + 1);
	
	datafield = (float *) calloc (size , sizeof (d));
	
	tempcenter = (float *) calloc (vectorsize , sizeof (d));
	
	for (i = 0 ; i < vectornum ; i++)
	
	{
	
		for (j = 0 ; j < vectorsize ; j++)
		
		{
		
			fscanf (df , "%10f" , &d);
			
			write (i , j + 1 , d);
		
		}
		
		write (i , 0 , -1);
	
	}
	
	if (feof (df)) printf (" File read error! ");
	
	fclose (df);	
	
	printf ("請輸入聚類數:\n");
	
	scanf ("%d" , &K);
	
	group = (struct GROUP *) calloc (K , sizeof (g));	
	
	for (i = 0 ; i < K ; i++)
	
	{
	
		group[i].center = (float*) calloc ((vectorsize) , sizeof (d));
		
		group[i].groupsize = 0;
	
	}
	
	for (i = 0 ; i < K ; i++)
	
	{
	
		for (j = 0 ; j < vectorsize ; j++)
		
		{
		
			*(group[i].center + j) = data (i , j + 1);

		}
	
	}

}


	
int  allocate()

{

	int  i , j , k , flag , index;
	
	float  D , D1 , sum;	
	
	for (i = 0 ; i < K ; i++)
	
	{
	
		group[i].groupsize = 0;
	
	}
	
	for (i = 0 ; i < vectornum ; i++)//按距離分配到各聚類域
	
	{
	
		D = distance (group[0].center , vector(i));
		
		k = 0;
		
		for(j = 1 ; j < K ; j++)
		
		{
		
			D1 = distance (group[j].center , vector(i));
			
			if(D > D1)
			
			{
			
				k = j;
				
				D = D1;
			
			}
		
		}

		write (i , 0 , (float) k);		
		
		group[k].groupsize++;
	
	}
	
	flag = 1;
	
	for (index = 0 ; index < K ; index++)//計算新的聚類中心
	
	{
	
		for (j = 0 ; j < vectorsize ; j++)
		
			tempcenter[j] = 0.0;
		
		sum = (float) group[index].groupsize;
		
		for (i = 0 ; i < vectornum ; i++)
		
		{
		
			if (index == (int) data (i , 0))
			
				for (j = 0 ; j < vectorsize ; j++)
				
					tempcenter[j] += data (i , j + 1) / sum;
		
		}
		
		for (j = 0 ; j < vectorsize ; j++)
		
		{
		
			if ( tempcenter[j] != group[index].center[j])
			
			{
			
				group[index].center[j] = tempcenter[j];
				
				flag = 0;
			
			}
		
		}

	}
	
	return flag;	

}



void  showresult()

{

	int  i , j , k;
	
	for (i = 0 ; i < K ; i++)
	
	{	
	
		printf ("\n第%3d組聚類中心坐標為:" , i + 1);
		
		for (j = 0 ; j < vectorsize ; j++)
		
			printf (" %10f " , group[i].center[j]);
		
		printf (" \n聚類包含的樣本點的坐標為:\n ");
		
		for (j = 0 ; j < vectornum ; j++)
		
		{
		
			if (data (j , 0) == i)
			
			{
			
				for (k = 0 ; k < vectorsize ; k++)
				
				{
				
					printf (" %10f " , data (j , k + 1));
				
				}
				
				printf (" \n ");
			
			}
	
		}	
		
	}

	printf (" \n ");

}



float  data (int i , int j)

{

	return *(datafield + i * (vectorsize + 1) + j);

}



void  write (int i , int j , float data)

{

	*(datafield + i * (vectorsize + 1) + j) = data;

}



float  * vector (int i)

{ 

	return datafield + i * (vectorsize + 1) + 1;

}



float  distance (float  * x , float  * y)
{

	int  i;
	
	float  z;
	
	for (i = 0 , z = 0 ; i < vectorsize ; i++)
	
		z = z + ((* (x + i)) - (* (y + i)))*((* (x + i))-(* (y + i)));
	
	return (float) sqrt (z);

}