算法 2.25.txt

数据结构各种算法原代码及图形示例

算法 2.25
void union_OL( LinkList &La，LinkList &Lb ) 
{
      // La 和 Lb 分别为表示集合 A 和 B 的循环链表的头指针，求 C=A∪B，操作
      // 完成之后，La为表示集合C 的循环链表的头指针，集合A和B的链表不再存在
      pa = La->next->next;     // pa 指向 A 中当前考察的结点
      pb = Lb->next->next;     // pb 指向 B 中当前考察的结点
      rc = La->next;           // rc 指向 C 当前的表尾结点的表尾
      while ( pa!=La->next && pb!=Lb->next ) {
        if ( pa->data < pb->data ) { // 链接 A 的结点，pa 指向 A 中下一结点
          rc->next = pa;  rc = pa;  pa = pa->next;
        }//if
        else if ( pa->data > pb->data ) {// 链接B的结点，pb指向B 中下一结点
          rc->next = pb;  rc = pb;  pb = pb->next;
        }
        else {    // 链接A的元素，释放B的结点，pa、pb分别指向各自下一元素
          rc->next = pa;  rc = pa;  pa = pa->next;
          qb = pb;  pb = pb->next;  delete qb;
        }//else
      }//while
      if ( pb == Lb->next )  rc->next = pa;    // 链接 A 的剩余段
      else {                             // 链接 B 的剩余段
        rc->next = pb;  pb = Lb->next;   // pb 指向 B 的头结点
        Lb->next = La->next;  La = Lb;   // 构成 C 的循环链
      }//else
      delete pb;                         // 释放 B 表的表头
} // union_OL