将一个带头结点的数据域依次为 a1,a2,...,an(n≥3)的单链表的所有结点逆置,即第一个 结点的数据域变为 an,...,最后一个结点的数据域为 a1。c语言编程实现以上功能要求。加上注释
时间: 2024-03-10 15:49:49 浏览: 51
带头结点的单链表的c算法实现
以下是实现此功能的C语言代码,已加上注释:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node { // 定义链表节点结构体
int data; // 节点数据
struct node *next; // 指向下一个节点的指针
} Node, *LinkedList; // 定义节点类型和链表类型
LinkedList createList(int n) { // 创建链表函数
LinkedList head = (LinkedList)malloc(sizeof(Node)); // 创建头节点
head->next = NULL; // 头节点的next指针指向NULL
LinkedList p = head; // 定义指针p指向头节点
int i;
for (i = 1; i <= n; i++) { // 循环创建n个节点
LinkedList newNode = (LinkedList)malloc(sizeof(Node)); // 创建新节点
newNode->data = i; // 新节点的数据为i
newNode->next = NULL; // 新节点的next指针指向NULL
p->next = newNode; // 指针p的next指针指向新节点
p = p->next; // 指针p指向下一个节点
}
return head; // 返回头节点
}
void printList(LinkedList head) { // 打印链表函数
LinkedList p = head->next; // 定义指针p指向第一个节点
while (p != NULL) { // 循环遍历链表
printf("%d ", p->data); // 打印节点数据
p = p->next; // 指针p指向下一个节点
}
printf("\n"); // 换行
}
void reverseList(LinkedList head) { // 链表逆置函数
if (head == NULL || head->next == NULL || head->next->next == NULL) { // 如果链表为空或只有一个节点或只有两个节点,则不需要逆置
return;
}
LinkedList p = head->next; // 定义指针p指向第一个节点
LinkedList q = p->next; // 定义指针q指向第二个节点
p->next = NULL; // 第一个节点的next指针指向NULL
while (q != NULL) { // 循环遍历链表
LinkedList temp = q->next; // 定义临时指针temp指向下一个节点
q->next = p; // 第二个节点的next指针指向第一个节点
p = q; // 指针p指向第二个节点
q = temp; // 指针q指向下一个节点
}
head->next = p; // 头节点的next指针指向逆置后的第一个节点
}
int main() {
LinkedList list = createList(5); // 创建长度为5的链表
printf("Original list: ");
printList(list); // 打印原始链表
reverseList(list); // 将链表逆置
printf("Reversed list: ");
printList(list); // 打印逆置后的链表
return 0;
}
```
在代码中,我们对每个函数和操作都添加了注释,以方便理解。
阅读全文