在c ++中实现简单链表的问题

Question

对于我的C ++编程课程，我的任务是实现一个简单的链表具有addElement，printList和deleteList函数。现在，我有以下代码：

#include <iostream>

using namespace std;

struct Node {
  int data;
  Node *next;
  Node(int i) : data(i), next(nullptr) {}
  friend ostream &operator<<(ostream &os, const Node &n) {
    os << "Node\n"
       << "\tdata: " << n.data << "\n\tthis: " << &n << "\n\tnext: " << n.next;
    return os;
  }
};

void addElement(Node **head, int data);

void printList(Node *head);

void deleteList(Node *head);

void deleteList(Node *head) {
  Node *next = head;
  while (next) {
    Node *deleteMe = next;
    next = next->next;
    delete deleteMe;
  }
}

void addElement(Node **head, int data) {
  Node *n = new Node(data);
  n->next = *head;
  head = &n;
}

void printList(Node *head) {
  Node *next = head;
  while(next) {
    cout << next->data;
    next = next->next;
  }
}

int main() {
  Node *list = nullptr;
  addElement(&list, 1);
  addElement(&list, 2);
  addElement(&list, 3);
  addElement(&list, 4);
  printList(list);
  deleteList(list);
  return 0;
}

我真的不知道为什么我的代码不起作用。这意味着，当我编译并运行程序时，什么也没发生。我没有收到任何警告，使用valgrind我找不到任何错误。请帮助和问候

Answer 1

void addElement(Node **head, int data) {
  Node *n = new Node(data);
  n->next = *head;
  head = &n;
}

有几种错误：

• head是此函数中的local变量，更改它不会对外界产生影响，您应该更改*head;和
• n是已经指向节点的指针，您应该直接使用它，而不是使用它的地址。

换句话说，代码的最后一行应该是：

*head = n;

---

还有其他几点。首先，如果您只是学习在C ++中使用引用，则可以避免C中普遍存在的所有双指针问题，这是后者语言的一大优势。您的代码将变为：

void addElement(Node *&head, int data) {
  Node *n = new Node(data);
  n->next = head;
  head = n;
}

// Call with: "addElement(list, 1)".

第二，如果要将项目追加到列表的[[end（更常见的要求）”，则可以通过两种方法来实现。第一个是搜索最后一个，然后在其后追加：

void addElement(Node *&head, int data) {
  Node *n = new Node(data);
    if (head == nullptr) {
        head = n;
    } else {
        Node *curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = n;
    }
}

第二个（效率更高）是也要维护tail元素，以便它始终可用，而您不必在每次插入时都进行搜索。最好将功能拆分为单独的List和Node类，例如：
#include <iostream>

using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int i) : data(i), next(nullptr) {}
};

struct List {
    Node *head;
    Node *tail;
    List() : head(nullptr), tail(nullptr) {}
};

void deleteList(List *&list) {
    Node *curr = list->head;
    while (curr != nullptr) {
        Node *deleteMe = curr;
        curr = curr->next;
        delete deleteMe;
    }
    delete list;
    list = nullptr;
}

void addElement(List *list, int data) {
    Node *n = new Node(data);
    if (list->head == nullptr) {
        list->head = list->tail = n;
    } else {
        list->tail->next = n;
        list->tail = n;
    }
}

void printList(List *list) {
    Node *curr = list->head;
    while (curr != nullptr) {
        cout << curr->data;
        curr = curr->next;
    }
    cout << '\n';
}

int main() {
    List *list = new List();

    addElement(list, 1);
    addElement(list, 2);
    addElement(list, 3);
    addElement(list, 4);

    printList(list);

    deleteList(list);

    return 0;
}

并且，最后，尽管我意识到您仍然是一个相对入门的人，但您至少应该
意识到

封装（信息隐藏）的好处。适当的实现是将每个类中的数据作为private成员，只能通过该类本身内的函数进行修改（当然，当然也应外部调用者的请求）。目前，我可以编写代码来轻松修改您的类的内部数据（data和next），从而引起严重的问题。如果内部数据是私有的，则可以更好地防止这种情况。

尽管我不建议您将此代码用于您的作业（假设这是教育性的工作，但无论如何我都会将其包括在内以供您检查：

#include <iostream>
#include <functional>

using namespace std;

// Only used within List and private there so leave as public.

struct Node {
    Node(int value) : m_data(value), m_next(nullptr) {}
    int m_data;
    Node *m_next;
};

// Properly encapsulae to protect memebrs.

class List {
public:
    List() : m_head(nullptr), m_tail(nullptr) {}
    ~List() { clearAll(); }
    void clearAll();
    void addElement(int data);
    void traverse(const std::function<void(int)> &callback);
private:
    Node *m_head;
    Node *m_tail;
};

// Clear all items in list.

void List::clearAll() {
    Node *curr = m_head;
    while (curr != nullptr) {
        Node *deleteMe = curr;
        curr = curr->m_next;
        delete deleteMe;
    }
    m_head = m_tail = nullptr;
}

// Add an item to list.

void List::addElement(int data) {
    Node *node = new Node(data);
    if (m_head == nullptr) {
        m_head = m_tail = node;
    } else {
        m_tail->m_next = node;
        m_tail = node;
    }
}

// Traverse list, calling a callback for each item.

void List::traverse(const std::function<void(int)> &callback) {
    Node *curr = m_head;
    while (curr != nullptr) {
        callback(curr->m_data);
        curr = curr->m_next;
    }
}

// Test harness for the code above.

int main() {
    List list; // could also 'new' this but not needed.

    list.addElement(1);
    list.addElement(2);
    list.addElement(3);
    list.addElement(4);

     // Advanced lambda stuff for callback.

    std::cout << "Items are:";
    list.traverse([](int i) -> void {
        std::cout << " " << i;
    });
    std::cout << "\n";

    return 0;
}