用C语言写一个带注释的双向链表
时间: 2023-07-04 14:31:10 浏览: 69
好的,下面是用C语言写的带注释的双向链表代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node *prev; // 前驱指针
struct Node *next; // 后继指针
} Node;
// 初始化双向链表
Node* initList() {
Node *head = (Node*)malloc(sizeof(Node)); // 创建头结点
head->prev = NULL; // 头结点的前驱指针指向NULL
head->next = NULL; // 头结点的后继指针指向NULL
return head; // 返回头结点
}
// 在双向链表的末尾插入一个节点
void insert(Node *head, int data) {
Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = data; // 设置新节点的数据域
newNode->prev = head->prev; // 设置新节点的前驱指针
newNode->next = head; // 设置新节点的后继指针
head->prev->next = newNode; // 修改前驱节点的后继指针
head->prev = newNode; // 修改头结点的前驱指针
}
// 在双向链表的指定位置插入一个节点
void insertAt(Node *head, int data, int pos) {
Node *p = head->next; // 从第一个节点开始遍历
int i = 1;
while (p != head && i < pos) { // 找到要插入位置的前一个节点
p = p->next;
i++;
}
if (i != pos) { // 如果插入位置不合法,则返回
printf("Error: invalid position.\n");
return;
}
Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
newNode->data = data; // 设置新节点的数据域
newNode->prev = p->prev; // 设置新节点的前驱指针
newNode->next = p; // 设置新节点的后继指针
p->prev->next = newNode; // 修改前驱节点的后继指针
p->prev = newNode; // 修改后继节点的前驱指针
}
// 删除双向链表的指定节点
void delete(Node *head, int data) {
Node *p = head->next; // 从第一个节点开始遍历
while (p != head && p->data != data) { // 找到要删除的节点
p = p->next;
}
if (p == head) { // 如果要删除的节点不存在,则返回
printf("Error: node not found.\n");
return;
}
p->prev->next = p->next; // 修改前驱节点的后继指针
p->next->prev = p->prev; // 修改后继节点的前驱指针
free(p); // 释放要删除的节点的内存空间
}
// 遍历双向链表
void traverse(Node *head) {
Node *p = head->next; // 从第一个节点开始遍历
while (p != head) { // 遍历到尾结点结束
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
Node *head = initList(); // 初始化双向链表
insert(head, 1); // 在双向链表的末尾插入一个节点
insert(head, 2);
insert(head, 3);
traverse(head); // 遍历双向链表
insertAt(head, 4, 2); // 在双向链表的指定位置插入一个节点
traverse(head); // 遍历双向链表
delete(head, 2); // 删除双向链表的指定节点
traverse(head); // 遍历双向链表
return 0;
}
```
希望这份代码能够帮助你理解双向链表的实现原理。