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; }
