C++实现关系与关系矩阵的代码详解

2024-04-02 19:04:59 384人浏览泡泡鱼

摘要

目录ADT集合关系关系矩阵功能实现关系的矩阵表示关系的性质判断关系的合成参考:ADT 集合 template<class Type> //集合的元素类型 class

ADT

集合

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);
    }
    
    M1.updateSize();
    printf("请输入关系R:(格式为\'a,b\'并用空格分割)\n");
    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){    //格式化输出矩阵,要定义常量成员函数
    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);
    }
    
    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);
    }
    
    M1.updateSize();
    printf("\n");
    return;
}
void outputMatrix(const RMatrix<char> &M1){    //格式化输出矩阵,要定义常量成员函数
    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);
    }
    
    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;
}