АйТи бубен

Инструменты пользователя

Инструменты сайта

Вы посетили:
dvusvjaznyj_spisok

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

— dvusvjaznyj_spisok [2020/06/13 13:45] (текущий)
Строка 1: Строка 1:
 +====== Двусвязный список ======
 +
 +
 +~~Title: Двусвязный список в С++ ~~
 +{{htmlmetatags>
 +metatag-description=(Пример реализации двусвязного списка в С++. Просто о сложном)
 +}}
 +
 +Отличие от односвязанного списка состоит в том, что в двусвязном (или двунаправленном списке) узел состоит не из двух, а из трех частей. В третьем компоненте хранится указатель на предыдущий элемент.
 +<file cpp>
 +    //узел (звено) списка
 +    struct node
 +    {
 + //Информационный элемент звена списка 
 + int value;
 +
 + // Указатель на предыдущее звено списка 
 +      node *prev; 
 +
 +  // Указатель на следующее звено списка 
 +      node *next;
 +    };
 +</file>
 +
 +===== Формирование двусвязного списка =====
 +
 +  - Отведем место для указателей в статической памяти и зарезервируем место для динамического объекта.
 +  - Присвоим значение переменной ptail, и поместим в информационное поле значение элемента.
 +  - Присвоим указателю на предыдущий элемент значение NULL (т. к. элемент первый - предыдущего нет).
 +  - Поместим в поле звена адрес еще одного - нового динамического объекта.
 +  - В новый добавленный объект записываем значение, в указатель на следующее звено записываем NULL, т. к. объект добавляется в конец.
 +  - В указатель на предыдущий элемент записываем адрес предыдущего объекта.
 +  - Переменная ptail должна содержать адрес последнего добавленного элемента, т. к. он добавлен в конец.
 +  - Двусвязный список из двух элементов готов.
 +
 +  - Вставка элемента в двусвязный список.
 +  - Выделить память под новый узел. 
 +  - Записать в новый узел значение.
 +  - В указатель на предыдущий узел записать адрес узла, который должен располагаться перед новым узлом.
 +  - Записать в указатель на следующий узел адрес узла, который должен быть расположен после нового узла.
 +  - В предыдущем узле заменяем значение указателя на следующий узел на адрес нового узла.
 +  - В следующем узле заменяем значение указателя на предыдущий узел на адрес нового узла.
 +На рисунке изображен двусвязный циклический список:
 +{{ ::dvusvyaznyy_tsiklicheskiy_spisok.png?nolink |}}
 +
 +===== Удаление элемента из двусвязного списка =====
 +
 +  - Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел узла, являющегося предыдущим для удаляемого узла.
 +  - Записать адрес узла, являющегося предыдущим для удаляемого, в указатель на предыдущий узел узла, следующего за удаляемым узлом.
 +  - Удалить узел, предназначенный для удаления.
 +
 +Такое построение позволяет производить движение по списку, как в прямом, так и в обратном направлении. 
 +
 +===== Реализация двусвязного списка =====
 +
 +<file cpp>
 +#include <iostream>
 +using namespace std;
 +
 +struct Elem
 +{
 +   int data; // данные
 +   Elem * next, * prev;
 +};
 +
 +class List
 +{
 +   // Голова, хвост
 +   Elem * Head, * Tail;
 +   // Количество элементов
 +   int Count;
 +
 +public:
 +
 +   // Конструктор
 +   List();
 +   // Конструктор копирования
 +   List(const List&);
 +   // Деструктор
 +   ~List();
 + 
 +   // Получить количество
 +   int GetCount();
 +   // Получить элемент списка
 +   Elem* GetElem(int);
 +
 +   // Удалить весь список
 +   void DelAll();
 +   // Удаление элемента, если параметр не указывается,
 +   // то функция его запрашивает
 +   void Del(int pos = 0);
 +   // Вставка элемента, если параметр не указывается,
 +   // то функция его запрашивает
 +   void Insert(int pos = 0);
 +
 +   // Добавление в конец списка
 +   void AddTail(int n);
 +
 +   // Добавление в начало списка
 +   void AddHead(int n);
 +
 +   // Печать списка
 +   void Print();
 +   // Печать определенного элемента
 +   void Print(int pos);
 +
 +   List& operator = (const List&);
 +   // сложение двух списков (дописывание)
 +   List operator + (const List&);
 +
 +   // сравнение по элементам
 +   bool operator == (const List&);
 +   bool operator != (const List&);
 +   bool operator <= (const List&);
 +   bool operator >= (const List&);
 +   bool operator < (const List&);
 +   bool operator > (const List&);
 +
 +   // переворачивание списка
 +   List operator - ();
 +};
 +
 +List::List()
 +{
 +   // Изначально список пуст
 +   Head = Tail = NULL;
 +   Count = 0;
 +}
 +
 +List::List(const List & L)
 +{
 +   Head = Tail = NULL;
 +   Count = 0;
 +
 +   // Голова списка, из которого копируем
 +   Elem * temp = L.Head;
 +   // Пока не конец списка
 +   while(temp != 0)
 +   {
 +      // Передираем данные
 +      AddTail(temp->data);
 +      temp = temp->next;
 +   }
 +}
 +
 +List::~List()
 +{
 +   // Удаляем все элементы
 +   DelAll();
 +}
 +
 +void List::AddHead(int n)
 +{
 +   // новый элемент
 +   Elem * temp = new Elem;
 +
 +   // Предыдущего нет
 +   temp->prev = 0;
 +   // Заполняем данные
 +   temp->data = n;
 +   // Следующий - бывшая голова
 +   temp->next = Head;
 +
 +   // Если элементы есть?
 +   if(Head != 0)
 +      Head->prev = temp;
 +
 +   // Если элемент первый, то он одновременно и голова и хвост
 +   if(Count == 0)
 +      Head = Tail = temp;
 +   else
 +      // иначе новый элемент - головной
 +      Head = temp;
 +
 +   Count++;
 +}
 +
 +void List::AddTail(int n)
 +{
 +   // Создаем новый элемент
 +   Elem * temp = new Elem;
 +   // Следующего нет
 +   temp->next = 0;
 +   // Заполняем данные
 +   temp->data = n;
 +   // Предыдущий - бывший хвост
 +   temp->prev = Tail;
 +
 +   // Если элементы есть?
 +   if(Tail != 0)
 +      Tail->next = temp;
 +
 +   // Если элемент первый, то он одновременно и голова и хвост
 +   if(Count == 0)
 +      Head = Tail = temp;
 +   else
 +      // иначе новый элемент - хвостовой
 +   Tail = temp;
 +
 +   Count++;
 +}
 +
 +void List::Insert(int pos)
 +{
 +   // если параметр отсутствует или равен 0, то запрашиваем его
 +   if(pos == 0)
 +   {
 +      cout << "Input position: ";
 +      cin >> pos;
 +   }
 +
 +  // Позиция от 1 до Count?
 +   if(pos < 1 || pos > Count + 1)
 +   {
 +      // Неверная позиция
 +      cout << "Incorrect position !!!\n";
 +      return;
 +   }
 +
 +   // Если вставка в конец списка
 +   if(pos == Count + 1)
 +   {
 +      // Вставляемые данные
 +      int data;
 +      cout << "Input new number: ";
 +      cin >> data;
 +      // Добавление в конец списка
 +      AddTail(data);
 +      return;
 +   }
 +   else if(pos == 1)
 +   {
 +      // Вставляемые данные
 +      int data;
 +      cout << "Input new number: ";
 +      cin >> data;
 +      // Добавление в начало списка
 +      AddHead(data);
 +      return;
 +   }
 +
 +   // Счетчик
 +   int i = 1;
 +
 +   // Отсчитываем от головы n - 1 элементов
 +   Elem * Ins = Head;
 +
 +   while(i < pos)
 +   {
 +      // Доходим до элемента, 
 +      // перед которым вставляемся
 +      Ins = Ins->next;
 +      i++;
 +   }
 +
 +   // Доходим до элемента, 
 +   // который предшествует
 +   Elem * PrevIns = Ins->prev;
 +
 +   // Создаем новый элемент
 +   Elem * temp = new Elem;
 +
 +   // Вводим данные
 +   cout << "Input new number: ";
 +   cin >> temp->data;
 +
 +   // настройка связей
 +   if(PrevIns != 0 && Count != 1)
 +      PrevIns->next = temp;
 +
 +   temp->next = Ins;
 +   temp->prev = PrevIns;
 +   Ins->prev = temp;
 +
 +   Count++;
 +}
 +
 +void List::Del(int pos)
 +{
 +   // если параметр отсутствует или равен 0, то запрашиваем его
 +   if(pos == 0)
 +   {
 +       cout << "Input position: ";
 +       cin >> pos;
 +   }
 +   // Позиция от 1 до Count?
 +   if(pos < 1 || pos > Count)
 +   {
 +      // Неверная позиция
 +      cout << "Incorrect position !!!\n";
 +      return;
 +   }
 +
 +   // Счетчик
 +   int i = 1;
 +
 +   Elem * Del = Head;
 +
 +   while(i < pos)
 +   {
 +      // Доходим до элемента, 
 +      // который удаляется
 +      Del = Del->next;
 +      i++;
 +   }
 +
 +   // Доходим до элемента, 
 +   // который предшествует удаляемому
 +   Elem * PrevDel = Del->prev;
 +   // Доходим до элемента, который следует за удаляемым
 +   Elem * AfterDel = Del->next;
 +
 +   // Если удаляем не голову
 +   if(PrevDel != 0 && Count != 1)
 +      PrevDel->next = AfterDel;
 +   // Если удаляем не хвост
 +    if(AfterDel != 0 && Count != 1)
 +      AfterDel->prev = PrevDel;
 +
 +   // Удаляются крайние?
 +   if(pos == 1)
 +       Head = AfterDel;
 +   if(pos == Count)
 +       Tail = PrevDel;
 +
 +   // Удаление элемента
 +   delete Del;
 +
 +   Count--;
 +}
 +
 +void List::Print(int pos)
 +{
 +   // Позиция от 1 до Count?
 +   if(pos < 1 || pos > Count)
 +   {
 +      // Неверная позиция
 +      cout << "Incorrect position !!!\n";
 +      return;
 +   }
 +
 +   Elem * temp;
 +
 +   // Определяем с какой стороны 
 +   // быстрее двигаться
 +   if(pos <= Count / 2)
 +   {
 +      // Отсчет с головы
 +      temp = Head;
 +      int i = 1;
 +
 +      while(i < pos)
 +      {
 +         // Двигаемся до нужного элемента
 +         temp = temp->next;
 +         i++;
 +      }
 +   }
 +   else
 +   {
 +       // Отсчет с хвоста
 +      temp = Tail;
 +      int i = 1;
 +
 +      while(i <= Count - pos)
 +      {
 +         // Двигаемся до нужного элемента
 +         temp = temp->prev;
 +         i++;
 +      }
 +   }
 +   // Вывод элемента
 +   cout << pos << " element: ";
 +   cout << temp->data << endl;
 +}
 +
 +void List::Print()
 +{
 +   // Если в списке присутствуют элементы, то пробегаем по нему
 +   // и печатаем элементы, начиная с головного
 +   if(Count != 0)
 +   {
 +      Elem * temp = Head;
 +      cout << "( ";
 +      while(temp->next != 0)
 +      {
 +          cout << temp->data << ", ";
 +          temp = temp->next;
 +      }
 +
 +      cout << temp->data << " )\n";
 +   }
 +}
 +
 +void List::DelAll()
 +{
 +   // Пока остаются элементы, удаляем по одному с головы
 +   while(Count != 0)
 +      Del(1);
 +}
 +
 +int List::GetCount()
 +{
 +    return Count;
 +}
 +
 +Elem * List::GetElem(int pos)
 +{
 +   Elem *temp = Head;
 +
 +   // Позиция от 1 до Count?
 +   if(pos < 1 || pos > Count)
 +   {
 +      // Неверная позиция
 +      cout << "Incorrect position !!!\n";
 +      return 0;
 +   }
 +
 +   int i = 1;
 +   // Ищем нужный нам элемент
 +   while(i < pos && temp != 0)
 +   {
 +      temp = temp->next;
 +      i++;
 +   }
 +
 +   if(temp == 0)
 +      return 0;
 +   else
 +      return temp;
 +}
 +
 +List & List::operator = (const List & L)
 +{
 +    // Проверка присваивания элемента "самому себе"
 +    if(this == &L)
 +       return *this;
 +
 +   // удаление старого списка
 +   this->~List(); // DelAll();
 +
 +   Elem * temp = L.Head;
 +
 +   // Копируем элементы
 +   while(temp != 0)
 +   {
 +      AddTail(temp->data);
 +      temp = temp->next;
 +   }
 +
 +   return *this;
 +}
 +// сложение двух списков
 +List List::operator + (const List& L)
 +{
 +   // Заносим во временный список элементы первого списка
 +   List Result(*this);
 +   // List Result = *this;
 +
 +   Elem * temp = L.Head;
 +
 +   // Добавляем во временный список элементы второго списка
 +   while(temp != 0)
 +   {
 +      Result.AddTail(temp->data);
 +      temp = temp->next;
 +   }
 +
 +   return Result;
 +}
 +
 +bool List::operator == (const List& L)
 +{
 +   // Сравнение по количеству
 +   if(Count != L.Count)
 +      return false;
 +
 +   Elem *t1, *t2;
 +
 +   t1 = Head;
 +   t2 = L.Head;
 +
 +   // Сравнение по содержанию
 +   while(t1 != 0)
 +   {
 +      // Сверяем данные, которые
 +      // находятся на одинаковых позициях
 +      if(t1->data != t2->data)
 +         return false;
 +
 +      t1 = t1->next;
 +      t2 = t2->next;
 +  }
 +
 +   return true;
 +}
 +
 +bool List::operator != (const List& L)
 +{
 +   // Используем предыдущую функцию сравнения
 +   return !(*this == L);
 +}
 +
 +bool List::operator >= (const List& L)
 +{
 +   // Сравнение по количеству
 +   if(Count > L.Count)
 +      return true;
 +   // Сравнение по содержанию
 +   if(*this == L)
 +      return true;
 +
 +   return false;
 +}
 +
 +bool List::operator <= (const List& L)
 +{
 +   // Сравнение по количеству
 +   if(Count < L.Count)
 +      return true;
 +   // Сравнение по содержанию
 +   if(*this == L)
 +       return true;
 +
 +   return false;
 +}
 +
 +bool List::operator > (const List& L)
 +{
 +   if(Count > L.Count)
 +     return true;
 +
 +   return false;
 +}
 +
 +bool List::operator < (const List& L)
 +{
 +   if(Count < L.Count)
 +       return true;
 +
 +   return false;
 +}
 +
 +// переворот
 +List List::operator - ()
 +{
 +   List Result;
 +
 +   Elem * temp = Head;
 +   // Копируем элементы списка, начиная с головного,
 +   // в свой путем добавления элементов в голову,
 +   // таким образом временный список Result будет содержать
 +   // элементы в обратном порядке
 +   while(temp != 0)
 +   {
 +       Result.AddHead(temp->data);
 +       temp = temp->next;
 +   }
 +
 +   return Result;
 +}
 +
 +// Тестовый пример
 +void main()
 +{
 +   List L;
 +
 +   const int n = 10;
 +   int a[n] = {0,1,2,3,4,5,6,7,8,9};
 +
 +   // Добавляем элементы, стоящие на четных индексах, в голову,
 +   // на нечетных - в хвост
 +   for(int i = 0; i < n; i++)
 +      if(i % 2 == 0)
 +         L.AddHead(a[i]);
 +      else
 +         L.AddTail(a[i]);
 +
 +   // Распечатка списка
 +   cout << "List L:\n";
 +   L.Print();
 +
 +   cout << endl;
 +
 +   // Вставка элемента в список
 +   L.Insert();
 +   // Распечатка списка
 +   cout << "List L:\n";
 +   L.Print();
 +
 +   // Распечатка 2-го и 8-го элементов списка
 +   L.Print(2);
 +   L.Print(8);
 +
 +   List T;
 +
 +   // Копируем список
 +   T = L;
 +   // Распечатка копии
 +   cout << "List T:\n";
 +   T.Print();
 +
 +   // Складываем два списка (первый в перевернутом состоянии)
 +   cout << "List Sum:\n";
 +   List Sum = -L + T;
 +   // Распечатка списка
 +   Sum.Print();
 +}
 +</file>
  
dvusvjaznyj_spisok.txt · Последнее изменение: 2020/06/13 13:45 (внешнее изменение)

Инструменты страницы

Я на связи КОНТАКТЫ
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: GNU Free Documentation License 1.3