template<class Type> //集合的元素类型 class Set{ //集合ADT int size; //基数 vector<Type> p; public: Set():size(0){} Set(int s):size(s){ p.resize(s); //重置大小 } int getSize()const{ return size; } void push(Type e){ //添加元素 size++; p.push_back(e); } void set(int pos,Type e){ //设置元素值 p[pos]=e; } Type operator[](int i){ return p[i]; } //下标读取 int findElem(Type e){ //返回指定元素的下标 for(int i=0;i<size;i++){ if(p[i]==e) return i; } return -1; } };
template<class Type> class Relation{ Set<Type> dom; //定义域 Set<Type> ran; //值域 public: Relation():dom(),ran(){} //无规模的初始化 Relation(int r_,int c_):dom(r_),ran(c_){} //有规模的初始化 int getR()const { return dom.getSize(); } //返回行,基类私有成员只可调用基类非私有函数获得 int getC()const { return ran.getSize(); } //返回列 Set<Type> getDom()const { return dom; } //返回定义域 Set<Type> getRan()const { return ran; } //返回值域 void pushDom(Type e){ dom.push(e); } //给定义域添加元素 void pushRan(Type e){ ran.push(e); } //给值域添加元素 int findDom(Type e){ //寻找定义域中元素的位置 return dom.findElem(e); } int findRan(Type e){ //寻找值域中元素的位置 return ran.findElem(e); } };
template<class Type> class RMatrix:public Relation<Type>{ vector< vector<short> > m; //二维矩阵用vector实现,注意不能使用bool类型,它有很高的特殊性 public: RMatrix(int r_,int c_):Relation<Type>(r_,c_){ for(int i=0;i<r_;i++){ vector<short> v(c_,0); m.push_back(v); //推入r_个长度为c_的vector数组构成一个r*c的二维数组 } } RMatrix():Relation<Type>(){ //不输入矩阵大小时 for(int i=0;i<MAX_NUM;i++){ vector<short> v(MAX_NUM,0); m.push_back(v); } } RMatrix(const RMatrix<Type> &M){ //复制构造函数 // printf("here!"); Set<Type> Dom=M.getDom(),Ran=M.getRan(); int k1=Dom.getSize(),k2=Ran.getSize(); for(int i=0;i<k1;i++){ Relation<Type>::pushDom(Dom[i]); } for(int i=0;i<k2;i++){ Relation<Type>::pushRan(Ran[i]); } m.resize(k1); for(int i=0;i<k1;i++){ m[i].resize(0); for(int j=0;j<k2;j++){ m[i].push_back(M[i][j]); // printf("%d",m[i][j]); } } } void updateSize(){ //根据定义域和值域的基数设置矩阵规模 int row=Relation<Type>::getDom().getSize(); //在子类中调用基类函数需要制定基类 int col=Relation<Type>::getRan().getSize(); // printf("row=%d,col=%d",row,col); m.resize(row); for(int i=0;i<row;i++){ m[i].resize(0); for(int j=0;j<col;j++){ m[i].push_back(short(0)); // printf("%d",m[i][j]); } } return; } vector<short> operator[](int p1)const { return m[p1]; } //可以直接双括号使用! void set(int p1,int p2,short e){ //设置矩阵值 m[p1][p2]=e; } void push(vector<short> v){ //添加矩阵的行 m.push_back(v); } /* 将两个关系矩阵合成,括号内的在右 */ RMatrix<Type> matrixSynthesis(const RMatrix<Type> &M1)const { RMatrix<Type> M; //此处的M是临时变量,必定被销毁,无法作为引用被返回 (<!-1) Set<Type> d=Relation<Type>::getDom(),r=M1.getRan(); //矩阵合成的行列关系差点弄错! int k1=d.getSize(),k2=r.getSize(),k3=M1.getR(); for(int i=0;i<k1;i++){ M.pushDom(d[i]); } for(int i=0;i<k2;i++){ M.pushRan(r[i]); } M.updateSize(); for(int i=0;i<k1;i++){ for(int j=0;j<k2;j++){ bool f=0; for(int p=0;p<k3;p++){ if(m[i][p] && M1[p][j]) f=1; } if(f) M.set(i,j,f); } } return M; } void randomRelation(){ //随机生成一段关系,需要放在updatesize之后 // printf("time=%d\n",time(0)); //伪随机的实现需要新添加两个文件头 srand(time(0)); //初始化随机数 int r=Relation<Type>::getR(),c=Relation<Type>::getC(); for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ m[i][j]=rand()%2; //生成0或1 } } return ; } bool isSelf()const { //自反性检测 int r=Relation<Type>::getR(); for(int i=0;i<r;i++){ if(!m[i][i]) return 0; } return 1; } bool antiSelf()const { //反自反性检测 int r=Relation<Type>::getR(); for(int i=0;i<r;i++){ if(m[i][i]) return 0; } return 1; } bool isSymmetric()const { //对称性 int r=Relation<Type>::getR(); for(int i=0;i<r;i++){ for(int j=i+1;j<r;j++){ if(m[i][j]!=m[j][i]) return 0; } } return 1; } bool antiSymmetric()const { //反对称性,注意都为0不违反反对称性! int r=Relation<Type>::getR(); for(int i=0;i<r;i++){ for(int j=i+1;j<r;j++){ if(m[i][j] && m[i][j]==m[j][i]) return 0; } } return 1; } bool isPassing()const { //传递性 RMatrix<Type> M_=matrixSynthesis(*this); //const函数只能调用const函数 <!-2 int r=Relation<Type>::getR(); for(int i=0;i<r;i++){ for(int j=0;j<r;j++){ if(m[i][j]==0 && M_[i][j]==1) return 0; } } return 1; } };
<!-1
处若是给函数返回值加上引用会报一个警告,调用函数后集合ADT处会出现一个内存错误,这是因为M此处是临时变量,是一定被销毁的,所以作为引用被返回当然就出了问题,而此处不用引用是完全可行的。如果一定要用引用,也许可以考虑把M定义为静态变量。<!-2
处曾有过一个报错:"passing 'const RMatrix<char>' as 'this' argument discards qualifiers",原因是当时我只将 isPassing
函数设为const,却没把其中调用的 matrixSynthesis
函数设为const。根据关系输出矩阵:
void inputRelation(RMatrix<char> &M1){ //输入关系 printf("请输入集合A的元素:\n"); string str; // cin.get(); //这里不能直接这样写,因为前面有可能是没有换行符的,那你就会少读一个字符,所以只能灵活加 getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); M1.pushRan(inp); } /* printf("请输入集合B的元素:\n"); getline(cin,str); stringstream ss2(str); while(ss2>>inp){ M1.pushRan(inp); } int k1=M1.getR(),k2=M1.getC(); Set<char> A=M1.getDom(),B=M1.getRan(); */ M1.updateSize(); printf("请输入关系R:(格式为\'a,b\'并用空格分割)\n"); getline(cin,str); stringstream ss(str); int a,b; int isA=1; while(ss>>inp){ //使用">>"流输入字符类型会自动忽略空格...抽象了,printf是读取空格的 // printf("%c",inp); if(inp==',') isA=0; else{ if(isA) a=M1.findDom(inp); else{ b=M1.findRan(inp); isA=1; M1.set(a,b,1); } } } printf("\n"); return; } void outputMatrix(const RMatrix<char> &M1){ //格式化输出矩阵,要定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系矩阵如下:\n"); for(int i=0;i<=k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<=k2;j++){ if(i==0 && j==0) printf(" "); else if(j==0) printf("%c ",Dom[i-1]); else if(i==0) printf("%c ",Ran[j-1]); else{ printf("%d ",M1[i-1][j-1]); } } printf("\n"); } } int main(){ RMatrix<char> M1; //设置集合的元素为字符类型 inputRelation(M1); outputMatrix(M1); return 0; }
根据矩阵输出关系序偶:
void inputMatrix(RMatrix<char> &M1){ //输入矩阵 printf("请输入集合A的元素:\n"); string str; getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); M1.pushRan(inp); } /* printf("请输入集合B的元素:\n"); getline(cin,str); stringstream ss2(str); while(ss2>>inp){ M1.pushRan(inp); } int k1=M1.getR(),k2=M1.getC(); Set<char> A=M1.getDom(),B=M1.getRan(); */ M1.updateSize(); printf("请输入关系矩阵:(空格分隔)\n"); int k=M1.getC(),tmp; for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ scanf("%d",&tmp); if(tmp) M1.set(i,j,tmp); } } printf("\n"); return; } void outputRelation(const RMatrix<char> &M1){ //格式化输出序偶,记得定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系序偶如下:\n"); for(int i=0;i<k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<k2;j++){ if(M1[i][j]){ // printf("i=%d,j=%d->",i,j); printf("(%c,%c) ",Dom[i],Ran[j]); } } printf("\n"); } } int main(){ RMatrix<char> M1; //设置集合的元素为字符类型 inputMatrix(M1); outputRelation(M1); return 0; }
I. 输入一个包含n个元素的集合A,要求随机产生3个定义在集合A上的不同的关系R1,R2,R3,其中,R1和R2是自反且对称的,R3是反对称的,并显示R1,R2,R3的关系矩阵表示。
先上一个尝试用伪随机实现的算法
void inputSet(RMatrix<char> &M1){ //输入集合 printf("请输入集合A的元素:\n"); string str; getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); M1.pushRan(inp); } /* printf("请输入集合B的元素:\n"); getline(cin,str); stringstream ss2(str); while(ss2>>inp){ M1.pushRan(inp); } int k1=M1.getR(),k2=M1.getC(); Set<char> A=M1.getDom(),B=M1.getRan(); */ M1.updateSize(); printf("\n"); return; } void outputMatrix(const RMatrix<char> &M1){ //格式化输出矩阵,要定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系矩阵如下:\n"); for(int i=0;i<=k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<=k2;j++){ if(i==0 && j==0) printf(" "); else if(j==0) printf("%c ",Dom[i-1]); else if(i==0) printf("%c ",Ran[j-1]); else{ printf("%d ",M1[i-1][j-1]); } } printf("\n"); } } void getRandom(RMatrix<char> &M,bool isSelf,bool isSymmetric,bool antiSymmetric){ //后三个参数标记函数性质,分别为自反性,对称性,反对称性 while(1){ M.randomRelation(); if(M.isSelf()==isSelf && M.isSymmetric()==isSymmetric && M.antiSymmetric()==antiSymmetric) return; } } int main(){ RMatrix<char> M1; //设置集合的元素为字符类型 inputSet(M1); RMatrix<char> M2(M1),M3(M1); getRandom(M1,1,1,0); getRandom(M2,1,1,0); getRandom(M3,0,0,1); outputMatrix(M1); outputMatrix(M2); outputMatrix(M3); return 0; }
构想是挺美好的,但是伪随机的效果让这个方法行不通,因为随机的效率太低,是按秒变化的,除非直接写在成员函数中根据一个seed一直随机,否则程序不可能通畅,但写在成员函数也不好,太特殊。
以下是后手加工版本:
void inputSet(RMatrix<char> &M1){ //输入集合 printf("请输入集合A的元素:\n"); string str; getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); M1.pushRan(inp); } /* printf("请输入集合B的元素:\n"); getline(cin,str); stringstream ss2(str); while(ss2>>inp){ M1.pushRan(inp); } int k1=M1.getR(),k2=M1.getC(); Set<char> A=M1.getDom(),B=M1.getRan(); */ M1.updateSize(); printf("\n"); return; } void outputMatrix(const RMatrix<char> &M1,string str=""){ //格式化输出矩阵,要定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); str=str+"关系矩阵如下:\n"; //连接矩阵名称 printf("%s",str.c_str()); for(int i=0;i<=k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<=k2;j++){ if(i==0 && j==0) printf(" "); else if(j==0) printf("%c ",Dom[i-1]); else if(i==0) printf("%c ",Ran[j-1]); else{ printf("%d ",M1[i-1][j-1]); } } printf("\n"); } } void getRandom(RMatrix<char> &M,bool isSelf,bool isSymmetric,bool antiSymmetric){ //后三个参数标记函数性质,分别为自反性,对称性,反对称性 M.randomRelation(); //先基础随机化处理 int r=M.getC(); if(isSelf){ //补足自反性 if(!M.isSelf()){ for(int i=0;i<r;i++){ M.set(i,i,1); } } } if(isSymmetric){ //补足对称性 if(!M.isSymmetric()){ for(int i=0;i<r;i++){ for(int j=i+1;j<r;j++){ if(M[i][j]!=M[j][i]) M.set(j,i,M[i][j]); } } } } if(antiSymmetric){ //补足反对称性 if(!M.antiSymmetric()){ for(int i=0;i<r;i++){ for(int j=i+1;j<r;j++){ if(M[i][j] && M[i][j]==M[j][i]) M.set(j,i,0); } } } } } int main(){ RMatrix<char> M1; //设置集合的元素为字符类型 inputSet(M1); RMatrix<char> M2(M1),M3(M1); getRandom(M1,1,1,0); getRandom(M2,1,1,0); getRandom(M3,0,0,1); outputMatrix(M1,"R1"); outputMatrix(M2,"R2"); outputMatrix(M3,"R3"); return 0; }
输出函数优化了一下,可以输出矩阵名称了。
II.给定一个矩阵判断其性质,并输出结果
void inputMatrix(RMatrix<char> &M1){ //输入矩阵 for(int i=0;i<6;i++){ M1.setDom(i,' '); M1.setRan(i,' '); } printf("请输入关系矩阵:(空格分隔)\n"); int k=6,tmp; for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ scanf("%d",&tmp); if(tmp) M1.set(i,j,tmp); } } printf("\n"); return; } void judgeMatrix(const RMatrix<char> &M1){ if(M1.isSelf()) printf("具有自反性\n"); if(M1.isSymmetric()) printf("具有对称性\n"); if(M1.antiSymmetric()) printf("具有反对称性\n"); if(M1.isPassing()) printf("具有传递性\n"); } int main(){ RMatrix<char> M1(6,6); inputMatrix(M1); judgeMatrix(M1); return 0; }
关系合成运算:
void outputMatrix(const RMatrix<char> &M1){ //格式化输出矩阵,要定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系矩阵如下:\n"); for(int i=0;i<=k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<=k2;j++){ if(i==0 && j==0) printf(" "); else if(j==0) printf("%c ",Dom[i-1]); else if(i==0) printf("%c ",Ran[j-1]); else{ printf("%d ",M1[i-1][j-1]); } } printf("\n"); } } void inputRelation(RMatrix<char> &M1,RMatrix<char> &M2){ //输入关系 printf("请输入集合A的元素:\n"); string str; getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); } printf("请输入集合B的元素:\n"); getline(cin,str); stringstream ss2(str); while(ss2>>inp){ M1.pushRan(inp); M2.pushDom(inp); } printf("请输入集合C的元素:\n"); getline(cin,str); stringstream ss3(str); while(ss3>>inp){ M2.pushRan(inp); } M1.updateSize(); M2.updateSize(); printf("请输入关系R1:(格式为\'a,b\'并用空格分割)\n"); getline(cin,str); stringstream ss(str); int a,b; int isA=1; while(ss>>inp){ //使用">>"流输入字符类型会自动忽略空格...抽象了,printf是读取空格的 // printf("%c",inp); if(inp==',') isA=0; else{ if(isA) a=M1.findDom(inp); else{ b=M1.findRan(inp); isA=1; M1.set(a,b,1); } } } printf("R1"); outputMatrix(M1); printf("请输入关系R2:(格式为\'a,b\'并用空格分割)\n"); getline(cin,str); stringstream ss_(str); isA=1; while(ss_>>inp){ //使用">>"流输入字符类型会自动忽略空格...抽象了,printf是读取空格的 // printf("%c",inp); if(inp==',') isA=0; else{ if(isA) a=M2.findDom(inp); else{ b=M2.findRan(inp); isA=1; M2.set(a,b,1); } } } printf("R2"); outputMatrix(M2); printf("\n"); return; } RMatrix<char> multiplyMatrix(const RMatrix<char> &M1,const RMatrix<char> &M2){ //默认集合元素就是char类型~ RMatrix<char> M; Set<char> d=M1.getDom(),r=M2.getRan(); int k1=d.getSize(),k2=r.getSize(),k3=M2.getR(); for(int i=0;i<k1;i++){ M.pushDom(d[i]); } for(int i=0;i<k2;i++){ M.pushRan(r[i]); } M.updateSize(); for(int i=0;i<k1;i++){ for(int j=0;j<k2;j++){ int f=0; for(int p=0;p<k3;p++){ if(M1[i][p] && M2[p][j]) f+=1; } if(f) M.set(i,j,f); } } return M; } void outputRelation(const RMatrix<char> &M1){ //格式化输出序偶,记得定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系序偶如下:\n"); for(int i=0;i<k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<k2;j++){ if(M1[i][j]){ // printf("i=%d,j=%d->",i,j); printf("(%c,%c) ",Dom[i],Ran[j]); } } printf("\n"); } } void getCalculate(const RMatrix<char> &M1,const RMatrix<char> &M2){ RMatrix<char> M=M1.matrixSynthesis(M2); //布尔积运算 printf("布尔积运算所得的"); outputMatrix(M); //输出布尔积结果 RMatrix<char> M_=multiplyMatrix(M1,M2); //矩阵乘积运算 printf("矩阵乘积所得的"); outputMatrix(M_); outputRelation(M); return; } int main(){ RMatrix<char> M1,M2; //设置集合的元素为字符类型 inputRelation(M1,M2); getCalculate(M1,M2); return 0; }
缝合并优化了几个函数。
关系的n次运算:
void outputMatrix(const RMatrix<char> &M1){ //格式化输出矩阵,要定义常量成员函数 int k1=M1.getR(),k2=M1.getC(); Set<char> Dom=M1.getDom(),Ran=M1.getRan(); printf("关系矩阵如下:\n"); for(int i=0;i<=k1;i++){ // printf("here?"); //手动断点 for(int j=0;j<=k2;j++){ if(i==0 && j==0) printf(" "); else if(j==0) printf("%c ",Dom[i-1]); else if(i==0) printf("%c ",Ran[j-1]); else{ printf("%d ",M1[i-1][j-1]); } } printf("\n"); } } void inputRelation(RMatrix<char> &M1){ //输入关系 printf("请输入集合A的元素:\n"); string str; // cin.get(); //这里不能直接这样写,因为前面有可能是没有换行符的,那你就会少读一个字符,所以只能灵活加 getline(cin,str); stringstream ss1(str); char inp; while(ss1>>inp){ M1.pushDom(inp); M1.pushRan(inp); } M1.updateSize(); printf("请输入关系R:(格式为\'a,b\'并用空格分割)\n"); getline(cin,str); stringstream ss(str); int a,b; int isA=1; while(ss>>inp){ //使用">>"流输入字符类型会自动忽略空格...抽象了,printf是读取空格的 // printf("%c",inp); if(inp==',') isA=0; else{ if(isA) a=M1.findDom(inp); else{ b=M1.findRan(inp); isA=1; M1.set(a,b,1); } } } printf("已知R"); outputMatrix(M1); return; } void nR(const RMatrix<char> &M1,int n){ RMatrix<char> M(M1); int n_=n; n--; while(n--) M=M.matrixSynthesis(M); printf("得出 R^%d",n_); outputMatrix(M); return; } int main(){ RMatrix<char> M1; //设置集合的元素为字符类型 inputRelation(M1); int n; printf("请输入n:"); scanf("%d",&n); nR(M1,n); return 0; }
参考:[
知乎-vector<bool>
新世纪debug战士-C++实现伪随机
]