如何使用 qsort 对依赖于另一个的数组进行排序？

Question

示例：

degree =  [2,3,3,2,2,2]

vertex =  [1,2,3,4,5,6]

顶点 1 的度数为 2，顶点 2 的度数为 3，依此类推...

我需要这个解决方案 vertex = [2,3,4,5,6,1]。我想使用度值更改顶点。（最后 4 个数字的顺序无关紧要（具有相同的度数。

我有更多的代码，但我认为有了这个就没问题了。

谢谢！

typedef struct {
    u32 Orden;
    u32 Grado;
} ParGradoOrden;

int comGrado (const void * a, const void * b) {
    const u32 x = ((ParGradoOrden *) a)->Grado;
    const u32 y = ((ParGradoOrden *) b)->Grado;
    const u32 xx = ((ParGradoOrden *) a)->Orden;
    const u32 yy = ((ParGradoOrden *) b)->Orden;

    if (x < y)
        return 1;
    else if (x > y)
        return -1;

    if (xx < yy)
        return -1;
    else if (xx > yy)
        return 1;

    return 0;
}

qsort(G->vertices, n, sizeof(ParGradoOrden), comGrado);

Grafostv* ConstruccionDelGrafo()
{
    Grafostv* G = (Grafostv*)malloc(sizeof(Grafostv));
    u32 n = 0; //number of vertexs
    u32 m = 0; //number of edges
    u32 v = 0; //vertex name
    u32 w = 0; // vertex name
    int c = 0; //auxiliar char needed for fgetc function
    char prev = 'a';
    char edge[50] = {0};

    G->m = m;
    G->n = n;
    G->orden = (u32*)malloc(sizeof(u32) * n);
    G->grados = (u32*)malloc(sizeof(u32) * n);
    G->vertices = (u32*)malloc(sizeof(u32*) * n);

    for (u32 i = 0; i < 2*m; ++i)
        G->vecinos[i] = (u32*)malloc(sizeof(u32)*2);

    for (u32 i = 0; i < 2*m; i += 2)
    { 
        if(scanf(" %c %u %u",&prev, &v, &w) != 3 || prev != 'e')
        {
            free(G->color);
            free(G->orden);
            free(G->grados);
            return NULL;
        }
            G->vecinos[i][0] = v;
            G->vecinos[i][1] = w;
            G->vecinos[i+1][0] = w;
            G->vecinos[i+1][1] = v;
    } 
    qsort(G->vecinos, 2*m, 2*sizeof(u32), compare);
    G->vertices[0] = G->vecinos[0][0];
    copiarAVertice(G->vertices,G->vecinos,G->grados, G->indEnVecinos, 2*m);
    memset(G->visitados,0,n*sizeof(u32));
    memcpy(G->orden,G->vertices,n*sizeof(u32)); 
    G->max = Greedy(G);
    printf("terminé Greedy\n");
    return G;
}

Answer 1

我认为您希望 degree 数组保持其当前顺序。如果你想将它与顶点数组一起排序，那么你需要编写自己的排序例程； qsort 不会做那个工作。

当然，如果您不对 degree 进行协同排序，那么必须从值中定义明确的 1-1 映射14=] 元素添加到 degree 元素的 indices，否则无法确定排序开始后哪个顶点的度数。您的示例似乎就是这种情况，顶点值比其对应的 degree 元素的索引大 1。

要根据 degree 对 vertex 数组进行排序，而不修改 degree，提交给 qsort 的比较函数必须能够访问 degree 通过文件范围变量。如果 degree 本身没有在文件范围内声明，那么您可以添加一个文件范围指针变量并将其设置为指向 degree。当然，这有一个限制，你不能同时执行多个排序。

设置完毕后，比较函数使用顶点编号从数组中访问顶点度数，并根据这些结果进行比较。那看起来像这样：

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

typedef unsigned int u32;

u32 *vert_degree;

int compare_vertices(const void *v1, const void *v2) {
    u32 degree1 = vert_degree[*(const u32 *)v1 - 1];
    u32 degree2 = vert_degree[*(const u32 *)v2 - 1];
    if (degree1 > degree2) {
        return -1;
    } else if (degree1 < degree2) {
        return 1;
    } else {
        return 0;
    }
}

int main(void) {
    u32 degree[] = {2,3,3,2,2,2};
    u32 vertex[] = {1,2,3,4,5,6};

    vert_degree = degree;
    qsort(vertex, 6, sizeof(vertex[0]), compare_vertices);

    printf("%d", vertex[0]);
    for (int i = 1; i < 6; i++) {
        printf(", %d", vertex[i]);
    }
    putchar('\n');
    return 0;
}

输出：

2, 3, 1, 4, 5, 6

如果您恰好在基于 glibc 的系统上（即 Linux），那么您还可以选择使用 qsort_r，它接受辅助数据，例如 degree 数组，并将其传递给比较函数（因此必须接受一个附加参数）。这使您可以避免依赖全局变量，但它特定于 glibc。

如何使用 qsort 对依赖于另一个的数组进行排序？

How can I sort an array that depends on another, with qsort?

c

arrays

sorting

qsort