1. 双向链表
1.1 概念与结构
注意:这⾥的“带头”跟前⾯我们说的“头结点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头结点。带头链表⾥的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这⾥“放哨的”
1.2 实现双向链表
List.h
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next; //指针保存下⼀个结点的地址
struct ListNode* prev; //指针保存前⼀个结点的地址
LTDataType data;
}LTNode;
//void LTInit(LTNode** pphead);
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.3 头插
思路:
要先把新节点的next指针指向head的next节点,然后head的next节点(d1)的prev指针指向要
插入的新节点,将插入新节点的prev指针指向head,最后head的next指针指向新节点。
代码实现(list.c):void LTHBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
1.4 尾插
思路:
要先把新节点的next指针指向head节点,然后head的prev节点(d3)的next指针指向要插入的
新节点,将插入新节点的prev指针指向head的prev节点(d3),head的prev指针指向新节点。
代码实现(list.c):void LTPBack(LTNode* phead, LTDataType x)
{
assert(phead);
//申请新的节点
LTNode* newnode = LTBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
1.5 尾删
代码实现:void LTPDel(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
LTNode* preva = del->prev;
preva->next = phead;
phead->prev = preva;
free(del);
del = NULL;
}
1.6 头删
如图:
代码实现:void LTHDel(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* next = phead->next;
next->next->prev = phead;
phead->next = next->next;
free(next);
next = NULL;
}
1.7 寻找指定位置数据
代码实现:
LTNode* LTFind(LTNode* phead, LTDataType x) {
assert(phead);
LTNode* pos = phead->next;
while (pos != phead)
{
if (pos->data == x)
return pos;
pos = pos->next;
}
return NULL;
}
1.8 指定位置之后插入节点
注:需调用1.7的方法找到相应位置后方可插入节点 代码实现: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;
}
1.9 删除指定位置的节点
注:需调用1.7的方法找到相应位置后方可插入节点 代码实现:void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos -> next;
free(pos);
pos = NULL;
}
最后来销毁双向链表:
//销毁链表
void LTDestory(LTNode** pphead)
{
assert(pphead && *pphead);
LTNode* pour = (*pphead)->next;
while (pour != *pphead)
{
LTNode* Next = pour->next;
free(pour);
pour = Next;
}
free(*pphead);
*pphead = NULL;
pour = NULL;
}
这就完成了一个双向链表,如有不懂欢迎私信博主 ,诚信在线为大家解答!!
标签:void,pos,next,链表,如何,LTNode,phead,双向,prev From: https://blog.csdn.net/L286594/article/details/140589292