首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2018-08-12
51
问题
有一个不带头结点的单链表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
学硕统考专业
相关试题推荐
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后,美国创立了资产阶级共和制度③地理位置优越,远离动乱的欧洲④拥有潜在的广阔的国内市场
“两个凡是”
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
下列选择中,()不是操作系统关心的主要问题。
高度为7的AVL树最少有()个结点。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
随机试题
全身麻醉患者完全清醒的标志是
下列哪一项不是清营汤证的临床表现
工程项目管理的目标是()、()、()和()去满足或超出工程项目各利害关系者的要求和期望。
携带植物种子、种苗以及其他繁殖材料进境的( )。
单位活期存款账户包括()。
()是指组织中职位等级的数目。
给长方形的长增加2,宽增加5恰好可以得到一个面积为100的正方形,则原长方形的周长是()。
列宁说:“没有革命的理论,就没有革命的运动。”这一命题的含义是
在微机中,西文字符所采用的编码是()。
Theydonotthrowlavishparties.Theireditorsarenotimmortalisedinfilms.ButthemagazinesputoutbyBritain’ssupermarke
最新回复
(
0
)