首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有带头结点的循环双链表表示的线性表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
69
问题
设有带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
邓小平在同江泽民等谈话时提出的中国社会主义农业改革和发展的“两个飞跃”是()。
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流
对西欧封建社会的说法不正确的是()。
国民政府对日宣战的时间是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
《道威斯计划》的实施所产生的直接结果是()。
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
两河流域分为两部分,其中南部称为()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
随机试题
党的十九大进一步明确了决胜全面建成小康社会的战略安排,要赢得全面建成小康社会的最后胜利,必须()
下列水泵中不属于叶片泵的是()。
[*]
肾病综合征低白蛋白血症的主要原因为
关于胃的形态描述,错误的是
普萘洛尔的特点有
伤口污染轻,清创术可延长时限至
拱一般可做成()。
根据《证券法》的规定,某上市公司的下列事项中,不属于证券交易内幕信息的是()。
甲与乙约定:“甲的儿子如果去外地工作,甲、乙之间的房屋租赁合同即行生效。”这一民事法律行为所附条件为()
最新回复
(
0
)