Поодиночке связанного списка c++реализации


Связанный Список В C++

Я новичок в данных структурах , и я должен реализовать мои собственные структуры данных для проекта. Я сделал это работать поодиночке связанный список структура данных в языке C++. Я хотел бы попросить всех, кто более опытнее меня в этом вопросе, если моя реализация-это достаточно оптимизирован, и если мое использование и распределение памяти нормально работает (потому что я думаю, что моя память может быть нарушена). Любые другие предложения и исправления приветствуются.

#pragma once
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include <limits>


using namespace std;

template <class T>
struct node
{
    T data;
    node<T> *next;
};

template <class T>
class SLL
{
        private:
        node<T> *head, *tail;
        public:

        SLL() // Constructor
        {
            head = nullptr;
            tail = nullptr;
            cout << "Constructor Called" << '\n';
        }


        ~SLL() // Destructor
        {
            int index = 1;
            node<T>* tempo;
            while(head != nullptr)
            {
                tempo = head->next;
                delete head;
                head = tempo;
                cout << "Destructor Called "<< "Destroying node number "<< index << '\n';
                index++;
            }
        }

        void createnode(T value)

        {
            node<T> *temp = new node<T>;
            temp->data = value;
            temp->next = nullptr;
            if(head == nullptr)
            {
                head = temp;
                tail = temp;
                temp = nullptr;
            }
            else
            {
                tail->next = temp;
                tail = temp;
            }
        }


        void display()
        {
            node<T> *temp = new node<T>;
            temp = head;
            while(temp != nullptr)
            {
                cout << temp->data <<" ";
                temp = temp->next;
            }
            cout << '\n';
        }


        void insert_start(T value)

        {
            node<T> *temp = new node<T>;
            temp->data = value;
            temp->next = head;
            head = temp;
        }



        void insert_position(int pos, T value)

        {
            node<T> *pre = new node<T>;
            node<T> *cur = new node<T>;
            node<T> *temp = new node<T>;
            cur = head;
            for(int i=1; i<pos; i++)
            {
                pre = cur;
                cur = cur->next;
            }
            temp->data = value;
            pre->next = temp;
            temp->next = cur;
        }


        void delete_first()
        {
            node<T> *temp = new node<T>;
            temp = head;
            head = head->next;
            delete temp;
        }


        void delete_last()
        {
            node<T> *current = new node<T>;
            node<T> *previous = new node<T>;
            current = head;
            while(current->next != nullptr)
            {
                previous = current;
                current = current->next;
            }
            tail = previous;
            previous->next = nullptr;
            delete current;
        }


        void delete_position(T pos)

        {
            node<T> *current = new node<T>;
            node<T> *previous = new node<T>;
            current = head;
            for(int i=1; i<pos; i++)
            {
                previous = current;
                current = current->next;
            }
            previous->next = current->next;
        }

        int length() const{

            node<T> *current = head;
            int len = 0;
            while(current){
                len++;
                current = current->next;
            }
            cout << "The lists length is: " << len << '\n';
            return len;
        }



        T find(int k)
        {
            node<T> *current = new node<T>;

            if(k < 1){
                cout << "Invalid Index point" << '\n';
                throw std::out_of_range ("Invalid Index point");
            }
            if(k > length()){
                cout << "Index Out of Bounds" << '\n';
                throw std::out_of_range ("Invalid Index point");
            }
            current = head;
            int index = 1;
            while (index < k && current){
                current = current->next;
                index++;
            }
            if(current){
                cout << "In index point: " << k << " || " << " The value is: "<< current->data << '\n';
                return current->data;
            }
        }

        int search(const T& x) const{

            node<T> *current = new node<T>;
            current = head;
            int index = 1;
            while (current && current->data != x){
                current = current->next;
                index++;
            }
            if(current){
                cout << "The value: " << x << " || " << "Was found in index point: " << index << '\n';
                return index;
            }
            return 0;
        }

        bool isempty(){

            if(head == nullptr){
                cout << "The list is empty" << '\n';
                return true;
            }
            cout << "The list is NOT empty" << '\n';
            return false;
        }

        T const findbig(){
            T max;
            node<T> *current = new node<T>;
            node<T> *nn = new node<T>;
            nn = head->next;
            current = head;
            max = std::numeric_limits<T>::min();
            int index = 1;
            while(current){
                if(current->data > max){
                    max = current->data;
                }
                current = current->next;
                index++;
            }
            cout << "The BIGGEST value found in the list is: " << max << '\n';
            return max;
            }

            T const findsmall(){
                T min;
                node<T> *current = new node<T>;
                current = head;
                min = std::numeric_limits<T>::max();
                int index = 1;
                while(current){
                    if(current->data < min){
                        min = current->data;
                    }
                    current = current->next;
                    index++;
                }
                cout << "The LOWEST value found in the list is: " << min << '\n';
                return min;
                }

};

#endif


Комментарии
4 ответа

Мне это нравится.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

Но это не очень уникальный. Если использовать в большом проекте это может конфликтовать с другими охранниками. Я обычно включаю пространство имен в гвардии. В качестве альтернативы вы можете создать GUID.

Не делай этого.

using namespace std;

Более подробно можно ознакомиться здесь почему “с помощью пространства имен std” считается плохой практикой?

Следует отметить, что стандартное пространство имен называется std и не standard поэтому она не стала обузой для обозначения объектов в стандартные пространства имен std::.

Весь код должен быть внутри пространства имен.
Зарегистрировать домен Spyros.com затем используйте namespace Spyros { весь ваш код.

Объект узел не должны быть открытыми для пользователя.

template <class T>
struct node
{
T data;
node<T> *next;
};

Я хотел бы отметить, что очень распространенной конвенции, чтобы сделать определенные типы пользователей имеют начальную букву Капитолия. В то время как переменные и функции имеют начальную букву в нижнем регистре.

Это позволяет различать два:

 Node(1,2);  // creating an object of type Node
node(1,2); // calling a function node()

Сделать это частный член класса протокол SSL.
Любопытно, почему вы выбрали односвязанный список. Это гораздо легче реализовать двусвязный список.

Пожалуйста, объявите один член каждой линии.

        node<T> *head, *tail;

Также * является частью типа. Поэтому положите его рядом с типом. Путь вы делаете это очень нравится в C++ информация тип гораздо важнее.

        node<T>*  head;
node<T>* tail;

Конструктор

Это хорошо:

        SLL() // Constructor
{
head = nullptr;
tail = nullptr;
cout << "Constructor Called" << '\n';
}

Но это лучше:

        SLL() // Constructor
: head(nullptr)
, tail(nullptr)
{
cout << "Constructor Called" << '\n';
}

Предпочитаю списков инициализаторов.
Это позволит членам быть инициализирован дважды (один раз в процессе инициализации и сразу в тело конструктора).

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

По существу: если вы определите их компилятор генерирует три метода для вас. Обычно, если нужно определить любым из этих методов вы действительно должны определить все три.

Три:

  ~SLL();                      // Destructor.
SLL(SLL const&); // Copy Constructor
SLL& operator=(SLL const&); // Copy Assignment

Определите деструктор (и управления ресурсами, поэтому работа). Поэтому вы должны определить два других (потому что реализация по умолчанию не делает управление ресурсами).

В настоящее время ваш код будет перерыв, если вы копируете список.

  {
SLL<int> list1;
list1.createnode(1);

SLL<int> list2(list1); // Copy constructed

SLL<int> list3;
list3 = list2; // Copy Assignment.
}
// All three lists point at the same node internally.
// Thus the destructor of all three objects will destroy the
// same node.

Деструктор

Это выглядит хорошо.

Методы

Ваши методы не соответствуют стандартным правилам именования. Вы должны смотреть на стандартные библиотеки и попробуйте подражать конвенций, которые они используют здесь.

Общие Замечания.

Проходя т по значению.

        void createnode(T value)

Это нормально для простых типов, как int. Но что, если T это вектор или другой список или некоторых других крупных объектов. При передаче по значению создается копия. В результате мы обычно проходим мимо const ссылка на вызываемую функцию, то можно сделать копию, если они хотят или просто читать его, если они не хотят копия.

        void createnode(T const& value)

Это может быть упрощена:

            node<T> *temp = new node<T>;
temp->data = value;
temp->next = nullptr;

Попробовать

 node<T>* temp = new node<T>(value, nullptr);

Отображение функция список-это нормально. Но это может быть полезно для просмотра других потоков (с std::cout находятся не только тип потока).

        void display()

Изменение

        void display(std::ostream& str = std::cout) const // display does not change the list so mark it const.

Используйте str параметр как поток. По умолчанию std::cout но вы можете пройти все (в том числе файл.

Следует также отметить, что в C++ стандартная способ печати-то это использовать operator<<. Мы можем определить это с точки зрения display() как это.

        friend std::ostream& operator<<(std::ostream& os, SSL const& list) {
list.display(os);
return os;
}

Теперь вы можете печатать поток в нормальном С++ способом.

В этой функции вы предполагаете, что pos является действительным.

        void insert_position(int pos, T value)

Дела пойдут совсем неправильно, если pos больше, чем количество элементов. Вы должны исправить это.

Эти два звонка, чтобы новые не нужны. Они вызывают у вас утечка памяти.

            node<T> *pre = new node<T>;
node<T> *cur = new node<T>;

Просто установите их на nullptr;

            node<T> *pre = nullptr;
node<T> *cur = nullptr;

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

Ты опять утечка памяти в удалите:

        void delete_first()
{
node<T> *temp = new node<T>;

void delete_last()
{
node<T> *current = new node<T>;
node<T> *previous = new node<T>;

В удалении вы забыли, чтобы проверить, если список пуст. Это будет вызывать некоторые вопросы. Вы должны рассмотреть ваши удалить реализаций для пустого ящика списка.

12
ответ дан 27 марта 2018 в 05:03 Источник Поделиться

не делай этого:

using namespace std;

Это позволит создать много конфликтов пространств имен. Пишу std:: где вам нужно разве это не ужасно.

У вас есть деструктор, так что вы также должны создать копировать и перемещать конструкторы, а также копировать и перемещать назначить перегрузок, Так что вы следовать правилу 5.

Создание узла делает дополнительную копию, когда это не нужно. И пусть стоимость магазин быть инициализирована в месте:

void createnode(T value)
{
node<T> *temp = new node<T>(std::move(value));
temp->next = nullptr;
if(head == nullptr)
{
head = temp;
tail = temp;
temp = nullptr;
}
else
{
tail->next = temp;
tail = temp;
}
}

template< class... Args >
void emplacenode(Args&&... args)
{
node<T> *temp = new node<T>(std::forward(args)...);//add constructor to init data.
temp->next = nullptr;
if(head == nullptr)
{
head = temp;
tail = temp;
temp = nullptr;
}
else
{
tail->next = temp;
tail = temp;
}
}

insert_start и insert_position не делай ничего с Т передают. insert_position также утечек 2 созданных узлов.

На самом деле очень много функций node<T> *current = new node<T>; что получает перезаписаны сразу. Это ужасная утечка. Если вам нужно инициализировать значение предпочитаю nullptr.

10
ответ дан 27 марта 2018 в 04:03 Источник Поделиться


  1. Использовать либо включить-охранники или нестандартных, но распространенных #pragma onceНе обе. Если вы настаиваете на использовании обоих, изменить порядок, как эти компиляторы оптимизация включает-охранники, как правило, настаивают на только комментарии и пробельные находясь вне гв.

  2. node реализация-деталь SLL. Как таковая, она должна быть в закрытой части SLL и подбирают шаблон-аргумент от этого.

  3. Никогда не используйте using namespace std; в Include-файле, не в том, что он гораздо лучше в исходный файл. Читать "Почему “с помощью пространства имен std;” считается плохой практикой?" по причинам.

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

  5. Рассмотрите возможность использования класса-инициализаторов для членов, и default-ную по умолчанию конструктор.

  6. Вы нарушаете правила 3 / 5 / 0. Как пользовательская dtor сигналы, ваш SLL владеет узлов. Так что копия-конструктор по умолчанию и копирования и присваивания, очевидно, неправильно.

  7. Используйте стандартный-библиотека-соглашения для имен. В противном случае, ваш контейнер несовместима со стандартной библиотеке. В качестве примера, см. std::forward_list.

  8. Если добавить итератор-интерфейс, много функций можно заменить на один вызов стандартного алгоритма.

  9. Считать ли вместо передачи T по стоимости, она не может быть более эффективным, чтобы иметь как постоянную ссылку и ссылку rvalue версии.

  10. Установка-строительства стоимость нового узла также может быть намного более эффективным. Другие методы могут делегировать без потери эффективности.

7
ответ дан 27 марта 2018 в 04:03 Источник Поделиться

Длина

Вы предложить способ вычисления длины списка. Но с момента создания списка, вы должны быть в состоянии отслеживать эту длину. Если вы добавить собственный счетчик, инкрементировать его при каждом добавлении узла и уменьшить его всякий раз, когда узел удаляется, вы должны быть в состоянии мгновенно обеспечить длину, вместо того, чтобы вычислять его каждый раз, когда пользователь запрашивает его.

Повторяющегося кода

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

Вы могли бы переопределить эти вызвав последнего:

void delete_first()
{
delete_position(1);
}

void delete_last()
{
delete_position(length);
}

Подобную вещь для методов вставки:

void insert_start(T value)
{
insert_position(value, 1);
}

Ошибка сегментирования

В find вы проверить вашу позицию входы:

   T find(int k)
{
if(k < 1){
cout << "Invalid Index point" << '\n';
throw std::out_of_range ("Invalid Index point");
}
if(k > length()){
cout << "Index Out of Bounds" << '\n';
throw std::out_of_range ("Invalid Index point");
}

Вы не сделаете этого в delete_position хотя. Если у вас есть список длиной 4, звонок delete_position(10) будет выглядеть прошлое в конец списка. Это проблема. Одним это легко исправить той же проверки, как указано выше.

Вы наверное также хотите, чтобы проверить вход для insert_position. Вы не хотите должность <1 в качестве входных данных, и не требуется ввода последних в конец списка.

6
ответ дан 27 марта 2018 в 07:03 Источник Поделиться