请描述如何在C语言中实现一个双向链表,并给出添加、删除和查找节点的标准函数实现。
时间: 2024-11-22 18:31:00 浏览: 5
双向链表是一种数据结构,其中每个节点都有指向前一个和后一个节点的指针,从而允许双向遍历。在C语言中实现双向链表需要定义一个结构体来表示节点,并提供相应的函数来处理链表。
参考资源链接:[FUNDAMENTALS OF DATA STRUCTURES IN C 部分习题英文答案整理](https://wenku.csdn.net/doc/6412b72abe7fbd1778d49539?spm=1055.2569.3001.10343)
首先,定义双向链表的节点结构体如下:
```c
typedef struct DoublyLinkedListNode {
int data; // 节点存储的数据
struct DoublyLinkedListNode* prev; // 指向前一个节点的指针
struct DoublyLinkedListNode* next; // 指向后一个节点的指针
} DoublyLinkedListNode;
```
接着,实现添加节点的函数。添加节点可以分为在链表尾部添加和在链表中间特定位置添加:
```c
void addNodeAtEnd(DoublyLinkedListNode** head, int data) {
// 创建新节点
DoublyLinkedListNode* newNode = (DoublyLinkedListNode*)malloc(sizeof(DoublyLinkedListNode));
newNode->data = data;
newNode->next = NULL;
newNode->prev = *head;
// 如果链表为空,新节点将成为头节点
if (*head == NULL) {
*head = newNode;
return;
}
// 否则,找到链表的最后一个节点并添加
DoublyLinkedListNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void addNodeAtPosition(DoublyLinkedListNode** head, int data, int position) {
// 先添加到链表尾部
addNodeAtEnd(head, data);
// 再移动到指定位置
for (int i = 0; i < position - 1; i++) {
if ((*head)->prev != NULL) {
*head = (*head)->prev;
}
}
}
```
删除节点的函数实现如下:
```c
void deleteNode(DoublyLinkedListNode** head, int key) {
// 检查链表是否为空
if (*head == NULL) return;
DoublyLinkedListNode* temp = *head;
// 查找要删除的节点
while (temp != NULL && temp->data != key) {
temp = temp->next;
}
// 如果找不到,返回
if (temp == NULL) return;
// 如果节点位于链表中间
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
// 节点是头节点
*head = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
```
最后,实现查找节点的函数:
```c
DoublyLinkedListNode* search(DoublyLinkedListNode* head, int key) {
DoublyLinkedListNode* current = head;
while (current != NULL) {
if (current->data == key) {
return current;
}
current = current->next;
}
return NULL;
}
```
以上提供了双向链表的基本操作的实现,包括添加、删除和查找节点。对于《数据结构基础 (C语言版)》的学习者来说,通过对照这些实现与书中提供的英文习题答案,可以加深对数据结构实践操作的理解,并有效提升编程能力。
参考资源链接:[FUNDAMENTALS OF DATA STRUCTURES IN C 部分习题英文答案整理](https://wenku.csdn.net/doc/6412b72abe7fbd1778d49539?spm=1055.2569.3001.10343)
阅读全文