数据结构-双向链表
单向链表只能找它的直接后继，而不能找到直接前驱，而双向链表不仅能找到直接后继，而且也能找到直接前驱/*******************************************************************************
*
*
* 设计双向链表的接口
* author：jindouliu2024@163.com
* date：2025.3.29
*
*
* Copyright (c)2024-2025 jindouliu2024@163.com All right Reserved
* *******************************************************************************/配置双向链表的头首节点
typedef struct DoubleLinkedList
{
DataType_t data; //结点的数据域
struct DoubleLinkedList *prev; //直接前驱的指针域
struct DoubleLinkedList *next; //直接后继的指针域
}DoubleLList_t;创建一个空的链表
//创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
DoubleLList_t * DoubleLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
Head->prev = NULL;
Head->next = NULL;
//3.把头结点的地址返回即可
return Head;
}创建一个新的结点
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 DoubleLList_HeadInsert(DoubleLList_t * Head,DataType_t data)
{
//创建新结点
DoubleLList_t * New= DoubleLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("HeadInsert create new node failed\n ");
return false;
}
//判断链表是否为空
if(Head->next == NULL){
Head->next = New;
return true;
}
New->next = Head->next;
Head->next->prev = New;
Head->next = New;
return true;
}尾插结点
bool DoubleLList_TailInsert(DoubleLList_t * Head,DataType_t data)
{
DoubleLList_t * Phead = Head;
//创建新结点
DoubleLList_t * New= DoubleLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("HeadInsert create new node failed\n ");
return false;
}
//判断链表是否为空
if(Head->next == NULL){
Head->next = New;
return true;
}
//遍历找到尾结点
while(Phead->next != NULL){
Phead = Phead->next;
}
Phead->next = New;
New->prev = Phead;
return true;
}指定目标结点后边插入
bool DoubleLList_DestInsert(DoubleLList_t * Head,DataType_t destval,DataType_t data)
{
DoubleLList_t * Phead = Head->next;
//创建新结点
DoubleLList_t * New= DoubleLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("HeadInsert create new node failed\n ");
return false;
}
//判断链表是否为空
if(Head->next == NULL){
Head->next = New;
return true;
}
//循环找到目标结点
while(Phead->next != NULL && Phead->data != destval){
Phead = Phead->next;
}
//如果目标不是尾结点
if(Phead->next == NULL && Phead->data != destval){
printf("do not find destval\n");
return false;
}
//如果目标是尾结点
if(Phead->next == NULL && Phead->data == destval){
Phead->next = New;
New->prev = Phead;
}
else{
New->next = Phead->next;
Phead->next->prev = New;
New->prev = Phead;
Phead->next = New;
}
return true;
}头删结点
bool DoubleLList_HeadDel(DoubleLList_t * Head)
{
DoubleLList_t * Phead = Head->next;
//判断链表是否为空
if(Head->next == NULL){
printf("this is empty list,do not delete head\n");
return false;
}
Head->next = Phead->next;
Phead->next = NULL;
Head->next->prev = NULL;
free(Phead);
return true;
}尾删结点
bool DoubleLList_TailDel(DoubleLList_t * Head)
{
DoubleLList_t * Phead = Head->next;
//判断链表是否为空
if(Head->next == NULL){
printf("this is empty list,do not delete head\n");
return false;
}
//遍历找到尾结点
while(Phead->next != NULL){
Phead = Phead->next;
}
Phead->prev->next = NULL;
Phead->prev = NULL;
free(Phead);
return true;
}指定目标结点删除
bool DoubleLList_DestDel(DoubleLList_t * Head,DataType_t destval)
{
DoubleLList_t * Phead = Head->next;
//判断链表是否为空
if(Head->next == NULL){
printf("this is empty list,do not delete head\n");
return false;
}
//循环遍历查找目标元素
while(Phead->next != NULL && Phead->data != destval){
Phead = Phead->next;
}
//查找到链表尾部，还没有找到destval，则直接退出
if(Phead->next == NULL && Phead->data != destval){
printf("can not find this destval,do not delete\n");
return false;
}
//只有头结点和首节点
if(Head->next->next == NULL && Head->next->data == destval)
{
Head->next = NULL;
Phead->prev = NULL;
free(Phead);
}
//最后一个结点是目标结点
else if(Phead->next == NULL && Phead->data == destval){
Phead->prev->next = NULL;
Phead->prev = NULL;
free(Phead);
//return true;
}
//目标结点在首结点
else if(Head->next == Phead){
Head->next = Phead->next;
Phead->next = NULL;
Head->next->prev = NULL;
free(Phead);
//return true;
}
//目标结点不在首尾结点
else{
Phead->prev->next = Phead->next;
Phead->next->prev = Phead->prev;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
// Phead->prev->next = Phead->next;
// Phead->next->prev = Phead->prev;
// Phead->next = NULL;
// Phead->prev = NULL;
// free(Phead);
return true;
}循环打印
bool DoubleLList_Print(DoubleLList_t * Head)
{
DoubleLList_t * Phead = Head;
//判断链表是否为空
if(Head->next == NULL){
printf("this is empty DoubleList\n");
return false;
}
//循环遍历链表
while(Phead != NULL){
Phead = Phead->next;
printf("data = %d\n",Phead->data);
if(Phead->next == NULL){
break;
}
}
return true;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]