【数据结构】线性表（三）循环链表的各种操作（创建、插入、查找、删除、修改、遍历打印、释放内存空间）

目录

线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

四、线性表的链接存储结构

1. 单链表

2. 循环链表

a. 循环链表节点结构体

b. 创建新节点

c. 在循环链表末尾插入节点

d. 删除循环链表中指定值的节点

e. 在循环链表中查找指定值的节点

f. 修改循环链表中指定节点的值

g. 打印循环链表

h. 释放循环链表内存空间

i. 主函数

j. 代码整合

线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

一个线性表是由零个或多个具有相同类型的结点组成的有序集合。

         按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。

【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_63834988/article/details/132089038?spm=1001.2014.3001.5501

四、线性表的链接存储结构

1. 单链表

    顺序表的优点是存取速度快。但是，无论是插入一个结点，还是删除一个结点，都需要调整一批结点的地址。要克服该缺点，就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表，可以克服上述缺点。

        链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。

【数据结构】线性表（二）单链表及其基本操作（创建、插入、删除、修改、遍历打印）-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/m0_63834988/article/details/133914875?spm=1001.2014.3001.5501

2. 循环链表

        从单链表的一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点，这对一些实际应用很不方便。解决的办法是把链接结构“循环化”，即把表尾结点的next域存放指向哨位结点的指针，而不是存放空指针NULL，这样的单链表被称为循环链表。循环链表使用户可以从链表的任何位置开始，访问链表中的任意结点。

a. 循环链表节点结构体

typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域
} Node;

        包含一个整型数据域 data 和一个指向下一个节点的指针域 next。

b. 创建新节点

Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}
  • 创建一个新的节点并返回指向该节点的指针：
    • 使用 malloc 分配了节点的内存空间；
    • 将传入的数据赋值给节点的 data 字段，并将 next 字段设置为 NULL。

c. 在循环链表末尾插入节点

void insert(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;(*head)->next = *head;  // 将尾节点指向头节点，形成循环} else {Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head;}
}
  • 调用 createNode 函数创建一个新节点，并将新节点的指针保存在 newNode 中。
  • 检查链表是否为空
    • 如果为空，则将 head 指向新节点，并将新节点的指针域 next 设置为指向自己，这样形成一个只有一个节点的循环链表。
    • 如果链表不为空，遍历链表找到尾节点，将尾节点的指针域 next 指向新节点，新节点的指针域 next 指向头节点，完成节点的插入操作。

d. 删除循环链表中指定值的节点

void deleteNode(Node** head, int data) {if (*head == NULL) {return;}Node* currNode = *head;Node* prevNode = NULL;while (currNode->next != *head) {if (currNode->data == data) {if (prevNode == NULL) {Node* lastNode = *head;while (lastNode->next != *head) {lastNode = lastNode->next;}*head = currNode->next;lastNode->next = *head;} else {prevNode->next = currNode->next;}free(currNode);return;}prevNode = currNode;currNode = currNode->next;}if (currNode->data == data) {if (prevNode == NULL) {*head = NULL;} else {prevNode->next = *head;}free(currNode);}
}
  • 检查链表是否为空，如果为空则直接返回。
  • 定义两个指针 currNode 和 prevNode
    • currNode 指向当前节点，初始时指向头节点
    • prevNode指向前一个节点，初始为 NULL
  • 遍历链表，如果找到了与指定值相等的节点，则判断该节点是否为头节点，
    • 如果是头节点，则需要找到尾节点将其指向新的头节点，并更新 *head 的值为删除节点的下一个节点，最后释放删除节点的内存。
    • 如果不是头节点，直接将前一个节点的指针域 next 指向删除节点的下一个节点，然后释放删除节点的内存。

e. 在循环链表中查找指定值的节点

Node* search(Node* head, int data) {if (head == NULL) {return NULL;}Node* currNode = head;while (currNode->next != head) {if (currNode->data == data) {return currNode;}currNode = currNode->next;}if (currNode->data == data) {return currNode;}return NULL;
}
  • 链表是否为空，如果为空则返回 NULL。
  • 定义一个指针 currNode，初始时指向头节点。
  • 遍历链表，如果找到了与指定值相等的节点，则返回该节点的指针。
  • 如果遍历完整个链表都没找到相等的节点，则返回 NULL。

f. 修改循环链表中指定节点的值

void modify(Node* head, int oldData, int newData) {Node* nodeToModify = search(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData;}
}
  • 调用上述e中 search 函数查找指定值的节点，并将返回的节点指针保存在 nodeToModify 中
  • 如果找到了节点，则将该节点的数据域 data 更新为 newData。

g. 打印循环链表

void printList(Node* head) {if (head == NULL) {printf("循环链表为空\n");return;}Node* currNode = head;do {printf("%d ", currNode->data);currNode = currNode->next;} while (currNode != head);printf("\n");
}
  • 检查链表是否为空，如果为空则打印提示信息并返回。
  • 定义一个指针 currNode，初始时指向头节点。
  • 使用 do-while 循环遍历链表，打印当前节点的数据，然后将指针移动到下一个节点，直到回到头节点为止。

h. 释放循环链表内存空间

void freeList(Node** head) {if (*head == NULL) {return;}Node* currNode = *head;Node* nextNode = NULL;while (currNode->next != *head) {nextNode = currNode->next;free(currNode);currNode = nextNode;}free(currNode);*head = NULL;
}
  • 检查链表是否为空，如果为空则直接返回。
  • 定义两个指针 currNode 和 nextNode
    • currNode 指向当前节点，初始时指向头节点
    • nextNode指向下一个节点，初始为 NULL
  • 使用 while 循环遍历链表，将 nextNode 指向 currNode 的下一个节点，释放 currNode 指向的节点的内存，然后将 currNode 更新为 nextNode。重复以上步骤，直到遍历完整个链表，并最后释放头节点的内存。

i. 主函数

int main() {Node* head = NULL;// 在循环链表中插入节点insert(&head, 10);insert(&head, 20);insert(&head, 30);insert(&head, 40);// 打印循环链表printf("循环链表: ");printList(head);// 删除循环链表中的节点deleteNode(&head, 20);// 打印删除节点后的循环链表printf("删除节点后的循环链表: ");printList(head);// 在循环链表中查找节点Node* searchResult = search(head, 30);if (searchResult != NULL) {printf("找到节点 %d\n", searchResult->data);} else {printf("未找到节点\n");}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf("修改节点值后的循环链表: ");printList(head);// 释放循环链表内存空间freeList(&head);return 0;
}
  • 定义一个指向头节点的指针 head，初始时为 NULL。
  • 通过调用 insert 函数，在循环链表中插入了四个节点，其数据分别为 10、20、30 和 40。
  • 调用 deleteNode 函数删除了值为 20 的节点，并再次调用 printList 函数打印删除节点后的循环链表。
  • 调用 search 函数查找值为 30 的节点，并根据返回结果打印相应的信息。
  • 调用 modify 函数修改值为 30 的节点的数据为 50，
  • 最后调用 freeList 函数释放循环链表占用的内存空间。

j. 代码整合

#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构体
typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在循环链表末尾插入节点
void insert(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;(*head)->next = *head;  // 将尾节点指向头节点，形成循环} else {Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head;}
}// 删除循环链表中指定值的节点
void deleteNode(Node** head, int data) {if (*head == NULL) {return;}Node* currNode = *head;Node* prevNode = NULL;while (currNode->next != *head) {if (currNode->data == data) {if (prevNode == NULL) {Node* lastNode = *head;while (lastNode->next != *head) {lastNode = lastNode->next;}*head = currNode->next;lastNode->next = *head;} else {prevNode->next = currNode->next;}free(currNode);return;}prevNode = currNode;currNode = currNode->next;}if (currNode->data == data) {if (prevNode == NULL) {*head = NULL;} else {prevNode->next = *head;}free(currNode);}
}// 在循环链表中查找指定值的节点
Node* search(Node* head, int data) {if (head == NULL) {return NULL;}Node* currNode = head;while (currNode->next != head) {if (currNode->data == data) {return currNode;}currNode = currNode->next;}if (currNode->data == data) {return currNode;}return NULL;
}// 修改循环链表中指定节点的值
void modify(Node* head, int oldData, int newData) {Node* nodeToModify = search(head, oldData);if (nodeToModify != NULL) {nodeToModify->data = newData;}
}// 打印循环链表
void printList(Node* head) {if (head == NULL) {printf("循环链表为空\n");return;}Node* currNode = head;do {printf("%d ", currNode->data);currNode = currNode->next;} while (currNode != head);printf("\n");
}// 释放循环链表内存空间
void freeList(Node** head) {if (*head == NULL) {return;}Node* currNode = *head;Node* nextNode = NULL;while (currNode->next != *head) {nextNode = currNode->next;free(currNode);currNode = nextNode;}free(currNode);*head = NULL;
}int main() {Node* head = NULL;// 在循环链表中插入节点insert(&head, 10);insert(&head, 20);insert(&head, 30);insert(&head, 40);// 打印循环链表printf("循环链表: ");printList(head);// 删除循环链表中的节点deleteNode(&head, 20);// 打印删除节点后的循环链表printf("删除节点后的循环链表: ");printList(head);// 在循环链表中查找节点Node* searchResult = search(head, 30);if (searchResult != NULL) {printf("找到节点 %d\n", searchResult->data);} else {printf("未找到节点\n");}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf("修改节点值后的循环链表: ");printList(head);// 释放循环链表内存空间freeList(&head);return 0;
}

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

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

相关文章

Flask Web 安装bootstrap失败pip install bootstrap

Flask Web 安装bootstrap失败pip install bootstrap

失败原因&#xff1a;网速太慢了 把公共wifi换成手机热点&#xff0c;成功&#xff1a;&#xff09; &#x1f603; 更新&#xff1a;开了手机热点还是报下面的错&#xff0c;但是把科学上网关了&#xff0c;就成功了&#xff0c;反正就是网络问题
阅读更多...
决策树oo

决策树oo

决策树学习的算法通常是一个递归地选择最优特征(选择方法的不同&#xff0c;对应着不同的算法)&#xff0c;并根据该特征对训练数据进行分割&#xff0c;使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分&#xff0c;也对应着决策树的构建 步骤&#…
阅读更多...
【Docker从入门到入土 1】Docker管理命令

【Docker从入门到入土 1】Docker管理命令

Part1 一、容器1.1 虚拟化技术的演变1.2 容器简介1.3 为什么要用到容器&#xff1f;1.4 常用的容器引擎1.5 容器和虚拟机 二、Docker2.1 什么是docker&#xff1f;&#xff08;面试题&#xff09;2.2 Docker和虚拟机的区别&#xff08;面试常问&#xff0c;记住&#xff09;2.3…
阅读更多...
视频号下载助手中的小程序怎么用？微信视频号提取下载教程

视频号下载助手中的小程序怎么用？微信视频号提取下载教程

​用过视频号视频下载助手都说好用&#xff0c;但还有不少人不知道如何操作&#xff0c;怎么才能快速提取视频号视频呢&#xff1f;今天就分享两个工具【视频下载助手】和【视频下载bot】两个结合的方式进行下载&#xff0c;具体操作看教程。 在微信客户端中搜索提取机器人&…
阅读更多...
mac电脑zsh: command not found: adb

mac电脑zsh: command not found: adb

“zsh: command not found: adb” 的解决方法&#xff1a; 前提 已经成功安装了 Android Studio. 打开 iTerm 终端依次输入下面命令&#xff1a; echo export ANDROID_HOME/Users/$USER/Library/Android/sdk >> ~/.zshrc echo export PATH${PATH}:$ANDROID_HOME/tool…
阅读更多...
【音视频|ALSA】基于alsa-lib开发ALSA应用层程序--附带源码

【音视频|ALSA】基于alsa-lib开发ALSA应用层程序--附带源码

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…
阅读更多...
HCIP复习第二课：HCIA（网络类型及数据链路层协议）

HCIP复习第二课：HCIA（网络类型及数据链路层协议）

目录 一、网络类型的分类&#xff08;4种&#xff09; 二、数据链路层协议 三、实验作业&#xff08;ppp实验&#xff09; 一、网络类型的分类&#xff08;4种&#xff09; 出现原因&#xff1a;对于不同的二层链路类型的网段&#xff0c;OSPF会生成不同的网络类型 1、多点接…
阅读更多...
“火焰杯”软件测试高校就业选拔赛获奖名单揭晓，河南工业大学人工智能与大数据学院两名学子上榜，奖金2万元!

“火焰杯”软件测试高校就业选拔赛获奖名单揭晓，河南工业大学人工智能与大数据学院两名学子上榜，奖金2万元!

10月14日&#xff0c;由大学生软件测试就业联盟主办的“火焰杯”软件测试高校就业选拔赛颁奖典礼在D204会议室隆重举行。我校人工智能与大数据学院软件工程1803班张志成同学夺得决赛一等奖&#xff0c;奖金20000元&#xff1b;软件工程1904班王博伦同学荣获初赛一等奖和决赛二等…
阅读更多...
【自动化测试】基于Selenium + Python的web自动化框架

【自动化测试】基于Selenium + Python的web自动化框架

一、什么是Selenium&#xff1f; Selenium是一个基于浏览器的自动化工具&#xff0c;她提供了一种跨平台、跨浏览器的端到端的web自动化解决方案。Selenium主要包括三部分&#xff1a;Selenium IDE、Selenium WebDriver 和Selenium Grid&#xff1a;  1、Selenium IDE&…
阅读更多...
如何通过SK集成chatGPT实现DotNet项目工程化？

如何通过SK集成chatGPT实现DotNet项目工程化？

智能助手服务 以下案例将讲解如何实现天气插件 当前文档对应src/assistant/Chat.SemanticServer项目 首先我们介绍一下Chat.SemanticServer的技术架构 SemanticKernel 是什么&#xff1f; Semantic Kernel是一个SDK&#xff0c;它将OpenAI、Azure OpenAI和Hugging Face等大…
阅读更多...
MyBatis--多案例让你熟练使用CRUD操作

MyBatis--多案例让你熟练使用CRUD操作

目录 一、前期准备 二、两种实现CRUD方式 三、增加数据&#xff08;INSERT&#xff09; 四、删除数据&#xff08;DELETE&#xff09; 五、查询数据&#xff08;SELECT&#xff09; 六、更新数据&#xff08;UPDATE&#xff09; 一、前期准备 1.创建maven项目并在pom文件…
阅读更多...
【计算机网络笔记】计算机网络性能（1）——速率、带宽、延迟

【计算机网络笔记】计算机网络性能（1）——速率、带宽、延迟

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 系列文章目录速率带宽延迟/时延(delay或latency) 下面介绍一些计算机网络中常用的性能指标。在本篇中涉及速…
阅读更多...
ELK架构Logstash的相关插件：grok、multiline、mutate、date的详细介绍

ELK架构Logstash的相关插件：grok、multiline、mutate、date的详细介绍

文章目录 1. grok (正则捕获插件)1.1 作用1.2 正则表达式的类型1.2.1 内置正则表达式1.2.2 自定义正则表达式 2. mutate (数据修改插件&#xff09;2.1 作用2.2 常见配置选项2.3 应用实例 3. multiline &#xff08;多行合并插件&#xff09;3.1 作用3.2 常用配置项及示例3.2.1…
阅读更多...
Looper分析

Looper分析

Looper分析 在 Handler 机制中&#xff0c;Looper 的作用是提供了一个消息循环 ( message loop ) 的机制&#xff0c;用于处理和分发消息。 Looper 是一个线程局部的对象&#xff0c;每个线程只能有一个 Looper 对象。它通过一个无限循环来不断地从消息队列中取出消息&#x…
阅读更多...
Linux搭建文件服务器

Linux搭建文件服务器

搭建简单文件服务器 基于centos7.9搭建http文件服务器基于centos7.9搭建nginx文件服务器基于ubuntu2204搭建http文件服务器 IP环境192.168.200.100VMware17 基于centos7.9搭建http文件服务器 安装httpd [rootlocalhost ~]# yum install -y httpd关闭防火墙以及selinux [roo…
阅读更多...
【软考-中级】系统集成项目管理工程师 【15 信息 (文档) 和配置管理】

【软考-中级】系统集成项目管理工程师 【15 信息 (文档) 和配置管理】

持续更新。。。。。。。。。。。。。。。 【第十五章】信息&#xff08;文档&#xff09;和配置管理 知识精讲考点 1:软件文档一般分为三类:开发文档、产品文档、管理文档。考点 2:文档的质量可以分为四级:考点 3:配置管考点 4:考点 5:考点6:考点 7:配置项版本号:考点 8:考点9…
阅读更多...
36张图详解网络基础知识

36张图详解网络基础知识

下午好&#xff0c;我的网工朋友。 在网工这行&#xff0c;只要是面试&#xff0c;一般都难逃网络协议相关的问题吧。 不管是OSI还是TCP/IP&#xff0c;这都是非常重要、基础的知识&#xff0c;很多知识点都是以它们为基础去串联的。 作为网络世界的底层技术&#xff0c;掌握…
阅读更多...
Docker安装ES7.14和Kibana7.14(无账号密码)

Docker安装ES7.14和Kibana7.14(无账号密码)

一、Docker安装ES7.14.0 1、下载镜像 docker pull elasticsearch:7.14.0 2、docker安装7.14.0 mkdir -p /usr/local/elasticsearch/config mkdir -p /usr/local/elasticsearch/data chmod 777 -R /usr/local/elasticsearch/ echo "http.host: 0.0.0.0" >> /u…
阅读更多...
Java 多线程案例

Java 多线程案例

文章目录 1. 多线程案例1.1 单例模式1.2 阻塞式队列 2. 定时器3. 线程池 1. 多线程案例 1.1 单例模式 单例模式&#xff08;Singleton Pattern&#xff09;是一种常用的软件设计模式&#xff0c;该模式的主要目标是确保一个类只有一个实例&#xff0c;并提供一个全局访问点。…
阅读更多...
关于网络协议的若干问题(五)

关于网络协议的若干问题(五)

1、DH 算法会因为传输随机数被破解吗&#xff1f; 答&#xff1a;DH 算法的交换材料要分公钥部分和私钥部分&#xff0c;公钥部分和其他非对称加密一样&#xff0c;都是可以传输的&#xff0c;所以对于安全性是没有影响的&#xff0c;而且传输材料远比传输原始的公钥更加安全。…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023