Связанный список и (буквенный) сортировка пузырьков

Question

У меня проблема с сортировкой пузырьков со связанным списком. Я не нашел ошибку в моем простом коде в течение нескольких часов. Не могли бы вы посмотреть на это?

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 

    for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 
    } 

    return 0; 
} 

и вот функция подкачки (но это, кажется, работает хорошо, потому что я проверил вручную все граничные случаи):

int listSwapWithNext(node_t **_list, size_t first) 
{ 
    node_t *pointer = *_list; 
    node_t *ptr_b; 
    node_t *ptr_c; 
    node_t *ptr_d; 

    if(!first) 
      ptr_b = pointer; 

    for(size_t i = 0; pointer->next->next; i++, pointer = pointer->next) 
    { 
      if(i == first - 1 || first == 0) 
      { 
       if(first) 
        ptr_b = pointer->next; 

       ptr_c = ptr_b->next; 
       ptr_d = ptr_c->next; 

       if(first) 
        pointer->next = ptr_c; 
       else 
        *_list = ptr_c; 

       ptr_c->next = ptr_b; 
       ptr_b->next = ptr_d; 

       break; 
      } 
    } 

    return 0;  
} 

Это вызывает эту аварию (на линии 229):

Когда я модифицировал состояние внутреннего контура в функции сортировки до:

for(int j = 0; j < size - 1 && pointer->next; j++) 

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

Спасибо!

EDIT: Вот модифицированная версия функции сортировки с условием ПРЕДОТВРАТИТЬ во внутреннем цикле и моих показателей отладки (сделанный с Е()):

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

Вот результат в консоли. Послушайте, он не делает каждый цикл, чтобы он плохо сортировал сортировку.

EDIT2: Вот essention проблемы. http://pastebin.com/e5K6C1A2

По-прежнему не могу решить эту проблему.

Answer 1

pointer = pointer->next Неверный вариант в том случае, если производится своп. Если вы сделали своп, pointer должен оставаться pointer, потому что он был перемещен вперед одним элементом.

Edit: я имею в виду это сделать:

if(strcmp(pointer->title, pointer->next->title) > 0) 
    listSwapWithNext(_list, j); 
else 
    pointer = pointer->next; 

Answer 2

Основываясь на том, что вы сказали, я считаю, что могу помочь вам определить несколько проблем в вашем коде. Я считаю, что проблемы, которые вы описываете, вызваны первым блоком кода, который вы опубликовали, в частности, этой частью.

for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 

Проблема броска этой линии:

if(strcmp(pointer->title, pointer->next->title) > 0) 

из-за того, как внутренний цикл строится здесь:

for(int j = 0 ; j < size - 1; j++) 

Так вы учета того факта, что, поскольку мы мы меняем места на 1 меньше, чем общий размер списка. Однако проблема состоит в том, что это заставляет вас попытаться разыменовать нулевой указатель при последнем проходе через него. Узел в связанном списке содержит указатель на некоторые данные и указатель на следующий объект. Итак, представьте себе, что происходит с секундой в последний раз, когда цикл for выполняется. Он выполняет свою свопинг, если strcmp истинно, тогда он продвигает указатель на ссылку следующего элемента в связанном списке. Здесь вы ошибаетесь. Так как вы сделали это, когда мы снова выполнить петлю, следующую строку:

if(strcmp(pointer->title, pointer->next->title) > 0) 

конкретно эта часть его: pointer->next->title потерпит неудачу, потому что текущий объект является последним элементом в связанном списке.По этой причине его следующий пункт указывает на NULL, и вы пытаетесь получить титульный объект элемента NULL, которого не существует.

Теперь рассмотрим измененный код.

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

У вас нет такой же ошибки, но вы получите неправильные результаты. Это не вызывается функцией сортировки, опять же, это вызвано строительством для цикла здесь:

for(j = 0 ; j < size - 1 && pointer->next; j++) 

для цикла будет выполняться до тех пор, как заданное условие истинно. Снова представим второе и последнее исполнение. Мы находимся в пределах наших границ, поэтому первое условие истинно, и после этого существует другой элемент, поэтому второе условие также верно. Петля запускается и продвигает указатель на следующий элемент. Теперь мы все еще находимся в пределах наших ограничений по размеру, поэтому true, но после этого больше нет элементов в списке, поэтому pointer->next - NULL. Это означает, что цикл не будет работать и, следовательно, не будет сортировать все данные, дающие вам плохие результаты.