首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表L===(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a3,……,an……a4,a2)。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用
设有带头结点的循环双链表表示的线性表L===(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a3,……,an……a4,a2)。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用
admin
2013-07-12
34
问题
设有带头结点的循环双链表表示的线性表L===(a
1
,a
2
,……,a
n-1
,a
n
)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a
1
,a
3
,……,a
n
……a
4
,a
2
)。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)算法的基本设计思想如分析所述。 (2)用C语言算法描述如下: void split(DLinkList &L){ DLinkList * p=L->next,* q,*s=NULL; L->next=L;L=>prior=L; //构造只有一个头结点的循环双链表 while(p!=L){ //扫描L的所有结点 q=p->next; p->next=L;p->prior=L->prior; //将*P结点插入到L循环双链表的末尾 L->prior->next=p;L->prior=p; p=q;q=p->next; if(S==NULL){ //s原为空表时,现只含有一个结点 s=p: s->next=s;s->prior=s; } else{ //将*P插入到s的前端 p->next=S;p->prior=s->prior; s->prior->next=p;s->prior=p; s=p; } p=q; } s->prior->next=L; //将L和S合并起来 L->prior->next=s: q=L->prior; L->prior=S->prior: S->prior=q: } (3)说明算法的复杂性:上述算法的时间复杂度为O(n),算法的空间复杂度为O(1)。
解析
用P指针扫描L的所有结点,先将L构造为只有一个带头结点的循环双链表,而用指针s构造不带头结点的循环双链表(初始时为NULL),对于奇数序号的结点*P,采用尾插法插入到L中,对于偶数序号的结点*P,采用头插法插入到s中。最后将L和s两个循环双链表连接成一个循环双链表,L为其头结点指针。
转载请注明原文地址:https://kaotiyun.com/show/2uxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
独立战争前,北美殖民地的类型主要包括()。①王室殖民地②业主殖民地③自治殖民地④“居留地"
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
在《资政新篇》中,洪仁轩提出的政治主张实际是要()。
国民政府对日宣战的时间是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
随机试题
确定调质钢的回火温度时,只考虑钢材的成分波动。()
A、1monthbeforemovingout.B、2monthsbeforemovingoutC、6monthsbeforemovingout.D、Atthetimewhenmovingout.A
Thispastfallsemester,atDukeUniversity,thereweretwostudentswhoweretakingorganicchemistry.Theydidprettywellin
A.阴陵泉B.肾俞C.关元D.三阳交E.带脉带下病兼湿热甚者配
为避免混杂因素影响调查结果,在不同年龄人群调查中,往往采取以下抽样调查方法中的哪一种
七情致病最易损伤哪几脏
患者,男,5岁,左脸靠耳部位大片红色皮疹,瘙痒,抓破后渗出流水,病势缠绵,2年反复发作,缠绵不愈,苔薄白,脉浮数,治疗应选用
下列选项中,影响胎儿正常生长发育的因素有()(2009.70)
Mostofyouwouldprobablysaythatwhatmakesyoutrulyhappyisyourfamilyandtheloveyoushareinyourrelationships,and
Inmybelief,someofthecommentsinthemovieaboutthejobmarketareactually________ofreal-lifedifficultiesinfinda
最新回复
(
0
)