数据结构——链表算法设计

链表

1、已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集， 并存放于A链表中。[南京航空航天大学2001六(10分)  2004一、1 (10 分)]

//递增链表A B求并集
p=A->next;
q=b->next;
A->next=NULL;                          //初始化p、q指针、使A置空
while(p){while(p->data<q->data){           //如果p的值小于q的值，则遍历至p的值大于等于q的值p=p->next;}if(p->data==q->data){            //p的值与q的值相等，头插法插入p，再让p等于下一个结点t=p->next;p->next=A->next;A->next=p;p=t;}q=q->next;                        //q指针向后移一位
}
return A;

2、设有两个从小到大排序的带头结点的有序链表ha,hb。试编写求这两个链表交运算的算法。要求结果链表仍是从小到大排序，但无重复元素。[南京航空航天大学1996 十一（10分）]

p=ha->next;q=hb->next;ha->next=NULL;r=ha;
while(p){while(p->data<q->data){p=p->next;}if(p->data==q->data){t=p->next;p->next=r->next;r->next=p;r=p;p=t;}q=q->next;
}

3、已知递增有序的单链表A、B和C分别存储了一个集合，设计算法实现A: =AU(B∩C),并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|).其中，(|A|为集合 的元素个数。[合肥工业大学2000五、1 (8分)]

//先求B∩C
p=B->next;
q=C->next;
B->next=NULL;
r=B;
while(p){while(p->data<d->data) p=p->next;if(p->data==q->data){t=p->next;p->next=r->next;r->next=p;p=t;}q=q->next;
}
//求A∪(B∩C)
p=A->next;
q=B->next;
A->next=NULL;
r=A;
while(p&&q){if(p->data==q->data){t=p->next;p-next=NULL;r->next=p;r=p;p=t;q=q->next;}else if(p->data>q->data){t=q->next;q->next=NULL;r->next=q;r=q;q=t;else{t=p->next;p->next=NULL;r->next=p;r=p;p=t;}
}
if(p) q=p;
while(q){t=q->next;q->next=NULL;r->next=q;r=q;q=t;
}