删除节点 - 链接列表 - C.-Java 学习之路

我试图从链表中删除一个节点，但我仍然是双指针概念的新手，所以我尝试使用全局变量来保持头指针 . 但是，当我在删除中间节点后尝试打印列表时，得到错误的结果 .

我看到了这个问题deleting a node in the middle of a linked list，我不知道我的删除节点功能与答案有什么不同 .

这是我的代码：

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

typedef unsigned char u8;
typedef struct Node node;
void addfirstnode( u8 );
void addnode( u8 );
void print( void );
void deletenode( u8 key );
void deleteonlynode();
void deletefirstnode();

struct Node
{
    u8 x;
    node *next;
};
node *head;
u8 length = 0;


void main( void )
{
    u8 x;
    printf( "\nTo add node enter 0\nTo print linked list enter 1\nTo exit press 2\nTo delete node press 3\nYour Choice:" );
    scanf( "%d", &x );
    if ( x == 2 )
    {
        printf( "\nThank You\nGood Bye" );
    }
    while ( x != 2 )
    {
        switch ( x )
        {
            u8 n;
            u8 key;
            case 0:            //Add node
                printf( "\nPlease enter first value:" );
                scanf( "%d", &n );
                if ( length == 0 )
                {
                    addfirstnode( n );
                    //printf("%d",head->x);
                }
                else
                {
                    addnode( n );
                }
                printf( "\nNode added , Thank you\n" );
                break;

            case 1:            //Print
                print();
                break;

            case 3:            //DeleteNode
                printf( "\nPlease enter value to be deleted:" );
                scanf( "%d", &key );
                deletenode( key );
                //deletefirstnode();
                break;

            default:
                printf( "\nInvalid Choice please try again\n" );
        }
        printf( "\nTo add node enter 0\nTo print linked list enter 1\nTo exit press 2\nTo delete node press 3\nYour Choice:" );
        scanf( "%d", &x );
        if ( x == 2 )
        {
            printf( "\nThank You\nGood Bye" );
        }
    }
    //where do I use free();
}

void addfirstnode( u8 n )
{
    head = ( node * ) malloc( sizeof( node ) );
    head->next = NULL;
    head->x = n;
    length++;
}

void addnode( u8 n )
{
    node *last = head;
    while ( ( last->next ) != NULL )
    {
        last = last->next;
    }
    last->next = ( node * ) malloc( sizeof( node ) );
    ( last->next )->next = NULL;
    ( last->next )->x = n;
    length++;
}

void print( void )
{
    node *last = head;
    u8 count = 1;
    printf( "\n---------------------" );
    if ( last == NULL )
    {
        printf( "\nList is empty" );
    }
    while ( last != NULL )
    {
        printf( "\nNode Number %d = %d", count, last->x );
        last = last->next;
        count++;
    }
    printf( "\n---------------------" );
    printf( "\n" );
}

void deletenode( u8 key )
{
    node *last = head;
    //node*postlast = NULL;
    if ( ( last->x == key ) && ( last->next == NULL ) )
    {
        deleteonlynode();
    }
    else
    {
        while ( last != NULL )
        {
            if ( ( last->x ) == key )
            {
                printf( "value to be deleted is found" );
                node *temp = last->next;
                last->next = last->next->next;
                free( temp );
                length--;
            }
            last = last->next;
        }
    }
}

void deleteonlynode()
{
    printf( "\n Deleting the only node" );
    free( head );
    head = NULL;
    length--;
}

void deletefirstnode()
{
    printf( "\n Deleting the first node" );
    node *temp = head;
    head = head->next;
    free( temp );
    length--;
}

2 回答

代码正在从链表中删除错误的项目：

看到：

if ( ( last->x ) == key )
        {
            printf( "value to be deleted is found" );
            node *temp = last->next;     // last->next? No, just last.
            last->next = last->next->next;
            free( temp );
            length--;
        }

last 指向要删除的元素 . 但是然后代码指定 temp 指向 last->next （NOT last ），然后从列表中删除它 .

因此，通过查看 node->next 而不是当前节点，它将从指针之前重新开始删除 . 基本上你的代码几乎已经存在了 .

void deletenode( u8 key )
{
    node *ptr = head;

    if ( ( ptr->x == key ) )
    {
        // Delete the first/head element
        node *temp = ptr;
        head = head->next;
        free( temp );
        length--;
    }
    else
    {
        while ( ptr->next != NULL )
        {
            if ( ( ptr->next->x ) == key )
            {
                printf( "value to be deleted is found" );
                node *temp = ptr->next;
                ptr->next = ptr->next->next;
                free( temp );
                length--;
            }
            ptr = ptr->next;
        }
    }
}

此外，我冒昧地将 last 重命名为 ptr ，因为这令我感到困惑 .

编辑：更新以干净地删除头部 .

回复于 2024-05-02T20:47:11+08:00

您的代码似乎正在删除 last->next ，而 last 应该是与该键匹配的节点 . 我猜以下代码可能会更短并删除

node* head;

/* returns the node* the previous_node->next should be after the deletion */
node* delete_node(node* current, u8 key) {
    if (current == NULL) return NULL;  // deletion comes to end
    if (head->x == key) {
        node* temp = current->next;
        free(current);
        return delete_node(temp, key);
    }
    current->next = delete_node(current->next, key);
    return current;
}


int main() {
    // build the linked list
    // ...
    head = delete_node(head, key);
    return 0;
}

但是，如果列表太长，则此实现（使用递归而不是循环）可能会导致StackOverFlow . 我没有测试过gcc是否会优化递归 .

回复于 2024-05-02T20:47:11+08:00

删除节点 - 链接列表 - C.

2 回答

相关问题