双向带头循环链表

一、概念

何为双向:此链表每一个节点的指针域由两部分组成,一个指针指向下一个节点,另一个指针指向上一个节点,并且两头的节点也是如此,头节点的下一个节点是尾节点,尾节点的上一个节点是头节点;

何为带头:此处的头节点是一个 哨兵位,在链表定义时就要手动设置,此节点只是起到头的作用,并不是真正的节点;在双向带头循环链表为空时,链表中只有一个头节点,当链表中连头节点都不存在时,此链表不能被称作一个有效链表;

何为循环:头节点的指针域中能指向前一个节点的指针指向尾节点,尾节点中能指向下一个节点的指针指向头节点,使得这个链表循环;


二、节点结构

struct ListNode
{ListDatatype data;struct ListNode* next;struct ListNode* prev;
};

data存储节点的胡数据,next作用是指向下一个节点,prev的作用是指向前一个节点;


三、基本功能实现

1、头文件

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<assert.h>
typedef int ListDatatype;typedef struct ListNode
{ListDatatype data;struct ListNode* next;struct ListNode* prev;
}ListNode;//初始化链表
void LTInit(ListNode** pphead);//尾插
void LTPushBack(ListNode* phead, ListDatatype x);//头插
void LTPushFront(ListNode* phead, ListDatatype x);//头删
void LTPopFront(ListNode* phead);//尾删
void LTPopBack(ListNode* phead);//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x);//删除指定位置的节点
void LTErase(ListNode* phead,ListNode* pos);//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x);//销毁双向带头循环链表
void LTDestroy(ListNode** phead);

2、函数的实现

初始化

//初始化
void LTInit(ListNode** pphead)
{assert(pphead);*pphead = (ListNode*)malloc(sizeof(ListNode));if (*pphead == NULL){perror("malloc failed");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}

初始化传二级指针,涉及到头节点的修改,默认-1为无效值,给定头节点的数据域是-1;让头节点的next和prev指针都指向自己,实现循环。

申请节点

//申请节点
ListNode* BuyNode(ListDatatype x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc failed");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;
}

申请的节点数据域为你传进的值;同样地,新节点地next和prev指针都指向自己;

尾插

//尾插
void LTPushBack(ListNode* phead, ListDatatype x)
{assert(phead);ListNode* newnode = BuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

尾插不涉及到头节点地改变,所以只需要传入一级指针;尾插进入一个数据,涉及到头节点的prev指针指向发生变化,和原连边尾节点的next指针指向发生变化,为了不造成节点找不到的情况,先修改newnode的指针指向,让newnode的next指向phead,prev指向原链表的尾节点,也就是phead->prev;此操作完成后,先让原链表的尾节点(phead->prev)的next指向newnode,使得newnode成为新的尾节点,再让头节点phead的prev指向作为新的尾节点的newnode,完成循环;

头插

//头插
void LTPushFront(ListNode* phead, ListDatatype x)
{assert(phead);ListNode* newnode = BuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

头插是往头节点(哨兵位)的下一个指针插入节点,因为头节点不存放有效数据,在链表中的的作用只是当做一个桩子;所以先让newnode的next指针指向原链表头指针的下一个节点,也就是phead->next,再让newnode的prev指针指向phead;   再让原链表头节点之后的那个节点(phead->next)的prev指向newnode,最后再让头节点的next指针指向newnode

注意:最后两行代码不能颠倒顺序,若是颠倒,那么phead的next指针就先指向newnode,再进行(    phead->next->prev = newnode;)操作时相当于newnode->prev=newnode,这样无法实现双向(尾插同样如此)

尾删

//尾删
void LTPopBack(ListNode* phead)
{assert(phead && phead->next!=phead);ListNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}

尾删首先要保证链表中含有可以删除的有效节点,所以assert断言中(phead->next!=phead)操作必不可少,若是只含有头节点,那么相当于phead->next=phead这行代码,那么断言错误;当然头节点是必须存在的;

先把要删除的尾节点存在del中,先不删除del,先把要修改的指针指向修改好之后再删除要删除的尾节点,这样是为了避免找不到尾节点的前后节点;pehad->prev就是尾节点,把头节点的prev指针指向倒数第二个节点也就是(del->prev),再让倒数第二个节点的next指针指向头节点;最后释放尾节点del;

头删

//头删
void LTPopFront(ListNode* phead)
{assert(phead && phead->next!=phead);//头删时要存在有效节点ListNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

头删删除的是头节点后面的那个指针,和尾删断言一样,链表中要存在有效节点,否则断言报错;先把要删除的节点存放起来,再先修改指针的指向,最后删除del;

查找结点

//查找节点
ListNode* NodeFind(ListNode* phead,ListDatatype x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

查找节点的方法是把链表遍历一遍,看有没有数据域等于要查找的节点的数据域,若是有则返回这个节点,反之返回NULL;

在指定位置之后插入节点

//在指定位置之后插入节点
void LTInsert(ListNode* phead, ListNode* pos,ListDatatype x)
{assert(phead && pos);ListNode* newnode = BuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

需要配合查找节点一起使用,将查找到的节点作为pos,在此后插入节点,同样地先改变newnode的先后指针指向,再去修改pos以及pos后一个几点的指针指向;

删除指定位置的节点

//删除指定位置的节点
void LTErase(ListNode* phead, ListNode* pos)
{assert(phead);assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

pos必须存在,删除先改变删除的节点的前后节的指针的指向,再删除pos;

销毁链表

//销毁双向带头循环链表
void LTDestroy(ListNode** pphead)
{assert(pphead && *pphead);ListNode* pcur = (*pphead)->next;while (pcur != *pphead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

销毁链表涉及到头节点的改变。要传入二级指针;并且要销毁链表中每一个节点,遍历删除,最后free掉头节点并置为空。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/374500.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ubuntu下载Nginx

一、Nginx下载安装&#xff08;Ubuntu系统&#xff09; 1.nginx下载 sudo apt-get install nginx2.nginx启动 启动命令 sudo nginx重新编译(每次更改完nginx配置文件后运行&#xff09;&#xff1a; sudo nginx -s reload3.测试nginx是否启动成功 打开浏览器访问本机80端口…

javaweb学习day1《HTML篇》--新浪微博(前端页面的创建思路及其HTML、css代码详解)

一、前言 本篇章为javaweb的开端&#xff0c;也是第一篇综合案例&#xff0c;小编也是看着黑马程序员的视频对里面的知识点进行理解&#xff0c;然后自己找一个新浪微博网页看着做的&#xff0c;主要还是因为懒&#xff0c;不想去领黑马程序员的资料了。 小编任务javaweb和ja…

3102. 最小化曼哈顿距离——leetcode

给你一个下标从 0 开始的数组 points &#xff0c;它表示二维平面上一些点的整数坐标&#xff0c;其中 points[i] [xi, yi] 。 两点之间的距离定义为它们的曼哈顿距离。 请你恰好移除一个点&#xff0c;返回移除后任意两点之间的 最大 距离可能的 最小 值。 示例&#xff1…

【k8s中安装rabbitmq】k8s中基于安装rabbitmq并搭建镜像集群-pvc版

文章目录 简介一.条件及环境说明4.2.创建configmap配置4.3.创建statefulset和service headless配置4.4.授权配置4.5.创建service配置 五.安装完后的配置六.安装说明 简介 该文搭建的rabbitmq集群是采用rabbitmq_peer_discovery_k8s的形式进行搭建&#xff0c;是通过该插件自动从…

这8个AI工具高效无敌,设计师又轻松了!

人工智能工具在设计领域的广泛应用给艺术界带来了巨大的变化。设计师可以使用各种工具来展示他们的创造力和灵感&#xff0c;而不受时间和空间的限制。这些专业的人工智能绘图工具允许设计师看到每一步的最终结果&#xff0c;从而更高效、更方便地创造和设计灵感。因此&#xf…

什么是业务架构、数据架构、应用架构和技术架构

TOGAF(The Open Group Architecture Framework)是一个广泛应用的企业架构框架&#xff0c;旨在帮助组织高效地进行架构设计和管理。而TOGAF的核心就是由我们熟知的四大架构领域组成&#xff1a;业务架构、数据架构、应用架构和技术架构。 所以今天我们就来聊聊&#xff0c;企业…

水文:CBA业务架构师

首先&#xff0c; 我们来了解一下什么是CBA业务架构师&#xff1f; CBA业务架构师认证是由业务架构师公会(Business Architecture Guild)授予的一种专业认证。标志着证书持有者已经掌握了业务架构的核心技能和知识&#xff0c;能够在实际工作中熟练运用业务架构技术和框架&…

SAP S4 销售组的定义和分配

spro-企业结构-定义-销售与分销-维护销售组 新增一个记录 spro-企业结构-分配-销售与分销-给销售办公室分配销售组

c++多态——virtual关键字,C++11 override 和 final,析构函数的重写。

目录 多态基本概念 virtual关键字 C11 override 和 final 举个栗子 析构函数的重写(基类与派生类析构函数的名字不同) 多态基本概念 概念&#xff1a;通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会 产生出不同…

关于string的‘\0‘与string,vector构造特点,反迭代器与迭代器类等的讨论

目录 问题一&#xff1a;关于string的\0问题讨论 问题二&#xff1a;C标准库中的string内存是分配在堆上面吗&#xff1f; 问题三&#xff1a;string与vector的capacity大小设计的特点 问题四&#xff1a;string的流提取问题 问题五&#xff1a;迭代器失效 问题六&#xf…

filex用户手册中文版解读

filex用户手册 filex的用户手册&#xff0c;看着好头疼呢&#xff0c;主要是没有&#x1f58a;记录&#xff0c;感觉就是浮在空中&#xff0c;飘在天上&#xff0c;好像懂了&#xff0c;又好像啥也没了解到&#xff0c;哈哈&#xff0c;有点意思。为了解决这个bug&#xff0c;…

哪个牌子开放式耳机质量好?五款全网爆火款式盘点!

开放式耳机是目前最流行的一种无线蓝牙耳机&#xff0c;与TWS耳机一样&#xff0c;拥有小巧轻盈的耳机主体&#xff0c;也有便携的补能收纳充电仓&#xff0c;但不同的是&#xff0c;开放式耳机有更加舒适的佩戴体验。作为资深数码产品测评师&#xff0c;我最近测评了多款产品&…

基于前馈神经网络 FNN 实现股票单变量时间序列预测(PyTorch版)

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…

原生小程序生成二维码并保存到本地

需求&#xff1a;我要在一个页面中生成一个二维码&#xff0c;并且这个二维码可以长按保存到本地或者发送给好友&#xff1b; 我这里是将生成的canvas二维码转换成图片&#xff0c;利用长按图片进行保存或转发 效果图&#xff1a; 第一步先下载对应的包&#xff1a; npm instal…

Docker部署gitlab私有仓库后查看root默认密码以及修改external_url路径和端口的方法

文章目录 1、docker部署最新版gitlab2、进入gitlab容器3、修改路径地址ip和端口4、检验效果 1、docker部署最新版gitlab #docker安装命令 docker run --detach \--name gitlab \--restart always \-p 1080:80 \-p 10443:443 \-p 1022:22 \-v /gitlab/config:/etc/gitlab \-v …

Apache中使用CGI

Apache24 使用Visual Studio 2022 // CGI2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <stdio.h> #include <stdlib.h>#include <stdio.h>void main() {//设置HTML语言printf("Content-type:text/html\n\n&q…

Redis基本命令源码解析-字符串命令

1. set 用于将kv设置到数据库中 2. mset 批量设置kv mset (msetnx) key1 value1 key2 value2 ... mset:msetCommand msetnx:msetnxCommand msetCommand和msetnxCommand都调用msetGenericCommand 2.1 msetGenericCommand 如果参数个数为偶数,则响应参数错误并返回 如果…

【游戏客户端】大话slg玩法架构(二)背景地图

【游戏客户端】大话slg玩法架构&#xff08;二&#xff09;背景地图 大家好&#xff0c;我是Lampard家杰~~ 今天我们继续给大家分享SLG玩法的实现架构&#xff0c;关于SLG玩法的介绍可以参考这篇上一篇文章&#xff1a;【游戏客户端】制作率土之滨Like玩法 PS&#xff1a;和之前…

hudi数据湖万字全方位教程+应用示例

1、时间轴&#xff08;TimeLine&#xff09; Hudi的核心是维护表上在不同的即时时间&#xff08;instants&#xff09;执行的所有操作的时间轴&#xff08;timeline&#xff09;&#xff0c;这有助于提供表的即时视图 一个instant由以下三个部分组成&#xff1a; 1&#xff09;…

视频号矩阵系统源码,实现AI自动生成文案和自动回复私信评论,支持多个短视频平台

在当今短视频蓬勃发展的时代&#xff0c;视频号矩阵系统源码成为了自媒体人争相探索的宝藏。这一强大的技术工具不仅能帮助我们高效管理多个短视频平台&#xff0c;更能通过AI智能生成文案和自动回复私信评论&#xff0c;为自媒体运营带来前所未有的便利与效率。 一、视频号矩…