Как исправить значения перезаписи qsort и почему это происходит? - PullRequest
Новая
       23

Как исправить значения перезаписи qsort и почему это происходит?

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

Когда я запускаю qsort () в C, он меняет некоторые значения.Например, мне нужно отсортировать этот массив по возрастанию в левом столбце:

исходный массив 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;
}

1 Ответ

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

Представляя проблему, вы, похоже, характеризуете свои данные как массив пар 2*m, но на самом деле они, по-видимому, структурированы как пара массивов 2*m несвязанных элементов. То есть направленный край i вашего графа представлен G->vecinos[0][i] и G->vecinos[1][i] (и есть другой направленный край, идущий в противоположном направлении), но эти два элемента не являются смежными в памяти. Они могут даже не быть рядом друг с другом.

Можно отсортировать это представление ребер, но не с помощью qsort. Вам нужно написать свою собственную процедуру сортировки, которая объединяет отдельные массивы G->vecinos[0] и G->vecinos[1].

Если бы это был я, я бы реструктурировал данные, поменяв местами измерения. Кроме того, я бы структурировал его для одного выделения - истинного динамически размещаемого двумерного массива, а не массива указателей. Это будет выглядеть примерно так: 

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

Ключевым понятием здесь, распространяющимся через пример, является указатель на массив. Таков тип указателя, к которому распадается многомерный массив, и он полностью и важно отличается от двойного указателя. Теперь это соответствует абстрактной идее массива ребер, потому что элементы массива верхнего уровня действительно соответствуют одному (направленному) ребру.

...