C++实现关系与关系矩阵
C++实现关系与关系矩阵
其实C++有内置的Set模板的...
ADT
集合
template //集合的元素类型
class Set{ //集合ADT
int size; //基数
vector 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 关系
template
class Relation{
Set dom; //定义域
Set 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 getDom()const { return dom; } //返回定义域
Set 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 RMatrix:public Relation{
vector< vector > m; //二维矩阵用vector实现,注意不能使用bool类型，它有很高的特殊性
public:
RMatrix(int r_,int c_):Relation(r_,c_){
for(int i=0;i v(c_,0);
m.push_back(v); //推入r_个长度为c_的vector数组构成一个r*c的二维数组
}
}
RMatrix():Relation(){ //不输入矩阵大小时
for(int i=0;i v(MAX_NUM,0);
m.push_back(v);
}
}
RMatrix(const RMatrix &M){ //复制构造函数
// printf("here!");
Set Dom=M.getDom(),Ran=M.getRan();
int k1=Dom.getSize(),k2=Ran.getSize();
for(int i=0;i::pushDom(Dom[i]);
}
for(int i=0;i::pushRan(Ran[i]);
}
m.resize(k1);
for(int i=0;i::getDom().getSize(); //在子类中调用基类函数需要制定基类
int col=Relation::getRan().getSize();
// printf("row=%d,col=%d",row,col);
m.resize(row);
for(int i=0;i operator[](int p1)const { return m[p1]; } //可以直接双括号使用!
void set(int p1,int p2,short e){ //设置矩阵值
m[p1][p2]=e;
}
void push(vector v){ //添加矩阵的行
m.push_back(v);
}
/* 将两个关系矩阵合成，括号内的在右 */
RMatrix matrixSynthesis(const RMatrix &M1)const {
RMatrix M; //此处的M是临时变量，必定被销毁，无法作为引用被返回 ( d=Relation::getDom(),r=M1.getRan(); //矩阵合成的行列关系差点弄错!
int k1=d.getSize(),k2=r.getSize(),k3=M1.getR();
for(int i=0;i::getR(),c=Relation::getC();
for(int i=0;i::getR();
for(int i=0;i::getR();
for(int i=0;i::getR();
for(int i=0;i::getR();
for(int i=0;i M_=matrixSynthesis(*this); //const函数只能调用const函数 ::getR();
for(int i=0;i 处若是给函数返回值加上引用会报一个警告，调用函数后集合ADT处会出现一个内存错误，这是因为M此处是临时变量，是一定被销毁的，所以作为引用被返回当然就出了问题，而此处不用引用是完全可行的。如果一定要用引用，也许可以考虑把M定义为静态变量。处曾有过一个报错:"passing 'const RMatrix' as 'this' argument discards qualifiers"，原因是当时我只将 isPassing函数设为const，却没把其中调用的matrixSynthesis函数设为const。
功能实现
关系的矩阵表示
根据关系输出矩阵：
void inputRelation(RMatrix &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 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 &M1){ //格式化输出矩阵,要定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set 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 M1; //设置集合的元素为字符类型
inputRelation(M1);
outputMatrix(M1);
return 0;
}
根据矩阵输出关系序偶：
void inputMatrix(RMatrix &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 A=M1.getDom(),B=M1.getRan();
*/
M1.updateSize();
printf("请输入关系矩阵:(空格分隔)\n");
int k=M1.getC(),tmp;
for(int i=0;i &M1){ //格式化输出序偶,记得定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set Dom=M1.getDom(),Ran=M1.getRan();
printf("关系序偶如下：\n");
for(int i=0;i",i,j);
printf("(%c,%c) ",Dom[i],Ran[j]);
}
}
printf("\n");
}
}
int main(){
RMatrix M1; //设置集合的元素为字符类型
inputMatrix(M1);
outputRelation(M1);
return 0;
}
关系的性质判断
I. 输入一个包含n个元素的集合A，要求随机产生3个定义在集合A上的不同的关系R1，R2，R3，其中，R1和R2是自反且对称的，R3是反对称的，并显示R1，R2，R3的关系矩阵表示。
先上一个尝试用伪随机实现的算法
void inputSet(RMatrix &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 A=M1.getDom(),B=M1.getRan();
*/
M1.updateSize();
printf("\n");
return;
}
void outputMatrix(const RMatrix &M1){ //格式化输出矩阵,要定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set 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 &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 M1; //设置集合的元素为字符类型
inputSet(M1);
RMatrix 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 &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 A=M1.getDom(),B=M1.getRan();
*/
M1.updateSize();
printf("\n");
return;
}
void outputMatrix(const RMatrix &M1,string str=""){ //格式化输出矩阵,要定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set 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 &M,bool isSelf,bool isSymmetric,bool antiSymmetric){ //后三个参数标记函数性质,分别为自反性，对称性，反对称性
M.randomRelation(); //先基础随机化处理
int r=M.getC();
if(isSelf){ //补足自反性
if(!M.isSelf()){
for(int i=0;i M1; //设置集合的元素为字符类型
inputSet(M1);
RMatrix 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 &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 &M1){
if(M1.isSelf()) printf("具有自反性\n");
if(M1.isSymmetric()) printf("具有对称性\n");
if(M1.antiSymmetric()) printf("具有反对称性\n");
if(M1.isPassing()) printf("具有传递性\n");
}
int main(){
RMatrix M1(6,6);
inputMatrix(M1);
judgeMatrix(M1);
return 0;
}
关系的合成
关系合成运算：
void outputMatrix(const RMatrix &M1){ //格式化输出矩阵,要定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set 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 &M1,RMatrix &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 multiplyMatrix(const RMatrix &M1,const RMatrix &M2){ //默认集合元素就是char类型~
RMatrix M;
Set d=M1.getDom(),r=M2.getRan();
int k1=d.getSize(),k2=r.getSize(),k3=M2.getR();
for(int i=0;i &M1){ //格式化输出序偶,记得定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set Dom=M1.getDom(),Ran=M1.getRan();
printf("关系序偶如下：\n");
for(int i=0;i",i,j);
printf("(%c,%c) ",Dom[i],Ran[j]);
}
}
printf("\n");
}
}
void getCalculate(const RMatrix &M1,const RMatrix &M2){
RMatrix M=M1.matrixSynthesis(M2); //布尔积运算
printf("布尔积运算所得的");
outputMatrix(M); //输出布尔积结果
RMatrix M_=multiplyMatrix(M1,M2); //矩阵乘积运算
printf("矩阵乘积所得的");
outputMatrix(M_);
outputRelation(M);
return;
}
int main(){
RMatrix M1,M2; //设置集合的元素为字符类型
inputRelation(M1,M2);
getCalculate(M1,M2);
return 0;
}
缝合并优化了几个函数。
关系的n次运算:
void outputMatrix(const RMatrix &M1){ //格式化输出矩阵,要定义常量成员函数
int k1=M1.getR(),k2=M1.getC();
Set 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 &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 &M1,int n){
RMatrix M(M1);
int n_=n;
n--;
while(n--)
M=M.matrixSynthesis(M);
printf("得出 R^%d",n_);
outputMatrix(M);
return;
}
int main(){
RMatrix M1; //设置集合的元素为字符类型
inputRelation(M1);
int n;
printf("请输入n:");
scanf("%d",&n);
nR(M1,n);
return 0;
}
参考:[
知乎-vector
新世纪debug战士-C++实现伪随机
]