如何制作带有本地声明头的链表？

Question

在我使用全局指针作为链表的头部之前，我需要制作一个连接两个链表的程序，但现在我需要在本地制作它，这样我就可以向它们中的每一个插入新元素（节点），但是我有双指针的问题，不知道什么时候用**，什么时候用*，什么时候用&。我可以找到任何类似的例子。下面是我现在的。

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

typedef struct element_{
    int x;
    struct element_ *next;
}element;


void insert(element **head, int x) {
    element *new_ = new element;
    element *p;
    new_->x = x;
    new_->next = NULL;

    if (head == NULL) {
        *head = new_;
        return;
    }
    else {
        for (p = *head;p->next != NULL;p = p->next) {}
        p->next = new_;
    }

}


int main(){
    element **head = NULL;

    insert(head,1);
    insert(head,3);
    insert(head,3);
    insert(head,4);

    for (element *p = *head;p != NULL;p = p->next){
        printf("%d ", p->x);
    }


}

Answer 1

您的代码几乎是正确的 C 代码。

如果 main 中的 head 是指向 element 的指针，则必须为其动态分配内存。它使代码变得不必要的复杂。我在 main 中创建了 head 指向 element 的指针。但是您想更改它在 insert 中的值，因此您必须通过引用传递。 C的传值方式就是传地址。 C中也没有new。使用malloc。最后记得清理。您必须为每个 malloc.

调用一个 free

如果它真的应该是 C++ 代码，您还有很多工作要做。例如，你不会使用指向指针的指针而是引用，你会使用智能指针而不是动态内存分配，...

即使这不是 C++ 编程方式，它也是有效的 C++ 代码（我不确定 headers）。

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

typedef struct element_{
    int x;
    struct element_ *next;
} element;

void insert(element **head, int x) {
    element *new_ = malloc(sizeof(element));
    element *p;
    new_->x = x;
    new_->next = NULL;

    if (*head == NULL) {
        *head = new_;
        return;
    } else {
        for (p = *head;p->next != NULL;p = p->next) {}
        p->next = new_;
    }
}

void clean(element **p) {
    if ((*p)->next != NULL) clean(&(*p)->next);
    free(*p);
    *p = NULL;
}

int main(){
    element *head = NULL;

    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 3);
    insert(&head, 4);

    for (element *p = head; p != NULL; p = p->next){
        printf("%d ", p->x);
    }

    clean(&head);
}

Answer 2

除了运算符new，程序中没有任何来自C++的东西。因此，如果用 operator new 代替 malloc 的调用，那么您将得到一个纯 C 程序。

所以 C 函数 insert 可以定义为

void insert(element **head, int x) 
{
    element *new_ = new element;

    new_->x = x;
    new_->next = NULL;

    while ( *head != NULL )
    {
        head = &( *head )->next;
    }

    *head = new_;
}

主要是你应该写

element *head = NULL;

insert( &head, 1 );
insert( &head, 3 );
insert( &head, 3 );
insert( &head, 4 );

for (element *p = head; p != NULL; p = p->next )
{
    printf("%d ", p->x);
}

看起来像 C++ 函数的东西 insert 可以按以下方式定义

void insert( element * &head, int x ) 
{
    element *new_ = new element { x, nullptr };

    element **current = &head;

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

    *current = new_;
}

主要是你应该写

element *head = nullptr;

insert( head, 1 );
insert( head, 3 );
insert( head, 3 );
insert( head, 4 );

for (element *p = head; p != nullptr; p = p->next )
{
    std::cout << p->x << ' ';
}

但要将该程序真正称为 C++ 程序，则应将列表定义为 class。此外，如果新节点附加到单向链表的尾部，那么您应该将列表定义为单向双向链表。

这是一个演示程序。

#include <iostream>
#include <functional>

class List
{
private:    
    struct Node
    {
        int data;
        Node *next;
    } *head = nullptr, *tail = nullptr;

public:
    List() = default;
    List( const List & ) = delete;
    List & operator =( const List & ) = delete;
    ~List()
    {
        clear();
    }

    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }

        tail = head;
    }

    void  push_front( int data ) 
    {
        head = new Node { data, head };
        if ( !tail ) tail = head;
    }       

    void  push_back( int data ) 
    {
        Node *node = new Node { data, nullptr };

        if ( tail )
        {
            tail = tail->next = node;
        }
        else
        {
            head = tail = node;
        }
    }       

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            std::cout << current->data << " -> ";
        }

        return std::cout << "null";
    }
};


int main()
{
    List list;

    list.push_back( 1 );
    list.push_back( 3 );
    list.push_back( 3 );
    list.push_back( 4 );

    std::cout << list << '\n';
}

它的输出是

1 -> 3 -> 3 -> 4 -> null

如何制作带有本地声明头的链表？

How to make linked list with localy declared head?

c++

linked-list

double-pointer

singly-linked-list

function-definition