谁能帮我解决我的链表错误？

Question

我的代码有问题。我需要编写一个程序来创建链表并执行插入、从头删除、从尾删除和打印。程序中的一切工作正常，但删除第一个节点功能。它在打印功能中抛出错误（在下面张贴了错误图片）。有谁知道这似乎是什么问题？删除最后一个节点的功能可以完美打印。

链表程序：

struct Node {
    int data;
    Node* next;
};

void insert(Node** head,int n) //insertion method
{
    Node* newNode = new Node;
    newNode->data = n;
    newNode->next = (*head);
    (*head) = newNode;
}

Node* deleteFront(struct Node* head)//deleting first node in the list
{
    if (head == NULL)
        return NULL;
    else
    {
        Node* t = head;
        head = head->next;
        free(t);
        t = NULL;
    }

    return head; 
}

Node* deleteEnd(struct Node* head)//deleting last node in the list
{
    if (head == NULL)
        return NULL;
    else if (head->next == NULL) {
        free(head);
        head = NULL;
    }
    else {
        Node* prev = head;
        Node* prev2 = head;

        while (prev->next != NULL)
        {
            prev2 = prev;
            prev = prev->next;
        }

        prev2->next = NULL;
        free(prev);
        prev = NULL;
    }

    return head;
}

void printLL(Node* h)
{
    while (h != NULL)
    {
        cout << h->data << " ";
        h = h->next;
    }

    cout << endl;
}

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    insert(&n, 60);
    insert(&n, 40);
    insert(&n, 20);
    printLL(n);

    deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);
}

错误图片：

error

output

Answer 1

由于您要在 deleteFront(n) 和 deleteLast(n) 中返回 head，但是您不会在 main() 中更新 head。这就是为什么它的 n 指向一些垃圾内存。通过将 head 存储在 n 变量中来更新您的 main()。

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    insert(&n, 60);
    insert(&n, 40);
    insert(&n, 20);
    printLL(n);

    n = deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    n = deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);

}

Answer 2

放轻松。我读了你的代码，逻辑上没有错误。但是，在参数的选择上存在一些错误。 insert中没有必要使用**。使用*可以满足要求，使用&实现对链表的赋值。 deleteFront 和 deleteEnd 也是如此。我修改了你的代码，现在程序可以正常运行，希望对你有帮助。

#include<iostream>
using namespace std;
struct Node {
    int data;
    Node* next;
};

void insert(Node*& head, int n) //insertion method
{
    Node* newNode = new Node;
    newNode->data = n;
    newNode->next = head;
    head = newNode;
}

Node* deleteFront(struct Node*& head)//deleting first node in the list
{
    if (head == NULL)
        return NULL;
    else
    {
        Node* t = head;
        head = head->next;
        free(t);
        t = NULL;
    }

    return head;
}

Node* deleteEnd(struct Node*& head)//deleting last node in the list
{
    if (head == NULL)
        return NULL;
    else if (head->next == NULL) {
        free(head);
        head = NULL;
    }
    else {
        Node* prev = head;
        Node* prev2 = head;

        while (prev->next != NULL)
        {
            prev2 = prev;
            prev = prev->next;
        }

        prev2->next = NULL;
        free(prev);
        prev = NULL;
    }

    return head;
}

void printLL(Node* h)
{
    while (h != NULL)
    {
        cout << h->data << " ";
        h = h->next;
    }

    cout << endl;
}

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    
    insert(n, 60);
    insert(n, 40);
    insert(n, 20);
    printLL(n);

    deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);
}

Answer 3

您的代码中的错误已在其他答案中提及，并提出了修复建议。

我想对您的链表设计再补充一点意见。在标准实现中，Node 对外界不可见。 Node 不是链表。 linked 列表包含 Nodes。因此，您将创建一个 class List，它将包含 Node 的定义和指向第一个节点实例的 head 指针。

然后您将所有函数作为方法添加到外部 class List。这些方法适用于内部 Node-chain。根据面向对象模型，您将封装方法的内部并仅向外界公开需要的内容。

您还应该注意的是，您的列表只是转发列表。它只有一个 link 到下一个元素。这使得一些操作变得困难，因为您可能需要始终从列表的开头开始遍历要操作的元素。查看您的函数 delete_end。在这里你甚至需要记住前面的元素。

在双重 linked 列表中，您也可以简单地访问前一个元素。

因此，如果您检查 std::forward_list 的 CPP 参考，您会发现一些听起来可能很奇怪的函数，例如 insert_after 或 erase_after 或迭代器 before_begin。这是仅具有前向引用的所有结果。像 delete_last 这样的函数在 CPP 语言中是 pop_back，甚至不存在。

因此您可能需要确认，如果您应该实施单 linked 列表或双 linked 列表。

为了让您更清楚地看到这一点，我为您创建了一个 linked 列表的完整示例代码。

这里我还添加了简单的 iterator 功能，允许以方便的方式使用 class，例如基于范围的 for 循环或 std::algorithms.

您可以利用这段代码来获得一些自己实现的想法。

#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>

// Very simple implementation of a forward list
class SinglyLinkedList {

    // The node
    struct Node {
        int data{};     // Data. Would normally be a templated argument
        Node* next{};   // And the pointer to the next node
       
        Node(int i, Node* n=nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
    };

    Node* head{};       // This is the start of the list
    // It would be advisable to have a tail pointer. We use the more inefficient approach here
    Node* getLast() { Node* n{ head }; while (n and n->next) n = n->next; return n; }

public:
    // Constructor / Destructor --------------------------------------------------------------------------------------------------------
    ~SinglyLinkedList() { clear(); }

    // Default constuctor
    SinglyLinkedList() {}   // Default

    // From an initialization list
    SinglyLinkedList(const std::initializer_list<int>& il) { clear();  for (const int i : il) push_back(i); } // From initializer list

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const int i : other) push_back(i); }

    // Move constructor. Will steal the elements from the other 
    SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }

    // Assignment operator
    SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const int i : other) push_back(i); }

    // Move assignment operator 
    SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }

    // Housekeeping --------------------------------------------------------------------------------------------------------------
    void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
    int empty() { return head == nullptr; }
    int size() { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }

    // Modify content --------------------------------------------------------------------------------------------------------------
    void push_front(int i) { Node* n = new Node(i); n->next = head; head = n; };
    void push_back(int i) { Node* n = new Node(i); Node* l = getLast();if (l) l->next = n; else head = n; }
    void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
    void pop_back() { // This is a little bit more difficult in a singly linked list
        if (head) {
            Node* n{ head }, *previous{};
            while (n and n->next) {
                previous = n;
                n = n->next;
            }
            delete n;
            if (previous)
                previous->next = nullptr;
            else
                head->next = nullptr;
        }
    }

    // Access elements --------------------------------------------------------------------------------
    int front() { return head ? head->data : 0; };
    int back() { Node* n = getLast(); return n ? n->data: 0; }

    // Add iterator properties to class ---------------------------------------------------------------
    struct iterator {                           // Local class for iterator
        Node* iter{};                           // Iterator is basically a pointer to the node
 
        // Define alias names necessary for the iterator functionality
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = int;
        using pointer = int*;
        using reference = int&;

        // Constructor
        iterator() {}
        iterator(Node* n) : iter(n) {}

        // Dereferencing
        reference operator *() const { return iter->data; }
        pointer operator ->() const { return &iter->data; }

        // Aithmetic operations
        iterator& operator ++() { if (iter) iter = iter->next; return *this;  }
        iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }
        iterator operator +(const difference_type& n) const { iterator temp{ *this };  difference_type k{ n }; while (k--)++temp; return temp; }
        iterator& operator +=(const difference_type& n) { difference_type k{ n }; while (k--)++* this; return *this; };

        // Comparison
        bool operator != (const iterator& other) const { return iter != other.iter; }
        bool operator == (const iterator& other) const { return iter == other.iter; }
        bool operator < (const iterator& other) const { return iter < other.iter; }
        bool operator > (const iterator& other) const { return iter > other.iter; }
        bool operator <= (const iterator& other) const { return iter <= other.iter; }
        bool operator >= (const iterator& other) const { return iter >= other.iter; }

        // Difference. Also complicated, because no random access
        difference_type operator-(const iterator& other) const {
            difference_type result{};
            Node* n{ iter }; 
            while (n and n != other.iter) { 
                ++result; 
                n = n->next; 
            } 
            return result;
        }
    };

    // Begin and end function to initialize an iterator
    iterator begin() const { return iterator(head); }
    iterator end() const { return iterator(); }
    
    // Functions typcical for forward lists ----------------------------------------------------------------------
    // Easy, becuase we can operate form the current iterator and do not need the "previous" element
    iterator insertAfter(iterator& pos, const int i) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* n = new Node(i, pos.iter->next);
            pos.iter->next = n;
            result = n;
        }
        return result;
    }
    iterator eraseAfter(iterator& pos) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* tmp = pos.iter->next->next;
            delete pos.iter->next;
            pos.iter->next = tmp;
            result = pos.iter->next;
        }
        return result;
    }
};
// Test/Driver Code
int main() {

    // Example for initilizer list
    SinglyLinkedList sllbase{5,6,7,8,9,10,11,12,13,14,15};
    // Show move constructor
    SinglyLinkedList sll(std::move(sllbase));

    // Add some values in the front
    sll.push_front(4);
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);

    // Delete 1st element (Number 1)
    sll.pop_front();
    // Delete last element
    sll.pop_back();

    // Use a std::algorithm on our custom linked list. Works because we have an interator
    SinglyLinkedList::iterator iter = std::find(sll.begin(), sll.end(), 8);

    // Now add an element after 8
    iter = sll.insertAfter(iter,88);
    // End delete the 9
    iter = sll.eraseAfter(iter);

    // Use range based for loop. Works because, we have iterators
    for (int i : sll)
        std::cout << i << ' ';
}

谁能帮我解决我的链表错误？

can anyone help me with my linked list error please?

c++

compiler-errors

linked-list

nodes

visual-studio