目录
  • ADT
    • 集合
    • 关系
    • 关系矩阵
  • 功能实现
    • 关系的矩阵表示
    • 关系的性质判断
    • 关系的合成
  • 参考:

    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);
        }
        /*
        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++实现伪随机

    声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。