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

有在原始代码中的两个主要问题，并且可能三分之一：

1. 时被交换节点是相邻的swap功能不起作用，但sort函数只交换相邻节点！
2. 交换两个节点ptr1和ptr1->next_，所述sort函数检查被交换的第一个节点，ptr1之后，是在列表的开头，并且如果是这样，使ptr1->next_列表的头部。但是，这两个节点现在是相反的顺序，所以在这种情况下它应该使ptr1->prev_成为列表的头部。
3. 比较函数通常在第一个参数小于第二个参数时返回负值，如果相等则返回零，如果第一个参数大于第二个参数则比较函数返回正值。如果第一个参数小于或等于第二个参数，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

同时处理其中节点是相邻的或不相邻的具有共同代码，第一交换（外部）的指针的两个节点的情况下，则交换两个节点的（内部）的指针。如果节点相邻，这将最终根据需要旋转指针，并且如果节点不相邻则交换指针对。请注意，如果节点相邻，其中一个“外部”指针将成为“其他”节点内部指针之一，反之亦然，但仍然可以实现：首先交换“外部”指针，然后交换“内部”指针。

确保在进行交换时根据需要使用临时指针（技术上指向节点指针的指针），否则通过交换操作部分覆盖节点指针。如果卡住了，我可以稍后更新一个例子。

更新 - 图表类型示例显示发生了什么，使用单个链接列表，只用下一个指针作为示例。假设你开始5个节点，0〜4：

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

交换1和3，0->和2->是外部指针，1->和3->是内部的。第一交换0->和2->

0->3 
2->1 

然后交换1->和3->

1->4 
3->2 

导致

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

从0-> 1-> 2启动 - > 3-> 4 swap 1和2，0->和1->是外部的，1->和2->是内部的。交换0-> 1->

0->2 
1->1 

然后交换1->并导致

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

实施例交换代码2->

1->3 
2->1 

。这段代码假设有指向第一个节点的头指针和指向最后一个节点（或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);