首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
已知非空链表A,其指针是list,链表中的结点由两部分组成:数据域data和指针域link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求: (1)给出算
admin
2017-01-04
72
问题
已知非空链表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月,发表《立宪法议》,首先提出君主立宪要求的是()。
文艺复兴运动兴起的时间是()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
1950年,人民政府开始全面调整工商业,采取了对私营工商业的加工订货、向农民收购土副产品、用协商方式解决劳资纠纷等措施。这些措施的主要任务是()
设某多道程序系统中有用户使用的内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执
随机试题
图2—11所示电路中,A1、A2为理想运算放大器,R1=R2=R3=R4=R,试求的值。
施工总承包方对所承包的建设工程承担施工任务的执行和组织的总的责任,其主要管理任务有()。
对设计概算编制依据的审查重点是()。
全球金融市场的发展趋势表现为()。Ⅰ.国际金融市场的一体化趋势Ⅱ.国际金融市场的证券化趋势Ⅲ.金融创新的趋势Ⅳ.全球货币统一的趋势
下列表述中,正确的有()。
在审计实施阶段,注册会计师可以将分析性复核直接作为实质性测试程序,以收集与账户余额和各类交易相关的特殊认定的证据。 ( )
社会接纳程度的评估方法主要有()。
试述我国的单一制国家结构形式。
MrMurdochbelievedthathispromotioncameSomepeoplethinkMrMurdochiscrazybecause
A、Becauseshefeelsveryhotintheroom.B、Becauseshewantstoavoidmeetingpeople.C、Becauseshewantstosmokeacigarette
最新回复
(
0
)