функция swapNode не работает в двусвязном списке

Question

Функция swapNode меняет 2 узла в списке. Функция create node* temp для хранения временных данных заменяет данные node* A и node* B. Я не могу понять, почему это не работает. Ниже приведен мой код:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
struct node;
struct list;

typedef struct node node;
typedef struct list list;

struct node
{
    int point;
    char name[30];
    node *next;
    node *prev;
};

struct list
{
    node *head;
    node *tail;
    int count;
};

node *allocateNewNode(int point, char name[30], node *prev, node *next);
list *createList();
bool insertHead(list *listNode, int point, char name[30]);
bool compareName(char a[30], char b[30]);
bool swapNode(list *listNode, char nameA[30], char nameB[30]);

int main()
{
    list *listNode = createList();

    insertHead(listNode, 10, "abc def");
    insertHead(listNode, 9, "qwe rty");
    insertHead(listNode, 8, "ui op");
    insertHead(listNode, 30, "fgh jkl");
    insertHead(listNode, 1234, "akaka");

    swapNode(listNode, "ui op", "abc def");

    node *temp = listNode->head;
    while (temp != NULL)
    {
        printf("%-20s%d\n", temp->name, temp->point);
        temp = temp->next;
    }
    free(temp);
    printf("\n%d", listNode->count);
    return 0;
}

node *allocateNewNode(int point, char name[30], node *prev, node *next)
{
    node *newNode = (node *)malloc(sizeof(node));
    newNode->point = point;
    strcpy(newNode->name, name);
    newNode->next = next;
    newNode->prev = prev;
    return newNode;
}

list *createList()
{
    list *listNode = (list *)malloc(sizeof(list));
    listNode->count = 0;
    listNode->head = NULL;
    listNode->tail = NULL;
    return listNode;
}

bool insertHead(list *listNode, int point, char name[30])
{
    node *newNode = allocateNewNode(point, name, NULL, listNode->head);
    if (listNode->head)
        listNode->head->prev = newNode;
    listNode->head = newNode;
    if (listNode->tail == NULL)
        listNode->tail = newNode;
    ++listNode->count;
    return true;
}
bool compareName(char a[30], char b[30])
{
    for (int i = 0; i < 31; i++)
    {
        if (a[i] != b[i])
            return false;
        if (a[i] == '\0')
            break;
    }

    return true;
}

bool swapNode(list *listNode, char nameA[30], char nameB[30])
{
    node *A = NULL, *B = NULL;
    node *temp = listNode->head;

    for (int i = 0; i < listNode->count - 1; i++)
    {
        if (compareName(temp->name, nameA))
            A = temp;
        else if (compareName(temp->name, nameB))
            B = temp;
        temp = temp->next;
        if (A || B)
            break;
    }
    if (!A || !B)
        return false;
    else if (A == B)
        return false;

    *temp = *A;
    *A = *B;
    *B = *temp;

    if (A->prev)
        A->prev->next = A;
    if (A->next)
        A->next->prev = A;
    if (A->prev)
        A->prev->next = A;
    if (A->next)
        A->next->prev = A;
    free(temp);
    return true;
}

TKS за вашу помощь

Answer 1

In swapNode, A и B изначально NULL. L oop, который ищет два совпадающих узла, завершается рано, когда обнаруживается любой из узлов:

        if (A || B)
            break;

Не более одного из A и B будет ненулевым, если l oop завершается, поэтому хотя бы один из A и B будет равен NULL. Это заставляет функцию возвращать false:

    if (!A || !B)
        return false;

Чтобы избежать этого, вы должны изменить l oop на разрыв, когда оба A и B не равны NULL:

        if (A && B)
            break;

Кроме того, l oop проверяет только count - 1 элементы списка, поэтому игнорирует последний элемент:

    for (int i = 0; i < listNode->count - 1; i++)

Чтобы проверить все элементы, вам необходимо изменить это to:

    for (int i = 0; i < listNode->count; i++)

В качестве альтернативы, вы можете проигнорировать listNode->count и проверить вместо него указатель temp:

    while (temp != NULL)

Это будет работать, потому что temp инициализируется в listNode->head , который будет NULL для пустого списка, а для непустого списка, элемент next последнего элемента в списке равен NULL, поэтому temp = temp->next; установит temp в NULL когда проверен последний элемент.

---

В swapNode есть другие проблемы, связанные с фактической заменой узлов после того, как они были найдены. Исходный код для этого выглядит совершенно неверно:

    *temp = *A;
    *A = *B;
    *B = *temp;

Указатель temp будет либо NULL, либо будет указывать на узел после узлов A и B.

    if (A->prev)
        A->prev->next = A;
    if (A->next)
        A->next->prev = A;
    if (A->prev)
        A->prev->next = A;
    if (A->next)
        A->next->prev = A;

Код не изменяется listNode->head или listNode->tail, когда A или B находится в начале или конце списка.

    free(temp);

Почему он освобождается temp здесь, когда все функции, которые предполагается выполнять, это обмен узлами?

Код для замены узлов A и B должен иметь возможность иметь дело ни с одним, ни с одним из обоих узлов, находящихся на конец (и) списка, причем A и B являются соседними узлами в любом порядке. Вот последовательность для обработки всего этого:

    /* update list head pointer */
    if (listNode->head == A)
        listNode->head = B;
    else if (listNode->head == B)
        listNode->head = A;

    /* update list tail pointer */
    if (listNode->tail == A)
        listNode->tail = B;
    else if (listNode->tail == B)
        listNode->tail = A;

    /* update ->prev->next pointers */
    if (A->prev != NULL && A->prev != B)
        A->prev->next = B;
    if (B->prev != NULL && B->prev != A)
        B->prev->next = A;

    /* update ->next->prev pointers */
    if (A->next != NULL && A->next != B)
        A->next->prev = B;
    if (B->next != NULL && B->next != A)
        B->next->prev = A;

    /* update A->prev and B->prev pointers */
    if (A->prev == B)
    {
        A->prev = B->prev;
        B->prev = A;
    }
    else if (B->prev == A)
    {
        B->prev = A->prev;
        A->prev = B;
    }
    else
    {
        temp = A->prev;
        A->prev = B->prev;
        B->prev = temp;
    }

    /* update A->next and B->next pointers */
    if (A->next == B)
    {
        A->next = B->next;
        B->next = A;
    }
    else if (B->next == A)
    {
        B->next = A->next;
        A->next = B;
    }
    else
    {
        temp = A->next;
        A->next = B->next;
        B->next = temp;
    }

Answer 2

Используя отладчик, вы увидите, что функция swapNode возвращает значение

    if (!A || !B)
        return false;

Если вы пройдете через for l oop, вы увидите, что вы break из l oop когда установлено хотя бы одно из A и B, т.е. когда найден первый соответствующий узел.

        if (A || B)
            break;

Измените это на

        if (A && B)
            break;