Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Двусвязный список.

Автор: andrew_121 12.4.2009, 18:28

Всем доброго времени сУток! Вопрос в следующем. Есть двусвязный список: Код struct Node { ...    Node* prev;    Node* next; }; Как(в теории) определить, закольцован он или нет? Рекурсия не подходит. Сами понимаете почему. В общем...любопытно Ваше мнение. Спасибо за внимание.

Автор: zim22 12.4.2009, 18:45

Код struct List {   Node* first;   Node *last; }; if (first == last) закольцован

Автор: mes 12.4.2009, 21:30

Цитата(andrew_121 @  12.4.2009,  17:28 ) Как(в теории) определить, закольцован он или нет? берешь два итератора("быстрый" и "медленный" ), пускаешь их по кругу, где на два шага "быстрого" приходится один шаг "медленного".. проверяешь оба итератора на равенство после каждого шага "быстрого", и если встретились раньше, чем "быстрый" дошел до конца, значит список закольцован.

Автор: Anikmar 12.4.2009, 21:31

100% результат - это создание массива указателей, в который помещать каждый узел и пробежаться по списку. Если такой адрес в массиве есть - значит закольцованность. Менее надежно - ввести в узлы служебное поле, которому присваивать определенное значение. Дошли до узла с таким значением - закольцован. Менее надежен потому, что случайно такое значение может быть. Для чистоты эксперимента прогнать второй раз с другим значением.

Автор: J0ker 13.4.2009, 00:17

Цитата(Anikmar @  12.4.2009,  21:31 ) Для чистоты эксперимента прогнать второй раз с другим значением.  для еще большей чистоты - прогнать третий раз потом четвертый потом пятый а потом доказывать начальству, что такого не может быть, что после пятого раза такой обломище ЗЫЖ к стенке надо таких прграммистов Добавлено через 2 минуты и 9 секунд 2mes,  а я там давал вторую часть задачи? починить список?

Автор: Anikmar 13.4.2009, 07:30

Цитата(J0ker @  13.4.2009,  00:17 ) для еще большей чистоты - прогнать третий раз Третий не нужно - для проверки 2-х раз достаточно    Цитата(J0ker @  13.4.2009,  00:17 ) ЗЫЖ к стенке надо таких прграммистов За что меня к стенке?    Я всего-лишь предложил 2 варианта - первый мне больше нравится.    Вашего варианта я же не видел - может он лучше, я бы свои не предлагал. Злые вы.

Автор: J0ker 13.4.2009, 09:11

Цитата(Anikmar @  13.4.2009,  07:30 ) Третий не нужно - для проверки 2-х раз достаточно т.е. второй раз "случайно такое значение"(С)Anikmar быть не может? это закон природы такой, да?    Цитата(Anikmar @  13.4.2009,  07:30 ) Вашего варианта я же не видел - может он лучше, я бы свои не предлагал. вы видели вариант mes'а, но видимо не прониклись Добавлено через 47 секунд Цитата(Anikmar @  13.4.2009,  07:30 ) Злые вы мы не злые, мы мудрые

Автор: Anikmar 13.4.2009, 09:44

Цитата(J0ker @  13.4.2009,  09:11 ) вы видели вариант mes'а, но видимо не прониклись А если конец списка ссылается на начало? Быстрый итератор будет равен первому элементу, а медленный в середине где-то? Разве равенство сработает? Цитата(J0ker @  13.4.2009,  09:11 ) т.е. второй раз "случайно такое значение"(С)Anikmar быть не может? это закон природы такой, да?    Второй раз случайно может быть, но это обнаружимо. В любом случае, я вижу только мой первый вариант как 100%  Все проникся - все равно догонит. Цитата(J0ker @  13.4.2009,  09:11 ) мы не злые, мы мудрые  Мудрые к стенке не ставят. Мудрые доводят до самоубийства.

Автор: mes 13.4.2009, 10:26

Цитата(Anikmar @  13.4.2009,  06:30 ) Вашего варианта я же не видел - может он лучше, я бы свои не предлагал. Предложенный мной вариант, был услышан некоторое время назад от Joker.    Цитата(J0ker @  12.4.2009,  23:17 ) а я там давал вторую часть задачи? починить список?  припоминаю.. для односвязанного списка.  Видится примерно такая картина: от места встречи проходим по круг у и узнаем длину петли.  и на основании длины петли, кол-во шагов быстрого итератора, и шагов медленного можно посчитать место пересечения. Так для случая отн. большой петли (если быстрый до места встречи успел пройти по петле только раз)  L=2*O-S ,  где L - длина от начала , до конца (до стыка который надо востанавливать)       О-длина петли       S-кол-во шагов медленного. Для остальной части задачи надо мозги напрячь.. попозже попробую..

Автор: jonie 13.4.2009, 11:40

имхо покрасить каждый элемент при простом проходе, если попали на покрашенное - значит кольцо есть.

Автор: mes 13.4.2009, 11:56

Цитата(jonie @  13.4.2009,  10:40 ) имхо покрасить каждый элемент при простом проходе, если попали на покрашенное - значит кольцо есть.   если только список предполагал возможность окрашивания +  надо как то убедиться что список нигде не подкрашен.

Автор: andrew_121 13.4.2009, 12:58

Цитата(jonie @  13.4.2009,  11:40 ) имхо покрасить каждый элемент при простом проходе, если попали на покрашенное - значит кольцо есть. Да. Этот вариант мне больше нравится. Цитата(mes @  13.4.2009,  11:56 ) надо как то убедиться что список нигде не подкрашен.  smile  И вернулись к изначальному вопросу

Автор: jonie 13.4.2009, 13:17

и в чем проблема создать map<void*, isColored> подобную структуру при обходе? не вижу никаких проблем.

Автор: andrew_121 13.4.2009, 13:21

jonie, Да. Спасибо. Вопрос решен.

Автор: mes 13.4.2009, 14:46

Цитата(jonie @  13.4.2009,  12:17 ) и в чем проблема создать map<void*, isColored> подобную структуру при обходе? не вижу никаких проблем.  а как узнать длину списка если он закольцован ? a если проверять есть ли в списке уже указатель, то зачем параметр isColored ?

Автор: andrew_121 13.4.2009, 15:20

mes, Вы правы! Начал реализовывать, и уперся     И так. Дисскусия продолжаеться.

Автор: mes 13.4.2009, 15:22

Цитата(andrew_121 @  13.4.2009,  14:20 ) Начал реализовывать, и уперся smile  smile  а чем не устраивает способ, где   Цитата два итератора("быстрый" и "медленный" ), ?

Автор: andrew_121 13.4.2009, 15:27

mes, Туплю по ходу   Не могу понять что и как...

Автор: mes 13.4.2009, 16:35

Цитата(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; // найден конец }

Автор: J0ker 13.4.2009, 16:35

Цитата(mes @  13.4.2009,  10:26 ) Для остальной части задачи надо мозги напрячь.. попозже попробую..  расстояние от точки встречи итераторов до точки пересечения всегда равно остатку от деления куска до пересечения на длину кольца т.е. простейший вариант пустить два "медленных" итератора - один из точки встречи, другой с начала списка - они встретятся в точке пересечения

Автор: mes 13.4.2009, 16:40

Цитата(J0ker @  13.4.2009,  15:35 ) т.е. простейший вариант пустить два "медленных" итератора -  нда..самое эффективное решение как всегда лежит на поверхности  J0ker,

Автор: jonie 14.4.2009, 09:20

Цитата а как узнать длину списка если он закольцован ? не вижу проблем при простом однонаправленном проходе с головы в хвост с сохранением метки "я тут был". В чем проблема-то? нечто вроде: Код //на входе алгоритма все вершины не крашенные текущая вершина=голова; while(не конец списка ИЛИ текущая вершина окрашена) {  покрасить текущую вершщину;  текущая вершина = следующий элемент; } если текущая верина окрашена, то есть кольцо.

Автор: mes 14.4.2009, 11:38

Цитата(jonie @  14.4.2009,  08:20 ) ИЛИ текущая вершина окрашена) { если Вы каждую элемент добавляете в карту, то  Цитата(mes @  13.4.2009,  13:46 ) зачем параметр isColored ?  а без него решение превращается в : Цитата(Anikmar @  12.4.2009,  20:31 ) это создание массива указателей, в который помещать каждый узел и  и требует наличие некого дополнительного объема памяти и также кол-во операций сравнения получается выше, чем у способа с двумя итераторами. ну вот и вопрос, зачем использовать заведомо медленный и не эффективный способ,  строить дополнительные механизмы,   когда все решается простым (двух-итераторным) обходом списка ?

Автор: jonie 14.4.2009, 12:16

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

Автор: Dov 14.4.2009, 12:25

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

Автор: mes 14.4.2009, 12:53

Цитата(Dov @  14.4.2009,  11:25 ) ты покажи ф-цию вывода элементов списка, а потом можно будет говорить.  Прежде чем выводить, тс. надо проверить не поврежден ли список, иначе прога войдет в бесконечный цикл

Автор: inside_pointer 14.4.2009, 23:38

Цитата(andrew_121) Как(в теории) определить, закольцован он или нет? Рекурсия не подходит. Сами понимаете почему. можно сохранить prev и next в prevsave и nextsave и, продвигаясь по списку, проверять next на NULL и prevsave, а prev на NULL и nextsave

Автор: J0ker 15.4.2009, 00:28

о блин толко щас заметил, что топик о двусвязном списке так тут все просто Код 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 двусвязный список может быть корректно закольцован только если хвост указывает на голову и наоборот все остальные случаи подпадают под термин "сломан"

Автор: andrew_121 15.4.2009, 10:38

Цитата(J0ker @  15.4.2009,  00:28 ) толко щас заметил, что топик о двусвязном списке    Цитата(J0ker @  15.4.2009,  00:28 ) двусвязный список может быть корректно закольцован только если хвост указывает на голову и наоборот все остальные случаи подпадают под термин "сломан" Все остальные случаи должны корректно обрабатываться. Вот над этим и бьюсь сейчас. Нужно что-то вроди отчета, который потом(возможно однажды) придется использовать для "ремонта" списка.

Автор: inside_pointer 15.4.2009, 11:44

Код     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");

Автор: mes 15.4.2009, 11:50

Цитата(inside_pointer @  15.4.2009,  10:44 )     for (startsave = cur = head;          cur == cur->next->prev              && cur != startsave;          cur = cur->next) а где проверка, что cur->next не ноль ?!

Автор: inside_pointer 15.4.2009, 11:51

я в процессе ещё

Автор: Dov 15.4.2009, 13:05

Код struct node {     int        data;     node   *next;     node   *prev; }; struct List {     node   *head;     List()     {         head = NULL;     }     void    inputList();     void    printList(); }; int main() {      setlocale(LC_ALL, ".1251");     List    list;     list.inputList();     list.printList();     return 0; } void List::inputList() {     node   *cur;     int        data;     head       = new( node );          cur        = head;     head->prev = NULL;      head->next = NULL;     cout << "введите элементы списка(0 - завершение ввода): \n";     cin  >> data;     while( data != 0 )     {         cur->next       = new ( node );         cur->next->prev = cur;         cur             = cur->next;         cur->next       = NULL;         cur->data       = data;         cin >> data;     }     if( head->next != NULL )     {         head->next->prev = cur;         // закомментируйте одну из следующих строчек:                 cur->next        = head->next;           // закольцуем список         //        cur->next        = NULL;                 // не будем закольцовывать            } } void List::printList() {     node  * cur;     cout << "список: ";     if( head->next != NULL )     {         cout << head->next->data << " ";         cur = head->next->next;         while( cur != head->next )         {             cout << cur->data << " ";             cur = cur->next;             // проверяем: NULL - не закольцован             if( cur == NULL )             {                 cout << " не";                 break;             }         }         cout << " закольцован " << endl;     }     else         cout << "пуст... \n"; }

Автор: mes 15.4.2009, 13:13

Цитата(Dov @  15.4.2009,  12:05 )     void    inputList();     void    printList(); а зачем их делать членами класса ?

Автор: Dov 15.4.2009, 13:29

Цитата(mes @  15.4.2009,  13:13 ) а зачем их делать членами класса ? mes, вопрос, ведь, не в этом. Не хочешь - не делай. Это просто иллюстрация, примерчик, так сказать. Показано, как проверить и всё. Дальше, пусть человек сам думает. Добавлено через 3 минуты и 19 секунд там нужна ещё проверка "в обратную сторону", аналогичная этой..

Автор: zim22 15.4.2009, 13:46

Цитата(Dov @  15.4.2009,  13:05 ) setlocale(LC_ALL, ".1251"); Я так понимаю, это чтобы в консоли русский текст корректно отображался. Однако я встречал ещё два аналогичных варианта: 1) setlocale(LC_ALL, ""); 2) setlocale(LC_ALL, "Russian"); Интересно, сколько их всего...

Автор: mes 15.4.2009, 14:02

Цитата(Dov @  15.4.2009,  12:29 ) Не хочешь - не делай. Это просто иллюстрация, примерчик, так сказать. Показано, как проверить и всё. Дальше, пусть человек сам думает. не хочу.. просто испугало.. представил, что эти строчки воспримут как руководство к действию.

Автор: Dov 15.4.2009, 14:08

Цитата(mes @  15.4.2009,  14:02 ) не хочу.. просто испугало.. представил, что эти строчки воспримут как руководство к действию.  гы-гы.... mes, зачем же о людях так думать?    Цитата(zim22 @  15.4.2009,  13:46 ) Интересно, сколько их всего... zim22, не знаю.  На моём компе если так не сделать, то будет на иврите выводить...

Автор: mes 15.4.2009, 14:17

Цитата(Dov @  15.4.2009,  13:08 ) mes, зачем же о людях так думать?  smile  да после соседней темы с  **(char *)&string еще и не такие ужасы привидятся..

Автор: andrew_121 15.4.2009, 14:58

Цитата(mes @  15.4.2009,  14:02 ) представил, что эти строчки воспримут как руководство к действию.  smile     Цитата(mes @  15.4.2009,  14:17 ) **(char *)&string Это что?

Автор: zim22 15.4.2009, 15:14

Цитата(andrew_121 @  15.4.2009,  14:58 ) Это что?  извращение в чистом виде

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)