연결된 목록 및 (알파벳순) 버블 정렬

Question

연결된 목록으로 버블 정렬에 문제가 있습니다. 몇 시간 동안 간단한 코드에서 버그를 발견하지 못했습니다. 저것 좀 볼래?

int listSwapWithNext(node_t **_list, size_t first) 
{ 
    node_t *pointer = *_list; 
    node_t *ptr_b; 
    node_t *ptr_c; 
    node_t *ptr_d; 

    if(!first) 
      ptr_b = pointer; 

    for(size_t i = 0; pointer->next->next; i++, pointer = pointer->next) 
    { 
      if(i == first - 1 || first == 0) 
      { 
       if(first) 
        ptr_b = pointer->next; 

       ptr_c = ptr_b->next; 
       ptr_d = ptr_c->next; 

       if(first) 
        pointer->next = ptr_c; 
       else 
        *_list = ptr_c; 

       ptr_c->next = ptr_b; 
       ptr_b->next = ptr_d; 

       break; 
      } 
    } 

    return 0;  
} 

그것은 (라인 229)이 충돌이 발생합니다 :

(I 수동으로 모든 경계 케이스를 테스트하기 때문에, 그러나 잘 작동하는 것 같다)

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 

    for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 
    } 

    return 0; 
} 

여기 스왑 기능입니다

정렬 함수의 내부 루프 condyition을 다음과 같이 수정했습니다.

for(int j = 0; j < size - 1 && pointer->next; j++) 

나쁜 주소에서 읽는 것을 막기 위해, 나는 이상한 것을 알아 차렸다. 내부 루프 somtimes 정확하게보다 한 번만 실행해야합니다.

감사합니다.

편집 : 다음은 수정 된 것 (printf와 함께 만든()) 내부 루프에 방지 조건 내 디버그 지표와 정렬 기능의 버전 :

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

여기 콘솔의 결과입니다. 보세요, 매 사이클마다 그렇게하지 않아서 나쁜 정렬을 가져옵니다.

EDIT2 : 여기에 문제의 essention의 . http://pastebin.com/e5K6C1A2

여전히이 문제를 해결할 수 없습니다.

Answer 1

pointer = pointer->next은 스왑이 이루어진 경우 올바르지 않습니다. 스왑을 만든 경우 pointer은 이미 하나의 요소만큼 앞으로 이동되었으므로 pointer으로 남아 있어야합니다.

편집 : 나는 이렇게 의미 :

if(strcmp(pointer->title, pointer->next->title) > 0) 
    listSwapWithNext(_list, j); 
else 
    pointer = pointer->next; 

Answer 2

당신이 말한 것을 근거로하면 코드에서 몇 가지 문제점을 파악하는 데 도움이 될 것입니다. 설명하는 문제는 귀하가 게시 한 첫 번째 코드 블록, 특히이 부분에 기인한다고 생각합니다.

for(int i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 

      for(int j = 0 ; j < size - 1; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       pointer = pointer->next; 
      } 

문제는이 라인에 의해 발생되는 :

때문에 내부 루프가 여기 어떻게 구성되는지의

if(strcmp(pointer->title, pointer->next->title) > 0) 

:

for(int j = 0 ; j < size - 1; j++) 

그래서 당신이 사실을 차지되는 우리 때문에 우리는 목록의 전체 크기보다 1을 덜 필요로합니다. 그러나 문제는 이것이 당신이 그것을 통해 마지막 실행에 널 포인터를 역 참조하려고하는 원인이된다는 것입니다. 연결된 목록의 노드에는 일부 데이터에 대한 포인터와 다음 객체에 대한 포인터가 있습니다. 그래서 for 루프가 실행되는 마지막 순간부터 2 번째로 일어나는 일을 상상해보십시오. strcmp이 참이면 스왑을 수행하고 링크 된 목록의 다음 요소를 참조하도록 포인터를 전진시킵니다. 여기가 잘못 된 곳입니다. 작업이 완료했기 때문에 우리가 다시이 줄을 루프를 실행할 때 :

if(strcmp(pointer->title, pointer->next->title) > 0) 

특별히이 부분 : pointer->next->title 현재 개체가 연결리스트의 마지막 요소이기 때문에 실패합니다.이런 이유 때문에 다음에 NULL을 가리키며 존재하지 않는 NULL 요소의 title 객체를 얻으려고합니다.

이제 수정 된 코드를 살펴보십시오.

int listSort(node_t ** _list) 
{ 
    int size = listSize(_list); 
    int i; 
    for(i = 0; i < size; i++) 
    { 
      node_t *pointer = *_list; 
      int j; 
      for(j = 0 ; j < size - 1 && pointer->next; j++) 
      { 
       if(strcmp(pointer->title, pointer->next->title) > 0) 
        listSwapWithNext(_list, j); 

       printf("# %d %d\n", i, j); 
       pointer = pointer->next; 
      } 
      printf("\n"); 
    } 

    return 0; 
} 

같은 오류가 발생하지 않지만 잘못된 결과가 발생합니다. 이것을 다시은의 구조로 인해, 정렬 기능에 의해 야기되지 않은 여기 for 루프 : 루프

for(j = 0 ; j < size - 1 && pointer->next; j++) 

A가 한 특정 조건이 참으로 실행된다. 다시 마지막 실행을 상상해보십시오. 우리는 크기 범위 내에 있으므로 첫 번째 조건은 참이고 두 번째 조건도 역시 참인 다른 요소가 있습니다. 루프가 실행되고 포인터가 다음 요소로 이동합니다. 이제 우리는 여전히 크기 제약 조건에 해당하므로 사실이지만이 이후에 목록에 더 이상 요소가 없으므로 pointer->next은 NULL입니다. 즉, 루프가 실행되지 않으므로 잘못된 결과를 제공하는 모든 데이터를 정렬하지 않습니다.