插入函数在链表尾部插入元素

Question

我想实现在链表尾部插入元素，我想使用成员函数来实现，目前我可以通过在外部创建一个函数来实现of 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;
}

看到了live on Coliru.

还有：avoid using 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;
}

看到了live on Coliru.

Answer 2

仅通过查看您的 insert 当前所做的事情，使其成为 node 的成员是没有意义的。您可以这样称呼您的 insert：

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

创建一个包含单个元素的列表。另一方面，在拥有 node.

类型的实例之前，您不能调用 node 的成员函数

如果你写一个 class 表示列表，而不仅仅是单个节点，那么转换会更简单。从这个开始：

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

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

linked_list l;
l.insert(42);

您需要做的就是将自由函数移动到 class 中，而不是使用参数 head，而是使用成员 head。也不再需要 return 头部了：

#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 return，如果它有错误，那么它仍然有现在是一个错误 ;)。您还应该为 node 和 linked_list 以及析构函数提供适当的构造函数，因为目前这会泄漏所有分配的内存。最后但同样重要的是，您需要阅读 3/5 规则：What is The Rule of Three?

插入函数在链表尾部插入元素

insertion function to insert elements in a linked list at tail

c++

singly-linked-list

member-function-pointers