首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-01-16
58
问题
有两个集合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
学硕统考专业
相关试题推荐
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
“两个凡是”
中国共产党领导下的民族区域自治模式最早是在()。
下列不属于苏联战时共产主义政策内容的是()。
阅读下列材料,并回答问题:当时帝国地跨欧亚非三洲。地中海成为它的内湖。境内农业、手工业和商业发展起来,海路畅通无阻,陆路纵横交错、四通八达,促进了贸易发展,也有利于信息传递和军队调防。帝国同北欧、印度、中国都有贸易往来,中国的丝绸也传到帝国。原来较落后的
以下不属于国民党控制金融的“四行”的是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
两宋时期,不同地域曾出现濂、洛、关、阐等学术流派。北宋后期到南宋中期,王安石的新学成为影响最大的学派,这主要是由于()
下列选项中,控制了西域政权的是()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
随机试题
西周时期实行的国家基本制度是()。
《麦坚利堡》这首诗的格调是()
急性梗阻性化脓性胆管炎临床表现是
五行分类中不属于金的是
在建设项目负责人的领导方式中,其中就一般情况而言()领导风格的效果是比较好的。
下列属于网络市场直接调研的方法有()。
“为充分保护投资者的利益,企业必须在有可供分配留存收益的情况下才进行收益分配”所体现的分配原则是()。
土地革命战争时期,毛泽东同志以马克思主义为指导,发表了《中国的红色政权为什么能够存在?》、《井冈山的斗争》、《星星之火,可以燎原》、《反对本本主义》等重要著作,这些著作()。
某地召开有关《红楼梦》的小型学术研讨会。与会者中,4个是北方人,3个是黑龙江人,1个是贵州人;3个是作家,2个是文学评论家,1个是教授;以上提到的是全体与会者。根据以上陈述,参加该研讨会的最少可能有几人?最多可能有几人?
Theoutlookfromthetopofthemountainisbreathtaking.
最新回复
(
0
)