Mergesort 实现中的分段错误

Question

我有一个程序 Mergesort 可以处理无序链接 list.The 我遇到的问题是分段错误（核心已转储）。

实际上我经常遇到这个错误，但我不知道如何解决。此外，它不会显示任何错误或警告消息来查找它。在这个源代码和其他一般情况下，我真的需要知道为什么我有这个以及我如何修复它。

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

typedef struct node_t node;
typedef struct node_t { int key; node *next; } node;
static node *head, *z;
node *merge(node *a, node *b)
{
    z->next =z;
    node *c = z;
    do
    {
        if (a->key > b->key)
        {
            c->next = a; c = a; a = a->next;
        }
        else
        {
            c->next = b; c = b; b = b->next;
        }
    } while (c != z);
    c = z->next;
    z->next = NULL;
    return c;
}
node *mergesort(node *c) {
    node *a = NULL; 
    node *b = NULL;
    if (c != NULL && c->next->next != NULL) {
        a = c; b = c;
        while (b->next != NULL && b->next->next != NULL) {
            c = c->next;
            b = b->next->next;
        }
        b = c->next;
        c->next = NULL;
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}
void printList(node* node) 
{ 
    while (node != NULL) { 
        printf("%d ", node->key); 
        node = node->next; 
    } 
} 
node *listcreate(int n, node *a)
{
    node *head = NULL;
    node *temp = NULL;
    node *p = NULL;
    int i=0;
    while(i<n)
    {
        temp = (node*) malloc(sizeof(node*));
        printf("Please insert the number: ");
        scanf("%d", &(temp->key));
        temp->next = NULL;
        if(head == NULL)
        head = temp;
        else
        {
            p = head;
            while(p->next != NULL)
            p = p->next;
            p->next = temp;
        }
        i++;
    }
    a = head;
}
int main() 
{ 
    node *a = NULL;
    listcreate(3, a);
    a = mergesort(a);
    printf("Sorted Linked List is: \n"); 
    printList(a); 

    getchar(); 
    return 0; 
}

Answer 1

对于最后一个问题，我认为分段错误的主要原因是访问未初始化的内存、程序越界或试图修改字符串文字。这些可能会导致分段错误，但不能保证它们会导致分段错误。以下是分段错误的一些常见原因 -

越界访问数组

取消引用 NULL 指针

取消引用释放的内存

取消引用未初始化的指针

“&”（地址）和“*”（解引用）运算符使用不当

printf 和 scanf 语句中的格式说明符不正确

堆栈溢出

写入只读存储器

Answer 2

首先，在包含 stdlib.h 的同时调用您的函数 mergesort 是不正确的，应该会在最近的 C 编译器中引发错误。

接下来，此代码序列通过取消引用空指针来调用未定义行为：

node *z = NULL;
node *c = z;
c->next = a;  //  UB!

此时，c是NULL，所以你不应该使用c->next。使用常见的 C 实现尝试写入导致段错误的不允许的内存。

您的算法尝试使用 sentinel，但恕我直言，这不是一个合适的用例。只记住第一个值会更简单。并且您还应该处理到达两个排序列表之一的末尾的情况。代码可以变成：

node *merge(node *a, node *b)
{
    node *c = z;           // current node initialized to null
    node *top;             // declare the future return value
    do
    {
        if (a->key > b->key)
        {
            if (c == z) top = a;    // if first value, remember it
            else c->next = a;       // else add the node to current list
            c = a; a = a->next;
            if (a == NULL) {        // explicitely handle end of input list
                c->next = b;
                break;
            }
        }
        else
        {
            if (c == z) top = b;
            else c->next = b; 
            c = b; b = b->next;
            if (b == NULL) {
                c->next = a;
            break;
            }
        }
    } while (c != z);
    return top;
}

但这还不是全部。您的代码混合了 C 和 C++。您只使用 C 库函数，但使用 C++ 编译器编译代码。 C 语言不允许函数重载，因此您不应重复使用具有不同参数集（mergesort）的标准库函数的名称。而在C语言中，you need not cast malloc.

即使使用我的修复程序，如果您不更改 mergesort 函数的名称，您的代码也会在任何体面的 C 编译器上中断。您已收到警告。

Mergesort 实现中的分段错误

Segmentation Fault in Mergesort implementation

c

algorithm

merge

linked-list

coredump