이중 연결 목록을 사용하여 C 스와핑

Question

링크 된 목록에서 노드의 위치를 ​​바꿔서 이상을 정렬 함수로 정렬하려고합니다. 이 함수 중 하나에서 논리적 오류가 발생합니다. 프로그램을 실행하면 무한 루프가됩니다.

업데이트 코드

int adjuctNodes(struct student_record_node** n1, struct student_record_node** n2) 

{ 
     struct student_record_node* prev_; 
     struct student_record_node* next_; 
     return((*n1)->next_==(*n2) && (*n2)->prev_ == (*n1))|| 
     ((*n1)->prev_ ==(*n2) && (*n2)->next_ == (*n1)); 
} 

void updateOuterPointer(struct student_record_node** n) 

{ 
    struct student_record_node* next_; 
    struct student_record_node* prev_; 
    if((*n)->next_!=NULL) 
      (*n)->prev_->next_=(*n); 
    if((*n)->next_ !=NULL) 
      (*n)->next_->prev_=(*n); 
} 


/*Swaping */ 

void swap(struct student_record_node** node1, struct student_record_node** node2) 

{ 


      struct student_recod_node* prev_; 
      struct student_recod_node* next_; 
      struct student_record_node* ptr=(*node1)->next_; 

      if(adjucntNodes((node1),(node2))) 
    { 
      (node1)->prev_=pnode2; 
      (node2)->prev_=pnode0; 
      (node1)->next_=pnode3; 
      (node2)->next_=pnode1; 

    }else{ 

      (node1)->prev_=pnode1; 
      (node2)->prev_=pnode0; 
      (node1)->next_=pnode3; 
      (node2)->next_=pnode2; 
    } 

    updateOuterPointer((node1)); 
    updateOuterPointer((node2)); 

} 
/*Sorting linked list*/ 


void sort(struct student_record_node**recordsHead,int(*compare_fcn)(struct 
student_record_node*,struct student_record_node*)) 

{ 

     int swapped; 
     struct student_record_node *ptr1=*recordsHead; 
     struct student_record_node *lptr = NULL; 

     if (ptr1 == NULL) 
       return; 

     do 
     { 
       swapped = 0; 
       ptr1 = *recordsHead; 


       while (ptr1->next_ != lptr) 
       { 
           if (compare_fcn(ptr1,ptr1->next_)) 
         { 
           printf("swapping\n"); 
           swap(&ptr1,&ptr1->next_); 
           if(ptr1==*recordsHead) 
           { 
            (*recordsHead)=ptr1->next_; 
           } 
           swapped=1; 

         } 

         else ptr1 = ptr1->next_; 
       } 
        lptr = ptr1; 
         ; 
     } 
     while (swapped); 


} 

Answer 1

이 두 가지 원래 코드의 문제, 그리고 아마도 3 위 : 노드가 인접 교환 될 때

이

1. swap 기능이 작동하지 않습니다는하지만, sort 기능은 인접 노드를 바꿉니다 ! 두 노드 ptr1 및 ptr1->next_, 첫 번째 노드가 교환되는 경우 sort 기능 검사, ptr1 교환 후
2. 는리스트의 헤드이고, 만약 그렇게 ptr1->next_리스트의 헤드한다.그러나 두 노드가 역순으로되어 있으므로이 경우에는 ptr1->prev_이 목록의 헤드가되어야합니다.
3. 비교 함수는 첫 번째 인수가 두 번째 인수보다 작 으면 음수 값을 반환하고, 두 번째 인수가 같으면 0을 반환하고 첫 번째 인수가 두 번째 인수보다 큰 경우 양수 값을 반환합니다. sort 함수는 현재 첫 번째 인수가 두 번째 인수보다 작거나 같은 경우 비교 함수가 0을 반환 할 것으로 예상됩니다. 이것은 버그 일 수도 있고 아닐 수도 있지만, 통상적이지 않습니다.

또한 노드에 대한 포인터에 포인터를 전달할 필요가 없으므로 swap 함수에 대한 인터페이스를 단순화 할 수 있습니다.

다음 예제 프로그램은 위의 문제를 해결

#include <stdio.h> 
#include <string.h> 

struct student_record_node { 
    struct student_record_node *next_; 
    struct student_record_node *prev_; 
    const char *name; 
    unsigned int age; 
}; 

void swap(struct student_record_node *node1, struct student_record_node *node2) 
{ 
    struct student_record_node *ptr1, *ptr2; 

    /* Swap the 'next_' pointers, taking adjacency into account. */ 
    ptr1 = node1 == node2->next_ ? node2 : node2->next_; 
    ptr2 = node2 == node1->next_ ? node1 : node1->next_; 
    node1->next_ = ptr1; 
    node2->next_ = ptr2; 
    /* Swap the 'prev_' pointers, taking adjacency into account. */ 
    ptr1 = node1 == node2->prev_ ? node2 : node2->prev_; 
    ptr2 = node2 == node1->prev_ ? node1 : node1->prev_; 
    node1->prev_ = ptr1; 
    node2->prev_ = ptr2; 
    /* Fix the links from other nodes. */ 
    if (node1->next_) node1->next_->prev_ = node1; 
    if (node1->prev_) node1->prev_->next_ = node1; 
    if (node2->next_) node2->next_->prev_ = node2; 
    if (node2->prev_) node2->prev_->next_ = node2; 
} 

int compare_ages(const struct student_record_node *a, 
     const struct student_record_node *b) 
{ 
    return a->age < b->age ? -1 : a->age > b->age ? 1 : 0; 
} 

int compare_names(const struct student_record_node *a, 
     const struct student_record_node *b) 
{ 
    return strcmp(a->name, b->name); 
} 

void sort(struct student_record_node **recordsHead, 
     int(*compare_fcn)(const struct student_record_node *, 
       const struct student_record_node *)) 
{ 
    int swapped; 
    struct student_record_node *ptr1; 
    struct student_record_node *lptr = NULL; 

    if (*recordsHead == NULL) 
     return; 

    do 
    { 
     swapped = 0; 
     ptr1 = *recordsHead; 

     while (ptr1->next_ != lptr) 
     { 
      if (compare_fcn(ptr1, ptr1->next_) > 0) 
      { 
       printf("swapping (%s:%u <=> %s:%u)\n", ptr1->name, ptr1->age, 
         ptr1->next_->name, ptr1->next_->age); 
       swap(ptr1, ptr1->next_); 
       if (ptr1 == *recordsHead) 
       { 
        /* ptr1 is now the second node. */ 
        (*recordsHead) = ptr1->prev_; 
       } 
       swapped = 1; 
      } 
      else 
      { 
       ptr1 = ptr1->next_; 
      } 
     } 
     lptr = ptr1; 
    } 
    while (swapped); 
} 

void dump(const struct student_record_node *students) 
{ 
    const struct student_record_node *prev_ = NULL; 
    unsigned int pos = 0; 

    while (students) 
    { 
     if (students->prev_ != prev_) 
     { 
      printf("[%u] ** Bad prev_ link!\n", pos); 
     } 
     printf("[%u] %s:%u\n", pos, students->name, students->age); 
     pos++; 
     prev_ = students; 
     students = students->next_; 
    } 
} 

int main(void) 
{ 
    static struct student_record_node testdata[] = 
    { 
     { testdata + 1, NULL, "susan", 20 }, 
     { testdata + 2, testdata + 0, "bill", 21 }, 
     { testdata + 3, testdata + 1, "joe", 18 }, 
     { testdata + 4, testdata + 2, "tom", 19 }, 
     { NULL, testdata + 3, "karen", 21 }, 
    }; 
    struct student_record_node *students = testdata; 

    puts("Original order:"); 
    dump(students); 
    puts("By name:"); 
    sort(&students, compare_names); 
    dump(students); 
    puts("By age:"); 
    sort(&students, compare_ages); 
    dump(students); 
    return 0; 
} 

출력 :

Original order: 
[0] susan:20 
[1] bill:21 
[2] joe:18 
[3] tom:19 
[4] karen:21 
By name: 
swapping (susan:20 <=> bill:21) 
swapping (susan:20 <=> joe:18) 
swapping (tom:19 <=> karen:21) 
swapping (susan:20 <=> karen:21) 
[0] bill:21 
[1] joe:18 
[2] karen:21 
[3] susan:20 
[4] tom:19 
By age: 
swapping (bill:21 <=> joe:18) 
swapping (karen:21 <=> susan:20) 
swapping (karen:21 <=> tom:19) 
swapping (bill:21 <=> susan:20) 
swapping (bill:21 <=> tom:19) 
swapping (susan:20 <=> tom:19) 
[0] joe:18 
[1] tom:19 
[2] susan:20 
[3] bill:21 
[4] karen:21 

Answer 2

노드들이 공통 코드, 제 스왑 두 노드들 (외부) 포인터 인접한 인접하거나하지 않는 경우는, 다음 두 노드 (내부) 포인터를 스왑 모두 처리하려면 . 이렇게하면 노드가 인접한 경우 필요에 따라 포인터를 회전시키고 노드가 인접하지 않으면 포인터 쌍을 서로 바꿉니다. 노드가 인접한 경우 "외부"포인터 중 하나가 "다른"노드 내부 포인터 중 하나가되고 반대의 경우도 있지만 여전히 작동합니다. "외부"포인터를 먼저 교체 한 후 "내부"포인터를 다음에 교체하십시오.

스왑을 수행 할 때 필요에 따라 임시 포인터 (기술적으로 노드 포인터에 대한 포인터)를 사용해야합니다. 그렇지 않으면 스왑 연산을 통해 노드 포인터를 부분적으로 덮어 씁니다. 막히면 나중에 예제로 업데이트 할 수 있습니다.

업데이트 - 예를 들어 다음 포인터로 연결된 링크 된 목록을 사용하여 어떤 일이 발생하는지 보여주는 다이어그램 유형 예제입니다. >

0->1->2->3->4 

스왑 1, 3, 0-> 2-> 상대 포인터는 1-> 3- 내부 위치 : 5 개 노드 0~4 시작 가정한다. 0-> 1-> 2부터 출발

0->3->2->1->4 

결과 우선 스왑 0-> 2-

0->3 
2->1 

후 1- 교체>> 3->

1->4 
3->2 

-> 3-> 4 스왑 1 및 2, 0-> 및 1-> 외부, 1-> 및 2-> 내부. 스왑 0-> 1->

0->2 
1->1 

는 1- 교체> 2->

1->3 
2->1 

는

0->2->1->3->4 

예 스왑 코드 생성. 이 코드는 첫 번째 노드를 가리키는 헤드 포인터와 마지막 노드 (또는 NULL)를 가리키는 테일 포인터가 있다고 가정합니다.

struct student_record_node *Head = &firstnode; /* head */ 
struct student_record_node *Tail = &lastnode; /* tail (NULL is ok) */ 

/* swap function */ 

void swap(struct student_record_node **Head, 
      struct student_record_node **Tail, 
      struct student_record_node *node1, 
      struct student_record_node *node2) 
{ 
struct student_record_node **en1 /* & external next ptr to 1 */ 
struct student_record_node **en2 /* & external next ptr to 2 */ 
struct student_record_node **ep1 /* & external prev ptr to 1 */ 
struct student_record_node **ep2 /* & external prev ptr to 2 */ 
struct student_record_node *tmp /* temp node ptr */ 
    en1 = (node1->prev_ != NULL) ? &(node1->prev_->next_) : Head; 
    en2 = (node2->prev_ != NULL) ? &(node2->prev_->next_) : Head; 
    ep1 = (node1->next_ != NULL) ? &(node1->next_->prev_) : Tail; 
    ep2 = (node2->next_ != NULL) ? &(node2->next_->prev_) : Tail; 
    /* swap en1, en2 */ 
    tmp = *en1; 
    *en1 = *en2; 
    *en2 = tmp; 
    /* swap ep1, ep2 */ 
    tmp = *ep1; 
    *ep1 = *ep2; 
    *ep2 = tmp; 
    /* swap n1, n2 next_ */ 
    tmp = node1->next_; 
    node1->next_ = node2->next_; 
    node2->next_ = tmp; 
    /* swap n1, n2 prev_ */ 
    tmp = node1->prev_; 
    node1->prev_ = node2->prev_; 
    node2->prev_ = tmp; 
} 

    /* call to swap function */ 
    swap(&Head, &Tail, node1, node2);