Не могли бы вы рассказать мне, что случилось с этим

Question

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

void insertionSort(listNode ** listPtr, listNodeCompareFcn compare) 
{ 

    listNode * sorted = *listPtr; 
    listNode * swapper; 
    listNode * prev; 
    int swapped; 

    while(sorted != NULL) 
    { 

    swapper = sorted -> next; 
    prev = findprev(*listPtr, swapper); 
    swapped = 0; 

    while(swapper != NULL && prev != NULL && swapper != *listPtr && compare(swapper,prev)) 

    { 
     swapNodes(*listPtr, prev, swapper); 
     prev = findprev(*listPtr, swapper); 
     swapped = 1; 
    } 

     if (!swapped) sorted = sorted -> next; 

    } 

} 


static listNode * findprev(listNode * head, listNode * ptr){ 

    listNode * current = head; 

    while (current -> next != NULL){ 
     if ((current -> next) == ptr) return current; 
     current = current -> next; 
    }  

    return NULL; 

} 

void swapNodes(listNode * head, listNode * l1, listNode * l2){ 

    listNode * prev = findprev(head, l1); 
    prev -> next = l2; 
    l1 -> next = l2 -> next; 
    l2 -> next = l1; 

} 

Answer 1

Я заметил:

Я сделал достаточно работы на SSCCE знать, что большая часть вашей проблемы в том, что вы не достаточно осторожны с головой списка. Если вы меняете головной узел и следующий узел, вам нужно обновить указатель главного узла, так как иначе вы потеряете перед собой список. Я с уверенностью уверен, что это всего лишь составляющая проблемы [это была целая проблема]. Учитывая действительный список, функция findprev() работает нормально. Ни swapNodes(), ни insertionSort() можно получить чистый счет здоровья (еще!), думаю. Например, если findprev() возвращает NULL, swapNodes() счастливо разыгрывает указатель NULL; врезаться!

Ниже приведена SSCCE-версия вашего кода, обновленная с информацией о заднем канале об исправлении до swapNodes(), указанной в комментарии выше. Функция compare() оказывается компаратором стиля С ++, а не компаратором стиля С; то есть он возвращает true, если узел 1 приходит до узла 2 и false в противном случае (тогда как компаратор C-типа возвращает -1, 0, +1 или, строго, отрицательный, ноль, положительный - меньше, чем, больше, больше, чем). Только с исправлением swapNodes() - смена интерфейса и кода - и правильная семантика компаратора, список отсортирован правильно. Вряд ли исчерпывающий тест, но хорошее начало.

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

typedef struct listNode listNode; 
struct listNode 
{ 
    int datum; 
    listNode *next; 
}; 

typedef int (*listNodeCompareFcn)(const listNode *n1, const listNode *n2); 
//static void swapNodes(listNode *head, listNode *l1, listNode *l2); 
static void swapNodes(listNode **head, listNode *l1, listNode *l2); 
static listNode *findprev(listNode *head, listNode *ptr); 

static int node_compare(const listNode *n1, const listNode *n2)  // SSCCE 
{ 
    assert(n1 != 0 && n2 != 0); 
    printf("Compare: %2d and %2d\n", n1->datum, n2->datum); 
    if (n1->datum < n2->datum) 
     return 1; 
// if (n1->datum < n2->datum) 
//  return -1; 
// else if (n1->datum > n2->datum) 
//  return +1; 
    else 
     return 0; 
} 

static void insertionSort(listNode **listPtr, listNodeCompareFcn compare) 
{ 
    listNode *sorted = *listPtr; 

    while (sorted != NULL) 
    { 
     listNode *swapper = sorted->next; 
     listNode *prev = findprev(*listPtr, swapper); 
     int swapped = 0; 

     while (swapper != NULL && prev != NULL && swapper != *listPtr && compare(swapper, prev)) 
     { 
      //swapNodes(*listPtr, prev, swapper); 
      swapNodes(listPtr, prev, swapper); 
      prev = findprev(*listPtr, swapper); 
      swapped = 1; 
     } 

     if (!swapped) 
      sorted = sorted->next; 
    } 
} 

static listNode *findprev(listNode *head, listNode *ptr) 
{ 
    listNode *current = head; 
    assert(current != 0); 

    while (current->next != NULL) 
    { 
     if (current->next == ptr) 
      return current; 
     current = current->next; 
    } 

    return NULL; 
} 

// Update via email 
void swapNodes(listNode **listPtr, listNode *l1, listNode *l2) 
{ 
    listNode *prev = findprev(*listPtr, l1); 
    if (prev == NULL) 
    { 
     l1->next = l2->next; 
     *listPtr = l2; 
     l2->next = l1; 
    } 
    else 
    { 
     prev->next = l2; 
     l1->next = l2->next; 
     l2->next = l1; 
    } 
} 

/* 
static void swapNodes(listNode *head, listNode *l1, listNode *l2) 
{ 
    listNode *prev = findprev(head, l1); 
    prev->next = l2; 
    l1->next = l2->next; 
    l2->next = l1; 
} 
*/ 

static listNode *node_insert(listNode *head, int datum)  // SSCCE 
{ 
    listNode *node = malloc(sizeof(*node)); 
    node->datum = datum; 
    node->next = head; 
    return node; 
} 

static void print_list(const char *tag, const listNode *list)  // SSCCE 
{ 
    printf("%-8s", tag); 
    while (list != 0) 
    { 
     printf(" -> %2d", list->datum); 
     list = list->next; 
    } 
    putchar('\n'); 
} 

int main(void)  // SSCCE 
{ 
    static const int unsorted[] = { 29, 3, 14, 2, 91, 87, 13, 29, 1 }; 
    enum { NUM_VALUES = sizeof(unsorted)/sizeof(unsorted[0]) }; 
    listNode *head = 0; 

    print_list("Empty:", head); 
    for (int i = 0; i < NUM_VALUES; i++) 
    { 
     head = node_insert(head, unsorted[i]); 
     print_list("Added:", head); 
    } 

    for (listNode *curr = head; curr != 0; curr = curr->next) 
    { 
     listNode *prev = findprev(head, curr); 
     if (prev == 0) 
      printf("%2d - no prior node\n", curr->datum); 
     else 
      printf("%2d - prior node %2d\n", curr->datum, prev->datum); 
    } 

    print_list("Before:", head); 
    insertionSort(&head, node_compare); 
    print_list("After:", head); 

    return 0; 
} 

Выход (включая диагностику) от SSCCE:

Empty: 
Added: -> 29 
Added: -> 3 -> 29 
Added: -> 14 -> 3 -> 29 
Added: -> 2 -> 14 -> 3 -> 29 
Added: -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Added: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
1 - no prior node 
29 - prior node 1 
13 - prior node 29 
87 - prior node 13 
91 - prior node 87 
2 - prior node 91 
14 - prior node 2 
3 - prior node 14 
29 - prior node 3 
Before: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 
Compare: 29 and 1 
Compare: 13 and 29 
Compare: 13 and 1 
Compare: 87 and 29 
Compare: 91 and 87 
Compare: 2 and 91 
Compare: 2 and 87 
Compare: 2 and 29 
Compare: 2 and 13 
Compare: 2 and 1 
Compare: 14 and 91 
Compare: 14 and 87 
Compare: 14 and 29 
Compare: 14 and 13 
Compare: 3 and 91 
Compare: 3 and 87 
Compare: 3 and 29 
Compare: 3 and 14 
Compare: 3 and 13 
Compare: 3 and 2 
Compare: 29 and 91 
Compare: 29 and 87 
Compare: 29 and 29 
After: -> 1 -> 2 -> 3 -> 13 -> 14 -> 29 -> 29 -> 87 -> 91