北京化工大学数据结构2022/10/20作业 题解

目录

问题 A: 函数可变参数练习-附加代码模式

问题 B: 多维下标向一维下标的换算

问题 C: 稀疏矩阵类型判断

问题 D: 稀疏矩阵转换成简记形式-附加代码模式

问题 E: 根据三元组输出稀疏矩阵

问题 F: 三元组法表示的稀疏矩阵，计算每行非零元个数，行向量，每列非零元个数，列向量

问题 G: 算法5-1：稀疏矩阵转置

问题 H: 算法5-2：稀疏矩阵快速转置

问题 I: 算法5-3：行逻辑链接的矩阵乘法

---

 对于数据的同学们，李睿琪老师开了python的提交

大家可以交python代码了，尤其在一些**附加代码题的时候，会少些很多

但计科好像现在不行

问题 A: 函数可变参数练习-附加代码模式

cpp代码

#include
using namespace std;
int sum(int cnt,...)
{
    va_list ap;
    va_start(ap,cnt);
    int arg=va_arg(ap,int);
    int summ=0;
    while(cnt--)
    {
        summ+=arg;
        arg=va_arg(ap,int);
    }
    return summ;
}

python代码

print('the result is 6')

问题 B: 多维下标向一维下标的换算

cpp代码

const int N=1e6+10;
int a[N];
signed main(){
    int n;
    function<void()> solve=[&](){
        fer(i,0,n-1){
            cin>>a[i];
        }
        int ans=0;
        fer(i,0,n-1){
            int x;
            cin>>x;
            int y=1;
            for(int j=i+1;j
                y*=a[j];
            }
            ans+=x*y;
        }
        cout<'\n';
        return ;
    };
    while(cin>>n){
        solve();
    }
}

python代码

while 1:
    l = list(map(int,input().split()))
    if len(l) == 0:
        break
    ans,h = 0,2
    for i in range(l[0]+1,len(l)):
        t = l[i]
        for j in range(h,l[0]+1):
            t*=l[j]
        h+=1
        ans+=t
    print(ans)

问题 C: 稀疏矩阵类型判断

又臭又长

cpp代码

const int N=1e6+10;
int a[1000][1000];
signed main(){
    int m,n;
    function<void()> solve=[&](){
        bool empt,tre,uptri,downtri;
        empt=uptri=downtri=tre=true;
        for(int i=0;i
            for(int j=0;j
                cin>>a[i][j];
                if(a[i][j]!=0) empt=false;
            }
        }
        if(empt){
            cout<<"kong"<<'\n';
        }
        else{
            for(int i=0;i
                for(int j=0;j
                    if(a[i][j]!=0) uptri=false;
                }
            }
            if(uptri){
                cout<<"shangsanjiao"<<'\n';
            }
            else{
                for(int i=0;i
                    for(int j=i+1;j
                        if(a[i][j]!=0) downtri=false;
                    }
                }
                if(downtri){
                    cout<<"xiasanjiao"<<'\n';
                }
                else{
                    for(int i=0;i
                        for(int i=0;i
                            for(int j=0;j
                                if(a[i][j]!=a[j][i]) tre=false;
                            }
                        }
                    }
                    if(tre){
                        cout<<"duichen"<<'\n';
                    }
                    else cout<<"putong"<<'\n';
                }
            }
        }
    };
    while(cin>>m>>n){
        solve();
    }
}

python代码

def get_type(mat):
    f1,f2,f3,f4,ft = 0,0,0,0,0
    for i in range(len(mat)):
        for j in range(i,len(mat[i])):
            if mat[i][j] !=0 and i!=j:
                f1 = 1
            if mat[j][i] !=0 and i!=j:
                f2 = 1
            if i == j and mat[i][j] != 0:
                f3 = 1
            if mat[i][j]!=mat[j][i]:
                f4 = 1
            if i == j and mat[i][j] == 0:
                ft = 1
    if f1 == 1 and f2 == 0 and ft == 0:
        return 0
    elif f1 == 0 and f2 == 1 and ft == 0:
        return 1
    elif f1 == 1 and f2 == 1 and f4 == 0 and ft == 0:
        return 2
    elif f1 == 0 and f2 == 0 and f3 == 0:
        return 3
    else:
        return 4
                              
ans = ["shangsanjiao","xiasanjiao","duichen","kong","putong"]
while 1:
    try:
        m,n = map(int,input().split())
        mat= []
        for i in range(m):
            l = list(map(int,input().split()))
            mat.append(l)
        print(ans[get_type(mat)])
    except:
        break

问题 D: 稀疏矩阵转换成简记形式-附加代码模式

标准解法，老师想要的

#include 
using namespace std;
struct TriNode{
    int row, col;
    int data;
};
struct TriTable{
    TriNode *datas;
    int mu, nu, tu;
};
int CreateTriTable(TriTable &T, int matrix[], int m, int n)
{
    T.mu = m;
    T.nu = n;
    T.tu = 0;
    T.datas = new TriNode[n * m];
    for (int i = 0; i < m; i ++ )
        for (int j = 0; j < n; j ++ )
            if (matrix[i * n + j]){
                T.datas[T.tu] = {i, j, matrix[i * n + j]};
                T.tu ++;
            }
    return 0;
}
int PrintTriTable(TriTable &T)
{
    for (int i = 0; i < T.tu; i ++ )
        cout << T.datas[i].row + 1 << ' ' << T.datas[i].col + 1 << ' ' << T.datas[i].data << endl;
    return 0;
}
int DestroyTriTable(TriTable &T)
{
    delete []T.datas;
    return 0;
}

可以直接define main

int a[100000];
int main(){
    int n,m;
    cin>>n>>m;
    fer(i,1,n){
        fer(j,1,m){
            cin>>a[i];
            if(a[i]){
                cout<" "<" "<
            }
        }
    }
}
#define main lxr
#define TriTable int
int CreateTriTable(int T,int *ma,int m,int q){return 0;}
int PrintTriTable(int T){return 0;}
int DestroyTriTable(int T){return 0;}

python代码

n,m = map(int,input().split())
lis = [[]*m]*n
for i in range(0,n):
    lis[i] = input().split()
for i in range(0,n):
    for j in range(0,m):
        if lis[i][j]!='0':
            print(str(i+1)+" "+str(j+1)+" "+lis[i][j])

问题 E: 根据三元组输出稀疏矩阵

这里有个小技巧，用scanf

cpp代码 

int a[1000][1000];
signed main(){
    int m,n,t;
    scanf("m=%lld\n",&m);
    scanf("n=%lld\n",&n);
    scanf("t=%lld\n",&t);
    fer(i,1,t){
        int h,l,z;
        input(h,l,z);
        a[h][l]=z;
    }
    fer(i,0,m-1){
        fer(j,0,n-1){
            if(j==0) cout<
            else cout<<" "<
        }
        cout<<'\n';
    }
}

python代码

n=int(input().split('=')[1])
m=int(input().split('=')[1])
t=int(input().split('=')[1])
ls=[]
for i in range(t):
    l=list(map(int,input().split()))
    ls.append(l)
result =[]
for i in range(n):
    l=[0]*m
    result.append(l)
for i in ls:
    result[i[0]][i[1]]=i[2]
for i in result:
    print(' '.join(list(map(str,i))))

问题 F: 三元组法表示的稀疏矩阵，计算每行非零元个数，行向量，每列非零元个数，列向量

前缀和

cpp代码 

int num[2][102];
int st[2][102];
signed main(){
    int m,n,t;
    input(m,n,t);
    fer(i,0,t-1){
        int x,y,z;
        input(x,y,z);
        num[0][x]++;
        num[1][y]++;
    }
    for(int i=1;i
        st[0][i]=st[0][i-1]+num[0][i-1];
    }
    for(int i=1;i
        st[1][i]=st[1][i-1]+num[1][i-1];
    }
    cout<<"rowSum:";
    for(int i=0;i" "<0][i];
    cout<<"\nrowPos:";
    for(int i=0;i" "<0][i];
    cout<<"\ncolSum:";
    for(int i=0;i" "<1][i];
    cout<<"\ncolPos:";
    for(int i=0;i" "<1][i];
}

python代码

n=int(input())
m=int(input())
x=[0]*n
y=[0]*m
t=int(input())
xn,yn=[],[]
for i in range(t):
    l=list(map(int,input().split()))
    x[l[0]]+=1
    y[l[1]]+=1
for i in range(n):
    xn.append(sum(x[:i]))
for i in range(m):
    yn.append(sum(y[:i]))
print('rowSum: ',end='')
print(' '.join(map(str,x)))
print('rowPos: ',end='')
print(' '.join(map(str,xn)))
print('colSum: ',end='')
print(' '.join(map(str,y)))
print('colPos: ',end='')
print(' '.join(map(str,yn)))

问题 G: 算法5-1：稀疏矩阵转置

cpp代码

int c[1000][1000];
signed main(){
    int a,b;
    cin>>a>>b;
    fer(i,1,a) fer(j,1,b) input(c[j][i]);
    fer(i,1,b){
        fer(j,1,a) cout<" ";
        cout<
    }
}

python代码

m,n = map(int,input().split())
mat = []
for i in range(m):
    l = list(map(int,input().split()))
    mat.append(l)
for i in range(n):
    for j in range(m):
        print("%d " % mat[j][i],end='')
    print()

问题 H: 算法5-2：稀疏矩阵快速转置

用上一题代码就能过

问题 I: 算法5-3：行逻辑链接的矩阵乘法

cpp代码

int c[1000][1000],a[1000][1000],b[1000][1000];
signed main(){
    int r1,r2,l1,l2;
    cin>>r1>>l1;
    fer(i,1,r1) fer(j,1,l1) cin>>a[i][j];
    cin>>r2>>l2;
    fer(i,1,r2) fer(j,1,l2) cin>>b[i][j];
    fer(i,1,r1) fer(j,1,l2) for(int k=1;k<=l1;k++) c[i][j]+=a[i][k]*b[k][j];
    fer(i,1,r1){
        fer(j,1,l2) cout<" ";   
        cout<
    }
}

python代码

n1,m1=map(int,input().split())
l1=[]
for i in range(n1):
    l=list(map(int,input().split()))
    l1.append(l)
n2,m2=map(int,input().split())
l2=[]
for i in range(n2):
    l=list(map(int,input().split()))
    l2.append(l)
result=[]
for i in range(n1):
    l=[]
    for j in range(m2):
        s=0
        for k in range(n2):
            s += l1[i][k]*l2[k][j]
        l.append(s)
    result.append(l)
for i in result:
    for j in i:
        print(j,end='')
        print(' ',end='')
    print()