Ссылка LinkedList с узлом

Ниже представлена ​​моя реализация шаблонов 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;
}
31 голос | спросил Yechiel Labunskiy 27 FebruaryEurope/MoscowbThu, 27 Feb 2014 17:43:11 +0400000000pmThu, 27 Feb 2014 17:43:11 +040014 2014, 17:43:11

2 ответа


29

Пожалуйста. О, пожалуйста, прекратите это делать.

using namespace std;

Если это был файл заголовка, вы просто загрязнили глобальное пространство имен для тех, кто использует ваш файл. Это приведет к запрету любого серьезного проекта. По какой-то причине это делается в учебниках и подходит для коротких десятилинейных примерных программ. Но как только вы пройдете 10 строк, у вас возникнут проблемы. Прекратите использовать его; это плохая привычка, которая приведет вас к реальным проблемам в любом проекте с приличным размером.

Почему «использование пространства имен std?» считается плохой практикой?

Вы действительно используете стандартную библиотеку в пространстве имен std. Таким образом, вам стоит всего 5 дополнительных символов.

std::list<T>    myList;

Узел представляет собой деталь реализации списка. Нет никаких оснований для того, чтобы кто-либо, пользующийся списком, точно знал, как вы это сделали. Также нет причин предоставлять им класс Node (так как теперь вам нужно будет поддерживать эту концепцию).

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

Итак, я бы сделал Node частным членом LinkedList.

На самом деле это не конструктор копирования, если вы не скопировали элемент next.

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

Но ОК. Я вижу это как оптимизацию. Но лично я бы использовал третий конструктор.

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

Затем вы можете передать NULL в качестве второго параметра, чтобы инициализировать следующий.

Итак, вы отключили оператор присваивания:

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

Это правильно в C ++ 03. Но это 2014, а C ++ 11 поддерживается всеми современными компиляторами, и большинство из них уже поддерживают C ++ 14. Поэтому вы должны начать использовать современную версию языка.

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

В вашей реализации связанного списка используется NULL в качестве терминатора (что хорошо). Но , если вы добавите значение фальшивого оповещения в свой список, это значительно упростит реализацию, так как у вас никогда не было указателей NULL (и конечных точек у дозорного органа).

В конструкторе копирования:

    if (!head && curr)

На этом этапе head всегда имеет значение NULL. Вы просто установили две строки выше.

Другое примечание о копии заключается в том, что она будет протекать, если вы выбросите исключение. Поскольку вы не знаете, что такое тип T, вы не представляете, как он будет реагировать на копирование. Если на полпути через копию выдается исключение, вы должны очистить любую выделенную память до того, как исключить распространение этого исключения из конструктора.

Вы находитесь на правильном пути с оператором присваивания.

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

В деструкторе:
Вы не используете curr, чтобы сделать что-нибудь полезное. Удалите его.

    Node<T> * curr = head;

        curr = head;

В ваших методах вставки. Я лично верну ссылку на *this (см. Ниже). Но в обоих методах вставки, которые вы проверяете на пустое, всегда немного странно, прежде чем назначать другой конец. Я бы разбил тест на пустой в свой собственный метод empty(), после чего вы можете протестировать empty() перед тем, как сделать свой специальный код кода.

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

Это позволяет использовать цепочку операторов.

LinkedList<T>  list;
list.insertToTail(1).insertToTail(2).insertToTail(3);

Ничего плохого в методе печати. Но я бы сделал еще три вещи. Поскольку метод print() не изменяет содержимое списка, он должен быть помечен как const. Вместо того, чтобы печатать на std::cout, я передавал выходной поток в качестве параметра (он может по умолчанию std::cout), когда ни один не предоставляется. оператор операционного оператора operator<<, который является обычным способом печати на C ++.

template<class T>
void LinkedList<T>::print(std::ostream& stream = std::cout) const;

std::ostream& operator<<(std::ostream& stream, LinkedList<T> const& data)
{
    data.print(stream);
    return stream;
}

Это дорогая печать, когда она сделана в обратном порядке.
Но как только вы измените список. Почему бы не повторно использовать стандартную функцию печати?

template<class T>
void LinkedList<T>::printBackwards(std::ostream& stream = std::cout) const
{
     LinkedList<T>  rev;
     for(Node<T>* curr = rev.head; curr != NULL; curr = curr->next)
     {    rev.insertToHead(curr->data);
     }
     rev.print(stream);
}

Наконец-то. В sumLists. Это хорошо. где один список пуст. Но вторая часть, где один список пуст, сложнее, и у вас много вложенных ifs. Почему бы не проверить и сделать каждый список индивидуально.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    while (curr1)
    {
        if (carry)
        {
            ResultList.insertToTail(curr1->data + carry);
            carry = 0;
            continue;
        }
        ResultList.insertToTail(curr1->data);
        curr1 = curr1->next;
    }

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

Вы также заметите, что две петли очень похожи. Таким образом, вы можете разбить этот код на отдельный метод и дважды вызвать его.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    AddStuffToListOne(curr1, ResultList);
    AddStuffToListOne(curr2, ResultList);

}
ответил Martin York 27 FebruaryEurope/MoscowbThu, 27 Feb 2014 20:10:10 +0400000000pmThu, 27 Feb 2014 20:10:10 +040014 2014, 20:10:10
8

Некоторые наблюдения:

Ваши данные должны (вероятно) быть закрытыми. В противном случае предприимчивый разработчик сделает это:

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

Node - это деталь реализации этого списка. Нет смысла определять его вне класса.

Это означает, что код должен выглядеть следующим образом:

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 *, но конструктора, получающего экземпляр 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
ответил utnapistim 27 FebruaryEurope/MoscowbThu, 27 Feb 2014 19:59:27 +0400000000pmThu, 27 Feb 2014 19:59:27 +040014 2014, 19:59:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132