fangdongheiha
Celia_D
采纳率100%
2020-03-21 17:38

C++:基于分治思想实现二维平面最近点对算法,n>3时程序崩溃

5
已采纳

感觉问题出在快速排序的两个函数上,麻烦各位大佬看一下哪里出了问题。

#include "stdafx.h"
#include <vector>
#include <math.h>
#include <time.h>
#include<algorithm>
#include <iostream>
using namespace std;

struct point//存储点坐标的结构体
{
    int index;
    float x,y;
};

void Same(int n,int k,point X[])//查找相同的坐标
{
    for(int i=0;i<n;i++)
    {
        if(X[k].x==X[i].x&&X[k].y==X[i].y)
        {
            X[k].x=(float)(rand()%10001);
            X[k].y=(float)(rand()%10001);
            Same(n,k,X);
        }
    }
}



void QuickSort1(point arr[], int left, int right)//快速排序
{
if (left<right)
    {   
        int i=left,j=right;
        point a; 
        a=arr[left];
        while (i<j)
        {
            while(i<j&&arr[j].x>=a.x) // 从右向左找第一个小于x的数
                j--; 
            if(i<j)
                arr[i++].x=arr[j].x;
            while(i<j&&arr[i].x<a.x) // 从左向右找第一个大于等于x的数
                i++; 
            if(i<j)
                arr[j--].x=arr[i].x;
        }
        arr[i].x=a.x;
        QuickSort1(arr,left,i-1); // 递归调用
        QuickSort1(arr,i+1,right);
    }

}

void QuickSort2(point arr[], int left, int right)//快速排序
{
if (left<right)
    {   
        int i=left,j=right;
        point a; 
        a=arr[left];
        while (i<j)
        {
            while(i<j&&arr[j].y>=a.y) // 从右向左找第一个小于x的数
                j--; 
            if(i<j)
                arr[i++].y=arr[j].y;
            while(i<j&&arr[i].y<a.y) // 从左向右找第一个大于等于x的数
                i++; 
            if(i<j)
                arr[j--].y=arr[i].y;
        }
        arr[i].y=a.y;
        QuickSort2(arr,left,i-1); // 递归调用
        QuickSort2(arr,i+1,right);
    }

}

float Distance(point a, point b)//求两点之间距离   !不能以distance命名,与函数模板重名,xutility文件会报错
{
    float x=a.x-b.x;
    float y=a.y-b.y;
    return sqrt(x*x+y*y);
}

void closest(point X[], point Y[],int low,int high,point &a,point &b,float &min)//求最近点对及其距离,设置ab的目的是输出最近点对的坐标
{
    int i,j,k,m;
    point al,bl,ar,br;
    float dl,dr;
    if((high-low)==1) // n=2直接计算两个点之间的距离
    {   
        a=X[low];
        b=X[high];
        min=Distance(X[low], X[high]);
    }
    else
    {  
        if((high-low)==2)  //    当n=3时直接计算
        {                        
            dl = Distance(X[low], X[low+1]);                       
            dr = Distance(X[low], X[low+2]);                      
            min = Distance(X[low+1], X[low+2]);                       
            if((dl<=dr)&&(dl<=min))
            {                    
                a = X[low], b = X[low+1], min = dl;              
            }
            else
            {
                if(dr<=min)
                {
                    a=X[low];
                    b=X[low+2]; 
                    min=dr;
                }
                else
                {
                    a=X[low+1];
                    b=X[low+2];             
                }                      
            }                
        }
        else //        当n>3时进行分治
        {                  
            point *SL = new point[(high-low)/2+1];             
            point *SR = new point[(high-low)/2];      
            m = (high-low)/2 + low;    //       把x数组以m为界划分为两半             
            j = k = 0;            
            for(i=0; i<=high-low; i++)
            {                       
                if(Y[i].index<=m)
                {                                
                    SL[j++] = Y[i];   //       收集左边子集中的最近点对                             
                }
                else
                {                      
                    SR[k++] = Y[i];   //       收集右边子集中的最近点对                           
                }                    
            }
                        closest(X,SL,low, m, al, bl, dl);       //     计算左边子集的最近点对
                        closest(X,SR,m+1, high, ar, br, dr);//  计算右边子集的最近点对
                        if(dl<dr)
                        {                              //    组合步得到左右子集中点的最短距离d
                                a = al, b = bl, min = dl;
                        }
                        else
                        {
                                a = ar, b = br, min = dr;
                        }
                        point *Z = new point[high-low+1];
                        k = 0;
                        for( i=0; i<=high -low; i++) // 收集距离中线距离小于d的元素,保存到数组Z(因Y数组按y坐标递增排序,Z数组也一样)
                        {       
                            if(fabs(X[m].x - Y[i].x)<min)//abs求整数绝对值
                            {  
                                Z[k].x = Y[i].x, Z[k++].y = Y[i].y;

                            }
                        }
                        for( i=0; i<k; i++)
                        {
                                for( j=i+1; (j<k)&&(Z[j].y-Z[i].y<min); j++){     //   若前后两点y轴的距离超过d则不可能使距离小于d,退出
                                        dl = Distance(Z[i], Z[j]);    //        计算前后两点的距离
                                        if(dl<min){                                   //     若小于min,则更新
                                                a = Z[i], b = Z[j], min = dl;
                                        }
                                }
                        }

                        delete SL;
                        delete SR;
                        delete Z;
                }
        }
}

void closest_pair(point X[], int n, point &a, point &b, float &min){
        if(n<2){        //      当点集个数小于2时不存在最近点对
                min= 0;
        }else{
               QuickSort1(X,0,n-1);      //        对x数组进行递增排序
               point *Y = new point[n];    //  初始化辅助点数组Y
                for( int i = 0 ; i < n ;i ++){
                        Y[i].index = i;
                        Y[i].x = X[i].x;
                        Y[i].y = X[i].y;
                }
                QuickSort2(Y,0,n-1);      //        对y数组进行递增排序
                closest(X,Y,0,n-1,a,b,min);              //     求亲密点对
                min = sqrt(min);                //  将得到的d开平方才是两点间真正的距离
                delete Y;
        }
}

void main()
{ 
    int n;
    cout<<"请输入点个数:"<<endl;
    cin>>n;
    point *X=new point[n];
     srand((int)time(0));
     for(int i=0;i<n;i++)
     {
         X[i].x=(float)(rand()%10001);
         X[i].y=(float)(rand()%10001);
     }
     //for(int j=0;j<n;j++)
      //  Same(n,j,X);
     point a,b;
     float min;
     closest_pair(X,n,a,b,min);
     if(n>=2)
     {
          printf("最近点对为:(%.0f,%.0f),(%.0f,%.0f) \n两点距离为:%.4f\n", a.x, a.y, b.x, b.y, min);
      }
     else{
                printf("不存在最近点对!\n");
        }

}


  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • weixin_39872903 weixin_anvirzh0612 1年前

    你好,是closest()函数point *SR 指针越界导致程序崩溃的。做如下修改可以解决程序崩溃问题
    point *SR = new point[(high - low) / 2]; 改为point *SR = new point[(high - low)+1]; OK

    点赞 1 评论 复制链接分享