Как удалить элемент из списка?, программирование |
Добро пожаловать, гость ( Вход | Регистрация )
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
Как удалить элемент из списка?, программирование |
ierton |
12.11.2010, 0:01
Сообщение
#1
|
Новичок Группа: Пользователи Braingames Сообщений: 2 Регистрация: 12.8.2010 Пользователь №: 20 521 |
Весь форум не читал, прошу прощения если задача с бородой. Говорят, что спрашивали на собеседовании в гугле.
Нужно реализовать удаление элемента односвязного списка, имея только указатель на удаляемый элемент (известно, что он не является последним). Другими словами, нужно сделать так, чтобы предыдущий элемент стал связан с следующим за данным. Короче говоря: struct Item { void* data; struct Item * next; } ; void delete_item(struct Item * item) { ??? } Список конечный, признак последнего элемента - p.next == 0. Язык - С. |
Alexandroppolus |
12.11.2010, 10:09
Сообщение
#2
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
Нужен элемент, предшествующий удаляемому.
Потому идем с начала списка, тогда либо начальный элемент соответствует item (в этом случае началом списка будет след. элемент, а этот просто удаляем из памяти), либо находим элемент, у которого next равен item (тогда присваиваем ему item->next, и удаляем item) |
De_Bill |
12.11.2010, 12:40
Сообщение
#3
|
Активный участник Группа: Пользователи Braingames Сообщений: 538 Регистрация: 24.7.2010 Пользователь №: 20 304 |
Долговато
Не проще ли, если у нас есть фактически ячейка памяти для Текущего элемента, записать в нее Следующий за ним(я боюсь писать код потому что меня бесят указатели), и тогда Предыдущий будет ссылаться сразу на Следующий? |
Powered by Java |
12.11.2010, 13:46
Сообщение
#4
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
Долговато Не проще ли, если у нас есть фактически ячейка памяти для Текущего элемента, записать в нее Следующий за ним(я боюсь писать код потому что меня бесят указатели), и тогда Предыдущий будет ссылаться сразу на Следующий? Так и надо Главное не забыть оригинальный следующий обнулить, что бы память не текла. |
Alexandroppolus |
12.11.2010, 18:10
Сообщение
#5
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
Блин, точно! Ведь знал же когда-то (совсем недавно)...
|
Troublemaker |
12.11.2010, 19:10
Сообщение
#6
|
Участник Группа: Пользователи Braingames Сообщений: 98 Регистрация: 3.2.2010 Пользователь №: 19 190 |
Весь форум не читал, прошу прощения если задача с бородой. Говорят, что спрашивали на собеседовании в гугле. Нужно реализовать удаление элемента односвязного списка, имея только указатель на удаляемый элемент (известно, что он не является последним). Другими словами, нужно сделать так, чтобы предыдущий элемент стал связан с следующим за данным. Короче говоря: struct Item { void* data; struct Item * next; } ; void delete_item(struct Item * item) { ??? } Список конечный, признак последнего элемента - p.next == 0. Язык - С. Так, не понял, а где указатель на начало списка? Про него ничего не сказано... P.S. Понял, в этом вся фишка вопроса. Но в таком случае ответ не чистый. Никакой уверенности в том, что на указанные элементы не ссылается кто-то извне, нет. Стало быть этот момент нужно уточнять. |
Powered by Java |
12.11.2010, 21:24
Сообщение
#7
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
Так, не понял, а где указатель на начало списка? Про него ничего не сказано... P.S. Понял, в этом вся фишка вопроса. Но в таком случае ответ не чистый. Никакой уверенности в том, что на указанные элементы не ссылается кто-то извне, нет. Стало быть этот момент нужно уточнять. В идеале, есть public List, в нем куча методов для работы с данными и private структура/класс Item. Так что внешних ссылок быть не должно, а head хранится непосредственно в List, у которого и просят имплементировать удаление. Кстати, проблему с последним элементом вполне возможно решить, но не средствами структуры, конечно. PS: однонаправленные списки - ЗЛО! |
Troublemaker |
12.11.2010, 21:33
Сообщение
#8
|
Участник Группа: Пользователи Braingames Сообщений: 98 Регистрация: 3.2.2010 Пользователь №: 19 190 |
В идеале, есть public List, в нем куча методов для работы с данными и private структура/класс Item. Так что внешних ссылок быть не должно, а head хранится непосредственно в List, у которого и просят имплементировать удаление. Кстати, проблему с последним элементом вполне возможно решить, но не средствами структуры, конечно. PS: однонаправленные списки - ЗЛО! Тогда предлагаю "многонаправленные": Есть список со случайными связями. То есть он однонаправленный (есть поле .next), кроме того, есть поле .random, которое ссылается на некий элемент из этого же списка. Задача: клонировать данный список (с сохранением связей). Ограничение: памяти использовать не больше, чем нужно для изначального списка и для нового. |
De_Bill |
13.11.2010, 7:55
Сообщение
#9
|
Активный участник Группа: Пользователи Braingames Сообщений: 538 Регистрация: 24.7.2010 Пользователь №: 20 304 |
"Задача: клонировать данный список (с сохранением связей). Ограничение: памяти использовать не больше, чем нужно для изначального списка и для нового."
поиск в глубину надо провернуть |
Powered by Java |
13.11.2010, 8:15
Сообщение
#10
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
|
De_Bill |
13.11.2010, 8:56
Сообщение
#11
|
Активный участник Группа: Пользователи Braingames Сообщений: 538 Регистрация: 24.7.2010 Пользователь №: 20 304 |
Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс
идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi) пишем Item1=A1 Item2=A2 while (Item1!=Ai.random){ Item1=Item1.next Item2=Item2.next } Bi.random=Item2; Ну и прокручиваем это для каждого i Конечно тут две лишних переменных, но, думаю, это ничего |
Powered by Java |
13.11.2010, 9:14
Сообщение
#12
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
Ну там какой-то странный вариант дфса конечно получается ну да ладно. хотя да, это вообще будет не дфс идем по некстам до конца первого списка, создаем элементы второго, пока что только с полями некст дальше берем i-тый элемент первого списка(Аi), и соответствующий ему эл-т второго списка (Bi) пишем Item1=A1 Item2=A2 while (Item1!=Ai.random){ Item1=Item1.next Item2=Item2.next } Bi.random=Item2; Ну и прокручиваем это для каждого i Конечно тут две лишних переменных, но, думаю, это ничего т.е. рандом элементы искать для каждого элемента нового списка? Слишком уж долго... О(n^2)... |
De_Bill |
13.11.2010, 10:37
Сообщение
#13
|
Активный участник Группа: Пользователи Braingames Сообщений: 538 Регистрация: 24.7.2010 Пользователь №: 20 304 |
Все зависит от того насколько сильно ограничение по памяти. Понятно что с булевским массивом или еще чем любой дуралей за О(n) решит
|
Powered by Java |
13.11.2010, 10:40
Сообщение
#14
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
Все зависит от того насколько сильно ограничение по памяти. Понятно что с булевским массивом или еще чем любой дуралей за О(n) решит А надо за О(n) и без памяти лишней PS: предлагаю финальное решение этой задачи через личку обсуждать. Пусть остальные тоже голову поломают |
Alexandroppolus |
13.11.2010, 10:56
Сообщение
#15
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
|
Powered by Java |
13.11.2010, 11:07
Сообщение
#16
|
Активный участник Группа: Модераторы BrainGames Сообщений: 544 Регистрация: 9.6.2008 Пользователь №: 8 397 |
|
Alexandroppolus |
13.11.2010, 11:28
Сообщение
#17
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
|
Alexandroppolus |
13.11.2010, 12:30
Сообщение
#18
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
Для всех интересующихся уточню: на этот раз структура элемента
Item { Item * next; Item * random}; т.е. только 2 указателя для маневров. Рандомная ссылка, как я понял, может указывать вперед и назад. В таком виде пока не решил. ( upd: решил, интересная задачка) |
ierton |
13.11.2010, 12:41
Сообщение
#19
|
Новичок Группа: Пользователи Braingames Сообщений: 2 Регистрация: 12.8.2010 Пользователь №: 20 521 |
Нужен элемент, предшествующий удаляемому. Потому идем с начала списка, тогда либо начальный элемент соответствует item (в этом случае началом списка будет след. элемент, а этот просто удаляем из памяти), либо находим элемент, у которого next равен item (тогда присваиваем ему item->next, и удаляем item) Нет, здесь идея именно в том, что указатель на начало списка неизвестен. Долговато Не проще ли, если у нас есть фактически ячейка памяти для Текущего элемента, записать в нее Следующий за ним(я боюсь писать код потому что меня бесят указатели), и тогда Предыдущий будет ссылаться сразу на Следующий? Да, это и есть решение Так, не понял, а где указатель на начало списка? Про него ничего не сказано... P.S. Понял, в этом вся фишка вопроса. Но в таком случае ответ не чистый. Никакой уверенности в том, что на указанные элементы не ссылается кто-то извне, нет. Стало быть этот момент нужно уточнять. Верно, гарантии нет. Но условие и не требует от решения каких-либо гарантий, лишь бы итоговый список оказался правильным. Боюсь, что если уточнять, то совсем очевидно станет. |
Troublemaker |
15.11.2010, 16:20
Сообщение
#20
|
Участник Группа: Пользователи Braingames Сообщений: 98 Регистрация: 3.2.2010 Пользователь №: 19 190 |
|
Упрощённая версия | Сейчас: 29.4.2024, 5:24 |