用C语言写一个双向链表
时间: 2023-12-29 10:50:16 浏览: 70
以下是一个双向链表的基本实现,包含节点的插入、删除、遍历等操作:
```
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *prev;
struct node *next;
};
struct node *head = NULL;
void insert(int value) {
struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = value;
new_node->prev = NULL;
new_node->next = head;
if (head != NULL) {
head->prev = new_node;
}
head = new_node;
}
void delete(int value) {
struct node *current = head;
while (current != NULL && current->data != value) {
current = current->next;
}
if (current == NULL) {
return;
}
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
}
void traverse() {
struct node *current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
insert(3);
insert(5);
insert(7);
insert(9);
traverse();
delete(5);
traverse();
delete(9);
traverse();
return 0;
}
```
在这个实现中,我们使用了一个结构体 `node` 来表示链表的节点。每个节点包含一个整数值 `data`,以及两个指针 `prev` 和 `next`,分别指向前一个节点和后一个节点。初始时,我们设置 `head` 为 `NULL`,表示链表为空。
在 `insert` 函数中,我们首先创建一个新节点,并将它的 `data` 值设置为传入的参数。然后,我们将新节点的 `prev` 指针设置为 `NULL`,因为新节点是链表的头节点。接着,我们将新节点的 `next` 指针设置为原来的头节点,并将头节点的 `prev` 指针设置为新节点,这样就完成了节点的插入操作。
在 `delete` 函数中,我们首先遍历链表,找到节点的值等于传入参数的节点,如果找到了,我们就将它的前驱节点的 `next` 指针指向它的后继节点,将它的后继节点的 `prev` 指针指向它的前驱节点,这样就完成了节点的删除操作。
在 `traverse` 函数中,我们遍历整个链表,依次输出每个节点的 `data` 值。
在 `main` 函数中,我们插入了四个节点,并调用 `traverse` 函数输出整个链表。然后,我们删除了值为 5 和 9 的节点,并再次调用 `traverse` 函数输出剩余的节点。最后,程序返回 0,表示正常结束。
阅读全文