2.26.c

数据结构习题及答案

2.26④  假设以两个元素依值递增有序排列的线性表
A和B分别表示两个集合（即同一表中的元素值各不相
同），现要求另辟空间构成一个线性表C，其元素为A
和B中元素的交集，且表C中的元素也依值递增有序排
列。试对单链表编写求C的算法。

实现下列函数：
void Intersect(LinkList &hc, LinkList ha, LinkList hb);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
void Intersect(LinkList &hc, LinkList ha, LinkList hb)
{
  LinkList p,q,pc,s;
  p=ha->next;q=hb->next;
  pc=hc;
  while(p&&q)
  {
    if(p->data<q->data) p=p->next;
    else if(p->data>q->data) q=q->next;
    else
    { s=(LNode*)malloc(sizeof(LNode)); 
      s->data=p->data;
      s->next=NULL;
      pc->next=s;pc=s;
      p=p->next;q=q->next;
      
    }
  }
}