обход односвязного списка в C ++

Question

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

Answer 5

Код выглядит нормально, но я бы предложил внести незначительные изменения в ваш 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 6

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

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

Но то, что у вас есть, выглядит прекрасно.

Answer 7

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