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

Question

我需要创建一个程序来连接两个链表，然后再使用全局指针作为列表的头部，但现在我需要在本地制作它，以便我可以插入新的元素(node(到它们中的每一个，但我在双指针方面遇到了问题，不确定何时使用**，何时使用*和何时&。我可以找到任何类似的例子。 下面是我现在所拥有的。

#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

程序中除了运算符new之外，程序中没有任何C++。因此，如果要用运算符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++那么您应该将列表定义为一个类。此外，如果将新节点附加到单链列表的尾部，则应将列表定义为单链双侧列表。

这是一个演示程序。

#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

Answer 2

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

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

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

尽管这不是C++编程方式，但它C++代码也是有效的(我不确定标头(。

#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);
}