Для пользователей, которые регистрируются. Если Вам не приходит письмо с подтверждением email, пишите на admin[at]quizful[dot]net - будем подтверждать вручную. Просим прощения за доставленные неудобства.
С уважением,
команда Quizful
С уважением,
команда Quizful
Знаете ли Вы, что
Если у вас есть уникальная статья и вы хотите, чтобы она стала достоянием общественности, вы можете разместить ее на Quizful.
←
→
Топ контрибуторов
←
→
Лента обновлений
|
ссылка
18:56:00
Комментарий от vasilchenko: Это не трудно, но мало кто мыслит в отличной от деся... |
|
ссылка
18:28:37
Добавлен вопрос в тест Java - Основы
|
|
ссылка
18:14:25
Комментарий от asker: молоток, возьми с полки пирожок. |
|
ссылка
17:36:28
Комментарий от alex_skn: korniltsev, Вы правы. Ответ к задаче исправил, спасибо ... |
|
ссылка
17:26:36
Комментарий от Petr0: Аналогично |
Статистика
Тестов: 130, вопросов: 5785. Пройдено: 113088 / 461686.
Копирование линейного списка
← к списку ← →
Вопрос
Дан линейный список. Каждый элемент содержит 2 указателя. Первый указывает на следующий элемент в списке. Второй указывает на случайный элемент в списке (может указывать на себя). Задача создать копию исходного списка за линейное число операций. Разрешено использовать память выделенную под исходный список + такой же по размеру блок памяти, выделенный под новый линейный список и блок памяти произвольного размера, который не зависит от размера исходного линейного списка. В конечном итоге должно получится 2 одинаковых линейных списка.
Ответ
Пусть a , b , c ,d .... - исходный линейный список
a.1 - первый указатель первого элемента
a.2 - второй указатель первого элемента
Создадим элемент a'.
a'.1 = a.1
изменим a.1
a.1 = указатель на a'
Создадим элемент b'.
b'.1 = b.1
изменим b.1
b.1 = указатель b'
Продолжаем для всех элементов списка.
a'.2 = (a.2).1
b'.2 = (b.2).1
и т.д.
Теперь восстанавливаем первые указатели в обоих списках
a.1 = a'.1
a'.1 = b.1
b.1 = b'.1
и т.д.
Получаем 5 * n операций, где n - длина исходного списка, то есть как и требовалось линейное число операций.
a.1 - первый указатель первого элемента
a.2 - второй указатель первого элемента
Создадим элемент a'.
a'.1 = a.1
изменим a.1
a.1 = указатель на a'
Создадим элемент b'.
b'.1 = b.1
изменим b.1
b.1 = указатель b'
Продолжаем для всех элементов списка.
a'.2 = (a.2).1
b'.2 = (b.2).1
и т.д.
Теперь восстанавливаем первые указатели в обоих списках
a.1 = a'.1
a'.1 = b.1
b.1 = b'.1
и т.д.
Получаем 5 * n операций, где n - длина исходного списка, то есть как и требовалось линейное число операций.
