2.37.c

数据结构习题及答案

2.37④  设以带头结点的双向循环链表表示的线性
表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的
算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。

实现下列函数：
void ReverseEven(BiLinkList &L);

双向循环链表类型定义如下：
typedef struct BiNode {
    ElemType       data;
    int            freq; // 2.38题用
    struct BiNode *prev,
                  *next;
} BiNode, *BiLinkList;
void ReverseEven(BiLinkList &L)
{

  BiLinkList p;
  p=L->next;
  if(p->next!=L)
  {
    while(p->next!=L&&p->next->next!=L)
      {
       p->next=p->next->next;
       p=p->next;
      }                                     //此时p指向最后一个奇数结点
    if(p->next==L) p->next=L->prev->prev;
    else p->next=L->prev;
    p=p->next;                             //此时p指向最后一个偶数结点
    while(p->prev->prev!=L)
     {
      p->next=p->prev->prev;
      p=p->next;
     }
    p->next=L;                             //后继指针形成循环
    for(p=L;p->next!=L;p=p->next) p->next->prev=p;
    L->prev=p;                            //前驱指针形成循环
  }
}