fina_ver.c

用迷宫算法实现聚点的统计

#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();
}