qq_40267093
2018-01-26 06:06
采纳率: 100%
浏览 1.9k
已采纳

段错误,检查是否有数组越界,指针异常,访问到不应该访问的内存区域

题目:给定一组二维点,每个点对应一个字符。给定任意一个位置,输出距离其最近点与它的距离。

输入

第一行两个数:点的个数N以及查询的个数M

接下来N行,每行2个浮点数和一个字符,代表点的坐标以及其对应的字符

接下来M行,每行2个浮点数,代表希望查询的位置

输出

M行,每行为点集中距离查询位置最近的距离,精确到小数点后4位。

代码:
#include
#include
#include
#include
#include
using namespace std;
struct data
{
double x;
double y;
};

struct Tnode
{
struct data dom_elt;
int split;
struct Tnode * left;
struct Tnode * right;
};

double ave(double a[],int n)
{
int sum=0;
for (int i=0;i<n;i++)
sum+=a[i];
return sum/n;
}

double variance (double a[],int n)
{
double sum=0;
double average=ave(a,n);//函数调用!!不许有【】!!!不许有int和double !!
for (int i=0;i<n;i++)
sum=(a[i]-average)*(a[i]-average);
return sum/n;
}

bool cmp1(data a, data b){
return a.x < b.x;
}

bool cmp2(data a, data b){
return a.y < b.y;
}

bool equal(data a, data b){
if (a.x == b.x && a.y == b.y)
{
return true;
}
else{
return false;
}
}
void ChooseSplit(data exm_set[], int size, int &split, data &SplitChoice){
double tmp1,tmp2;
double v1,v2;
double flag1[size],flag2[size];
for(int i=0;i<size;i++){
flag1[i]=exm_set[i].x;
flag2[i]=exm_set[i].y;}
v1=variance(flag1,size);
v2=variance(flag2,size);
/*tmp1 = tmp2 = 0;
for (int i = 0; i < size; i++)
{
//while((double)size * exm_set[i].x * exm_set[i].x!=0&&(double)size * exm_set[i].x!=0)
tmp1 += 1.0 / (double)size * exm_set[i].x * exm_set[i].x;
tmp2 += 1.0 / (double)size * exm_set[i].x;

}
double v1 = tmp1 - tmp2 * tmp2;
tmp1 = tmp2 = 0;
for (int i = 0; i < size; i++)
{
    //while((double)size * exm_set[i].x * exm_set[i].x!=0&&(double)size * exm_set[i].x!=0){
    tmp1 += 1.0 / (double)size * exm_set[i].y * exm_set[i].y;
    tmp2 += 1.0 / (double)size * exm_set[i].y;
    ///}
}
double v2 = tmp1 - tmp2 * tmp2;*/
split = v1 > v2 ? 1:0;
if (split == 0)
{
    sort(exm_set,exm_set + size-1, cmp1);
}
else{
    sort(exm_set,exm_set + size-1, cmp2);
}
SplitChoice.x = exm_set[size / 2].x;
SplitChoice.y = exm_set[size / 2].y;

}

Tnode* build_kdtree(data exm_set[], int size, Tnode* T){
if (size == 0){
return NULL;
}
else{
int split;
data dom_elt;
ChooseSplit(exm_set, size, split, dom_elt);
data exm_set_right [100];
data exm_set_left [100];
int sizeleft ,sizeright;
sizeleft = sizeright = 0;
if (split == 0)
{
for (int i = 0; i < size; i++)
{
if (!equal(exm_set[i],dom_elt) && exm_set[i].x <= dom_elt.x)
{
exm_set_left[sizeleft].x = exm_set[i].x;
exm_set_left[sizeleft].y = exm_set[i].y;
sizeleft++;
}
else if (!equal(exm_set[i],dom_elt) && exm_set[i].x > dom_elt.x)
{
exm_set_right[sizeright].x = exm_set[i].x;
exm_set_right[sizeright].y = exm_set[i].y;
sizeright++;
}
}
}
else{
for (int i = 0; i < size; i++)
{

            if (!equal(exm_set[i],dom_elt) && exm_set[i].y <= dom_elt.y)
            {
                exm_set_left[sizeleft].x = exm_set[i].x;
                exm_set_left[sizeleft].y = exm_set[i].y;
                sizeleft++;
            }
            else if (!equal(exm_set[i],dom_elt) && exm_set[i].y > dom_elt.y)
            {
                exm_set_right[sizeright].x = exm_set[i].x;
                exm_set_right[sizeright].y = exm_set[i].y;
                sizeright++;
            }
        }
    }
    T = new Tnode;
    T->dom_elt.x = dom_elt.x;
    T->dom_elt.y = dom_elt.y;
    T->split = split;
    T->left = build_kdtree(exm_set_left, sizeleft, T->left);
    T->right = build_kdtree(exm_set_right, sizeright, T->right);
    return T;
}

}
double Distance(data a, data b){
double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return sqrt(tmp);
}
void searchNearest(Tnode * Kd, data target, data &nearestpoint, double & distance){
stack search_path;
Tnode* pSearch = Kd;
data nearest;
double dist;
while(pSearch != NULL)
{
search_path.push(pSearch);

    if (pSearch->split == 0)
    {
        if(target.x <= pSearch->dom_elt.x)
        {
            pSearch = pSearch->left;
        }
        else
        {
            pSearch = pSearch->right;
        }
    }
    else{
        if(target.y <= pSearch->dom_elt.y)
        {
            pSearch = pSearch->left;
        }
        else
        {
            pSearch = pSearch->right;
        }
    }
}
nearest.x = search_path.top()->dom_elt.x;
nearest.y = search_path.top()->dom_elt.y;
while(!search_path.empty()){search_path.pop();}
dist = Distance(nearest, target);
Tnode *pBack;
while(!search_path.empty())
{
    pBack = search_path.top();
    search_path.pop();
    if(pBack->left == NULL && pBack->right == NULL)
    {
        if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
        {
            nearest = pBack->dom_elt;
            dist = Distance(pBack->dom_elt, target);
        }
    }
    else
    {
        int s = pBack->split;
        if (s == 0)
        {
            if( fabs(pBack->dom_elt.x - target.x) < dist)
            {
                if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
                {
                    nearest = pBack->dom_elt;
                    dist = Distance(pBack->dom_elt, target);
                }
                if(target.x <= pBack->dom_elt.x)
                    pSearch = pBack->right;
                else
                    pSearch = pBack->left;
                if(pSearch != NULL)
                    search_path.push(pSearch);
            }
        }
        else {
            if( fabs(pBack->dom_elt.y - target.y) < dist)
            {
                if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
                {
                    nearest = pBack->dom_elt;
                    dist = Distance(pBack->dom_elt, target);
                }
                if(target.y <= pBack->dom_elt.y)
                    pSearch = pBack->right;
                else
                    pSearch = pBack->left;
                if(pSearch != NULL)
                    search_path.push(pSearch);
            }
        }
    }
}
nearestpoint.x = nearest.x;
nearestpoint.y = nearest.y;
distance = dist;

}
int main(){
double x,y;
int m,n;
cin>>m>>n;
data exm_set[m];
char pos[m];
for(int i=0;i {
cin>>x>>y;
cin>>pos[i];
exm_set[i].x = x;
exm_set[i].y = y;
}
struct Tnode *root = NULL;
root = build_kdtree(exm_set, m, root);

data nearestpoint;
double distance;
data target;
for(int j=0;j<n;j++)
{
    double xx,yy;
    cin>>xx>>yy;
    target.x=xx;
    target.y=yy;
    searchNearest(root, target, nearestpoint, distance);
    printf("%.4f\n", distance);
}

}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题