Различия
Показаны различия между двумя версиями страницы.
— | dvusvjaznyj_spisok [2021/07/31 21:57] (текущий) – создано - внешнее изменение 127.0.0.1 | ||
---|---|---|---|
Строка 1: | Строка 1: | ||
+ | ====== Двусвязный список ====== | ||
+ | |||
+ | ~~Title: Реализация двусвязного списка на c ~~ | ||
+ | {{htmlmetatags> | ||
+ | metatag-description=(Пример реализации двусвязного списка в С++. Удаление элемента из двусвязного списка.) | ||
+ | }} | ||
+ | |||
+ | * [[dinamicheskie_struktury_dannyx]] | ||
+ | * [[zametki_po_jazyku_c]] | ||
+ | |||
+ | Отличие от односвязанного списка состоит в том, что в двусвязном (или двунаправленном списке) узел состоит не из двух, а из трех частей. В третьем компоненте хранится указатель на предыдущий элемент. | ||
+ | <file cpp> | ||
+ | //узел (звено) списка | ||
+ | struct node | ||
+ | { | ||
+ | // | ||
+ | int value; | ||
+ | |||
+ | // Указатель на предыдущее звено списка | ||
+ | node *prev; | ||
+ | |||
+ | // Указатель на следующее звено списка | ||
+ | node *next; | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | ===== Формирование двусвязного списка ===== | ||
+ | |||
+ | - Отведем место для указателей в статической памяти и зарезервируем место для динамического объекта. | ||
+ | - Присвоим значение переменной ptail, и поместим в информационное поле значение элемента. | ||
+ | - Присвоим указателю на предыдущий элемент значение NULL (т. к. элемент первый - предыдущего нет). | ||
+ | - Поместим в поле звена адрес еще одного - нового динамического объекта. | ||
+ | - В новый добавленный объект записываем значение, | ||
+ | - В указатель на предыдущий элемент записываем адрес предыдущего объекта. | ||
+ | - Переменная ptail должна содержать адрес последнего добавленного элемента, | ||
+ | - Двусвязный список из двух элементов готов. | ||
+ | |||
+ | - Вставка элемента в двусвязный список. | ||
+ | - Выделить память под новый узел. | ||
+ | - Записать в новый узел значение. | ||
+ | - В указатель на предыдущий узел записать адрес узла, который должен располагаться перед новым узлом. | ||
+ | - Записать в указатель на следующий узел адрес узла, который должен быть расположен после нового узла. | ||
+ | - В предыдущем узле заменяем значение указателя на следующий узел на адрес нового узла. | ||
+ | - В следующем узле заменяем значение указателя на предыдущий узел на адрес нового узла. | ||
+ | На рисунке изображен двусвязный циклический список: | ||
+ | {{ :: | ||
+ | |||
+ | ===== Удаление элемента из двусвязного списка ===== | ||
+ | |||
+ | - Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел узла, являющегося предыдущим для удаляемого узла. | ||
+ | - Записать адрес узла, являющегося предыдущим для удаляемого, | ||
+ | - Удалить узел, предназначенный для удаления. | ||
+ | |||
+ | Такое построение позволяет производить движение по списку, | ||
+ | |||
+ | ===== Реализация двусвязного списка ===== | ||
+ | |||
+ | <file cpp> | ||
+ | #include < | ||
+ | using namespace std; | ||
+ | |||
+ | struct Elem | ||
+ | { | ||
+ | int data; // данные | ||
+ | Elem * next, * prev; | ||
+ | }; | ||
+ | |||
+ | class List | ||
+ | { | ||
+ | // Голова, | ||
+ | Elem * Head, * Tail; | ||
+ | // Количество элементов | ||
+ | int Count; | ||
+ | |||
+ | public: | ||
+ | |||
+ | // Конструктор | ||
+ | | ||
+ | // Конструктор копирования | ||
+ | | ||
+ | // Деструктор | ||
+ | | ||
+ | |||
+ | // Получить количество | ||
+ | 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&); | ||
+ | |||
+ | // сравнение по элементам | ||
+ | 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:: | ||
+ | { | ||
+ | // Изначально список пуст | ||
+ | Head = Tail = NULL; | ||
+ | Count = 0; | ||
+ | } | ||
+ | |||
+ | List:: | ||
+ | { | ||
+ | Head = Tail = NULL; | ||
+ | Count = 0; | ||
+ | |||
+ | // Голова списка, | ||
+ | Elem * temp = L.Head; | ||
+ | // Пока не конец списка | ||
+ | | ||
+ | { | ||
+ | // Передираем данные | ||
+ | AddTail(temp-> | ||
+ | temp = temp-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | List:: | ||
+ | { | ||
+ | // Удаляем все элементы | ||
+ | | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // новый элемент | ||
+ | Elem * temp = new Elem; | ||
+ | |||
+ | // Предыдущего нет | ||
+ | | ||
+ | // Заполняем данные | ||
+ | | ||
+ | // Следующий - бывшая голова | ||
+ | | ||
+ | |||
+ | // Если элементы есть? | ||
+ | | ||
+ | Head-> | ||
+ | |||
+ | // Если элемент первый, | ||
+ | | ||
+ | Head = Tail = temp; | ||
+ | else | ||
+ | // иначе новый элемент - головной | ||
+ | Head = temp; | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // Создаем новый элемент | ||
+ | Elem * temp = new Elem; | ||
+ | // Следующего нет | ||
+ | | ||
+ | // Заполняем данные | ||
+ | | ||
+ | // Предыдущий - бывший хвост | ||
+ | | ||
+ | |||
+ | // Если элементы есть? | ||
+ | | ||
+ | Tail-> | ||
+ | |||
+ | // Если элемент первый, | ||
+ | | ||
+ | Head = Tail = temp; | ||
+ | else | ||
+ | // иначе новый элемент - хвостовой | ||
+ | Tail = temp; | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // если параметр отсутствует или равен 0, то запрашиваем его | ||
+ | | ||
+ | { | ||
+ | cout << "Input position: "; | ||
+ | cin >> pos; | ||
+ | } | ||
+ | |||
+ | // Позиция от 1 до Count? | ||
+ | | ||
+ | { | ||
+ | // Неверная позиция | ||
+ | cout << " | ||
+ | return; | ||
+ | } | ||
+ | |||
+ | // Если вставка в конец списка | ||
+ | | ||
+ | { | ||
+ | // Вставляемые данные | ||
+ | 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; | ||
+ | |||
+ | | ||
+ | { | ||
+ | // Доходим до элемента, | ||
+ | // перед которым вставляемся | ||
+ | Ins = Ins-> | ||
+ | i++; | ||
+ | } | ||
+ | |||
+ | // Доходим до элемента, | ||
+ | // который предшествует | ||
+ | Elem * PrevIns = Ins-> | ||
+ | |||
+ | // Создаем новый элемент | ||
+ | Elem * temp = new Elem; | ||
+ | |||
+ | // Вводим данные | ||
+ | cout << "Input new number: "; | ||
+ | cin >> temp-> | ||
+ | |||
+ | // настройка связей | ||
+ | | ||
+ | PrevIns-> | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // если параметр отсутствует или равен 0, то запрашиваем его | ||
+ | | ||
+ | { | ||
+ | cout << "Input position: "; | ||
+ | cin >> pos; | ||
+ | } | ||
+ | // Позиция от 1 до Count? | ||
+ | | ||
+ | { | ||
+ | // Неверная позиция | ||
+ | cout << " | ||
+ | return; | ||
+ | } | ||
+ | |||
+ | // Счетчик | ||
+ | int i = 1; | ||
+ | |||
+ | Elem * Del = Head; | ||
+ | |||
+ | | ||
+ | { | ||
+ | // Доходим до элемента, | ||
+ | // который удаляется | ||
+ | Del = Del-> | ||
+ | i++; | ||
+ | } | ||
+ | |||
+ | // Доходим до элемента, | ||
+ | // который предшествует удаляемому | ||
+ | Elem * PrevDel = Del-> | ||
+ | // Доходим до элемента, | ||
+ | Elem * AfterDel = Del-> | ||
+ | |||
+ | // Если удаляем не голову | ||
+ | | ||
+ | PrevDel-> | ||
+ | // Если удаляем не хвост | ||
+ | if(AfterDel != 0 && Count != 1) | ||
+ | AfterDel-> | ||
+ | |||
+ | // Удаляются крайние? | ||
+ | | ||
+ | Head = AfterDel; | ||
+ | | ||
+ | Tail = PrevDel; | ||
+ | |||
+ | // Удаление элемента | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // Позиция от 1 до Count? | ||
+ | | ||
+ | { | ||
+ | // Неверная позиция | ||
+ | cout << " | ||
+ | return; | ||
+ | } | ||
+ | |||
+ | Elem * temp; | ||
+ | |||
+ | // Определяем с какой стороны | ||
+ | // быстрее двигаться | ||
+ | | ||
+ | { | ||
+ | // Отсчет с головы | ||
+ | temp = Head; | ||
+ | int i = 1; | ||
+ | |||
+ | while(i < pos) | ||
+ | { | ||
+ | // Двигаемся до нужного элемента | ||
+ | temp = temp-> | ||
+ | i++; | ||
+ | } | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | // Отсчет с хвоста | ||
+ | temp = Tail; | ||
+ | int i = 1; | ||
+ | |||
+ | while(i <= Count - pos) | ||
+ | { | ||
+ | // Двигаемся до нужного элемента | ||
+ | temp = temp-> | ||
+ | i++; | ||
+ | } | ||
+ | } | ||
+ | // Вывод элемента | ||
+ | cout << pos << " element: "; | ||
+ | cout << temp-> | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // Если в списке присутствуют элементы, | ||
+ | // и печатаем элементы, | ||
+ | | ||
+ | { | ||
+ | Elem * temp = Head; | ||
+ | cout << "( "; | ||
+ | while(temp-> | ||
+ | { | ||
+ | cout << temp-> | ||
+ | temp = temp-> | ||
+ | } | ||
+ | |||
+ | cout << temp-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void List:: | ||
+ | { | ||
+ | // Пока остаются элементы, | ||
+ | | ||
+ | Del(1); | ||
+ | } | ||
+ | |||
+ | int List:: | ||
+ | { | ||
+ | return Count; | ||
+ | } | ||
+ | |||
+ | Elem * List:: | ||
+ | { | ||
+ | Elem *temp = Head; | ||
+ | |||
+ | // Позиция от 1 до Count? | ||
+ | | ||
+ | { | ||
+ | // Неверная позиция | ||
+ | cout << " | ||
+ | return 0; | ||
+ | } | ||
+ | |||
+ | int i = 1; | ||
+ | // Ищем нужный нам элемент | ||
+ | | ||
+ | { | ||
+ | temp = temp-> | ||
+ | i++; | ||
+ | } | ||
+ | |||
+ | | ||
+ | return 0; | ||
+ | else | ||
+ | return temp; | ||
+ | } | ||
+ | |||
+ | List & List:: | ||
+ | { | ||
+ | // Проверка присваивания элемента " | ||
+ | if(this == &L) | ||
+ | | ||
+ | |||
+ | // удаление старого списка | ||
+ | | ||
+ | |||
+ | Elem * temp = L.Head; | ||
+ | |||
+ | // Копируем элементы | ||
+ | | ||
+ | { | ||
+ | AddTail(temp-> | ||
+ | temp = temp-> | ||
+ | } | ||
+ | |||
+ | | ||
+ | } | ||
+ | // сложение двух списков | ||
+ | List List:: | ||
+ | { | ||
+ | // Заносим во временный список элементы первого списка | ||
+ | List Result(*this); | ||
+ | // List Result = *this; | ||
+ | |||
+ | Elem * temp = L.Head; | ||
+ | |||
+ | // Добавляем во временный список элементы второго списка | ||
+ | | ||
+ | { | ||
+ | Result.AddTail(temp-> | ||
+ | temp = temp-> | ||
+ | } | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | // Сравнение по количеству | ||
+ | | ||
+ | return false; | ||
+ | |||
+ | Elem *t1, *t2; | ||
+ | |||
+ | t1 = Head; | ||
+ | t2 = L.Head; | ||
+ | |||
+ | // Сравнение по содержанию | ||
+ | | ||
+ | { | ||
+ | // Сверяем данные, | ||
+ | // находятся на одинаковых позициях | ||
+ | if(t1-> | ||
+ | | ||
+ | |||
+ | t1 = t1-> | ||
+ | t2 = t2-> | ||
+ | } | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | // Используем предыдущую функцию сравнения | ||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | // Сравнение по количеству | ||
+ | | ||
+ | return true; | ||
+ | // Сравнение по содержанию | ||
+ | | ||
+ | return true; | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | // Сравнение по количеству | ||
+ | | ||
+ | return true; | ||
+ | // Сравнение по содержанию | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | bool List:: | ||
+ | { | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | // переворот | ||
+ | List List:: | ||
+ | { | ||
+ | List Result; | ||
+ | |||
+ | Elem * temp = Head; | ||
+ | // Копируем элементы списка, | ||
+ | // в свой путем добавления элементов в голову, | ||
+ | // таким образом временный список Result будет содержать | ||
+ | // элементы в обратном порядке | ||
+ | | ||
+ | { | ||
+ | | ||
+ | temp = temp-> | ||
+ | } | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | // Тестовый пример | ||
+ | void main() | ||
+ | { | ||
+ | List L; | ||
+ | |||
+ | const int n = 10; | ||
+ | int a[n] = {0, | ||
+ | |||
+ | // Добавляем элементы, | ||
+ | // на нечетных - в хвост | ||
+ | | ||
+ | if(i % 2 == 0) | ||
+ | | ||
+ | else | ||
+ | | ||
+ | |||
+ | // Распечатка списка | ||
+ | cout << "List L:\n"; | ||
+ | | ||
+ | |||
+ | cout << endl; | ||
+ | |||
+ | // Вставка элемента в список | ||
+ | | ||
+ | // Распечатка списка | ||
+ | cout << "List L:\n"; | ||
+ | | ||
+ | |||
+ | // Распечатка 2-го и 8-го элементов списка | ||
+ | | ||
+ | | ||
+ | |||
+ | List T; | ||
+ | |||
+ | // Копируем список | ||
+ | T = L; | ||
+ | // Распечатка копии | ||
+ | cout << "List T:\n"; | ||
+ | | ||
+ | |||
+ | // Складываем два списка (первый в перевернутом состоянии) | ||
+ | cout << "List Sum: | ||
+ | List Sum = -L + T; | ||
+ | // Распечатка списка | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | <panel type=" | ||
+ | |||
+ | Язык С и его производные один из самых востребованных и высокооплачиваемых языков программирования. | ||
+ | |||
+ | C++ Developer. Professional Разработчик С++ (Углубленный уровень) [[https:// | ||
+ | |||
+ | </ |
📌 Удобный подбор VPS по параметрам доступен на DIEGfinder.com - официальном инструменте проекта DIEG. Это часть единой экосистемы, созданной для того, чтобы помочь быстро найти подходящий VPS/VDS сервер для любых задач хостинга.
📌 Для тестирования скриптов, установщиков VPN и Python-ботов рекомендуем использовать надежные VPS на короткий срок. Подробнее о быстрой аренде VPS для экспериментов - читайте здесь.
💥 Подпишись в Телеграм 💥 и задай вопрос по сайтам и хостингам бесплатно!7 Самых Популярных Статей
- Как запустить скрипты и веб-приложения на Python
- Что такое страны TIER 1,2,3
- 7 способов сравнения файлов по содержимому в Windows или Linux
- Установка и тестирование веб-панели HestiaCP
- Nginx простые примеры конфигурации
- top, htop, atop определение загрузки ОС (Load average, LA)
- Использование rsync в примерах
7 Самых Популярных Обзоров
- Хостинг для Python-скриптов и приложений
- ТОП 4 лучших антидетект браузеров (Бесплатные & Платные)
- Подборка купонов (промокоды) на хостинг, антидетект браузеры
- Обзор THE.Hosting (PQ Hosting): надежный хостинг с профессиональной поддержкой
- Хостинг в России
- Хостинг в Европе
- Обзор браузера Dolphin {anty} для мультиаккаунтинга