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);