首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
admin
2017-01-04
50
问题
已知非空链表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年,人民政府开始全面调整工商业,采取了对私营工商业的加工订货、向农民收购土副产品、用协商方式解决劳资纠纷等措施。这些措施的主要任务是()
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
随机试题
末乳是指牛停止产乳前一周左右所分泌的乳,末乳带有微咸、苦味和油脂氧化气味。
如何处理遥控器失灵故障?
《背影》的作者是()
显影液中不包括的物质是
《检察官法》规定的不能担任检察官的条件有()。
违法事实确凿并有法定依据,对公民处以50元以下、对法人或者其他组织处以()元以下罚款或者警告的行政处罚的,可以当场作出处罚决定。
关于证券交易结算流程中的清算环节,下列表述正确的有()。
有氧运动:燃烧脂肪()。
AncientGreekphilosopherAristotleviewedlaughteras"abodilyexerciseprecioustohealth."But【B1】______someclaimstothe
关于VisualBasic“方法”的概念错误的是
最新回复
(
0
)