c - C中如何交换链表节点

Question

我正在尝试交换两个链表，我的排序功能不起作用。我怎样才能交换整个节点。我想做的是交换整个列表，而不是交换它的成员。

typedef struct    node
{
    char          *first_name;
    char          *last_name;
    struct node   *next;
}person;


person *new_p(char *name, char *last)
{
    person *p;

    p = malloc(sizeof(p));
    if (p)
    {
        p->first_name = name;
        p->last_name = last;
        p->next = NULL;
    }
    return (p);
}

void swap(person *a, person *b)
{
    person tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

void    sort(person *s)
{
     person *list;

    list = s;
    while (list->next)
    {
        if (strcmp(list->first_name, list->next->first_name) > 0)
        {
            swap(list, list->next);
        }
        list = list->next;
    }
}

Answer 1

您的交换函数混合了节点数据和节点指针，因此数据(包括与 next 指针相关的数据)正在被“交换”...

...这种混淆可能会导致内存泄漏和节点链中断。如果幸运的话，链将保持完整，但您将交换整个子部分，而不是仅交换两个节点。

要交换节点数据，请考虑(这是未经测试的代码):

// ugly, but should work
typedef struct node {
  char* first_name;
  char* last_name;
  struct node* next;
} person;

void swap(person* a, person* b) {
  person tmp;
  tmp.first_name = a->first_name;
  tmp.last_name = a->last_name;
  a->first_name = b->first_name;
  a->last_name = b->last_name;
  b->first_name = tmp.first_name;
  b->last_name = tmp.last_name;
}

或者这个(不那么难看并且更容易维护):

typedef struct {
  char* first_name;
  char* last_name;

} person_s;

typedef struct person_nd person_nd;

struct person_nd {
  person_s data;
  person_nd* next;
};

void swap2(person_nd* a, person_nd* b) {
  person_s tmp;
  tmp = a->data;
  a->data = b->data;
  b->data = tmp;
}

这些都是丑陋的解决方案。正确的方法是保持数据不变并交换节点的位置。

这要求我们了解有关节点列表结构的更多信息，特别是引用节点的指针的地址。

另一方面，这种类型的解决方案是数据独立的，因此数据结构的更新不需要重写实现。

即(这肯定会失败，但它应该演示这个概念):

void swap3(person_nd** a, person_nd** b) {
  person_nd* tmp = *a;
  // swap the position in the tree.
  *a = *b;
  *b = tmp;
  // swap the "forward" branches
  tmp = (*a)->next;
  (*a)->next = (*b)->next;
  (*b)->next = tmp;
}