首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2019-01-16
31
问题
有一个不带头结点的单链表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
学硕统考专业
相关试题推荐
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
中华人民共和国恢复在联合国合法席位的时间是()。
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
印加人记载事物使用的方法是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
中华人民共和国恢复在联合国合法席位的时间是()。
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
随机试题
证明样品符合技术标准的认证模式称为
Excel2010是一种()软件。
A.小肠切除吻合术B.化脓性阑尾炎手术C.腹腔镜疝修补术D.结肠脾区癌引起的急症肠梗阻手术E.胃后壁穿孔手术属于“I”切口的手术是
本案一审法院决定适用简易程序是否正确?原因是什么?二审法院的审理期限按照法律规定是多长时间?如果本案二审法院不能按法定期限结案,其应如何处理?
甲、乙、丙、丁计划设立一家从事技术开发的天际有限责任公司。按照公司设立协议,甲以其持有的君则房地产开发有限公司20%的股权作为其出资。下列哪些情形会导致甲无法全面履行其出资义务?(卷三2011年真题试卷第69题)
设置会计科目的相关性原则是指所设置的会计科目应当符合国家统一的会计制度的规定。()
下列不属于共用部位的是()。
班主任工作的重要性体现在哪些方面?
现当代的不少文学作品被改编为影视剧,比如路遥的《平凡的世界》等。下列被改编为影视剧的小说与其作者对应正确的有()。
大气污染物分为一次污染物和二次污染物。从污染源排进大气后,直接污染空气称一次污染物,主要有二氧化硫、一氧化碳、氮氧化物、二氧化氮、颗粒物(飘尘、降尘、油烟等),氮气及含氧、氮、氯、硫有机化合物以及放射性物质等。二次污染物是由于阳光照射污染物,排入环境中的一
最新回复
(
0
)