根据双链表的知识,设计一个算法(函数),将双链表L(至少包含两个数据节点)中的所有结点逆置,在main函数中调用该算法,测试算法的准确性。(用数据结构与算法和c语言的知识解决)
时间: 2024-10-17 21:06:42 浏览: 22
删除结点x:-数据结构基础
在C语言中,我们可以使用迭代的方式来设计一个函数来逆置双链表。首先,我们需要定义一个链表节点的结构体,然后创建一个辅助指针以及前驱和后继指针。下面是具体的步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// 逆置链表函数
void reverseList(Node** head) {
Node* current = *head;
Node* temp = NULL; // 辅助指针
while (current != NULL) {
temp = current->prev; // 将当前节点的前驱保存到临时变量
current->prev = current->next; // 更新当前节点的前驱
current->next = temp; // 更新当前节点的后继
current = current->prev; // 移动到下一个节点
}
// 如果原头节点没有改变,则需要将其作为新的头节点
if (temp != NULL) {
*head = temp->prev;
}
}
// 测试逆置功能
int main() {
// 创建示例链表
Node* listHead = createNode(1);
listHead->prev = NULL;
listHead->next = createNode(2);
listHead->next->prev = listHead;
listHead->next->next = createNode(3);
listHead->next->next->prev = listHead->next;
// 输出原始链表
printf("Original List: ");
printList(listHead);
// 逆置链表
reverseList(&listHead);
// 输出逆置后的链表
printf("\nReversed List: ");
printList(listHead);
return 0;
}
// 打印链表函数
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
```
在这个程序中,`reverseList()` 函数通过不断地交换节点的前驱和后继指针来完成链表的逆置,最后更新头节点指向新头(原尾)。在`main()` 中,我们首先创建了一个简单的双向链表,并调用了这个逆置函数来验证其效果。
阅读全文