链表与节点实现_编程黑洞网

以下是我的模板化Node和LinkedList类的实现。如果有人能向我指出我可以改进的地方，我将非常感激。

//LinkedList with SumLists()

#include <iostream>
#include <set>

using namespace std;

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

template<class T>
class LinkedList
{
public:

    Node<T> * head;
    Node<T> * tail;

    LinkedList(const LinkedList& LL);
    LinkedList& operator=(LinkedList byValList);
    LinkedList(): head(NULL), tail(NULL) {}
    LinkedList(Node<T> * newNode) : head(newNode), tail(newNode) {}
    ~LinkedList();

    static LinkedList<int> sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2);

    void insertToTail(T val);
    void insertToHead(T val);
    void print();
    void printBackwards();
};

template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& LL) : head(NULL), tail(NULL)
{
    const Node<T> * curr = LL.head;

    if (!head && curr)
    {
        head = new Node<T>(curr->data);
        tail = head;
        curr = curr->next;
    }

    while (curr)
    {
        Node<T> * newNode = new Node<T>(curr->data);
        tail->next = newNode;
        tail = newNode;
        curr = curr->next;
    }
}

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    std::swap(head, byValList.head);
    return *this;
}

template<class T>
LinkedList<T>::~LinkedList()
{
    Node<T> * curr = head;
    while (head)
    {
        head = head->next;
        delete curr;
        curr = head;
    }
}

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(val);
    if (tail == NULL)
    {
        newNode->next = tail;
        tail = newNode;
        head = newNode;
        return;
    }
    tail->next = newNode;
    tail = tail->next;
}

template<class T>
void LinkedList<T>::insertToHead(T val)
{
    Node<T> * newNode = new Node<T>(val);
    newNode->next = head;
    head = newNode;
    if (head->next == NULL)
        tail = newNode;
}

template<class T>
void LinkedList<T>::print()
{
    Node<T> * curr = head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL"<<endl;
}

template<class T>
void LinkedList<T>::printBackwards()
{
    Node<T> * curr;
    LinkedList ReversedList(new Node<T>(head->data));
    curr = head->next;
    while (curr)
    {
        ReversedList.insertToHead(curr->data);
        curr = curr->next;
    }

    curr = ReversedList.head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL\n";
}

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    Node<T>* curr1 = LL1.head;
    Node<T>* curr2 = LL2.head;

    LinkedList<int> ResultList;

    int newData;
    int carry = 0;

    while (curr1 && curr2)
    {
        newData = (curr1->data + curr2->data + carry) % 10;
        carry = (curr1->data + curr2->data + carry) / 10;
        ResultList.insertToTail(newData);

        curr1 = curr1->next;
        curr2 = curr2->next;
    }

    while (curr1 || curr2)
    {
        if (carry)
        {
            if (curr1)
                ResultList.insertToTail(curr1->data + carry);
            if (curr2)
                ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        if (curr1)
        {
            ResultList.insertToTail(curr1->data);
            curr1 = curr1->next;
        }
        if (curr2)
        {
            ResultList.insertToTail(curr2->data + carry);
            curr2 = curr2->next;

        }


    }

    return ResultList;
}

int main()
{
    LinkedList<int> LL1(new Node<int>(7));
    LL1.insertToTail(1);
    LL1.insertToTail(6);
    LL1.insertToTail(5);
    LL1.insertToTail(4);

    LinkedList<int> LL2(new Node<int>(5));
    LL2.insertToTail(9);
    LL2.insertToTail(2);

    LinkedList<int> LL = LL1.sumLists(LL1, LL2);
    LL.print();
    LL2.print();
    LL = LL2;
    LL.print();
    LL2.print();

    return 0;
}

顺便说一下，您可以删除#include ，因为在代码中没有使用它。

#1 楼

请。哦，请不要再这样做了。

using namespace std;

如果这是头文件，则您只是污染了使用该文件的任何人的全局名称空间。这将使它从任何严肃的项目中都被禁止使用。出于某种原因，这是在教科书中完成的，适用于简短的十行示例程序。但是一旦超过10行，就会出现问题。停止使用；这是个坏习惯，会使您在任何大小的项目上都遇到真正的问题。

为什么“使用命名空间标准”；认为是不好的做法吗？

您确实将标准库放在名称空间std中。因此，使用它仅需花费5个额外的字符。任何人都没有理由使用该列表来确切了解您的实现方式。也没有理由为他们提供Node类（因为您现在将需要维护该概念）。如果您不复制Node成员，它实际上不是一个复制构造函数。

std::list<T>    myList;

但是可以。我可以看到这是一种优化。
但是我个人会使用第三个构造函数。

因此已禁用赋值运算符：

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

这在C ++ 03中是正确的。但这是2014年，所有现代编译器都支持C ++ 11，并且大多数已经支持C ++ 14。因此，您应该开始使用该语言的现代版本。但是，如果将伪造的哨兵值添加到列表中，则将实现起来更加容易，因为您永远不会有NULL指针（终点没有哨兵）。 br />

Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

此时，LinkedList始终为NULL。您只需在上面设置两行即可。

注意该副本的另一件事是，如果引发异常，它将泄漏。由于您不知道next的类型是什么，因此您不知道它将如何响应复制。如果复制过程中途引发异常，则应清除到目前为止分配的所有内存，然后再让异常从构造函数中传播出去。

赋值运算符在正确的轨道上。 >

Node<T>(const Node<T>& copyNode, Node<T>* next)
    : data(copyNode.data)
    , next(next) 
{}

我会这样写：

private:
    Node<T>& operator=(const Node<T>&);

在析构函数中：
你不要使用head做任何有用的事情。删除它。

    Node<T>& operator=(const Node<T>&) = delete;

在插入方法中。我个人将返回对T的引用（请参见下文）。但是在两种插入方法中，在分配另一端之前，检查空值总是有点奇怪。我会将空测试分解为自己的方法curr，然后可以在做特殊情况代码之前测试*this。 br />

    if (!head && curr)

打印方法没有问题。但是我还要做三件事。由于empty()方法不会修改列表的内容，因此应将其标记为empty()。而不是始终打印到print()，我将输出流作为参数传递（如果未提供该参数，则默认为const。我还将编写输出运算符std::cout，因为这是C ++中的常规打印方式。 br />

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    // BUT this line is not enough
    //     Assignment should make a copy of all the elements.
    std::swap(head, byValList.head);


    // Usually this is implemented as:
    // Now you need to write a version of swap for this class
    // (both member and free standing)
    byValList.swap(*this);

    return *this;
}

向后打印时价格昂贵。
但是一旦列表反转，为什么不重新使用标准打印功能？

template<class T>
LinkedList<T>::swap(LinkedList<T>& rhs) noexcept // swap is supposed to be 
{                                                // free from exception
    std::swap(head,  rhs.head);                  // throwing
    std::swap(tail,  rhs.tail);
}

template<class T>
void swap(LinkedList<T>& lhs, LinkedList<T>& rhs) {lhs.swap(rhs);}

最后。在sumLists中。它的罚款到这一点。其中一个列表为空。但是，其中一个列表为空的第二部分过于复杂，并且您有很多嵌套的ifs。为什么不单独检查并分别处理每个列表。

    Node<T> * curr = head;

        curr = head;

您还将注意到两个循环非常相似。因此，您可以将该代码分成一个单独的方法，然后调用两次。

template<class T>
LinkedList<T>& LinkedList<T>::insertToTail(T val);

\ $ \ begingroup \ $
非常感谢您抽出宝贵的时间进行全面的审查。这对我改善C ++编程非常有帮助。
\ $ \ endgroup \ $
–耶契尔（Yechiel Labunskiy）
2014-2-27在16:53

\ $ \ begingroup \ $
Loki，我需要独立的交换功能做什么？
\ $ \ endgroup \ $
–耶契尔（Yechiel Labunskiy）
2014-2-27在18:30

\ $ \ begingroup \ $
用于Kernig查找（AKA ADL查找）的自由站立交换帮助。如果您写：swap（ll1，ll2）;其中ll1和ll2是LinkedList 然后它将使用Kernig查找来查找您的交换实现，该实现比默认交换更好。
\ $ \ endgroup \ $
–马丁·约克
2014-2-27在21:09

\ $ \ begingroup \ $
作为这个网站的长期贡献者，我认为我从未邀请您加入聊天室。随时来找常客聊天。 :)
\ $ \ endgroup \ $
–syb0rg
2014-2-28的3:40

\ $ \ begingroup \ $
@LokiAstari我对您要求不高，请在复习后在答案中添加一段以获取完整的课程代码。仅出于比较目的。您的评论非常有帮助，对于初学者来说，了解您在上述问题代码中所做的区别将更加有益。谢谢。
\ $ \ endgroup \ $
–超人
15年10月28日在10:04

#2 楼

一些观察结果：

您的数据应（可能）是私有的。否则，进取的开发人员将执行此操作：

LinkedList<int> l;
// naively delete contents of l
delete l.head;

是列表的实现细节。在类外定义它是没有意义的。

这意味着代码应如下所示：

template<class T>
class LinkedList
{
// private:
    struct Node // Node is a private implementation detail
    {
        T data;
        Node *next;
        Node(const T& d):data(d), next() {}
        Node(const Node& copyNode) : data(copyNode.data), next() {}

    private:
        Node& operator=(const Node&);
    };
    Node* head;
    Node* tail;

public:
    // ... rest of code here
};

尾部私有的，您将需要向类中添加迭代和/或数据检索API。

在设计类时，请考虑从客户端代码的角度看待它的方式，而不是它的方式。已实现（即，您正在实现“ T的实例列表”，而不是“ Node的实例列表”）。这意味着您不应让构造函数接收Node *，而应让构造函数接收T实例。

您的print和printBackwards函数应该（可能）接收输出流作为参数（然后，使用相同的代码打印到std :: ostringstream，std :: fstream，std :: cout等）。

您的赋值复制和交换实现应这样写：

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    using std::swap;        // enable ADL
    swap(*this, byValList); // implementation swaps by moving if there's a
                            // LinkedList<T>::LinkedList<T>(LinkedList<T>&&)
                            // defined; (consider defining it)

    return *this;
}

此功能可以使用std :: move：

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(std::move(val)); // <<<<< 
    // ... 
}

对于POD型T，没有它很好，但是如果我写

LinkedList<std::string> l;
std::string s{' ', 10000};
l.insertToTail(s); // creates one copy of s for argument, and one for the node

会发生什么？

\ $ \ begingroup \ $
如果存在move构造函数，则通过移动来交换实现。否则，它通过复制来完成。默认情况下，没有移动构造函数。
\ $ \ endgroup \ $
–马丁·约克
14年2月27日在16:15

\ $ \ begingroup \ $
@LokiAstari，我不知道（赞成：）。
\ $ \ endgroup \ $
–utnapistim
2014-2-27在16:42

#3 楼

我怀疑sumLists中有一个BUG： br />

if (carry)
{
    if (curr1)
        ResultList.insertToTail(curr1->data + carry);
    if (curr2)
        ResultList.insertToTail(curr2->data + carry);
    carry = 0;
    continue;
}

\ $ \ begingroup \ $
嗨，第一个答案很不错：）如果您解释了您认为的错误，也许对OP也会有所帮助，这也会带来更好的答案
\ $ \ endgroup \ $
–IEatBagels
18-10-30在19:14