Двусвязный список удаление элемента

У меня есть задание, в котором я должен написать функцию, которая может удалить любую часть двусвязного списка, в котором есть значение с предопределенным вводом. Я работал над этим в течение достаточно долгого времени, и я не могу найти что-то еще не так с кодом, который я написал. Назначение гласит следующее:

Напишите функцию C ++ для удаления узлов в связанном списке. Функция принимает два аргумента — заголовок связанного списка и значение, которое нужно удалить. Следует удалить все узлы, которые содержат значение, которое будет удалено. Должен вернуть заголовок связанного списка.

Структура связанного списка:

Итак, когда он запускает тест

и должен удалить все 3s, он получает результат

что правильно. Это работает с другими примерами, которые должны удалить предметы в голове, а также с примерами, которые должны удалить хвост. Он работал со всеми желаемыми функциями …. кроме …

где 2 должны быть удалены. Это только получение результата

Таким образом, дополнительные 2 остаются по какой-то причине. Есть догадки? Я предоставил все, что мне было предоставлено для этого вопроса. Я думаю, что проблема может быть в моем разделе для удаления промежуточных элементов в двусвязном списке, но я полностью потерян. Спасибо!

Решение

Я дополнение к ответу Барри:

Это установит псевдоним temp для вашего текущего узла tmp затем установите next указатель вашего предыдущего узла на NULL, удалить текущий узел и установить ваш tmp-указатель на temp , но это просто псевдоним для вашего только что удаленного узла. Вы, вероятно, хотите node *temp=tmp->prev; чтобы установить тмп в новый последний элемент.

Вероятно, причиной вашей ошибки является то, что вы сравниваете ваше сравнение со значением

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

Другие решения

Это выглядит подозрительно (добавив несколько пробелов):

node1 это просто псевдоним для tmp , На самом деле это не служит какой-либо другой цели. Затем вы delete tmp и назначить его node1 — это именно то, что вы только что удалили!

Вы, вероятно, хотите сделать:

Проблема возникает, когда ваш начальный головной узел соответствует значению.

В этом случае вы устанавливаете следующий узел в качестве нового заголовка и избавляетесь от старого, а затем устанавливаете tmp в качестве нового заголовка,

Затем, когда вы выходите из операторов if, вы устанавливаете

Таким образом, в вашем блоке if вы устанавливаете текущий узел следующим узлом, а затем удаляете то, что раньше было вашим текущим узлом, а затем, выходя из оператора if, вы снова переходите к следующему узлу, фактически полностью пропуская новый головной узел.

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

Также внутри структуры объявлены функции-члены, которые обрабатывают список.

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

Двусвязный список

М ы рассмотрели односвязный список и пришли к неутешительным выводам – список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 1, с дополнительными манёврами можно добиться сложности вставки в конец порядка 1 и определения длины за O(1), но удаление с конца, вставка и поиск элемента остаются O(n).

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

Двусвязный список – это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.

Для реализации списка нам понадобится структура узел

Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура "Двусвязный Список" будет хранить свой размер (чтобы не пересчитывать количество элементов каждый раз), а также указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент

В случае, когда в списке нет элементов, оба они равны нулю. Если в списке один элемент, то оба указателя ссылаются на один и тот же элемент (соответственное, они равны). Об этом постоянно следует помнить: каждый раз, удаляя или вставляя элемент, придётся проверять, чтобы указатели head и tail правильно хранили адреса.

Первая функция, как обычно, создаёт экземпляр структуры DblLinkedList

В ней нет ничего интересного. Заодно опишем функцию, которая удаляет список

Теперь, определим набор стандартных функций – pushFront и popFront для работы с головой, pushBack И popBack для работы с последним элементом, getNth, insert и deleteNth для вставки и удаления в произвольное место.

Вставка спереди очень похожа на вставку в односвязный список. Сначала создаётся новый элемент

потом задаём ему значения

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

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

Теперь перекинем указатель head на вновь созданный элемент и увеличим значение счётчика size

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

Сначала создадим указатель на первый элемент списка. Он понадобится, чтобы после изменения всех указателей prev и next мы смогли удалить узел.

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

Далее проверяем, что удаляемы элемент не является одновременно последним (когда в списке всего один элемент), после чего освобождаем память.

Вставка в конец и удаление с конца очень похожи – просто мы переворачиваем список. Соответственное, все prev меняются на next, а head на tail

Получение n-го элемента очень простое и не отличается от оного для односвязного списка.

Можно улучшить эту функцию: если список длинный, то в зависимости от индекса можно проходить либо с начала в конец, либо с конца в начало. Это позволяет всегда использовать не более N/2 шагов.

Теперь можно написать функцию удаления и вставки узла. Сначала находим нужный элемент, затем создаём либо новый узел (если вставка), либо указатель на удаляемый элемент. Затем изменяем все указатели.

Не забываем, конечно, смотреть за значениями head И tail, чтобы они указывали на существующие в данный момент элементы.

Добавим пару вспомогательных функций, которые помогут в работе. Первая – это печать списка. Так как тип значения – void*, то необходимо передавать функцию печати одного элемента.

В примерах будем использовать переменные типа int

Вторая функция – создание списка из массива

Теперь можно пользоваться двусвязным списком

Сортировка вставками

Р анее мы рассмотрели алгоритм сортировки однонаправленного связного списка методом слияния. Двусвязный список можно сортировать точно также, поэтому сейчас рассмотрим другой алгоритм – сортировку вставками. Суть алгоритма очень простая – создаём новый двунаправленный связный список. Вставляем в него первый элемент неотсортированного списка. Для вставки второго элемента проходим по отсортированному списку и ищем место, куда вставить. Если место не найдено, то вставляем в конец. Очевидно, что если тип данных не известен, то необходимо будет передавать функцию сравнения, с помощью которой можно изменить порядок сортировки.

Для реализации нам понадобится ещё одна функция – вставка до указанного элемента. Эта функция будет получать указатель на список, указатель на узел, перед которым нужно вставить элемент и новые данные.

Теперь непосредственно сортировка

Видно, что в конце в переданном списке не остаётся элементов, так как мы их выталкиваем, так что старый список мы подменяем на вновь созданный.

Сложность алгоритма – O(n 2 ), мы имеем одни проход по неотсортированному списку сложностью порядка n, для каждого элемента проходим по отсортированному.

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

Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список

Каждый узел двунаправленного (двусвязного) линейного списка (ДЛС) содержит два поля указателей — на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит нулевое значение. Указатель на следующий узел последнего узла также содержит нулевое значение.

Узел ДЛС можно представить в виде структуры:

Основные действия, производимые над узлами ДЛС:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Удаление корня списка
• Вывод элементов списка
• Вывод элементов списка в обратном порядке
• Взаимообмен двух узлов списка

Инициализация ДЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поля указателей на следующий и предыдущий узлы содержат нулевое значение.

Добавление узла в ДЛС

Функция добавления узла в список принимает два аргумента:

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

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ДЛС включает в себя следующие этапы:

• создание узла добавляемого элемента и заполнение его поля данных;
• переустановка указателя «следующий» узла, предшествующего добавляемому, на добавляемый узел;
• переустановка указателя «предыдущий» узла, следующего за добавляемым, на добавляемый узел;
• установка указателя «следующий» добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
• установка указателя «предыдущий» добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).

Таким образом, функция добавления узла в ДЛС имеет вид:

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ДЛС

В качестве аргументов функции удаления узла ДЛС передается указатель на удаляемый узел. Поскольку узел списка имеет поле указателя на предыдущий узел, нет необходимости передавать указатель на корень списка.

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ДЛС включает в себя следующие этапы:

• установка указателя «следующий» предыдущего узла на узел, следующий за удаляемым;
• установка указателя «предыдущий» следующего узла на узел, предшествующий удаляемому;
• освобождение памяти удаляемого узла.

Удаление корня ДЛС

Функция удаления корня ДЛС в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

Вывод элементов ДЛС

Функция вывода элементов ДЛС аналогична функции для ОЛС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

Для ДЛС также можно вызвать функцию вывода элементов списка в обратном порядке.

Вывод элементов ДЛС в обратном порядке

Функция вывода элементов ДЛС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке.

Взаимообмен узлов ДЛС

В качестве аргументов функция взаимообмена узлов ДЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

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

• заменяемые узлы являются соседями;
• заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.

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

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

Функция взаимообмена узлов списка выглядит следующим образом: