Hello,好久不见,今天我们讲链表的双向链表,这是一个很厉害的链表,带头双向且循环,学了这个链表,你会发现顺序表的头插头删不再是一个麻烦问题,单链表的尾插尾删也变得简单起来了,那废话不多说,让我们开始我们的学习吧!
首先我们要了解它的物理和逻辑结构,那他们的样子是怎样的呢,首先是一个带头的,那这个难道是我们的哨兵位吗,又是双向,且循环,那让我们来画图了解它吧。
大致就是这样的一个形状,那我们现在需要这样的一个结构体来实现这样的功能,首先应该有一个存储数据的,就是data,然后就是得有两个指针,一个指向前面的节点,一个就是指向后面的节点,那我们就叫它们一个pre指向前面,一个next指向后面,我们来实现一下吧。
typedef int DListType;
typedef struct DList
{
struct DList* pre;
struct DList* next;
DListType data;
}DLNode;
为了方便我们写后面的时候结构体方便一点,我们先定义结构体为DLNode,这样更加方便使用。
现在我们要实现下面的各种接口来完成双链表
首先最重要的就是怎么初始化
初始化的话我们先要想想这个接口函数改的参数和返回值
因为是双向链表,所以得有一个head的头节点,这样才能链接后面的内容
初始化双链表
DLNode* DListInit();
接口函数的名字
这里我们分析首先我们得返回值为什么不是void,而是DLNode*
因为我们要在这里面创建一个头节点,这个节点我们后面都得使用,其次还有一个原因就是这样头节点就不会被销毁,当然我们也可以在外面创建一个节点,然后我们在传它的指针进去,对结构体的内容进行修改,都可以达到相同的作用,废话不多说,我们来实现吧!
DLNode* DListInit()
{
DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
assert(pHead);
pHead->next = pHead;
pHead->pre = pHead;
}
其实很简单,这里必须指针指向自己才可以,如果不这样的话,那我们的循环就不能实现了。
接下来就是怎么打印,打印很简单,我们将它这个指针传过去就行了。
打印双链表
void DListPrint(DLNode* pHead)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
打印函数的想法就是我们找head后面的那个节点,然后打印,因为头节点我们不打印,所以取cur开始,因为是循环,所以cur最后会等于pHead,这样的话就是一个循环,所以我们找下一个就行了,然后打印后更新cur。
接下来我们要创建一个节点,这样才能链接起来我们的节点。
DLNode* CreatNewNode(DListType x)
DLNode* CreatNewNode(DListType x)
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
newnode->pre = NULL;
return newnode;
}
创造节点好了,接下来就是尾插一个节点进去,我们前面单链表尾插首先要找到尾的位置,然后再去尾插,同时要先找到尾的前一个位置,然后free尾,这样时间复杂度就是O(N),所以效率不是特别高,那我们现在因为head的位置里存放的就是尾的位置,所以不用进行查找了。我们现在来实现一下吧
双链表尾插
void DListPushBACK(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* newnode = CreatNewNode(x);
DLNode* pre = pHead->pre;
pHead->pre = newnode;
newnode->next = pHead;
pre->next = newnode;
newnode->pre = pre;
}
其实尾插也很简单,我们这里先用一个指针保存位置,这样的话下一次插入就可以找到尾的位置,而且还不用注重顺序,这样大大的提升效率
有了尾插那就肯定有头插,一样的办法我们来实现一下
双链表的头插
void DListPushFront(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* newnode = CreatNewNode(x);
DLNode* next = pHead->next;
pHead->next = newnode;
newnode->pre = pHead;
newnode->next = next;
next->pre = newnode;
}
有了头插这些,那肯定还有头删和尾删
那我们也来实现一下吧
尾删
void DListPopBack(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->pre;
del->pre->next = pHead;
pHead->pre = del->pre;
free(del);
}
}
前面写的代码都需要测试一下,我们先来测试三个
#include"DList.h"
void test()
{
DLNode* head = DListInit();
DListPushBack(head, 1);
DListPushBack(head, 2);
DListPushBack(head, 3);
DListPushBack(head, 4);
DListPrint(head);
DListPushFront(head, 111);
DListPushFront(head, 111);
DListPushFront(head, 111);
DListPrint(head);
DListPopBack(head);
DListPopBack(head);
DListPopBack(head);
DListPrint(head);
}
int main()
{
test();
return 0;
}
发现我们的程序没有问题,我们再来实现一下头删
void DListPopFront(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->next;
pHead->next = del->next;
del->next->pre = pHead;
free(del);
}
}
接下来就是双链表的查找,有了查找我们才能和在任意位置的删除和插入连用,那我们现在来实现一下吧
DLNode* DListFind(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
随机插入
void DListInsert(DLNode* pos, DListType x)
{
assrt(pos);
DLNode* newnode = CreatNewNode(x);
DLNode* pospre = pos->pre;
pospre->next = newnode;
newnode->pre = pospre;
newnode->next = pos;
pos->pre = newnode;
}
也不是随机插入,是在pos位置之前插入,我们直接传pos和x就行,然后在根据之前的想法一步一步的进行插入链接就行
这里可以更新一下头插和尾插,这里就不演示了
那我们在写一个删除pos位置的函数
删除pos位置
void DListPop(DLNode* pos)
{
assert(pos);
DLNode* pospre = pos->pre;
DLNode* posnext = pos->next;
pospre->next = posnext;
posnext->pre = pospre;
free(pos);
}
还有一个destory我们开辟的空间,这个遍历一遍数组, 然后一个一个释放就行,但是会有问题,我们释放的时候必须看要机记住位置,可以从尾巴开始释放,用一个指针记住前面一个的位置,然后释放掉尾巴,然后更新前一个位置,用while控制一下就行了
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DListType;
typedef struct DList
{
struct DList* pre;
struct DList* next;
DListType data;
}DLNode;
DLNode* DListInit();
void DListPrint(DLNode* pHead);
DLNode* CreatNewNode(DListType x);
void DListPushBack(DLNode* pHead, DListType x);
void DListPushFront(DLNode* pHead, DListType x);
void DListPopBack(DLNode* pHead);
void DListPopFront(DLNode* pHead);
DLNode* DListFind(DLNode* pHead, DListType x);
void DListInsert(DLNode* pos, DListType x);
void DListPop(DLNode* pos);
#include"DList.h"
DLNode* DListInit()
{
DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
pHead->next = pHead;
pHead->pre = pHead;
}
void DListPrint(DLNode* pHead)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
DLNode* CreatNewNode(DListType x)
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
newnode->pre = NULL;
return newnode;
}
void DListPushBack(DLNode* pHead, DListType x)
{
DLNode* newnode = CreatNewNode(x);
DLNode* pre = pHead->pre;
pHead->pre = newnode;
newnode->next = pHead;
pre->next = newnode;
newnode->pre = pre;
}
void DListPushFront(DLNode* pHead, DListType x)
{
DLNode* newnode = CreatNewNode(x);
DLNode* next = pHead->next;
pHead->next = newnode;
newnode->pre = pHead;
newnode->next = next;
next->pre = newnode;
}
void DListPopBack(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->pre;
del->pre->next = pHead;
pHead->pre = del->pre;
free(del);
}
}
void DListPopFront(DLNode* pHead)
{
assert(pHead);
if (pHead->next != pHead)
{
DLNode* del = pHead->next;
pHead->next = del->next;
del->next->pre = pHead;
free(del);
}
}
DLNode* DListFind(DLNode* pHead, DListType x)
{
assert(pHead);
DLNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void DListInsert(DLNode* pos, DListType x)
{
assrt(pos);
DLNode* newnode = CreatNewNode(x);
DLNode* pospre = pos->pre;
pospre->next = newnode;
newnode->pre = pospre;
newnode->next = pos;
pos->pre = newnode;
}
void DListPop(DLNode* pos)
{
assert(pos);
DLNode* pospre = pos->pre;
DLNode* posnext = pos->next;
pospre->next = posnext;
posnext->pre = pospre;
free(pos);
}
谢谢大家,我们下期再见
版权声明:本文为博主作者:在冬天去看海原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/2301_76895050/article/details/132501633