首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
43
问题
设有带头结点的循环双链表表示的线性表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://jikaoti.com/ti/8wajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
魏晋南北朝时期道家得到了迅速发展,援儒入道,在道教官方化过程中有重大贡献的北朝人物是()。
在1956年4月提出实现马克思主义同中国实际“第二次结合”任务的是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
在五四运动至新中国成立前这一时期,实际上可供中国人民选择的建国方案主要是()。
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
以下选项不属于希腊城邦的形成方式和途径的是()。
晚清时期清帝年号的正确排序是()
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
随机试题
A.约0.5%B.1%~2%C.15%~25%D.40%E.60%川崎病冠状动脉瘤发生率
简述贯彻在集体活动中进行集体教育原则的基本要求。
A、Thefederalgovernmenthasspent60billiondollarsonresearchsofar.B、Publicresearchuniversitiesreceive17.4billiondo
凡士林的灭菌方法是
某药店利用季节性感冒流行时机,在标价之外加价出售某药品,受到没收违法所得并处2000元罚款的处罚。此处罚依据的法律是
唐朝的“三省”包括()。
对某商场地下车库的机械排烟系统进行验收时,选择一个防烟分区的一只感温探测器和一只手动报警装置进行模拟火灾试验,然后观察排烟阀和排烟风机的动作情况,并使用风速仪测试相应排烟口处的风速。下列现场情况及排烟口处的风速测试结果中,符合验收要求的是()。
下列各项中.应在收回委托加工应税消费品后征收消费税的是()。
①至④是风险管理中的4个活动,其恰当的顺序是(30)。风险识别的一个方法是(31) 。
ThepeopleoftheUSAhavebeenopposedtoacentralizedgovernmentsincelongbeforetheRevolutionof1776.Whenthe13coloni
最新回复
(
0
)