C++實現關係與關係矩陣的程式碼詳解

2022-04-04 10:00:18

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=%dn",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;
}