C++, Visual C++, Теория

C++. Линейный двухсвязный список. Пример шаблонного класса

Линейный двухсвязный список. Пример шаблонного класса

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

Содержание

Поиск на других ресурсах:

1. Общее описание составляющих прогаммы

Разработанная программа носит демонстрационный характер. При создании приложения использовался тип приложения Console Application.

В разработанном примере объявляются следующие программные элементы:

  • шаблонная структура Element<T>, описывающая один элемент списка;
  • шаблонный класс List<T>, реализующий двухсвязный список структур типа Element<T>.

Структура Element<T> содержит следующие поля:

  • data – поле, являющееся данными;
  • next – указатель на следующий элемент списка;
  • prev – указатель на предыдущий элемент списка.

В шаблонном классе List<T> реализованы следующие элементы:

  • внутренние поля begin и end типа Element<T>*. Это указатели на первый и последний элемент списка;
  • внутреннее поле count – количество элементов в списке;
  • внутренний скрытый (private) метод Move(int) – возвращает элемент списка по заданному индексу;
  • внутренний скрытый (private) метод Copy(const List&) – осуществляет копию из списка;
  • внутренний скрытый (private) метод CorrectIndex(int) – определяет, имеет ли позиция (индекс) элемента списка корректное значение;
  • конструктор List();
  • конструктор копирования List(const List&);
  • оператор копирования operator=(const List&);
  • деструктор List~();
  • метод GetElement(int) – возвращает элемент по заданному индексу;
  • метод SetElement(T, int) – устанавливает значение элемента по заданному индексу;
  • метод AddEnd(T) – добавляет новый элемент в конец списка;
  • метод AddBegin(T) – добавляет новый элемент в начало списка;
  • метод Insert(T, int) – вставка элемента в заданную позицию списка;
  • метод Del(int) – удалить элемент из заданной позиции списка;
  • метод Clear() – очистка списка;
  • метод Reverse() – реверсирование списка;
  • метод Print() – вывод списка;
  • метод Count() – вернуть количество элементов в списке;
  • операторная функция operator+(const List&) – конкатенация списков;
  • операторная функция operator==(const List&) – сравнение списков на равенство;
  • операторная функция operator!=(const List&) – сравнение списков на неравенство;
  • операторная функция operator>=(const List&) – сравнение списков;
  • операторная функция operator<=(const List&) – сравнение списков;
  • операторная функция operator>(const List&) – сравнение списков;
  • операторная функция operator<(const List&) – сравнение списков.

  ⇑

2. Общая структура программы (сокращенный код)

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

#include <iostream>
using namespace std;

// Структура, описывающая один элемент (узел)
template <class T>
struct Element
{
  // Составляющие структуры Element<T>
};

// Клас, реализующий двусвязный список
template <class T>
class List
{
  // Составляющие класса List<T>
  // ...
};

// Реализация методов класса List<T>
// ...

void main()
{
  // Клиентский код (тестирование)
  // ...
}

  ⇑

3. Составляющие программы (подробный обзор)
3.1. Структура Element<T>

В программе объявление структуры имет вид:

// Структура, описывающая один елемент (узел)
template <class T>
struct Element
{
  T data; // данные
  Element<T>* next; // адрес следующего элемента в списке
  Element<T>* prev; // адрес предыдущего элемента в списке
};

  ⇑

3.2. Класс List<T>. Программный код

В данной реализации класса List<T> определены только сигнатуры (прототипы) методов, которые в нем реализованы. Сами реализации методов класса описываются в следующих пунктах.
Программный код класса следующий.

// Класс, реализующий двусвязный список
template <class T>
class List
{
private:
  Element<T>* begin; // указатель на первый элемент списка
  Element<T>* end; // указатель на последний элемент списка
  int count; // количество элементов в списке

  // Метод, возвращающий элемент в заданной позиции,
  // считается что позиция корректна.
  Element<T>* Move(int index);

  // Метод, копирующий список
  void Copy(const List<T>& obj);

  // Метод, проверяющий корректность позиии (индекса) в списке
  bool CorrectIndex(int index);

public:
  // Конструктор
  List();

  // Конструктор копирования
  List(const List& obj);

  // Оператор копирования
  List<T>& operator=(const List& obj);

  // Деструктор
  ~List();

  // ---------- Методы доступа к отдельным элементам списка --------
  // Получить элемент списка по индексу
  T GetElement(int index);

  // Изменить значение элемента в заданной позиции
  void SetElement(T _data, int index);

  // ---------- Методы изменения размера списка ------------
  // Добавить элемент в конец списка
  void AddEnd(T _data);

  // Добавить элемент в начало списка
  void AddBegin(T _data);

  // Вставка элемента в заданную позицию списка
  void Insert(T _data, int index);

  // Удалить элемент в заданной позиции,
  // позиция нумеруется с 0
  void Del(int index);

  // Очистка списка
  void Clear();

  // Реверсирование списка
  void Reverse();

  // Вывод списка
  void Print(string msg);

  // Получить количество элементов списка
  int Count();

  // ------------------------------------------
  // Перегрузка операторов
  // Операция + - конкатенация списков
  List<T>& operator+(const List<T>& obj);

  // Операция сравнения списков на равенство
  bool operator==(const List& obj);

  // Операция сравнения списков на неравенство
  bool operator!=(const List& obj);

  // Операция >=
  bool operator>=(const List& obj);

  // Операция <=
  bool operator<=(const List& obj);

  // Операция >
  bool operator>(const List& obj);

  // Операция <
  bool operator<(const List& obj);
};

  ⇑

3.2.1. Внутренние поля класса

В классе List<T> линейный список представлен тремя внутренними полями:

  • begin – указатель на начало списка;
  • end – указатель на конец списка;
  • count – количество элементов списка.

 

// Класс, реализующий двусвязный список
template <class T>
class List
{
private:
  Element<T>* begin; // указатель на первый элемент списка
  Element<T>* end; // указатель на последний элемент списка
  int count; // количество элементов в списке

  ...

}

  ⇑

3.2.2. Дополнительные внутренние методы класса

В классе выделен ряд операций (методов), используемых в разных методах. Эти методы объявляются в разделе private.

3.2.2.1. Метод Move(int). Получить элемент в заданной позиции

Метод Move(int) возвращает указатель на элемент списка по заданной позиции.

// Получить элемент в заданной позиции
template <class T>
Element<T>* List<T>::Move(int index)
{
  // 1. Установить указатель на начало списка
  Element<T>* t = begin;

  // 2. Перемотать в позицию index
  for (int i = 0; i < index; i++)
    t = t->next;

  // 3. Вернуть указатель
  return t;
}

  ⇑

3.2.2.2. Метод Copy(const List<T>&). Сделать копию из списка

Для текущего экземпляра метод Copy() реализует копию из списка, являющегося входным параметром obj.

// Метод, делающий копию из списка
template <class T>
void List<T>::Copy(const List<T>& obj)
{
  // 1. Очистить список (освободить память)
  Clear();

  // 2. Цикл копирования this <= obj
  Element<T>* t = obj.begin;

  while (t != nullptr)
  {
    AddEnd(t->data);
    t = t->next;
  }
}

  ⇑

3.2.2.3. Метод CorrectIndex(int). Проверка корректности позиции (индекса) в списке

Метод CorrectIndex() получает входным параметром позицию index и возвращает true, если позиция корректна, то есть лежит в диапазоне [0..count-1]. В противном случае метод возвращает false.

// Метод, проверяющий корректность позиции (индекса) в списке
template <class T>
bool List<T>::CorrectIndex(int index)
{
  return (index >= 0) && (index < count);
}

  ⇑

3.2.3. Специальные функции класса
3.2.3.1. Конструктор List<T>(). Создание пустого списка

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

// Конструктор
template <class T>
List<T>::List()
{
  // Создать пустой список
  begin = end = nullptr;
  count = 0;
}

  ⇑

3.2.3.2. Конструктор копирования List<T>(const List<T>& obj). Копирование списка при его присваивании с одновременной инициализацией

При объявлении объекта класса List<T> и одновременном присваивании ему экземпляра другого объекта вызывается конструктор копирования.

// Конструктор копирования
template <class T>
List<T>::List(const List& obj)
{
  // Сделать копию из списка
  Copy(obj);
}

  ⇑

3.2.3.3. Оператор копирования operator=(const List<T>& obj). Присваивание списков

Оператор копирования вызывается при присваивании экземпляров класса.

// Оператор копирования
template <class T>
List<T>& List<T>::operator=(const List& obj)
{
  Copy(obj);
  return *this;
}

  ⇑

3.2.3.4. Деструктор ~List<T>(). Удаление (очистка) списка

В деструкторе происходит освобождение памяти, выделенной под список, путем вызова метода Clear().

// Деструктор
template <class T>
List<T>::~List()
{
  Clear(); // очистить список
}

  ⇑

3.2.4. Методы GetElement(int) и SetElement(T, int). Доступ к отдельным элементам списка

Метод GetElement() возвращает элемент списка по заданному индексу. В отличие от метода Move() здесь производится проверка значения index на корректность. Если значение index некорректно, то создается исключительная ситуация типа out_of_range.
Метод SetElement() изменяет значение элемента списка по заданному индексу.

// Получить элемент списка по индексу
template <class T>
T List<T>::GetElement(int index)
{
  // Проверка, корректен ли индекс,
  // если индекс не корректен, сгенерировать исключение
  if (!CorrectIndex(index))
    throw out_of_range("Incorrect index.");

  // Если индекс корректен, то вернуть элемент
  Element<T>* t = Move(index);
  return t->data;
}

// Изменить значение элемента в указанной позиции
template <class T>
void List<T>::SetElement(T _data, int index)
{
  // Проверка, корректна ли позиция
  if (!CorrectIndex(index))
    return;

  // Получить элемент по позиции и изменить его значение
  Element<T>* t = Move(index);
  t->data = _data;
}

  ⇑

3.2.5. Методы, изменяющие список в целом
3.2.5.1. Метод AddEnd(T). Добавить элемент в конец списка

Метод AddEnd() добавляет новый элемент в конец списка.

// Добавить элемент в конец списка
template <class T>
void List<T>::AddEnd(T _data)
{
  try
  {
    // 1. Создать новый элемент с данными _data
    Element<T>* t = new Element<T>;
    t->next = nullptr; // следующего элемента нет
    t->prev = end; // установить предыдущий элемент
    t->data = _data; // записать данные

    // 2. Заполнить поле next пока что последнего элемента
    if (end != nullptr)
      end->next = t;

    // 3. Проверка, есть ли в списке элементы
    if (count == 0)
    {
      // если элементов нет,
      // то это одновременно и начало и конец списка
      begin = end = t;
    }
    else
    {
      // если элементы в списке есть, то это конец списка
      end = t;
    }

    // 3. Увеличить общее количество элементов
    count++;
  }
  catch (bad_alloc e)
  {
    // Если память не выделена, то вывести системное сообщение
    cout << e.what() << endl;
  }
}

  ⇑

3.2.5.2. Метод AddBegin(T). Добавить элемент в начало списка

 

// Добавить элемент в начало списка
template <class T>
void List<T>::AddBegin(T _data)
{
  try
  {
    // 1. Создать новый элемент (новую ячейку памяти)
    // и заполнить его данными
    Element<T>* t = new Element<T>;
    t->data = _data; // данные
    t->prev = nullptr; // предыдущего элемента нет

    // следующий элемент указывает на предыдущий первый
    t->next = begin;

    // 2. Есть ли элементы в списке?
    if (count > 0)
    {
      // если есть, то перенаправить предыдущее начало списка
      begin->prev = t;
      begin = t;
    }
    else
    {
      // если элементов нет, то начало и конец есть тем самым элементом
      begin = end = t;
    }

    // 3. Увеличить общее количество элементов
    count++;
  }
  catch (bad_alloc e)
  {
    // если память не выделена, то обработать ошибку
    cout << e.what() << endl;
  }
}

  ⇑

3.2.5.3. Метод Insert(T, int). Вставка элемента в заданную позицию списка

 

// Вставка элемента в заданную позицию списка
template <class T>
void List<T>::Insert(T _data, int index)
{
  // 1. Проверка, корректна ли позиция
  if (!CorrectIndex(index))
    return;

  // 2. Проверка, вставка ли в конец списка (по указателю end)
  if (index == count)
  {
    // Добавить данные по указателю end
    AddEnd(_data);
    return;
  }

  // 3. Проверка, вставка ли в начало списка (перед begin)
  if (index == 0)
  {
    AddBegin(_data);
    return;
  }

  try
  {
    // 4. Получить элемент перед позицией вставки
    Element<T>* itemPrev = Move(index - 1);

    // 5. Получить элемент в позиции вставки
    Element<T>* item = Move(index);

    // 6. Создать новый элемент и вставить его в список
    Element<T>* t = new Element<T>;
    t->data = _data;
    t->next = item;
    t->prev = itemPrev;
    itemPrev->next = t;
    item->prev = t;

    // 7. Увеличить количество элементов
    count++;
  }
  catch (bad_alloc e)
  {
    // Если память не выделена, то вывести системное сообщение
    cout << e.what() << endl;
  }
}

  ⇑

3.2.5.4. Метод Del(int). Удалить элемент в заданной позиции

 

// Удалить элемент в заданной позиции,
// позиция нумеруется с 0
template <class T>
void List<T>::Del(int index)
{
  // 1. Проверка, есть ли элементы в списке
  if (count == 0) return;

  // 2. Игнор, если позиция указана неправильно
  if (!CorrectIndex(index))
    return;

  // 3. Перейти к удаляемому элементу
  Element<T>* item = Move(index);

  // 4. Получить предыдущий элемент
  Element<T>* itemPrev = item->prev;

  // 5. Получить следующий элемент
  Element<T>* itemNext = item->next;

  // 6. Проверка, удаляется ли не первый элемент списка
  if ((count > 1) && (itemPrev != nullptr))
    itemPrev->next = itemNext; // обойти элемент item

  // 7. Проверка, удаляется ли не последний элемент списка
  if ((itemNext != nullptr) && (count > 1))
    itemNext->prev = itemPrev;

  // 8. Если удаляется первый элемент
  if (index == 0)
    begin = itemNext;

  // 9. Если удаляется последний элемент
  if (index == count - 1)
    end = itemPrev;

  // 10. Удалить элемент item
  delete item;

  // 11. Уменьшить общее количество элементов
  count--;
}

  ⇑

3.2.5.5. Метод Clear(). Очистка списка

 

// Очистка списка
template <class T>
void List<T>::Clear()
{
  // Нужно count раз удалить первый элемент списка
  int n = count; // сделать копию из count - важно!
  for (int i = 0; i < n; i++)
    Del(0);
}

  ⇑

3.2.5.6. Метод Reverse(). Реверсирование списка

 

// Реверсирование списка
template <class T>
void List<T>::Reverse()
{
  List<T> L;
  Element<T>* t = begin;

  // цикл формирования списка,
  // элемент добавляется в начало списка
  while (t != nullptr)
  {
    L.AddBegin(t->data);
    t = t->next;
  }
  *this = L;
}

  ⇑

3.2.6. Метод Print(string). Вывод списка

С целью определения текущего состояния списка в классе реализован метод Print(). Метод выводит список в удобочитаемой форме.

// Вывод списка
template <class T>
void List<T>::Print(string msg)
{
  cout << msg << " => ";

  Element<T>* t = begin;
  for (int i = 0; i < count; i++)
  {
    cout << t->data << " ";
    t = t->next;
  }
  cout << endl;
}

  ⇑

3.2.7. Метод Count(). Получить количество элементов в списке

 

// Получить количество элементов списка
template <class T>
int List<T>::Count()
{
  return count;
}

  ⇑

3.2.8. Реализация базовых операций в списках
3.2.8.1. Операторная функция operator+(const List<T>& obj). Перегрузка оператора +. Конкатенация списков

Для реализации удобной конкатенации (сложения) списков, в классе перегружен оператор + с помощью функции operator+().

// Операция + - конкатенация списков
template <class T>
List<T>& List<T>::operator+(const List<T>& obj)
{
  // 1. Получить доступ к списку obj
  Element<T>* t = obj.begin;

  // 2. Добавить к временному списку элементы t
  while (t != nullptr)
  {
    AddEnd(t->data);
    t = t->next;
  }

  // 3. Вернуть объединенный список
  return *this;
}

  ⇑

3.2.8.2. Операторная функция operator==(const List<T>& obj). Перегрузка оператора ==. Сравнение списков на равенство

Полезными при работе со списками будут операции сравнения. Одной из них является операция сравнения списков на равенство, реализуемая в операторной функции operator==().

// Операция сравнения списков на равенство
template <class T>
bool List<T>::operator==(const List<T>& obj)
{
  // 1. Сначала сравнить размеры списков
  if (count != obj.count)
    return false;

  // 2. Если размеры одинаковы, то сравнить поэлементно
  Element<T>* t1 = begin;
  Element<T>* t2 = obj.begin;

  while (t1 != nullptr)
  {
    // Как только найдено хотя бы одно несовпадение, то выход с кодом false
    if (t1->data != t2->data)
      return false;

    t1 = t1->next;
    t2 = t2->next;
  }

  return true;
}

  ⇑

3.2.8.3. Операторная функция operator!=(const List<T>& obj). Перегрузка оператора !=. Сравнение списков на неравенство

Сравнение списков на неравенство реализовано в операторной функции operator!=(), перегружающей оператор !=.

// Операция сравнения списков на неравенство
template <class T>
bool List<T>::operator!=(const List<T>& obj)
{
  // Использовать оператор сравнения ==
  return !(*this == obj);
}

// Операция >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Сравнить количество элементов
  if (count > obj.count)
    return true;

  // 2. Сравнить по содержанию
  if (*this == obj)
    return true;

  return false;
}

  ⇑

3.2.8.4. Операторная функция operator>=(const List<T>& obj). Перегрузка оператора >=

 

// Операция >=
template <class T>
bool List<T>::operator>=(const List<T>& obj)
{
  // 1. Сравнение по количеству элементов
  if (count > obj.count)
    return true;

  // 2. Сравнение по содержанию
  if (*this == obj)
    return true;

  return false;
}

  ⇑

3.2.8.5. Операторная функция operator<=(const List<T>& obj). Перегрузка оператора <=

 

// Операция <=
template <class T>
bool List<T>::operator<=(const List<T>& obj)
{
  // 1. Сравнение по количеству элементов в списке
  if (count < obj.count)
    return true;

  // 2. Сравнение по содержанию
  if (*this == obj)
    return true;

  return false;
}

  ⇑

3.2.8.6. Операторная функция operator>(const List<T>& obj). Перегрузка оператора >

 

// Операция >
template <class T>
bool List<T>::operator>(const List<T>& obj)
{
  if (count > obj.count)
    return true;
  return false;
}

  ⇑

3.2.8.7. Операторная функция operator<(const List<T>& obj). Перегрузка оператора <

 

// Операція <
template <class T>
bool List<T>::operator<(const List<T>& obj)
{
  if (count < obj.count)
    return true;
  return false;
}

  ⇑

3.2.9. Функция main(). Клиентский код

Тестирование работы класса List<T> осуществляется в функции main(). Здесь объявляется экземпляр класса, для которого вызываются базовые методы.

void main()
{
  // Тест
  List<double> L1; // Создать список

  // Добавить элементы в список
  L1.AddBegin(2.0);
  L1.AddBegin(1.0);
  L1.AddEnd(3.0);
  L1.AddEnd(4.0);
  L1.Print("L1: ");

  // Вставить элемент в заданную позицию
  L1.Insert(-2.5, 2);
  L1.Print("L1.Insert: ");

  // Конструктор копирования
  List<double> L2 = L1;
  L2.Print("L2: ");

  // Оператор копирования
  List<double> L3;
  L3 = L2;
  L3.Print("L3: ");

  // Получить элемент
  double x = L1.GetElement(3);
  cout << "x = " << x << endl;

  // Установить новый элемент
  L3.SetElement(100.55, 0);
  L3.Print("L3: ");

  // Сравнить два списка
  if (L1 == L3)
    cout << "L1==L2" << endl;
  else
    cout << "L1!=L2" << endl;

  // Реверсирование списка
  L1.Reverse();
  L1.Reverse();
  L1.Print("L1: ");
}

  ⇑

4. Запуск программы. Результаты

После запуска на выполнение программа выдаст следующий результат

L1: => 1 2 3 4
L1.Insert: => 1 2 -2.5 3 4
L2: => 1 2 -2.5 3 4
L3: => 1 2 -2.5 3 4
x = 3
L3: => 100.55 2 -2.5 3 4
L1!=L2
L1: => 1 2 -2.5 3 4
L6: =>

  ⇑

Связанные темы

  ⇑