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

Я работаю над проектом, который требует, чтобы я сортировал связанный список, используя сортировку вставкой, наиболее эффективным способом. Я написал алгоритм, который работал, но он был не самым эффективным — он сравнивал значения с начала списка, а не возвращался назад. Теперь у меня есть алгоритм, который сравнивает значения в обратном направлении, но он не работает. Отладчик показывает, что current-> prev — это nullptr, поэтому он не будет запускать функцию. У меня это инициализировано и когда я делаю cout prev это печатает значение. Я просмотрел другие посты на эту тему, но не могу найти, что не так с этой строкой моего кода. Вот заголовочный файл, который содержит функцию в классе связанного списка:

Вот исходный файл:

Решение

Я понял, как это исправить. Внутренний цикл побежал while (current != nullptr) поэтому, когда ток был во главе, и он был назначен current->prev это указывало на nullptr. Я изменил условие цикла while на current->prev != nullptr и теперь он работает правильно, так как он никогда не указывает на nullptr.

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

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

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

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

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

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

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

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

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

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

Читайте также:  Acronis true image hd disk migration utility

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Мтс набранный вами номер не используется

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

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

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

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

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

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

Подскажите как правильно сортировать двусвязный список. Сделал вот такую реализацию, но как вообще правильно нужно сортировать и какие есть варианты сортировки?

2 ответа 2

Традиционным алгоритмом сортировки для списка – именно списка – является алгоритм MergeSort, построенный на принципе "onion braid" ("косичка из луковиц"). Он прекрасно сортирует односвязные списки, а уж двусвязность списка никакой принципиальной роли в таком алгоритме не играет.

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

Именно этот алгоритм обычно реализуется в std::list::sort() . Собственно ради него шаблону std::list и дали свой собственный метод sort() .

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

Заводим K > 0 "крючков" (с номерами от 0 до K-1 ), на которые мы будем вешать промежуточные подсписки. Число K может быть произвольным, его роль станет понятна из дальнейшего описания

Берем первый узел node из исходного списка и вешаем его на крючок 0 , если он свободен (изначально он, разумеется, будет свободен)

Берем следующий узел node из исходного списка и пытаемся повесить его на крючок 0 . Мы сразу видим, что крючок занят (т.е. hooks[0] != nullptr ). Тогда мы снимаем с крючка 0 уже подвешенный туда ранее узел prev_node . Крючок 0 при этом освобождается)

затем соединяем узлы node и prev_node в сортированный список длины 2

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

Читайте также:  Чем лучше 64 битная система

Далее вешаем этот список длины 2 на крючок 1 (если он свободен)

Продолжаем в том же духе. Берем из входного списка очередной узел и вешаем его на крючок 0 . Берем из входного списка еще один очередной узел, видим, что крючок номер 0 занят. Сливаем эти узлы в отсортированный список длины 2. Пытаемся повесить его на крючок номер 1 . Видим, что он тоже занят (!). Сливаем два отсортированных списка длины 2 в один отсортированный список длины 4 и вешаем его на крючок 2 . Крючки 0 и 1 становятся свободными.

Продолжаем продолжать в том же духе. В каждый момент времени крючок номер k будет либо свободен, либо занят отсортированным списком длины 2 k . Каждый новый элемент из исходного списка либо подвешивается на свободный крючок 0 , либо вызывает движущийся слева-направо по массиву hooks каскад слияний и перевешеваний подсписков, пока не будет найден свободный крючок. Списки длины 1 объединяются в списки длины 2, списки длины 2 – в списки длины 4, длины 4 – в 8 и т.д. и т.п.

Разумеется, каскад перевешиваний должен останавливаться, если достигнут последний элемент массива hooks . Те подсписки, которые сумеют добраться до самого последнего элемента массива hooks , т.е крючка K-1 , сливаются в один длинный список и продолжают висеть на крючке K-1 . Таким образом подсписок на крючке K-1 может быть длиннее 2 K-1 .

  • Когда исходный список полностью вычитан и развешан по крючкам, просто делаем финальный проход по массиву hooks и сливаем все подвешенные на крючках подсписки в один финальный сортированный список.
  • Величина K , как сказано выше, может быть произвольной. Слишком малое значение K не сломает алгоритм, но понизит его эффективность. Имеет смысл выбирать K примерно равной log2 от ожидаемого количества элементов во входных списках. Понятно, что на 32-битной платформе нет смысле брать K больше, чем 32.

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

    Для работы с двусвязным списком можно просто постоянно поддерживать две ссылки prev и next при линковке элементов друг с другом. Однако, так как этот алгоритм часто перелинковывает элементы списка, возможно более разумным будет в течение всего алгоритма рассматривать список как односвязный, т.е. поддерживать только ссылки next . А уже в самом конце работы алгоритма, когда формируется финальный отсортированный список (на шаге 5), установить правильные значения ссылок prev .

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    Adblock detector