Обмен 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

Для того, чтобы обрабатывать как случаи, когда узлы являются смежными или не смежны с общим кодом, первая подкачки (внешние) указатели на два узел, а затем поменять местами (внутренние) указатели на два элементах узла , Это приведет к вращению указателей по мере необходимости, если узлы смежны, и обмен парами указателей, если узлы не смежны. Обратите внимание, что если узлы смежны, один из «внешних» указателей будет одним из внутренних указателей «других» узлов, и наоборот, но он все же работает: сначала меняйте «внешние» указатели, затем «внутренние» указатели.

Обязательно используйте временные указатели (технические указатели на указатели узлов) по мере необходимости при выполнении свопов, иначе вы переписываете указатели узлов частично через операцию свопинга. Если застрял, я могу обновить пример позже.

update - пример типа диаграммы, чтобы показать, что происходит, используя один связанный список с помощью только следующих указателей в качестве примера. Предположим, вы начинаете с 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-> и 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);