-1

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

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; 

}
4

1 回答 1

2

我评论说：

我在 SSCCE 上做了足够多的工作，知道您的问题的主要部分是您对列表的头部不够小心。如果交换头节点和下一个节点，则需要更新头节点指针，否则会丢失链表的最前面。我可以肯定这只是问题的一部分[实际上是整个问题]。给定一个有效的列表，该findprev()函数可以正常工作。我认为，既swapNodes()不能也insertionSort()不能得到一份干净的健康单（还没有！）。例如，如果findprev()返回 NULL，则swapNodes()愉快地取消对 NULL 指针的引用；碰撞！

这是您的代码的 SSCCE 版本，更新了有关修复的反向通道信息，以swapNodes()在上面的评论中标识。该compare()函数原来是 C++ 风格的比较器，而不是 C 风格的比较器；也就是说，如果节点 1 在节点 2 之前，则返回 true，否则返回 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
于 2013-04-18T14:16:11.513 回答