首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2018-08-12
25
问题
有一个不带头结点的单链表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
学硕统考专业
相关试题推荐
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
全国高校院系调整的具体时间是()。
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
北约和华约两个组织对峙近半个世纪,其影响是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
操作系统采用页式存储管理方法,要求()。
随机试题
在报火警时,应当精简清晰地说明火灾发生情况和火灾信息,其中不包含的是()。
()是指由梁和柱以刚接或铰接相连接成承重体系的房屋建筑结构。
随着孩子的长大,他们往往能比成年人更快地接受新的社会信息,会把他们的文化传递给自己的父辈,社会学学者把这一影响作用称为___________。
税收收入的来源;即各种税收收入的最终出处,称为()
何谓目标监测?
在我国上消化道出血最常见的病因是
头围是指自眉弓上方最突出处,经枕后结节绕头的周长。()
()队成为首支进入亚冠足球联赛决赛的中超球队。
社会体育,是由企业、事业单位职工,国家机关工作人员,以及城镇或农村居民等不同的群体,为达到健身、健心、健美、娱乐、医疗等目的而进行的内容丰富、形式多样的身体锻炼活动。根据上述定义,以下哪项活动不是社会体育活动?
以下民事法律关系中属于物权法律关系的是()。
最新回复
(
0
)