首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
49
问题
设有带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
简述辛亥革命前革命派和改良派论战的主要内容,并谈谈你对这场论战的基本看法。(南京大学2002年综合卷真题)
第三世界所共有的特征及崛起的标志是什么?
试析英法绥靖政策和美国中立政策的原因。(南京大学2013年国际关系史真题)
春秋时期,()作为灌溉工具应用于农业生产中。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
马克思创立马克思主义哲学时,吸收了被列宁称之为“基本内核”的哲学思想,该思想的创立者是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
简述清代秘密立储制的操作并作出评价。
詹天佑自主设计修建了中国第一条铁路是在()。
随机试题
原子吸收光谱法中的基体效应干扰可采用()方法消除。
砒石治疟,始见于
以下不能采取留置送达方式的是:
泵的性能由其工作参数加以表述,包括()。
总会计师的权限包括( )。
根据海关规定,在货物进境后、办结海关放行手续前,有下列情形之一依法应当退运的,由海关责令当事人将进口货物直接退运境外;
债权人除了按期取得本息外,对债务人不能作其他干预。()
在赠与合同中,赠与人撤销权的行使期限是()。
下列各句中,没有语病的一句是()
1959年中共八届八中全会召开后,在全党范围开展的错误斗争是()。
最新回复
(
0
)