2.23.c

数据结构习题及答案

2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn)，试写
一个按下列规则合并A、B为线性表C的算法，即使得
      C=(a1,b1,...,am,bm,bm+1,...,bn)  当m≤n时；
或者  C=(a1,b1,...,an,bn,an+1,...,am)  当m＞n时。
线性表A、B和C均以单链表作存储结构，且C表利用A表和
B表中的结点空间构成。注意：单链表的长度值m和n均未
显式存储。

实现下列函数：
void Merge(LinkList ha, LinkList hb, LinkList &hc)
/* 依题意，合并带头结点的单链表ha和hb为hc  */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
void Merge(LinkList ha, LinkList hb, LinkList &hc)
/* 依题意，合并带头结点的单链表ha和hb为hc  */
{

  LinkList p,q,hold1,hold2;
  p=ha->next;q=hb->next;
  if(!p){hc=hb;free(ha);}
  else{
       hc=ha;
       while(p&&q)
         {
          hold1=p->next;
          hold2=q->next;
          p->next=q;
          if(hold1)
             {
              q->next=hold1;
              p=hold1;q=hold2;
              }
          else break;
          }
      free(hb);
      }

}