当前位置: 首页 > news >正文

线性表--链表-1

主要内容

  1. 链表基础练习题

一.链表练习题

1.设计一个递归算法,删除不带头结点的单链表 L 中所有值为 X 的结点

代码如下(示例):
f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点,
显然有f(L->next,x)的功能是删除以L->next 为首结点指针的单链表中所有值等于x 的结点。
由此,可以推出递归模型如下。
终止条件:f(L,x)=不做任何事情;    若L为空表
递归主体:f(L,x)=删除*L结点;f(L->next,x); 若L->data==xf(L,x)=f(L->next,x);  其他情况void Del_X_3(Linklist &L,ElemType x){//递归实现在单链表L中删除值为x的结点LNode *p; //p指向待删除结点if(L==NULL) //递归出口return;if(L->data==x){ //若L所指结点的值为Xp=L; //删除*L,并L=L->next;free(p);Del_X_3(L,x); //递归调用}else  //若L所指结点的值不为XDel_X_3(L->next,x);  //递归调用
}

2.设 L为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值

代码如下(示例):
void R Print(LinkList L){
//从尾到头输出单链表L中每个结点的值if(L->next!=NULL){ //递归R_Print(L->next);) //ifif(L!=NULL) print(L->data); //输出函数
}
void R_Ignore_Head(LinkList L){
if(L->next!=NULL) R_Print(L->next);
}

3.试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为 O(1).

代码如下(示例):
假设 pre、p和r指向3个相邻的结点,如下图所示。假设经过若干操作后,*pre 之前的结点的指针都已调整完毕,它们的 next 都指向其原前驱结点。现在令*p 结点的 next 域指向pre 结点,注意到一旦调整指针的指向,*p 的后继结点的链就会断开,为此需要用r 来指向原*p 的后继结点。处理时需要注意两点:一是在处理第一个结点时,应将其 next 域置为 NULL,而不是指向头结点(因为它将作为新表的尾结点);二是在处理完最后一个结点后,需要将头结点的指针指向它

在这里插入图片描述

LinkList Reverse(LinkList L){
//依次遍历线性表 L,并将结点指针反转INode *pre,*p=L->next,*r=p->next;p->next=NULL; //处理第一个结点while(r!=NULL){ //r为空,则说明p为最后一个结点pre=p; //依次继续遍历p=r;r=r->next;p->next=pre; //指针反转}L->next=p; //处理最后一个结点return L;
}

4.有一个带头结点的单链表 L,设计一个算法使其元素递增有序。

代码如下(示例):
算法思想:采用直接插入排序算法的思想,先构成只含一个数据结点的有序单链表,然后依次扫描单链表中剩下的结点*p (直至 p==NULL 为止),在有序表中通过比较查找插入*p 的前驱结点*pre,然后将*p 插入到*pre 之后,如下图所示。

在这里插入图片描述

void Sort(LinkList &L)(
//本算法实现将单链表L的结点重排,使其递增有序LNode *p=L->next,*pre;LNode *r=p->next; //r保持*p后继结点指针,以保证不断链微p->next=NULL; //构造只含一个数据结点的有序表p=r;while(p!=NULL)(r=p->next; //保存*p的后继结点指针pre=L;while(pre->next!=NULL&&pre->next->data<p->data)pre=pre->next; //在有序表中查找插入*p的前驱结点*prep->next=pre->next; //将*p插入到*pre之后pre->next=p;p=r; //扫描原单链表中剩下的结点}
}

5.设计一个算法用于判断带头结点的循环双链表是否对称

代码如下(示例):
算法思想:让 p从左向右扫描, 从右向左扫描,直到它们指向同一结点(p==g,当循环双链表中结点个数为奇数时)或相邻(p->next=g或g->prior=p,
当循环双链表中结点个数为偶数时)为止,若它们所指结点值相同,则继续进行下去,否则返回 0。若比较全部相等,则返回1int Symmetry(DLinkList L){
//本算法从两头扫描循环双链表,以判断链表是否对称DNode *p=L->next,*q=L->prior; //两头工作指针while(p!=q&&p->next!=g) //循环跳出条件if(p->data==q->data){ //所指结点值相同则继续比较p=p->next;q=q->prior;}else //否则,返回0return 0;return 1; //比较结束后返回1
}

6.有两个循环单链表,链表头指针分别为 h1和h2,编写一个函数将链表 h2 链接到链表h1 之后,要求链接后的链表仍保持循环链表形式

代码如下(示例):
算法思想:先找到两个链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起来,再使之成为循环的。LinkList Link(linklist &hl,LinkList ah2){
//将循环链表h2链接到循环链表h1之后,使之仍保持循环链表的形式LNode *p,*q; //分别指向两个链表的尾结点p=h1;while(p->next!=h1) //寻找h1的尾结点p=p->next;q=h2;while(q->next!=h2) //寻找h2的尾结点q=q->next;p->next=h2; //将h2链接到h1之后q->next=h1; //令h2的尾结点指向 h1return hl;
}

总结

以上是今天要讲的内容,练习了链表相关习题。

相关文章:

线性表--链表-1

文章目录 主要内容一.链表练习题1.设计一个递归算法&#xff0c;删除不带头结点的单链表 L 中所有值为 X 的结点代码如下&#xff08;示例&#xff09;: 2.设 L为带头结点的单链表&#xff0c;编写算法实现从尾到头反向输出每个结点的值代码如下&#xff08;示例&#xff09;: …...

WPF小知识

在编写WPF程序遇到一些小问题&#xff0c;所以记录起来&#xff0c;查其他方便。 Label自动换行 网上搜的都不能自动换行&#xff0c;发现使用Run 就可以。在脚本中直接调用labTip.Text进行赋值就可以了。 <Label Foreground"#FF9E9E9E" FontSize"16"…...

坐标系下的运动旋量转换

坐标系下的运动旋量转换 文章目录 坐标系下的运动旋量转换前言一、运动旋量物体运动旋量空间运动旋量 二、伴随变换矩阵三、坐标系下运动旋量的转换四、力旋量五、总结参考资料 前言 对于刚体而言&#xff0c;其角速度可以写为 ω ^ θ ˙ \hat {\omega} \dot \theta ω^θ˙&…...

Android Termux安装MySQL,通过内网穿透实现公网远程访问

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f516;系列专栏&#xff1a; C语言、Linux、Cpolar ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前…...

Python in Visual Studio Code 2023年11月发布

排版&#xff1a;Alan Wang 我们很高兴地宣布 Visual Studio Code 的 Python 和 Jupyter 扩展将于 2023 年 11 月发布&#xff01; 此版本包括以下公告&#xff1a; 改进了使用 Shift Enter 在终端中运行当前行弃用内置 linting 和格式设置功能对 Python linting 扩展的改进重…...

算法通关村——数字中的统计、溢出、进制转换处理模板

数字与数学基础问题 1、数字统计 1.1、符号统计 LeetCode1822. 给定一个数组&#xff0c;求所有元素的乘积的符号&#xff0c;如果最终答案是负的返回-1&#xff0c;如果最终答案是正的返回1&#xff0c;如果答案是0返回0. 这题其实只用看数组中0和负数的个数就好了&#x…...

ESP01S通过心知天气获取天气和时间信息

ESP01S通过心知天气获取天气和时间信息 设置STA模式 ATCWMODE1 连接wifi ATCWJAP"wifi名称","wifi密码"3.设置时间地域 ATCIPSNTPCFG1,8获取时间 ATCIPSNTPTIME?返回&#xff1a; CIPSNTPTIME:Fri Nov 17 17:09:22 2023 OK连接心知服务器 ATCIPSTAR…...

docker容器内core dumped却找不到core文件

1. 检查ulimit&#xff0c; 使用命令&#xff1a; ulimit -a rootb7c19f6da1e3:/usr# ulimit -a core file size (blocks, -c) unlimited data seg size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks…...

ubuntu提高 github下载速度

Github一般用于Git的远程仓库&#xff0c;由于服务器位于国外&#xff0c;国内访问速度比较慢&#xff0c;为了提高访问速度&#xff0c;决定绕过DNS域名解析。 获取Github的IP地址 按下ctrl&#xff0b;alt&#xff0b;T打开命令终端&#xff0c;输入&#xff1a; nslookup gi…...

Node.js之path路径模块

让我为大家介绍一下path路径模块吧&#xff01; 什么是path路径模块&#xff1f; path 模块是 Node.s 官方提供的、用来处理路径的模块。它提供了一系列的方法和属性&#xff0c;用来满足用户对路径的处理需求。 介绍三个关于path模块的方法&#xff1a; path.join() 方法&…...

TCP与UDP协议

TCP与UDP协议 1、TCP协议&#xff1a; 1、TCP特性&#xff1a; TCP 提供一种面向连接的、可靠的字节流服务。在一个 TCP 连接中&#xff0c;仅有两方进行彼此通信。广播和多播不能用于 TCP。TCP 使用校验和&#xff0c;确认和重传机制来保证可靠传输。TCP 给数据分节进行排序…...

“ /^A-Z:\\{1,2}^/:\*\?<>\|+\.(jpg|gif|png|bmp)$/i ”这个正则表达式的理解

这个正则表达式可以分解为以下几个部分&#xff1a; ^&#xff1a;这是一个开始符号&#xff0c;表示匹配必须从字符串的开始部分开始。/&#xff1a;这是一个斜杠符号&#xff0c;通常在正则表达式中用来表示特殊字符的转义。A-Z:&#xff1a;这部分表示匹配一个大写字母后跟…...

批量下载Sentinel数据脚本2023

批量下载Sentinel数据脚本2023 那些最好的程序员不是为了得到更高的薪水或者得到公众的仰慕而编程&#xff0c;他们只是觉得这是一件有趣的事情&#xff01; 批量下载Sentinel数据脚本2023 批量下载Sentinel数据脚本2023&#x1f33f;前言&#x1f33f;脚本地址&#x1f4e7;Su…...

lv11 嵌入式开发 ARM指令集中(伪操作与混合编程) 7

目录 1 伪指令 2 伪操作 3 C和汇编的混合编程 4 ATPCS协议 1 伪指令 本身不是指令&#xff0c;编译器可以将其替换成若干条等效指令 空指令NOP 指令LDR R1, [R2] 将R2指向的内存空间中的数据读取到R1寄存器 伪指令LDR R1, 0x12345678 R1 0x12345678 LDR伪指令可以将任…...

北邮22级信通院数电:Verilog-FPGA(10)第十周实验 实现移位寄存器74LS595

北邮22信通一枚~ 跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章 持续关注作者 迎接数电实验学习~ 获取更多文章&#xff0c;请访问专栏&#xff1a; 北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客 目录 一.代码部分 二.管脚分配 三.实现过程讲解及效…...

麒麟系统安装找不到安装源!!!!设置基础软件仓库时出错

记录--华为RH2288 V3服务器安装麒麟系统遇到的问题 1.遇到的问题--“设置基础软件仓库时出错”报错导致无法继续安装 没办法下一步 先说结论&#xff1a;系统bug 该问题在CentOS、Rocky Linux最新版中均存在 解决&#xff1a; &#xff08;一&#xff09;、如果是外网直接配…...

代码随想录算法训练营第三十九天【动态规划part02】 | 62.不同路径、63. 不同路径 II

62.不同路径 题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路&#xff1a; 动规五部曲 确定dp数组及其下标含义&#xff1a;dp[i][j] 表示从&#xff08;0,0&#xff09;出发&#xff0c;到&#xff08;i,j&#x…...

鸿蒙4.0开发笔记之DevEco Studio如何使用Previewer窗口预览器(一)

一、预览器作用 DevEco Studio预览器概况在HarmonyOS应用开发过程中&#xff0c;通过使用预览器&#xff0c;可以查看应用的UI效果&#xff0c;方便开发者实时查看应用的运行效果&#xff0c;随时调整代码。 二、打开Previewer预览器 1、正常启动 打开预览器的位置在DevEco…...

音视频转换软件Permute mac中文板特点介绍

Permute mac是一款Mac平台上的媒体格式转换软件&#xff0c;由Chaotic Software开发。它可以帮助用户快速地将各种音频、视频和图像文件转换成所需格式&#xff0c;并提供了一些常用工具以便于用户进行编辑和处理。 Permute mac软件特点 - 支持大量格式&#xff1a;支持几乎所…...

前端uniapp列表下拉到底部加载下一页列表【下拉加载页面/带源码/实战】

目录 一. 图片1.2. 二.list.vue三.uni-load-more.vue最后 一. 图片 1. 2. 二.list.vue <template><view><!--列表--><scroll-view scroll-y"true" class"scroll-Y" :style"height: scrollviewHigh px;" lower-threshol…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...

Spring AI中使用ChatMemory实现会话记忆功能

文章目录 1、需求2、ChatMemory中消息的存储位置3、实现步骤1、引入依赖2、配置Spring AI3、配置chatmemory4、java层传递conversaionId 4、验证5、完整代码6、参考文档 1、需求 我们知道大型语言模型 &#xff08;LLM&#xff09; 是无状态的&#xff0c;这就意味着他们不会保…...

Git 使用大全:从入门到精通

Git 是目前最流行的分布式版本控制系统&#xff0c;被广泛应用于软件开发中。本文将全面介绍 Git 的各种功能和使用方法&#xff0c;包含大量代码示例和实践建议。 文章目录 Git 基础概念版本控制系统Git 的特点Git 的三个区域Git 文件状态 Git 安装与配置安装 GitLinuxmacOSWi…...

CodeBuddy一腾讯内部已有超过 85% 的程序员正在使用de编程工具

大家好&#xff0c;我是程序员500佰&#xff0c;目前正在前往独立开发路线&#xff0c;我会在这里分享关于编程技术、独立开发、技术资讯以及编程感悟等内容。 如果本文能给你提供启发和帮助&#xff0c;还请留下你的一健三连&#xff0c;给我一些鼓励&#xff0c;谢谢。 本文直…...

SpringBoot3中使用虚拟线程的详细过程

在 Spring Boot 3 中使用 Java 21 的虚拟线程&#xff08;Virtual Threads&#xff09;可以显著提升 I/O 密集型应用的并发能力。以下是详细实现步骤&#xff1a; 1. 环境准备 JDK 21&#xff1a;确保安装 JDK 21 或更高版本Spring Boot 3.2&#xff1a;最低要求&#xff08;p…...