这个是一个标题哦
- 双链表
- 那么,开始准备吧
-
- 双链表的本体
- 初始化
- 得到一个节点
- 打印链表
- 销毁链表
- 经典的增删查改
-
- 插入操作
-
- 头插
- 尾插
- 指定位置前插入
- 遇到困难偷大懒
- 删除操作
- 简单偷个懒吧!
- 查询和修改
- 最后
文章图片
在淦了四篇刷题笔记之后,菜鸡大学生想起她之前在单链表挖的坑还没填。遂,填。有一说一菜鸡大学生的坑品还是可以的。下一篇是动图教程哦,所以…(暗示) 开搞!
双链表
文章图片
(今天的攻略对象)
和上次的单链表相比,今天要写的双链表有以下不同:
- 带哨兵位的头结点。
- 双向的,每个节点不仅可以指向下一个,还可以指向上一个。
- 循环链表,最后一个节点指向第一个节点。
文章图片
typedef int ListDataType;
typedef struct ListNode
{
struct ListNode* prev;
//*
struct ListNode* next;
ListDataType data;
}ListNode;
初始化 在初始化的时候我们就要带上我们的哨兵位了。
我们先生成一个节点,里面的数据置为0 (数据多少都无所谓,反正都不会用上) 然后将节点的前指针和后指针统统指向自己。
这样,一个循环链表的雏形就出来了。
//初始化
ListNode* ListInit()
{
ListNode* phead= BuyListNode(0);
phead->next = phead;
phead->prev= phead;
return phead;
}
得到一个节点 没啥,就多了一个前指针。
随便写写就好。
//得到一个节点
ListNode* BuyListNode(ListDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = https://www.it610.com/article/x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
打印链表 同上,注意结束条件变成了
cur!=phead
,因为是循环链表嘛。//打印
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
销毁链表 整一个cur指针,从头的下一个节点开始删,直到下一个节点是头,然后把头和cur一起删掉。
我决定画个图玩玩。
文章图片
//销毁
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
ListNode* next = phead->next;
while (next!=phead)
{
free(cur);
cur = next;
next = next->next;
}
free(cur);
free(phead);
}
经典的增删查改 插入操作 头插
双链表由于结构的优越性,增删查改变得嘎嘎简单,只要我们能找到要插入的节点两侧的节点,然后就是无脑操作。
所以我们就大致画画图,放个代码就好了。
- 首先创建新节点
文章图片
- 接着我们将phead和first与新节点链接。
文章图片
- 然后就结束了。
文章图片
文章图片
//头插
void ListPushFront(ListNode* phead, ListDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* first = phead->next;
phead->next = newnode;
newnode->next = first;
newnode->prev = phead;
first->prev = newnode;
}
尾插
同理。
我连图都懒得画。
//尾插
void ListPushBack(ListNode* phead, ListDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* tail = phead->prev;
phead->prev = newnode;
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
}
指定位置前插入
…(暗示)
//某个位置前插入数据
void ListInsert(ListNode* pos, ListDataType x)
{
ListNode* newnode = BuyListNode(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
遇到困难偷大懒
有了指定位置插入我们可以偷头插和尾插的懒了。
- 尾插就是在phead的前面插入数据。
- 头插就是在phead的下一位前面插入数据。
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}
删除操作 似乎更加简单了?但是要检查链表是不是为空即
phead->next!=phead
.//头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next!=phead);
ListNode* first = phead->next;
phead->next = first->next;
first->next->prev = phead;
free(first);
}//尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
phead->prev = tail->prev;
tail->prev->next = phead;
free(tail);
}//删除某个位置数据
void ListErase(ListNode* phead, ListNode* pos)
{
assert(phead);
assert(phead->next != phead);
//稍微考虑一下phead吧,不考虑也行 ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
简单偷个懒吧! 这里使用的是不带phead玩的版本。
//尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListErase(phead->prev);
}//头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListErase(phead->next);
}
查询和修改 很简单哦,只要遍历就可以了。
//查某个值,返回地址
ListNode* ListFind(ListNode* phead, ListDataType x)
{
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data =https://www.it610.com/article/= x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}//改某个值
void ListChange(ListNode* phead, ListDataType sourse, ListDataType destination)
{
assert(phead);
ListNode* pos= ListFind(phead, sourse);
pos->data = https://www.it610.com/article/destination;
}
最后 感觉这一篇好水哦(笑)
看在下一篇是动图教程的份上,捧个小场不过分吧。
推荐阅读
- 半截入土C++|[烂莓子的c++学习笔记](二)函数重载
- 半截入土C++|[烂莓子的c++学习笔记](一)命名空间&&缺省参数
- C语言入土之路|[数据结构]题海啊,全是水(四)相交链表、环形链表、环形链表II
- C++的工作原理(了解编译原理)
- 有关C++中Qt多线程的缺失文章
- Stork,第2部分(创建表达式解析器)
- Stork(如何用C++编写编程语言)
- Stork,第4部分(实现语句和总结)
- 算法|leetcode刷题指南