c - 如何修复qsort覆盖值，为什么会这样？

当我在C中运行qsort（）时，它会更改一些值。
例如，我必须按左列的升序对数组进行排序：

初始vecinos数组：

1 ------ 2

2 ------ 1

2 ------ 4

4 ------ 2

2 ------ 3

3 ------ 2

3 ------ 4

4 ------ 3

预期的vecinos数组：

1 ------ 2

2 ------ 1

2 ------ 4

2 ------ 3

3 ------ 2

3 ------ 4

4 ------ 2

4 ------ 3

我的代码的结果是：

1 ------ 2

1 ------ 1

2 ------ 4

2 ------ 2

2 ------ 3

3 ------ 2

3 ------ 4

3 ------ 3

4 ------ 3

typedef unsigned int u32;


int compare( const void* a , const void* b )
{
    const u32 ai = *( const u32* )a;
    const u32 bi = *( const u32* )b;

    if( ai < bi )
    {
        return -1;
    }
    else if( ai > bi )
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

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};
  while(true) //module to ignore comments
  {
    prev = (char)c;
    c = fgetc(stdin);
    if((char)c == 'p' && (prev == '\n' || prev == '\r') )
    {
      break;
    }
  }
  if (scanf("%s" "%u" "%u",edge, &n, &m))// %s\n breaks my inputs
      printf("Total vertices: %u. Total aristas %u\n", n, m);
  G->m = m;
  G->vecinos = (u32**)malloc(sizeof(u32*) * 2);
  for (u32 i = 0; i < 2; ++i)
  {
    G->vecinos[i] = (u32*)malloc(sizeof(u32)*2*m);
  }
  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[0][i] = v;
    G->vecinos[1][i] = w;
    G->vecinos[0][i+1] = w;
    G->vecinos[1][i+1] = v;
  }

  qsort(G->vecinos[0], 2*m, sizeof(u32), compare);
  return G;
}

最佳答案

在介绍问题时，您似乎将数据表征为2*m对的数组，但实际上它们似乎是由2*m不相关元素的一对数组构成的。也就是说，图形的有向边i用G->vecinos[0][i]和G->vecinos[1][i]表示（还有另一个有向边在相反的方向），但是这两个元素在内存中并不相邻。他们甚至可能彼此不靠近。

可以对边缘的表示进行排序，但不能使用qsort进行排序。您需要编写自己的排序例程，以对单独的数组G->vecinos[0]和G->vecinos[1]进行共同排序。

如果是我，我将重组数据，交换尺寸。此外，我将为单个分配构造它-真正的动态分配2D数组，而不是指针数组。看起来像这样：

// Structure definition
typedef struct some_key {
    // ...
    u32 (*vecinos)[2];  // a pointer to a 2-element array (the first of an array of such)
    // ...
} Grafostv;

Grafostv* ConstruccionDelGrafo() {
    Grafostv* G = (Grafostv*) malloc(sizeof(Grafostv));

    // ... vecinos allocation
    G->vecinos = malloc(2 * m * sizeof(*G->vecinos));  // just the one malloc() call

    // ... vecinos assignments:
    for (u32 i = 0; i < 2*m; i += 2) {
        // ...
        // note the inversion of index order:
        G->vecinos[i][0] = v;
        G->vecinos[i][1] = w;
        G->vecinos[i+1][0] = w;
        G->vecinos[i+1][1] = v;
    }

    // ... and that allows easier sorting, because each distinct logical unit
    // (two u32 objects describing a directed graph edge) is stored as a single
    // contiguous unit (a two-element array).
    qsort(G->vecinos, 2 * m, sizeof(*G->vecinos), vecino_comp);
}

// ... where vecino_comp() looks like this:
int vecino_comp(const void *v1, const void *v2) {
    const u32 (*vecino1)[2] = v1;
    const u32 (*vecino2)[2] = v2;

    if ((*vecino1)[0] < (*vecino2)[0]) {
        return -1;
    } else if ((*vecino1)[0] > (*vecino2)[0]) {
        return 1;
    } else if ((*vecino1)[1] < (*vecino2)[1]) {
        return -1;
    } else if ((*vecino1)[1] > (*vecino2)[1]) {
        return 1;
    } else {
        return 0;
    }
}

贯穿示例的关键概念是指向数组的指针。这是多维数组会衰减到的指针类型，它与双指针完全不同且很重要。现在，这与边缘数组的抽象概念是一致的，因为顶级数组的元素确实确实每个都对应一个（有向）边缘。