删除多维结构的行

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

最近的点是代表第 1 行和第 3 行的点，应从结构中删除它们。

输出应为：(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;
}

结构对我来说是新的，多维数组更难。你能帮我完成这个任务吗？

input/output

的更多示例

注意：不允许使用辅助数组

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)

更新：

thank you very much, could you just modify without typedef? – 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 的评论中简要提到了 [取自您的 linked 数据示例]，但目前的代码无法处理完全重复的点太好。所有维度的所有点的数据都相同除了最后一个：

目前，如果我们有两个 相同的 点，这些点将被删除（即它们的距离为 0.0）。因此，我们将删除 1 和 1.00
这与您的第二个示例相反，其中删除了 1.1 和 1.00 点。
即使我们 excluded/ignored 点相同，匹配的也将是 1.00 的 第一个 副本。也就是说，1 点和 1.1 点将被删除。
我只是通过删除输入数据中相同的点之一来对此进行了一些尝试。

考虑以上因素后：

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

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

删除多维结构的行

Remove rows of multidimensional structures

c

arrays

structure

multidimensional-array