#include <stdio.h> 
#include <math.h>
#define TRUE            1
#define FALSE           0 
int N;//數據個數
int K;//集合個數
int * CenterIndex;//初始化質心數組的索引
double * Center;//質心集合
double * CenterCopy;//質心集合副本
double * AllData;//數據集合
double ** Cluster;//簇的集合
int * Top;//集合中元素的個數，也會用作棧處理

 
//隨機生成k個數x(0<=x<=n-1)作為起始的質心集合
void CreateRandomArray(int n, int k,int * center)
{
    int i=0;
    int j=0;    
    srand( (unsigned)time( NULL ) );
    for( i=0;i<k;++i)//隨機生成k個數
    {
        int a=rand()%n;//判重
        
        for(j=0;j<i;j++)
            if(center[j]==a)//重復
                break;

        if(j>=i)//如果不重復，加入
            center[i]=a;
        else
            i--;//如果重復，本次重新隨機生成

    }     
}
 
//返回距離最小的質心的序號
int GetIndex(double value,double * center)
{
    int i=0;
    int index=i;//最小的質心序號
    double min=fabs(value-center[i]);//距質心最小距離
    for(i=0;i<K;i++)
    {
        if(fabs(value-center[i])<min)//如果比當前距離還小，更新最小的質心序號和距離值
        {
             index=i;
             min=fabs(value-center[i]);
        }
    }
    return index;
}
 

void CopyCenter()//拷貝質心數組到副本
{
    int i=0;
    for(i=0;i<K;i++)
        CenterCopy[i]=Center[i];
}

void InitCenter()//初始化質心，隨機生成法
{
    int i=0;
    CreateRandomArray(N,K,CenterIndex);//產生隨機的K個<N的不同的序列
    for(i=0;i<K;i++)
    {
        Center[i]=AllData[CenterIndex[i]];//將對應數據賦值給質心數組
    }
    CopyCenter();//拷貝到質心副本
}

void AddToCluster(int index,double value)//加入一個數據到一個Cluster[index]集合
{
    Cluster[index][Top[index]++]=value;//這里同進棧操作
} 

//重新計算簇集合
void UpdateCluster()
{    
    int i=0;
    int tindex;
    //將所有的集合清空，即將TOP置0
    for(i=0;i<K;i++)
        Top[i]=0;
    for(i=0;i<N;i++)
    {
        tindex=GetIndex(AllData[i],Center);//得到與當前數據最小的質心索引
        AddToCluster(tindex,AllData[i]);        //加入到相應的集合中 
    }
}

void UpdateCenter()//重新計算質心集合，對每一簇集合中的元素加總求平均即可
{
    int i=0;
    int j=0;
    double sum=0;
    for(i=0;i<K;i++)
    {
        sum=0;  //計算簇i的元素和   
       
        for(j=0;j<Top[i];j++)
             sum+=Cluster[i][j];
        if(Top[i]>0)//如果該簇元素不為空
           Center[i]=sum/Top[i];//求其平均值
    }
}

int IsEqual(double * center1 ,double * center2)//判斷2數組元素是否相等
{
    int i;
    for(i=0;i<K;i++)
    {
         if(fabs(center1[i]!=center2[i]))
             return FALSE;
    }
    return TRUE;
}

void Print()//打印聚合結果
{
    int i,j;
    printf("-------------------------------------- ");
    for(i=0;i<K;i++)
    {
         printf("第%d組: 質心（%f） ",i,Center[i]);
          for(j=0;j<Top[i];j++)
          {
              printf("%f ",Cluster[i][j]);
          }           
    }     
}

void InitData()//初始化聚類的各種數據
{
    int i=0;
    int a;
    printf("輸入數據個數： ");     
    scanf("%d",&N);
    printf("輸入簇個數： ");     
    scanf("%d",&K);    
    if(K>N)
    {
        exit(0);
    }
    Center=(double *)malloc(sizeof(double)*K);//為質心集合申請空間
    CenterIndex=(int *)malloc(sizeof(int)*K);//為質心集合索引申請空間
    CenterCopy=(double *)malloc(sizeof(double)*K);//為質心集合副本申請空間
    Top=(int *)malloc(sizeof(int)*K); 
    AllData=(double *)malloc(sizeof(double)*N);//為數據集合申請空間
    Cluster=(double **)malloc(sizeof(double *)*K);//為簇集合申請空間
    //初始化K個簇集合
    for(i=0;i<K;i++)
    {
        Cluster[i]=(double *)malloc(sizeof(double)*N);
        Top[i]=0;
    }
    printf("輸入%d數據： ",N);
    for(i=0;i<N;i++)
    {
        scanf("%d",&(a));
        AllData[i]=a;
    }
    InitCenter();//初始化質心集合      
    UpdateCluster();//初始化K個簇集合
     
}
/*
算法描述：
K均值算法：
    給定類的個數K，將N個對象分到K個類中去，
    使得類內對象之間的相似性最大，而類之間的相似性最小。
*/
main()
{
    int Flag=1;//迭代標志，若為false,則迭代結束
    int i=0;
     InitData();//初始化數據      
     while(Flag)//開始迭代
     {
         UpdateCluster();//更新各個聚類
         UpdateCenter();//更新質心數組
         if(IsEqual(Center,CenterCopy))//如果本次迭代與前次的質心聚合相等，即已收斂，結束退出
         {
             Flag=0;
         }
         else//否則將質心副本置為本次迭代得到的的質心集合
         {
             CopyCenter();//將質心副本置為本次迭代得到的的質心集合
         }
     }
     Print();//輸出結果
     getchar();
     getchar();
     
}