2. 考研
  3. 设有带头结点的循环双链表表示的线性表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)根据设计思想，采用

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

学硕统考专业

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