时间戳

首页 > 解决方案 > 在 C++ 中实现简单链表的问题，没有输出

c++ - 在 C++ 中实现简单链表的问题，没有输出

问题描述

对于我的 C++ 编程课程，我的任务是使用我自己的函数来实现一个简单addElement()的链表。printList()deleteList()

当我编译并运行以下程序时，没有任何反应。我没有收到任何警告，并且使用 valgrind 我找不到任何问题。

我正在使用的程序代码如下：

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

我不知道为什么我的代码不起作用并产生输出。请帮助和亲切的问候

标签： c++listpointerslinked-list

解决方案

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

错在几个方面：

  • head是这个函数中的一个局部变量，改变它对外界没有影响，你应该改变*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)".

其次，如果您希望将您的项目附加到列表的末尾（更常见的要求），您可以通过几种方式做到这一点。第一个是搜索最后一个，然后在后面附加它：

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

最后，虽然我意识到您仍然是一个相对初学者，但您至少应该了解封装（信息隐藏）的好处。一个适当的实现将每个类中的数据作为私有成员，只能由类本身的函数修改（当然，当然是在外部调用者的请求下）。

就目前而言，我可以编写可以轻松修改类的内部数据（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;
}

推荐阅读