首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
有一个不带头结点的单链表list,链表中结点都有两个域:数据域data和指针域link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求: (1)
admin
2018-08-12
46
问题
有一个不带头结点的单链表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
学硕统考专业
相关试题推荐
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
北约和华约两个组织对峙近半个世纪,其影响是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
操作系统采用页式存储管理方法,要求()。
随机试题
这是能想象得出的最好的办法。
设二维随机变量(X,Y)的概率密度为f(x,y)则P{X≤0.5,Y≤1}=()
体内氨的储存和运输的重要形式是
与深孔爆破法比较,浅孔爆破具有()的特点。
关于几个名词的概念,下列叙述正确的是( )。
(2009年真题)关于著作权贸易,下列表述中正确的是()。
全心全意为人民服务,一个最基本的要求就是要坚持一切从人民群众的根本利益出发。
最早绕过好望角而抵达印度的航海家是()。
根据弗洛伊德的发展理论,“恋母情结”出现的阶段是()
以下程序的输出结果是()。#include<iostream.h>main(){intb[3][3]={0,1,2,0,1,2,0,1,2},ij,t=1;for(i=0;i<3;i++)for(j
最新回复
(
0
)