C语言 删除链表最后一个节点的代码不起作用

cgvd09ve  于 2023-06-28  发布在  其他
关注(0)|答案(2)|浏览(155)

我尝试在单链表上执行插入和删除操作,但deletelast()(删除链表的最后一个节点)函数不适用于具有2个以上节点的链表。
下面是代码:

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

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

node *head = NULL;

void insertbegin(int *a)
{
    node *newnode = (node *)malloc(sizeof(node));
    newnode->next = head;
    head = newnode;
    newnode->data = *a;
    printf("success!!");
}

void display()
{
    if (head != NULL)
    {
        node *temp = head;
        while (temp != NULL)
        {
            printf("%d\t", temp->data);
            temp = temp->next;
        }
    }
    else if (head == NULL)
    {
        printf("the linked list is empty\n");
    }
}

void insertlast()
{
    int b;
    printf("enter the value of the element:\n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->next == NULL)
        {
            temp->next = newnode;
            newnode->next = NULL;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
    temp = NULL;
}

void insertspecific()
{
    int n, b;
    printf("enter the value after which you want to insert a node: \n");
    scanf("%d", &n);
    printf("enter te data of the node to be inserted: \n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->data == n)
        {
            newnode->next = temp->next;
            temp->next = newnode;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
}

void deletebegin()
{
    if (head == NULL)
        printf("the list is empty.\n");
    else
    {
        node *newhead = head;
        head = newhead->next;
        printf("success deletion");
        free(newhead);
    }
}

void deletelast()
{
    if (head == NULL)
    {
        printf("the list is empty\n");
    }
    else if (head->next->next == NULL)
    {
        node *temp = NULL;
        temp = head->next;
        head->next = NULL;
        free(temp);
        temp = NULL;
    }
    else
    {
        node *temp = head;
        node *ptr = NULL;
        while (temp != NULL)
        {
            if (temp->next->next == NULL)
            {  
                ptr = temp->next;
                temp->next == NULL;
                free(ptr);
                ptr = NULL;
            }
            temp = temp->next;
        }
        printf("deleted the node from the last\n");
    }
}

void main()
{
    int a;
    int choice = 0;
    while (choice != 9)
    {
        printf("\n\n*********Main Menu*********\n");
        printf("\nChoose one option from the following list ...\n");
        printf("\n===============================================\n");
        printf("\n1.Insert at begining\n2.Insert at last\n3.Insert after a specific position\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.traverse\n8.Display the Linked list\n9.Exit\n");
        printf("\nEnter your choice?\n");
        scanf("\n%d", &choice);
        switch (choice)
        {
        case 1:
            printf("enter the value you want to insert: \n");
            scanf("%d", &a);
            insertbegin(&a);
            break;
        case 2:
            insertlast();
            break;
        case 3:
            insertspecific();
            break;
        case 4:
            deletebegin();
            break;
        case 5:
            deletelast();
            break;
        case 6:
            // deletespecific();
            break;
        case 7:
            // traverse();
            break;
        case 8:
            display();
            break;
        case 9:
            exit(0);
            break;
        default:
            printf("Please enter valid choice..");
        }
    }
}

我正在使用insertbegin()函数插入节点,并使用display()函数查看链表,但deletelast()函数正在工作,并且没有为超过2个节点提供输出。我的逻辑是使用temp指针遍历链表,当我到达倒数第二个节点时,我将其next值更改为NULL,并使用ptr指针释放最后一个节点。但由于某种原因,它不起作用。
我对DSA还是个新手。
运行deletelast()函数时的输出屏幕

7bsow1i6

7bsow1i61#

假设你有一个空列表:你的第一个分支检测到没有什么可做的。
假设你有一个只有一个节点的列表:

  • head不是NULL,指向唯一节点;
  • head->next指向NULL;
  • head->next->nextundefined behavior,因为你试图解引用NULL指针。哎哟!!

这段代码的一个更好的版本是:

else if(head->next==NULL)    // list with only one node
{
    free(head);             // delete the node
    head=NULL;              // and the list is empty now
}

如果您有多个节点,则会进入else分支。不幸的是,在这个分支中,您再次尝试next->next,它将由于相同的原因失败。
话虽如此,不需要在一个节点的列表和多于一个节点的列表之间进行区别。因此,您可以在相同类型的循环中简化和处理两者:

while (head) {  // as long as there are nodes:  
    temp = head->next   // keep track of the next node before current is deleted
    free (head);        // kill current node
    head = next;        // ready to process next node unless (could be null)
}

更好的是,您不再需要if (head==NULL),因为循环可以很好地处理这种特殊情况,如果headNULL,则什么也不做。

hm2xizp9

hm2xizp92#

对于初学者来说,定义函数的方式依赖于全局变量是一个坏主意,就像你的代码中函数定义依赖于全局变量head一样。在这种情况下,你将无法或将非常困难,例如在一个程序中同时使用两个列表。
通过指向函数insertbegin的指针向该函数传递一个整数

void insertbegin(int *a)

这说不通函数应该声明为

void insertbegin(int a)

在函数display中,指针temp应声明为const node *类型

void display()
{
    if (head != NULL)
    {
        const node *temp = head;
        //...

因为函数中的列表没有改变。
而不是else if

else if (head == NULL)

有足够的东西可以用

else
//...

函数insertlast有几个缺点。

void insertlast()
{
    int b;
    printf("enter the value of the element:\n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->next == NULL)
        {
            temp->next = newnode;
            newnode->next = NULL;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
    temp=NULL;
}

对于初学者来说,它应该接受一个值,该值将通过一个参数插入到列表中,方式与函数insertbegin相同。

void insertlast( int b );

如果列表为空,即head等于NULL,则该函数不插入任何内容。如果列表是空的,并且在列表中插入了一个值,那么指针head将被改变。
如果列表不为空,则此while循环

while (temp != NULL)
{
    if (temp->next == NULL)
    {
        temp->next = newnode;
        newnode->next = NULL;
        newnode->data = b;
    }
    temp = temp->next;
}

是一个无限循环
可以通过以下方式声明和定义该函数

int insertlast( int data )
{
    node *newnode = malloc( sizeof( *newnode ) );
    int success = newnode != NULL;

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

        if ( head == NULL )
        {
            head = newnode;
        }
        else
        {       
            node *temp = head;

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

            temp->next = newnode;
        }
    }

    return success;
}

函数insertspecific也不应该向用户询问任何问题。函数的调用者应该通过函数参数提供所需的值。该函数不向用户报告是否在列表中找到具有指定值的节点。如果没有找到这样的节点,函数将产生内存泄漏。因此,至少在分配新节点之前,您需要首先找到目标节点,然后插入新节点。
函数deletelast也无效。

void deletelast()
{
    if (head == NULL)
    {
        printf("the list is empty\n");
    }
    else if(head->next->next==NULL)
    {
        node *temp=NULL;
        temp=head->next;
        head->next=NULL;
        free(temp);
        temp=NULL;
    }
    else
    {
        node *temp = head;
        node *ptr=NULL;
        while (temp != NULL)
        {
            if (temp->next->next == NULL)
            {  
                ptr=temp->next;
                temp->next == NULL;
                free(ptr);
                ptr=NULL;
            }
            temp=temp->next;
        }
        printf("deleted the node from the last\n");
    }
}

例如,如果列表只有一个节点,那么这个if语句

else if(head->next->next==NULL)

调用未定义的行为。目前还不清楚为什么它存在于函数中。
在这个if语句中的以下while循环中也存在未定义行为的相同问题

if (temp->next->next == NULL)

在删除最后一个节点之后,因为循环继续其迭代。
使用您的方法,该函数可以如下所示。

void deletelast()
{
    if ( head == NULL )
    {
        printf("the list is empty\n");
        return;            
    }

    if ( head->next == NULL )
    {
        node *temp = head;
        head = NULL;
        free( temp );
    }
    else
    {
        node *temp = head;

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

        free( temp->next );
        temp->next = NULL;
    }

    puts( "deleted the node from the last" );
}

请注意,根据C标准,不带参数的函数main应声明为

int main( void )

相关问题