C에서 단일 링크 목록의 요소 정렬

단일 링크 된 목록에서 요소를 정렬하려면 어떻게해야합니까 (list-> id와 같은 값으로)? 생각 해낸 아이디어는 최대한의 가치를 찾고 색인을 저장하는 것입니다. 그런 다음 * 헤드 포인터가 해당 요소를 가리 키도록 목록을 반복합니다 ... 그리고이 요소를 첫 번째 요소로 바꿉니다. 마지막 문장은 ... 어떻게해야합니까?C에서 단일 링크 목록의 요소 정렬

출처

2013-01-22 khernik

목록이나 다른 데이터 구조와 똑같이 정렬 할 수 있습니다. 다양한 O (n) 복잡도에서 다양한 종류가 있습니다. 연결된 목록의 특정 구현에서 요소를 바꾸는 방법은 연결된 목록을 구현하는 방법에 따라 다릅니다. 필드가 정수이면 유명한 "스왑"함수를 사용할 수 있습니다. – PinkElephantsOnParade

실제 목록 노드의 순서가 변경되도록 목록을 "다시 연결"하는 것이 아니라 데이터를 바꾸는 것이 더 쉽습니다.

당신의 분야가 정수인 경우, 당신은 같은 것을 할 수있는 :

static void swap_ids(ListNode *a, ListNode *b) 
{ 
    const int a_id = a->id; 

    a->id = b->id; 
    b->id = a_id; 
}

출처

2013-01-22 14:34:49 unwind

감사, 좋은 지적! – khernik

좋은 생각 :) 목록에 더 복잡한 요소가 포함되어있는 경우에도 스와핑에 다시 링크하는 것보다 더 많은 작업이 필요할 수 있습니다. +1이 경우에도. –

가 나는 목록을 정렬하는 방법에 가장 좋은 방법은 merge sort을 구현하는 것입니다 말할 것입니다.

아직도하려고하는 것은 선택 정렬로 알려져 있으며 실행 가능합니다 (사실 매우 어렵지 않습니다). 포인터을 목록의 요소 인 요소로 유지 한 다음 링크를 이동시켜 헤드 요소 앞에 놓습니다 (헤드도 이동해야 함). 난 당신이 일반적으로 단 하나의 링크 된 목록에 머리를 유지하는 최소한의 요소를 선택해야한다는 말하고있다.

출처

2013-01-22 14:35:49

C에서 단일 링크 목록의 요소 정렬

답변

관련 문제