прохождение односвязного списка в C ++

Question

Мне было интересно, можно ли просмотреть связанный список следующим образом:

currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

Возможно ли это сделать в C ++, когда я пытаюсь найти узел перед currentNode в односвязном списке?

Я пытаюсь реализовать что-то подобное в консольном приложении для школьного задания, поэтому предположим, что я не могу использовать что-то необычное, например, библиотеки повышения / список / что-нибудь, что облегчает жизнь и т. Д. Итак, в принципе, у меня есть только довольно примитивные типы данных и библиотеки в моем распоряжении.

Answer 1

Возможно, вы захотите убедиться, что ссылка prevNode-> также не является пустой ссылкой, если currentNode фактически не связан.

Answer 2

Убедитесь, что вы учитываете все возможные крайние случаи:

• Что происходит randomNode равно firstNode? Что вы возвращаете? Что вы должны вернуть?
• Что происходит, когда randomNode является последним узлом в списке?
• Что происходит, когда randomNode равен NULL?
• Что происходит, когда randomNode нет в списке?

Теперь, не все эти случаи могут быть применимы, в зависимости от того, знаете ли вы что-нибудь о randomNode, и некоторые из них могут быть тривиальными. Но о них стоит задуматься.

Если вы рассмотрите все это очень тщательно, есть простое и элегантное решение, которое справится со всеми из них.

Answer 3

Этот код пересекает некоторую часть вашего списка, но какая часть зависит от того, каким образом ваш список связан. Если он идет от head-> tail (читай: head-узел ссылается на узел, который ссылается на tail), то вы должны пройти по списку, начиная со случайного местоположения до tail. Если ссылки - head <-tail, то вы переходите от случайного местоположения к голове. В любом случае вы бы не трогали все узлы в списке. </p>

Все вышеперечисленное предполагает наличие некоторого списка ссылок как такового:

[head]<->[0...N Nodes]<->[Tail]

Ссылки могут быть в любом случае.

Кроме того, вы можете связать головной и хвостовой узлы и создать круговой связанный список. В этом сценарии можно посетить все узлы, просто пройдя до тех пор, пока вы не вернетесь к исходному узлу.

Answer 4

Код выглядит нормально, но я бы посоветовал внести небольшие изменения в ваше while состояние

while(prevNode != currentNode && prevNode != NULL)

По двум причинам

• Ваш код, как указано в настоящий момент, может остановиться, если на искомый узел указывает либо prevNode, либо prevNode->link (и, следовательно, мы не будем знать, какой именно из двух пунктов указывает на currentNode - если бы мы хотели знать, мы должны были бы проверить с условием if). С изменением выше, целевой узел гарантированно будет сохранен в prevNode (если вообще - см. Следующий пункт).
• В целях безопасности было бы хорошо проверить, что prevNode не является NULL. Однако, как упоминает Павел, этот тест не нужен, если currentNode гарантированно присутствует в списке.

---

Редактировать в ответ на комментарий

Учитывая, что вам не нужно знать, находится ли currentNode в prevNode или prevNode->link, и, поскольку вы хотите остановиться (если возможно) на currentNode == prevNode->link, тогда ваш исходный while в порядке. Однако ...

есть оператор if выше код, который предотвращает prevNode от нуля уже

Похоже, вам не хватает смысла проверять NULL. Да, хорошо, что вы проверяли это раньше, но причина, по которой у нас есть проверка NULL в цикле, заключается в том случае, когда currentNode означает , а не в списке, поэтому вы в конечном итоге достигаете последнего узла , Предположительно (если вы делаете это, как и большинство других связанных списков), значение link для вашего последнего узла равно NULL. Если это так, ваш текущий код в конечном итоге вызовет NULL->link, что, конечно, приведет к сбою вашей программы. Вот почему вы все равно должны проверить на NULL

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

Если вы абсолютно уверены , что currentNode будет в списке, тогда я думаю , что проверка также не нужна, но это действительно хорошая привычка, чтобы попасть в .

Answer 5

Это должно работать просто отлично. Вы уже пробовали это?

Answer 6

Небольшая вещь, которую я бы изменил с помощью кода, который был опубликован (помимо возможности, обсуждаемой в других ответах на запуск за пределы списка, если currentNode нет в списке, или другая обработка ошибок) - это когда цикл завершен, вы не знаете, указывает ли prevNode или prevNode->link на currentNode. Это не большая проблема (так как вы можете легко проверить это), но мне кажется, что лучше всего проверить эту особую ситуацию перед поиском, поэтому ясно, что это особый случай.

Answer 7

Вы можете даже иметь:

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

Но то, что у тебя есть, выглядит хорошо.