首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2019-01-16
66
问题
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
选项
答案
(1)算法的基本设计思想:本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后,从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 (2)算法设计如下: typedef struct LNode{ int data; struct LNode*link; }*linkedlist; LinkedList LinkListSort(LinkedList list){ Lnode*p,*q: P=list->link: //p是工作指针,指向待排序的当前元素 list一>link=null: //假定第一个元素有序,即链表中现只有一个结点 while(P!=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/6aRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
蒙古三次西征,先后率军的大汗是()。
文艺复兴运动兴起的时间是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
中华人民共和国恢复在联合国合法席位的时间是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
系统阐明社会主义初级阶段理论是在()。
编写判定给定的二叉树是否是二叉排序树的函数。
随机试题
张老师积极参加学校的教学改革研究活动。经过一段时间的酝酿,他确定了“中国儿童教育发展研究”这一课题。这样的选题违背了教育研究选题的()。
属于高效消毒剂的是()。
_______过程是决策的组织落实过程。
试述社会进步的统一性和多样性的关系原理及其现实意义。
女性,50岁,因风湿性关节炎长期服用布洛芬(芬必得)6年,尿检出现尿糖(+),pH值7.0,血Na+130mmol/L,K+3.2mmol/L,尿氯化铵试验pH5.0,尿NaCO3再吸收试验FE一HCO3—17%。诊断考虑
进入阴毛中,环绕阴器,上达小腹的经脉是
借款合同的法律特征主要体现在()。
春秋时期,有人强调“日困而还,月盈而匡”。这一说法体现了()。
按照刑法的规定,不得假释的犯罪分子包括()。
Usingtheinformationinthetext,completeeachsentence14-18withanexpressionfromthelistbelow.Foreachsentence(14
最新回复
(
0
)