平台网站建设设计,天元建设集团有限公司现状,女装店网站源码,微信公众平台小程序入口上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表#xff1a;链接未来#xff1a;深入理解链表数据结构#xff08;一.c语言实现无头单向非循环链表#xff09;-CSDN博客
那今天接着给大家带来带头双向循环链表的实现#xff1a; 文章目录 一.项目文件规划…上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表链接未来深入理解链表数据结构一.c语言实现无头单向非循环链表-CSDN博客
那今天接着给大家带来带头双向循环链表的实现 文章目录 一.项目文件规划二.基本结构及功能一览(DoubleList.h)结构体定义接口功能一览 三.各功能接口具体实现1.创建节点2.初始化3.打印4.尾插5.尾删6.头插7.头删8.查找9.插入pos前10.删除pos位置11.销毁 四.利用插入和删除改变“两插两删”快速写出链表 一.项目文件规划 头文件DoubleList.h:用来基础准备常量定义typedef链表表的基本框架函数的声明源文件DoubleList.h:用来各种功能函数的具体实现源文件test.c:用来测试功能是否有问题进行基本功能的使用 二.基本结构及功能一览(DoubleList.h)
结构体定义
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//下一个节点struct ListNode* prev;//上一个节点LTDataType val;//数据
}LTNode;接口功能一览
LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印数据void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//在pos前插入
void LTErase(LTNode* pos);//删除posvoid LTDestroy(LTNode* phead);//销毁三.各功能接口具体实现
1.创建节点
因为后面尾插头插插入初始化都要用到创建新节点所以抽出来作为一个函数
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));//动态开辟if (newnode NULL){perror(malloc);return -1;}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}2.初始化
1.第一种返回动态开辟的地址不会销毁
LTNode* LTInit()
{LTNode* a CreateLTNode(-1);a-next a;//一开始一个节点时下一个和上一个都指向自己a-prev a;//return a;
}2.第二种传入二级指针要直接改变头节点的值
void LTInit(LTNode** pphead)
{*pphead CreateLTNode(-1);(*pphead)-next *pphead;(*pphead)-prev *pphead;
}这两种皆可
3.打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;//头结点数据无效不需要打印while (cur ! phead){printf(%d , cur-val);cur cur-next;}printf(\n);
}4.尾插 void LTPushBack(LTNode* phead, LTDataType x)//无有效节点也适用
{assert(phead);LTNode* newnode CreateLTNode(x);LTNode* tail phead-prev;// phead tail newnode 位置展示newnode-next phead;phead-prev newnode;newnode-prev tail;tail-next newnode;
}5.尾删 void LTPopBack(LTNode* phead)//只有一个有效节点也适用
{assert(phead);LTNode* tail phead-prev;LTNode* pretail tail-prev;// phead pretail tail 位置展示free(tail);tail NULL;phead-prev pretail;pretail-next phead;
}6.头插 void LTPushFront(LTNode* phead, LTDataType x)//无有效节点也适用
{assert(phead);LTNode* newnode CreateLTNode(x);//phead newnode firest tail 位置展示newnode-next phead-next;phead-next-prev newnode;newnode-prev phead;phead-next newnode;
}7.头删 void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//只有哨兵位时不能删LTNode* first phead-next;LTNode* second first-next;//phead first second tail 位置展示free(first);first NULL;phead-next second;second-prev phead;
}8.查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);assert(phead-next ! phead);//只有哨兵位时没必要查LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}9.插入pos前
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode CreateLTNode(x);LTNode* pre pos-prev;//pre newnode pos tail 位置展示pre-next newnode;newnode-prev pre;newnode-next pos;pos-prev newnode;
}将前一个节点 pre 的 next 指针指向新节点 newnode将新节点 newnode 的 prev 指针指向前一个节点 pre将新节点 newnode 的 next 指针指向指定节点 pos将指定节点 pos 的 prev 指针指向新节点 newnode 10.删除pos位置 void LTErase(LTNode* pos)
{assert(pos);LTNode* pre pos-prev;LTNode* next pos-next;//pre pos next tail 位置展示pre-next next;next-prev pre;free(pos);pos NULL;
}11.销毁
因为每个节点时malloc动态开辟出来的要把每个节点都依次销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur-next ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
}四.利用插入和删除改变“两插两删”快速写出链表
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);//尾插就是在phead前插入
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTErase(phead-prev);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead-next, x);//头插就是插入到phead的下一个
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTErase(phead-next);
}那这次就先到这里啦两种常见的链表都已经实现完毕接下来大概率是栈和队列了感谢大家支持
