首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2019-01-16
57
问题
有一个不带头结点的单链表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
学硕统考专业
相关试题推荐
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
“两个凡是”
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱,其基本理由是他们()
编写判定给定的二叉树是否是二叉排序树的函数。
随机试题
Womendonotavoidfightingbecausetheyaredaintyorscared,butbecausetheyhaveagreaterstakethanmeninstayingalivet
应首先选择以下哪种辅助检查如该患者确诊为颈椎病脊髓型,应选择下列哪种治疗方法最佳
滇东南地区某山岭重丘区拟建一个高速公路工程,全长62.05km,其中山岭区长18.9km,设计行程速度80km/h,路基宽22.5m;重丘区43.15km,设计行程速度80km/h,路基宽24.5m。主要工程数量如下:土方287.5万m3,石方320.4
能够行使同时履行抗辩权的合同有()。
将边长为1的正方体一刀切割为2个多面体,其表面积之和最大为()。
下列关于C++函数的说明中,正确的是()。
Oftenconjuringimagesofdank,smelly,mosquito-infestedwastelands,uponcloserlook,wetlandsareactuallybiologicallydiver
Pregnancymothersaregettinganewtooltohelpkeepthemselvesandtheirbabieshealthy:pregnancytipssentdirectlytotheir
A、Hewantedtofollowthetraditionofhiscountry.B、Hebelievedthatitsymbolizedaneverlastingmarriage.C、Itwasthoughta
BritishCuisine:TheBestofOldandNewBritishcuisine(烹饪)hascomeofageinrecentyearsaschefs(厨师)combinethebest
最新回复
(
0
)