VPF::Двунапрвленный линейный список

Annihilator

Дата 8.5.2008, 13:37 (ссылка)

(нет голосов)

Загрузка ...

bytegrinder

Профиль
Группа: Участник
Сообщений: 493
Регистрация: 21.11.2006
Где: Омск

Репутация: 1
Всего: 3

Цитата(JackYF @ 8.5.2008, 16:29)

Цитата(Annihilator @ 8.5.2008, 02:36

)

А почему нельзя рекурсией??

Гланды можно через одно место вырвать, но зачем? smile

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

Тогда вопрос, где рациональнее будет использовать рекурсию. В деревьях?

--------------------

Если вы не можете сделать хоpошyю пpогpаммy, сделайте, чтобы она по кpайней меpе выглядела хоpошо

baldina

Дата 8.5.2008, 13:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

не понял, тебе нужен шаблонный двусвязный список или общий шаблонный интерфейс, который может быть реализован двусвязным списком или чем-нить еще?

Добавлено @ 13:40

Цитата

Тогда вопрос, где рациональнее будет использовать рекурсию

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

Добавлено @ 13:42
почти все алгоритмы типа "разделяй и властвуй" просто и красиво реализуются рекурсией

Это сообщение отредактировал(а) baldina - 8.5.2008, 13:58

Любитель

Дата 8.5.2008, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 24
Всего: 92

Цитата(Annihilator @ 8.5.2008, 13:37

)

Тогда вопрос, где рациональнее будет использовать рекурсию. В деревьях?

Для рекурсивных структур (те же деревья), для алгоритмов с возвратом и пр. рекурсивная реализация выглядит проще. И для начала вполне сойдёт. Если будут проблемы с проивзодительностью (что в больших проектах лучше анализировать, конечно, нормальным профайлером) - любую рекурсию можно развернуть с помощью стека (иногда лучше использовать очередь, но суть та же).

Добавлено через 12 минут и 40 секунд
Есть понятие tail recursion ("хвостовая" рекурсия) - когда рекурсивный вызов происхоодит в самом конце. Типа:

Код


void printList(ListNode* node)
{
   printData(node->data);
   printList(node->next); // после _ничего_ нет
}

Точнее даже не обязательно именно в конце - важно, что результаты рекурсивного вызова не сказываются на операторах, следующих после рекурсивного вызова:

Код


void printList(ListNode* node)
{
   printData(node->data);
   printList(node->next);
   printf("%s", "End node printing");
}

"Хвостовая" рекурсия всегда разворачивается в обычный цикл (без использования стека).

--------------------

http://oryolalex.mybrute.com

JackYF

Дата 8.5.2008, 19:26 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Любитель @ 8.5.2008, 12:52

)

"Хвостовая" рекурсия всегда разворачивается в обычный цикл (без использования стека).

на всех компиляторах и во всех языках? пруфлинк?

--------------------

Пожаловаться на меня как модератора можно здесь.

Любитель

Дата 9.5.2008, 00:19 (ссылка)

(нет голосов)

Загрузка ...

Программист-романтик

Профиль
Группа: Комодератор
Сообщений: 3645
Регистрация: 21.5.2005
Где: Воронеж

Репутация: 24
Всего: 92

Нет, я не про то smile

Речь про другое - разворачивается (ручными средствами) в цикл без привлечения своего стека/очереди. Банальный вариант - заменить рекурсию переприсваиванием параметров и гоуту на начало функции. Как оптимизаторы компилеров действуют - это уже к докам по компилеру.

--------------------

http://oryolalex.mybrute.com

JackYF

Дата 9.5.2008, 12:12 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Любитель @ 8.5.2008, 23:19

)

разворачивается (ручными средствами)

Всё, я тебя понял smile

--------------------

Пожаловаться на меня как модератора можно здесь.

r18Romik

Дата 12.5.2008, 06:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 33
Регистрация: 13.2.2008
Где: Пермь

Репутация: нет
Всего: нет

Люди всё таки кто нибудь может помочь...со структурой???
Читать выше.....

bsa

Дата 12.5.2008, 14:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

Цитата(r18Romik @ 12.5.2008, 06:38)

Люди всё таки кто нибудь может помочь...со структурой???
Читать выше.....

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »