c++ - 你将如何编写一个函数来创建一个链表？

Question

我想知道是否可以创建一个创建链接列表的函数，这是我的尝试，如果有人能告诉我这是否正确，我将不胜感激。

逻辑如下：

• 取一个起始节点，创建的链表将连接到该节点
• 创建所有需要创建的节点并将它们的内存地址存储在一个向量中
• 遍历连接所有节点的向量

#include <iostream>
#include <vector>
using namespace std;

class node{
    public:;
    int value;
    node *next;

    node():value(0),next(NULL){};
    
};

void CreateList(node& starting_node, int number_of_nodes_to_create){



    // Keep track of all the nodes addresses that need to be created

    vector <node*> nodes = {};
    // Create the nodes
    for (int i = 0; i < number_of_nodes_to_create;i++){
        node *temp = new node;
        nodes.push_back(temp);
    }

    // Attach the first created node to the starting node
    starting_node.next = nodes[0];

    // We now have all the new nodes, now we just need to link them all up with pointers

    

    for (int i = 0; i < nodes.size()-1;i++){

        nodes[i] ->next = nodes[i+1];

    }



}

我是初学者，欢迎大家批评！

标签： c++

Answer 1

你根本不需要vector。您的功能可以简化为：

#include <iostream>
#include <vector>
using namespace std;

class node{
public:
    int value;
    node *next;

    node() : value(0), next(NULL) {}
};

void CreateList(node* &starting_node, int number_of_nodes_to_create){

    // if the list already exists, find the end of it...
    node **n = &starting_node;
    while (*n) {
        n = &((*n)->next);
    }

    // Create the nodes
    while (number_of_nodes_to_create > 0) {
        *n = new node;
        n = &((*n)->next);
        --number_of_nodes_to_create;
    }
}

void DestroyList(node *starting_node) {
    while (starting_node) {
        node *n = starting_node->next;
        delete starting_node;
        starting_node = n;
    }
}

int main() {
    node* head = NULL;
    CreateList(head, 5);
    ...
    DestroyList(head);
}

在线演示

但是，列表创建通常不会将现有节点作为输入。通常创建应该创建列表，然后返回第一个（头）节点，例如：

#include <iostream>
#include <vector>
using namespace std;

class node{
public:
    int value;
    node *next;

    node() : value(0), next(NULL) {}
};

node* CreateList(int number_of_nodes_to_create){
    node *head = NULL, **n = &head;
    while (number_of_nodes_to_create > 0) {
        *n = new node;
        n = &((*n)->next);
        --number_of_nodes_to_create;
    }
    return head;
}

void DestroyList(node *head) {
    while (head) {
        node *n = head->next;
        delete head;
        head = n;
    }
}

int main() {
    node* head = CreateList(5);
    ...
    DestroyList(head);
}

在线演示