이 C 코드 조각이 무한 루프로 끝나는 이유는 무엇입니까?

Question

이 코드에서 무한 루프를 수정하려고했습니다. 그러나 무한 루프가 발생하는 이유를 이해할 수 없습니다. 이 코드는 처리되기 전에 가장 작은 것부터 가장 큰 것까지 작업을 정렬하려고합니다.

SortJobs() 
{ 
    linked_list ptr, h, temp, pptr; 
    int i, j; 

    pptr = ready_queue; 
    ptr = ready_queue->next; 
    h= ready_queue; 

    while(ptr != NULL) {  
     if ((ready_queue->pcb.job_length - ready_queue->pcb.run_time) > (ptr->pcb.job_length - ptr->pcb.run_time)) { 
      ready_queue = ptr; 
      pptr->next = ptr->next; 
      ptr->next = h->next;     
      h->next = pptr->next; 
      pptr->next = h; 
      ptr=h->next; 
      h=ready_queue; 
      pptr=ptr->next; 
     } else { 
      pptr = ptr; 
      ptr=ptr->next;   
     } 
    } 
} 

Answer 1

ptr은 항상 null이 아니기 때문에 ??

Answer 2

gdb은 이러한 문제를 디버깅하는 데 귀하의 친구입니다. 디버거를 사용하십시오!

OTOH는 circular-(linked)-list입니다.

팁 : SortJobs()을 실행하기 전에 ready_queue을 실행하고 모든 요소를 ​​인쇄하여 무한 루프에 있는지 확인하십시오.

링크 된 목록의 마지막 노드를 NULL으로 설정하지 않았기 때문에 무한 루프가 발생할 수 있습니다. addNode() 기능을 확인할 수 있습니다.

Answer 3

눈에 띄는 문제는이 라인이 :

pptr=ptr->next; 

때때로이 선 다음에 할 수 있습니다

pptr->next = ptr->next; 

pptr을 변경하지

또는 사이 ptr. 그러면 ptr->next->next == ptr->next과 함께 작은 노드 연결 고리가 생깁니다. 따라서 링크 된 목록에서 벗어날 수는 없습니다.

전반적으로 알고리즘이 매우 혼란 스럽습니다. 각 변수에 대해 하나의 논리적 인 의미를 결정하고 적절한 루프 불변량을 생각해 내야합니다. 예를 들어, 루프 반복이 끝나면 때때로 ptr == pptr->next (올바른 것 같아요)이 표시되지만 때로는 pptr == ptr->next (위의 이유로 잘못된 것 같습니다)입니다.

Answer 4

알고리즘이 매우 혼란스럽고 잘못된 것 같습니다. 루프가 어떻게 든 끝나고 모든 결과를 올바르게 처리했다면 첫 번째 요소는 job_length - run_time이 최소 인 요소이지만 나머지 목록은 정렬되지 않습니다.

ruakh이 지적했듯이 문제는 다음 포인터를 모두 조작 할 때 목록을 엉망으로 만든다는 것입니다. 나는 전체 노드를 움직이는 목록 자체의 구조에 손대지 않고 memcpy를 사용하고 노드가 가지고있는 데이터 만 이동시킨다. 우리는, 좀 잘 테스트/잘 알려진 정렬 알고리즘을 사용하는 거라고 노드들이 올바르게 쉽게 도움을 찾을 것입니다 이런 식으로하고 다음 중 하나를 교환 할 수 있는지 이제

// I assume your linked list is made of nodes such as this 
typedef struct { 
    struct Node next; 
    struct Node prev;  // optional 
    struct Somewhat pcb; 
} Node; 

void swapData(Node *n1, Node *n2) 
{ 
    struct pcb temp; 

    memcpy(&temp, n1->pcb, sizeof(struct Somewhat)); 
    memcpy(n1->pcb, n2->pcb, sizeof(struct Somewhat)); 
    memcpy(n2->pcb, &temp, sizeof(struct Somewhat)); 
} 

: 다음은 샘플 funcion입니다 누가 당신의 코드를 보게 될 것입니다 자신을 죽일 유혹되지 않습니다 (의도 장난, 나는 단지 농담이야;)). Selection sort 또는 Bubble sort과 같은 간단한 알고리즘을 제안 해 드리겠습니다. 매우 빠르지 만 구현하기 쉽습니다.