首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
admin
2017-01-04
55
问题
已知非空链表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
学硕统考专业
相关试题推荐
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
广西壮族自治区的设立时间是()。
解析两个战场的地位、作用及相互关系。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
院系调整
中共八届九中全会提出的恢复和调整国民经济的方针是()。
罗斯福新政的中心措施是对()的调整。
设某多道程序系统中有用户使用的内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执
随机试题
根本的,激进的a.r______
深Ⅱ度烧伤,烧伤深度可达
易受光线影响而变质的药品是需在冷处贮存的药品是
水泥混凝土拌和站基本组成一般不包括()。
从损益表来看,()可能影响企业的收入支出,进而影响企业的借款需求。
金融市场上有固定的货币资金供应者和需求者,并且角色不会发生变化。()
工资项目的预算首先应当分析当地政府有关部门本年度发布的()对工资预算的影响,如有变化应进行必要的调整。(2005年5月三级真题)
Weallhavetimeswhensomeonedoessomethingtosupportyou.Youaregratefulfortheir【C1】______gesture.Andthenyoumoveon
美国学制类型是()。
2010年,福建省全年进出口总额1087.82亿美元,比上年增长36.6%。其中,出口714.97亿美元,增长34.1%;进口372.86亿美元,增长41.6%。批准设立外商直接投资项目1139个,比上年增长21.3%。其中.合同外资金额121
最新回复
(
0
)