嵌入式开发学习———Linux环境下数据结构学习（三）

单向循环链表

单向循环链表是一种特殊的单向链表，尾节点的指针指向头节点，形成一个闭环。适用于需要循环访问的场景，如轮询调度。

  • 结构特点：每个节点包含数据域和指向下一个节点的指针，尾节点的指针指向头节点而非空值。
  • 操作复杂度：
    • 插入/删除头节点：O(1)
    • 插入/删除尾节点：O(n)（需遍历到尾部）
  • 代码示例（C++）：
struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};

双向链表

双向链表的每个节点包含前驱和后继指针，支持双向遍历，但需要更多内存存储指针。

  • 结构特点：节点包含前驱指针（prev）、数据域和后续指针（next）。
  • 操作复杂度：
    • 任意位置插入/删除：O(1)（已知前驱节点时）
    • 按值查找：O(n)
  • 代码示例（C++）：
struct DNode {int data;DNode* prev;DNode* next;DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

 
作业：

 1.双向链表的部分操作

#include "linklist.h"int main(int argc, const char *argv[])
{//定义一个头linklistptr headptr=NULL;//定义循环变量int i;//定义位置变量int seat;//头的初始化headptr=LinklistHeadnodeApply();//定义新输入数据datatype nwedata;//循环输入数据for(i=0;i<5;i++){puts("请输入一个数：");scanf(" %d",&nwedata);//调用双向链表的头插函数LinklistHeadinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的遍历函数frontLinklistShowfront(headptr);//循环输入数据for(i=0;i<5;i++){puts("请输入一个数：");scanf(" %d",&nwedata);//双向链表的尾插函数LinklistTailinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的头删函数LinklistHeaddelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的尾删函数LinklistTaildelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts("输入想插入的位置：");scanf(" %d",&seat);puts("输入想插入的数据：");scanf(" %d",&nwedata);//调用双向链链表按位置插入函数LinklistSeatinsert(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts("输入想删除的位置：");scanf(" %d",&seat);//调用双向链链表按位置插入函数LinklistSeatdelete(headptr,seat);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts("输入想要修改的位置：");scanf(" %d",&seat);puts("输入想改成的数据：");scanf(" %d",&nwedata);//调用双向链链表按位置修改函数LinklistSeatalter(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts("输入想查找的位置：");scanf(" %d",&seat);//调用双向链链表按位置查找函数LinklistSeatsift(headptr,seat);return 0;
}

#ifndef _LINKLIST_H__
#define _LINKLIST_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>//返回值枚举
enum returntype
{//失败返回FAULSE=-1,//成功返回SUCCESS
};//存储数据类型
typedef int datatype;//双向链链表结构体
typedef struct Node
{//数据域共用体union{//头节点数据域int len;//普通节点数据域datatype data;};//前向指针域struct Node *front;//后向指针域struct Node *next;
}linklist,*linklistptr;//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void);//普通节点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata);//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata);//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr);//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr);//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata);//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr);//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr);//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat);//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat);#endif
#include "linklist.h"//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void)
{//头节点堆区申请linklistptr headptr=(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(headptr==NULL){return NULL;}//初始化headptr->len=0;headptr->front=NULL;headptr->next=NULL;return headptr;
}//普通点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata)
{//普通节点堆区申请linklistptr comptr=(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(comptr==NULL){return NULL;}//初始化comptr->data=nwedata;comptr->front=NULL;comptr->next=NULL;return comptr;
}//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{//定义普通节点指针linklistptr comptr=NULL;//判断是否为nullif(headptr==NULL){return FAULSE;}//普通节点申请comptr=LinklistComnodeApply(nwedata);//申请判断if(comptr==NULL){return FAULSE;}//头插comptr->next=headptr->next;comptr->front=headptr;//判断是否为首个数据if(headptr->next){headptr->next->front=comptr;}headptr->next=comptr;//个数自增headptr->len++;return SUCCESS;
}//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr)
{//定义链表指针linklistptr ptr=NULL;//定义循环变量int i;//判断是否为null//判断链表是否为空if(headptr==NULL||headptr->len==0){return FAULSE;}//输出ptr=headptr->next;puts("正序链表现有数据：");while(ptr){printf("%d ",ptr->data);ptr=ptr->next;}putchar(10);return SUCCESS;
}//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr)
{//定义链表指针linklistptr ptr=NULL;//定义循环变量int i;//判断是否为NULL//判断链表是否为空if(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr->next;while(ptr->next){ptr=ptr->next;}//输出puts("逆序链表现有数据：");while(ptr!=headptr){printf("%d ",ptr->data);ptr=ptr->front;}putchar(10);return SUCCESS;
}//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{//定义链表指针和普通节点指针linklistptr ptr=NULL,comptr=NULL;//判断头是否为nullif(headptr==NULL){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}//初始化普通节点comptr=LinklistComnodeApply(nwedata);//判断申请是否成功if(comptr==NULL){return FAULSE;}//尾插ptr->next=comptr;comptr->front=ptr;//个数自增headptr->len++;return SUCCESS;
}
//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断头是否为nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找到要删除的数据第一个节点deltr=headptr->next;//头删headptr->next=deltr->next;//判断是否只有一个节点if(deltr->next){deltr->next->front=headptr;}free(deltr);deltr=NULL;//个数自减headptr->len--;return SUCCESS;
}//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断头是否为nullif(headptr==NULL||headptr->len==0){return FAULSE;}//找尾部ptr=headptr;while(ptr->next){ptr=ptr->next;}ptr->front->next=NULL;free(ptr);ptr=NULL;headptr->len--;return SUCCESS;
}//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针和普通节点指针linklistptr ptr=NULL,comptr=NULL;//判断头是否为NULL//判断位置是否合法if(headptr==NULL||seat<=0||seat>headptr->len+1){return FAULSE;}//找到对应位置的前一个位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}//初始化普通节点comptr=LinklistComnodeApply(nwedata);//if(comptr==NULL){return FAULSE;}//插入comptr->next=ptr->next;comptr->front=ptr;if(ptr->next!=NULL){ptr->next->front=comptr;}ptr->next=comptr;headptr->len++;return SUCCESS;
}//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针和将删节点指针linklistptr deltr=NULL,ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到对应位置的前一个位置ptr=headptr;for(i=0;i<seat-1;i++){ptr=ptr->next;}deltr=ptr->next;ptr->next=deltr->next;if(deltr->next!=NULL){deltr->next->front=deltr->front;}free(deltr);deltr=NULL;headptr->len--;return SUCCESS;
}//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针linklistptr ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return FAULSE;}//找到对应位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}ptr->data=nwedata;return SUCCESS;
}//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针linklistptr ptr=NULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptr==NULL||headptr->len==0||seat<=0||seat>headptr->len){return NULL;}//找到对应位置ptr=headptr;for(i=0;i<seat;i++){ptr=ptr->next;}printf("linklist[%d]=%d\n",seat,ptr->data);return ptr;
}

运行示例：


2.牛客网刷题

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

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

相关文章

【华为机试】684. 冗余连接

【华为机试】684. 冗余连接

文章目录684. 冗余连接描述示例 1示例 2提示解题思路核心分析问题转化算法选择策略1. 并查集 (Union-Find) - 推荐2. 深度优先搜索 (DFS)3. 拓扑排序算法实现详解方法一&#xff1a;并查集 (Union-Find)方法二&#xff1a;深度优先搜索 (DFS)数学证明并查集算法正确性证明时间复…
阅读更多...
Ⅹ—6.计算机二级综合题7---10套

Ⅹ—6.计算机二级综合题7---10套

目录 第7套 【填空题】 【修改题】 【设计题】 第8套 【填空题】 【修改题】 【设计题】 第9套 【填空题】 【修改题】 【设计题】 第10套 【填空题】 【修改题】 【设计题】 第7套 【填空题】 题目要求：给定程序中，函数fun的功能是:将形参s所指字符串中所…
阅读更多...
【三桥君】大语言模型计算成本高，MoE如何有效降低成本？

【三桥君】大语言模型计算成本高，MoE如何有效降低成本？

​ 你好&#xff0c;我是 ✨三桥君✨ &#x1f4cc;本文介绍&#x1f4cc; >> 一、引言 在AI技术飞速发展的当下&#xff0c;大语言模型&#xff08;LLM&#xff09;的参数规模不断增长&#xff0c;但随之而来的计算成本问题也日益凸显。如何在保持高效推理能力的同时扩…
阅读更多...
Python游戏开发利器：Pygame从入门到实战全解析

Python游戏开发利器：Pygame从入门到实战全解析

引言 Pygame是Python中最受欢迎的2D游戏开发库之一&#xff0c;基于SDL&#xff08;Simple DirectMedia Layer&#xff09;构建&#xff0c;支持图形渲染、音效处理、事件响应等核心功能。无论是开发简单的休闲游戏&#xff0c;还是复杂的交互式应用&#xff0c;Pygame都能提供…
阅读更多...
行为型模式-协作与交互机制

行为型模式-协作与交互机制

行为型模式聚焦于对象间的行为交互&#xff0c;通过规范对象协作方式提升系统的灵活性与可扩展性。在分布式系统中&#xff0c;由于多节点异步通信、网络不可靠性及状态一致性挑战&#xff0c;行为型模式需针对分布式特性进行适应性设计。本文从观察者、策略、命令、责任链、状…
阅读更多...
spring boot 整合 Spring Cloud、Kafka 和 MyBatis菜鸟教程

spring boot 整合 Spring Cloud、Kafka 和 MyBatis菜鸟教程

环境准备确保项目中已引入 Spring Boot、Spring Cloud、Kafka 和 MyBatis 的依赖。以下是一个典型的 Maven 依赖配置&#xff1a;<dependencies><!-- Spring Boot Starter --><dependency><groupId>org.springframework.boot</groupId><artif…
阅读更多...
20 BTLO 蓝队靶场 Sticky Situation 解题记录

20 BTLO 蓝队靶场 Sticky Situation 解题记录

难度&#xff1a;5/10考察技能: Windows admin, Autopsy 使用场景&#xff1a;分析USB设备使用情况Autopsy使用注意&#xff1a;用管理员打开&#xff0c;在实际分析时注意先复制一个镜像文件&#xff0c;保存好原文件常用的Windows USB 取证的位置:Windows XP:Registry Key: U…
阅读更多...
安装及配置Go语言开发环境与VSCode集成指南

安装及配置Go语言开发环境与VSCode集成指南

安装Go语言开发 安装Go语言开发环境是第一步。访问Go官网&#xff0c;下载适合操作系统的安装包&#xff0c;如果进不去可以访问Go官方镜像站。 根据自己的系统选择对应的安装包&#xff0c;我这边是Windows系统就点击安装第一个即可。 点击下一步即可。 验证安装是否成功可以…
阅读更多...
专题：2025微短剧行业生态构建与跨界融合研究报告|附100+份报告PDF汇总下载

专题：2025微短剧行业生态构建与跨界融合研究报告|附100+份报告PDF汇总下载

原文链接&#xff1a; https://tecdat.cn/?p43384 分析师&#xff1a;Boyu Wang 在此对 Boyu Wang 对本文所作的贡献表示诚挚感谢&#xff0c;他在武汉大学完成了数据科学与大数据技术专业的学习。擅长 R 语言、Python、机器学习、数据可视化。 中国短视频行业在经历爆发式增…
阅读更多...
配置NGINX

配置NGINX

Nginx环境配置与前端VUE部署安装nginx&#xff1a;命令sudo yum update && sudo yum install nginx部署:拷贝前端到目录/home/publish/idasweb/下修改nginx配置&#xff1a;进入到/etc/nginx目录下&#xff0c;修改nginx.conf中user www-data为user root&#xff0c;不…
阅读更多...
MySQL深度理解-MySQL索引优化

MySQL深度理解-MySQL索引优化

1.Order by与Group by优化1.1Case1employees表中建立了name&#xff0c;position和age索引&#xff0c;并且使用了order by age进行排序操作&#xff1a;EXPLAIN SELECT * FROM employees WHERE name LiLei and position dev order by age最终explain的结果发现使用了idx_nam…
阅读更多...
「Linux命令基础」用户和用户组实训

「Linux命令基础」用户和用户组实训

用户与用户组关系管理 在Linux系统中，用户和用户组的关系就像班级里的学生和小组。一个用户可以同时属于多个组，这种灵活的成员关系为权限管理提供了便利。创建用户时，系统会自动生成一个与用户同名的主组，这个组会成为用户创建文件时的默认属组。 理解用户和用户组的关系…
阅读更多...
Https以及CA证书

Https以及CA证书

目录 1. 什么是 HTTPS 通信机制流程 证书验证过程 CA证书 浏览器如何校验证书合法性呢&#xff1f; 1. 什么是 HTTPS HTTP 加上加密处理和认证以及完整性保护后即是 HTTPS。 它是为了解决 HTTP 存在的安全性问题&#xff0c;而衍生的协议&#xff0c;那使用 HTTP 的缺点有…
阅读更多...
数字图像处理（四：图像如果当作矩阵，那加减乘除处理了矩阵，那图像咋变）：从LED冬奥会、奥运会及春晚等等大屏，到手机小屏，快来挖一挖里面都有什么

数字图像处理（四：图像如果当作矩阵，那加减乘除处理了矩阵，那图像咋变）：从LED冬奥会、奥运会及春晚等等大屏，到手机小屏，快来挖一挖里面都有什么

数字图像处理&#xff08;四&#xff09;三、&#xff08;准备工作&#xff1a;玩具咋玩&#xff09;图像以矩阵形式存储&#xff0c;那矩阵一变、图像立刻跟着变&#xff1f;原图发挥了钞能力之后的图上述代码包含 10 个图像处理实验&#xff0c;每个实验会生成对应处理后的图…
阅读更多...
SpringBoot航空订票系统的设计与实现

SpringBoot航空订票系统的设计与实现

文章目录前言详细视频演示具体实现截图后端框架SpringBoot持久层框架Hibernate成功系统案例&#xff1a;代码参考数据库源码获取前言 博主介绍:CSDN特邀作者、985高校计算机专业毕业、现任某互联网大厂高级全栈开发工程师、Gitee/掘金/华为云/阿里云/GitHub等平台持续输出高质…
阅读更多...
2025年PostgreSQL 详细安装教程（windows）

2025年PostgreSQL 详细安装教程（windows）

前言 PostgreSQL 是一个功能强大的开源关系型数据库管理系统(ORDBMS)&#xff0c;以下是对它的全面介绍&#xff1a; 基本概况 名称&#xff1a;通常简称为 "Postgres" 类型&#xff1a;对象-关系型数据库管理系统 许可&#xff1a;开源&#xff0c;采用类MIT许可…
阅读更多...
Java日志按天切分方法

Java日志按天切分方法

使用 Logrotate&#xff08;推荐&#xff09;Logrotate 是 Linux 系统自带的日志管理工具&#xff0c;支持自动切割、压缩和删除旧日志。步骤&#xff1a;创建 Logrotate 配置文件在 /etc/logrotate.d/ 下新建配置文件&#xff08;如 java-app&#xff09;&#xff1a;sudo nan…
阅读更多...
进阶向:基于Python的本地文件内容搜索工具

进阶向:基于Python的本地文件内容搜索工具

概述 大家好&#xff01;今天我们将一起学习如何用Python创建一个简单但强大的本地文件内容搜索工具。这个工具特别适合处理大量文本文件时的快速检索需求。 为什么要学习这个工具 如果你刚接触编程&#xff0c;完全不用担心&#xff01;我会从零开始讲解&#xff0c;确保每…
阅读更多...
多模态AI的可解释性

多模态AI的可解释性

多模态AI的可解释性挑战 在深入探讨解决方案之前&#xff0c;首先需要精确地定义问题。多模态模型因其固有的复杂性&#xff0c;其内部决策过程对于人类观察者而言是不透明的。 模态融合机制 (Modal Fusion Mechanism)&#xff1a;模型必须将来自不同来源&#xff08;如图像和文…
阅读更多...
MySQL深度理解-MySQL事务优化

MySQL深度理解-MySQL事务优化

1.什么是事务事务就是进行多个操作&#xff0c;要么同时执行成功&#xff0c;要么同时执行失败。2.事务的特性 - ACID特性2.1原子性Atomicity原子性&#xff08;Atomicity&#xff09;&#xff1a;当前事务的操作要么同时成功&#xff0c;要么同时失败。原子性由undo log日志来…
阅读更多...
最新文章

Copyright @ 2022~2023