首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
52
问题
设有带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
七月流血事件以后俄国国内政治形势总的特点是()。
论述王守仁心学思想的形成背景及主要观点
共产国际“七大”号召建立的反法西斯统一战线中不包括()。
火烧圆明园事件发生在哪次战争中?()
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
1895年发现X射线,拉开物理学革命序幕的科学家是()。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
1946年初,“美国计划将中共以一种类似西欧共产党所占的地位,纳入一个实际政体的政治和军事范围之内,敌对的两党共同参加一个以蒋介石为首的经过改组的联合政府”。材料反映出美国的意图是()
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
随机试题
下列选项中,属于社会公德内容的有
Thereisonethingthateveryonewantsmorethananythingelse.Somepeopletrytogetitbymakingmoney.Theythinkthatwhen
秦先生,高血压病,近期血压波动较大,为该病人测量血压时应做到
关于慢性胃炎的叙述,正确的是()。
根据《公司登记管理条例》的规定,自治区、直辖市工商行政管理局负责本辖区内()的登记。
大宇电子有限公司为一般纳税人,增值税率17%。2007年因生产经营所需要,于年初开始自营建造厂房一幢,发生如下业务,要求:根据以下业务编制会计分录。4月30日经查明原因,定额内损耗3000.00元,不可抗力发生意外损耗11000.00元,仓库保管员玩
中国近代葡萄酒酿造业始于()。
某市工商局春节期间出台叫停“禁止自带酒水”等六项措施,引起了中国烹饪协会高调反弹,工商部门作出解释声明:这是对于不规范行为的合法做法。此事件引起社会极大反响,并持续发酵!请问你怎么看?
人民检察院决定逮捕犯罪嫌疑人、被告人的,由人民检察院执行。()
下列可以激活属性窗口的操作是()。
最新回复
(
0
)