首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-01-16
47
问题
有两个集合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
学硕统考专业
相关试题推荐
清代医学家()强调解剖学对医病的重要性,并通过亲自对尸体的解剖,绘制成《亲见改正脏腑图》25种。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
中国共产党领导下的民族区域自治模式最早是在()。
论述赫鲁晓夫改革的背景、主要内容及作用。
全国高校院系调整的具体时间是()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
以下()协议完成了从网卡到IP地址的映射。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
编写判定给定的二叉树是否是二叉排序树的函数。
随机试题
在D盘下新建一个Excel工作簿,完成以下操作:(1)在Sheet1工作表的A1:H6区域中建立和编辑如表所示的数据表。(2)设置“班级学习成绩表”为居中、加粗、字号20,“高一”、“高二”和“高三”为居中、加粗、字号16,各班级标题居中、加粗,其余
静脉回流的影响因素,包括
类风湿关节炎最早侵犯的关节是
某城市小学投资700万元建设教学楼,组织工程施工公开招标,招标文件规定投标人应具备的资格条件中,正确合理的是()。
根据《测绘法》,省、自治区、直辖市和自治州、县、自治县、市行政区域界线的标准画法图,由()拟订,报国务院批准后公布。
在下列给出的投资方案评价方法中,可用于计算期不同的互斥型方案评价的动态方法是()。
Whatdoesthefutureholdfortheproblemofhousing?Agood(1)_____depends,ofcourse,onthemeaningof"future".Ifoneis
现代计算机中采用二进制码,下列选项中不是它的优点是
Thecurrentadministration,beingworriedoversomeforeigntradebarriersbeingremovedandourexportsfailingtoincreaseas
NicholasChauvin,aFrenchsoldier,airedhisvenerationofNapoleonBonaparteso______andunceasinglythathebecamethelaug
最新回复
(
0
)