亲宝软件园·资讯

展开

C++关系矩阵

Festu 人气:0

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

功能实现

关系的矩阵表示

根据关系输出矩阵：

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");
    stringstream ss2(str);
    while(ss2>>inp){
    int k1=M1.getR(),k2=M1.getC();
    Set<char> A=M1.getDom(),B=M1.getRan();
    */
    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);
    }
    /*
    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");
    stringstream ss2(str);
    while(ss2>>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){    //格式化输出矩阵,要定义常量成员函数
    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++实现伪随机

加载全部内容
相关教程
猜你喜欢
用户评论