求两个集合的并集与差集

  照例还是每天刷一些笔面试题，今天的两道题是和集合有关的：
 1. A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
  这是腾讯一年的笔试题。这里插一句，昨天刚刚考过腾讯的笔试，感觉相对于阿里，腾讯的题更注重对基础的考察，但包罗面比较广，应该来说如果认真将操作系统，数据结构，网络等计算机最基础的知识都准备一下（要拿出考研的热情，根据自己基础准备3~6个月），再大致练一些coding，过腾讯的笔试不应该有很大的问题。
   言归正传，假设集合用数组存储，首先对数组排序，则时间复杂度为O(nlogn)，然后基于两个排过序的数组，进行比较求交集，复杂度为O(n)，先贴上代码：
          

#include <stdio.h>
#include <stdlib.h>
#define M 8
#define N 5
int cmp(const void *a, const void *b)
{
    int *x = (int *)a;
    int *y = (int *)b;
    return (*x) - (*y);
}

int main(void)
{
    int A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};
    int B[] = {39 ,8 , 10, 6, -1};
    //对数组A和数组B进行快排
    qsort(A, M, sizeof(int), cmp);
    qsort(B, N, sizeof(int), cmp);
    //FindIntersection(A, B);
    int i = 0, j = 0;
    int cnt = 0;
    int result[M > N ? M : N];//保存集合的结果
    //设置i、j索引，分别指向数组A和B，相等则同时移动，不相等则移动较小值的索引
    while(i < M && j < N)
    {
        if(A[i] == B[j])
        {
            result[cnt] = A[i];
            i++;
            j++;
            cnt++;
        }
        else if(A[i] < B[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }
    for(i = 0; i < cnt; i++)
    {
        printf("%4d", result[i]);
    }
    return 0;
}

代码一目了然，没有什么可说的，需要重点说一下的是qsort函数，qsort函数是编译器自带的快速排序函数，详细介绍如下：
 

头文件：stdlib.h

用 法： void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

参数： 1 待排序数组首地址

            2 数组中待排序元素数量

            3 各元素的占用空间大小

            4 指向函数的指针，用于确定排序的顺序

关于fcmp函数的书写方式，维基百科上有更标准的写法，这里也贴一下，以供参考：
        

/* Comparison function. Receives two generic (void) pointers. */
int compare(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    /* to avoid undefined behaviour through signed integer overflow,
        avoid: return x - y; */
    int ret;
    if (x == y)
      ret = 0;
    else
      ret = (x < y) ? -1 : 1;

    return ret;
}

  2. 已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
   这是迅雷2014年的校招试题，贴上代码

struct node
{
    int elem;
    node* next;
};

void difference(node** LA , node* LB)
{
    node *pa , *pb , *pre , *q;
    pre = NULL;
    pa = *LA;

    while(pa)
    {
        pb = LB;
        while(pb && pa->elem != pb->elem )
            pb = pb->next;
        if(pb)
        {
            if(!pre)
                *LA = pa->next ;
            else
                pre->next = pa->next;
            q = pa;
            pa = pa->next;
            free(q);
        }
        else
        {
            pre = pa;
            pa = pa->next;
        }
    }
}

代码中的指针pa用于指向集合A的元素；pb指向集合B的元素；临时指针q指向需要被删除的元素；pre用于实现删除时结点的链接，与pa保持所指结点的前后继关系

一般来说，集合有两种存储方式，数组或链表，本题两种存储方式都涉及到了，这两题仅是给出了解法，应该不是最高效的方法，后面再不断地更新完善吧！



参考资料：
         维基百科： />          题1代码：http://blog.csdn.net/jie1991liu/article/details/13168255
         题2代码：http://blog.csdn.net/hackbuteer1/article/details/11482103