Что должен найти эффективный алгоритм, является ли отдельно связанный список круговым/циклическим или нет? [дубликат]
Бизнес-причина расположения CSS: можно сдуть клиентов путем высказывания, что "наш портал полностью настраиваем/со сменными окнами, не пишущий код!"
С другой стороны, я не вижу зла в разработке элементов блока с таблицами. Элементами блока я имею в виду, где не имеет никакого смысла разбивать упомянутый элемент в различных проектах.
Так, табличным данным лучше всего подарили бы таблицы, конечно. Разрабатывание главных стандартных блоков (таких как строка меню, тикер новостей, и т.д.) в их собственных таблицах должно быть в порядке также. Просто не полагайтесь на таблицы для полного макета страницы, и Вы будете в порядке, мне кажется.
6 ответов
Стандартный ответ - взять два итератора в начале, увеличить первый один раз, а второй дважды. Проверьте, указывают ли они на один и тот же объект. Затем повторяйте, пока тот, который увеличивается дважды, либо не достигнет первого, либо не достигнет конца.
Этот алгоритм находит любую круговую ссылку в списке, а не только то, что это полный круг.
Псевдокод (не Java, непроверенный - с ума сойти)
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
}
}
@samoz, с моей точки зрения, имеет ответ! Псевдокод отсутствует. Было бы что-то вроде
yourlist - это ваш связанный список
allnodes = hashmap
while yourlist.hasNext()
node = yourlist.next()
if(allnodes.contains(node))
syso "loop found"
break;
hashmap.add(node)
извините, код очень псевдо (в последнее время выполняйте больше сценариев, чем java)
Нет конкретного пути для перехода на более раннюю версию, см. эту ссылку для официального MS
Если вы любите приключения (и вам повезет), вы можете попробовать преобразовать свой RDL 2008 года в соответствие с 2005 годом, но я предполагаю, что это будет серьезная задача. Файлы RDL - это просто файлы xml, соответствующие спецификации RDL, открытой и опубликованной Microsoft.
Спецификация RDL для служб отчетов 2008 доступна здесь:
http://download.microsoft.com/download/6/5/7/6575f1c8-4607-48d2-941d-c69622e11c32/RDL_spec_08.
Вот хороший сайт, на котором можно копировать различные решения.
цикл поиска односвязный список
Это победитель на этом сайте
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
Это решение "Флойда" Алгоритм поиска цикла ", как опубликовано в "Недетерминированных алгоритмах" автора Роберт У. Флойд в 1967 году. называется "Черепаха и Заяц" Алгоритм ».
Он никогда не выйдет из цикла, это также можно сделать в следующем решении:
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
if(i.next()==j)
break;
}
}