atravessando uma lista vinculada isoladamente em C ++

StackOverflow https://stackoverflow.com/questions/1522828

Pergunta

Eu queria saber se é possível percorrer uma lista ligada assim: 


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

É possível fazer isso em C ++ quando eu estou tentando encontrar o nó antes currentNode em uma lista vinculada isoladamente?

I tentar implementar algo parecido com isso em um aplicativo de console para um trabalho escolar de modo supor que eu não posso usar nada extravagante como a bibliotecas de impulso / list / qualquer coisa que torna a vida mais fácil, etc. Então, basicamente, eu só tenho bastante tipos de dados e bibliotecas primitivos à minha disposição.

Foi útil?

Solução

Você pode querer se certificar de que prevNode-> link não é uma referência nula, quer, no caso currentNode não está realmente ligada.

Outras dicas

Isso deve funcionar muito bem. Você já tentou isso ainda?

Esse código irá percorrer alguma parte de sua lista, mas que parte depende de que maneira sua lista está vinculado. Se ele vai de cabeça-> cauda (leia-se: ligações nó principal para um nó que links para a cauda), então você iria atravessar sua lista a partir da localização aleatória para a cauda. Se os links são cabeça <-tail então você percorrer a partir da localização aleatória na cabeça. Em ambos os casos, você não iria tocar todos os nós na lista.

Todos os acima assume alguma lista de links como tal: 

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

Os links podem ser de qualquer maneira.

Além disso, você pode ligar os nós de cabeça e cauda e criar uma lista circular ligada. Nesse cenário, é possível visitar todos os nós simplesmente atravessando até que você esteja de volta ao seu nó original.

Certifique-se de considerar todos os casos possíveis de ponta:

  • O que acontece randomNode igual firstNode? O que você voltar? O deve você retornar?
  • O que acontece quando randomNode é o último nó na lista?
  • O que acontece quando randomNode é NULL?
  • O que acontece quando randomNode não está na lista?

Agora, nem todos estes casos podem ser aplicáveis, dependendo se você sabe alguma coisa sobre randomNode, e alguns destes podem ser trivial. Mas todos eles são vale a pena pensar.

Se você considerar tudo isso com muito cuidado, há uma solução simples e elegante que alças todos eles.

O código parece bem, mas gostaria de sugerir uma pequena alteração em sua condição while 

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

Por duas razões

  • O seu código, como atualmente declarou, poderia parar se o nó que estamos procurando é apontado por qualquer prevNode ou prevNode->link (e, portanto, não terá idéia de que determinado um dos dois pontos para currentNode - se quiséssemos sabe, nós teríamos que verificar com uma condição if). Com a mudança acima, o nó de destino é garantido para ser armazenado em prevNode (se em tudo - ver ponto seguinte).
  • Por razões de segurança, seria bom verificar que prevNode não é NULL. No entanto, como Pavel menciona, este teste é desnecessário se currentNode é garantido para estar na lista.

Editar em resposta ao comentário

Uma vez que você não precisa saber se currentNode está em prevNode ou prevNode->link, e desde que você quer parar (se possível) na currentNode == prevNode->link, então o seu while original está bem. No entanto ...

existe uma instrução if mais acima na o código que impede prevNode de ser nula já

Parece que você está perdendo o ponto de por que você deve verificar se há NULL. Sim, isso é bom você verificar isso antes, mas a razão pela qual temos a verificação NULL no circuito é no caso em que currentNode é não na lista, para que, eventualmente, atingir o último nó. Presumivelmente (se você fizer isso como a maioria das outras listas ligadas) o valor de link para o seu último nó é NULL. Se assim for, o seu código atual acabará chamando NULL->link que, naturalmente, irá travar o seu programa. É por isso que você ainda deve verificar se há NULL 

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

Se você é absolutamente certo que currentNode vai estar na lista, então eu acho que o check também é desnecessário, mas é realmente um bom hábito de entrar .

Você pode até ter: 

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

Mas o que você tem aparência bem.

Uma pequena coisa que eu mudaria com o código conforme publicado (além da possibilidade discutida em outras respostas de correr no final da lista se currentNode não está na lista ou outro tratamento de erros) é que quando o tempo loop é feito você não sabe se prevNode ou prevNode->link pontos para currentNode. Este não é um grande problema (desde que você pode facilmente teste para ele), mas parece-me que é melhor para testar esta situação caso especial antes da pesquisa, por isso é claro que é um caso especial.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top