插入函数，用于在链表尾部插入元素

Question

我想在链表尾部插入元素，我想使用成员函数来完成它，目前我能够通过创建struct外的函数来做到这一点，请帮助我应该修改什么来实现它作为成员函数。

我的传统方法:

#include<iostream>
using namespace std;
struct node{
int data;
node *next;
};
node * Insert(int v,node *head){
if(head==NULL){
node *temp=new node;
head=temp;
temp->data=v;
temp->next=NULL;
return head;
}
else{
node *temp=head;
while(temp->next!=NULL){
temp=temp->next;
}
node *temp_new=new node;
temp_new->data=v;
temp_new->next=NULL;
temp->next=temp_new;
return head;
}
}

Answer 1

这是一个工作示例。其思想是，从成员函数中，递归地调用node::Insert，直到到达最后一个元素，然后只有在那里创建下一个元素。

#include <iostream>
struct node{
int data;
node *next = nullptr;
node *Insert(int v);
};
node *node::Insert(int v)
{
if (next == nullptr)
{
next = new node;
next->data = v;
return next;
}
else
{
return next->Insert(v);
}
}
int main()
{
node a{3};
a.Insert(2);
a.Insert(5);
std::cout << a.data << ' ' << a.next->data << ' ' << a.next->next->data << ' ' << std::endl;

return 0;
}

观看Coliru现场直播

Also: avoidusing namespace std.

添加

正如评论中所指出的，展开递归可能是一个好主意。下面是上述代码的非递归版本:

#include <iostream>
struct node{
int data;
node *next = nullptr;
node *Insert(int v);
};
node *node::Insert(int v)
{
if (next == nullptr)
{
next = new node;
next->data = v;
return next;
}
else
{
auto p = next;
while (p->next != nullptr)
p = p->next;
p->next = new node;
p = p->next;
p->data = v;
return p;
}
}
int main()
{
node a{3};
a.Insert(2);
a.Insert(5);
std::cout << a.data << ' ' << a.next->data << ' ' << a.next->next->data << ' ' << std::endl;

return 0;
}

观看Coliru现场直播

Answer 2

仅通过查看您的insert当前做什么，使其成为node的成员是没有意义的。你可以这样调用你的insert:

node* root = nullptr;
root = Insert(42,root);

创建包含单个元素的列表。另一方面，在拥有node类型的实例之前，不能调用node的成员函数。

如果您编写一个表示列表而不仅仅是单个节点的类，则转换会更简单。从下面开始:

struct node{
int data;
node *next;
};
struct linked_list {
node* head;
};

现在上面的两行看起来像这样:

linked_list l;
l.insert(42);

您所需要做的就是将自由函数移动到类中，而不是使用参数head，而是使用成员head。也不需要再返回头部了:

#include<iostream>
using namespace std;
struct node{
int data;
node *next;
};
struct linked_list {
node* head = nullptr;
void Insert(int v){
if(head==nullptr){
head =new node;
head->data=v;
head->next=nullptr;
}
else{
node *temp=head;
while(temp->next!=nullptr){
temp=temp->next;
}
node *temp_new=new node;
temp_new->data=v;
temp_new->next=nullptr;
temp->next=temp_new;
}
}
};

注意，我没有改变任何实现(只有NULL->nullptr和void返回，如果它有一个错误，那么它现在仍然有一个错误;)您还应该为node和linked_list提供适当的构造函数和析构函数，因为目前这会泄漏所有已分配的内存。最后但同样重要的是，你需要阅读3/5法则:什么是3法则?