#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<math.h>

typedef int datatype;  /*二維圖表的數據類型*/
#define line 5  /*行*/
#define row 5   /*列*/
#define maxsize 20  /*聚點最大值*/

typedef struct node
{
	int x;
	int y;
	struct node *next;
}linkstack;   /*鏈棧結點類型*/
linkstack *top;

typedef struct
{
	int x;
	int y;/*坐標增量，取值－1，0，1*/
}moved;
moved move[4];

void Begin();
void Progress();
void End();
void daying1(); /*打印二維數組圖表*/
void daying2(int jvdian[],int i,int j); /*打印聚點數組*/
void Restore();/*恢復原始圖表，并輸出*/
void Shaomiao(); /*掃描方向表*/
linkstack *Pushlstack(linkstack *top,int i,int j);/*將元素x插入鏈棧top的頂部*/
linkstack *Poplstack(linkstack *top,int *i,int *j);/*刪除鏈棧top的頂部結點*/
void Data_chuli(int xz,int yz);/*核心的算法：處理單個聚點*/
void Quicksort(int R[],int sl,int tl);  /*對R[sl]到R[tl]快速排序*/ 
int Partition(int R[],int l,int h); /*返回劃分后被定位的基準記錄的位置*/
                                         /*對無序區R[l]到R[h]的劃分*/
void Savefile();/*在外存中用文件的形式保存所有數據:原始圖表，聚點數組，平均像素*/

datatype picture[line+2][row+2];
int jvdian[maxsize]; /*用來記錄聚點的信息*/
int count=0;  /*統計聚點的像素*/
int total=0;  /*統計聚點的個數*/
float average;  /*所有聚點的平均像素*/

int main()
{
	Shaomiao();
	Begin();
	Progress();
	End();
	Savefile();

	return 0;
}

void Shaomiao()
{
	move[0].x=0;
	move[0].y=-1;
	move[1].x=1;
	move[1].y=0;
	move[2].x=0;
	move[2].y=1;
	move[3].x=-1;
	move[3].y=0;
}

linkstack *Pushlstack(top,i,j)/*將元素x插入鏈棧top的頂部*/
linkstack *top;
int i;
int j;
{
	linkstack *p;
	p=malloc(sizeof(linkstack));/*生成新結點*p*/
	p->x=i;
	p->y=j;
	p->next=top;
	return p;/*返回新棧頂指針*/
}

linkstack *Poplstack(tp,i,j)/*刪除鏈棧top的頂點結點*/
linkstack *tp; /*讓datap指向頂點結點的值，返回新棧指針*/
int *i;
int *j;
{
	linkstack *p;
	if(tp==NULL)
	{
		printf("One point has been dealed with.\n");
        return NULL;
	}
	else
	{
		*i=tp->x;
		*j=tp->y;/*棧頂結點數據存入*datap*/
		p=tp;      /*保存棧頂結點地址*/
		tp=tp->next; /*從鏈棧上摘下棧頂結點*/
		free(p);    /*釋放原棧頂結點*/
		return tp; /*返回新棧頂結點*/
	}
}

int Partition(R,l,h) /*返回劃分后被定位的基準記錄的位置*/
int R[];   /*對無序區R[l]到R[h]的劃分*/
int l;
int h;
{
	int i,j,temp;
	
	i=l;  j=h;  temp=R[i]; /*初始化，temp為基準*/

	do{
		while((R[j]>=temp) && (i<j))
			j--;    /*從右向左掃描，查找第一個關鍵字小于temp的記錄*/
		if(i<j) R[i++]=R[j];  /*交換R[i]和R[j]*/
		while((R[i]<=temp) && (i<j))
			i++;    /*從左向右掃描，查找第一個關鍵字大于temp的記錄*/
		if(i<j) R[j--]=R[i];  /*交換R[i]和R[j]*/
	} while(i!=j);
	R[i]=temp;      /*基準temp已被最后定位*/
	
	return i;
}   /*Partition*/

void Quicksort(R,sl,tl)  /*對R[sl]到R[tl]快速排序*/
int R[];
int sl;
int tl;
{
	int i;

	if(sl<tl)      /*只有一個記錄或者沒有記錄時無須排序*/
	{
		i=Partition(R,sl,tl); /*對R[sl]到R[tl]做劃分*/
		Quicksort(R,sl,i-1);  /*遞歸處理左區間*/
		Quicksort(R,i+1,tl);  /*遞歸處理右區間*/
	}
}   /*Quicksort*/

void Begin()
{
	int i,j,k;
	int temp;
	
	k=1;
	for(i=0;i<=line+1;i++)
	{
		picture[i][0]=0;
        picture[i][row+1]=0;
	}
	for(i=0;i<=row+1;i++)
	{
		picture[0][i]=0;
        picture[line+1][i]=0;
	}

	for(i=1;i<=line;i++)
		for(j=1;j<=row;j++)
		{
			printf("Picture[%d][%d]=",i,j);
			scanf("%d",&temp);
			picture[i][j]=temp;
			if  (fmod(k,row)==0) printf("\n\n");
			k++;
		}

}

void Progress()
{
	int m,n;
	
	for(m=1;m<=line;m++)
		for(n=1;n<=row;n++)
			if ((picture[m][n]!=0) && (picture[m][n]!=-1 ))
			{
				count=0;
				total++;
				Data_chuli(m,n);
				jvdian[total]=count;
			}
}

void Data_chuli(xz,yz)/*核心的算法：處理單個聚點*/
int xz; /*x軸*/
int yz; /*y軸*/
{
	int i,j,v;
	int k,l; /*記錄棧頂結點的坐標*/
	
	i=xz;
	j=yz;

    

	if ((picture[i][j]!=0) && (picture[i][j]!=-1))
	{		
		top=Pushlstack(top,i,j);  /*將未處理的點入棧、*/
		count++;                  /*統計、*/
		picture[i][j]=-1;       /*做標記，取值為－1*/
	}
	
	for(v=0;v<4;v++)/*掃描四個方向，符合條件的入棧，忽略其它元素*/
	{
		i=xz+move[v].x;
		j=yz+move[v].y;
		if ((picture[i][j]!=0) && (picture[i][j]!=-1))
		{
			top=Pushlstack(top,i,j);
			count++;
			picture[i][j]=-1;
		}
	}
	
	top=Poplstack(top,&k,&l);  /*出棧*/
	if (top!=NULL)	
		Data_chuli(k,l);
				
}

void End()
{
	printf("Chu li hou de Tu shi:\n");
	daying1();
	Restore();
	printf("There are %d jvdian in the picture.\n",total);
	printf("And the Xiangshu of the points are:\n");
	daying2(jvdian,1,total);

    Quicksort(jvdian,1,total);
	printf("After sort,the Xiangshu of the points are:\n");

    daying2(jvdian,1,total);
	printf("The average of the jvdian is:%-5.2f\n\n",average);

}

void daying1()  /*格式輸出二維圖表*/
{
	int i,j,k;
	
	for(i=1;i<=line;i++)
	{
		k=1;
		for(j=1;j<=row;j++)
		{
			printf("picture[%d][%d]=%3d  ",i,j,picture[i][j]);
			if (fmod(k,4)==0) printf("\n");
			k++;
		}
	    printf("\n\n");	
	}
}

void daying2(R,i,j)
int R[];
int i;
int j;
{
 int k;/*統計所有聚點的像素和*/

 k=0;
 for(i=1;i<=total;i++)
	{
	 k=k+R[i];
	 printf("jvdian[%d]=%3d  ",i,R[i]);
	 if (fmod(j,4)==0) printf("\n");
	 j++;
	}
 average=(float)k/(float)total;
 printf("\n");

}

void Restore()  /*恢復原始圖表，并輸出*/
{
	int i,j,k;

	for(i=1;i<=line;i++)
		for(j=1;j<=row;j++)
			if (picture[i][j]==-1) picture[i][j]=1;/*恢復原始圖表*/

	printf("Yuan shi Tu biao shi:\n");
	for(i=1;i<=line;i++)
	{
		k=1;
		for(j=1;j<=row;j++)
		{
			printf("%3d",picture[i][j]);
			if (fmod(k,row)==0) printf("\n");/*輸出原始圖表*/
			k++;
		}
	}
}

void Savefile()/*在外存中用文件的形式保存所有數據:原始圖表，聚點數組，平均像素*/
{
	FILE *fp;
	char filename[15];/*文件的名稱*/
	int i,j;

	printf("Please Enter one name for saving the data above.\n");
	scanf("%s",filename);
	if((fp=fopen(filename,"w"))==NULL)
	{
		printf("Cannot open this file\n");
		getch();
		exit(0);
	}

    fputs("\nYuan shi tu biao shi:\n",fp);
	for(i=1;i<=line;i++)
	{
		for(j=1;j<=row;j++)
			fprintf(fp,"%d ",picture[i][j]);
		fputs("\n",fp);
	}
	
	fputs("Ge jv dian de xiang su shi:\n",fp);
	for(i=1;i<=total;i++)
	{
		fprintf(fp,"jvdian[%d]=%d ",i,jvdian[i]);
        if (fmod(i,4)==0)
			fputs("\n",fp);
	}

	fputs("\n\nSuo you jvdian de ping jun xiang shu shi:",fp);
	fprintf(fp,"%-5.2f",average);

	fclose(fp);
	printf("Please input any key to end this program.\nBye bye.\n");
	getch();
}