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

admin2013-12-31  23

问题 设有带头结点的循环双链表表示的线性表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://jikaoti.com/ti/zCajFFFM
0

最新回复(0)