修订版:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int T;
// 打印数组
void Print(T* beg, T* end, const char* msg)
{
printf(msg);
while(beg != end)
printf("%d ", *beg++);
putchar('\n');
}
// 把元素向左移以覆盖重复元素
void MoveUp(T* dest, T* src, T* end)
{
while(src != end)
*dest++ = *src++;
}
// 去重
T* Unique(T* beg, T* end)
{
T* dupBeg = end;
if(end - beg <= 1)
return end;
while(++beg != end)
{
if(*(beg - 1) == *beg)
{
dupBeg = beg;
while(*++dupBeg == *(dupBeg - 1) && dupBeg != end);
if(dupBeg == end)
return beg;
else
{
MoveUp(beg, dupBeg, end);
end -= dupBeg - beg;
}
}
}
return end;
}
// 求差集
T* SetDiff(T* a, T* endOfA, T* b, T* endOfB, T* c)
{
T* p;
for(; a != endOfA; ++a)
{
for(p = b; p != endOfB; ++p)
if(*p == *a)
break;
if(p == endOfB)
*c++ = *a;
}
return c;
}
inline int Cmp(const void* lhs, const void* rhs)
{
return *(const T*)lhs - *(const T*)rhs;
}
int main()
{
// 只是个示例，元素个数很多的话可以用动态数组
T a[] = , *endOfA = a + sizeof(a) / sizeof(a[0]);
T b[] = , *endOfB = b + sizeof(b) / sizeof(b[0]);
T* c, *endOfC;
// 排序
qsort(a, endOfA - a, sizeof(T), Cmp);
qsort(b, endOfB - b, sizeof(T), Cmp);
// 去重
endOfA = Unique(a, endOfA);
endOfB = Unique(b, endOfB);
Print(a, endOfA, "Set A: ");
Print(b, endOfB, "Set B: ");
// c = a - b;
c = (T*)malloc(sizeof(T) * (endOfA - a));
endOfC = SetDiff(a, endOfA, b, endOfB, c);
Print(c, endOfC, "Difference of A & B: ");
free(c);
return 0;
}
这样的话用C++更简单，直接set_difference:
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
int a[] = ;
int b[] = ;
list<int> la(a, a + 6);
list<int> lb(b, b + 5);
list<int> lc;
// 排序
la.sort();
lb.sort();
// 去重
la.unique();
lb.unique();
// 求差集，存在lc中
set_difference(la.begin(), la.end(), lb.begin(), lb.end(), back_inserter(lc));
// 打印
copy(lc.begin(), lc.end(), ostream_iterator<int>(cout, " "));
}
至于存储数据的数据结构，list，deque都是理想的选择，vector不太适合，因为你的数据量比较大，其他的就不用我说了吧，数据结构 + <algorithm> 就可以了，STL的算法和数据结构效率应该够高了吧，思路给你，具体的地方需要的话自己改一下。
如果嫌list是占用空间大的话可以用deque，但是unique和sort等方法就必须使用<algorithm>中的了，还有别忘了erase。