c - 函数 swapNode 在双向链表中不起作用
问题描述
函数swapNode
交换列表中的 2 个节点。node* temp
用于存储临时数据的函数 create然后交换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;
}
谢谢你的帮助
解决方案
在swapNode
和A
最初B
是NULL
。当找到任何一个节点时,搜索两个匹配节点的循环会提前终止:
if (A || B)
break;
当循环终止时,最多A
和之一B
将为非 NULL,因此至少A
和之一B
将为 NULL。这会导致函数返回false
:
if (!A || !B)
return false;
A
为避免这种情况,您应该将循环更改为在两者B
都为非 NULL时中断:
if (A && B)
break;
此外,循环仅检查count - 1
列表的元素,因此它忽略了最后一个元素:
for (int i = 0; i < listNode->count - 1; i++)
要检查所有元素,您需要将其更改为:
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
将指向 and 节点之后的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;
}
推荐阅读
- python - 无法在 Cloud Dataflow 上的 apache 梁程序中使用来自 beam_utils.sources 的 CsvFileSource
- python - 如何绘制文本文件中的数据?
- python - 自动搜索列表和抓取表
- angular - Angular 多个网站图标取决于环境
- .net - 如何从 openshift docker 镜像中读取文件
- keras - Keras-rl 中的 Keras LSTM 层
- javascript - 从对象数组中获取 2 个值
- vue.js - Vue 组件与其所在的页面交互
- php - SQL WeekOfYear() 在年底停止。备择方案?
- html - 元素的动态 ID