Segfault с сортировкой слиянием в связанном списке - PullRequest
Новая
       53

Segfault с сортировкой слиянием в связанном списке

0 голосов
/ 26 января 2019

Моя цель с этим кодом состоит в том, чтобы с помощью огромного связанного списка отсортировать его по данным «count», а в случае связи - по данным «name».

Вот сортировка слияниемАлгоритм, который я реализую: 

void split(struct nlist* source, struct nlist** front, struct nlist** back) {
   struct nlist* fast;
   struct nlist* slow;

   if (source == NULL || source->next == NULL) {
      *front = source;
      *back = NULL;
      return;      
   }

   slow = source;
   fast = source->next;

   while (fast != NULL) {
      fast = fast->next;
      if (fast != NULL) {
         slow = slow->next;
         fast = fast->next;
      }
   }

   *front = source;
   *back = slow->next;
   slow->next = NULL;
}

struct nlist* SortedMerge(struct nlist* a, struct nlist* b) {
   struct nlist* result = NULL;

   if (a == NULL)
      return(b);
   else if (b == NULL)
      return(a);

   if (a->count > b->count) {
      result = a;
      result->next = SortedMerge(a->next, b);
   }

   else if (a->count == b->count) {
      if (strcmp(a->name, b->name) > 0) {
         result = a;
         result->next = SortedMerge(a->next, b);
      }
      else {
         result = b;
         result->next = SortedMerge(a, b->next);
      }
   }

   else {
      result = b;
      result->next = SortedMerge(a, b->next);
   }

   return(result);
}

void mergesort(struct nlist **start) {
   struct nlist* head = *start;
   struct nlist* a;
   struct nlist* b;

   if ((head == NULL) || (head->next == NULL)) {
      return;
   }

   split(head, &a, &b);

   mergesort(&a);
   mergesort(&b);

   *start = SortedMerge(a, b);
}

Где я вызываю mergesort в начале моего списка.

Структура nlist содержит три вещи: число int, имя char * иstruct nlist * next.

В этом коде обычно нет проблем, но при тестировании на крайние случаи, пропуская этот код по всему словарю, я получаю ошибку segfault при сортировке списка.Это не проблема с размером списка, потому что, когда я пропускаю сортировку и просто возвращаю список несортированным, проблем не возникает.

При запуске через gdb я вижу, что в segfaultSortedMerge, особенно при проверке a-> count или b-> count.Я получаю сообщение об ошибке:

(a = переменная чтения ошибок: невозможно получить доступ к памяти по адресу 0x7fffff7fefe8, b = переменная чтения ошибок: невозможно получить доступ к памяти по адресу 0x7fffff7fefe0)

Любые идеи о том, что может быть причиной этого?

1 Ответ

0 голосов
/ 26 января 2019

То, что происходит, - это то, что ваш код повторяется слишком глубоко, и ваш стек работает в вашей куче. Чтобы избежать этого, нужно либо ограничить количество узлов в списке, либо переписать ваш код не рекурсивно.

...