Как я могу отсортировать массив, который зависит от другого, с помощью qsort? - PullRequest
Новая
       19

Как я могу отсортировать массив, который зависит от другого, с помощью qsort?

0 голосов
/ 18 апреля 2019

Пример: 

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;
}

1 Ответ

1 голос
/ 18 апреля 2019

Насколько я понимаю, вы намерены сохранить массив degree в его нынешнем порядке.Если вы хотите выполнить совместную сортировку с массивом вершин, вам нужно написать собственную процедуру сортировки;qsort не будет выполнять эту работу.

Конечно, если вы не выполняете совместную сортировку degree, тогда должно быть четко определенное отображение 1-1 из значений из vertex элементов к индексам из degree элементов, иначе нет способа определить, какая степень соответствует какой вершине после начала сортировки.Это похоже на случай с вашим примером: значения вершин на единицу больше, чем индексы соответствующих им элементов degree.

Чтобы отсортировать массив vertex по degree без изменения 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.

...