Поменять местами ноды в односвязном списке
Я застрял на применении односвязного списка. Проблема в том, что я не могу понять почему не меняются местами последний и предпоследние элементы списка.
Чтобы поменять первый и последний узлы в односвязном списке, можно три случая рассмотреть:
- меньше двух узлов: вернуть список как есть
- ровно два узла: поменять узлы местами
- больше двух: сделать, чтобы последний узел указывал бы на второй узел, а предпоследний — на первый.
где next_to_last() ищет предпоследний узел:
Это достаточно прямолинейное решение в лоб, возможно есть более элегантный подход.
Поменять местами два элемента односвязного списка
Поменять два элемента односвязного списка
Я где-то ошибся, и функция swap(smen2 -> pNext, smen1 -> pNext); в строке 123 ничего не меняет.
Поменять местами два элемента двусвязного списка
Доброго времени суток. Помогите пожалуйста с задачей. Необходимо реализовать функцию, которая.
Поменять местами два элемента двусвязного списка и удалить из него указанный элемент
Дан двусвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка.
Поменять местами последний и предпоследний элементы односвязного списка
Ребят, помогите, пожалуйста, реализовать ф-ию замены последнего и предпоследнего элементов местами.
Сообщение было отмечено Dennis Ritchie как решение
Решение
Сообщение от Nosey
Сообщение от Dennis Ritchie
Когда речь идет о списках, хранящих какие-то "полезные данные", задание "поменять местами два элемента" — неоднозначно.
* Во-первых, в списке "поменять местами два элемента" можно путем перецепления ссылок на узлы списка. "Полезные данные" останутся на прежних местах в памяти, но порядок физических узлов в списке изменится.
* Во-вторых, в списке "поменять местами два элемента" можно просто путем обмена "полезных данных", хранящихся в узлах, оставив ссылки нетронутыми. В таком случае наоборот, "полезные данные" обменяются в памяти, но порядок физических узлов в списке останется прежним.
С точки зрения распечатки содержимого списка, результат будет одним и тем же в обоих случаях. Однако побочные эффекты этих вариантов различаются. Например, если у меня есть два посторонних внешних указателя на обмениваемые узлы списка, то в первом способе "полезные данные", видимые через эти указатели, останутся прежними. А во втором способе они тоже обменяются.
О каком именно обмене идет речь?
Второй способ, понятное дело, применим к любому контейнеру. Поэтому когда в задаче явно говорят о списке, то это зачастую является "намеком" именно на первый способ.
Как поменять местами позиции двух узлов в односвязном списке, изменяя только указатели?
Я пытаюсь поменять местами два узла односвязного списка с заданными нулями индексами. В моем коде я обрабатываю много случаев, но этот подход действителен только когда j-i<=2 . Если между i и j есть разница в 3 или более, я не смогу ее обработать.
Пожалуйста, помогите мне исправить мой подход.
3 ответа
Основы указателя-жокея для замены узлов в связанном списке просты:
- Найдите в списке указатели, которые указывают на узлы, которые вы хотите поменять местами. Одним из этих указателей может быть указатель head , но по крайней мере один из них будет указателем next в списке. Помните, что это указатели, которые указывают на узлы, которые вы меняете.
- Поменяйте местами эти указатели
- Поменяйте местами указатели next этих узлов, чтобы восстановить оставшийся порядок в списке.
- Вот и все.
Для этого проще всего использовать указатели на указатели . Это позволяет избежать необходимости полностью обходить указатели prev , что делает алгоритм ужасно более сложным, чем он должен быть.
Ваш подход доблестный, но явно сложный. Придерживайтесь алгоритма, приведенного выше, и это станет намного понятнее, что нужно. Найдите несколько указателей, указывающих на то, что вы хотите поменять местами, поменяйте местами, а затем поменяйте местами внутренние указатели.
Учитывая все это, алгоритм реализован следующим образом (сохраняя ваше желание сканировать список только один раз, чтобы найти оба узла для обмена). Комментарии о том, как алгоритм соответствует коду, встроены:
Это не сделало бы справедливости без действующего примера. Далее будет построен упорядоченный список из десяти элементов, пронумерованных 1..10. Затем он использует описанную выше процедуру подстановки с нулевым индексом, чтобы поменять местами различные элементы, в частности, что-то, что меняет головной узел, хвостовой узел и некоторые внутренние узлы, а затем отменяет все это, изменяя свопы, чтобы прийти к списку, который мы начали с.
Большинство крайних случаев, которые вы пытаетесь избежать, просто исчезают, если вы помните, что пытаетесь сделать: меняйте указатели, а не узлы. Хитрость заключается в том, чтобы найти указатели (не их значения; фактические указатели), которые указывают на узлы, которые вы хотите поменять, и поменять значения этих указателей.
Похоже, вы стараетесь справиться с угловыми случаями, но ваш код все еще не в состоянии справиться с базовыми случаями, и это потому, что вы делаете его сложным. Попробуйте еще раз проанализировать — что это за задача и каковы требования для ее решения.
Давай я тебе помогу : —
- Задача 1 — Нахождение i-го индексного узла и j-го индексного узла путем обхода связанного списка (нет необходимости находить расстояние между ними)
- Задача 2 — Замена обоих узлов
Требования — Чтобы поменять узел, получить доступ к его предыдущему узлу (что кажется вам известным, так как вы пробовали это в своем коде)
Некоторые угловые случаи —
- Если я == j или i> j (управляется вашим кодом)
- Если у i-го узла нет предыдущего узла (т. Е. Он возглавляет связанный список)
Теперь попробуйте проанализировать ваш код.
Для справки смотрите код ниже
Надеюсь, это поможет.
Продолжайте спрашивать, продолжайте расти 🙂
Вы делаете свою логику свопинга более сложной, чем она должна быть. Попробуйте что-то вроде этого:
Поменять местами два узла в односвязном списке
Как переключить два узла в односвязном списке на паскале?
(Здесь pNode — указатель на узел в списке.)
Узлы определяются следующим образом:
Этот код не работает. Он либо не компилируется, говоря «Невозможно взять адрес константных выражений», либо просто ничего не делает. Я думаю, это связано с тем, как работают указатели.
Я нашел актуальную информацию здесь, но я не читаю C.
Спасибо за любой совет!
задан 13 июн ’14, 22:06
Можете ли вы показать, как определены ваши узлы — Ken White
Спасибо. Я не хотел просто предположить, что ваше определение узла было таким же, как код C, который вы связали. 🙂 — Ken White
Код, который не компилируется, не отображается? Или где ошибка? — Marco van de Voort
2 ответы
Думаю, что-то вроде этого сработает:
Я не был уверен, что это сработает в классическом Паскале. Я не очень хорошо помню, что было раньше — Delphi меня избаловал. 🙂 — Кен Уайт
Что-то вроде этого должно сработать для вас. Он использует локальную переменную типа Node (которая, предположительно, является указателем на PNode) в качестве заполнителя.
Вот его версия, которая не является методом объекта, с консольным приложением, которое его тестирует:
Спасибо за хороший ответ, но он не работает для меня. Странно, один из узлов вычеркнут из списка напрочь! — миги
Он отлично работает в тестовом приложении, которое я предоставил. Я не могу объяснить, почему это не работает, когда вы реализуете это в своем коде, потому что я не вижу вашего кода. — Кен Уайт
Я просто перебираю узлы списка, чтобы записать их. После подкачки один из замененных элементов просто опускается. Хм. — миги
Я не вижу вашей реализации списка, как вы добавляете элементы или выделяете память или какую-либо другую информацию. Я добавил пару строк кода в тестовое приложение выше, чтобы продемонстрировать, что оба узла не повреждены (но поменялись местами) после замены. Просто чтобы уточнить: вы используете только функцию List.switch в своем коде, а не код тестового приложения, который использует New и Dispose? — Кен Уайт
Я понимаю. Да, я тестирую его на своем коде и получаю здесь какое-то странное поведение. Список обрезается перед первым замененным узлом, а узел перед первым замененным узлом указывает на второй замененный узел. Может проблема в моей реализации, но я трижды проверил и так не думаю. — миги
Не тот ответ, который вы ищете? Просмотрите другие вопросы с метками linked-list pascal or задайте свой вопрос.