C语言 交换双向链表中的节点时出现问题

Question

我正在尝试使用 C 交换双向链表中的两个节点。如果我传入一些值，例如列表的头部和尾部，以及介于两者之间的一些值，它就可以工作。然而，在其他方面，一个的价值似乎被另一个覆盖了，我陷入了一个循环。

节点/列表：

struct node //node for linked list
{
    unsigned long int *id;
    char *firstname, *lastname, *department;
    float *gpa;
    struct node *next, *prev;
};
struct linked_list //doubly linked_list data structure
{
    struct node *head, *tail;
};

我可以成功地将节点添加到列表中，并将尾部移动到新添加的节点。

void *add_node(struct node **tail, unsigned long int *id, char *first, char *last, char *dept, float *gpa) //create a node, add to tail
{
    struct node *newStudent = (struct node*)malloc(sizeof(struct node));
    newStudent->firstname = (char*)malloc(strlen(first)+1);
    newStudent->lastname = (char*)malloc(strlen(last)+1);
    newStudent->department = (char*)malloc(strlen(dept)+1);
    newStudent->id = (unsigned long int*)malloc(sizeof(unsigned long int));
    newStudent->gpa = (float*)malloc(sizeof(float));
    *(newStudent->id) = *id;
    *(newStudent->gpa) = *gpa;
    strcpy(newStudent->firstname, first);
    strcpy(newStudent->lastname, last);
    strcpy(newStudent->department, dept);
    newStudent->next = NULL;
    if(tail) //not the first node in the list
    {
        newStudent->prev = *tail;
        (*tail)->next = newStudent;
        *tail = newStudent;
    }
    else //head of the list
        return newStudent;
}

最后，我的交换函数：

void *_swap(struct node **x, struct node **y, struct linked_list **list)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    memcpy(temp, *x, sizeof(struct node));
    if( (*y)->prev ) /// if y has a previous...
    {
        (*x)->prev = (*y)->prev;
        (*y)->prev->next = *x;
    }
    else
        (*x)->prev = NULL;
    if( (*y)->next )  /// if y has a next...
    {
        (*x)->next = (*y)->next;
        (*y)->next->prev = *x;
    }
    else
        (*x)->next = NULL;
    if( temp->prev) /// if original x has a previous...
    {
        (*y)->prev = temp->prev;
        temp->prev->next = *y;
    }
    else
        (*y)->prev = NULL;
    if(temp->next) /// if original x has a next...
    {
        (*y)->next = temp->next;
        temp->next->prev = *y;
    }
    else
    (*y)->next = NULL;
    free(temp);
    if((*list)->head == *x && (*list)->tail == *y)
    {
        (*list)->head = *y;
        (*list)->tail=*x;
    }
    else if((*list)->head == *y && (*list)->tail == *x)
    {
        (*list)->head = *x;
        (*list)->tail=*y;
    }
    else if((*list)->head == *x)
        (*list)->head = *y;
    else if((*list)->head == *y)
        (*list)->head = *x;
    else if((*list)->tail == *x)
        (*list)->tail = *y;
    else if((*list)->tail == *y)
        (*list)->tail = *x;
    printf("%s %s %s %s %snnnn", (*list)->head->firstname, (*list)->head->next->firstname, (*list)->head->next->next->firstname, (*list)->head->next->next->next->firstname, (*list)->head->next->next->next->next->firstname);
}

当我打电话给类似的东西 临时>下一个>上一页 = *y;在这种情况下，它有时似乎覆盖了 x 的值，而不是简单地将linked_list指针重新分配给 y。

我能够很好地构建我的列表：

struct linked_list *list = (struct linked_list*)malloc(sizeof(struct linked_list));
list->head = (struct node*)malloc(sizeof(struct node));
list->tail = (struct node*)malloc(sizeof(struct node));
unsigned long int *id = malloc(sizeof(unsigned long int));
*id = 343232;
float gpa = 3.2;
list->head = add_node(NULL, id, "Matthew", "D", "CECS", &gpa);
list->tail = list->head;
add_node(&(list->tail), id, "John", "X", "PNY", &gpa);
add_node(&(list->tail), id, "Rebecca", "H", "ECE", &gpa);

Answer 1

在你的代码中有很多东西跳出来。

• 你分配了很多东西，通常是不必要和无用的。正如 rcgldr 指出的那样，交换函数不应该分配新节点。毕竟，交换后，该列表由相同的节点组成，只是顺序不同。没有新节点。

• 您的"客户端代码"，即使用链表函数的函数（在您的示例中可能main），不应显式分配内存。它也不应该手动填充节点。它应该只调用 add_node 和 delete_node ，您还应该对其进行编码以释放所有分配的内存。

• 在您的案例中，无需将指针传递到指针。传递指向节点和列表结构的指针就足够了。这允许您更改结构的字段。指向结构的指针的指针仅在要更改结构句柄本身（例如通过重新分配它）时才有意义，但您没有这样做。（指向指针的指针通常用于单向链表，其中头部不存储在结构中。即使在那里，将单个指针包装在结构中也可能很有用，这样就不需要指向指针的指针。

• 所有逻辑都应该发生在函数中。不要修改"main"中的next和prev指针;这就是函数的用途。当你调用一个函数并从它返回时，某些"不变量"应该成立，例如：

  • 当列表为空时，head和tail都NULL。
  • 否则，head指向第一个节点;"head->prev is NULL . The尾部points to the last node; ´tail->next NULL。
  • 当节点nd具有前一个节点时，则nd->prev->next == nd 。
  • 同样，当一个节点nd有一个下一个节点时，则nd->next->prev == nd .

  您甚至可以编写一个健全性检查函数，以便在函数进入和退出时强制实施这些变量。

• 为所有字段分配数据。内存分配对字符串有意义，字符串是字符数组，其长度事先不知道。对于标量变量id和gpa没有意义。您可以将它们声明为非指针，然后直接分配给它们。（分配内存并通过指针访问它们并没有错，但直接访问要简单得多。

• 你的一些函数返回 void * ，void 指针。那不是你想要的。要么你的函数应该void，即没有返回值，要么它们应该返回指向节点的指针。（void 指针是合法数据类型，引用指向任何数据类型的指针，您无法取消引用。它用于泛型函数（如 qsort），不应在代码中使用。您不是在编写泛型函数，而是在为具体链表编写函数。

您可以将交换视为删除节点并将它们重新插入到它们各自的旧前身之后。您仍然需要注意捕获节点相邻的情况。

下面是一个示例实现，它试图尊重我上面提到的要点：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef unsigned long int ulong;
struct node
{
    ulong id;
    char *name;
    float gpa;
    struct node *next;
    struct node *prev;
};
struct list
{
    struct node *head;
    struct node *tail;
};

/*
 *      Create a new, unconnected node
 */
struct node *node_new(ulong id, const char *name, float gpa)
{
    struct node *node = malloc(sizeof(*node));  // Error checking!
    node->prev = NULL;
    node->next = NULL;
    node->id = id;
    node->gpa = gpa;
    node->name = malloc(strlen(name) + 1);
    strcpy(node->name, name);
    return node;
}
/*
 *      Create a list
 */
struct list *list_new()
{
    struct list *list = malloc(sizeof(*list));  // Error checking!
    list->head = list->tail = NULL;
    return list;
}
/*
 *      Add a student to list
 */
struct node *list_add(struct list *list,
    ulong id, const char *name, float gpa)
{
    struct node *node = node_new(id, name, gpa);
    node->prev = list->tail;
    if (list->tail == NULL) {
        list->head = list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }
    return node;
}
/*
 *      Delete a node from the list.
 */
void list_delete(struct list *list, struct node *node)
{
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next;
    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev;
    free(node->name);
    free(node);
}
/*
 *      Find student by id; return NULL if not found.
 */
struct node *list_find_by_id(const struct list *list, ulong id)
{
    struct node *node = list->head;
    while (node) {
        if (node->id == id) return node;
        node = node->next;
    }
    return NULL;
}
/*
 *      Extract a node without deleting
 */
void list_remove(struct list *list, struct node *node)
{
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next;
    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev;
    node->prev = node->next = NULL;
}
/*
 *      Insert node after prev or at the front when prev is NULL
 */
void list_insert_after(struct list *list,
    struct node *node, struct node *prev)
{
    if (prev) {
        node->next = prev->next;
        prev->next = node;
    } else {
        node->next = list->head;
        list->head = node;
    }
    node->prev = prev;
    if (node->next) node->next->prev = node;
}
/*
 *      Swap two nodes' positions in the list
 */
void list_swap(struct list *list, struct node *x, struct node *y)
{
    if (x == y) return;
    struct node *xprev = x->prev;
    struct node *yprev = y->prev;
    if (xprev == y) {            
        list_remove(list, x);
        list_insert_after(list, x, yprev);
    } else if (yprev == x) {            
        list_remove(list, y);
        list_insert_after(list, y, xprev);
    } else {
        list_remove(list, x);
        list_remove(list, y);
        list_insert_after(list, x, yprev);
        list_insert_after(list, y, xprev);
    }
}
/*
 *      Print list
 */
void list_print(const struct list *list)
{
    const struct node *node = list->head;
    while (node) {
        printf("%8lu  %-20s  %8.1fn", node->id, node->name, node->gpa);
        node = node->next;
    }
    printf("n");
}
/*
 *      Delete a list and all its nodes
 */
void list_destroy(struct list *list)
{
    while (list->head) list_delete(list, list->head);
    free(list);
}
/*
 *      Example client code using the list
 */
int main()
{
    struct list *list = list_new();
    list_add(list, 342232, "Matthew",   3.2);
    list_add(list, 342856, "John",      1.9);
    list_add(list, 342109, "Rebecca",   6.4);
    list_add(list, 342834, "Shirley",   2.6);
    list_add(list, 343009, "Simon",     1.4);
    list_add(list, 342170, "Antonio",   3.5);
    list_print(list);
    struct node *simon = list_find_by_id(list, 343009);
    struct node *becky = list_find_by_id(list, 342109);
    if (simon && becky) {
        list_swap(list, simon, becky);
        list_print(list);
    }
    list_destroy(list);
    return 0;
}