Question

设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的

设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表C，使C为A和B的差集，且C中元素也递增有序

Answer 1

这个问题就是剔除A中的B元素，最朴素的算法就是遍历A，逐个判断是否在B中，算法复杂度为O(n*m)，若用二分查找的话，就是O(n*logm)，显然效率低下。

考虑到A,B中元素都是有序的，对A中第一个元素，在B中找到第一个不比它小的元素，若两者相等，则该元素剔除，否则加入到c中；对A中下个元素，重复该过程，一直到A或B某一个比较完。算法复杂度为O(n+m)。

struct Node {
    int num;
    struct Node *pNext;
};

typedef struct Node *List;

List chaji( List a, List b)
{
    List c = NULL;
    
    while ( a != NULL && b!= NULL)
    {
        while ( a->num > b->num)
            b = b->pNnext;
        if ( a->num < b->num)
        {
            if (c == NULL) 
                c = malloc(sizeof(struct Node));
            else
            {   
                c->pNext = malloc(sizeof(struct Node));
                c = c->pNext;
            }
            c->num = a->num;
            c->pNext = NULL;
         }
         a = a->pNext;
     }
     
     return c;
}