目录一、本章重点二、带头双向循环链表介绍2.1什么是带头双向循环链表?2.2最常用的两种链表结构三、带头双向循环链表常用接口实现 3.1结构体创建3.2带头双向循环链表的初始化 3.
图解
typedef int DataType;
typedef struct DListnode
{
DataType data;
DListNode* prev;
DListNode* next;
}DListNode;
void DListInint(DListNode** pphead)
{
*pphead = (DListNode*)malloc(sizeof(DListNode));
(*pphead)->next = (*pphead);
(*pphead)->prev = (*pphead);
}
或者使用返回节点的方法也能实现初始化
DListNode* DListInit()
{
DListNode* phead = (DListNode*)malloc(sizeof(DListNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
DListNode* BuyDListNode(DataType x)
{
DListNode* temp = (DListNode*)malloc(sizeof(DListNode));
if (temp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
temp->prev = NULL;
temp->next = NULL;
temp->data = x;
return temp;
}
void DListPushBack(DListNode* phead,DataType x)
{
DListNode* newnode = BuyDListNode(x);
DListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void DListNodePrint(DListNode* phead)
{
DListNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void DListNodePushFront(DListNode* phead, DataType x)
{
DListNode* next = phead->next;
DListNode* newnode = BuyDListNode(x);
next->prev = newnode;
newnode->next = next;
newnode->prev = phead;
phead->next = newnode;
}
void DListNodePopBack(DListNode* phead)
{
if (phead->next == phead)
{
return;
}
DListNode* tail = phead->prev;
DListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
void DListNodePopFront(DListNode* phead)
{
if (phead->next == phead)
{
return;
}
DListNode* firstnode = phead->next;
DListNode* secondnode = firstnode->next;
secondnode->prev = phead;
phead->next = secondnode;
free(firstnode);
firstnode = NULL;
}
DListNode* DListNodeFind(DListNode* phead, DataType x)
{
DListNode* firstnode = phead->next;
while (firstnode != phead)
{
if (firstnode->data == x)
{
return firstnode;
}
firstnode = firstnode->next;
}
return NULL;
}
void DListNodeInsert(DListNode* pos, DataType x)
{
DListNode* prev = pos->prev;
DListNode* newnode = BuyDListNode(x);
newnode->next = pos;
newnode->prev = prev;
prev->next = newnode;
pos->prev = newnode;
}
void DListNodeErase(DListNode* pos)
{
DListNode* prev = pos->prev;
DListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
链表的中间节点(力扣)
给定一个头结点为 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,
这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
来源:力扣(LeetCode)
思路:快慢指针
取两个指针,初始时均指向head,一个为快指针(fast)一次走两步,另一个为慢指针(slow)一次走一步,当快指针满足fast==NULL(偶数个节点)或者fast->next==NULL(奇数个节点)时,slow指向中间节点,返回slow即可。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast=head;
struct ListNode* slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
到此这篇关于C语言 超详细介绍与实现线性表中的带头双向循环链表的文章就介绍到这了,更多相关C语言 双向循环链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C语言超详细介绍与实现线性表中的带头双向循环链表
本文链接: https://www.lsjlt.com/news/144336.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0