Basic Computer Science – Learning set and implement the required methods specified in the lab specification.
这是计算机科学基础课程中的第一个实验，主要是借助计算机语言来进行set（集合）的各种操作。
为了达到实验效果，在该实验中禁止使用STL容器。
Analysis
由于集合的特点是 unordered and no duplicated（无序并且不重复），我们可以通过以下两种方式实现set。
不同的方法时间复杂度和空间复杂度有较大差异，但是由于Lab的测试样例太小，因此在此处两种方式并无显著差异。
Method 1
通过顺序遍历的方式剔除数组中的重复元素，最终剩余的元素即为set。
该方法较好的模拟了剔除元素的过程，但是对于集合的其他操作如equal、subset、union、intersetion等，该方法时间复杂度会更高。
Make Set
朴素方法剔除重复元素时间复杂度为O(n^2)，空间复杂度为O(n)，这也是建立一个set的成本。
for(int i=0;i<len-1;i++)
{
for(int j=i+1;j<len;j++)
{
if(str[i]==str[j])
{
for(int k=j;k<len;k++)
{
str[k]=str[k+1];
}
len--;
j--;
}
}
}
Equal
判断是否相等。可以直接判断两个set中元素是否相同，朴素的查找最坏情况时间复杂度是O(n^2)，我们也可以通过sort()和strcmp()函数降低时间复杂度和代码难度
char set1[100],set2[100];
sort(set1,set1+strlen(set1));
sort(set2,set2+strlen(set2));
if(!strcmp(set1,set2))
{
cout<<"Equal!";
}else cout<<"Not equal!";
在c++中可以直接使用string类做字符串，string支持“=”运算符，无需借助函数。
Subset
判断子集。不能直接借助strcmp函数，因为strcmp是按照字典序返回大小，与两集合中元素是否重复无关。
朴素判断的时间复杂度为O(mn)
char set1[100],set2[100];
int len1=strlen(set1);
int len2=strlen(set2);
bool flag=1;
for(int i=0;i<len1;i++)
{
bool f=0;
for(int j=0;j<len2;j++)
{
if(set1[i]==set2[j])
{
f=1;
break;
}
}
if(f) continue;
else {
flag=0;
break;
}
}
if(flag) cout<<"A is a subset of B";
else cout<<"A is not a subset of B";
Union
求并集。我们可以通过连接两个set形成一个字符串，然后对新字符串进行make set操作，即可得到一个Union。
这样的时间复杂的约为make set的时间复杂度O((m+n)^2)。
或者是朴素算法遍历两个数组，时间复杂度为O(mn)
char set1[100],set2[100];
char set3[100];
int len1=strlen(set1);
int len2=strlen(set2);
strcpy(set3,set2);
int len3=strlen(set3);
bool flag=1;
for(int i=0;i<len1;i++)
{
bool f=0;
for(int j=0;j<len2;j++)
{
if(set1[i]==set2[j])
{
f=1;
break;
}
}
if(f) continue;
else {
set3[len3++]=set1[i];
}
}
另一种思路是使用two_point（前提是set经过了排序），然后使用类似归并排序的方式创建新集合，这里不在赘述。
时间复杂度为O(m+n)+O(log n)（排序的时间）
Intersetion
求交集。朴素算法仍为 O(mn)
char set1[100],set2[100];
char set3[100];
int tot=0;
cin>>set1;
cin>>set2;
int len1=strlen(set1);
int len2=strlen(set2);
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(set1[i]==set2[j])
{
set3[tot++]=set1[i];
break;
}
}
}
set3[tot]='\0';
Method 2
通过计数排序统计出现的元素，最后遍历计数数组，若非0则代表当前key是set的元素。
该方法除Make Set外，其他操作时间复杂度均为O(1).
Make Set
时间复杂度为O(n)，空间复杂度为2*n;
但我们可以通过二进制状态压缩实现空间复杂度的优化，
void make_set()
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[input[i]])
{
new_set[input[i]]=1;
}
}
return ;
}
Equal
bool check_equal()
{
for(int i=0;i<256;i++)
{
if(set1[i]!=set2[i])
{
return 0;
}
}
return 1;
}
Subset
bool check_subset()
{
for(int i=0;i<256;i++)
{
if(set1[i]==1&&set2[i]==0)
{
return 0;
}
}
return 1;
}
Union
void union_set()
{
for(int i=0;i<256;i++)
{
set1[i]+=set2[i];
}
return ;
}
Intersetion
void make_intersetion()
{
for(int i=0;i<256;i++)
{
intersetion[i]=set1[i]&&set2[i];
}
return ;
}
Example
以下给出该实验的几个实例，实现方式采用Method 2.
Task1
Write a method to produce a set from the input. (note: elements in the set are unordered, and no duplicated elements).
#include<bits/stdc++.h>
using namespace std;
int new_set[256]={0};
string input;
string empty_set="\\n";
void make_set()
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[input[i]])
{
new_set[input[i]]=1;
}
}
return ;
}
void out_set()
{
bool f=0;
for(int i=0;i<256;i++)
{
if(new_set[i])
{
if(f)
printf(",%c",i);
else {
f=1;
printf("{%c",i);
}
}
if(i==255&&f) cout<<"}";
}
if(f==0) cout<<"The set is empty!";
return ;
}
void rec()
{
memset(new_set,0,sizeof new_set);
}
int main()
{
rec();
make_set();
out_set();
return 0;
}
Task2
Given two sets, write a method to check if the two sets are equal
#include<bits/stdc++.h>
using namespace std;
int new_set[2][256];
string input;
string empty_set="\\n";
void make_set(int n)
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[n][input[i]])
{
new_set[n][input[i]]=1;
}
}
return ;
}
bool check_equal()
{
for(int i=0;i<256;i++)
{
if(new_set[0][i]!=new_set[1][i])
{
return 0;
}
}
return 1;
}
void rec()
{
memset(new_set,0,sizeof new_set);
}
int main()
{
rec();
for(int i=0;i<2;i++)
{
make_set(i);
}
if(check_equal())
{
cout<<"Equal.";
}else cout<<"Not equal.";
return 0;
}
Task3
Given two inputs, A and B, write a method to check if the A is a subset of the B.
#include<bits/stdc++.h>
using namespace std;
int new_set[2][256];
string input;
string empty_set="\\n";
void make_set(int n)
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[n][input[i]])
{
new_set[n][input[i]]=1;
}
}
return ;
}
bool check_subset()
{
for(int i=0;i<256;i++)
{
if(new_set[0][i]==1&&new_set[1][i]==0)
{
return 0;
}
}
return 1;
}
void rec()
{
memset(new_set,0,sizeof new_set);
return ;
}
int main()
{
rec();
for(int i=0;i<2;i++)
{
make_set(i);
}
if(check_subset())
{
cout<<"A is a subset of the B.";
}else cout<<"A is not a subset of the B.";
return 0;
}
Task4
Given two inputs, write a method to output the set union of these inputs.
#include<bits/stdc++.h>
using namespace std;
int new_set[2][256];
string input;
string empty_set="\\n";
void make_set(int n)
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[n][input[i]])
{
new_set[n][input[i]]=1;
}
}
return ;
}
void union_set()
{
for(int i=0;i<256;i++)
{
new_set[0][i]+=new_set[1][i];
}
return ;
}
void out_set()
{
bool f=0;
for(int i=0;i<256;i++)
{
if(new_set[0][i])
{
if(f)
printf(",%c",i);
else {
f=1;
printf("{%c",i);
}
}
if(i==255&&f) cout<<"}";
}
if(f==0) cout<<"The set is empty!";
return ;
}
void rec()
{
memset(new_set,0,sizeof new_set);
return ;
}
int main()
{
rec();
for(int i=0;i<2;i++)
{
make_set(i);
}
union_set();
out_set();
return 0;
}
Task5
Given two inputs, write a method that will output the set intersection of these inputs.
#include<bits/stdc++.h>
using namespace std;
int new_set[2][256];
int intersetion[256];
string input;
string empty_set="\\n";
void make_set(int n)
{
cin>>input;
if(input==empty_set) return ;
int len=input.size();
for(int i=0;i<len;i++)
{
if(input[i]==',') continue;
if(!new_set[n][input[i]])
{
new_set[n][input[i]]=1;
}
}
return ;
}
void make_intersetion()
{
for(int i=0;i<256;i++)
{
intersetion[i]=new_set[0][i]&&new_set[1][i];
}
return ;
}
void out_set()
{
bool f=0;
for(int i=0;i<256;i++)
{
if(intersetion[i])
{
if(f)
printf(",%c",i);
else {
f=1;
printf("{%c",i);
}
}
if(i==255&&f) cout<<"}";
}
if(f==0) cout<<"The set is empty!";
return ;
}
void rec()
{
memset(new_set,0,sizeof new_set);
return ;
}
int main()
{
rec();
for(int i=0;i<2;i++)
{
make_set(i);
}
make_intersetion();
out_set();
return 0;
}