首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-01-16
41
问题
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。
选项
答案
(1)算法的基本设计思想:分别从A、B的头结点开始,依次比较A、B中元素的内容,如果A中的元素值大于B中的元素值,则将B中的结点插入结果链表,反之将A中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此,如果A、B中两个元素值相同,只将其中的一个加入结果链表。 (2)算法的设计如下: typedef struct LNode{ int data; struct INode*next; }* Linkedlist; LinkedList union(IAnkedList la,lb){ pa=la一>next; pb=lb一>next; //设工作指针pa和pb pc=la; //pc为结果链表当前结点的前驱指针 while(pa&&pb){ if(pa->data
data){ pc->next=pa; pc=pa; pa=pa->next } else if(pa->data>pb->data){ pc->next=pb; pc=pb; pb=pb一>next; } else{ //处理pa一>data=pb一>data. pc->next=pa: pc=pa; pa=pa一>next; u=pb; pb=pb一>next; flee(u); } } if(pa)pc一>next=pa; //若la表未空,则链入结果表 else pc->next=pb; //若lb表未空,则链入结果表 free(lb): //释放lb头结点 return(1a); } (3)本题中的主要操作是依次比较A、B链表中的数据元素值的大小,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/ciRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
新文化运动把斗争矛头指向了儒家传统道德,是因为()
“两个凡是”
斯大林模式的突出特点是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
毛泽东提出“政权是由枪杆子中取得的”论段是在()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
随机试题
从人对现实世界的认识出发,将具体事物抽象为便于理解和研究的模型,称为()
红细胞沉降率加速主要是由于
A.透明管型B.蜡样管型C.上皮细胞管型D.白细胞管型E.红细胞管型急性肾盂肾炎时尿中常见
化痰药治痰证时最常配伍的是
公路水运工程施工企业分管生产安全负责人是本单位安全生产工作的()责任人。
下列项目中属于企业所得税暂行条例规定的应计入收入总额的有()。
石窟属于一种独特的寺庙形式,是专供佛教徒修行礼拜的场所,通常它的内部是用()进行装饰的。
乙建筑公司向甲建材公司发出传真,表示“急需0号水泥100吨”。甲公司收到传真后,立即回电表示没问题,并开始安排货源。但三日后,当甲公司询问如何发货时,乙公司表示已经购得,不再需要该种水泥。双方发生争议,甲公司诉至法院。[中财2014年研]根据上述
(75)________________makescomputersabletodojobswhichtillnow,onlyhumanbrainscando.
A、Givingnecessitytothehomelesswithfriends.B、Helpingdeliveringpackagesinthepostoffice.C、Takinggoodstothelocaln
最新回复
(
0
)