首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2018-08-12
48
问题
有一个不带头结点的单链表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)完成功
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
随机试题
在氯苯硝化生产一硝基氯化苯生产车间,收率为92%,选择性为98%,则氯化苯的转化率为()。
简述网上营销渠道设计应注意的问题。
由于小动脉扩张而使流人局部组织或器官中的血量增多的现象,称
辐射对人体危害很大,其中()属电离辐射。
在作业场所中可能接触的电磁辐射包括非电离辐射、电离辐射。下列电磁辐射中,属于电离辐射的是()。
洋务运动是在19世纪60年代初清政府镇压太平天国起义的过程中和第二次鸦片战争结束后兴起的。洋务派主张学习西方武器装备和科学技术,以“自强”“求富”为目标,兴办的洋务事业有()
Thedawnoftheoilagewasfairlyrecent.AlthoughthestuffwasusedtowaterproofboatsintheMiddleEast6,000yearsago,e
下列选项中,哪些是按照文件的物理结构划分的文件分类?()
输入/输出端口有两种编址方法,即I/O端口与存储器单元统一编址和I/O端口单独编址。前一种编址的主要优点是【 】,后一种编址的主要优点是专用I/O指令字节数少,指令执行快和不占用存储空间。
Themostconsistentlyidentifiedteachereffectivenessvariableistimeontask.Thatis,themoretimethatstudentsspendon
最新回复
(
0
)