问题

       已知递增有序的单链表A、B分别存储了一个集合，请设计算法以求出两个集合A和B的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

分析

      初始一个化链表，定义一个常数i初值为0，从A和B的第一个结点开始遍历。A和B结点分别处理大于、小于、等于三种情况即可。

代码

int fun(LinkList A, LinkList B, LinkList &C){ int i = 0; C = (LinkList)malloc(sizeof(LNode)); LNode *p = A -> next, *q = B -> next, *r = C; while(p && q) { if(p -> data < q -> data) { LNode *temp = (LinkList)malloc(sizeof(LNode)); temp -> data = p -> data; temp -> next = NULL; r -> next= temp; r = r -> next; p = p -> next; i++; }else if(p -> data == q -> data) { p = p -> next; q = q -> next; }else if(p -> data > q -> data) { q = q -> next; } } if(B == NULL) {///B链表结束，A链表剩余的元素即为只在A中出现的元素ikan while(p) { LNode *temp = (LinkList)malloc(sizeof(LNode)); temp -> data = p -> data; temp -> next = NULL; r -> next= temp; r = r -> next; p = p -> next; i++; } } return i; }

源代码

       http://123.206.59.223:8080/code/code/15.rar