如何修复qsort覆盖值，以及为什么会发生这种情况？

Question

当我在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;
}

Answer 1

在您对问题的呈现中，您似乎将数据表征为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;
    }
}

通过示例普遍存在的关键概念是指向数组的指针。这是多维数组衰减的指针类型，并且它与双指针完全且重要的不同。现在，这与边缘数组的抽象概念一致，因为顶层数组的元素确实每个都对应于一个（有向）边。