Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
Alvin Seville
332 / 265 / 131
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
1

Копирование односвязного линейного списка

08.07.2018, 18:54. Просмотров 1407. Ответов 5
Метки нет (Все метки)


Дан список, каждый узел которого в качестве данных имеет другой указатель на узел, причем известно, что он
указывает на какой-то элемент того же списка. Требуется построить копию данного списка, в которой дополнительный
указатель на узел («данные») указывает на узел копии с тем же номером в копии, с каким указатель в оригинале
для данного узла указывал на элемент исходного списка (за линейное время, на константной памяти, кроме заведения
копий узлов).
Можете дать подсказку того в каком направлении думать? Непонимание реализации именно в этом:
узел которого в качестве данных имеет другой указатель на узел, причем известно, что он
указывает на какой-то элемент того же списка
1
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.07.2018, 18:54
Ответы с готовыми решениями:

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

Создание линейного односвязного списка
-найти произведение элементов списка. -вывести на экран нечетные элементы списка.

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

Гайд по сортировке односвязного линейного списка
Посоветуйте пожалуйста толковый гайд по сортировке. Уже столько всего перерыл, прочитал, но понять...

5
Эксперт по математике/физике
4144 / 2048 / 422
Регистрация: 19.07.2009
Сообщений: 3,102
Записей в блоге: 23
08.07.2018, 22:58 2
Односвязный список состоит из узлов, причём каждый узел является парой из ссылки на следующий узел и данных.
В рассматриваемой задаче вторая компонента узла (данные) также является указателем, причём то, на что он указывает, во всех случаях также является узлом некоторого списка.
Проще говоря, в этой задаче узел - это пара из двух указателей, а все рассматриваемые указатели указывают исключительно на какие-то узлы.

Односвязный список есть первый его узел. Рекурсивно определяется множество узлов списка. Каждый узел состоит из двух указателей. Один из них указывает на "следующий" узел. А второй...
Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
узел которого в качестве данных имеет другой указатель на узел, причем известно, что он
указывает на какой-то элемент того же списка
указывает на какой-то узел этого же списка. Может, на себя. Может, на следующий. Может, на первый.

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

Все остальные обсуждения, как мне кажется, следует сопровождать иллюстрациями с двумя изоморфными непересекающимися графами узлов. Рисуйте.
1
Alvin Seville
332 / 265 / 131
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
09.07.2018, 00:06  [ТС] 3
Mysterious Light, я думаю что при создании копии списка следует где то хранить ссылки (которые лежат в информационных полях узлов списка). Только вот где и как...
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 997
09.07.2018, 11:30 4
Лучший ответ Сообщение было отмечено OwenGlendower как решение

Решение

делаешь в два шага
1) создать список того же размера но с пустым полем данных
2) делаешь двойной цикл прохода по двум очередям одновременно, в первом цикле берешь данные из ячейки первой очереди, во втором цикле находишь куда ссылка из данных указывает и записываешь соответствующую ссылку в данные в ячейке второй очереди.
1
Alvin Seville
332 / 265 / 131
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
09.07.2018, 17:08  [ТС] 5
wingblack, не списки, а именно очереди?
0
291 / 263 / 47
Регистрация: 09.04.2013
Сообщений: 997
10.07.2018, 09:22 6
Цитата Сообщение от Volobuev Ilya Посмотреть сообщение
wingblack, не списки, а именно очереди?
Ошибся, списки конечно.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.07.2018, 09:22

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

Сортировка односвязного линейного списка по алфавиту
Всем здравствуйте! Имеется линейный список. Помогите, пожалуйста, написать сортировку студентов...

Проход по элементам односвязного линейного списка
Допустим у меня существует класс линейного односвязного списка. Надо пройти по его элементам и...

Найти наименьший элемент односвязного линейного списка
Найти наименьший элемент односвязного линейного списка. Сценарий: обходя список найти минимальное...

Найти сумму элементов линейного односвязного списка
Доброго времени суток! Помогите пожалуйста решить информационное поле линейного односвязного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.