双向链表的定义与基本操作
双向链表操作实现双向链表
双向链表（Doubly Linked List）是一种链式数据结构，其中的每个节点不仅指向下一个节点，还指向前一个节点。这与单向链表不同，后者每个节点只包含到下一个节点的引用。双向链表因此允许在两个方向上遍历：向前和向后。
每个节点在双向链表中通常包含三部分：
[*]指向前一个节点的引用（或指针）。
[*]存储的数据元素。
[*]指向下一个节点的引用（或指针）。
双向链表的优点包括：
[*]可以从任意一个节点出发，既能够向前访问也能够向后访问，增加了灵活性。
[*]在已知节点位置的情况下，插入和删除操作可以高效地进行，因为只需要改变相应节点的前驱和后继的指针即可。
缺点是由于每个节点需要额外存储指向前一个节点的指针，因此相比单向链表会占用更多的内存空间。
代码实现
双向链表的创建、插入、删除、查找等常用操作。
#include <stdio.h> // 标准输入输出库，用于 printf 等函数
#include <stdbool.h> // 布尔类型库，提供 bool、true、false
#include <stdlib.h> // 标准库，提供 malloc/calloc/free 和 exit 等函数
//定义链表中数据域的类型为 int
typedef int DataType_t;
//定义双向链表的结点结构体
typedef struct DoubleLinkedList
{
DataType_t data; //结点的数据域
struct DoubleLinkedList *prev; //直接前驱的指针域
struct DoubleLinkedList *next; //直接后继的指针域
}DoubleLList_t;
//创建头结点：初始化一个空的双向链表
DoubleLList_t* DoubleLList_Create(void)
{
// 为头结点动态分配内存，并初始化为 0（calloc 会清零）
DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
// 如果内存分配失败，打印错误信息并退出程序
if(Head == NULL){
perror("Calloc memory for the Head is failed!\n");
exit(-1);
}
Head->next = NULL;
Head->prev = NULL;
return Head;
}
//创建一个新结点（仅数据域赋值，指针域初始化为 NULL）
DoubleLList_t* DoubleLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域（2个）进行初始化
New->data = data;
New->prev = NULL;
New->next = NULL;
return New;
}
// 头插法：在链表头部（第一个有效结点位置）插入新元素
bool DbleLList_HeadInsert(DoubleLList_t* Head,DataType_t data)
{
// 创建新结点
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL){
return false;
}
// 若为空，新结点直接作为第一个有效结点
if(Head->next == NULL){
Head->next = New;
}
else{// 否则，将新结点插入到首结点之前
New->next = Head->next;
Head->next->prev = New;
Head->next = New;
}
return true;// 插入成功
}
// 尾插法：在链表尾部插入新元素
bool DbleLList_TailInsert(DoubleLList_t* Head,DataType_t data)
{
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL) {
return false;
}
//如果只有头结点，New直接成为首结点
if(Head->next == NULL){//如果只有头结点，New直接成为首结点
Head->next = New;
}
else{// 否则，从首结点开始遍历，寻找最后一个结点
DoubleLList_t *Find_Tail = Head->next;
while(Find_Tail->next != NULL){
Find_Tail = Find_Tail->next;
}
// 找到尾结点后，将新结点连接在其后
Find_Tail->next = New;
New->prev = Find_Tail;
}
return true;
}
//指定在链表中某个结点后插入一个新结点
bool DbleLList_DestInsert_l(DoubleLList_t* Head,DataType_t dest,DataType_t data)
{
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL) {
return false;
}
if(Head->next == NULL){//如果只有头结点，New直接成为首结点
Head->next = New;
}
DoubleLList_t *Find_Dest = Head->next;
//遍历链表，找到数据域data等于目标值dest的结点
while(Find_Dest->data != dest){
if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
printf("无效指定结点位置\n");
return false;
}
Find_Dest = Find_Dest->next;
}
if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，数据域data等于dest，新结点New成为尾结点
Find_Dest->next = New;
New->prev = Find_Dest;
}
else{
New->next = Find_Dest->next;
Find_Dest->next->prev = New;
New->prev = Find_Dest;
Find_Dest->next = New;
}
return true;
}
//指定在链表中某个结点前插入一个新结点
bool DbleLList_DestInsert_f(DoubleLList_t *Head,DataType_t dest,DataType_t data)
{
DoubleLList_t *New = DoubleLList_NewNode(data);
if (New == NULL) {
return false;
}
if(Head->next == NULL){//如果只有头结点，New直接成为首结点
Head->next = New;
}
DoubleLList_t *Find_Dest = Head->next;
//遍历链表，找到数据域data等于目标值dest的结点
while(Find_Dest->data != dest){
if (Find_Dest->next == NULL){//若遍历到链表最后一个结点，data和dest还不相等，说明dest为无效指定结点位置
printf("无效指定结点位置\n");
return false;
}
Find_Dest = Find_Dest->next;
}
//1.首结点是目标结点
if(Find_Dest == Head->next){
New->next = Head->next;
Head->next->prev = New;
Head->next = New;
}
else{
New->prev = Find_Dest->prev;
Find_Dest->prev->next =New;
New->next = Find_Dest;
Find_Dest->prev = New;
}
return true;
}
//遍历链表并输出所有结点的data值
bool DbleLList_Print(DoubleLList_t *Head)
{
DoubleLList_t *Phead = Head;
if(Head->next == NULL){
printf("current DoubleLList is empty!\n");
return false;
}
printf("链表内容: ");
while(Phead->next){
Phead = Phead->next;
printf("%d ",Phead->data);
if(Phead->next == NULL){
break;
}
}
printf("\n");
return true;
}
//删除链表头结点
bool DbleLList_HeadDel(DoubleLList_t *Head)
{
DoubleLList_t *Temp= Head->next;
//if链表只有一个头结点
if(Head->next == NULL){
printf("current DoubleLList is empty!\n");
return false;
}
//if当前链表只有一个首结点
if(Temp->next == NULL){
Head->next = NULL;
free(Temp);
return true;
}
//新的首结点pre指向NULL不指向Head
Temp->next->prev = NULL;
//头结点next指向要删除结点的next
Head->next = Temp->next;
free(Temp);
return true;
}
//指定位置删除链表结点
bool DbleLList_del_dest(DoubleLList_t* Head,DataType_t dest)
{
if(Head->next == Head){
printf("current DoubleLList is empty!\n");
return false;
}
DoubleLList_t *Find_Dest = Head->next;
while(Find_Dest->data != dest){
if (Find_Dest->next == NULL){//若遍历到链表最后一个结点
printf("未找到指定节点\n");
return false;
}
Find_Dest = Find_Dest->next;
}
if (Head->next == Find_Dest){//若目标结点是链表第一个结点
if(Find_Dest->next = NULL){//若目标结点还是是链表唯一结点
Head->next = NULL;
}
else{
Find_Dest->next->prev = NULL;
Head->next = Find_Dest->next;
}
}
else{//若目标结点是链表最后一个结点
if(Find_Dest->next == NULL){
Find_Dest->prev->next = NULL;
}
else{//若目标结点有前驱后继
Find_Dest->prev->next = Find_Dest->next;
Find_Dest->next->prev = Find_Dest->prev;
}
}
free(Find_Dest);
return true;
}主函数测试
int main(int argc, char const *argv[])
{
// 创建双向链表
DoubleLList_t *Head = DoubleLList_Create();
printf("1. 创建双向链表完成\n");
DbleLList_Print(Head);
// 测试头插法
printf("\n2. 测试头插法插入 10, 20, 30\n");
DbleLList_HeadInsert(Head, 10);
DbleLList_HeadInsert(Head, 20);
DbleLList_HeadInsert(Head, 30);
DbleLList_Print(Head); // 预期结果: 30 20 10
// 测试尾插法
printf("\n3. 测试尾插法插入 40, 50\n");
DbleLList_TailInsert(Head, 40);
DbleLList_TailInsert(Head, 50);
DbleLList_Print(Head); // 预期结果: 30 20 10 40 50
// 测试指定节点后插入
printf("\n4. 测试在20后插入25\n");
DbleLList_DestInsert_l(Head, 20, 25);
DbleLList_Print(Head); // 预期结果: 30 20 25 10 40 50
// 测试指定节点前插入
printf("\n5. 测试在40前插入35\n");
DbleLList_DestInsert_f(Head, 40, 35);
DbleLList_Print(Head); // 预期结果: 30 20 25 10 35 40 50
// 测试删除头节点
printf("\n6. 测试删除头节点\n");
DbleLList_HeadDel(Head);
DbleLList_Print(Head); // 预期结果: 20 25 10 35 40 50
// 测试删除指定节点
printf("\n7. 测试删除节点10\n");
DbleLList_del_dest(Head, 10);
DbleLList_Print(Head); // 预期结果: 20 25 35 40 50
// 测试删除尾节点
printf("\n8. 测试删除尾节点(50)\n");
DbleLList_del_dest(Head, 50);
DbleLList_Print(Head); // 预期结果: 20 25 35 40
// 测试删除中间节点
printf("\n9. 测试删除中间节点(25)\n");
DbleLList_del_dest(Head, 25);
DbleLList_Print(Head); // 预期结果: 20 35 40
// 测试删除所有节点
printf("\n10. 测试删除所有节点\n");
DbleLList_HeadDel(Head);
DbleLList_HeadDel(Head);
DbleLList_HeadDel(Head);
DbleLList_Print(Head); // 预期结果: 空链表
// 释放头节点
free(Head);
Head = NULL;
printf("\n11. 释放链表完成\n");
return 0;
}测试结果
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]