首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
admin
2017-01-04
69
问题
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
选项
答案
(1)算法的基本设计思想:首先要查找最小值结点。将其移到链表最前面,实质上是将该结点从链:上摘下(不是删除并回收空间),再插入到链表的最前面。 (2)算法的实现如下: typedef struct LNode{ char data; struct LNode*link; }*Linkedlist; LinkedList delinsert(LinkedList list){ //将链表中数据域值最小的那个结点移到链表的最前面 Linkedlist*P,*pre,*q; P=list一>link: //p是链表的工作指针 pre=list; //pre指向链表中数据域最小值结点的前驱 q=P; //q指向数据域最小值结点,初始假定是第一结点 while(p一>link!=null){ if(p一>link一>data<q一>data){pre=P;q=p一>link;} //找到新的最小值结点 p=p一>link; } if(q!=list一>link){ //若最小值是第一元素结点,则不需再操作 pre一>link=q一>link://将最小值结点从链表上摘下 q一>link=list一>link; //将q结点插到链表最前面 list一>link=q; } }//算法结束
解析
转载请注明原文地址:https://kaotiyun.com/show/ehRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
下列改革内容不是在《天朝天亩制度》中提出的一项是()
解析两个战场的地位、作用及相互关系。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
“瓜步之战”发生在下列哪两个政权之间?()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
苏联实行的新经济政策与美国推行的罗斯福新政之间的相似之处是()。①面临极为困难的经济形势②最主要内容是调整和复兴工业③国家颁布法令强制干预经济④通过发展商品经济生产来恢复农业
1950年,人民政府开始全面调整工商业,采取了对私营工商业的加工订货、向农民收购土副产品、用协商方式解决劳资纠纷等措施。这些措施的主要任务是()
随机试题
膨胀机启机前应先进行节流制冷,使温度达到()K左右时,启动膨胀机。
属于公共利益集团的有________、________、________。
A.炭疽芽孢杆菌B.布鲁菌C.肉毒梭菌D.鼠疫耶尔森菌E.破伤风梭菌是可以产生外毒素的革兰阴性菌()
某重度急性发作的支气管哮喘患者,其首选药物是
(2007年)在麦克斯韦速率分布律中,速率分布函数f(v)的意义可理解为()。
现浇混凝土墩台混凝土分层分段对称浇筑时,各段的浇筑应到距模板上缘()mm处为止。
客户的下列信息中,属于财务信息的是()。
从中国银行证监会成立之日起,中国人民银行不再行使银行业金融机构的监督管理权。()
某幼儿园中班把班里每个孩子的体检结果公布在教室门口,上面除了身高体重等项目外,还包括血液检查结果等内容。该幼儿园的做法()。
某居民小区位于市郊区外环线边缘,小区内有住户1840户,常住居民5300多人,基本上都是二十世纪五六十年代支边支农回城的人员、动迁人员和外地入住人员。小区人员有三大特点:一是无业和生活困难的居民多;二是六十岁以上的老人多;三是外来人员多。小区所在社区接上级
最新回复
(
0
)