节点插入、链表

Question

我有这段代码，它通过它在 starting.This 处插入节点代码还包含一个打印链表的函数，如果为空，它会打印 linked list is empty 。

当我运行这段代码时，我的输出是 Linked list is empty .

struct node {
    int data;
    node* next;
}* start = NULL;

void append(node* linkedlist, int data)
{
    node* new_element = NULL;
    new_element = (node*)malloc(sizeof(struct node));
    new_element->data = data;
    if (linkedlist == NULL) {
        linkedlist = new_element;
        new_element->next = NULL;
    }

    else {
        new_element->next = (linkedlist)->next;
        (linkedlist)->next = new_element;
    }
}

int main()
{
    append(start, 4);
    append(start, 5);
    printList(start);
}

更新：

void printList(node* linkedlist)
{
    node* ptr = linkedlist;
    if (linkedlist == NULL) {
        printf("Linked list is empty");
        exit(0);
    }
    else {

        while (ptr != NULL) {
            cout << ptr->data;
            ptr = ptr->next;
        }
    }
}

我可能做错了什么？我应该更改什么才能使其正常工作？

Answer 1

您的问题出在这里linkedlist = new_element; 将参数传递给函数时，它们是按值传递的。即使当您传递 pointer 时，您实际上传递的是该指针的副本（您可以通过在函数内部和函数外部打印 linkedlist 的地址来验证）。语句 linkedlist = new_element; 将 new_element 分配给一个副本。一旦函数 return 你最终什么都没有（和内存泄漏）。请记住，当您需要更改指针本身时，您必须使用双 pointer **

Answer 2

你输入了指向 null 的 start 的值。然后将其复制到另一个指针 linkedlist 并将其设置为新值。在函数 start 仍然指向 null 之后，因为您从未更改 start.

的值

您可以尝试将声明更改为

void append(node *&linkedlist,int data)

如果您使用的是 C++ 编译器。

其他

void append(node **linkedlist,int data)
...
append(&start,4);

如果您使用的是 C

Answer 3

在追加函数中你应该

首先将newnode的next初始化为null
插入前检查是否为空列表，如果为空则将其作为头部。
如果它不为空，则将新节点指向列表的头部并使其成为新的头部。
要反映在追加中完成的插入，您应该 return 函数的修改头（也相应地修改 main）。

看这段代码：-

    node *append(node *linkedlist,int data){
        node *new_element=NULL;
        new_element=(node *)malloc(sizeof(struct node));
        new_element->data=data;
        new_element->next=NULL;// initialise next of newnode to  be null here
        // In case of empty list make this as first node
        if(linkedlist==NULL)
        {
              linkedlist=new_element;
        }
       else
        {
            new_element->next=(linkedlist);//point the new node to head of list
            (linkedlist)=new_element;// make new node as head
        }
        return linkedlist;
    }


    int main()
    {
        start = append(start, 4);
        start = append(start, 5);
        printList(start);
    }

Answer 4

我认为您的 if 语句不正确。我会这样做

if(linkedlist == null)
{
    //head node is null i.e, linked list is empty hence make the new node as head node
    linkedlist = new_element;  
}else{
    //make the new node point to the head
    new_element->next = linkedlist;
    //make the new node as head node
    linkedlist = new_element;
}

Answer 5

对于初学者，您显示的代码不是有效的 C 代码。您正在使用 C++ 元素。所以该程序甚至不会编译为 C 程序。

由于最初设置为 NULL 的节点 start 可以通过函数更改，因此您必须通过引用传递它。否则函数参数linkedlist是函数的局部变量，在函数中会被改变，最后在函数退出后销毁。所以原来的指针start本身是不会改变的。

还有这个else代码块

    else {
        new_element->next = (linkedlist)->next;
        (linkedlist)->next = new_element;
    }

错了。此代码块不会在列表的开头插入新节点。它在第一个已经存在的节点之后插入一个新节点。

考虑到函数名称append不适合在列表的开头插入节点。取个insert这样的名字比较好。该函数可以如下所示

int insert( struct node **linkedlist, int data )
{
    struct node *new_element = malloc( sizeof( struct node ) );
    int success = new_element != NULL;

    if ( success )
    {
        new_element->data = data;
        new_element->next = *linkedlist;
        *linkedlist = new_element;
    }

    return success;
}

如果您确实需要一个将节点附加到列表的函数，那么它可以采用以下方式

int append( struct node **linkedlist, int data )
{
    struct node *new_element = malloc( sizeof( struct node ) );
    int success = new_element != NULL;

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

        while ( *linkedlist != NULL ) linkedlist = &( *linkedlist )->next; 
        *linkedlist = new_element;
    }

    return success;
}

这是一个演示程序

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

struct node 
{
    int data;
    struct node* next;
} *start = NULL;

int insert( struct node **linkedlist, int data )
{
    struct node *new_element = malloc( sizeof( struct node ) );
    int success = new_element != NULL;

    if ( success )
    {
        new_element->data = data;
        new_element->next = *linkedlist;
        *linkedlist = new_element;
    }

    return success;
}

int append( struct node **linkedlist, int data )
{
    struct node *new_element = malloc( sizeof( struct node ) );
    int success = new_element != NULL;

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

        while ( *linkedlist != NULL ) linkedlist = &( *linkedlist )->next; 
        *linkedlist = new_element;
    }

    return success;
}

void printList( struct node* linkedlist )
{
    if ( linkedlist == NULL ) 
    {
        puts( "Linked list is empty" );
    }
    else 
    {
        for ( struct node *current = linkedlist; current != NULL; current = current->next ) 
        {
            printf( "%d ", current->data );
        }
        printf( "\n" );
    }
}

int main( void ) 
{
    const int N = 10;

    for ( int i = 1; i <= N; i++ )
    {
        if ( i % 2 == 0 ) append( &start, i );
        else insert( &start, i );
    }

    printList( start );

    return 0;
}

它的输出是

9 7 5 3 1 2 4 6 8 10

Answer 6

当您在 C 中传递参数时，它会创建一个本地副本供函数使用。当您在函数内部修改参数时，它只会更改本地副本。

void f1( int a )
{
    a = 1; // modification does not affect the calling function
}

int b=0;
f1( b );
assert( b == 0 ); // b was not changed by f

在C（或C-style C++）中，如果你想让一个函数修改一个参数，你需要把它作为一个指针来传递：

void f2( int * a )
{
    (*a) = 1;
}

int b=0;
f2( &b );
assert( b == 1 ); // b was changed by f

如果该参数已经是指针类型，则需要将其作为指向指针的指针传递：

void f3( int * * a )
{
    (*a) = (int*) malloc(sizeof(int));
    (**a) = 1;
}

int * b = NULL;
f3( &b );
assert( b != NULL ); // the pointer was initialized
assert( *b == 1 ); // the pointed-to value was initialized

C++ 中的赋值过程可以稍微简单一些，因为您可以使用 reference parameters 而不是显式指定指针。

节点插入、链表

Node Insertion,Linked Lists

c

pointers

linked-list

singly-linked-list