首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
68
问题
设有带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
根据1931年的威斯敏斯特法,英国()。
撰写《南海寄归内法传》和《大唐西域求法高僧传》二书,记录了南亚许多国家的社会、文化和宗教状况,成为研究7世纪印度、巴基斯坦和南洋各国历史、地理可靠资料的是()。
婆罗门教的经典和主要教义。
论述新石器时代及其文化类型。
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
以下关于中国官僚资本的表述,错误的是()。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
明代中后期,随着工商业的发展和南北经济联系的加强,在江南地区,自宋元以来初露端倪的新的城市类型——()得到很快的发展。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
随机试题
患者,男,55岁。肺结核患者。今晨剧咳后突然出现呼吸困难、左胸刺痛、大汗淋漓。体格检查:心率140次/分,呼吸40次/分,左胸叩诊鼓音,左肺呼吸音消失。目前该患者最适当的处理方法是
仁达中学委托其教务人员赵某购买一批电教器材,赵某到百货公司购买时,正赶上该公司举行有奖销售,赵某代购电教器材得到了5张奖券,他自己把奖券收了起来,后百货公司抽奖,这几张奖券中有1张中了头奖,可得彩电1台,该电视机应当_________。
在国际贸易海洋运输中,运输贵重物品或有特殊用途的货物一般采用的海运提单是()提单。
下列选项所述情况中,应认定为工伤的是()。
要精心上课,处理好()的关系,及时把握和运用生成性课程资源,防止机械照搬教案。
根据以下情境材料,回答下列问题。某年某省高院通报一年以来全省法院审理毒品犯罪案件的情况,当年全省各级人民法院审结各类毒品犯罪案件共6835人。下图分别为毒品犯罪主体身份类比比例示意图和毒品犯罪案件被告人作案时年龄情况示意图:根据上述信息,下列选项表
在提取诱发遗忘研究的一般范式中,不包括的阶段是()。(2017年)
Aperson’shomeisasmuchareflectionofhispersonalityastheclotheshewears,thefoodheeatsandthefriendswithwhomh
A、30B、20C、60D、0C选项均为数字,因此听音时应关注与数字相关的信息。题目问女士每周抽多少根烟。会话中,男士问女士是否把自己描述为重度吸烟者。女士回答说,她不会把每周抽3包20支装的烟称之为重度抽烟。由此可见,女士每周抽20x3=60根,
A、It’shereditary.B、Theshampooheusedcausedit.C、Hecombshishairtoomuch.D、Heisoldenoughtolosehair.A信息明示题。男士一开始就
最新回复
(
0
)