郴州seo优化公司,伊宁网站建设优化,免费软件大全,网站推广方法汇总目录 1.双链表的定义 2.双链表的创建和初始化 3.双链表的插入节点操作 4.双链表的删除节点操作 5.双链表的查找节点操作 6.双链表的更新节点操作 7.完整代码 #x1f308;嗨#xff01;我是Filotimo__#x1f308;。很高兴与大家相识#xff0c;希望我的博客能对你有所帮助… 目录 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;
}
输出结果如下
