删除多维结构行

Question

我需要删除表示多维结构点的行，它们彼此最接近。

例如，如果结构是：

struct Point dot[100] = {
    {{1, 1, 1, 1}},
    {{2, 2, 2, 2}},
    {{1.3, 1.3, 1.3, 1.3}}
};

在应用欧氏距离公式后，距离为：

D12=sqrt(1-2)^2+(1-2)^2+(1-2)^2+(1-2)^2)=2

d13=sqrt((1-1.3)^2+(1-1.3)^2+(1-1.3)^2+(1-1.3)^2)=0.6

D23=sqrt(2-3)^2+(2-3)^2+(2-3)^2+(2-3)^2)=2

最近的点代表row1和row3，它们应该从结构中删除。

输出应该是：(2,2,2,2)

#include <stdio.h>
struct Point {
    double coordinate[100];
};
void remove_closest(struct Point dot[], int n, int dimension){
int i,j;
for(i=0;i<n;i++){
    for(j=0;j<dimension-1;j++){
      // 
    }
}
}
int main() {
struct Point dot[100] = {
    {{1, 1, 1, 1}},
    {{2, 2, 2, 2}},
    {{1.3, 1.3, 1.3, 1.3}}
};
 int i,j,dimension=4;
 remove_closest(dot, 3, dimension);

 for (i=0; i<3; i++) {
    printf("(");
    for (j=0; j<dimension-1; j++)
        printf("%g,", dot[i].coordinate[j]);
    printf("%g)\n", dot[i].coordinate[dimension-1]);
}
    return 0;
}

结构对我来说是新的，多维数组使它更加困难。你能帮我做这件事吗？

更多的输入/输出示例

• 注意:不允许使用辅助数组。

Answer 1

好吧，根据所有的标准，我会这么做。我把这段代码概括了一下。我重命名了几个变量，以便更具描述性。对该守则作了注释：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// number of elements in an array
#define COUNTOF(_arr)           (sizeof(_arr) / sizeof(_arr[0]))

// maximum number of dimensions -- adjust to suit
#define MAXDIM      4

struct point {
    double coordinate[MAXDIM];
};

// prtpoint -- print single point
void
prtpoint(const struct point *ptcur,int ndim)
{
    int sep = '(';

    for (int idxdim = 0; idxdim < ndim;  ++idxdim) {
        printf("%c%g",sep,ptcur->coordinate[idxdim]);
        sep = ',';
    }

    printf(")\n");
}

// prtlist -- print all points
void
prtlist(const struct point *points,int npoint,int ndim,const char *title)
{

    if (title != NULL)
        printf("%s: %d\n",title,npoint);

    for (int idxdot = 0;  idxdot < npoint;  ++idxdot)
        prtpoint(&points[idxdot],ndim);
}

double
square(double x)
{

    return x * x;
}

double
euclidean_distance(const struct point *points,int ndim,int idxlo,int idxhi)
{
    double dist = 0.0;
    const struct point *ptlo = &points[idxlo];
    const struct point *pthi = &points[idxhi];

    // sum of the squares of all the dimensions
    for (int idxdim = 0;  idxdim < ndim;  ++idxdim)
        dist += square(ptlo->coordinate[idxdim] - pthi->coordinate[idxdim]);

    dist = sqrt(dist);

    return dist;
}

// remove_closest -- remove closest points
int
remove_closest(struct point *points, int npoint, int ndim)
{
    int minlo = -1;
    int minhi = -1;
    double mindist = 0.0;

    // find the indexes of the two points that have the minimum distance
    for (int idxlo = 0;  idxlo < (npoint - 1);  ++idxlo) {
        for (int idxhi = idxlo + 1;  idxhi < npoint;  ++idxhi) {
            double curdist = euclidean_distance(points,ndim,idxlo,idxhi);

            // (1) grab the first distance we calculate as the minimum
            // (2) get the "best" minimum
            if ((minlo < 0) || (curdist < mindist)) {
                minlo = idxlo;
                minhi = idxhi;
                mindist = curdist;
                continue;
            }
        }
    }

    // strip the two closest entries
    struct point *ptsrc = points;
    struct point *ptdst = points;
    for (int idxcur = 0;  idxcur < npoint;  ++idxcur, ++ptsrc) {
        // skip either of the two lowest points
        if ((idxcur == minlo) || (idxcur == minhi)) {
#ifdef DEBUG
            printf("REMOVE: %d ",idxcur);
            prtpoint(ptsrc,ndim);
#endif
            continue;
        }

        // copy the point to fill the gap
        // NOTE: we _could_ just _always_ do the copy but doing this
        // conditionally is a speedup (i.e. avoid unnecessary copies)
        if (ptdst != ptsrc)
            *ptdst = *ptsrc;

        ++ptdst;
    }

    npoint -= 2;

    return npoint;
}

void
dolist(struct point *points,int npoint,int ndim)
{

    // should never happen [because if we get here, the compiler _should_
    // have complained in the definition of the array we've been passed]
    if (ndim > MAXDIM)
        exit(9);

    prtlist(points,npoint,ndim,"Before");
    npoint = remove_closest(points,npoint,ndim);
    prtlist(points,npoint,ndim,"After");
}

void
test01(void)
{
    struct point points[] = {
        {{1, 1, 1, 1}},
        {{2, 2, 2, 2}},
        {{1.3, 1.3, 1.3, 1.3}}
    };

    dolist(points,COUNTOF(points),4);
}

void
test02(void)
{
    struct point points[] = {
        // NOTE: duplicate points aren't handled the way this example implies
#if 0
        {{1, 1, 1, 1}},
#endif
        {{1, 1, 1, 1.00}},
        {{1, 1, 1, 1.2}},
        {{1, 1, 1, 1.145}},
        {{1, 1, 1, 1.31}},
        {{1, 1, 1, 1.1}},
    };

    dolist(points,COUNTOF(points),4);
}

int
main(void)
{

    test01();
    test02();

    return 0;
}

在用-DDEBUG编译之后，下面是程序输出：

Before: 3
(1,1,1,1)
(2,2,2,2)
(1.3,1.3,1.3,1.3)
REMOVE: 0 (1,1,1,1)
REMOVE: 2 (1.3,1.3,1.3,1.3)
After: 1
(2,2,2,2)
Before: 5
(1,1,1,1)
(1,1,1,1.2)
(1,1,1,1.145)
(1,1,1,1.31)
(1,1,1,1.1)
REMOVE: 2 (1,1,1,1.145)
REMOVE: 4 (1,1,1,1.1)
After: 3
(1,1,1,1)
(1,1,1,1.2)
(1,1,1,1.31)

更新：

非常感谢你，你能不能修改一下不带ty胡枝子？- devec

好吧，如果你真的愿意的话-)

原文是：

typedef struct point {
    double coordinate[MAXDIM];
} point_t;

请注意，如果我想成为一条“聪明的裤子”，我可以用#define来完成这一任务，并且仍然满足要求;-)：

struct point {
    double coordinate[MAXDIM];
};
#define point_t struct point

但是，我已经编辑了上面的代码，只使用了普通的struct。我所做的只是做了简单的struct定义。然后，在全球范围内将所有point_t转换为struct point。所以，真的不太难。(例如)更改：

double
euclidean_distance(const point_t *points,int ndim,int idxlo,int idxhi)

转入：

double
euclidean_distance(const struct point *points,int ndim,int idxlo,int idxhi)

更新2：

虽然我简要介绍了从链接数据示例中提取的test02注释，但目前的代码没有很好地处理精确的重复点。除了最后一个维度外，所有维度的所有点的数据都是相同的：

1
1.1
1.00
1.2
1.145
1.31

1. 现在，如果我们有两个相同的点，这就是要移除的点(即它们的距离是0.0)。所以，我们要去掉1和1.00
2. 这与删除1.1和1.00点的第二个示例相反。
3. 即使我们排除/忽略了相同的点，它也将是匹配的1.00的第一个副本。也就是说，将删除1点和1.1点。
4. 我只是删除了输入数据中一个相同的点，从而对此做了一点解释。

在考虑了上述情况后：

1. 在您的示例中，您删除的两个点是1.1和1.00。距离是：0.1
2. 但是，我的代码删除了1.1和1.145。距离是：0.045

所以，我认为你的例子是不正确的，你删除了错误的点。你可能得决定这是否与你有关。