{ab}*({bc}+{cd})的求解

前两在网上看到一道题，觉得有意思，这两天用C实现了一下。具体问题的详细描述我忘了，大致就是四则混合运算，只是这里不是数，而是集合，可以把每个大括号当作一个集合。集合的＋相当于是求并集，－求交集的补集，＊求交集，当然，这里运算符也有优先级。

这题的思路很容易想到，因为当年学数据结构的时候已经讲过了，让符号依次进栈，根据下一个符号来决定上一个符号是否进行计算。数据也应该放到栈里面，不过C语言里的数据结构相关的函数都得自己定义，符号已经用栈了，所以数据的存放我选择用链表来实现，这样两种都可以练习一下。可以定义一个头结点，每来一个｛｝，插到头结点后面，这样每次运算的时候，用head->next，与head->next->next，来进行运算，运算后合并，其实和栈也差不多。

{}中的数据元素，我分别用了三种数据结构来实现。

第一种是链表，这是最容易想到的。为什么呢？因为如果把{}当作一个链表的话，里面的元素个数是变化的，变化的我们自然会想到用链表了，何况还要进行交并运算。所以第一种方法是将每个{}当作一个结点，所以的{}可以构成一个链表。
不过问题来了，链表对于查找是很慢的，比如求交集的时候，得遍历以查看其其是否在当前链表中。要想快速定位，hash最好不过了。

第二种是类似于hash表的数据结构。题中我们只对字母进行操作，如果假定只对小写字母进行操作的话，那么也就是说，最多一个{}中有26个字母，我们就可以先为每个结点分配一个大写为26的数组，用字母通过运算来作为下标，比如c,利用（c-'a')来作为其下标，增加相应的元素只用将相应的位赋1，查找时也只用判断其是否为1即可。
既然每个字母只有两种状态，存在或者不存在，那么我们完全可以用位来实现，这样，一个int型（32位机及其以上）就可以包含26个字母了。

第三种利用位来实现，用位一是节约空间，不过空间对于现在的计算机来说根本不算啥，其主要的好处是运算简单了，来看看＋，－，＊怎么实现的：
/**************** MATHEMATIC OPERATION ****************/
void addition(BIT_SET *dst, BIT_SET *src)
{
  dst->letters |= src->letters;
}

void subtraction(BIT_SET *dst, BIT_SET *src)
{
  dst->letters &= ~(dst->letters & src->letters);
}

void multiplication(BIT_SET *dst, BIT_SET *src)
{
  dst->letters &= src->letters;
}
非常简单，如果用其它两种，即使是上面的类似于hash表的，也得做一次循环，看其中的位是否存在于另一个集合中，只是find过程比较快而已。

后面两种都采用了以空间换时间的方法，虽然浪费了一些存贮空间，但是时间上得到了提高。以后对于这种固定集合的，都可以考虑一下用这种思想。

代码这里就不贴了，思想最重要。