首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
18
问题
设有带头结点的循环双链表表示的线性表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://jikaoti.com/ti/zCajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《关于建国以来党的若干历史问题的决议》对毛泽东和毛泽东思想历史地位的科学评价。
最先提出农业生产责任制的是()。
关于戊戌变法的历史意义,表述正确的是()①反映了时代的需求和民族精神②唤醒近代中国的民族意识③促进了资产阶级革命的到来④显示了民族资产阶级的弱势
1991年,南斯拉夫联邦解体,分裂为新国家的数目为()。
下列战争与马拉松长跑运动项目起源有关的是()
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
在操作系统中,P,V操作是一种()。
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
随机试题
在考生文件夹下的“samp1.accdb”数据库文件中已建立两个表对象(名为“职工表”和“部门表”)。请按以下要求,顺序完成表的各种操作:设置表对象“职工表”的聘用时间字段默认值为系统日期。
使血压测量值相对准确的措施不包括
《最高人民法院关于审理盗窃案件具体应用法律若干问题的解释》规定:各地高级人民法院可根据本地区经济发展状况,并考虑社会治安状况,在本解释规定的数额幅度内,分别确定本地区执行“数额较大”、“数额巨大”、“数额特别巨大”的标准。依据法理学的有关原理,下列正确的表
以下企业中,属于转让定价调查应重点选择的企业有()。
每笔个人汽车贷款只能展期()次。
客户信用评级是商业银行对客户偿债能力和偿债意愿的计量和评价,反映客户违约风险的大小。()
下列关于处理意见分歧的说法中,正确的是()。
王华被学校委派到国际交流处负责外籍老师的引进和管理工作。()
Previousresearchesonmindfulnessmeditationhaveshownsomeresultsthatinfluencepeopleformanyyears.Itshowsthatmindfu
SIGG’strendyaluminumwaterbottleshavescoredalotoffreeadvertisinginrecentyears.SIGGhasbeen【67】formorethan100y
最新回复
(
0
)