2. 考研
  3. 设有带头结点的循环双链表表示的线性表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

admin2013-12-31  25
问题 设有带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a3，…，an，…，a4，a2)。要求：
    (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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)