首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
70
问题
设有带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
英国在准备撤出印度时采取的策略是()
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
法西斯势力上台后,英国面对挑战一心推行绥靖政策。其主要目的是()。
在《资政新篇》中,洪仁轩提出的政治主张实际是要()。
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
()时,为补充兵力,开拓财源,“料民于太原”(今山西西南部)。料民就是清查民数,以便于征兵,结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。
阅读下列材料,结合所学知识回答问题:材料一16—17世纪西欧医生的地位还很低,尽管主要的宫廷医生有很高的经济收入,但医生并不被认为是一个很光荣的职业,直到17世纪中叶,一位绅士还拒绝同一位有钱的医生的女儿结婚。律师职业虽然不被视为低等,
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
1947年签订的()标志着国际贸易体系的建立,实际上形成了以美国为中心的国际贸易体系。
随机试题
1822年,英国人巴贝奇首先提出来整个计算过程自动化的概念,设计出了第一台通用自动时序控制机械式计算机,称为________。
为观察肾的分泌排泄功能应做的检查是( )
预防HBeAg阳性母亲所生的新生儿HBV感染最有效的措施是
下列哪种情况在发生垂体危象时最为多见
据统计报载:截至到2001年年底,某市有高科技园区3个,已征土地6325hm2,占该市各类开发区已征土地总面积的18%。该城市在2002年年初,为了合理的利用已征土地,综合制定了科学的规划布局方案,将废弃的小型工场、市场等以及公共设施进行了重新布置,对城
工程项目质量控制系统的构成,依控制内容划分不正确的为()。
年化收益率有______与______之分。( )
对幼儿园活动的正确理解是()。
Studythedrawingcarefullyandwriteanessayof160-200words.Youshould1)describethedrawingbriefly,2)interpretthe
A、Sheagreeswithdieting.B、Sheopposesdieting.C、Shenevercaresaboutdieting.D、Shehasbeenonadiet.B信息明示题。对话一开始,男士询问女士
最新回复
(
0
)