【C 数据结构】循环链表

文章目录

  • 【 1. 基本原理 】
  • 【 2. 循环链表的创建 】
    • 2.1 循环链表结点设计
    • 2.2 循环单链表初始化
  • 【 3. 循环链表的 插入 】
  • 【 4. 循环单链表的 删除操作 】
  • 【 5. 循环单链表的遍历 】
  • 【 6. 实例 - 循环链表的 增删查改 】
  • 【 7. 双向循环链表 】

【 1. 基本原理 】

  • 对于单链表以及双向链表,其就像一个小巷,无论怎么样最终都能从一端走到另一端,然而循环链表则像一个有传送门的小巷,因为循环链表当你以为你走到结尾的时候,其实你又回到了开头。
  • 循环链表和非循环链表其实创建的过程以及思路几乎完全一样,唯一不同的是,非循环链表的尾结点指向空(NULL),而 循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为 循环单链表(Circular linkedlist)。如下图所示:
    在这里插入图片描述

【 2. 循环链表的创建 】

2.1 循环链表结点设计

  • 以单循环链表为例,对于循环单链表的结点,可以完全参照于单链表的结点设计,如图:
    • data表示数据,其可以是简单的类型(如int,double等等),也可以是复杂的结构体(struct类型)
    • next表示指针,它永远指向自身的下一个结点, 对于 只有一个结点的存在,这个next指针则永远指向自身,对于一个 循环链表的尾部结点,next永远指向开头。
      在这里插入图片描述
  • 其代码可以表示为:
typedef struct list
{
    int data;
    struct list *next;
}list;
//data为存储的数据,next指针为指向下一个结点

2.2 循环单链表初始化

  • 如同单链表的创建,我们需要先创建一个头结点并且给其开辟内存空间,但与单链表不同的是,我们需要在开辟内存空间成功之后将头结点的next指向head自身。我们可以创建一个init函数来完成这件事情,为了以后的重复创建和插入,我们可以考虑 在init重创建的结点next指向空,而在主函数调用创建之后手动 将head头结点的next指针指向自身。这样的操作方式可以方便过后的创建单链表,直接利用多次调用的插入函数即可完成整体创建。
  • C语言实现可以表示为:
//初始结点
list *initlist()
{
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL)
    {
        printf("创建失败,退出程序");
        exit(0);
    }
    else
    {
        head->next=NULL;
        return head;
    }
}
  • 在主函数重调用:
//初始化头结点
list *head=initlist();
head->next=head;

【 3. 循环链表的 插入 】

  • 对于插入数据的操作,基本与单链表的插入操作相同,我们可以创建一个独立的结点,通过将需要插入的结点的上一个结点的next指针指向该节点,再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。
    在这里插入图片描述
  • C 代码可以表示为:
//插入元素
//三个参数分别是链表,位置,参数
list *insert_list(list *head,int pos,int data)
{
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL)
    {
        for(int i=1;i<pos;i++)
        {
            t=t->next;  //走到需要插入的位置处
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}

【 4. 循环单链表的 删除操作 】

  • 如图所示,循环单链表的删除操作可以参考单链表的删除操作,其都是 找到需要删除的结点,将其前一个结点的next指针直接指向删除结点的下一个结点 即可,但需要注意的是尾节点和头结点的特判,尤其是尾结点,因为删除尾节点后,尾节点前一个结点就成了新的尾节点,这个新的尾节点需要指向的是头结点而不是空,其重点可以记录为【删除节点的前一节点.next=删除结点.next】这样的操作可以省去头尾结点的特判:
    在这里插入图片描述
  • C 代码:
//删除元素
int delete_list(list *head) 
{
    if(head == NULL) 
    {
        printf("链表为空!\n");
        return 0;
    }
    //建立临时结点存储头结点信息(目的为了找到退出点)
    //如果不这么建立的化需要使用一个数据进行计数标记,计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素,这是我们不想让他发生的
    list *temp = head; //作为遍历的前一个节点         
    list *ptr = head->next;//作为遍历的当前节点

    int del;
    printf("请输入你要删除的元素:");
    scanf("%d",&del);

    while(ptr != head) 
    {
        if(ptr->data == del) 
        {
            if(ptr->next == head) //如果是最后一个尾节点
            {
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;    //核心删除操作代码
            free(ptr);
            //printf("元素删除成功!\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}

【 5. 循环单链表的遍历 】

  • 与普通的单链表和双向链表的遍历不同,循环链表需要进行结点的判断,找到尾节点的位置,由于尾节点的next指针是指向头结点的,所以不能使用链表本身是否为空(NULL)的方法进行简单的循环判断,我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断
  • 此外还有一种计数的方法,即建立一个计数器count=0,每一次next指针指向下一个结点时计数器加一,当count数字与链表的节点数相同的时候即完成循环,这样做有一个 问题就是获取到链表的节点数同时也需要完成一次遍历才可以达成目标
  • C代码:
//遍历元素
int display(list *head) 
{
    if(head != NULL) 
    {
        list *p  = head;
        //遍历头节点到,最后一个数据
        while(p->next != head ) 
        {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行
        //把最后一个节点赋新的节点过去
        return 1;
    }
    else
    {
        printf("头结点为空!\n");
        return 0;
    }
}

【 6. 实例 - 循环链表的 增删查改 】

 #include<stdio.h>
#include<stdlib.h>
typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据,next指针为指向下一个结点
 
//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败,退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}
 
//创建--插入数据
int create_list(list *head){
    int data;   //插入的数据类型
    printf("请输入要插入的元素:");
    scanf("%d",&data);
 
    list *node=initlist();
    node->data=data;
    //初始化一个新的结点,准备进行链接
 
    if(head!=NULL){
        list *p=head;
        //找到最后一个数据
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("头结点已无元素\n");
        return 0;
    }
 
}
 
//插入元素
list *insert_list(list *head,int pos,int data){
    //三个参数分别是链表,位置,参数
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<=pos;i++){
            t=t->next;
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}
 
//删除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("链表为空!\n");
        return 0;
    }
    //建立零时结点存储头结点信息(目的为了找到退出点)
    //如果不这么建立的化需要使用一个数据进行计数标记,计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素,这是我们不想让他发生的
    list *temp = head;          
    list *ptr = head->next;
 
    int del;
    printf("请输入你要删除的元素:");
    scanf("%d",&del);
 
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { //循环结束的条件换成ptr->next == head
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;
            free(ptr);
            //printf("元素删除成功!\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}
 
 
//遍历元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍历头节点到,最后一个数据
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行 ( o=^•ェ•)o ┏━┓
        //把最后一个节点赋新的节点过去
        return 1;
    } else {
        printf("头结点为空!\n");
        return 0;
    }
}
 
int main(){
    //初始化头结点//
    list *head=initlist();
    head->next=head;
    通过插入元素完善链表/
    for(int i=0;i<5;i++){   //只是演示使用,不具体提供输入
        create_list(head);
    }
    display(head);
    插入元素
    head=insert_list(head,1,10);
    display(head);
    删除元素
    delete_list(head);
    display(head);
    return 0;
}

【 7. 双向循环链表 】

  • 循环链表还有一个进阶的概念练习,同双向链表与单链表的关系一样,循环单链表也有一个孪生兄弟——双向循环链表,其设计思路与单链表和双向链表的设计思路一样,就是 在原有的双向链表的基础上,将尾部结点和头部结点进行互相连接

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【嵌入式学习】ARM day04.11

一、思维导图 二、练习 实现三个灯闪烁 汇编代码 .text .global _start _start: 使能GPIOE和F时钟LDR r0,0x50000A28LDR r1,[R0]ORR R1,R1,#(0X3<<4)STR R1,[R0]配置GPIOE和F的MODER寄存器LDR r0,0x50006000 GPIOELDR R1,0X50007000 G…

C语言.指针(5)

指针&#xff08;5&#xff09; 1.sizeof和strlen的对比1.1sizeof1.2strlen1.3sizeof和strlen的对比 2.数组和指针笔试题解析2.1一维数组2.2字符数组2.3二维数组 3.指针运算笔试题解析3.1 题目13.2 题目23.3 题目33.4 题目43.5 题目53.6 题目63.7 题目7 1.sizeof和strlen的对比…

Qt栅格布局的示例

QGridLayout * layoutnew QGridLayout;for(int i0;i<10;i){for(int j0;j<6;j){QLabel *labelnew QLabel(this);label->setText(QString("%1行%2列").arg(i).arg(j));layout->addWidget(label,i,j);}}ui->widget->setLayout(layout); 这样写程序会崩…

NC65 查询默认密码(sql)

NC65 使用sql查询设置的默认密码&#xff08;如果系统设置有&#xff09;&#xff1a; select * from sm_user_defaultpwd

电商技术揭秘十三:云计算在电商中的应用场景

相关系列文章 电商技术揭秘一&#xff1a;电商架构设计与核心技术 电商技术揭秘二&#xff1a;电商平台推荐系统的实现与优化 电商技术揭秘三&#xff1a;电商平台的支付与结算系统 电商技术揭秘四&#xff1a;电商平台的物流管理系统 电商技术揭秘五&#xff1a;电商平台…

C++11 设计模式2. 简单工厂模式

简单工厂&#xff08;Simple Factory&#xff09;模式 我们从实际例子出发&#xff0c;来看在什么情况下&#xff0c;应用简单工厂模式。 还是以一个游戏举例 //策划&#xff1a;亡灵类怪物&#xff0c;元素类怪物&#xff0c;机械类怪物&#xff1a;都有生命值&#xff0…

「Java开发指南」如何利用MyEclipse启用Spring DSL?(一)

本教程将引导您通过启用Spring DSL和使用Service Spring DSL抽象来引导Spring和Spring代码生成项目&#xff0c;本教程中学习的技能也可以很容易地应用于其他抽象。在本教程中&#xff0c;您将学习如何&#xff1a; 为Spring DSL初始化一个项目创建一个模型包创建一个服务和操…

实体抽取全解析:技术与实战

目录 一、前言二、实体抽取技术概览基于规则的实体抽取基于统计的实体抽取基于深度学习的实体抽取 三、实体抽取的发展历程早期的实体抽取方法基于规则和词典的方法基于特征的机器学习方法 深度学习时代的实体抽取从传统模型到神经网络序列标注模型的兴起预训练语言模型的革命 …

如何修改 MySQL 8.0 的密码

在 MySQL 8.0 中修改用户密码是数据库管理的一项基本任务。本教程将引导您完成这一过程&#xff0c;确保即使是初学者也能理解并成功执行。 介绍 MySQL 是最流行的关系数据库管理系统之一。作为数据库管理员或开发人员&#xff0c;您可能需要更改用户的密码来保证账户安全。本…

QT 信号与槽的简单使用

文章目录 1.通过Singloat and Slots Editor 添加信号与槽2. 通过拖动动态添加3.通过转到槽方式添加&#xff08;自动关联&#xff09;4. 自定义信号与槽&#xff08;connect)4.1 connect方式4.2 自定义信号 1.通过Singloat and Slots Editor 添加信号与槽 点添加&#xff0c;然…

突破像素限制,尽显照片细腻之美——Topaz Gigapixel AI for Mac/Win

在这个数字化的时代&#xff0c;我们都热爱用照片记录生活中的美好瞬间。然而&#xff0c;有时候我们会发现&#xff0c;由于各种原因&#xff0c;照片的像素可能无法满足我们的需求。这时候&#xff0c;Topaz Gigapixel AI for Mac/Win 这款强大的照片放大工具应运而生。 Top…

open c UF_MODL_create_simple_hole 识别放置平面 UF_MODL_ask_face_data

在BLOCK上创建一个简单孔 UF_FEATURE_SIGN sign UF_NULLSIGN;double block_orig[3] { -25.0,-25.0,0.0 };char* block_len[3] { "50","50","30" };tag_t blk_obj;UF_MODL_create_block1(sign, block_orig, block_len, &blk_obj);tag_t bo…

PSPICE、Multisim和Saber哪个更适合电路仿真?没想到是它

PSPICE、Multisim和Saber这三个软件都是非常流行的模拟电路仿真工具&#xff0c;它们各自有各自的优缺点&#xff0c;我简单讲一下&#xff1a; PSPICE&#xff1a; 优点&#xff1a; 精度高&#xff1a;PSPICE是专业的电路仿真软件&#xff0c;可以进行高精度的模拟电路仿真…

兮兮牧场养殖小游戏积分兑换互动商城引流模式

刚注册的新会员必须要进入牧场才能激活所有功能 一、获得动物的途径的方式 第一种是邀请好友注册获得&#xff0c;第二种是看广告获得 邀诘好友注册获得动物明细: 1、从兮兮牧场的邀请好友的链接去邀请好友才能获得&#xff0c;其他邀请码无效 2、注册赠送小鸡一只; 3、邀…

基于Springboot + vue + MySQL +Tomcat 社区医院管理服务系统 (含源码)

目录 &#x1f4da; 前言 &#x1f4d1;摘要 &#x1f4d1;系统架构 &#x1f4da; 数据库设计 &#x1f4ac; 用户注册实体属性图 &#x1f4ac; 医生实体属性图 &#x1f4da; 系统功能的具体实现 &#x1f4ac; 前台模块 用户注册 医生信息 &#x1f4ac; 后台功能模…

Docker部署SpringBoot+Vue前后端分离项目

文章目录 1. 安装Docker1. 1 卸载旧版Docker1.2 配置yum仓库1.3 安装Docker1.4 添加自启动配置1.5 配置阿里云镜像加速1.6 测试 2. 安装Nginx2.1 拉取镜像2.2 安装Nginx2.3 测试 3. 安装MySQL3.1 拉取镜像3.2 安装MySQL3.3 连接MySQL 4. 部署SpringBoot项目4.1 Maven打包4.2 编…

centos7安装 on-my-zsh

如下&#x1f447; yum install -y zsh chsh -s /bin/zsh yum install -y git sh -c "$(curl -fsSL https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh)" 重启即可生效啦~

Windows搭建LightPicture图片管理网站结合内网穿透实现公网访问本地图片

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…

【LAMMPS学习】八、基础知识(2.2)类型标签

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

车载数据终端丨车载平板丨车载平板电脑为何在叉车上使用

车载终端平板是一种专门设计用于车辆和运输行业的电子设备。它们通常被安装在叉车、卡车、拖车和其他机动车辆上&#xff0c;以便驾驶员可以更方便地管理和控制运输任务。 为了了解车载终端平板为何能够在叉车上使用&#xff0c;我们需要考虑以下几个方面&#xff1a; 物理结构…