C++ 프로그램: 연결 목록에서 두 번째로 작은 요소 찾기

순서가 지정된 데이터 요소 모음으로, 각 데이터 요소에는 다음 요소(때로는 이전 요소)에 대한 링크가 있으며, 연결된 목록이 있다고 가정하면 두 번째로 작은 요소를 찾아야 합니다. 아래는 다음 시나리오입니다.

몇 가지 간단한 입력 및 출력 시나리오를 가정해 보겠습니다

이 시나리오를 가정하면 연결 목록이 있고 그 안에 포함된 요소는 "8->4->6->2->9,"입니다. 그러면 연결된 목록 전체를 반복한 후 두 번째로 작은 요소는 8입니다.

으아악

링크드 리스트 프로그래밍 구현

으아악

연결된 목록의 모든 요소가 동일한 값을 갖는 또 다른 경우를 생각해 보세요. 모든 요소를 ​​반복한 후에는 두 번째로 작은 요소가 연결된 목록에서 발견되지 않습니다. 연결된 목록의 각 요소에는 동일한 값이 포함되어 있기 때문입니다.

으아악

알고리즘

작업을 수행하는 동안 따라야 할 단계는 다음과 같습니다

• 두 변수(S1, S2) 할당

• S1은 연결 리스트의 가장 작은 요소를 저장합니다

• S2는 연결 목록에서 두 번째로 작은 요소를 보유합니다.

• 반복할 때마다 가장 작은 요소가 S1으로 이동되고, 해당 요소가 발견되면 S2로 이동됩니다

• 최소값(S1)이 새로운 작은 값보다 작으면 새로운 작은 값이 최소값(S1)이 됩니다.

• 새 작은 것(S1)이 작아지고, 작은 것(S1)이 두 번째 작은 것(S2)으로 이동합니다.

• 각 가능한 순회 후에 최종 출력에서 ​​두 번째로 작은 요소가 출력이 됩니다.

예

C++ 구현에서는 2개의 변수를 유지할 수 있습니다. 1이 가장 작고, 다른 것이 두 번째로 작으며, 연결된 목록을 순회하면서 더 작은 요소를 만날 때마다 가장 작은 변수가 다음으로 작은 변수로 업데이트되고, 새로운 더 작은 변수가 가장 작은 변수가 됩니다. 따라서 요소가 가장 작은 요소보다 작을 때마다 두 번째로 작은 요소가 가장 작은 요소가 되고 가장 작은 요소가 새 요소가 됩니다. 그렇지 않은 경우 두 번째로 작은 요소를 비교하고 현재 요소가 두 번째로 작은 요소보다 작은지 확인한 후 그에 따라 업데이트합니다.

으아악

출력

으아악

결론

연결된 목록을 한 번 순회하면 시간 복잡도는 O(n)입니다. 위의 정보가 유용하다고 생각되면 공식 웹사이트를 방문하여 프로그래밍에 관한 더 많은 관련 주제를 알아보세요.

위 내용은 C++ 프로그램: 연결 목록에서 두 번째로 작은 요소 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!