首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2018-08-12
43
问题
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或.Java语言描述算法,关键之处给出注释。
选项
答案
(1)算法的基本设计思想:本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后,从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 (2)算法设计如下: typedef struct LNode{ int data; struct LNode * link; } * linkedlist; LinkedList Link ListSort(LinkedList list) { Lnode * p,*q: p=list->link; //p是工作指针,指向待排序的当前元素 list->link=null; //假定第一个元素有序,即链表中现只有一个结点 while(p!=2 null) { r=p一>link; //r是p的后继 q=list; if(q一>data>p->data) { //处理待排序结点p比第一个元素结点小的情况 p一>link=list; list=p; //链表指针指向最小元素 } else{ //查找元素值最小的结点 while(q一>link==null&&q一>link一>data
data) q=q一>link; p一>link=q一>link; //将当前排序结点链入有序链表中 q一>link=p; } p=r: //p指向下个待排序结点 } }
解析
转载请注明原文地址:https://kaotiyun.com/show/ncRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
Whatproductdotheysell?
胆红素主要来源于()。
中国人最常见的病毒性肝炎是()。
计入产品成本的费用包括()。
根据下列资料回答86~90题2007年全国粮食种植面积10533万公顷,比上半年增加70万公顷;棉花种植面积559公顷,增加7公顷;油料种植面积1094万公顷,减少60万公顷;糖料种植面积167万公顷,增加10万公顷。全国2007年粮食产量50
(2016河南)某人走失了一只小狗,于是开车沿路寻找,突然发现小狗沿路边往反方向走,车继续行30秒后,他下车去追小狗,如果他的速度比小狗快3倍、比车慢3/4,问他追上小狗需要多长时间?
甲是公安局局长,乙是公安局刑侦大队大队长,乙有一套闲置房子欲以市价1000万元出售,甲得知后让乙以500万元卖给自己,乙不得不照办。1个月后甲调到外省,乙极其后悔。关于本案下列说法正确的是()
国际格局走向多极化,是时代进步的要求,符合各国人民的利益。世界多极化格局有利于
______isaprincipalrepresentativeofTheLondonSchool.
书法和绘画在早期的皇权时代,书法和绘画是上层社会最为尊崇的艺术,大部分是由业余爱好者创作的,这些业余爱好者通常是有充足的闲暇时间来对笔法和画法进行技术和鉴赏完善的贵族和士大夫。书法被认为是最高等、最纯洁的绘画形式。晋朝时,人们开始欣赏绘画的美丽,
最新回复
(
0
)