Моя реализация двусвязный список на C++


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

template <class DataType>
class dList
{
private:
  // The Node Structure.
  struct Node
  {
    DataType data;
    Node *next;
    Node *prev;
  };
  // The 'head' And 'tail' Pointers.
  Node *head, *tail;
  // Miscellaneous Variables.
  int itemsInList; // The Number Of Items In The List.
public:
  // The Default Constructor.
  dList()
  {
    head = nullptr;
    tail = nullptr;
    itemsInList = 0;
  }
  // Insertion Operations.
  void insertEnd(DataType itemToInsert);
  void insertBeginning(DataType itemToInsert);
  int insertAfterNth(DataType itemToInsert, int afterNth);
  int insertAfterSpecific(DataType itemToInsert, DataType afterData);
  // Deletion Operations.
  int deleteBeginning();
  int deleteEnd();
  int deleteNthNode(int nthNode);
  int deleteSpecificNode(DataType nodeToDelete);
  // Display Operations.
  int displayF();
  int displayB();
  // Useful Utility Operations.
  int numberOfItems();
  bool isEmpty();
  DataType searchFor(DataType searchTerm);
};

// The Insert To The End Function.
template <class DataType>
void dList<DataType>::insertEnd(DataType itemToInsert)
{
  // Creating The New Node With The Item We Want To Insert First.
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  newNode->next = nullptr; // Since We Are Adding To The End, It'll Point Nowhere.
  // Checking If The List Is Full.
  if (head == nullptr)
  {
    newNode->prev = nullptr;
    head = tail = newNode;
  }
  // Otherwise (If The List Is Not Empty).
  else
  {
    newNode->prev = tail;
    tail->next = newNode;
    tail = newNode;
  }
  itemsInList++; // Increase The Items In The List.
}

// The Insert To The Beginning Function.
template <class DataType>
void dList<DataType>::insertBeginning(DataType itemToInsert)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  if (head == nullptr)
  {
    newNode->next = newNode->prev = nullptr; // Set Both Of 'newNode->next' And 'newNode->prev' To 'nullptr'
    head = tail = newNode;
  }
  else
  {
    newNode->prev = nullptr;
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
  }
  itemsInList++;
}

// The Insert After Nth Node Function.
template <class DataType>
int dList<DataType>::insertAfterNth(DataType itemToInsert, int afterNth)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  Node *temp1 = head;
  int counter = 1;
  while (temp1 != nullptr)
  {
    if (counter == afterNth) break;
    if (temp1->next == nullptr) return 1;
    counter++;
    temp1 = temp1->next;
  }
  // Special Case For Tail, If Inserting After The Last Node.
  if (temp1 == tail)
  {
    newNode->next = nullptr;
    temp1->next = newNode;
    newNode->prev = temp1;
    tail = newNode;
  }
  // All Other Cases.
  else
  {
    Node *temp2 = temp1->next;
    temp1->next = newNode;
    newNode->prev = temp1;
    temp2->prev = newNode;
    newNode->next = temp2;
  }
  itemsInList++;
  return 0;
}

// The Insert After Specific Data Function.
template <class DataType>
int dList<DataType>::insertAfterSpecific(DataType itemToInsert, DataType afterData)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  Node *temp = head;
  while (temp->data != afterData)
  {
    if (temp->next == nullptr) return 1; // Indicating That The Node Data To Insert After Was Not Found.
    temp = temp->next;
  }
  if (temp == tail)
  {
    newNode->next = nullptr;
    temp->next = newNode;
    newNode->prev = temp;
    tail = newNode;
  }
  else
  {
    Node *temp2 = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
    temp->prev = newNode;
    newNode->next = temp2;
  }
  itemsInList++;
  return 0;
}

// The Delete Beginning Function.
template <class DataType>
int dList<DataType>::deleteBeginning()
{
  // Check If The List Is Empty.
  if (head == nullptr) return 1; // Indicating That The Operation Failed, Since List Is Empty.
  // Otherwise.
  if (tail == head)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    Node *temp = head;
    head = head->next;
    head->prev = nullptr;
    delete temp;
  }
  return 0;
}

// The Delete End Function.
template <class DataType>
int dList<DataType>::deleteEnd()
{
  if (head == nullptr) return 1;
  if (tail == head)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    Node *temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
  }
  return 0;
}

// The Delete Nth Node Function.
template <class DataType>
int dList<DataType>::deleteNthNode(int nthNode)
{
  if (head == nullptr) return 1;
  int counter = 1;
  Node *temp = head;
  while (temp != nullptr)
  {
    if (counter == nthNode) break;
    if (temp->next == nullptr) return 2;
    counter++;
    temp = temp->next;
  }
  if (head == tail)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
  }
  return 0;
}

// The Delete Specific Node Data Function.
template <class DataType>
int dList<DataType>::deleteSpecificNode(DataType nodeToDelete)
{
  if (head == nullptr) return 1;
  Node *temp = head;
  while (temp != nullptr)
  {
    if (temp->data == nodeToDelete) break;
    if (temp->next == nullptr) return 2;
    temp = temp->next;
  }
  if (head == tail)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
  }
  return 0;
}

// The Display Forward Function.
template <class DataType>
int dList<DataType>::displayF()
{
  // Check Whether The List Is Empty.
  if (head == nullptr) return 1; // Indicating That The List Is Empty.
  // Otherwise (If List Is Not Empty).
  Node *temp = head;
  cout << "\n\n\n" << "\t" << "| ";
  while (temp != nullptr)
  {
    cout << temp->data << " | ";
    temp = temp->next;
  }
  cout << "\n\n\n";
  return 0; // Indicating That The List Was Displayed Successfully.
}

// The Display Backward Function.
template <class DataType>
int dList<DataType>::displayB()
{
  if (head == nullptr) return 1;
  Node *temp = tail;
  cout << "\n\n\n" << "\t" << "| ";
  while (temp != nullptr)
  {
    cout << temp->data << " | ";
    temp = temp->prev;
  }
  cout << "\n\n\n";
  return 0;
}

// The Number Of Items Inside The List Function.
template <class DataType>
int dList<DataType>::numberOfItems()
{
  return (itemsInList);
}

// The Is Empty Function.
template <class DataType>
bool dList<DataType>::isEmpty()
{
  if (head == nullptr) return true;
  return false;
}

// The Search For A Specific Node Function.
template <class DataType>
DataType dList<DataType>::searchFor(DataType searchTerm)
{
  if (head == nullptr) return -1; // Indicating That The List Is Empty.
  Node *temp = head;
  int counter = 1;
  while (temp != nullptr)
  {
    if (temp->data == searchTerm) break;
    if (temp->next == nullptr) return -2; // Indicating That The Item Was Not Found In The List.
    counter++;
    temp = temp->next;
  }
  return counter; // Returns The Node Number Of The Searched Item If It's Found.
}

Спасибо заранее



740
2
задан 21 марта 2018 в 07:03 Источник Поделиться
Комментарии
3 ответа


  • Сухой 1. Вы инициализируете node->data независимо от того, где вы хотите вставить узел. Пусть конструктор справиться с этим. Еще лучше, пусть конструктор создать node в известное состояние. Полезным умолчанию .next = nullptr и .prev = nullptr.

  • Сухой 2. Посмотрите внимательно на insertEnd. Само название функции означает, что tail хотел бы отметить newNode несмотря ни на что, и newNode->prev будет указать старый хвост ни на что. Единственное отличие-роль newNode. Предложили переписать:

    newNode->prev = tail;
    if (head == nullptr) {
    assert(tail == nullptr);
    head = newNode;
    } else {
    assert(tail != nullptr);
    tail->next = newNode;
    }
    tail = newNode;

    То же самое относится к insertBeginning.

    Как Примечание стороны, считают переименование их append и prependдля того чтобы быть больше в соответствии с стл push_front и push_back соответственно.


  • А delete* семье не удается обновить itemsInList.

  • searchFor объявляется для возврата DataTypeно на самом деле она возвращает counter, который int.

  • Я не уверен, я вижу полезность searchFor (кому будет нужен этот индекс вообще? - рассмотреть вопрос о возврате Node * и повторное использование этого метода в insertAfterSpecific и deleteSpecific). Однако повторный тест для nullptr-Несс предлагает переписать:

    while (temp != nullptr) {
    if (temp->data == searchTerm) {
    return counter;
    counter++;
    }
    return -2;

  • isEmpty реализуется с неодобрением пути. Рассмотрим

    return head == nullptr;

    Как Примечание стороны, поскольку это условие подразумевает itemsInList == 0 это еще одно хорошее место для assert.


5
ответ дан 21 марта 2018 в 08:03 Источник Поделиться

Ну, есть много, чтобы исправить, и даже больше, чтобы улучшить:


  1. Внимание Правило 3 / 5:
    Ваш класс управляет списком узлов, за исключением это не так. Вам реализуется только по умолчанию-конструктор (хотя вы действительно должны пометить его как noexcept и constexpr), забыв копирования/перемещения - конструктор, копирования/перемещения - назначения и dtor.

  2. Индексы хороши только в интерфейсе структура данных, которая позволяет постоянно-время индексирования. Вы должны использовать итератор, который дает вам доступ ко всему по-ряд-петлю и все хорошие алгоритмы.
    Если у вас нет терпения, чтобы их реализовать, по крайней мере использовать сырье Node* для позиции.

  3. Как-это нельзя выразить одним после последнего узла (односвязные списки есть до первого узла, а). Рассмотреть вопрос о сокращении Node для двух указателей, и использовать его в определении dList (который также содержит itemsInList) и DataNode (который также содержит data), который позволит вам исправить это.

    template <class T>
    class dList {
    struct Node { Node *next, *prev; };
    struct DataNode : Node { T data; };
    Node base{};
    std::size_t count{};
    ...
    };

  4. Теперь, когда вы можете выразить указатель в конце прошлого, вы можете удалить все специальные-код, который нужно обойти, что неспособность.

  5. Следуйте именования-конвенций стандартной библиотеки, где возможно. Вы не можете использовать власть шаблонов (а это требует множество дополнительных запоминания), если каждый использует свои собственные соглашения. И написание шаблонов, чтобы абстрагироваться от таких бесполезных различий, без субстанции-это реальная боль.

  6. Использовать агрегатно-инициализация при выделении нового узла. Таким образом, есть ровно одно место в функции, где может быть сгенерировано исключение, делая ваше исключение-безопасный код.

  7. Если вы хотите выразить отказ выполнять операции с обратным кодом, звоните в операции try@@ и вернуть bool вместо int вы только использовать два произвольных значений.

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

Соблюдать правило трех/пять/ноль.

Управление ресурс освобождает клиента от необходимости переживать за срок службы объекта управления, устранения утечки памяти и другие проблемы. Ресурсом может быть любой объект, который требует динамического создания/удаления.

Мартиньо р. Фернандеш определил правило ноль следующим образом:


Классы, которые имеют пользовательские деструкторы, копирование/конструкторы перемещения или копирования/перемещения операторы присваивания должны заниматься исключительно собственности. Другие классы не должны иметь собственные деструкторы, копирование/конструкторы перемещения или копирования/перемещения операторов присваивания.

Рассмотрим следующий код, который просто копирует список и изменяет копии.

dList<int> original;
original.insertEnd(0); // original = [0]

auto modified = original; // modified = [0]
modified.insertEnd(1); // modified = [0, 1]

modified.displayF(); // prints "| 0 | 1 |"
original.displayF(); // expects "| 0 |", printed "| 0 | 1 |", oops.

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

График ниже показывает, как компилятор может не подразумевать определенные операции, если вы объявляете другим себя.
C++ Special Member Functions
А не запоминать или постоянно ссылается на графике, как правило, "если вы должны предоставлять какие-либо специальные функции-члены, а затем обеспечить им все." Скотт Мейерс делает шаг вперед, предложив:


[Я]вместо выражения [правило ноль] не объявляя [функции-члены для копирования, перемещения и уничтожения] функции [править] выразил объявляя их явно и столь же явно предпочитают, чтобы компилятор автоматически реализаций.


  Node *head, *tail;

Предпочитаю в стиле C++ Декларатор. В C++ делает акцент на видах (думаю о ссылках) а c подчеркивает синтаксические структуры кода. Что также приводит к директиве декларируя одно имя в декларации. Это мелочи, хотя и согласуются с использование с-Декларатор стиль (что очень важно).

  Node* head;  // or Node * head;


  dList()
{
head = nullptr;
tail = nullptr;
itemsInList = 0;
}

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

template <class DataType>
class dList
{
private:
Node* head{nullptr};
Node* tail{nullptr};
int itemsInList{0};
public:
dList() = default;


  void insertEnd(DataType itemToInsert);

Для входных параметров, предпочитают копировать дешевые типы по значению и прочая ссылкой наconst. При копировании дешевая, ничего не собирается бить простота и безопасность копирование. Так DataType это шаблонный тип, он реально может быть какой-нибудь предмет типа с потенциалом, чтобы быть большого размера, вы не можете сделать предположение, что это будет дешево копировать. Есть более продвинутые методы оптимизации для передачи аргументов, которое вы можете смотреть в качестве, вы узнаете больше о семантике перемещения.

  void insertEnd(const DataType& itemToInsert);


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

Возвращают правильные типы. C++ имеет bool для возвращения true или false. searchFor() попытки бросить int что DataType это, который может провалиться. Если вам нужно вернуться к вызываемому государства, рассмотреть возможность перечисления или отчеты об ошибках стратегий, перечисленных ниже.

Убедитесь, что ваши предпосылки не нарушены. Если поведение по умолчанию для передачи вне диапазона индекса insertAfterNth() (либо слишком большой или отрицательное), в результате новый узел добавляется в конец?

template <class DataType>
bool dList<DataType>::insertAfterNth(const DataType& new_value,
int nth_index)
{
auto* nth_node = find_by_index(nth_index);
return !insert_after_node(nth_node, new_node);
}

template <class DataType>
bool dList<DataType>::insertAfterSpecific(const DataType& new_value,
const DataType& search_value)
{
auto* nth_node = find_by_value(search_value);
return insert_after_node(nth_node, new_value);
}

Для более современных упражнений, использовать std::unique_ptr вместо сырых указателей. Смотреть утечки-Свобода в C++... по умолчанию.


// The Search For A Specific Node Function.
template <class DataType>
DataType dList<DataType>::searchFor(DataType searchTerm)
{
if (head == nullptr) return -1; // Indicating That The List Is Empty.
Node *temp = head;
int counter = 1;
while (temp != nullptr)
{
if (temp->data == searchTerm) break;
if (temp->next == nullptr) return -2; // Indicating That The Item Was Not Found In The List.
counter++;
temp = temp->next;
}
return counter; // Returns The Node Number Of The Searched Item If It's Found.
}

Не лишними == или != условиям. Избежать многословия и сократить возможности для ошибки.

Не говорите в комментариях, что может быть явно указано в коде. Составители не читайте комментарии. Комментарии являются менее точными, чем код. Комментарии не обновляются последовательно, как код. Рассмотрите возможность использования реального механизма обработки ошибок в тех ситуациях, которые требуют их. В этом примере, не найдя элемента в пустой список или список должен возвращать одинаковое значение. Возвращаясь после конца из стандартной библиотеки это. В вашем случае, возвращая Союз тип (std::optional, std::variant, std::expectedили boost:: вариантов) может быть лучше.


template <class DataType>
int dList<DataType>::numberOfItems()
{
return (itemsInList);
}

Сохранить код простым. В C++14 добавляет бахромой случай, в котором круглые скобки, а возвращаемое значение интерпретируется как выражение. В этом случае выражение становится просто отлично. В мире auto-дедукция, все могло взорваться.

1
ответ дан 22 марта 2018 в 01:03 Источник Поделиться