VPF::Двусвязный список. - Форум программистов

andrew_121

Дата 13.4.2009, 15:20 (ссылка)

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

Загрузка ...

Кодофей

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

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

mes, Вы правы! Начал реализовывать, и уперся smile

И так. Дисскусия продолжаеться. smile

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

Удалил аккаунт. Прощайте!

mes

Дата 13.4.2009, 15:22 (ссылка)

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

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

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

Цитата(andrew_121 @ 13.4.2009, 14:20

)

Начал реализовывать, и уперся smile smile

а чем не устраивает способ, где

Цитата

два итератора("быстрый" и "медленный" ),

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

http://opendots.net

andrew_121

Дата 13.4.2009, 15:27 (ссылка)

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

Загрузка ...

Кодофей

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

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

mes, Туплю по ходу smile

Не могу понять что и как... smile

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

Удалил аккаунт. Прощайте!

mes

Дата 13.4.2009, 16:35 (ссылка)

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

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

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

Цитата(andrew_121 @ 13.4.2009, 14:27

)

Не могу понять что и как...

вот набросок (работоспособность не проверял):

Код


struct node {  node * next;  };

bool fn(node *first)
{
    struct step { void operator ()(node *& it1, node *& it2, bool flag) { if (flag) it1=it1->next;  it2=it2->next;  }  } step;

    int counter=0;
    if  (first) for (node * it1 = first, * it2 = first->next; it2; step(it1, it2, ++counter & 1))
                  if (it2 && it2==it1) return true; // замкнут
    return false; // найден конец
}

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

http://opendots.net

J0ker

Дата 13.4.2009, 16:35 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(mes @ 13.4.2009, 10:26

)

Для остальной части задачи надо мозги напрячь.. попозже попробую..

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

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

mes

Дата 13.4.2009, 16:40 (ссылка)

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

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

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

Цитата(J0ker @ 13.4.2009, 15:35

)

т.е. простейший вариант пустить два "медленных" итератора -

нда..самое эффективное решение как всегда лежит на поверхности smile

J0ker, smile

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

http://opendots.net

jonie

Дата 14.4.2009, 09:20 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

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

Цитата

а как узнать длину списка если он закольцован ?

не вижу проблем при простом однонаправленном проходе с головы в хвост с сохранением метки "я тут был". В чем проблема-то?

нечто вроде:

Код


//на входе алгоритма все вершины не крашенные
текущая вершина=голова;
while(не конец списка ИЛИ текущая вершина окрашена) {
 покрасить текущую вершщину;
 текущая вершина = следующий элемент;
}

если текущая верина окрашена, то есть кольцо.

Это сообщение отредактировал(а) jonie - 14.4.2009, 09:21

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

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

mes

Дата 14.4.2009, 11:38 (ссылка)

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

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

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

Цитата(jonie @ 14.4.2009, 08:20

)

ИЛИ текущая вершина окрашена) {

если Вы каждую элемент добавляете в карту, то

Цитата(mes @ 13.4.2009, 13:46

)

зачем параметр isColored ?

а без него решение превращается в :

Цитата(Anikmar @ 12.4.2009, 20:31

)

это создание массива указателей, в который помещать каждый узел и

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

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

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

http://opendots.net

jonie

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

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

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

аа , я думал вы нашли там баг фатальный)

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

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

Dov

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

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

andrew_121, ты покажи ф-цию вывода элементов списка, а потом можно будет говорить. Ты же выводишь элементы каким-то образом? Как ты это делаешь? По кругу или нет?

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

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

mes

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

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

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

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

Цитата(Dov @ 14.4.2009, 11:25

)

ты покажи ф-цию вывода элементов списка, а потом можно будет говорить.

Прежде чем выводить, тс. надо проверить не поврежден ли список, иначе прога войдет в бесконечный цикл smile

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

http://opendots.net

inside_pointer

Дата 14.4.2009, 23:38 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

Цитата(andrew_121)

Как(в теории) определить, закольцован он или нет?
Рекурсия не подходит. Сами понимаете почему.

можно сохранить prev и next в prevsave и nextsave и, продвигаясь по списку, проверять next на NULL и prevsave, а prev на NULL и nextsave

J0ker

Дата 15.4.2009, 00:28 (ссылка)

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

Загрузка ...

Опытный

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

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

о блин
толко щас заметил, что топик о двусвязном списке
так тут все просто

Код


if(head && head->prev)
    return сломано;
for(node *n = head; n != NULL; n = n->next)
    if(n->next && (n->next->prev != n || n->next == head))
        return сломано;
return Ok;

Добавлено @ 00:33
двусвязный список может быть корректно закольцован только если хвост указывает на голову и наоборот
все остальные случаи подпадают под термин "сломан"

Это сообщение отредактировал(а) J0ker - 15.4.2009, 00:43

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

andrew_121

Дата 15.4.2009, 10:38 (ссылка)

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

Загрузка ...

Кодофей

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

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

Цитата(J0ker @ 15.4.2009, 00:28

)

толко щас заметил, что топик о двусвязном списке

Цитата(J0ker @ 15.4.2009, 00:28

)

двусвязный список может быть корректно закольцован только если хвост указывает на голову и наоборот
все остальные случаи подпадают под термин "сломан"

Все остальные случаи должны корректно обрабатываться. Вот над этим и бьюсь сейчас. Нужно что-то вроди отчета, который потом(возможно однажды) придется использовать для "ремонта" списка.

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

Удалил аккаунт. Прощайте!

inside_pointer

Дата 15.4.2009, 11:44 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


    for (startsave = cur = head; cur && cur == cur->next->prev; ) {
         cur = cur->next;
         if (cur == startsave)
             break;
    }
    if (cur == startsave)
        printf("have a cycle\n");
    else if (cur == NULL)
        printf("have no cycle\n");
    else
        printf("list is broken\n");

Это сообщение отредактировал(а) inside_pointer - 15.4.2009, 11:58

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