网站建设需要了解的信息,电商培训基地,建站网站 国外,珠海网站制作平台这篇博客将介绍带头循环的双向链表#xff0c;实现链表的头部插入/删除#xff0c;尾部插入/删除#xff0c;查找#xff0c;以及任意位置的插入删除。
1.结构
带头循环的双向链表的结构如下图所示#xff0c;一个结点内部包含数据#xff0c;以及分别指向前一个以及后…这篇博客将介绍带头循环的双向链表实现链表的头部插入/删除尾部插入/删除查找以及任意位置的插入删除。
1.结构
带头循环的双向链表的结构如下图所示一个结点内部包含数据以及分别指向前一个以及后一个地址的指针由此构成了双向且头结点可指向最后一个结点同样的最后的一个结点最终指向头结点由此构成了循环。且头结点作为哨兵位不存储数据。 2. 链表的定义以及初始化
我们在此处定义结构体包含数值分别指向前后结点的结构体指针
typedef int LTDataType;typedef struct SListNode
{LTDataType data;struct SListNode* next;struct SListNode* prev;}LTNode;
关于链表的初始化先创建一个结点再完成对链表的初始化。
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;//初始化newnode-prev NULL;return newnode;
}LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
}
LTNode* plist LTInit(); 3. 链表的头插与尾插
链表的头插与尾插在此处则比单链表简单许多只需要完成四个指针的指向即可示意图与代码如下且当链表只存在一个头结点时方法仍然相同无需额外讨论。 void LTPushFront(LTNode* phead, LTDataType x)//头插
{assert(phead);LTNode* newnode BuyLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
}
void LTPushBack(LTNode* phead, LTDataType x)//尾插
{assert(phead);LTNode* newnode BuyLTNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;} 4. 链表的头删与尾删
链表的头删与尾删在此非常简单只需改变指针指向即可示意图如下所示 void LTPopFront(LTNode* phead) //头删
{assert(phead);assert(!LTEmpty(phead));LTNode* Fir phead-next;LTNode* FirNext Fir-next;free(Fir);phead-next FirNext;FirNext-prev phead;
}
void LTPopBack(LTNode* phead) //尾删
{assert(phead);assert(!LTEmpty(phead));LTNode* tail phead-prev;LTNode* tailprev tail-prev;free(tail);tailprev-next phead;phead-prev tailprev;
}
在此处为了避免当链表只剩下哨兵位仍然删除结点为此 我们增加了链表判空函数代码如下
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
} 5. 链表的查找
链表中数据的查找只需要遍历一遍链表即可由于是循环链表当回到头结点时即完成了一遍的遍历。代码如下
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
6. 链表的任意位置插入
链表的任意位置插入与头插尾插类似代码如下
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyLTNode(x);LTNode* prev pos-prev;prev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}
因此我们可以改写我们的头插与尾插
LTInsert(phead-next, x);//头插
LTInsert(phead, x);//尾插
7. 链表的删除任意位置结点
同样的链表删除任意位置的结点与头删和尾删类似代码如下
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);
} 因此我们可以改写我们的头删与尾删
LTErase(phead);//头删
LTErase(phead-next);//尾删8. 链表的打印与销毁
打印链表方便我们观察链表的数据最后销毁链表防止内存泄漏代码如下
void LTPrint(LTNode* phead)
{assert(phead);printf(guard);LTNode* cur phead-next;while (cur ! phead){printf(%d,cur-data);cur cur-next;}printf(\n);
}
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
} 9 .结果
int main()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//尾插 1 2 3 4LTPushFront(plist, 5);LTPushFront(plist, 6);LTPushFront(plist, 7);LTPushFront(plist, 8);LTPrint(plist);//头插 8 7 6 5LTPopFront(plist);LTPopFront(plist);LTPrint(plist);//头删 8 7LTPopBack(plist);LTPopBack(plist);LTPrint(plist);//头删 3 4LTNode* pos LTFind(plist, 5);LTInsert(pos, 50);LTPrint(plist);//在 5 之前插入50LTErase(pos);LTPrint(plist);//删除 5LTDestroy(plist);//链表销毁plist NULL;return 0;
}
