링크 목록을 사용한 삽입 정렬

-1

(1) 삽입 정렬 만 구현하며 (2) 저장 용 배열 대신 긴 정수를 저장하기 위해 연결된 목록을 사용합니다. 따라서 정렬은 연결된 목록에서 수행해야합니다.링크 목록을 사용한 삽입 정렬

내 코드는 다음과 같습니다.

Node *Insertion_Sort(Node *sublist) { 
//Initialize`enter code here` 
Node *dummy_node = malloc(sizeof(Node)); 
dummy_node->next = NULL; 

Node *prev_node = sublist; 
Node *curr_node = sublist->next; 

Node *head = prev_node; 

Node *temp_node = malloc(sizeof(Node)); 
while(curr_node->next != NULL){ 
    if (prev_node->value < curr_node->value) { 
     //advance the pointers 
     prev_node = curr_node; 
     if (curr_node != NULL) { 
      curr_node = curr_node->next; 
      printf("Advancing prev=%ld curr=%ld\n", prev_node->value, curr_node->value); 
     } 
     else 
     { 
      break; 
     } 
    } 
    else 
    { 
     //swap 
     temp_node = curr_node; 
     prev_node->next = curr_node->next; 
     curr_node->next = prev_node; 
     // Advance 
     prev_node = curr_node; 
     curr_node = curr_node->next; 
     head = prev_node; 
    } 
} 
//curr_node->next = NULL; 

return head; 
}

그러나 부분적으로 만 작동합니다. 아무도 나를 도울 수 있습니까?

출처

2014-02-28 user3295123

"부분적으로 만 작동합니다"라고 정의하십시오. – dornhege

@dornhege와 마찬가지로 현재 출력은 얼마입니까? 문제 영역은 무엇이라고 생각하십니까? 추가 정보를 통해 질문에 쉽게 답할 수 있습니다. –

이 정렬 루틴에서 * anything *을 할당한다는 것은 의문의 여지가 있습니다. C++ 프로그램에서 그것을하기 위해'malloc()'을 사용하고 있다는 것은 매우 의심 스럽습니다. 스왑을 제외하고는 임시 저장을 위임 한 삽입 정렬에서 아무것도 기억하지 못합니다. 링크 된 목록을 사용하고 있기 때문에 교환해야하는 유일한 것은 포인터가 아닌 노드입니다. – WhozCraig

노드에 공간을 할당 할 필요는 없습니다. Insertion sort에 대한 위키 링크. 당신은 아마 두 번째 의사 코드 예제를 사용하기로하고 (일부는 내가 정렬하기 전에, 당신은 노드 제거하고 삽입하여 정렬 된 부분에 삽입하고) : 루프 동안 내부를 교체

for i ← 1 to length(A) 
    x ← A[i] 
    j ← i 
    while j > 0 and A[j-1] > x 
     A[j] ← A[j-1] 
     j ← j - 1 
    A[j] ← x

을 A [i]가 삽입 될 필요가있는 곳을 스캔하기 만하면됩니다. A [i]가 소트 된리스트의 것보다 큰 경우, 내부 루프는 반복하지 않고, j == i가되고, A [i]는 이동 될 필요가 없다 (단지 외부 루프와 계속된다) .

출처

2014-02-28 21:19:54 rcgldr

링크 목록을 사용한 삽입 정렬

답변

관련 문제