C ++链表追加方法 [英] C++ linked list append method

问题描述

我正在用C ++编写一个链接列表模板类，作为我自己的练习，以帮助我重新开始C ++编程.我有以下类定义:

I am writing a linked list template class in C++ as an exercise for myself to help me get back into C++ programming. I've got the following class definition:

template <typename T>
class List
{
public:
    List();
    ~List();

    void append(T data);
    void display();
    int  count();

private:
    struct Node
    {
        T data;
        Node *next;
    } *head;
};

我有两个版本的append方法-一个有效，一个无效.我无法弄清楚在执行的操作方面有什么区别，以及为什么第二个不起作用.这是可行的方法:

I have two versions of the append method - one that works and one that doesn't. I can't figure out what the difference, in terms of the operations performed, is, and why the second one doesn't work. Here's the one that works:

template <typename T>
void List<T>::append(T data)
{
    if (head == NULL)
    {
        head = new Node;
        head->data = data;
        head->next = NULL;
    }
    else
    {
        Node *p = head, *q;
        while (p != NULL)
        {
            q = p;
            p = p->next;
        }

        p = new Node;
        p->data = data;
        p->next = NULL;
        q->next = p;
    }
}

这是一个似乎实际上没有向列表中添加任何元素的元素:

And here's the one that doesn't seem to actually add any elements to the list:

template <typename T>
void List<T>::append(T data)
{
    Node *p = head, *q = head;

    while (p != NULL)
    {
        q = p;
        p = p->next;
    }

    p = new Node;
    p->data = data;
    p->next = NULL;
    if (q != NULL)
    {
        q->next = p;
    }
}

关于为什么第二个版本不添加任何元素的任何想法?我一直在尝试将T类型设置为int.

Any ideas as to why the second version doesn't add any elements? I've been trying it with type T as int.

P.S.无论是在编译期间还是在运行期间，两个版本都不会给出任何错误或警告.

P.S. Neither version gives any errors or warnings during compilation, nor during runtime.

推荐答案

第二种方法仅处理列表为非空的情况.

The second method only handles the case where the list is non-empty.

当列表为空时，行 q->next = p; 永远不会到达，所以新元素被泄漏，在 p超出范围.

When the list is empty, the line q->next = p; is never reached, so the new element is leaked with no pointer existing to it after p goes out of scope.

如果要消除空列表的特殊情况，您想要的是 Node ** ，例如:

What you want, if you would like to eliminate the special case for empty list, is a Node **, like thus:

template <typename T>
void List<T>::append(T data)
{
    Node** q = &head; /* head acts as the first Node::next link */

    /* invariant: q points to some Node::next field (or head, which acts like one) */
    while (*q)
        q = &(*q)->next;

    /* invariant: q points to the Node::next field at the end of the chain, which is currently NULL */
    *q = new Node { data, nullptr };
}

这篇关于C ++链表追加方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！