算法 2.26.txt

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

算法 2.26
void union_OL_1( LinkList &La，LinkList &Lb ) 
{
      // La 和 Lb 分别为表示集合 A 和 B 的循环链表的头指针，求 C=A∪B，操作
      // 完成之后，La为表示集合C 的循环链表的头指针，集合A和B的链表不再存在
      La->next->data=MAX; Lb->next->data=MAX;  // 头结点的数据域设置最大值MAX
      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;
        }
        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;
        }
      }//while
      rc->next=La;                     // 封闭链环
      delete Lb->next;                 // 释放 B 表的表头
} // union_OL_1