网站导航
> 文档中心 > 详解双向循环带头节点链表——十分钟单手吊打链表

详解双向循环带头节点链表——十分钟单手吊打链表

网友: 文档中心 2022-03-24 08:06:51

目录

    • 传统艺能😎
    • 过渡区🤣
    • 和单链表比较🤔
    • 分类🤔
    • 空间申请👏
    • 初始化👏
    • 尾插👏
    • 尾删👏
    • pos位插入👏
    • 源码奉上🎉
    • ==Slist.h==
    • ==test.c==
    • ==Slist.c==

传统艺能😎

小编是双非本科大一计科菜鸟（打灰人 ）不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】

过渡区🤣

10天军训终于完了，时间管理大师都没法在这段时间打理学习，中途用所剩无几的理性上传了一篇之前笔记随笔，阅读量却没让我失望，于是我就以最快的速度回来继续奋勇直追！
在这里插入图片描述

和单链表比较🤔

之前我讲过了单链表，也就是单向不带头不循环链表，看起来和现在的这个简直天差地别，但是——没有关系，我们必须知道一点：

单向不带头不循环链表是最简单的结构，但实现却比较复杂
双向循环带头节点链表是最复杂的结构，但实现却最简单

单链表一般出现在我们熟知的 OJ 题目中，而生活中实际运用却高度依赖于双链表，因为双链表效率高，实现方便，简单易懂，代码清爽，结构严谨，巴拉巴拉……

分类🤔

之前提到过三个分类：
在这里插入图片描述
双向就是后一个节点存有指向前一个和后一个的指针，既可以正向访问也可以逆向访问，相比单链表灵活性直接上了一个档次。

在这里插入图片描述
所谓带头，指的就是带哨兵位的头，这里的哨兵位相当于一个结构体。
在这里插入图片描述
循环就是指链表尾节点不指向 NULL 而是指向 phead，从而使头插头删尾插尾删等基本操作变得十分简单。

当然不止以上6种，两两排列组合可以得到更多的形式。

空间申请👏

老规矩，开辟空间肯定是第一步：

Seqlist* buymalloc(Seqtype x){Seqlist* newnode = (Seqlist*) malloc (sizeof(Seqlist));if (newnode == NULL){printf("malloc fail!\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}

初始化👏

Seqlist* phead = NULL;phead=ListInit();

这里就开始设置哨兵位头节点：

Seqlist* init(){Seqlist* phead = buymalloc(0);phead->next = phead;//指向下一个节点的指针指向自身phead->prev = phead;//指向上一个节点的指针指向自身return phead;}

因为创建的结构体指针 phead 指向NULL，因此我们需要在初始化时创建一个哨兵位头结点，使 phead 指向这个头节点；在后续的使用中，plist始终是指向这个头结点，并不会被修改，因此不需要传入二级指针

存在哨兵位头结点时，改变的是哨兵位（结构体）节点，传入的是结构体的指针（地址），非哨兵位改变的是结构体指针那传入的就是结构体指针的指针（地址）

注意：这里开辟空间参数为 0，这里目的是只要让头结点不为空即可，不用在意值的大小。

尾插👏

以基本功能举两个栗子来实际体会一下和单链表的差距：

void pushback(Seqlist* phead, Seqtype x){assert(phead);Seqlist* newnode = buymalloc(x);Seqlist* tail = phead->prev;tail->next = newnode;tail = newnode->prev;newnode->next = phead;phead->prev = newnode;}

用ppt手残一张图出来配合食用，勿喷捏：
在这里插入图片描述
注意各个步骤的顺序，前后的逻辑严格，不可随意调换，稍有差错就可能找不到前一个或者后一个节点的地址。

尾删👏

void popback(Seqlist* phead){assert(phead);assert(phead != phead->next);Seqlist* tail = phead->prev;Seqlist* tailprev = tail->prev;free(tail);tail = NULL;tailprev->next = phead;phead->prev = tailprev;}

在这里插入图片描述

pos位插入👏

其实比起头插尾插，pos位插入其实更为简单，注意pos位插入是指 pos 的前一位插入，思路即 pos 前前一个节点与pos前一个节点链接，再和 pos 后一个节点链接就行，中间步骤直接链接即可。

void insert(Seqlist* pos, Seqtype x){assert(pos);Seqlist* newnode = buymalloc(x);Seqlist* posprev = pos->prev;//找到插入节点的正确位置newnode->next = pos;posprev->next = newnode;newnode->prev = posprev;}

我们之前说过，头插头删尾插尾删其实是 pos 位插入删除的特殊实现情况，所以我们格局打开：写出 pos 位插入删除即可搞定所有插删操作。

那么头插就可以写成这样：

void pushfront(Seqlist* phead,Setype x){assert(phead);insert(phead->next,x);}

尾插同理：

void pushback(Seqlist* phead,Setype x){assert(phead);insert(phead,x);}

😎是不是突然就觉得头尾删插是个什么渣渣！😎
没错，这就是结构最复杂操作却最简单的双向带头循环链表。

源码奉上🎉

Slist.h

#pragma once#include#include#includetypedef int Seqtype;typedef  struct Seqlist{Seqtype data;struct Seqlist* next;struct Seqlist* prev;}Seqlist;Seqlist* buymalloc(Seqtype x);//开辟空间Seqlist* init();//初始化void print(Seqlist* phead);//打印void pushback(Seqlist* phead, Seqtype x);//尾插void popback(Seqlist* phead);//尾删void popfront(Seqlist* phead);//头删void pushfront(Seqlist* phead, Seqtype x);//头插Seqlist* find(Seqlist* phead, Seqtype x);//查找void insert(Seqlist* pos, Seqtype x);//pos位插入void erase(Seqlist* pos);//pos位删除

test.c

# define _CRT_SECURE_NO_WARNINGS #include"Slist.h"void test(){Seqlist* phead = init();pushback(phead, 2);pushback(phead, 3);popback(phead);    print(phead);}int main(){test();return 0;}

Slist.c

# define _CRT_SECURE_NO_WARNINGS #include"Slist.h"Seqlist* buymalloc(Seqtype x){Seqlist* newnode = (Seqlist*) malloc (sizeof(Seqlist));if (newnode == NULL){printf("fail!\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}void pushback(Seqlist* phead, Seqtype x){assert(phead);Seqlist* newnode = buymalloc(x);Seqlist* tail = phead->prev;tail->next = newnode;tail = newnode->prev;newnode->next = phead;phead->prev = newnode;}//哨兵位头结点，改变的是哨兵位（结构体）节点，//传的是结构体的指针（地址），非哨兵位改变的是结构体指针那//传的就是结构体指针的指针（地址）void print(Seqlist* phead){assert(phead);Seqlist* newnode = phead->next;while(newnode != phead){printf("%d ", newnode->data);newnode = newnode->next;}}Seqlist* init(){Seqlist* phead = buymalloc(0);phead->next = phead;phead->prev = phead;return phead;}void popback(Seqlist* phead){assert(phead);assert(phead != phead->next);Seqlist* tail = phead->prev;Seqlist* tailprev = tail->prev;free(tail);tail = NULL;tailprev->next = phead;phead->prev = tailprev;}void insert(Seqlist* pos, Seqtype x){assert(pos);Seqlist* newnode = buymalloc(x);Seqlist* posprev = pos->prev;newnode->next = pos;posprev->next = newnode;newnode->prev = posprev;}void pushfront(Seqlist* phead, Seqtype x){assert(phead);insert(phead->next, x);}Seqlist* find(Seqlist* phead, Seqtype x){assert(phead);Seqlist* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

今天就到这里吧，摸了家人们。

杭州女装网

网络标签：

相关问题