C++等价与偏序关系的矩阵处理
C++等价与偏序关系的矩阵处理
Set模板的使用说明：sevencheng798-C++ Set用法总结整理
草稿本：
编写一段代码，接收键盘的输入，输入集合X。 例如 ： 1,2,…,10 两种情况：偏序关系R分别为 (1)“小于等于”<=；(2)“大于等于”>= 2 建立关系R的关系矩阵，并在屏幕打印输出对应关系的哈塞图。 3．利用关系矩阵求解 4. 当集合X={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}时，R为定义在X的偏序关系{(a, b)| a小于等于b}，打印输出{2,3,4}的上界，下界，最小上界和最大下界。 等价关系的划分
代码如下：
#include <iostream> #include <set> #include <string> #include <vector> #include <sstream> using namespace std; void getSetElm(set<int> &S,vector<int> &v){ //将集合元素数组化，无需提前设置数组大小 int c=0; v.resize(S.size()); for(set<int>::iterator it=S.begin();it!=S.end();++it){ //将集合元素有序装入数组方便顺序访问 v[c]=*it; c++; //计数器 } return ; } int findEle(vector<int> v,int n){ //根据元素寻找对应下标 int k=v.size(); for(int i=0;i<k;i++){ if(v[i]==n) return i; } return -1; } void outputRelationMatrix(vector< vector<int> > M,set<int> S){ //输出关系矩阵 int k=S.size(); vector<int> v1(k); getSetElm(S,v1); for(int i=0;i<=k;i++){ for(int j=0;j<=k;j++){ if(!i){ if(!j) cout<< ; else cout<<v1[j-1]<< ; } else { if(!j){ cout<<v1[i-1]<< ; } else{ cout<<M[i-1][j-1]<< ; } } } cout<<endl; } return ; } void outputRelation(vector<set<int>> E){ //输出集合的等价类划分 int k=E.size(); for(int i=0;i<k;i++){ cout<<集合：; vector<int> tmp; getSetElm(E[i],tmp); int k1=tmp.size(); for(int j=0;j<k1;j++){ cout<<tmp[j]<< ; } cout<<endl; } return ; } void getEquivalenceClass(set<int> &S,vector< vector<int> > &M){ //根据等价关系对集合进行划分 vector<set<int>> equalClass; vector<int> v; getSetElm(S,v); vector<int> v1(v); //v1用于查询元素原有下标 for(int i=0;i<v.size();i++){ set<int> tmp; tmp.insert(v[i]); int a=findEle(v1,v[i]); //确定元素的原有下标 for(int j=i+1;j<v.size();j++){ int b=findEle(v1,v[j]); if(M[a][b]){ tmp.insert(v[j]); v.erase(v.begin()+j); //删除已归类的元素 j--; //少了一个元素 } } equalClass.push_back(tmp); //推入一个等价类 } outputRelation(equalClass); return ; } void inputSet(set<int> &S,string str=X){ //输入关系 str=Input Set +str+:\n; cout<<str; string s; getline(cin,s); stringstream ss(s); int tmp; while(ss>>tmp){ S.insert(tmp); } // for(set<int>::iterator it=S.begin();it!=S.end();it++){ // cout<<*it<< ; // } return ; } void getMod3(set<int> &S,vector<set<int>> &thr){ //获得对3取模的等价类 for(set<int>::iterator it=S.begin();it!=S.end();it++){ int k=*it; thr[k%3].insert(k); } return ; } void getMod5(set<int> &S,vector<set<int>> &fiv){ //获得对5取模的等价类 for(set<int>::iterator it=S.begin();it!=S.end();it++){ int k=*it; fiv[k%5].insert(k); } return ; } void getRelationMatrix(set<int> &S,vector<set<int>> &mod,vector< vector<int> > &M){ //由等价类创建关系 int k=mod.size(),n=S.size(); M.resize(n); for(int i=0;i<n;i++){ //创建一个n*n的矩阵 M[i].resize(n); } vector<int> elm(n); getSetElm(S,elm); for(int i=0;i<k;i++){ //遍历等价类 int k1=mod[i].size(); vector<int> e(k1); getSetElm(mod[i],e); for(int j=0;j<k1-1;j++){ //将等价类转化为关系矩阵 int a=findEle(elm,e[j]); //找出对应元素在矩阵中的位置 for(int p=j+1;p<k1;p++){ int b=findEle(elm,e[p]); M[a][b]=M[b][a]=1; //标记关系矩阵 } } } if(k==3) cout<<模3关系矩阵R3：\n; else cout<<模5关系矩阵R5：\n; outputRelationMatrix(M,S); } int main(){ set<int> rel; inputSet(rel); vector<set<int>> five(5),three(3); getMod3(rel,three); getMod5(rel,five); vector< vector<int> > M3,M5; getRelationMatrix(rel,three,M3); //先处理模3 getRelationMatrix(rel,five,M5); //再处理模5 cout<<按模3划分出的等价类如下：\n; getEquivalenceClass(rel,M3); //根据M3矩阵划分等价类 cout<<按模5划分出的等价类如下：\n; getEquivalenceClass(rel,M5); //根据M5矩阵划分等价类 return 0; } 先说结论：STL中的set模板用来写关系矩阵是真的反人类，非顺序容器的特性注定它就不适合转化成矩阵这种顺序容器的形式（二维数组），所以还是自己设计ADT效果更好。
实现功能：输入一位正数作为集合元素（一位是为了输出矩阵的格式规整，正数是因为负数会有问题但懒得解决），分别输出它按3取模所得的关系矩阵和等价类划分、按5取模所得的关系矩阵和等价类划分。
参考:[
]
偏序关系的重要元素求解
#include <iostream> #include <set> #include <string> #include <vector> #include <sstream> using namespace std; void getSetElm(set<int> &S,vector<int> &v){ //将集合元素数组化，无需提前设置数组大小 int c=0; v.resize(S.size()); for(set<int>::iterator it=S.begin();it!=S.end();++it){ //将集合元素有序装入数组方便顺序访问 v[c]=*it; c++; //计数器 } return ; } int findEle(vector<int> v,int n){ //根据元素寻找对应下标 int k=v.size(); for(int i=0;i<k;i++){ if(v[i]==n) return i; } return -1; } void outputRelationMatrix(vector< vector<int> > M,set<int> S){ //输出关系矩阵 int k=S.size(); vector<int> v1(k); getSetElm(S,v1); for(int i=0;i<=k;i++){ for(int j=0;j<=k;j++){ if(!i){ if(!j) cout<< ; else cout<<v1[j-1]<< ; } else { if(!j){ cout<<v1[i-1]<< ; } else{ cout<<M[i-1][j-1]<< ; } } } cout<<endl; } return ; } void findImpElm(set<int> &S,set<int> &sonS,vector< vector<int> > &M){ //全序的偏序关系求解四元与四界，不具有一般性 vector<int> s,son; set<int> low,up; getSetElm(sonS,son); getSetElm(S,s); int k=s.size(),k1=son.size(); int max1,max2,min1,min2; //极大元，最大元，极小元，最小元 for(int i=0;i<k;i++){ //全序情况下的求解法，属于特殊情况 int a=i,f1=1,f2=1; for(int j=0;j<k1;j++){ int b=findEle(s,son[j]); if(!M[a][b]) f1=0; if(!M[b][a]) f2=0; } if(f1){ //下界 low.insert(s[i]); } if(f2){ //上界 up.insert(s[i]); } f1=1; //极大元 f2=1; //极小元 int f3=1,f4=1; //最大元和最小元 for(int j=0;j<k;j++){ //四元 if(j==i) continue; //避开矩阵的对角线 int b=j,tmp=M[i][j],rtmp=M[j][i]; if(tmp){ //存在元素e使得s[i]<e f1=0; //非极大元 f3=0; //非最大元 } if(!tmp){ //存在元素e使得s[i]<e不成立 f4=0; //非最小元 } if(rtmp){ //存在元素e<s[i] f2=0; //非极小元 f4=0; //非最小元 } if(!rtmp){ //存在元素e使得e<s[i]不成立 f3=0; //非最大元 } } if(f1) {max1=s[i];} //极大元 if(f2) {min1=s[i];} //极小元 if(f3) {max2=s[i];} //最大元 if(f4) {min2=s[i];} //最小元 } cout<<集合X在该关系下的重要元素：\n; cout<<极大元：<<max1<<endl; cout<<极小元：<<min1<<endl; cout<<最大元：<<max2<<endl; cout<<最小元：<<min2<<endl; vector<int> v1,v2; getSetElm(up,v1); //v1上界 getSetElm(low,v2); //v2下界 int len1=v1.size(),len2=v2.size(),maxLow,minUp; //上下确界 cout<<子集sonX关于集合X在该关系下的重要元素：\n; cout<<上界：; for(int i=0;i<len1;i++){ cout<<v1[i]<< ; int f=1,a=findEle(s,v1[i]); for(int j=0;j<len1;j++){ int b=findEle(s,v1[j]); //确认在原矩阵中的下标 if(!M[a][b]){ //最小上界 f=0; break; } } if(f) minUp=v1[i]; //上确界 } cout<<endl<<上确界：<<minUp<<endl; cout<<下界：; for(int i=0;i<len2;i++){ cout<<v2[i]<< ; int f=1,a=findEle(s,v2[i]); for(int j=0;j<len2;j++){ int b=findEle(s,v2[j]); //确认在原矩阵中的下标 if(!M[b][a]){ //最大下界 f=0; break; } } if(f) maxLow=v2[i]; //下确界 } cout<<endl<<下确界：<<maxLow<<endl; return; } void inputSet(set<int> &S,string str=X){ //输入关系 str=Input Set +str+:\n; cout<<str; string s; getline(cin,s); stringstream ss(s); int tmp; while(ss>>tmp){ S.insert(tmp); } // for(set<int>::iterator it=S.begin();it!=S.end();it++){ // cout<<*it<< ; // } return ; } void getSmall(set<int> &S,vector< vector<int> > &sml){ //获得<=的偏序关系矩阵 int k=S.size(); sml.resize(k); for(int i=0;i<k;i++){ sml[i].resize(k,0); sml[i][i]=1; //自反性 } vector<int> v; getSetElm(S,v); for(int i=0;i<k-1;i++){ //传递性 int a=i; //确认下标位置 for(int j=i+1;j<k;j++){ int b=j; sml[a][b]=1; } } cout<<小于等于的偏序关系矩阵：\n; outputRelationMatrix(sml,S); cout<<哈塞图：\n; for(int i=k-1;i>=0;i--){ if(i!=k-1) cout<<|<<endl; cout<<v[i]<<endl; } return ; } void getBig(set<int> &S,vector< vector<int> > &big){ //获得>=的偏序关系矩阵 int k=S.size(); big.resize(k); for(int i=0;i<k;i++){ big[i].resize(k,0); big[i][i]=1; //自反性 } vector<int> v; getSetElm(S,v); for(int i=1;i<k;i++){ //传递性 int a=i; //确认下标位置 for(int j=0;j<i;j++){ int b=j; big[a][b]=1; } } cout<<大于等于的偏序关系矩阵：\n; outputRelationMatrix(big,S); cout<<哈塞图：\n; for(int i=0;i<k;i++){ if(i) cout<<|<<endl; cout<<v[i]<<endl; } return ; } int main(){ set<int> rel,sonRel; inputSet(rel); vector< vector<int> > M1,M2; getSmall(rel,M1); //M1为小于等于 getBig(rel,M2); //M2为大于等于 inputSet(sonRel,sonX); cout<<\n小于等于关系下的重要元素：\n; findImpElm(rel,sonRel,M1); //求解小于等于关系下的重要元素 cout<<\n大于等于关系下的重要元素：\n; findImpElm(rel,sonRel,M2); //求解大于等于关系下的重要元素 return 0; } 偏序关系的处理比想象中难不少，好在实验只要求写小于等于与大于等于，可以只考虑全序状况，做特殊的关系处理求解，若是追求一般性则难度不小。
实现功能：输入集合X，输出两种偏序关系的关系矩阵，再输入子集sonX，输出两种偏序关系下X的四元与sonX的四界。
KMP算法
待实现目标：在长度为n的文本串中查找一个长度为m的模式串。
暴力匹配：
KMP匹配：
分析：其重要思想在于 i 不做回退，而是选择处理 j ，根据其退出位置找到最近且有共同前缀的位置。
算法步骤如下：
- 若
S[i]==P[j]，则i++ && j++ - 若
s[i]!=P[j] && j!=0，则j=Next[j] - 若
s[i]!=P[j] && j==0，则i++
确定 Next[] 数组是KMP算法的核心思想：
int Next[MAXN]; int getFail(char *p, int plen){ //预计算Next[]。用于失配的情况下，得到j回溯的位置 Next[0]=0; Next[1]=0; for(int i=1; i < plen; i++){ int j = Next[i]; //在i位置退出后可能匹配的位置 while(j && p[i] != p[j]) j = Next[j]; //寻找前缀相同的可能前缀子串 Next[i+1] = (p[i]==p[j]) ? j+1 : 0; //匹配相同前缀的子串 } } 想要理解透彻会比较费时间，也比较绕，可以参考：v_JULY_v-从头到尾理解KMP
简单补充一下自己的理解：
首先要明确，通过分析模式串的结构寻找 j 的可替代位置是KMP的核心，在确定 Next[i] 时，比较的是 i-1 位置的匹配结果，换言之一定要弄清楚，位置 i 的匹配结果决定的是 Next[i] 的值，也就是 i 位置前缀匹配则不论 P[i+1] 是什么，都已经规定了 i+1 的退出位置，这一点在圈圈绕绕理解KMP时是很重要的。
注意到评论区有如下提问：
非常感谢作者！！！初学者有一个地方还不太明白，想请教一下各位大佬：按照这个未优化的next数组求法，模式串p = “ababaa”得到的结果是 -1 0 0 1 2 3 。但是按照匹配原则来说，如果末尾的a匹配失败了以后应该跳转到p[0]而不是p[3]。这个未优化的求法是不是应该再增加对于末尾的字符的一次判断比较好呀？~ 他的问题本身很好解决，但他让我想到了另一个问题，这个问题正与前面规定退出位置的优先级有关。举个例子，给出模式串P1：
a b a b a b 0 0 0 1 2 3 注意 P[5]=b 的退出值 Next[5]=3 ，但实际上若是在 P[5] 退出，这个退出值必然是0，这是因为 P[5]=P[3]=P[1]=b ，显然退出时不过是将这个比较过程重复了一遍，但是整合时会发现如果跳出位置的值与待跳出位置的值相等，也就是 P[Next[j]]=P[j] ，那这里是可以再向前跳一步的，就像我们计算 Next[] 碰到前缀不一致时那样：
while(P[Next[j]]==P[j] && j!=0){ j=Next[j]; } 但是这里说的都是废话，理由有以下三点：
- 我们知道
Next[i]的值是在i-1位置确定的，因此要做这种比较需要额外的运算，不方便也破坏了原来的算法结构，也就是一种类似DP的前置状态的无后效性转移。 - 这个迭代过程的退出值是无法存储的，如果将它存储至
Next[i]中，试问在i位置前缀匹配的情况下，Next[i]+1的值已经无法作为标记，Next[i+1]的值怎么办？ - 在实际计算中，这种优化其实一点时间都没有节省。
提出来只是为了方便更好的理解KMP算法。