- 陶小凡
-
修订版:
#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(" ");
}
// 把元素向左移以覆盖重复元素
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[] = {12,23,18,15,12,13}, *endOfA = a + sizeof(a) / sizeof(a[0]);
T b[] = {4,12,26,23,14}, *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[] = {12,23,18,15,12,13};
int b[] = {4,12,26,23,14};
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。
- nicehost
-
***************************我也来分析****************************
1,我们现来考虑“这么大的数组该怎么读,是否要在内存中为他们开辟空间?”
根据“ 由于A、B两个集合,每个集合的元素存在重复且很多(可能会有几万个,甚至更多)。”的要求,
可知道,这么多的数据,“可能会有几万个,甚至更多”,那么用数组行吗?
这么多数据我想,最好还是从其他文件读入。
但是这么多的数据,一下子全部读到内存里来,何况重复的数据是我们不需要,我们为何要把这么多的垃圾放到内存中来呢?
不要浪费内存啊!那么这样的话,数据长度不是更不确定了。怎么办?动态链表?好,那就动态链表吧。
2,上面第一条,我们已经说了不要把垃圾方进来?那么怎么才不让那些垃圾驻进内存呢?
对于用链表表示的,我只想到了,每读入一个不是垃圾的数据进对它进行排序,搜索前面以被认为不是垃圾的数据,如果没有与读入的相等,就读如它到内存中去,否则舍去。
- snjk
-
我也来回答
int i,j,asize,bsize;
for(i=0;i<asize;i++)
{
for(j=i+1;j<asize;j++)
if(a[i]==a[j])a[i]=0;
}
for(i=0;i<bsize;i++)
{
for(j=i+1;j<bsize;j++)
if(a[i]==b[j])b[i]=0;
}
for(i=0;i<asize;i++)
{
for(j=0;j<bsize;j++)
if(a[i]==b[j]){a[i]=0;b[j]=0;}
}
j=0
for(i=0;i<asize;i++)
if(a[i]!=0){c[j]=a[i];j++;}
//把下边代码去了就只有A中的了
for(i=0;i<bsize;i++)
if(b[i]!=0){c[j]=a[i];j++;}
- 我不懂运营
-
我也来说一下我的思路!至于程序代码我就不写了!
我们要考虑到这两个集合中的元素可能会很多,而且重复的也可能很多!所以分两步来完成这件事情!
第一步:去除两个集合中的相同元素,同时给两个集合中的元素排序.(由小到大顺序,在排序的时候去掉相同元素是很方便的)
第二步:对于A集合中的第i+1个元素Ai+1(i是初值为0整数),去和B集合的第j+1个元素Bj+1开始比较(j是初值为0整数),若Ai+1<Bj+1,则说明B集合中没有和Ai+1相同的元素(Ai+1比较结束),给i++;若Ai+1=Bj+1,则说明从B集合找到了和Ai+1相同的元素,所以此时删除Ai+1(Ai+1比较结束),给i++,j++;若Ai+1>Bj+1,则说明Ai+1和Bj+1不是相同的元素(Ai+1比较结束),给j++。重复第二步直到A集合中的所有元素比较完成!
这样至少我感觉程序的效率会是很高的!
- LocCloud
-
有点意思
- max笔记
-
刚贴的答案居然发现有个bug!!!现紧急更正如下:
注:本程序不管A集还是B集,都只保留去了重号后大的集内的号(正好你模板答案就是此种情形)
-----------差集程序++6.0(企业级解决方案)-----内附精美图文说明.......
#include "iostream.h"
int k,kk=0;
int *qvchonghao(int m,int b[]) //去重号函数
{
int s,ss,r[50000];
for (s=0;s<m;s++){
for(ss=0;ss<m;ss++){
if (s!=ss && b[ss]==b[s]) goto conti;}
r[k++]=b[s];
conti:;
}
for (s=0;s<k;s++) b[s]=r[s];
return (b);
}
int *chaji (int m,int n,int a[],int b[],int c[])// 求差集程序
{
int s,ss;
if (m>=n){
for (s=0;s<m;s++){
for(ss=0;ss<n;ss++){
if (b[ss]==a[s]) goto contii;}
c[kk++]=a[s];
contii:;
}
}
if (m<n){
for (s=0;s<n;s++){
for(ss=0;ss<m;ss++){
if (a[ss]==b[s]) goto contii2;}
c[kk++]=b[s];
contii2:;
}
}
return (b);
}
int main()
{
int i,m,n,c[50000];
int a[10]={12,23,18,15,12,13,20,23,13,27};
int b[10]={14,12,26,23,14,15,12,26,23,56};
qvchonghao(10,a); //传达第一个数组大小及数组,去重号。
m=k;
k=0;
qvchonghao(10,b);//传达第二个数组大小及数组,去重号。
n=k;
chaji(m,n,a,b,c);//使用时这句不用动。当然a,b得是你的数据数组。
for (i=0;i<kk;i++) cout<<c[i]<<" "<<endl;//c的长度就是全局变量kk
return(0);
}
- S笔记
-
每个集合里面的整数大小有限定么?
我想知道的是:
你所说的整数是int型的吧?
如果是,那么以下办法效率超高,如果不是,全当路过,没看见:
首先,将所有负整数全部化为正整数,由于int 的范围是一般来说,-32768--32767,我们约定,所有数据加上40000!现在,所有数据都是正整数了。
然后,开设两个80000格的short型数组(保证每个数可以转化为数组下标!)。
程序代码如下(假定你的输入是:首先输入一个数,表示a有多少个元素,然后是一行整数,为a的各个元素;然后又是一个数,表示b的元素个数,接着又是一行整数,表示b中各个元素,如果不是,改写读入部分就可以了)
#include <stdio.h>
int main()
{
short en1[80000],en2[80000];
long int b; /* 用来存放读入数据 */
register int i; /*循环变量 */
int n;
/* 读入部分,读入一个数b,将其加上40000,使en1[b]等于1;同理读入en2[]的数据 */
scanf ("%d", &n);
for (i=0; i<n; i++){
scanf ("%d", &b);
b += 40000;
if (en1[b] != 1)
en1[b] = 1;
}
scanf ("%d", &n);
for (i=0; i<n; i++){
scanf ("%d", &b);
b += 40000;
if (en2[b] != 1)
en2[b] = 1;
}
for (i=0; i<80000; i++){
if ((en1[i] == 1) && (en2[i] != 1))
printf ("%ld ", i - 40000);
}
return 0;
}
总结:
该算法的巧妙之处在于,将读入数据处理成正数以后,用脚标代替原来的数,所开的数组里面的元素仅仅表示此数据是否存在。
代码简洁明了,数据结构简单。
该算法不是一种正规的算法,但确享有任何算法无法达到的效率!!!
读入数据,n1、n2次循环,输出数据80000次循环,总时间复杂度仅仅约为:
n1 + n2 + 80000次!!!
在数据量大约超过40000的时候,速度优于快速排序对单一数组的一次排序!!!
本算法的缺点:对int型有特效,但对于long int型则心有余而力不足了。
- 再也不做稀饭了
-
////////////////////////////////////////////////////////
程序虽然简单但写起来比较费时,如果你是自己练习最好动下手。
我这两天没时间写了,send me your contact by message and I may reply you soon.
补充一下,这是线性表最好不使用链表。
////////////////////////////////////////////////////////
我的想法是先对集合A和B采用相同的方法进行排序,比如都使用由小到大的方式进行排序,如果想保留原来的A和B的话,可以复制,然后对复制品进行排序。
然后是比较,假定把A和B都进行了从小到大的排序,使用两个下标IdxA、IdxB,大致算法为:
LenA = A集合中的数据个数
LenB = B集合中的数据个数
IdxA = IdxB = 0
while(IdxA < LenA)
{
while(A[IdxA]>B[IdxB] && IdxB<LenB) IdxB++;
if(IdxB >= LenB) break;//比较结束
if(A[IdxA] == B[IdxB])//找到与B中相同的元素
{
处理的方法有二:
方法一是把A中后面的元素集体前移:
for(int i=IdxA;i<LenA-1;i++) A[i] = A[i+1];
LenA--;
方法二是把当前数标记为一个其他元素不可能取到的特殊值,然后IdxA++,循环结束后把标为特殊值的元素从集合中去掉;
这里使用第一种方法
}
}
如果要保留原集合中数据的排列顺序,可以增加两个下标数组:SufixA[LenA]和SufixB[LenB],并初始化:
for(i=0;i<LenA;i++)
SufIxA[i]=i;
for(i=0;i<LenB;i++)
SufIxB[i]=i;
排序时对A[Sufix[i]]进行比较,然后调整SufIxA数组中的元素即可。
- 北境漫步
-
注意点是做题的要求还是你自己的要求?
直接对A里面的每一个数与B的每一个比较,发现一样的就删掉
然后判断重复的去掉
就行了
如果是题目的话,应该又每个数的大小限制和每个集合中数的总数的大小限制
如果总数比较小,小于10的6次方级别,还可以用数组标志位的办法来做
会简单很多
你可以补充下问题
- tt白
-
如果要保留原集合中数据的排列顺序,可以增加两个下标数组:SufixA[LenA]和SufixB[LenB],并初始化:
for(i=0;i<LenA;i++)
SufIxA[i]=i;
for(i=0;i<LenB;i++)
SufIxB[i]=i;
排序时对A[Sufix[i]]进行比较,然后调整SufIxA数组中的元素即可
- coco
-
—:我的想法是首先对A数组进行排序,并删除多余的元素,存入一个动态链表表中,因为数组较大,移动很浪费时间。算法如下:
struct list{int a;struct list *next
}*starA,*starB*p,*q;
while(i<N){
if(!starA){strB=new list(A[i]);
starA->next=NULL;
continue; }
q=p=starA;
if(p->a<A[i]&&p->next){q=p;p=p->next;}
if(!p->next){p->next=new list(A[i]);
p->next->next=NULL;
continue;}
if(p->a==A[i])continue;
q->next=new list(A[i]);
q->next->next=p;
}
二:接着就是对B的处理,与A相同;
while(i<M){
if(!starB){strB=new list(B[i]);
starB->next=NULL;
continue; }
q=p=starB;
if(p->a<B[i]&&p->next){q=p;p=p->next;}
if(!p->next){p->next=new list(B[i]);
p->next->next=NULL;
continue;}
if(p->a==B[i])continue;
q->next=new list(B[i]);
q->next->next=p;
}
三:对两个排好序的链表,进行差集计算了,采用左右缝缘法:
list *p1,*q1;
p1=p=starA;q1=q=starB;
void left(){
while(p->a<q->a&&p->next)
{p1=p;p=p->next;}
if(p->a==q->a) {p1->next=p->next;
delete p;
p=p1->next;
}
void right(){
while(q->a>p->a&&q->next)
{ q1=q;
q=q->next;
delete q1;}
}
void sufa(){
while(p->next){
right();
left();
}
四:就是将链表复制到表C了 由于时间仓促,算法不严谨,建议各个链表设置一个头结点,算法可以非常简单写出。