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

2019_41 考研408

2019年(单链表)

41.(13分)设线性表

采用带头结点的单链表保存,链表中的结点定义如下:

typedef struct node {

int data;

struct node* next;

}NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L'=(q,a,,a,an-1,as,an-2y…)。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

(3)说明你所设计的算法的时间复杂度。

思路:因为题目要求要空间复杂度为O(1),所以我们不能再额外申请空间了,然后再找到链表的中间结点,将其一分为二,分为L和L2的单链表,并将L2链表进行原地逆置,最后再将L和L2进行混合合并。

一、找到中间结点,并一分为二。

思路:定义两个指针p1和p2,p1指针每次走两步,p2指针每次走一步,当p1指针走到最后,p2指针必定走到中间结点。(写代码的过程中还应该注意总结点是奇数还是偶数)

代码段:

void find_middle(LinkList L,LinkList &L2)        //寻找链表中间结点,并设置好L2链表 
{L2 = (LinkList)malloc(sizeof(LNode));    //设置第二条链表的头结点 LinkList pcur,ppre;                        //双指针法,pcur跨两步,ppre跨一步。 ppre = pcur = L->next;    //一开始都指向第一个结点,即首元结点 while(pcur)        {pcur = pcur->next;if(pcur == NULL)    //防止pcur为空 {break;}pcur = pcur->next;    //若此处pcur为空,则不满足循环条件 if(pcur == NULL)    //为了使得偶数个,ppre依然指向a1,a2到a6中的a3结点 {break;}ppre = ppre->next;}L2->next = ppre->next;    //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre->next = NULL;     //此时的ppre为前一半链表的最后一个结点,最后一个结点的指针域应该为NULL     
}

二、将L2原地逆置

思路:分别定义3个指针r、s、t,让r、s、t分别指向前三个结点,再让第二个结点指向第一个结点,然后r、s、t同时向后移动一位,再让第三个结点指向第二个结点,然后r、s、t同时向后移动一位,如此往复循环,当t为null时循环结束。因为原有链表的头结点变成链表最后一个结点,最后一个结点应该指向NULL,最后让L2头结点指向新的首元结点s。

代码段:

void reverse(LinkList L2)    //逆转。因为L2的头结点不会发生改变 
{LinkList r,s,t;r = L2->next;    //一开始r指向首元结点 if(r == NULL){return ;//链表为空 }s = r->next;    //一开始r指向s if(s == NULL){return;//链表只有1个结点    } t = s->next;    //一开始让s指向twhile(t){s->next = r;    //原地逆置,让s指向r r = s;            //以下3句,是3个指针同时向后移动一位 s = t;t = t->next; } s->next = r;L2->next->next = NULL;//逆置后,原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2->next = s;    //此时s是逆置后链表的第一个结点,L2的头结点应该指向它 
}

三、将L与L2进行混合合并

思路:将L与L2链表合并,合并时分别轮流放入一个结点。定义3个指针pc、p、q,一开始指针pc指向L链表的首元结点,指针p指向L链表的第二结点,指针q指向L2链表的首元结点。并且让pc指针始终指向合并后新链表的尾部,使用p指针始终指向链表L待放入的结点,q指针始终指向链表L2待放入的结点。

代码段:

void merge(LinkList L,LinkList L2)    //将L与L2混合并合并 
{LinkList  pcur,p,q;pcur = L->next;    //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p = pcur->next;    //p指向L链表的第二个结点。p用来遍历L链表。 q = L2->next;    //q指向L2链表的首元结点。q用来遍历L2的链表。 while(p!=NULL && q!=NULL)    //以下步骤画图,就会非常的直观。 {pcur->next = q;q = q->next;pcur = pcur->next;pcur->next = p;p = p->next;pcur = pcur->next;    } //任何一个链表都可能剩余一个结点,放进来即可。 if(p!=NULL){pcur->next = p;}if(q!=NULL){pcur->next = q;}
}

总代码:

#include<stdio.h> //2019年考研408真题,第41题 
#include<stdlib.h>typedef int ElemType;
typedef struct LNode{ElemType data;        //数据域 struct LNode *next;    //指针域 
}LNode,*LinkList;void list_tail_insert(LinkList &L)    //尾插法建立链表 
{L = (LinkList)malloc(sizeof(LNode));L->next = NULL;ElemType x;scanf("%d",&x);LNode *s;//用来指向申请的新结点LNode *r=L;//r始终指向链表尾部while(x != 999){s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;    //r->next指向s结点r = s;            //r要指向新的尾部 scanf("%d",&x); } r->next = NULL;    //让尾结点的next为NULL 
}void find_middle(LinkList L,LinkList &L2)        //寻找链表中间结点,并设置好L2链表 
{L2 = (LinkList)malloc(sizeof(LNode));    //设置第二条链表的头结点 LinkList pcur,ppre;                        //双指针法,pcur跨两步,ppre跨一步。 ppre = pcur = L->next;    //一开始都指向第一个结点,即首元结点 while(pcur)        {pcur = pcur->next;if(pcur == NULL)    //防止pcur为空 {break;}pcur = pcur->next;    //若此处pcur为空,则不满足循环条件 if(pcur == NULL)    //为了使得偶数个,ppre依然指向a1,a2到a6中的a3结点 {break;}ppre = ppre->next;}L2->next = ppre->next;    //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre->next = NULL;     //此时的ppre为前一半链表的最后一个结点,最后一个结点的指针域应该为NULL     
}                            void reverse(LinkList L2)    //逆转。因为L2的头结点不会发生改变 
{LinkList r,s,t;r = L2->next;    //一开始r指向首元结点 if(r == NULL){return ;//链表为空 }s = r->next;    //一开始r指向s if(s == NULL){return;//链表只有1个结点    } t = s->next;    //一开始让s指向twhile(t){s->next = r;    //原地逆置,让s指向r r = s;            //以下3句,是3个指针同时向后移动一位 s = t;t = t->next; } s->next = r;L2->next->next = NULL;//逆置后,原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2->next = s;    //此时s是逆置后链表的第一个结点,L2的头结点应该指向它 
}void merge(LinkList L,LinkList L2)    //将L与L2混合并合并 
{LinkList  pcur,p,q;pcur = L->next;    //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p = pcur->next;    //p指向L链表的第二个结点。p用来遍历L链表。 q = L2->next;    //q指向L2链表的首元结点。q用来遍历L2的链表。 while(p!=NULL && q!=NULL)    //以下步骤画图,就会非常的直观。 {pcur->next = q;q = q->next;pcur = pcur->next;pcur->next = p;p = p->next;pcur = pcur->next;    } //任何一个链表都可能剩余一个结点,放进来即可。 if(p!=NULL){pcur->next = p;}if(q!=NULL){pcur->next = q;}
}void print_list(LinkList L)        //打印输出链表 
{L = L->next;while(L != NULL){printf("%3d",L->data);L = L->next;}printf("\n");
}int main()
{LinkList L;    //L是头指针 LinkList search;    //用来存储拿到的某一个结点 list_tail_insert(L);    //输入数据可以为数据 print_list(L);//链表打印LinkList L2=NULL;    find_middle(L,L2); //寻找中间结点,并返回第二条链表 。只有一个结点时,L2中是没有结点的 printf("-----------------------------\n");print_list(L);print_list(L2);printf("-----------------------------\n");reverse(L2);print_list(L2);printf("-----------------------------\n");merge(L,L2);free(L2);print_list(L);return 0; 
}

相关文章:

2019_41 考研408

2019年(单链表)41.(13分)设线性表采用带头结点的单链表保存&#xff0c;链表中的结点定义如下:typedef struct node {int data;struct node* next;}NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法&#xff0c;重新排列L中的各结点&#xff0c;得到线性表L(q,a,,a,an…...

Linux账号与用户组

目录 用户标识符&#xff1a;UID与GID 用户账号 /etc/passwd文件结构 1、账号名称 2、密码 3、UID 4、GID 5、用户信息说明栏 6、家目录 7、shell /etc/shadow文件结构 1、账号名称 2、密码 3、最近修改密码的日期 4、密码不可被修改的天数&#xff08;与第三字…...

有趣的Hack-A-Sat黑掉卫星挑战赛——定位卫星Jackson

国家太空安全是国家安全在空间领域的表现。随着太空技术在政治、经济、军事、文化等各个领域的应用不断增加&#xff0c;太空已经成为国家赖以生存与发展的命脉之一&#xff0c;凝聚着巨大的国家利益&#xff0c;太空安全的重要性日益凸显[1]。而在信息化时代&#xff0c;太空安…...

JAVA集合专题3 —— vector + LinkedList + Set

目录vector的特点LinkedList底层结构模拟双向链表比较ArrayList和LinkedListSet接口基本介绍Set接口的遍历方式Set接口实现类对象的特点Set接口实现类HashSet模拟HashSet/HashMap的底层结构vector的特点 Vector底层是一个对象数组Vector是线程同步的&#xff0c;即线程安全的&…...

Scout:一款功能强大的轻量级URL模糊测试与爬取工具

关于Scout Scout是一款功能强大的轻量级URL模糊测试与爬取工具&#xff0c;可以帮助广大研究人员进行URL模糊测试&#xff0c;并爬取目标Web服务器中难以扫描发现的VHSOT、文件和目录等资源。 项目中包含了一个完整的字典文件&#xff0c;并尽可能地提供了更多的便携性&#…...

leaflet 解决marker呈现灰色边框的问题

第052个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet示例中处理marker外面有灰色边框的问题,请看未处理会后的图片。 处理后的结果非常满意,不再显示灰色边框。处理方法参考源代码。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意…...

MySQL JSON类型字段的查找与更新

MySQL 提供了丰富的函数用于 JSON 类型字段的查找与更新&#xff0c;详见官方文档。 创建一个表 t1&#xff0c;basic_info 字段为JSON类型: CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT,basic_info json DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB DEFAULT CH…...

element Ui树状图控件 spring boot Vue 实现角色授权功能

目录 前言&#xff1a; 二. element ui 2.1官网提供的核心代码 三.表结构 ​编辑 四.后端 4.1功能分析 4.2实体类 4.3 查询全部权限显示的结果 4.2修改角色权限的后台方法 五.vue 5.0代码总览 5.1树形图 5.2所需要的绑定数据 5.3所需方法 前言&#xff1a; 先上图…...

已解决sc delete MongoDB卸载MongoDB拒绝访问。

已解决sc delete MongoDB卸载MongoDB拒绝访问。 文章目录报错问题报错翻译报错原因解决方法联系博主免费帮忙解决报错报错问题 粉丝群里面的一个小伙伴遇到问题跑来私信我&#xff0c;想卸载MongoDB数据库&#xff0c;但是发生了报错&#xff08;当时他心里瞬间凉了一大截&…...

python的opencv操作记录11——阈值分割

文章目录传统图像处理分割阈值分割一个应用场景opencv库中的阈值分割固定阈值THRESH_OTSU 大津法阈值自适应阈值传统图像处理分割 现在提到图像分割&#xff0c;很多人会直接想到当前火爆的深度学习的各种分割网络&#xff0c;比如实例分割&#xff0c;语义分割等。其实在传统…...

Python-项目实战--飞机大战-英雄登场(7)

目标设计英雄和子弹类使用pygame.key.get_pressed()移动英雄发射子弹1.设计英雄和子弹类1.1英雄需求游戏启动后&#xff0c;英雄出现在屏幕的水平中间位置&#xff0c;距离屏幕底部120像素英雄每隔0.5秒发射一次子弹&#xff0c;每次连发三枚子弹英雄默认不会移动&#xff0c;需…...

寒假安全作业nginx-host绕过实例复现

1.测试环境搭建 LNMP架构的话&#xff0c;肯定就是linux、nginx、mysql、php四大组件。在后面的复现中我们还会用到https的一部分知识&#xff0c;故这里的nginx就需要使用虚拟主机并且配置https证书&#xff0c;且具有php解析功能。 1.1 基础nginx配置 #1.创建web目录 mkdir …...

RocketMQ-消息消费模式 顺序消费

RocketMQ-消息消费模式 顺序消费RocketMQ-消息消费模式集群模式集群模式的演示(本身就默认)Rocketmq存储队列广播模式顺序消费如何改实现顺序消费RocketMQ-消息消费模式 集群模式 在消费模式为集群的情况下,如果机器是集群的,消息只会给集群中的其中一台机器消费到 集群模…...

一、Java并发编程之线程、synchronized

黑马课程 文章目录1. Java线程1.1 创建和运行线程方法一&#xff1a;Thread方法二&#xff1a;Runnable&#xff08;推荐&#xff09;lambda精简Thread和runnable原理方法三&#xff1a;FutureTask配合Thread1.2 查看进程和线程的方法1.3 线程运行原理栈与栈帧线程上下文切换1.…...

12.hadoop系列之MapReduce分区实践

本文我们学习MapReduce默认分区以及自定义分区实践 当我们要求将统计结果按照条件输出到不同文件(分区)&#xff0c;比如按照统计结果将手机归属地不同省份输出到不同文件中(分区) 1.默认Partitioner分区 public class HashPartitioner<K, V> extends Partitioner<…...

有了独自开,一个人就是一个团队

文章目录 简单介绍优点 优秀案例平台福利总结 简单介绍 独自开是一个基于商品与服务交易全流程的PaaS开发平台。对于开发者&#xff0c;独自开可以协助开发者一个人独自开发一套系统。 优点 独自开有独创的分层标准化平台架构&#xff0c;可以满足系统的任何个性化需求。 …...

web期末复习 2023.02.11

文章目录Web 的概念Web 组成用户通过浏览器请求资源的过程:HTML 超文本标记语言CSS插入样式表的方法有三种:对象&#xff0c;类&#xff0c;实例一个完整的 JavaScript 实现是由以下 3 个不同部分组成的&#xff1a;JavaScript 用法什么是 Java Server Pages?JSP 注释JSP 的 J…...

第44章 用户密码实体及其约束规则的定义实现

1 说明&#xff1a; 由当前程序需要兼容实现多种用户密码的加密操作&#xff0c;所以必须把“CustomerPassword”定义为实体类&#xff0c;该类用于用于把加密方式、密钥及其加密后的密码持久化到“CustomerPassword”表中&#xff0c;以便用为用户登录操作提供验证支撑。 如果…...

聊聊并发与锁

持续坚持原创输出&#xff0c;点击蓝字关注我吧1.并发与并行并发可以充分地利用 CPU 资源&#xff0c;一般都会使用多线程实现。多线程的作用是提高任务的平均执行速度&#xff0c;但是会导致程序可理解性变差&#xff0c;编程难度加大。关于对并发与并行的概念&#xff0c;大家…...

开源项目 —— 原生JS实现斗地主游戏 ——代码极少、功能都有、直接粘贴即用

目录 效果如下 目录结构 GameEntity.js GrawGame.js konva.min.js PlayGame.js veriable.js index.html 结语&#xff1a; 前期回顾 卡通形象人物2 写代码-睡觉 丝滑如德芙_0.活在风浪里的博客-CSDN博客本文实现了包含形象的卡通小人吃、睡、电脑工作的网页动画https://…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...