你能告诉我这有什么问题吗

Question

需要帮助，请需要帮助，请我的代码编译得很好，但是当我运行时它给出了一个段错误，我不知道为什么。我已经检查了代码很多次，但仍然不知道问题出在哪里。请需要帮助。

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

我评论过:

I've done enough work on an SSCCE to know that a major part of your problem is that you are not being careful enough with the head of your list. If you swap the head node and the next node, you need to update the head node pointer, as otherwise you lose the front of the list. I'm tolerably certain that's only a component of the trouble [it was in fact the whole trouble]. Given a valid list, the findprev() function works fine. Neither swapNodes() nor insertionSort() can be given a clean bill of health (yet!), I think. For instance, if findprev() returns NULL, swapNodes() happily dereferences the NULL pointer; crash!

这是您代码的 SSCCE 版本，已使用有关修复上述评论中的 swapNodes() 的反向 channel 信息进行了更新。 compare() 函数实际上是一个 C++ 风格的比较器，而不是 C 风格的比较器；也就是说，如果节点 1 位于节点 2 之前，则返回 true，否则返回 false(而 C 风格比较器返回 -1、0、+1 — 或严格来说，负数、零、正数 — 对于小于、等于、大于)。只需修复 swapNodes()(接口(interface)和代码更改)以及正确的比较器语义，列表即可正确排序。这不是一个详尽的测试，但却是一个好的开始。

#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