首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-01-16
42
问题
有两个集合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
学硕统考专业
相关试题推荐
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读以下史料,并回答问题:初,范阳祖逖,少有大志,与刘琨俱为司州主簿,同寝,中夜闻鸡鸣,蹴琨觉,曰:“此非恶声也!”因起舞。及渡江,左丞相睿以为军谘祭酒。逖居京口,纠合骁健,言于睿曰:“晋室之乱,非上无道而下怨叛也,由宗室争权,自相鱼肉,遂使戎狄乘隙,毒
西周统治者提出的天命思想和与此相应的治国思想分别为()。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
下列关于《凡尔赛和约》的说法,全部错误的是()。①《凡尔赛和约》中不许德国设防区是莱茵河西岸50公里以内区域②《凡尔赛和约》中,战胜国处置德国的全部海外殖民地的方式是“托管制”③和约有关德国疆界问题,把原属波兰的领上基本上归还波兰④
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱,其基本理由是他们()
系统阐明社会主义初级阶段理论是在()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
随机试题
私募基金管理人自成为中国投资基金业协会的观察会员之日起()年,同时符合资产管理规模标准和合规经营目标的,可以申请成为普通会员。
肌肉兴奋-收缩耦联的关键因素是()
管理者考评应符合的要求是()。
病变区巩膜呈紫红色,形成结节样隆起的巩膜炎类型是
地图以概括、抽象的形式反映出制图对象的带有规律性的类型特征,而将那些次要、非本质的物体舍弃,这个过程称为制图综合。()是制图综合对制图现象进行的两种基本处理。
利息是资金时间价值的一种重要表现形式,通常用( )作为衡量资金时间价值的相对尺度。
唐先生月薪8000元,按规定月均缴纳三险一金1500元。在不考虑其他减免税的情况下,唐先生在2016年8月工资薪金所得的应纳税所得额为()元。
西欧封建制度确立于()。
坚持集体教育就不能考虑个人情况。()
如果劳动的边际产值大于工资率,可能是因为()。
最新回复
(
0
)