目录

题目

思路

代码

数据结构

STL

题目

假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素即为集合中的成员。编程实现集合A和集合B的交运算。

输入

第一行为集合A的数据元素个数n;

第二行输入n个集合A的数据元素 ;

第三行为集合B的数据元素的个数；

第四行输入m个集合B的数据元素

输出

A和B的交集

样例输入

8
0 5 6 3 8 7 9 10
7
1 3 4 7 8 9 5

样例输出

5 3 8 7 9

思路

和SWUST OJ#1037集合的并运算有点类似

集合的并运算

由于集合是没有重复数据的，所以也是开一个桶，进行记忆化处理。

先遍历顺序表b，让b中所有的数，对应的桶赋值为1。然后再遍历顺序表a，若判断对应的桶也为1，则插入至顺序表c，桶变为0。完成求交集

最后输出顺序表c就行

注意：是先遍历b，因为最后输出是按照a的顺序来的。

//合并顺序表，求交集
void SeqlistMerge(Seqlist* &La,Seqlist* &Lb,Seqlist* &Lc) {int bucket[100005]={0};//开桶记忆化处理for(int i=0;i<Lb->len;i++) bucket[Lb->data[i]]=1;for(int i=0;i<La->len;i++) {//若桶为1，说明之前没有插入过该数据if(bucket[La->data[i]]==1) {Lc->data[Lc->len++]=La->data[i];bucket[La->data[i]]=0;//已经插入了,将桶赋值为0,以后就不再插入}}
}

代码

顺序表模板

数据结构

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
//定义顺序表
typedef struct {int data[10005];int len;
}Seqlist;
// 初始化顺序表
void SeqlistInit(Seqlist* &L) {L=(Seqlist*)malloc(sizeof(Seqlist));L->len=0;
}
//创建顺序表，输入数据
void SeqlistCreate(Seqlist* &L) {int n,x;cin>>n;while(n--) {cin>>x;L->data[L->len++]=x;}
}
//合并顺序表，求交集
void SeqlistMerge(Seqlist* &L1,Seqlist* &L2,Seqlist* &L3) {int bucket[100005]={0};for(int i=0;i<L2->len;i++) bucket[L2->data[i]]=1;for(int i=0;i<L1->len;i++) {if(bucket[L1->data[i]]) {L3->data[L3->len++]=L1->data[i];bucket[L1->data[i]]=0;}}
}
//打印顺序表，输出数据
void SeqlistPrint(Seqlist* &L) {for(int i=0;i<L->len-1;i++) {cout<<L->data[i]<<" ";}cout<<L->data[L->len-1]<<endl;
}
int main() {Seqlist *L1,*L2,*L3;SeqlistInit(L1);SeqlistCreate(L1);SeqlistInit(L2);SeqlistCreate(L2);SeqlistInit(L3);SeqlistMerge(L1,L2,L3);SeqlistPrint(L3);return 0;
}

STL

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>a,b,c;
int bucket[100005];
int main() {int m,n,x;cin>>m;while(cin>>x,a.push_back(x),--m);cin>>n;while(cin>>x,bucket[x]=1,b.push_back(x),--n);vector<int>::iterator it;for(it=a.begin();it!=a.end();it++) {if(bucket[*it]) {c.push_back(*it);bucket[*it]=0;}}for(it=c.begin();it!=c.end();it++) {cout<<*it<<" ";}return 0;
}