{
int i,j; //分别表示中线左边，右边的点 double d=sqrt(cnode.space); i=mid;
while(i>=0&&L.data[i].x>=(midX-d)) //在左边的d区域内 { j=mid;
while(L.data[++j].x<=(midX+d)&&j<=L.count) //在右边的d区域内 {
if(L.data[j].y<(L.data[i].y-d)||L.data[j].y>(L.data[i].y+d))//判断
纵坐标是否在左边某固定点的2d区域内
continue;
double space = square(L.data[i],L.data[j]);
if(cnode.space>space) //在满足条件的区域内依次判断
{
cnode.a=L.data[i]; cnode.b=L.data[j]; cnode.space=space; } --i; } }
//分治法求最近对
void DivideConquer(const List &L,CloseNode &closenode,int begin,int end)
{
if(begin!=end) {
int mid = (begin+end)/2; //排列后的中间的那个点 double midX = L.data[mid].x;
15
}
DivideConquer(L,closenode,begin,mid); //继续在左半边用分治法求最近对 DivideConquer(L,closenode,mid+1,end); //继续在右半边用分治法求最近对middle(L,closenode,mid,midX); //判断左右各距中线d的区域，是否有最近对
} }
void main() { //初始化 List list;int i,j; CloseNode closenode;
closenode.space = 10000; //最近点的距离 create(list); //输入各点到NList中 printf(\各点坐标为:\\n\ for( i=0;i printf(\ printf(\ } printf(\用分治法求最近对)\\n\\n\ paixu(list); printf(\经过以x轴为基值从小到大排序后的各点:\\n\ for( j=0;j printf(\ printf(\ } DivideConquer(list,closenode,0,list.count-1); { printf(\最近点对为: (%.0lf ,%.0lf),(%.0lf,%.0lf)\node.b.y); printf(\ 16 } printf(\最近距离为: %lf\\n\\n\\t\} 4 实验结果分析 4.1 快速排序问题运行结果及分析 从键盘输入给定的一个无序序列，快速的重新排列成一个有序序列。输出这个排列后的有序序列，每个值之间用空格隔开。 运行结果如图4.1 例一：给定10个无序正整数，38，27，55，50，13，49，65，40，78，100。 图4.1 (a) 例一快速排序结果 17 例二：给定10个无序负整数，－12，－31，－46，－30，－58，－90，－43，－28，－7，－20。 图4.1 (b) 例二快速排序结果 例三：给定10个无序正负混合整数，－24，46，19，31，－17，－10，59，63，－11，72。 图4.1 (c) 例三快速排序结果 图4.1各种不同情况的快速排序结果 18 4.2 棋盘覆盖问题运行结果及分析 从键盘输入棋盘的规模大小K，并输入特殊方格（特殊方格用数组下标表示）。输出2×2的棋盘，并用数字显示各L型骨牌，特殊方格用数字0表示。由键盘提示：棋盘数学显示。 运行结果如图4.2 图4.2 (a) 规模k为1的棋盘显示 k k 图4.2 (b) 规模k为2的棋盘显示 19
分治法开放性实验报告-正文
