006　求单链表的差集

利用单链表的基本运算，求A-B。即如果单链表A中出现的元素，在B中也出现，则将A中的该元素删除。例如，单链表A中的元素为{22，7，15，56，89，38，44，65，109，83}，B中的元素为{15，9，22，89，33，65，90，83}，则执行A-B操作后，A中的元素为{7，56，38，44，109}。

【分析】

这是上海大学考研试题，下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A中的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表表示，先把集合A、B中的元素按递增排列，C为空；操作完成后，A、B保持不变，C中元素按递增排列。函数Append（last，e）是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址。函数Difference（A，B）实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以方便新结点的添加。当A-B运算执行完毕后，再删除并释放表示结果集合的链表的表头结点。

第1章\范例01-07.c

运行结果（见图1.20）

图1.20　算法运行效果

这个算法也可以利用单链表的基本运算实现（无须对链表进行排序）。对于单链表A中的每个元素e，在单链表B中进行查找，如果在B中存在与A相同的元素，则将元素从A中删除。算法如下：