C语言用结构体的思路求最接近点对

柔光的暖阳◎ 2023-05-28 09:54 4阅读 0赞

## 问题描述: ##

**给定平面上n个点，找其中的一对点，使得在n个点组成的所有点  
对中，该点对间的距离最小。**

## 问题分析： ##

要求平面内的点对，我们首先来看看**一维**的情况：  
![在这里插入图片描述][20200326115928355.png]  
对于图中的两点，它们的距离为：

> D=x2-x1

当点数大于2时，也只需求出相邻两个点间的距离，取最小的即可。  
再来看看二维的情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzAwNjkz_size_16_color_FFFFFF_t_70]  
对于二维图中，同样可以由公式写出两点之间的距离：（只写出了D1）

> D1= ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \\sqrt\{(x1-x2)^2+(y1-y2)^2\} (x1−x2)2\+(y1−y2)2

当点数多的时候也是求出两两之间的距离，取最小值即可：  
**以同样的道理也可以托展出三维的情况。**

## 代码实现： ##

##### 定义结构体：（包含点的属性） #####

struct Point{ 
    	double x;
    	double y;
    }point[MAX];// #define MAX 10
    //定义了一个结构体数组，名字point，定义了最大10个点，可以任意修改

##### 查找函数：（根据上述分析写出关键代码） #####

void FoundNearestPoints(Point P[],int n)//传入保存所有点的数组和点个数
    { 
    	float Dmin=100000; //定义一个足够大的数，后续更新最小值
    	float D=0;   //定义一个保存现阶段两点间距离的平方的变量
    	int a=0,b=0;
    	for(int i=0;i<n-1;i++) //纯C环境不能这样写，会报错
    	{ 
    		for(int j=i+1;j<n;j++)
    		{ 
    			D=(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y);
    			//注意：这里是两点间距离的平方
    			if(D<Dmin)
    			{ 
    				Dmin=D;  //更新最小距离
    				//保存最短距离点对的下标
    				a=i;  
    				b=j;
    			}
    		}
    	}
    	printf("最近的点对为：(%0.lf,%0.lf)与(%0.lf,%0.lf)\n",P[a].x,P[a].y,P[b].x,P[b].y);
    	printf("最短距离为：%f\n",sqrt((double)Dmin)); //最终化最短距离
    }

##### 主函数：（创建关于点的数组并且调用查找函数） #####

void main()
    { 
    	int num; //定义一个全局变量，用来保存点的个数
    	//用 do--while 来规范输入
    	do
    	{ 
    	printf("请输入点的个数：(位于2到10之间)\n");
    	scanf("%d",&num);
    	}
    	while(num<2||num>MAX);
    	printf("请输入每个点的x、y值\n");
    		for(int i=0;i<num;i++)
    		{ 
    			printf("请输入第%d个值：\n",i+1);
    			scanf("%lf%lf",&point[i].x,&point[i].y);
    		}
    	FoundNearestPoints(point,num);
    }

## 最后：（附上三维情况下的源码） ##

#include<stdio.h>
    #include<math.h>
    #define MAX 10
    struct Point{ 
    	double x;
    	double y;
    	double z;
    }point[MAX];  //定义了一个结构体数组，名字point，定义了最大10个点，可以任意修改
    
    void  FoundNearestPoints(Point P[],int n); 
    
    void main()
    { 
    	int num;
    	do
    	{ 
    	printf("请输入点的个数：(位于2到10之间)\n");
    	scanf("%d",&num);
    	}
    	while(num<2||num>MAX);
    	printf("请输入每个点的x,y,z的值\n");
    		for(int i=0;i<num;i++)
    		{ 
    			printf("请输入第%d个值：\n",i+1);
    			scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z);
    		}
    	FoundNearestPoints(point,num);
    }
    void FoundNearestPoints(Point P[],int n)
    { 
    	float Dmin=100000; //定义一个足够大的数，后续更新最小值
    	float D=0;   //定义一个保存现阶段两点间距离的平方的变量
    	int a=0,b=0;
    	for(int i=0;i<n-1;i++)//纯C环境不能这样写，会报错
    	{ 
    		for(int j=i+1;j<n;j++)
    		{ 
    			D=(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y)+(P[i].z-P[j].z)*(P[i].z-P[j].z);//求解两点间距离的平方
    			if(D<Dmin)
    			{ 
    				Dmin=D;  //更新最小距离
    				//保存最短距离点对的下标
    				a=i;  
    				b=j;
    			}
    		}
    	}
    	printf("最近的点对为：(%0.lf,%0.lf,%0.lf)与(%0.lf,%0.lf,%0.lf)\n",P[a].x,P[a].y,P[a].z,P[b].x,P[b].y,P[b].z);
    	printf("最短距离为：%f\n",sqrt((double)Dmin)); //最终化最短距离
    }

[20200326115928355.png]: /images/20230528/4a59725d737d4be780bdfecae1c4d1f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzAwNjkz_size_16_color_FFFFFF_t_70]: /images/20230528/1bd7baf8a33849d998c831440e427203.png