目录
1.双链表的定义
2.双链表的创建和初始化
3.双链表的插入节点操作
4.双链表的删除节点操作
5.双链表的查找节点操作
6.双链表的更新节点操作
7.完整代码
🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。
💡本文由Filotimo__✍️原创,首发于CSDN📚。
📣如需转载,请事先与我联系以获得授权⚠️。
🎁欢迎大家给我点赞👍、收藏⭐️,并在留言区📝与我互动,这些都是我前进的动力!
🌟我的格言:森林草木都有自己认为对的角度🌟。
1.双链表的定义
双链表是一种常见的数据结构,它由一系列节点组成,每个节点包含两个指针,一个指向前一个节点,另一个指向后一个节点。与单链表不同的是,双链表的节点可以双向访问,因此可以在任意位置快速插入、删除和查找元素。
一个双链表通常包含以下属性和操作:
头节点(head):指向第一个节点的指针。
尾节点(tail):指向最后一个节点的指针。
节点(node):包含数据和两个指针的数据单元。
插入(insert):在指定位置插入一个新的节点。
删除(delete):删除指定位置的节点。
查找(search):根据给定的值查找节点。
遍历(traverse):按顺序访问链表中的每个节点。
2.双链表的创建和初始化
创建一个双链表需要定义一个结构体,包含数据域和前后指针域。初始化时要注意将头结点的前后指针均指向 NULL。
struct DNode {
int data; //数据域
struct DNode *prior; //前驱指针域
struct DNode *next; //后继指针域
};
struct DNode *createList() {
struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
head->prior = NULL;
head->next = NULL;
return head;
}
定义结构体struct DNode表示双向链表的节点。
该节点包括三个成员变量:
int data表示节点的数据域,可以存储整数类型的数据。
struct DNode *prior表示指向前一个节点的指针域。
struct DNode *next表示指向后一个节点的指针域。
在createList函数内部,首先通过malloc函数动态分配了一块内存,大小为一个struct DNode结构体的大小。然后将分配的内存强制转换为struct DNode*类型,并将其赋值给head指针变量,作为链表的头节点。
3.双链表的插入节点操作
在插入节点时,需要将新节点插入到某个节点之前或之后,通过修改前后指针实现。具体操作分为两步,先将新节点的前后指针赋值,然后修改它前后节点的指针。需要注意判断特殊情况,如插入到空链表、插入到头结点等。
void insertNode(struct DNode *p, int data) {
if (p == NULL) return;
struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
newNode->data = data;
newNode->prior = p;
newNode->next = p->next;
if (p->next != NULL) p->next->prior = newNode;
p->next = newNode;
}
函数insertNode接受两个参数:指向双向链表结点的指针p和要插入的数据data。
如果p不为空,则创建一个新的双向链表结点newNode,通过malloc函数动态分配内存。然后,将新节点的data字段设置为传入的data值。再将新节点的prior字段设置为指向p,将新节点的next字段设置为指向p->next。
检查p的下一个结点是否为空,如果不为空,则将下一个结点的prior字段指向新节点newNode。最后将p的next指针指向新结点newNode,完成插入操作。这样,插入操作就将新节点插入到了链表中p结点之后的位置。
4.双链表的删除节点操作
在删除节点时,需先找到要删除的节点,然后修改前后节点的指针。在执行 free 操作后,需要将指针置为 NULL,避免出现野指针。
void deleteNode(struct DNode *p) {
if (p == NULL) return;
p->prior->next = p->next;
if (p->next != NULL) p->next->prior = p->prior;
free(p);
p = NULL;
}
如果p不为空,将p结点的前驱结点的next指针指向p结点的后继结点,断开p结点与前后结点的连接。即p->prior->next = p->next。
检查p结点的后继结点是否为空,如果不为空,则将后继结点的前驱指针指向p结点的前驱结点,断开p结点与后继结点的连接。即p->next->prior = p->prior。
使用free函数释放了指针p指向的内存,将p结点从链表中删除。
将指针p设置为NULL,确保不再引用已经删除的结点。
5.双链表的查找节点操作
查找节点时,可以采用遍历的方法进行查找。需要注意判断特殊情况,如链表为空等。
struct DNode *findNode(struct DNode *head, int data) {
if (head == NULL) return NULL;
struct DNode *p = head->next;
while (p != NULL) {
if (p->data == data) return p;
p = p->next;
}
return NULL;
}
如果head不为空,代码将p指针初始化为head结点的下一个结点,即head->next。
使用while循环遍历链表,如果指针p指向的结点的data字段等于要查找的数据data,则直接返回该结点的指针p,表示查找成功。
如果没有查找到要找的数据,即p到达链表结尾指针为NULL,则返回NULL,表示查找失败。
6.双链表的更新节点操作
更新节点操作与单链表类似,具体步骤为先查找要更新的节点,然后修改其数据域的值即可。
void updateNode(struct DNode *p, int newData) {
if (p != NULL) {
p->data = newData;
}
}
首先检查指针p是否为空,如果不为空,则将指针p所指向的结点的data字段更新为新的数据newData。如果结点p为空,则不进行任何操作。
7.完整代码
#include <stdio.h>
#include <stdlib.h>
//双链表结构体定义
struct DNode {
int data; //数据域
struct DNode *prior; //前驱指针域
struct DNode *next; //后继指针域
};
//创建双链表
struct DNode *createList() {
struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
head->prior = NULL;
head->next = NULL;
return head;
}
//插入节点
void insertNode(struct DNode *p, int data) {
if (p == NULL) return;
struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
newNode->data = data;
newNode->prior = p;
newNode->next = p->next;
if (p->next != NULL) p->next->prior = newNode;
p->next = newNode;
}
//删除节点
void deleteNode(struct DNode *p) {
if (p == NULL) return;
p->prior->next = p->next;
if (p->next != NULL) p->next->prior = p->prior;
free(p);
p = NULL;
}
//查找节点
struct DNode *findNode(struct DNode *head, int data) {
if (head == NULL) return NULL;
struct DNode *p = head->next;
while (p != NULL) {
if (p->data == data) return p;
p = p->next;
}
return NULL;
}
//更新节点
void updateNode(struct DNode *p, int newData) {
if (p != NULL) {
p->data = newData;
}
}
//遍历双链表
void traverseList(struct DNode *head) {
if (head == NULL) return;
struct DNode *p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//测试双链表
int main() {
struct DNode *head = createList(); //创建链表
//插入节点
insertNode(head, 1);
insertNode(head, 2);
insertNode(head, 3);
insertNode(head, 4);
traverseList(head); //遍历链表
struct DNode *p = findNode(head, 2); //查找节点
if (p != NULL) {
printf("Found node: %d\n", p->data);
updateNode(p, 5); //更新节点
printf("After updated, the list is:\n");
traverseList(head); //遍历链表
}
deleteNode(findNode(head, 3)); //删除节点
printf("After deleted, the list is:\n");
traverseList(head); //遍历链表
return 0;
}
输出结果如下:文章来源:https://www.toymoban.com/news/detail-778104.html
文章来源地址https://www.toymoban.com/news/detail-778104.html
到了这里,关于【数据结构】双链表的定义和操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!