2

我是一个初学者，正在尝试学习数据结构。我写了一个从链表中删除一个元素的代码。如果列表中已经存在该元素，则编译和运行过程中不会出现问题。但是，当我尝试删除列表中不存在的元素时，即使我已经编写了这种情况，也会发生分段错误。你能帮我看看吗？

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int x;
    struct node *next;
}node;

void addElement(node *r, int x)
{
    for(; r->next!=NULL; r=r->next);
    r->next=(node*)malloc(sizeof(node));
    r->next->x=x;
    r->next->next=NULL;

}
node* add_Element_inorder(node *r, int x)
{
    if(r==NULL)
    {
        r=(node*)malloc(sizeof(node));
        r->next=NULL;
        r->x=x;
        return r;
    }
    if(r->x>x)
    {
        node*tmp=(node*)malloc(sizeof(node));
        tmp -> x = x;
        tmp->next=r;
        return tmp;
    }
    node *iter=r;

    while(iter->next!=NULL && iter->next->x < x)
    {

        iter=iter->next;
    }

    node*tmp=(node*)malloc(sizeof(node));
    tmp->next = iter->next;
    iter->next=tmp;
    tmp->x=x;
    return r;

}
void print_Linked_L(node *r)
{
    node* iter = r;
    printf("%d ", iter->x);
    iter=iter->next;
    while(iter != NULL)
    {
        printf("%d ", iter->x);
        iter=iter->next;
    }

}
node* erase_Element(node *r, int x)
{
   node*iter=r;
   if(iter->x == x)
   {
       r=r->next;
       free(iter);
       return r;
   }

   while(iter->next->x != x && iter->next!=NULL)
   {
       iter=iter->next;

   }

    if(iter->next==NULL)
    {
        printf("Number does not exist.");
        return r;
    }

   node *temp=iter->next;
   iter->next=iter->next->next;
   free(temp);
   return r;
}

int main()
{

    node *root = (node*)malloc(sizeof(node));
    root=NULL;
    root= add_Element_inorder(root, 400);
    root= add_Element_inorder(root, 40);
    root= add_Element_inorder(root, 4);
    root= add_Element_inorder(root, 450);
    root= add_Element_inorder(root, 50);
    node *iter=root;
    print_Linked_L(root);
    root =erase_Element(root,45);
    printf("\n");
    print_Linked_L(root);







return 0;
}
4

2 回答 2

1 
while(iter->next->x != x && iter->next!=NULL)

在此代码中，首先运行 iter->next->x，然后运行 ​​iter->next!=NULL 您取消引用 null。解决方案是：

while(iter->next!=NULL && iter->next->x != x )
于 2020-04-24T20:05:51.413 回答
0

事实上，所有的功能都是不正确的。

例如在这个函数中

void addElement(node *r, int x)
{
    for(; r->next!=NULL; r=r->next);
    r->next=(node*)malloc(sizeof(node));
    r->next->x=x;
    r->next->next=NULL;

}

不检查 t 是否等于 NULL。该功能应至少定义为

node * addElement( node *head, int x )
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL ) current = current->next;

        new_node->next = NULL;
        current->next = new_node;
    }

    return head;
}

在函数add_Element_inorder中有两个很多重复的代码。该函数可以更简单地定义。

node * add_Element_inorder( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL || x < head->x )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL && !( x < current->next->x ) )
        {
            current = current->next;
        }

        new_node->next = current->next;
        current->next = new_node;
    }

    return head;
}

print_Linked_L当指向头节点的指针等于 NULL 时，该函数可以为空列表调用未定义的行为。

void print_Linked_L(node *r)
{
    node* iter = r;
    printf("%d ", iter->x);
    //...

该功能可以定义为

void print_Linked_L( const node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->x );
    }

    puts( "null" );
}

erase_Element由于 while 语句中的条件顺序不正确，当没有具有目标值的节点时，该函数再次调用未定义的行为

while(iter->next->x != x && iter->next!=NULL)

那就是首先你需要检查是否iter->next != NULL并且只有在之后检查它的值是否不等于x。

该函数可以通过以下方式定义

node * erase_Element( node *head, int x )
{
    if ( head != NULL )
    {
        if ( head->x == x )
        {
            node *tmp = head;
            head = head->next;
            free( tmp );
        }
        else
        {
            node *current = head;

            while ( current->next != NULL && current->next->x != x )
            {
                current = current->next;
            }

            if ( current->next != NULL )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                printf( "Number %d does not exist in the list.\n", x );
            }   
        }
    }

    return head;
}

函数 main 以内存泄漏开始

int main()
{
    node *root = (node*)malloc(sizeof(node));
    root=NULL;

首先分配内存，然后由于覆盖指针根，返回的地址立即丢失。

这是一个演示程序，显示了更新的函数定义。

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

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

node * addElement( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL ) current = current->next;

        new_node->next = NULL;
        current->next = new_node;
    }

    return head;
}    

node * add_Element_inorder( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL || x < head->x )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL && !( x < current->next->x ) )
        {
            current = current->next;
        }

        new_node->next = current->next;
        current->next = new_node;
    }

    return head;
}

void print_Linked_L( const node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->x );
    }

    puts( "null" );
}

node * erase_Element( node *head, int x )
{
    if ( head != NULL )
    {
        if ( head->x == x )
        {
            node *tmp = head;
            head = head->next;
            free( tmp );
        }
        else
        {
            node *current = head;

            while ( current->next != NULL && current->next->x != x )
            {
                current = current->next;
            }

            if ( current->next != NULL )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                printf( "Number %d does not exist in the list.\n", x );
            }   
        }
    }

    return head;
}

int main(void) 
{
    node *root = NULL;

    root = add_Element_inorder( root, 400 );
    root = add_Element_inorder( root, 40 );
    root = add_Element_inorder( root, 4 );
    root = add_Element_inorder( root, 450 );
    root = add_Element_inorder( root, 50 );

    print_Linked_L( root );

    root = erase_Element( root, 45 );
    print_Linked_L(root);   
    root = erase_Element( root, 400 );
    print_Linked_L(root);   
    root = erase_Element( root, 40 );
    print_Linked_L(root);   
    root = erase_Element( root, 4 );
    print_Linked_L(root);   
    root = erase_Element( root, 450 );
    print_Linked_L(root);   
    root = erase_Element( root, 50 );
    print_Linked_L(root);   

    return 0;
}

程序输出为

4 -> 40 -> 50 -> 400 -> 450 -> null
Number 45 does not exist in the list.
4 -> 40 -> 50 -> 400 -> 450 -> null
4 -> 40 -> 50 -> 450 -> null
4 -> 50 -> 450 -> null
50 -> 450 -> null
50 -> null
null
于 2020-04-24T20:45:31.430 回答