2. 考研
  3. 42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，

admin2012-06-26  91
问题 42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C十十或JAVA语言描述算法，关键之处给出注释。
    (3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案(1)算法的基本设计思想如解析所述。 (2)用C语言算法描述如下： Void spl．it(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://www.kaotiyun.com/show/Lyxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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