在尝试合并两个链表时，为什么我会出现分段错误（核心转储）？

问题描述 投票：0回答：3

所以我试图合并两个链表，但出现分段错误 两个链表分别是(1)->(2)->(3)和(1)->(3)->(4)。即使我 malloc 

l
和 
k
，输出也保持不变。该程序工作正常，直到调用 
merge
函数。由于我是初学者，一些详细的解释会有很大帮助。

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

typedef struct node
{
    int val;
    struct node *next;
} node;

typedef struct linkedlist
{
    node *head;
    node *tail;
} linkedlist;

void createlinkedlist(linkedlist *l)
{
    l->head = NULL;
    l->tail = NULL;
}

void push(linkedlist *l, int value)
{
    node *newnode = (node *)malloc(sizeof(node));
    if (newnode == NULL)
    {
        printf("insertion failed");
        return;
    }
    newnode->val = value;
    newnode->next = NULL;
    if (l->tail != NULL)
    {
        l->tail->next = newnode;
    }
    l->tail = newnode;
    if (l->head == NULL)
    {
        l->head = newnode;
    }
}

void display(linkedlist *l)
{
    node *printval = l->head;
    printf("\n");
    while (printval != NULL)
    {
        printf("%d-->", printval->val);
        printval = printval->next;
    }
}

void merge(linkedlist *l, linkedlist *k)
{
    node *lnext = l->head->next;
    node *lprevious = l->head;
    node *rprevious = k->head;
    node *rnext = k->head->next;
    if ((lprevious->val) <= (rprevious->val))
    {
        node *h = lprevious;
        while (lprevious != NULL && rprevious != NULL)
        {
            if (lprevious->val <= rprevious->val)
            {
                lprevious->next = rprevious;
                rprevious->next = lnext;
                rprevious = rnext;
                rnext = rnext->next;
                lprevious = lprevious->next;
            }
            else
            {
                lprevious = lprevious->next;
                lnext = lnext->next;
            }
        }
        l->head = h;
    }
    else
    {
        // node *h = head2;
        // while (previous != NULL || head2 != NULL) {
    }
}

int main()
{
    linkedlist l;
    linkedlist k;
    createlinkedlist(&l);
    createlinkedlist(&k);
    push(&l, 1);
    push(&l, 2);
    push(&l, 4);

    push(&k, 1);
    push(&k, 3);
    push(&k, 4);
    display(&k);
    display(&l);
    merge(&l, &k);
    display(&l);
}

我得到的输出。

1-->3-->4-->
Segmentation fault (core dumped)

最糟糕的是我的调试器没有显示任何错误。

c pointers linked-list segmentation-fault malloc
3个回答
0
投票
The segmentation fault occurs because of a logical error in the merge function. Specifically, there are a few issues with the way the nodes are being linked together.

Here are the problems in the merge function:

The condition for checking if a node in the second linked list should be inserted into the first linked list is not correct. The condition should be (lprevious->val <= rprevious->val), but it's currently set as (lprevious->val) <= (rprevious->val). The extra parentheses are not necessary and cause the comparison to be incorrect.

The merge function is assuming that both linked lists are non-empty. However, there should be checks to handle the cases where one or both of the linked lists are empty.

The while loop in the merge function should continue as long as both lprevious and rprevious are not NULL. However, the loop's termination condition is based only on lprevious != NULL, which could lead to accessing NULL pointers for the second linked list if it is shorter than the first one.

The function is not correctly updating the tail pointer of the first linked list after the merge.

To fix these issues, you can update the merge function as follows:
void merge(linkedlist *l, linkedlist *k)
{
    node *lprevious = l->head;
    node *rprevious = k->head;

    // Check if either linked list is empty
    if (lprevious == NULL)
    {
        l->head = rprevious;
        l->tail = k->tail;
        return;
    }
    if (rprevious == NULL)
    {
        return;
    }

    if (lprevious->val > rprevious->val)
    {
        // Swap l and k pointers so that l always points to the smaller head
        linkedlist temp = *l;
        *l = *k;
        *k = temp;
    }

    node *lnext;
    node *rnext;

    while (lprevious != NULL && rprevious != NULL)
    {
        lnext = lprevious->next;
        rnext = rprevious->next;

        if (lnext == NULL || lnext->val > rprevious->val)
        {
            // Insert the node from the second list into the first list
            lprevious->next = rprevious;
            rprevious->next = lnext;
            rprevious = rnext;
        }
        lprevious = lprevious->next;
    }

    // Update the tail pointer of the first list if needed
    if (rprevious != NULL)
    {
        l->tail->next = rprevious;
        l->tail = k->tail;
    }
}

通过这些更改，合并功能现在应该可以正常工作。它正确处理任一链表为空的情况，并将两个链表中的节点正确链接在一起。

现在，当您运行程序时，您应该获得链接列表的正确合并输出：

1-->1-->2-->3-->4-->4-->

0
投票

merge
功能有问题：

    如果
  • node *lnext = l->head->next;
     是空列表，则 
    l
    具有未定义的行为，因为 
    l->head
    是空指针。
  • 同样的问题
    node *rnext = k->head->next;
  • 与
    if ((lprevious->val) <= (rprevious->val))
    有同样的问题：如果其中一个列表为空，则
    lprevious
    或
    rprevious
    可能是空指针。

merge
函数应将
r
头部中的任何较小元素插入到
l
头部之前，然后迭代
l
，保持指向前一个元素的指针。

这是修改后的版本：

void merge(linkedlist *l, linkedlist *k) {
    node *n = k->head;
    if (n == NULL) {
        // k is an empty list: nothing to do
        return;
    }
    if (l->head == NULL) {
        // l is an empty list: move all elements from k to l
        l->head = k->head;
        l->tail = k->tail;
        k->head = k->tail = NULL;
        return;
    }
    if (l->head->val > n->val) {
        // insert head element of k at head of l
        k->head = n->next;
        n->next = l->head;
        l->head = n;
    }
    node *prev = l->head;
    while ((n = k->head) != NULL) {
        if (prev->next == NULL) {
            // reached end of l: append all elements of k
            prev->next = n;
            l->tail = k->tail;
            break;
        }
        if (prev->next->val > n->val) {
            // insert node n between prev and prev->next
            k->head = n->next;
            n->next = prev->next;
            prev->next = n;
        }
        prev = prev->next;
    }
    // clear the k list
    k->head = k->tail = NULL;
}
0
投票

您似乎正在尝试按升序合并列表。

您的函数

merge
有几个错误。

第一个是它没有考虑到通常传递给函数的一个或两个列表可以为空。在这种情况下，这些语句位于函数的开头

node *lnext = l->head->next;
node *rnext = k->head->next;

已经调用未定义的行为。

这些语句中的 while 循环也存在同样的问题

rnext = rnext->next;
lnext = lnext->next;

因为指针 

rnext
和 
lnext
可以是空指针。

while 循环中的 if 语句也存在逻辑错误。

至少如果

lprevious->val
不大于
rprevious->val
，并不意味着需要在节点
rprevious
之后插入节点
lprevious
。

if (lprevious->val <= rprevious->val)
{
    lprevious->next = rprevious;
    rprevious->next = lnext;
    rprevious = rnext;
    rnext = rnext->next;
    lprevious = lprevious->next;
}
else
{
    lprevious = lprevious->next;
    lnext = lnext->next;
}

另一方面，如果

lprevious->val
大于
rprevious->val
，那么并不意味着你必须移动到第二个节点
lprevious->next
。

并且该函数不考虑应更改的指针 

l->tail
和 
r->tail
。

如果一开始只是根据给定的两个列表形成一个新列表，然后将第一个列表设置为形成的列表，并将第二个列表设置为空列表，那么功能代码会更清晰。

请记住，您还需要编写一个函数来释放列表节点的所有分配内存。

函数的参数

display
也应该有限定符
const

void display( const linkedlist *l)

因为该函数不会更改传递的列表。

并且功能

push
不应显示任何消息。

if (newnode == NULL)
{
    printf("insertion failed");
    return;
}

函数的调用者将决定是否输出消息。此外，函数的调用者应该有可能知道函数调用的结果。也就是说，函数应该通过其返回值向调用者报告失败或成功。

这是一个演示程序，展示如何实现

merge
功能。

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

typedef struct node
{
    int val;
    struct node *next;
} node;

typedef struct linkedlist
{
    node *head;
    node *tail;
} linkedlist;


int push( linkedlist *l, int value )
{
    node *newnode = malloc( sizeof( node ) );
    int success = newnode != NULL;

    if (success)
    {
        newnode->val = value;
        newnode->next = NULL;

        if (l->head == NULL)
        {
            l->head = newnode;
        }
        else
        {
            l->tail->next = newnode;
        }

        l->tail = newnode;
    }

    return success;
}

void merge( linkedlist *l, linkedlist *r )
{
    node *head = NULL;
    node *tail = NULL;

    node **current = &head;

    while (l->head != NULL && r->head != NULL)
    {
        if (r->head->val < l->head->val)
        {
            *current = r->head;
            r->head  = r->head->next;
        }
        else
        {
            *current = l->head;
            l->head  = l->head->next;
        }

        tail = *current;
        current = &( *current )->next;
    }

    if (l->head != NULL)
    {
        *current = l->head;
        tail = l->tail;
    }

    if ( r->head != NULL )
    {
        *current = r->head;
        tail = r->tail;
    }

    l->head = head;
    l->tail = tail;

    r->head = r->tail = NULL;
}

FILE *display( const linkedlist *l, FILE *fp )
{
    for (const node *current = l->head; current != NULL; current = current->next)
    {
        fprintf( fp, "%d -> ", current->val );
    }

    fputs( "null", fp );

    return fp;
}

void clear( linkedlist *l )
{
    while (l->head)
    {
        node *current = l->head;
        l->head = l->head->next;
        free( current );
    }

    l->tail = l->head;
}

int main( void )
{
    linkedlist l = { .head = NULL, .tail = NULL };

    for (int i = 0; i < 10; i += 2)
    {
        push( &l, i );
    }

    fputc( '\n', display( &l, stdout ) );

    linkedlist r = { .head = NULL, .tail = NULL };

    for (int i = 1; i < 10; i += 2)
    {
        push( &r, i );
    }

    fputc( '\n', display( &r, stdout ) );

    putchar( '\n' );

    merge( &l, &r );

    fputc( '\n', display( &l, stdout ) );
    fputc( '\n', display( &r, stdout ) );

    clear( &l );
}

程序输出为

0 -> 2 -> 4 -> 6 -> 8 -> null
1 -> 3 -> 5 -> 7 -> 9 -> null

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
null

最后还有一个更重要的评论。如果您想构建排序列表，则应重写函数 

push
以提供按升序插入新节点的功能。

在这种情况下，函数可以如下所示

int push( linkedlist *l, int value )
{
    node *newnode = ( node * )malloc( sizeof( node ) );
    int success = newnode != NULL;

    if (success)
    {
        newnode->val = value;

        node **current = &l->head;

        while (*current != NULL && !( newnode->val < ( *current )->val ))
        {
            current = &( *current )->next;
        }

        newnode->next = *current;
        *current = newnode;

        if ( newnode->next == NULL )
        {
            l->tail = newnode;
        }
    }

    return success;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.