如何帮客户做网站,短视频代运营方案模板,友情链接大全,温州建站软件一、什么是双链表#xff1f; 双链表#xff0c;顾名思义#xff0c;是一种每个节点都包含两个链接的链表#xff1a;一个指向下一个节点#xff0c;另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比#xff0c;双链表不仅可以…一、什么是双链表 双链表顾名思义是一种每个节点都包含两个链接的链表一个指向下一个节点另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比双链表不仅可以从头节点开始遍历还可以从尾节点开始遍历甚至从中间某个节点开始双向遍历。
二、双链表的特点
双向性每个节点都包含两个指针一个指向前一个节点一个指向后一个节点。这使得双链表在遍历上更加灵活。 动态性链表的大小可以根据需要动态地增加或减少无需预先分配固定大小的内存空间。 三、实现双链表
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;三、实现的功能
LTNode* LTInit();// 初始化双链表
void LTDestroy(LTNode* phead);//销毁
void LTPrint(LTNode* phead);//打印
bool LTEmpty(LTNode* phead);//判断链表是否为空·void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);//指定删除
LTNode* LTFind(LTNode* phead, LTDataType x);//查找 1.创建节点
// 创建新的双链表节点
LTNode* LTBuyNode(LTDataType x) { LTNode* newNode (LTNode*)malloc(sizeof(LTNode)); if (newNode NULL) { perror(malloc fail!); exit(1); } newNode-data x; newNode-next NULL; newNode-prev NULL; return newNode;
} 使用malloc函数在堆上动态地分配内存空间以存储LTNode结构体的大小。 检查malloc是否成功分配了内存。如果返回NULL表示内存分配失败此时调用perror函数打印错误消息并使用exit(1)退出程序。 如果内存分配成功将新节点的数据成员data设置为参数x的值。 初始化新节点的next和prev指针为NULL表示这个新节点在创建时并不指向任何其他的节点。 返回指向新创建节点的指针。 2.初始化
LTNode* LTInit() { LTNode* pheda LTBuyNode(-1); // 使用-1作为哨兵位头节点的数据 pheda-next pheda; // 指向自己表示链表为空 pheda-prev pheda; return pheda;
} 3.双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);// 创建一个新节点newnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;} newnode-prev phead-prev; 将新节点的prev指针设置为当前链表的尾节点。 newnode-next phead; 将新节点的next指针设置为头节点。 phead-prev-next newnode; 更新当前尾节点的next指针使其指向新节点。 phead-prev newnode; 更新头节点的prev指针使其指向新节点 4.双链表的尾删
//尾删
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-prev;del-prev-next phead;phead-prev del-prev;free(del);del NULL;
} prev指针指向链表的最后一个节点 del-prev-next phead; 和 phead-prev del-prev; 这两行代码更新了链表的链接将尾节点从链表中移除。 5.双链表的头插
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode -next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
} newnode -next phead-next;将新节点的next指针指向当前链表的第一个节点 newnode-prev phead;将新节点的prev指针指向链表的头节点 phead-next-prev newnode;更新当前链表第一个节点的prev指针使其指向新节点。 phead-next newnode;更新链表的头节点的next指针使其指向新节点这样新节点就成为了链表的第一个节点。 6.双链表的头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;phead-next del-next;phead-next-prev phead;free(del);del NULL;} LTNode* del phead-next;将待删除的节点的地址赋给del指针。 phead-next del-next;更新链表的头节点的next指针使其跳过待删除的节点直接指向下一个节点。 phead-next-prev phead;由于我们刚刚更新了phead-next现在它指向的是原第一个节点的下一个节点。我们将这个新节点的prev指针更新为指向链表的头节点。 7.双链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d , pcur-data);pcur pcur-next;}printf(\n);
}
8.在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x); newnode- next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
9.指定删除
void LTErase(LTNode* pos)
{assert(pos);assert(pos ! pos-next);pos-prev-next pos-next;// 更新pos的前一个节点的next指针pos-next-prev pos-prev;//更新pos的下一个节点的prev指针free(pos);pos NULL;
} 10.判空
bool LTEmpty(LTNode* phead)
{return phead-next phead;
} 11.销毁
//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead){LTNode* tmp cur;cur cur-next;free(tmp);}free(phead);
}
四、全部源码
LTNode* LTBuyNode(LTDataType x)
{LTNode* Node (LTNode*)malloc(sizeof(LTNode));if (Node NULL){perror(malloc fail!);exit(1);}Node-data x;Node-next NULL; Node-prev NULL; return Node;
}
LTNode* LTInit() {LTNode* pheda LTBuyNode(-1); // 使用-1作为哨兵头节点的数据 pheda-next pheda; // 指向自己表示链表为空 pheda-prev pheda; return pheda;
}//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead){LTNode* tmp cur;cur cur-next;free(tmp);}free(phead);
}
//打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d , pcur-data);pcur pcur-next;}printf(\n);
}
//判断链表是否为空·
bool LTEmpty(LTNode* phead)
{return phead-next phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-prev;del-prev-next phead;phead-prev del-prev;free(del);del NULL;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode -next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;phead-next del-next;phead-next-prev phead;free(del);del NULL;}
//查找LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}curcur-next;}return NULL;
}在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x); newnode- next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}//指定删除
void LTErase(LTNode* pos)
{assert(pos);assert(pos ! pos-next);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}
五、结语
让我们一起在编程的道路上不断前行创造更加美好的未来
