Печатные края не соответствуют узлам

Question

У меня есть программа, которая читает файл с двумя столбцами чисел, сортирует их, создает три таблицы, одну только с узлами (индивидуально), одну со всеми ребрами и одну, в которой количество ребер для каждого узла. Проблема в том, что когда я пытаюсь распечатать края, он печатает их неправильно или говорит, что не может их найти. Через какой-то GDB я узнал, что первые массивы в порядке, но третий хранит кучу случайных чисел (или нулей) до конца. Любая помощь будет оценена. Файл выглядит следующим образом (начальный / конечный узел для каждого края):

7856    8192
7754    7005
7862    1982
7862    3293
7862    4037
7862    5210
7862    5605
7862    7860

Код выглядит следующим образом:

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



int mapcmp(const void *a,const void *b){
  return ( *(int*)a - *(int*)b );
}

int mapdoublesize(int** map,int nodes){
    int* new_array=malloc(nodes*2*sizeof(int));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }
    nodes*=2;
    for(int i=0;i<nodes;i++){
        new_array[i]=(*map)[i];
    }

    free(*map);
    *map=new_array;
    return nodes;
}

typedef struct {
    int start;
    int end;   
} path;

int cmp(const void *a,const void *b){
    int l=((path*)a)->start;
    int r=((path*)b)->start;

    if(l>r)
        return 1;
    if(l<r)
        return -1;
    if(l==r)
        return 0;
  }

int doublesize(path** array,int n){
    path* new_array=malloc(n*2*sizeof(path));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<n;i++){
        new_array[i]=(*array)[i];
    }
    free(*array);
    *array=new_array;
    n*=2;
    return n;

}


int main()
{
    int maxsize=10;
    int test;
    path* array=malloc(maxsize*sizeof(path));
    if(array==NULL) {
        printf("Error allocating memory\n");
        abort();
    }


    FILE* fd=fopen("Wiki-Vote.txt","r");
    if(fd==NULL) {
        printf("Error opening file\n");
        abort();
    }
    char buff[200];
    int counter=0;

    char c;
  while(fgets(buff,200,fd)) {

        c=buff[0];
        if(c=='#') {
            continue;
        }
    sscanf(buff,"%d%d",&array[counter].start,&array[counter].end);
        counter++;
        if(counter==maxsize){
           maxsize=doublesize(&array,maxsize); 
    }

    }
  int i;
  maxsize=counter;
    counter=0;
    qsort(&array[0],maxsize,sizeof(path),cmp);




  counter=0;
  int nodes=10;
  int* map=malloc(nodes*sizeof(int));
  if(map==NULL){
    printf("Error allocating memory\n");
    abort();
  }

for(i=0;i<maxsize;i++){
  if(map[counter-1]==array[i].start)
    continue;
        map[counter]=array[i].start;
        counter++;
        if(counter==nodes){
          nodes=mapdoublesize(&map,nodes);
        }
}
int j;
for(i=0;i<maxsize;i++){
  for(j=0;j<counter;j++){
    if(map[j]==array[i].end)
      break;
  }
  if(j!=counter)
    continue;
  map[counter]=array[i].end;
  counter++;
  if(counter==nodes)
    nodes=mapdoublesize(&map,nodes);
}

nodes=counter;
qsort(&map[0],nodes,sizeof(int),mapcmp);


  int* arraynodes=malloc(nodes*sizeof(int));
  int* arrayedges=malloc(maxsize*sizeof(int));
  if(arraynodes==NULL||arrayedges==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  counter=1;

  arraynodes[0]=0;
  for(i=0;i<maxsize;i++){
    arrayedges[i]=array[i].end;
    if(array[i].start!=array[i+1].start){
      arraynodes[counter]=i;
      counter++;
    }
  }


int x;
  printf("give number to search: "); 
  scanf("%d",&x);
  for(i=0;i<nodes;i++){
    if(x==map[i]){
      printf("found \n");
      break;
    }

  }
  if(i==nodes){
    printf("not found \n");
    abort();
  }

  for(j=arraynodes[i];j<arraynodes[i+1];j++){
    printf("%d\n",arrayedges[j]);
  }

  free(arraynodes);
  free(arrayedges);
  free(map);
    fclose(fd);
    free(array);
        return 0;
}

Answer 1

Основной ответ:

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

Вы перебирайте список ребер, и каждый раз, когда изменяется начальная точка, вы сохраняете текущее смещение в arraynodes Это ошибочно, потому что не все узлы являются отправной точкой ребра. Таким образом, если ваш список ребер имеет ребро от узла 5 -> 7, а затем ребро от 6 -> 7, вы зарегистрируете изменение начальной точки с 5 на 6, но вы сохраните текущее смещение в начале arraynodes и не для 5-го узла.

Чтобы исправить это, вместо этого сделайте следующее: Сохраните смещение в списке ребер, изначально равное нулю. Выполните итерацию по узлам, для каждого узла сохраните текущее смещение в arraynodes. Затем увеличивайте смещение до тех пор, пока начальная точка ребра при текущем смещении равна текущему узлу. Таким образом, arraynodes сообщит вам для каждого индекса узла, в каком индексе в списке ребер хранятся ребра, начинающиеся в этом узле.

  /**
   * Assumption: Edges are sorted by their starting point.
   */

  int edge_count = maxsize;
  int edge_offset = 0;

  /**
   * For each node:
   *
   * - Store current edge_offset in arraynodes
   * - Increment edge_offset as long as the start point
  *    of the edge at that offset matches the current node.
   */
  for (int i = 0; i < nodes; i++) {
    int current_node = map[i];
    arraynodes[i] = edge_offset;

    while (edge_offset < edge_count && array[edge_offset].start == current_node) {
      edge_offset++;
    }
  }

  /**
   * Copy end-points of edges to arrayedges.
   *
   * You don't really need this, you could also directly
   * access the end-points in your output loop ...
   */
  for (int i = 0; i < edge_count; i++) {
    arrayedges[i] = array[i].end;
  }

Проблемы безопасности памяти:

Есть несколько проблем с безопасностью памяти в вашем коде:

1. Переполнение буфера: при первом проходе l oop, counter равно нулю, поэтому map[counter-1] выходит за пределы.

  counter = 0;
  int nodes = 10;
  int *map = malloc(nodes * sizeof(int));
  if (map == NULL) {
    printf("Error allocating memory\n");
    abort();
  }

  for (i = 0; i < maxsize; i++) {
    if (map[counter - 1] == array[i].start)
      continue;

Переполнение буфера: при инициализации карты вы хотите удвоить ее размер при заполнении. Однако в mapdoublesize, когда вы копируете данные со старой карты на новую карту, вы перебираете всю новую карту, поэтому вторая половина этого l oop читает за пределами старой карты:

  nodes *= 2;
  for (int i = 0; i < nodes; i++) {
    new_array[i] = (*map)[i];
  }

Переполнение буфера: в последней итерации этого l oop: Доступ к array[i+1] выходит за пределы:

  for (i = 0; i < maxsize; i++) {
    arrayedges[i] = array[i].end;
    if (array[i].start != array[i + 1].start) {

Переполнение буфера: в ваших выходных данных l oop, если i является последним узлом, ваш доступ к arraynodes[i+1] выходит за пределы:

for (j = arraynodes[i]; j < arraynodes[i + 1]; j++) {

I не гарантирую, что я обнаружил все проблемы с безопасностью памяти. Вполне возможно, что еще. Я бы посоветовал вам улучшить структурирование и документирование вашей программы: разбейте вашу программу на более мелкие функции, которые выполняют один шаг, и документируйте предположения и предварительные условия этого шага (т.е. каковы границы массива, к которому вы обращаетесь?). Дайте имена переменных, которые четко описывают их назначение, не используйте переменные повторно. Это должно помочь вам обнаружить ошибки такого рода. Также я бы посоветовал вам использовать инструменты для проверки безопасности памяти. И G CC, и Clang имеют функцию ASAN, которая автоматически вставляет отладочный код в ваш двоичный файл, который будет обнаруживать и сообщать о проблемах безопасности памяти при запуске вашей программы. Вы можете включить это, скомпилировав с -fsanitize=address ( reference ). Другим инструментом с аналогичной областью применения будет Valgrind ( reference ). Эти программы, конечно, не могут найти все ошибки, так как они только динамически анализируют код, который фактически выполняется. Если в какой-то ветви вашей программы есть ошибка, которая не достигнута текущим исполнением, она не будет обнаружена. Таким образом, вы все еще не можете внимательно посмотреть на вашу программу.