王道数据结构C语言循环链表基本操作实现

news/2024/4/19 4:33:38

文章目录

  • 一、循环单链表
    • 1.1初始化及判空操作
    • 1.2判断是否是尾结点
  • 二、循环双链表
    • 2.1初始化
    • 2.2判空
    • 2.3判断尾结点
    • 2.4循环双链表的删除


一、循环单链表

1.1初始化及判空操作

其实循环链表就是在单链表(双链表)上做一点小小的优化

它是把尾结点的next指向了头结点
如果当前链表为空,也就是只有一个头结点(头结点不放东西)
那么头结点的next是要指向它自己的,形成一个循环
在这里插入图片描述

我们判空也只需要判断头结点的next是不是头结点自己

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdbool.h>
typedef struct {int data;//结点存放的数据类型,这里考试一般把int换成ElemTypeLNode* next;//指向下一个结点的指针
}LNode,*LinkList;//初始化一个循环单链表
bool Init(LinkList *L) {(*L) = (LNode*)malloc(sizeof(LNode));//分配一个头结点if ((*L) = NULL) {return false;}(*L)->next = L;//头结点的next指向头结点,先构成一个简单的循环、return true;
}//判断循环单链表是否为空
bool Empty(LinkList L) {if (L->next == L) {return true;}else {return false;}
}


1.2判断是否是尾结点

这个也很好搞,尾结点指向头结点嘛,你就看哪个结点的next指向头结点就完了

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode* p) {if (p->next == L) {return true;}else {return false;}
}

很多时候对链表的操作都是在头部或者尾部,我们普通单链表如果要找最后一个结点,但是只给了头结点,我们只能一个一个往后遍历,时间复杂度为O(n)

然而对于循环单链表来说,如果我们让这个单链表的指针L不是指向头结点,而是指向尾部这个结点,从尾部找到头部只需要往后找一个结点即可,时间复杂度为O(1),而找尾部的话,因为本身指针就是指向尾部,时间复杂度也是O(1)

二、循环双链表

对于循环双链表来说,除了要把尾部结点next指向头结点,还要把头结点的prior指向尾结点
在这里插入图片描述

2.1初始化

初始化由于只有一个头,所以头的next指向自己,prior也要指向自己
在这里插入图片描述

//循环双链表初始化
typedef struct {int data;//考试中一般把int换成ElemTypeDNode* prior;DNode* next;
}DNode,*DLinkList;//初始化空的循环双链表
bool InitDLinkList(DLinkList* L) {(*L) = (DNode*)malloc(sizeof(DNode));//分配一个头结点if (L == NULL) {//内存不足,分配失败return false;}(*L)->prior = L;//头结点的prior指向头结点(*L)->next = L;//头结点的next指向头结点return true;
}

2.2判空

这个和循环单链表判空一样,因为空表的时候就一个头结点,它的next指向自己

bool isTail(DLinkList L, DNode* p) {if (p->next == L) {return true;}else {return false;}
}

2.3判断尾结点

这个和单循环那里也是一样的,给一个结点,你就看它的next是不是指向头结点就行了

bool isTail(DLinkList L, DNode* p) {if (p->next == L) {return true;}else {return false;}
}

2.4循环双链表的删除

这个比普通双链表删除更简单,普通的还要判断被删的是不是尾结点

循环的双链表你直接进行下面的三步代码就完了,因为它是一个循环连起来的,是不是尾结点无所谓。

//删除p的后继结点q
p->next=q->next;
q->next->prior=p;
free(q);

https://dhexx.cn/news/show-5071392.html

相关文章

期权翻倍行情一个月会出现几次?

期权翻倍一个月出现几次&#xff1f;期权翻倍行情一周有2次左右&#xff0c;也是必做的行情&#xff0c;出现的时候敢不敢满仓的去交易呢&#xff0c;从数据来说&#xff0c;每周2次&#xff0c;一个月8次机会最少也能吃到期权翻倍行情。本文来自&#xff1a;期权酱 期权行情在…

VIRTIO-SCSI代码分析(2)VIRTIO 驱动分析

QEMU模拟出VIRTIO SCSI设备后&#xff0c;在虚拟机中呈现SCSI设备和PCIE设备。而在虚拟机中&#xff0c;PCIE设备与VIRTIO PCI驱动匹配触发virtio_pci_probe()注册生成virtio设备&#xff0c;而virtio设备与虚拟机中的virtio驱动匹配触发对应probe函数最终注册对应的驱动。 这里…

【无公网IP内网穿透】Windows搭建Web站点

什么是cpolar&#xff1f; cpolar是一个非常强大的内网穿透工具&#xff0c;开发调试的必备利器。 它可以将本地内网服务器的HTTP、HTTPS、TCP协议端口映射为公网地址端口&#xff0c;使得公网用户可以轻松访问您的内网服务器&#xff0c;无需部署至公网服务器。支持永久免费使…

Spring boot原理

起步依赖 Maven的传递依赖 自动配置 Springboot的自动配置就是当spring容器启动后&#xff0c;一些配置类、bean对象就自动存入到IOC容器中&#xff0c;不需要我们手动去声明&#xff0c;从而简化了开发&#xff0c;省去了繁琐的配置操作。 自动配置原理&#xff1a; 方案一…

基于matlab实现的 BPSK调制AWGN通道未编码数据误码率程序

完整程序&#xff1a; clear; close all; clc; c0; rate1; %Code rate N10000000; %Number of bits for EbNoc0:1:10 %Ratio of bit energy to no…

用Jmeter进行压测详解

简介&#xff1a; 1.概述 一款工具&#xff0c;功能往往是很多的&#xff0c;细枝末节的地方也很多&#xff0c;实际的测试工作中&#xff0c;绝大多数场景会用到的也就是一些核心功能&#xff0c;根本不需要我们事无巨细的去掌握工具的所有功能。所以本文将用带价最小的方式讲…

论文总结《A Closer Look at Few-shot Classification Again》

原文链接 A Closer Look at Few-shot Classification Again 摘要 这篇文章主要探讨了在少样本图像分类问题中&#xff0c;training algorithm 和 adaptation algorithm的相关性问题。给出了training algorithm和adaptation algorithm是完全不想关的&#xff0c;这意味着我们…

Kubernetes Dashboard安装部署

Kubernetes Dashboard安装部署 1. 下载Dashboard 部署文件2. 修改yaml配置文件3. 应用安装&#xff0c;查看pod和svc4. 创建dashboard服务账户5. 创建admin-user用户的登录密钥6. 登录6.1 使用token登录(1) 短期token(2) token长期有效 6.2 使用 Kubeconfig 文件登录 7.安装met…

redis 主存复制

1. 前言 Redis的持久化机制&#xff0c;它很好的解决了单台Redis服务器由于意外情况导致Redis服务器进程退出或者Redis服务器宕机而造成的数据丢失问题。 在一定程度上保证了数据的安全性&#xff0c;即便是服务器宕机的情况下&#xff0c;也可以保证数据的丢失非常少。 通常…

苹果CMS主题 MXonePro二开优化修复开源版影视网站源码

MXPro模板主题(又名&#xff1a;mxonepro)是一款基于苹果cms程序的一款全新的简洁好看UI的影视站模板类似于西瓜视频&#xff0c;不过同对比MxoneV10魔改模板来说功能没有那么多,也没有那么大气&#xff0c;但是比较且可视化功能较多简洁且有周更记录样式等多功能后台设置&…