C++에서 단일 연결리스트를 순회

가이 같은 연결리스트 통과 할 수있는 경우에 궁금 :C++에서 단일 연결리스트를 순회


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

내가 노드를 찾기 위해 노력하고 때 C++에서이 작업을 수행하는 것이 가능을 단일 링크 된 목록에서 currentNode보다 먼저?

나는 콘솔 앱에서 학교 과제를 위해 이것을 구현하려고하는데, 내가 부스트 라이브러리 /리스트/인생 등을 더 쉽게 만드는 어떤 것도 쓸 수 없다고 가정한다. 그래서 기본적으로, 나는 단지 상당히 원시적 인 데이터 유형과 라이브러리를 사용할 수 있습니다.

출처

2009-10-05 cskwrd

"궁금한 점"을 시도해보고 작동 방식을 확인하는 이유는 무엇입니까? 난 당신이 항상 적어도 하나의 노드를 가지고 있으며,'randomNode'가리스트에서 유효한 노드라는 것을 보장한다고 가정 할 때 (여기서 "off"를 결코 실행하지 않을 것입니다) 여기에는 아무런 문제가 없습니다. –

정확히하고 싶습니까? 연결된 목록에서 노드를 검색 하시겠습니까? – Ashwin

while 조건이 조금 이상해 보입니다 ... 왜 prevNode! = currentNode?또한 목록이 비어있을 수 있습니까? currentNode가리스트에 존재하지 않을 수 있습니까? –

currentNode가 실제로 연결되어 있지 않은 경우 prevNode-> link도 null 참조가 아닌지 확인하고 싶을 수 있습니다.

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

을하지만 당신이 가진 것은 잘 보이는 :

출처

2009-10-05 22:58:08

currentNode가 목록에 있다고 보장되면), 루프는 항상 목록의 끝에서 종료됩니다. – sepp2k

잘 작동합니다. 아직 해 보셨습니까?

출처

2009-10-05 22:57:12

예 아니요. 그것은 내 코드에 있지만 다른 부분이 없어서 며칠 동안 작업하지 않았으므로 모든 것이 "엮여 진"것은 아닙니다. – cskwrd

당신은 할 수 있습니다. 노드 우리가있는 경우

출처

2009-10-05 23:06:16 Ashwin

이 코드는 잘 보이지만, 나는 두 가지 이유

현재 언급 한 바와 같이

귀하의 코드에 대한 while 조건
```
while(prevNode != currentNode && prevNode != NULL) 
```
에 작은 변화를 제안, 막을 수 찾는 것은 prevNode 또는 prevNode->link입니다 (그러므로 우리는 두 점 중 어느 특정 점이 currentNode인지 전혀 알 수 없습니다 - 알고 싶으면 if c로 확인해야합니다) ondition). 위의 변경 사항을 적용하면 대상 노드는 prevNode에 저장됩니다 (해당되는 경우 다음 지점 참조).
안전을 위해 prevNode이 NULL이 아닌지 확인하는 것이 좋습니다. 그러나 Pavel이 언급 한 것처럼 currentNode이 목록에있을 것이라면이 테스트는 불필요합니다. 응답

편집하면 currentNode이 prevNode 또는 prevNode->link에 있는지 여부를 알 필요가 없습니다 감안할 때

을 언급하고, 귀하는 currentNode == prevNode->link에 (가능한 경우)를 중지하기 원하기 때문에, 원본 while은 문제가 없습니다. 그러나 ...

가있는 경우 널되는 것을 prevNode을 방지 코드의 최대 높은 문 이미 당신이 체크해야하는 이유의 요점을 놓치고있는 것 같다

NULL입니다. 네, 이전에 확인해 주셔서 좋습니다. 그러나 루프에 체크가있는 이유는 목록에 currentNode이 이 아니고이 아니므로 결국 마지막 노드에 도달하게됩니다.아마도 (다른 링크 된 목록과 마찬가지로 이렇게하면) 마지막 노드의 link 값은 NULL입니다. 그렇다면 현재 코드가 결국 NULL->link으로 끝나고 결국 프로그램이 중단됩니다. 당신이 확신currentNode 그 목록에있을 것입니다 경우 당신은 여전히 나는 또한 불필요 확인를 추측 , NULL

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

를 확인해야하지만, 정말에 좋은 습관 이유입니다 가입하다.

출처

2009-10-05 23:07:40 GRB

그 이유는 내가 그 조건을 가지고있는 이유는 if 문이 더 높은 코드에서 prevNode이 이미 널이되는 것을 막기 위해서이다. 따라서 기본적으로 prevNode이 현재 노드 또는 노드와 동일하다는 것을 확인하고 싶다. currentNode은 처음이다. . – cskwrd

해당 코드는 목록의 일부를 트래버스하지만 목록이 연결되는 방식에 따라 다릅니다. 그것이 head-> tail (읽기 : 헤드 노드 링크가 꼬리쪽으로 연결되는 노드로 연결되는 경우)에서라면 임의의 위치에서 꼬리까지 목록을 가로 지르게됩니다. 링크가 머리 < -tail 인 경우 임의의 위치에서 머리까지 트래버스합니다. 두 경우 모두 목록의 모든 노드를 건드리지 않을 것입니다.

위의 모든

는 다음과 같은 몇 가지 링크 목록을 가정

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

링크 중 하나의 방법이 될 수 있습니다.

또한 머리 및 꼬리 노드를 연결하고 순환 링크 된 목록을 만들 수 있습니다. 이 시나리오에서는 원래 노드로 돌아갈 때까지 단순히 탐색하여 모든 노드를 방문 할 수 있습니다.

출처

2009-10-05 23:16:19 RyanY

내가 게시 한 코드로 변경하려는 작은 것 (currentNode가 목록이나 다른 오류 처리에없는 경우 목록의 끝에서 실행되는 다른 답변에서 논의 된 가능성을 제외하고)은 루프가 완료되면 prevNode 또는 prevNode->link이 currentNode을 가리키는 지 알 수 없습니다. 이것은 큰 문제는 아니지만 (쉽게 테스트 할 수 있기 때문에), 검색하기 전에이 특별한 경우 상황을 테스트하는 것이 가장 좋습니다. 따라서 특별한 경우라는 것이 확실합니다.

출처

2009-10-05 23:28:35

이 가능한 에지 모든 경우에 고려하십시오 :

이 randomNode를 어떻게됩니까

이 firstNode 동일을? 너는 무엇을 돌려 주느냐? 무엇 반환해야합니까?
randomNode이 목록의 마지막 노드 일 때 어떻게됩니까?
randomNode이 NULL 일 때 어떻게됩니까?
randomNode이 목록에 없으면 어떻게됩니까?

이제는 randomNode에 대해 알고있는 경우에 따라 이러한 모든 사례가 적용될 수있는 것은 아니며 그 중 일부는 사소한 문제 일 수 있습니다. 그러나 그들은 모두 생각할 가치가 있습니다.

이 모든 것을 매우 신중하게 고려하면 간단하고 세련된 솔루션으로 모든 것을 처리 할 수 있습니다.

출처

2009-10-05 23:44:51

C++에서 단일 연결리스트를 순회

답변

관련 문제