| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Задача на двухсторонний список |
| Автор: Goryachev 30.3.2005, 23:56 |
| Задача: Сделать двухсторонний список, пользуясь одним указателем в структуре, и двумя внешними указателями на список. Обсудите. Ответ приведу позже. |
| Автор: cardinal 31.3.2005, 01:34 |
| В голову пришло следующее... |
| Автор: Олег М 31.3.2005, 07:49 | ||
 Ну да, p1,p2 - указывают на текущю позицию, элементы указывают разные стороны - p1->item - в сторону головы, p2->item в сторону хвоста. При смене текущей позиции нужно менять указатели соответствующим образом |
| Автор: cardinal 31.3.2005, 13:44 | ||
Я бы только сказал, p1->item - в сторону текущего элемента, а p2->item в сторону его предыдущего элемента... Уж больно трудно в таком списке сказать где голова, а где хвост...  |
| Автор: maxim1000 31.3.2005, 14:28 |
 а я не понял задачи что такое двусторонний список? |
| Автор: _hunter 31.3.2005, 14:38 |
| список, двжение по элементам которого возможно и вперед и назад |
| Автор: maxim1000 31.3.2005, 14:44 |
| тогда не надо даже двух внешних указателей (достаточно одного)... просто делаем кольцевой список, движение вперед - как обычно, движение назад - двигаемся вперед, пока не найдем элемент, который указывает на исходный |
| Автор: _hunter 31.3.2005, 15:20 |
| а если элементов много? слишком долго ходить придется... |
| Автор: maxim1000 31.3.2005, 16:25 | ||||
а о времени речь не шла
|
| Автор: Олег М 31.3.2005, 16:44 | ||
А о чём тогда вообще речь шла? Как раз об этом! |
| Автор: Goryachev 1.4.2005, 09:24 |
| cardinal Очень круто все сделанно, но у тебя список изменяется динамически, итого: чтоб завершить работу с таким списком (если параметры by value), то надо будет возвращаться до начала обратно, чтоб плменять поинтеры на их начально правильное положение. Теперь подумайте, как это сделать, не изменяя динамически поинтеры.  |
| Автор: cardinal 1.4.2005, 15:04 | ||||
Это чтобы delete сделать чтоли? А я его так сделаю: См. шаг три. Я рекурсивно спущусь по p1 и p2 функцией, которая будеть выглядеть примерно так функция (получает поинтер x) { if pointer(элемента) <> NULL ,то функция(pointer(элемента)); else delete x; }
Может позже... |
| Автор: yaja 4.4.2005, 17:42 |
| Не понял ((( По определению двунаправленный список, ето такая хрень, в которой для любого элемента можно получить предыдущий и следующий. Однако, при предложенных требованиях, очевидно, ето сделать нельзя. Т.ч уточните, что должен делать етот "список" ))) |
| Автор: Goryachev 4.4.2005, 22:19 | ||
Не совсем. Если ты киваешь на определенный элемент, то можешь получить предыдущий и следующий. Решение дам в субботу. Еще есть время подумать... |
| Автор: yaja 8.4.2005, 17:15 |
| Что-то мне в голову такой изврат пришел в голову... Будем хранить не указатель в каждом элементе, а xor указателей на предыдущий и на следущий, а внешние указатели будут хранить текущий элемент(p1) и элемент(p2) из которого мы пришли в p1. Тогда указатели на следущий и предыдущий элемент - p2 и (p1->xoredPointer) ^ p2 в зависимость откуда мы пришли в p1. Вроде должно работать |
| Автор: Goryachev 10.4.2005, 23:40 |
| yaja Зверь, это то решение, которое я хотел дать. Все, решили. |