목록의 요소는 어떻게 바꿀 수 있습니까?

Question

저는 데이터 구조와 알고리즘에 대해 독자적으로 배우려고합니다. C로 double-linked리스트를 썼는데 이제리스트에서 수행 할 알고리즘을 쓰고 싶습니다. 목록 항목을 교환하는 기본 방법은 무엇입니까? 내용을 바꾸거나 다음 및 이전 목록 항목을 가리키는 포인터를 다시 정렬하는 것이 더 좋습니까?

Answer 1

포인터를 재정렬하십시오. 데이터 항목을 교환하면 부작용이 발생할 수 있습니다. 특히 함수 바깥의 노드에 대한 참조를 저장했을 수도 있고 보통 일 때 노드의 순서를 재 배열하면 노드에 대한 참조를 보유한 사람들이 갑자기 그 노드를 찾지 못하게 할 수 있습니다. 노드가 새 데이터를 가리 킵니다. 이는 일반적으로 노드의 중요한 특성을 식별하는 데이터가 이 아니고의 목록에있는 데이터이기 때문입니다. 실제 콘텐츠를 교환 링크 된리스트의 엘리먼트에 저장되는 콘텐츠의 종류에 따라

void swap (node *a, node *b) { 
    node *tmp; 

    tmp = a; 
    a = b; 
    b = tmp; 
} 

Answer 2

정규 스왑은 포인터의 재배치를 통해 수행 부작용이 없으며, 빠른 물론이다 요소의 (예를 들어 다른 길이 문자열의 링크 된 목록에 대해 생각) 까다로울 수 있으므로 다음 및 이전 목록 항목을 가리키는 포인터를 쉽게 바꿀 수 있습니다.

Answer 3

:

Answer 4

콘텐츠를 어떻게 할당했는지에 따라 다릅니다.

콘텐츠에 포인터를 저장하는 경우 콘텐츠를 전환하는 것이 중요하지 않습니다. 노드의 일부인 큰 구조를 가지고 있다면 포인터를 전환하는 것이 전체 내용을 복사하는 것보다 효율적일 수 있습니다.

Answer 5

나는 대부분의 사람들이 이미 말한 것과 관련이있다. 약간의 배경이 도움이 될 것입니다. 즉, 포인터 교환은 작동하는 것이 보장되는 반면, 오브젝트 교환은 항상 보이는 것만 큼 단순하지는 않습니다. 생성 될 수 있고 생성 될 임시 객체를 생각하면 예외 (일반적으로 C++ 언어 기능이 아니라)가 발생하여 실제로 컨테이너 (목록)를 바람직하지 않은 상태로 남겨 둘 수 있습니다. 컨테이너에있는 불변량을 찾으십시오. 스왑은 요소를 그대로 유지하고 목록 크기를 그대로 유지해야합니다.