| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Восстановление двусвязного списка. |
| Автор: namelessTee 23.4.2012, 15:08 |
| Возможно есть какие нибудь алгоритмы, для восстановления двусвязного списка, в ситуации если у одно из не концевых элементов связь была установлена таким образом, что список стал замкнутым (проще говоря образовался деадлок, который превращает обход списка в бесконечный цикл). Задетектить проблему довольно легко - достаточно проверить, что один и тот же элемент появился в цепочке 2 раза, а вот есть ли алгоритм позволяющий восстановить последовательность исходя например из того, что все остальные элементы корректно изменили все свои связи? Под корректностью изменения связей понимается, что элемент который должен был идти после элемента вызывающего деадлок, считает элемент вызвавший деадлок предыдущим, и содержит корректную ссылку на следующий элемент. И это все при условии: элементы хранятся в одном месте и могут принадлежать разным спискам(идентификатора родительского списка они не содержат); один и тот же элемент может принадлежать только одному списку; первый элемент списка корректен и не вызывает деадлок; Интересует не обязательно алгоритм гарантирующий 100% восстановление цепочки, главное что бы было гарантированно - что не будут повреждены остальные списки. |
| Автор: ksnk 23.4.2012, 16:52 |
| Нужно у списка хранить кроме головы еще и хвост. Если пробегаясь с головы в хвост получаем deadlock, то нужно пробежаться с хвоста в голову и перерисовать ссылки. |
| Автор: namelessTee 23.4.2012, 17:21 |
| Ага, спасибо, почти к тому же и пришли уже, с той лишь только разницей, что приходится не хранить хвост, а пробегаться по всем элементам и искать путь обратно в список(точнее к деадлоку) . Хвост нельзя хранить по техническим причинам :( . |
| Автор: ksnk 28.4.2012, 21:54 | ||
Мнээ.... А ломается именно это список? По которому нужно добежать до дидлока? Как можно по кривому списку восстановить всю цепочку? Можно только выкинуть элементы за циклической ссылкой и сказать, что так и былО. |
