tasman Jun 30 2007 at 22:58

Усложнение задачи про списки

1 min

7.7K

Comments 23

posthuman Jul 1 2007 at 01:23

Кажется так:
Проходим по списку и делаем две операции: считаем кол-во нодов и разворачиваем поинтеры в обратную сторону.

0-->0--> ===> 0<--0<-- // разворачивание, другого слова не нашел :)

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

пи.си. кажись сложно будет понять, без рисунка.

asgard Jul 1 2007 at 01:27

а если список двусвязный?
в данном случае развернуть поинтеры не рекурсивно будет довольно проблемно.

posthuman Jul 1 2007 at 01:40

Если список двухсвязный, то решение такое же, только разворачивать ничего не надо. Типа идешь по next, если дошел до начала, то есть круг. Подсчет также тривиален.

asgard Jul 1 2007 at 01:46

просто и в случае односвязного разворичивать не нужно.
есть исходный список list *src, делаем list *tmp = src. в цикле во время обхода подсчитываем кл-во элементов. если tmp == src, значит список циклический, если tmp == NULL, значит нет.

posthuman Jul 1 2007 at 01:54

:)
если он циклический, то вы застрянете в цикле, и до NULL не дойдете.

posthuman Jul 1 2007 at 01:55

а также до src.

asgard Jul 1 2007 at 01:56

кто вам такое сказал?
если заведомо известно, что src суть началос списка, то данный вариант работоспособен.

posthuman Jul 1 2007 at 02:01

(0)-->(1)-->(2)-->(3)-->(4)-->(5)

Представте себе, что (5)-->(2)
попав в цикл, вы будете блуждать в нем..

tasman Jul 1 2007 at 02:34

А как определить что поинтер "неразвернутый"?

posthuman Jul 1 2007 at 14:34

начальный лист:

(0)-->(1)-->(2)-->(3)-->(4)-->(5) + (5)-->(2)

после прохождения:

(0)(5)

(2)-->(5) это и есть не развернутый поинтер, тот который не нужно разворачивать, чтобы попасть куда-то.

posthuman Jul 1 2007 at 14:39

баг какой-то, не дает развернуть стрелки.. Все поинтеры от 0 до 5 идут в обратном порядке, и только (2)-->(5) в другом.

tasman Jul 1 2007 at 16:24

Правильно ли я понял, что "неразворот" определяется по тому, что за "меньшим" (2) следует "больший" (5)? Если так, то видимо я не очень корректно поставил условие задачи. Как я уже заметил в http://www.habrahabr.ru/blog/sport_progr…
над элементами списка порядок не определен, поэтому сказать что (2) меньше (5) нельзя. Фактически есть только указатели, а как их там нам менеджер памяти раздал, в каком порядке - неизвестно.

asgard Jul 1 2007 at 01:26



list *tmp = source_list, *prev = NULL;

int i = 0, cyclic = 0;





for(;;) {

  if(tmp == NULL) {

     cyclic = 1;

     break;

  }

  if((i > 0) && (tmp == source_list)) {

     break;

  }



  i++;

  tmp = tmp->next;

}



if(cyclic)

 printf("Nodes number in the cyclic list is %d\n", i);

else

 printf("This list was not cyclic one.\n");

asgard Jul 1 2007 at 01:26

чёрт, здесь prev не нужен =)

asgard Jul 1 2007 at 01:29

и естесвенно в первом ифе в цикле cyclic = 0, а во втором = 1.
p/s когда же я научусь проверять комментарии перед отправкой? =)

tasman Jul 1 2007 at 02:31

Да, моя ошибка, список конечно не закольцованый, а просто имеющий цикл. То есть 1, 2, и так далее, i элементы в цикле могут не состоять.

crazylammer Jul 1 2007 at 13:31

Наверное, можно сделать так. Начинаем идти с первого элемента двумя указателями. Один - с шагом 2, другой - с шагом 3. Если есть цикл то второй в какой-то момент догонит первого (НОД(2, 3) = 1). Тогда элемент, в котором догнали, входит в цикл. Ну и все, пройдем по циклу один раз, считая элементы.

Псевдокод:

p1 = begin, p2 = begin;

while (p1 != p2) {
p1 += 2, p2 += 3;
if (кто-то вылез за границу) - цикла нет.
}
int length = 1;
p2++;
while (p1 != p2) {
p2++;
length++;
}
length - ответ

Решение неоптимально (не использует изменяемость списка, будет сделано в худшем случае несколько проходов (штук 6, что ли)), но все равно за O(n).. Пока ничего лучшего мне в голову не приходит.

crazylammer Jul 1 2007 at 13:53

А, ну разумеется, количество проходов можно сократить (первый указатель - +1; второй - (+1 - сравнили с первым, +1 - сравнили), но со временем я погорячился - будет длина цикла + длина "предцикла" + еще один лишний проход по циклу для подсчета. Можно ли избавиться от этого прохода (как-то поменяв список), мне не очевидно :).

tasman Jul 1 2007 at 14:13

Подходит. А если теперь необходимо найти еще и длину "предцикла"?

crazylammer Jul 1 2007 at 14:26

Первое, что приходит в голову - один указатель бегает по циклу, другой идет от начала. Второй сделал шаг - первый оббежал весь цикл. Не встретились - второй опять делает шаг. Но длина цикла*длина начала - наверное, долго. Еще подумаю ;).

crazylammer Jul 1 2007 at 15:04

А что имеется в виду под изменяемостью списка? Значения в узлах или порядок соединения элементов? И какие операции разрешены над элементами списка? Только сравнение на равенство, или, например, на них определен порядок?

tasman Jul 1 2007 at 16:14

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

marcor Dec 25 2018 at 12:07

Забавно:, с 2007 года никто не предложил полного решения.

Мне начинает приходить в голову, что в общем случае без использования дополнительных данных это невозможно, ибо нет признака посещённости.
По-хорошему, я бы предложил обходить такой список как дерево: через добавление чёрно-серо-белой окраски элементов.

Show the best of all time