帮我用C语言写一个单链表,要求能实现单链表的基本操作且附带注释
时间: 2024-05-06 21:21:38 浏览: 95
好的,您可以参考下面的代码实现单链表,每一个部分都有注释说明:
```
#include <stdio.h>
#include <stdlib.h>
// 单链表结构体
typedef struct ListNode {
int val; // 节点值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
// 初始化一个空的单链表
void initList(ListNode** head) {
*head = NULL; // 头节点指针设为NULL,代表空链表
}
// 在单链表末尾添加一个节点
void addNode(ListNode** head, int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 新建一个节点
newNode->val = val; // 节点值设置为输入的值
newNode->next = NULL; // 新节点后面没有节点了,所以指针为NULL
if (*head == NULL) { // 如果是空链表,头节点就指向新节点
*head = newNode;
return;
}
ListNode* p = *head;
while (p->next != NULL) { // 遍历查找链尾
p = p->next;
}
p->next = newNode; // 在链尾插入新节点
}
// 在单链表任意位置插入一个节点
void insertNode(ListNode** head, int pos, int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 新建一个节点
newNode->val = val; // 节点值设置为输入的值
newNode->next = NULL;
if (pos == 1) { // 如果在链表头插入新节点
newNode->next = *head;
*head = newNode;
return;
}
ListNode* p = *head;
int i = 1;
while (i < pos - 1 && p != NULL) { // 遍历查找插入位置的前一个节点
p = p->next;
i++;
}
if (p == NULL) { // 如果插入位置超过了链表长度,则不插入
return;
}
newNode->next = p->next; // 在插入位置插入新节点
p->next = newNode;
}
// 删除单链表中第一个值等于val的节点
void deleteNode(ListNode** head, int val) {
ListNode* p = *head;
ListNode* pre = NULL; // 定义前驱节点指针
while (p != NULL && p->val != val) { // 遍历查找所需删除的节点
pre = p;
p = p->next;
}
if (p == NULL) { // 如果未找到所需删除的节点,则不删除
return;
}
if (pre == NULL) { // 如果需要删除的节点是头节点,则头节点指针指向下一个节点
*head = (*head)->next;
} else {
pre->next = p->next; // 将前驱节点的next指针指向删除节点的next指针
}
free(p); // 释放删除节点的空间
}
// 查找单链表中第一个值等于val的节点,返回该节点的位置
int findNode(ListNode* head, int val) {
ListNode* p = head;
int pos = 1; // 定义节点位置变量
while (p != NULL && p->val != val) { // 遍历查找节点
p = p->next;
pos++;
}
if (p == NULL) { // 如果未找到节点,则返回0
return 0;
} else {
return pos; // 返回节点位置
}
}
// 输出单链表
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) { // 遍历输出每个节点的值
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main() {
ListNode* head;
initList(&head); // 初始化一个空链表
addNode(&head, 1); // 在链表末尾添加节点
addNode(&head, 2);
addNode(&head, 3);
insertNode(&head, 2, 4); // 在指定位置插入节点
deleteNode(&head, 2); // 删除节点
int pos = findNode(head, 4); // 查找节点位置
if (pos != 0) {
printf("The position of the node is %d\n", pos);
} else {
printf("The node is not found\n");
}
printList(head); // 输出链表
return 0;
}
```
以上就是一个用C语言实现的单链表,附带有详细注释,希望能够对您有所帮助。
阅读全文