本文主要是介绍数据结构之“双向链表”,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 链表的分类
- 2.双向链表
- 2.2 双向链表的打印
- 3.双向链表的插入/删除
- 3.1双向链表的尾插
- 3.2双线链表的头插
- 3.3双向链表的尾删
- 3.4双线链表的头删
- 4. 在pos位置之后插入结点
- 5. 删除pos指定位置的结点
- 6. 双向链表的销毁
- 7.比较
1. 链表的分类
链表的种类有(2x2x2)种,带头/不带头;单向/双向;循环/不循环。
带头/不带头
在之前学习单链表(不带头单向不循环链表)时,它是不带头的,它的第一个结点是可以变的,比如: 我们还可以将第一个结点删除;头插一个数据,等等
但是带头的链表,它的第一个结点(头结点)存储的不是有效数据,其余结点存储的是有效数据。头结点俗称为“哨兵位”,它只是用来占位子的。
单向/双向
单向:只能通过前一个的next找到下一个结点,不能通过下一个结点找到前一个结点的地址。
双向:通过前一个可找到后一个,通过后一个可找到前一个
循环/不循环
2.双向链表
1.全称是:带头双向循环链表
2.双向链表的结点结构:数据+下一个结点的地址next+上一个结点的地址prev
typedef int DataType;//双像链表的定义
typedef struct ListNode
{DataType val;struct ListNode* next;struct ListNode* prev;
};
3.双向链表在使用之前就要有头结点(哨兵位)。(初始化创建一个头结点)
记得:双向链表是:带头双向循环链表,要循环!!!那必定next和prev不可能指向空,而是指向它自己
//LTNode.c里的内容LTNode* LTBuynode(DataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode; //上/下结点地址都是自己,达到循环的目的return newnode;
}void LTInit(LTNode** pphead)
{//创建一个头结点*pphead = LTBuynode(-1);
}
4.双向链表在插入新结点的时候,不需要判断链表有没有头结点。双向链表一定有头结点(哨兵位)。
5.双向链表为空:只有哨兵位。
6.记得写#include<malloc.h>
#include<stdlib.h>
2.2 双向链表的打印
记得注意循环打印链表时,什么时候停止打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next; //pcur等于谁呢?不要写成哨兵位了,要写成第一个有效结点while (pcur!=phead) //双向链表打印到什么时候停止,当pcur==phead时{printf("%d(%p) ->", pcur->val, pcur);pcur = pcur->next;}printf("NULL\n");
}
3.双向链表的插入/删除
双向链表插入或者删除,传过去的都是一级指针。因为phead是头结点,也就是哨兵位。哨兵位是不能被改变的,所以传一级指针。
3.1双向链表的尾插
3.2双线链表的头插
重点:头插是指将新数据成为第一个有效结点,而不是换掉“哨兵位”。
void LTPushFront(LTNode* phead, DataType x)
{assert(phead);LTNode* newnode = LTBuynode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}
3.3双向链表的尾删
如果双向链表里,只有一个哨兵位,也是不可以删除的。所以要对链表进行判断,是否为空(空就是:phead->next=phead; phead->prev=phead;)。
判断用bool,记得包含头文件#include<stdbool.h>
bool LTempty(LTNode* phead)
{//传进来的哨兵位不能为空assert(phead);return phead->next == phead;//如果相等,则是return true
}
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTempty(phead)); //若链表不为空,则LTempty(phead)返回的是false,!LTempty(phead)则是trueLTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del->val = 0;del->next = del->prev = NULL;
}
3.4双线链表的头删
bool LTempty(LTNode* phead)
{//传进来的哨兵位不能为空assert(phead);return phead->next == phead;//如果相等,则是return true
}
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTempty(phead)); //若链表不为空,则LTempty(phead)返回的是false,!LTempty(phead)则是trueLTNode* del = phead->next;LTNode* Next = del->next;phead->next = Next;Next->prev = phead;free(del);del->val = 0;del->next = del->prev = NULL;
}
4. 在pos位置之后插入结点
不需要头结点,只需要pos
LTNode* LTFind(LTNode* phead, DataType x)
{assert(phead);LTNode* pcur = phead->next; //要让pcur是第一个有效结点while (pcur != phead){if (pcur->val == x)return pcur;pcur = pcur->next;}
}
void LTInsert(LTNode* pos, DataType x)
{assert(pos);LTNode* newnode = LTBuynode(x); //插入的数据LTNode* Next = pos->next;newnode->prev = pos;newnode->next = Next;pos->next = newnode;Next->prev = newnode;
}
5. 删除pos指定位置的结点
LTNode* LTFind(LTNode* phead, DataType x)
{assert(phead);LTNode* pcur = phead->next; //要让pcur是第一个有效结点while (pcur != phead){if (pcur->val == x)return pcur;pcur = pcur->next;}
}
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos->val = 0;pos->prev = pos->next = NULL;
}
6. 双向链表的销毁
循环,将每一个结点都销毁(先保存pcur->next,防止pcur销毁之后,找不到下一个结点)。最后将哨兵位也销毁。
传二级指针
void LTDestroy(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;while (pcur != (*pphead)){LTNode* Next = pcur->next;free(pcur);pcur = NULL;pcur = Next;}free(*pphead);*pphead = NULL;
}
7.比较
这篇关于数据结构之“双向链表”的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!