首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表L=(a1,a2,…,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a3,…,an,…,a4,a2)。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C
设有带头结点的循环双链表表示的线性表L=(a1,a2,…,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a3,…,an,…,a4,a2)。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C
admin
2013-12-31
48
问题
设有带头结点的循环双链表表示的线性表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)用p指针扫描L的所有结点,先将L构造为只有一个带头结点的循环双链表,而用指针s构造不带头结点的循环双链表(初始时为NULL),对于奇数序号的结点*p,采用尾插法插入到L中,对于偶数序号的结点*p,采用头插法插入到S中。最后将L和S两个循环双链表连接成一个循环双链表,L为其头结点指针。 (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)。
解析
转载请注明原文地址:https://kaotiyun.com/show/tSxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“五年不征”、“三年不上粮”、“公平交易”、“平买平卖”,这是()起义军提出的口号。
简述第二次科技革命的主要内容。
简述1931—1937年间的日本侵华史实。(南京大学2004年中国近现代史真题)
试总结苏联二三十年代社会主义建设的特点、成就及存在的问题
晚清时期下列武装力量出现的先后顺序是
关于垄断组织的积极作用,不正确的说法是()。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
一个在以太网中的主机试图发送一个帧,当它尝试了16次仍然失败之后,它应该()。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
随机试题
切换文档窗口的快捷键______。
肾性贫血
取得勘查许可证的某企业经过一定勘查后,估计勘查作业区内只会有小型贫矿,决定转让探矿权。李某有意接手,向朋友咨询。其朋友的下列哪些说法是正确的?()
有一天,某公安机关法医鉴定室的法医王某在下班途中,亲眼目睹了一起故意伤害案。下列说法正确的是:()
下列各项中,应按照“现代服务—生活服务”税目计缴增值税的是()。
(2018年)下列各项中,符合流动性溢价理论的是()。
在下列情形中,可能表明管理层存在舞弊动机或压力的有()。
蛋白质是决定生物体结构和功能的重要物质。下列相关叙述错误的是()。
领导让你从“老人跌入水中没人扶致死”入手,针对社会道德状况进行调查,请问你如何展开调查?
A、 B、 C、 D、 ADelphi被称为第四代编程语言,它是基于窗口和面向对象的编程方法。它是一种可视化的开发工具,并且提供了数据迁移工具(DataPump)可以将数据从一个数据库全部或部分迁移到另一种数
最新回复
(
0
)