精华内容
下载资源
问答
  • 稀疏矩阵的运算
    2021-04-23 07:46:21

    是否有可能通过例如加速大型稀疏矩阵计算.最佳地放置parantheses?

    我要问的是:我可以通过强制Matlab以指定顺序(例如“从右到左”或类似的东西)执行操作来加速以下代码吗?

    我有一个稀疏的方形对称矩阵H,它先前已被分解,并且稀疏向量M的长度等于H的维数.我想要做的是以下内容:

    编辑:一些额外的信息:H通常是4000×4000. z和c的计算大约进行了4000次,而dVa和dVaComp的计算每4000次循环进行10次,总计40000次. (迭代地解决dVa和dVaComp,其中更新P_mis).

    这里M * c * M’将成为具有4个非零元素的稀疏矩阵.在Matlab中:

    [L U P] = lu(H); % H is sparse (thus also L, U and P)

    % for i = 1:4000 % Just to illustrate

    M = sparse([bf bt],1,[1 -1],n,1); % Sparse vector with two non-zero elements in bt and bf

    z = -M'*(U \ (L \ (P * M))); % M^t*H^-1*M = a scalar

    c = (1/dyp + z)^-1; % dyp is a scalar

    % while (iterations < 10 && ~=converged)

    dVa = - (U \ (L \ (P * P_mis)));

    dVaComp = (U \ (L \ (P * M * c * M' * dVa)));

    % Update P_mis etc.

    % end while

    % end for

    并且为了记录:尽管我多次使用H的倒数,但预先计算它并不快.

    谢谢=)

    最佳答案 有一些事情对我来说并不完全清楚:

    >命令M =稀疏([t f],[1 -1],1,n,1);不可能是对的;你说在行t,f和列1,-1上应该有1;第-1列显然不能正确.

    >结果dVaComp是一个完整的矩阵,因为它与P_mis相乘,而你说它应该是稀疏的.

    暂时搁置这些问题,我看到了一些小的优化:

    >您使用inv(H)* M两次,因此您可以预先计算它.

    >否定dVa可以移出循环.

    >如果您不明确需要dVa,也可以将赋值分配给变量.

    >标量的反转意味着将1除以该标量(c的计算).

    实现更改,并尝试公平比较(我只使用了40次迭代来保持总时间很小):

    %% initialize

    clc

    N = 4000;

    % H is sparse, square, symmetric

    H = tril(rand(N));

    H(H<0.5) = 0; % roughly half is empty

    H = sparse(H+H.');

    % M is sparse vector with two non-zero elements.

    M = sparse([1 N],[1 1],1, N,1);

    % dyp is some scalar

    dyp = rand;

    % P_mis = full vector

    P_mis = rand(N,1);

    %% original method

    [L, U, P] = lu(H);

    tic

    for ii = 1:40

    z = -M'*(U \ (L \ (P*M)));

    c = (1/dyp + z)^-1;

    for jj = 1:10

    dVa = -(U \ (L \ (P*P_mis)));

    dVaComp = (U \ (L \ (P*M * c * M' * dVa)));

    end

    end

    toc

    %% new method I

    [L,U,P,Q] = lu(H);

    tic

    for ii = 1:40

    invH_M = U\(L\(P*M));

    z = -M.'*invH_M;

    c = -1/(1/dyp + z);

    for jj = 1:10

    dVaComp = c * (invH_M*M.') * ( U\(L\(P*P_mis)) );

    end

    end

    toc

    这给出了以下结果:

    Elapsed time is 60.384734 seconds. % your original method

    Elapsed time is 33.074448 seconds. % new method

    更多相关内容
  • 内蒙古科技大学 数据结构课程设计说明书 题 目稀疏矩阵运算器设计 学生姓名 学 号 专 业计算机科学与技术 班 级计 09-1 班 指导教师刘 月 峰 2011 年 6 月 24 日 稀疏矩阵运算器设计 摘 要 摘要设计一稀疏矩阵运算器...
  • 稀疏矩阵运算

    2015-04-14 13:00:18
    三元组法实现稀疏矩阵的加,减,乘,求逆运算
  • 10稀疏矩阵运算器.doc

    2021-12-05 22:14:55
    10稀疏矩阵运算器.doc
  • Python解决稀疏矩阵运算

    千次阅读 2020-12-27 23:38:38
    题目:稀疏线性方程组的求解方法 简单的方程如: AX=b 其中 python有很多功能库,这些库对于编程很有帮助,可以在pycharm的Project Interpreter导入库,例如numpy、os、scipy等比较基础的库,下面是用来求解的...

    用Python求解微分线性方程

    因为之前用matlab也编写过,所以前不久试着用python写,感觉之间互通点也蛮多的,易理解。

    题目:稀疏线性方程组的求解方法

    简单的方程如: AX=b
    其中A矩阵与b向量

    python有很多功能库,这些库对于编程很有帮助,可以在pycharm的Project Interpreter导入库,例如numpy、os、scipy等比较基础的库,下面是用来求解的代码:

    import numpy as np
    from scipy import linalg
    import os
    #输入矩阵维数
    print("你好,这里是计算稀疏矩阵线性方程组的地方,非诚勿扰!")
    dism_num = input("你的A矩阵维数是:")
    dism_num = int(dism_num)
    print("接下来请你依次输入矩阵的行向量(注意只能输入英文逗号,):")
    A =[]
    #X =[]
    for i in range(1,dism_num+1):
        a=input("第"+str(i)+"行向量是:")
        alist = a.split(",")
        alist = [int(alist[j]) for j in range(len(alist))]
        A.append(alist)
    print("你所输入的矩阵行向量是:")
    print(A)
    #记录输入的X矩阵
    
    #输入向量b
    print("输入b向量")
    b = input("b向量是:")
    b_list = b.split(",")
    b_list = [int(b_list[j]) for j in range(len(b_list))]
    print("你输入的b向量是:")
    print(b_list)
    #记录b向量
    
    #询问是否计算单个答案(单元素)
    ask = input("是否只需求解单个值:(是或否)")
    while(True):
        if ask == '是':
            ask_a = 'T'
            ask_num = input("请继续输入你所需要的答案序号:")
            ask_num = int(ask_num)
            if ask_num<=dism_num and ask_num>0:
                print("OK,马上帮你计算")
                break
            else:
                print("输入的值超出矩阵维数,请重新输入:")
        if ask == '否':
            ask_a = 'F'
            break
    #询问完成,只有当用户输入正确的序号才可以进行计算,否则重新询问
    
    #开始计算x向量了
    A = np.array(A)
    b = np.array(b_list)
    x = linalg.solve(A,b)
    print("计算的结果的:")
    if ask_a == 'F':
        print(x)
    if ask_a =='T':
        print(x[ask_num-1])
    #计算完x向量了
    
    os.system("pause")
    #用于py文件结束玩暂停显示结果
    

    其基本流程如图:代码开发流程
    运行结果如下:
    代码运行结果
    希望对你有所帮助!

    展开全文
  • 内蒙古科技大学 数据结构课程设计说明书 题 目稀疏矩阵运算器设计 学生姓名 学 号 专 业计算机科学与技术 班 级计 09-1 班 指导教师刘 月 峰 2011 年 6 月 24 日 稀疏矩阵运算器设计 摘 要 摘要设计一稀疏矩阵运算器...
  • 问题描述: 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算 可以大大节省...我写的这个稀疏矩阵运算器代码非常完整,功能也都能正确实现,绝对不会让你们失望的,有需要的朋友们赶紧下载吧!
  • #资源达人分享计划#
  • 采用三元组表示稀疏矩阵,并实现基本运算的实验报告。
  • 稀疏矩阵乘积 描述 给定两个N × N的稀疏矩阵A和B,其中矩阵A有P个元素非0,矩阵B有Q个元素非0。请计算两个矩阵的乘积C = A × B并且输出C中所有非0的元素。 输入 第一行包含三个整数N, P, Q 以下P行每行三个整数i, ...
  • 清华大学版《数据结构》第三次试验代码,原创
  • 数据结构:稀疏矩阵运算

    千次阅读 2021-05-21 06:11:13
    题目:设计一个程序,实现一个能进行稀疏矩阵基本运算的计算器。按照教科书《数据结构(C语言版)》(严蔚敏等)5.3.2节中描述的方法,以十字链表表示稀疏矩阵。一、需求分析稀疏矩阵是指那些多数元素为零的矩阵。利用...

    题目:设计一个程序,实现一个能进行稀疏矩阵基本运算的计算器。按照教科书《数据结构(C语言版)》(严蔚敏等)5.3.2节中描述的方法,以十字链表表示稀疏矩阵。

    一、需求分析

    稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进修学校储存和计算可以大大节省储存空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的计算器。

    以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。

    测试数据

    \left[ \begin{matrix} 10&0& 0 \\ 0&0&9 \\ -1&0&0 \\ \end{matrix}\right] + \left[ \begin{matrix} 0&0& 0 \\ 0&0&-1 \\ 1&0&-3 \\ \end{matrix}\right]= \left[ \begin{matrix} 10&0& 0 \\ 0&0&8 \\ 0&0&-3 \\ \end{matrix}\right]

    \left[ \begin{matrix} 10&9 \\ 0&9 \\ -1&0 \\ \end{matrix}\right] - \left[ \begin{matrix} 0&0 \\ 0&-1 \\ 1&-3 \\ \end{matrix}\right]= \left[ \begin{matrix} 10&0 \\ 0&10 \\ -2&-3 \\ \end{matrix}\right]

    \left[ \begin{matrix} 4&-3&0&0&1 \\ 0&0&0&8&0 \\ 0&0&1&0&0 \\ 0&0&0&0&0 \end{matrix}\right] \times \left[ \begin{matrix} 3&0&0 \\ 4&2&0 \\ 0&1&0 \\ 1&0&0 \\ 0&0&0 \end{matrix}\right] = \left[ \begin{matrix} 0&-6&0 \\ 8&0&0 \\ 0&1&0 \\ 0&0&0 \end{matrix}\right]

    二、概要设计

    1.数据结构

    ADT SparseMatrix{

    数据对象:D={ aij | i = 1,2,...,m; j = 1,2,...,n;

    aij∈ElemSet, m和n分别为矩阵的行数和列数}

    数据关系:R={Row,Col}

    Row={|1≤i≤m,1≤j≤n-1 }

    Col={|1≤i≤m-1,1≤j≤n }

    基本操作:

    CreateSMatrix(&M)

    操作结果:创建稀疏矩阵M。

    PrintSMatrix(M)

    初始条件:稀疏矩阵M存在。

    操作结果: 输出稀疏矩阵M。

    AddSMatrix(M, N, &Q)

    初始条件:稀疏矩阵M与N的行数和列数对应相等。

    操作结果:求稀疏矩阵的和Q=M+N。

    SubtSMatrix(M, N, &Q)

    初始条件:稀疏矩阵M与N的行数和列数对应相等。

    操作结果:求稀疏矩阵的差Q=M-N。

    MultSMatrix(M, N, &Q)

    初始条件:稀疏矩阵M的列数等于N的行数。

    操作结果:求稀疏矩阵乘积Q=M*N。

    }ADT SparseMatrix

    2. 使用函数

    (1)行逻辑链接的顺序表

    int CreateSMatrix(RLSMatrix *M)

    操作结果:创建稀疏矩阵

    int PrintSMatrix(RLSMatrix M)

    操作结果:打印稀疏矩阵

    int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

    操作结果:稀疏矩阵加法,Q=M+N

    int SubSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

    操作结果:稀疏矩阵减法,Q=M-N

    int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

    操作结果:稀疏矩阵乘法,Q=M*N

    (2)十字链表

    int CreateSMatrix_OL(CrossList *M)

    操作结果:创建稀疏矩阵

    int PrintSMatrix_OL(CrossList M)

    操作结果:打印稀疏矩阵

    int AddSMatrix_OL(CrossList *A, CrossList *B)

    操作结果:将稀疏矩阵B加到稀疏矩阵A上

    int SubSMatrix_OL(CrossList *A, CrossList *B)

    操作结果:在稀疏矩阵A上减去稀疏矩阵B

    int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C)

    操作结果:稀疏矩阵乘法,C=A*B

    三、详细设计

    1. 数据储存结构

    (1)行逻辑链接顺序表

    #define MAXSIZE 400 // 最大非零元个数

    #define MAXRC 20 // 最大行数和列数

    typedef struct{

    int i,j; // 该非零元的行下标和列下标

    int e;

    }Triple;

    typedef struct{

    Triple data[MAXSIZE+1]; // 非零元三元组表

    int rpos[MAXRC+1]; // 各行第一个非零元位置表

    int mu,nu,tu; // 矩阵行数、列数和非零元个数

    }RLSMatrix;

    (2)十字链表

    #define MAXSIZE 400 // 最大非零元个数

    #define MAXRC 20 // 最大行数和列数

    typedef struct OLNode{

    int i,j; // 该非零元的行和列下标

    int e;

    struct OLNode *right, *down; // 该非零元所在行表和列表的后继链域

    }OLNode, *OLink;

    typedef struct {

    OLink *rhead, *chead; // 行和列链表头指针向量基址由CreateSMatrix分配

    int mu, nu, tu; // 稀疏矩阵行数、列数和非零元个数

    }CrossList;

    2.基本功能实现

    2.1行逻辑链接顺序表

    (1)稀疏矩阵创建

    分别读入矩阵行数、列数以及非零元个数,同时提示输入各个非零元位置和数值,对于输入的非零元判断是否合法,并根据行号和列号进行以行为主序的储存,最后计算各行首个非零元位置。

    int CreateSMatrix(RLSMatrix *M){

    if(M) free(M);

    int m,n,t;

    do{

    printf("输入矩阵行数,列数和非零元数目,用空格隔开\n");

    scanf("%d %d %d", &m, &n, &t);

    if(m < 0 || n < 0 || t < 0 || t > m*n){

    printf("参数错误 \n");

    }

    }while(m < 0 || n < 0 || t < 0 || t > m*n);

    M->mu = m; M->nu = n; M->tu = t;

    printf("请按行优先输入三元组\n");

    int i,j,e,k;

    int p,q;

    for(k = 1; k <= t; k++){

    do{

    printf("输入第%d个非零元的行号 列号 值, 用空格隔开\n",k);

    scanf("%d %d %d", &i, &j, &e);

    if(i <= 0 || j <= 0 || i > m || j > n|| e==0){

    printf("参数错误\n");

    }

    }while(i <= 0 || j <= 0 || i > m || j > n|| e==0);

    for(p = 1; p <= k-1 && (i > M->data[p].i || (i == M->data[p].i && j > M->data[p].j)); p++); //找到三元组插入的位置

    for(q = k-1;q >= p; q--) M->data[q+1] = M->data[q]; //行序大的三元组依次向后移动

    M->data[p].i = i;

    M->data[p].j = j;

    M->data[p].e = e;

    }

    int row,x;

    int num[MAXRC + 1];

    for(row = 1; row <= M->mu; ++row) num[row] = 0;

    for(x = 1; x <= M->tu; ++x) ++num[M->data[x].i]; // 每一行非零元个数

    M->rpos[1] = 1;

    for(row = 2; row<=M->mu; ++row) M->rpos[row] = M->rpos[row-1] + num[row-1]; // 各行首个非零元位置

    return 1;

    }

    (2)稀疏矩阵加减法

    加减法基本思路一致,这里以加法为例。找到M和N矩阵各行非零元素的起始和终末位置之后开始遍历,对列号相等和不等两种情况分别处理,并处理相加结果等于0的情况。

    int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

    int arow;

    int p,q,s = 1;

    int tp,tq;

    if(M.mu != N.mu || M.nu != N.nu) return 0;

    Q->mu = M.mu; Q->nu = M.nu;

    for(arow = 1; arow <= M.mu; ++arow){

    Q->rpos[arow] = Q->tu + 1;

    p = M.rpos[arow]; q = N.rpos[arow];

    if(arow < M.mu){

    tp = M.rpos[arow + 1];

    tq = N.rpos[arow + 1];

    }

    else{

    tp = M.tu + 1;

    tq = N.tu + 1;

    }

    while(p < tp && q < tq){

    if(M.data[p].j != N.data[q].j){ // 列号不等

    if(M.data[p].j < N.data[q].j){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    s++; p++; Q->tu++;

    }else{

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = N.data[q].e;

    s++; q++; Q->tu++;

    }

    }else{ // 列号相等

    if(M.data[p].e + N.data[q].e != 0){ // 结果非零

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e + N.data[q].e;

    s++; q++; p++; Q->tu++;

    }else{q++; p++;}

    }

    }

    while(p < tp){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    p++; s++; Q->tu++;

    }

    while(q < tq){

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = N.data[q].e;

    q++; s++; Q->tu++;

    }

    }

    return 1;

    }

    (3)稀疏矩阵乘法

    对于M中每个元素M.data[p]找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q],求得M.data[p].e * N.data[q].e,对Q中元素设计累计和变量,初值为零,扫描数组M,求得相应元素乘积累加到适当的求累计和变量上。Q中元素行号与M中元素行号一致,又M中元素以M的行序为主序,因此对Q进行逐行处理,先求得累计和的中间结果(Q的一行),再压缩储存到Q.data中去。

    int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

    // 求矩阵乘积Q=M×N,采用行逻辑链接储存表示

    int arow,brow;

    int p,q,t,tp;

    int ccol;

    int ctemp[MAXRC + 1];

    if(M.nu != N.mu) return 0;

    Q->mu = M.mu; Q->nu = N.nu; Q->tu = 0; // Q初始化

    if(M.tu * N.tu != 0){ // Q是非零矩阵

    for(arow = 1; arow <= M.mu; ++arow){ // 处理M的每一行

    for(int i = 1; i <= N.nu; i++) ctemp[i] = 0; // 当前行各元素累加器清零

    Q->rpos[arow] = Q->tu + 1;

    if(arow < M.mu) tp = M.rpos[arow + 1];

    else{tp = M.tu + 1;}

    for(p = M.rpos[arow]; p

    brow = M.data[p].j; // 找到对应元所在N中的行号

    if(brow < N.mu) t = N.rpos[brow + 1];

    else{t = N.tu + 1;}

    for(q = N.rpos[brow]; q

    ccol = N.data[q].j; // 乘积元素在Q中的列号

    ctemp[ccol] += M.data[p].e * N.data[q].e;

    }// for q

    }// 求得Q中第crow(=arow)行的非零元

    for(ccol = 1; ccol <= Q->nu; ++ccol){ //压缩储存改行非零元

    if(ctemp[ccol]){

    if(++Q->tu > MAXSIZE) return 0;

    Q->data[Q->tu].i = arow;

    Q->data[Q->tu].j = ccol;

    Q->data[Q->tu].e = ctemp[ccol];

    }// if

    } // for ccol

    }// for arow

    }// if

    return 1;

    }// MultSMatrix

    (4)稀疏矩阵输出

    通过双重循环,打印稀疏矩阵中非零元和零元素

    int PrintSMatrix(RLSMatrix M){

    int row,col,t = 1;

    for(row = 1; row <= M.mu; row++){

    for(col = 1; col <= M.nu; col++){

    if(M.data[t].i == row && M.data[t].j == col){

    printf("%d\t",M.data[t].e);

    t++;

    }else{

    printf("0\t");

    }

    }

    printf("\n");

    }

    return 1;

    }

    2.2十字链表

    (1)稀疏矩阵创建

    读入矩阵行数、列数和非零元个数,同时提示输入各个非零元位置和数值,对于输入的非零元判断是否合法,生成结点并完成在行链表和列链表中的插入。

    int CreateSMatrix_OL(CrossList *M){

    if(M) free(M);

    int c;

    int m,n,t;

    int i,j,k,e;

    OLink p,q;

    do{

    printf("输入矩阵行数,列数和非零元数目,用空格隔开\n");

    scanf("%d %d %d", &m, &n, &t);

    if(m < 0 || n < 0 || t < 0 || t > m*n){

    printf("参数错误 \n");

    }

    }while(m < 0 || n < 0 || t < 0 || t > m*n);

    M->mu = m; M->nu = n; M->tu = t;

    if(!(M->rhead = (OLink*)malloc((m+1)*sizeof(OLink)))) exit(-2);

    if(!(M->chead = (OLink*)malloc((n+1)*sizeof(OLink)))) exit(-2);

    for(c = 1; c <= M->mu; c++) M->rhead[c]=NULL; // 初始化行列头指针向量

    for(c = 1; c <= M->nu; c++) M->chead[c]=NULL;

    for(k = 1; k <= t; k++){ // 按任意顺序输入非零元

    do{

    printf("输入第%d个非零元的行号 列号 值, 用空格隔开\n",k);

    scanf("%d %d %d", &i, &j, &e);

    if(i <= 0 || j <= 0 || i > m || j > n|| e==0){

    printf("参数错误\n");

    }

    }while(i <= 0 || j <= 0 || i > m || j > n|| e==0);

    if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p->i = i; p->j = j; p ->e = e; // 生成结点

    if(M->rhead[i] == NULL || M->rhead[i]->j > j){

    p->right = M->rhead[i];

    M->rhead[i] = p;

    }else{ // 寻找行表中的插入位置

    for(q = M->rhead[i]; (q->right) && (q->right->j < j); q = q->right);

    p->right = q->right;

    q->right = p;

    } // 完成行插入

    if(M->chead[j] == NULL || M->chead[j]->i > i){ // 寻找列表中的插入位置

    p->down = M->chead[j];

    M->chead[j] = p;

    }else{

    for(q = M->chead[j]; (q->down) && (q->down->i < i); q = q->down);

    p->down = q->down;

    q->down = p;

    } // 完成列插入

    }

    return 1;

    }

    (2)稀疏矩阵加减法

    加减法基本思路一致,这里以加法为例。

    非空指针pa和pb分别指向矩阵A,B中行值相同的两个结点,pa==NULL表明矩阵A在改行没有非零元,分为以下四种情况:

    若pa==NULL或pa->j>pb->i,则需要在A矩阵的链表中插入一个值为bij的结点,此时,需要改变同一行中前一结点的right域值,以及同一列中前一结点的down域值。

    若pa->jj,则将pa指针向右推进一步

    若pa->j==pb->j,且pa->e+pb->e!=0,则只要将aij+bij的值送到pa所指结点的e域即可,其他所有域的值都不变

    若pa->j==pb->j,且pa->e+pb->e==0,则需要在A矩阵链表中删除pa所指结点,此时需要改变同一行中前一结点的right域值以及同一列前一结点的down阈值。

    为了便于插入和删除节点,还需要设置一些辅助指针。其一是在A的行链表上设pre指针,指示pa所指结点的前驱结点;其二是在A的每一列的链表上设一个指针hl[j],其初值和列链表的头指针相同,即hl[j]=chead[j]

    int AddSMatrix_OL(CrossList *A, CrossList *B){

    OLink pa, pb, pre, p, hl[MAXRC + 1];

    int i, j;

    if(A->mu != B->mu || A->nu != B->nu) return 0;

    for(j = 1; j <= A->nu; j++) hl[j] = A->chead[j];

    for(i = 1; i <= A->mu; i++){

    pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL;

    while(pb){

    if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p->i = pb->i; p->j = pb->j; p->e = pb->e;

    if(pa == NULL || pa->j > pb->j){ // 在A中插入pb所指结点的复制结点p

    if(pre == NULL) A->rhead[p->i] = p;

    else{pre->right = p; }

    p->right = pa;

    pre = p;

    if(A->chead[p->j] == NULL || A->chead[p->j]->i > p->i){

    p->down = A->chead[p->j];

    A->chead[p->j] = p;

    }else{ // 在hl[p->j]中找到新结点的前驱,插入结点

    p->down = hl[p->j]->down;

    hl[p->j]->down = p;

    }

    hl[p->j] = p;

    pb = pb->right;

    A->tu++;

    }else if(pa && pa->j < pb->j){ // pa指向本行下一个非零结点

    pre = pa;

    pa = pa->right;

    }else if(pa->j == pb->j){ // 加和

    pa->e += pb->e;

    if(pa->e == 0){ // 加和为0,删除结点,修改行表和列表相应指针

    if(pre == NULL) A->rhead[pa->i] = pa->right;

    else{pre->right = pa->right; }

    p = pa; pa = pa->right;

    if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down;

    else{hl[p->j]->down = p->down; }

    free(p);

    pb = pb->right;

    A->tu--;

    }else{pre = pa; pa = pa->right; pb = pb->right; }

    }

    }

    }

    return 1;

    }

    (3)稀疏矩阵乘法

    对于C中i行j列的元素,分别使p指向A中i行链表头指针,q指向B中j列链表头指针,累加和e置为零。p,q不为空时,

    当p->j > q->i,q指针下移

    当p->j < q->i,p指针右移

    当p->j == q->i,对乘积累计求和,并移动指针

    累加器e不为0时,则在矩阵C行列链表中插入节点p1,设置cpre和rpre分别指示行列链表中p1的前驱结点。

    int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C){

    int i, j, e;

    OLink p, q, p1, rpre, cpre;

    if(A.nu != B.mu) return 0;

    C->mu = A.mu; C->nu = B.nu; C->tu = 0; // 初始化矩阵C

    if(!(C->rhead = (OLink*)malloc((C->mu+1)*sizeof(OLink)))) exit(-2);

    if(!(C->chead = (OLink*)malloc((C->nu+1)*sizeof(OLink)))) exit(-2);

    for(i = 1; i <= C->mu; i++) C->rhead[i] = NULL;

    for(j = 1; j <= C->nu; j++) C->chead[j] = NULL;

    for(i = 1; i <= C->mu; i++){

    for(j = 1; j <= C->nu; j++){

    p = A.rhead[i]; q = B.chead[j]; e = 0; // p,q分别指向A中该行链表头指针,B中该列链表头指针

    while(p && q){

    if(p->j > q->i){

    q = q->down;

    }else if(p->j < q->i){

    p = p->right;

    }else{

    e += p->e * q->e; // 乘积累加

    q = q->down;

    p = p->right;

    }

    }

    if(e){ // 累加不为0

    C->tu++;

    if(!(p1 = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p1->i = i; p1->j = j; p1->e = e;

    p1->right = NULL; p1->down = NULL;

    // 行插入

    if(C->rhead[i] == NULL) {C->rhead[i] = p1; rpre = p1;}

    else{rpre->right = p1; rpre = p1; }

    // 列插入

    if(C->chead[j] == NULL) {C->chead[j] = p1; cpre = p1;}

    else{cpre->down = p1; cpre = p1; }

    }

    }

    }

    return 1;

    }

    (4)稀疏矩阵输出

    通过双重循环,打印稀疏矩阵中非零元和零元素

    int PrintSMatrix_OL(CrossList M){

    OLink p;

    int row,col;

    for(row = 1; row <= M.mu; row++){

    if(M.rhead[row]){

    p = M.rhead[row];

    for(col = 1; col <= M.nu; col++){

    if(p->i == row && p->j == col && p != NULL){

    printf("%d\t",p->e);

    if(p->right) p = p->right;

    }else{printf("0\t");}

    }

    }else{for(col = 1; col <= M.nu; col++) printf("0\t");}

    printf("\n");

    }

    return 1;

    }

    4.主程序

    通过读入操作序号来进行相应操作,在满足操作对应条件下进行相应操作,并打印结果,两种储存方式下主程序结构基本一致,只是运算时调用函数不同。

    int main(){

    int num;

    CrossList M, N, Q;

    do{

    printf("操作:1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出\n");

    scanf("%d",&num);

    if(num == 1 || num == 2 || num == 3){

    printf("请输入矩阵1\n");

    CreateSMatrix_OL(&M);

    printf("请输入矩阵2\n");

    CreateSMatrix_OL(&N);

    printf("两矩阵为:\n");

    PrintSMatrix_OL(M);

    printf("\n");

    PrintSMatrix_OL(N);

    switch(num){

    case 1:

    {

    if(AddSMatrix_OL(&M, &N)){

    printf("结果:\n");

    PrintSMatrix_OL(M);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 2:

    {

    if(SubSMatrix_OL(&M, &N)){

    printf("结果:\n");

    PrintSMatrix_OL(M);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 3:

    {

    if(MultSMatrix_OL(M,N,&Q)){

    printf("结果:\n");

    PrintSMatrix_OL(Q);

    }

    else {printf("参数错误\n");}

    break;

    }

    default: break;

    }

    }

    }while(num == 1 || num == 2 || num == 3);

    return 1;

    }

    5.程序的层次结构

    b04c32d1c27b?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    层次结构

    四、用户手册

    本程序的运行环境为DOS操作系统,执行文件为:sparsematrix.exe和crossmatrix.exe 分别对应行逻辑链接顺序表和十字链表实现的稀疏矩阵计算器

    进入程序按提示操作,输入要进行操作对应的序号

    根据操作提示输入两矩阵的行数、列数和非零元个数,并输入非零元的行号,列号以及值

    结果打印

    根据操作提示退出程序

    五、测试结果

    \left[ \begin{matrix} 10&0& 0 \\ 0&0&9 \\ -1&0&0 \\ \end{matrix}\right] + \left[ \begin{matrix} 0&0& 0 \\ 0&0&-1 \\ 1&0&-3 \\ \end{matrix}\right]= \left[ \begin{matrix} 10&0& 0 \\ 0&0&8 \\ 0&0&-3 \\ \end{matrix}\right]

    \left[ \begin{matrix} 10&9 \\ 0&9 \\ -1&0 \\ \end{matrix}\right] - \left[ \begin{matrix} 0&0 \\ 0&-1 \\ 1&-3 \\ \end{matrix}\right]= \left[ \begin{matrix} 10&0 \\ 0&10 \\ -2&-3 \\ \end{matrix}\right]

    \left[ \begin{matrix} 4&-3&0&0&1 \\ 0&0&0&8&0 \\ 0&0&1&0&0 \\ 0&0&0&0&0 \end{matrix}\right] \times \left[ \begin{matrix} 3&0&0 \\ 4&2&0 \\ 0&1&0 \\ 1&0&0 \\ 0&0&0 \end{matrix}\right] = \left[ \begin{matrix} 0&-6&0 \\ 8&0&0 \\ 0&1&0 \\ 0&0&0 \end{matrix}\right]

    b04c32d1c27b?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    测试结果1

    b04c32d1c27b?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    测试结果2

    b04c32d1c27b?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation

    测试结果3

    六、源代码

    sparsematrix.c

    #include

    #include

    #define MAXSIZE 400

    #define MAXRC 20

    typedef struct{

    int i,j;

    int e;

    }Triple;

    typedef struct{

    Triple data[MAXSIZE+1];

    int rpos[MAXRC+1];

    int mu,nu,tu; // 行,列,非零元个数

    }RLSMatrix;

    int CreateSMatrix(RLSMatrix *M){

    if(M) free(M);

    int m,n,t;

    do{

    printf("输入矩阵行数,列数和非零元数目,用空格隔开\n");

    scanf("%d %d %d", &m, &n, &t);

    if(m < 0 || n < 0 || t < 0 || t > m*n){

    printf("参数错误 \n");

    }

    }while(m < 0 || n < 0 || t < 0 || t > m*n);

    M->mu = m; M->nu = n; M->tu = t;

    printf("请按行优先输入三元组\n");

    int i,j,e,k;

    int p,q;

    for(k = 1; k <= t; k++){

    do{

    printf("输入第%d个非零元的行号 列号 值, 用空格隔开\n",k);

    scanf("%d %d %d", &i, &j, &e);

    if(i <= 0 || j <= 0 || i > m || j > n|| e==0){

    printf("参数错误\n");

    }

    }while(i <= 0 || j <= 0 || i > m || j > n|| e==0);

    for(p = 1; p <= k-1 && (i > M->data[p].i || (i == M->data[p].i && j > M->data[p].j)); p++); //找到此三元组插入的位置

    for(q = k-1;q >= p; q--) M->data[q+1] = M->data[q]; //行序比它大的三元组依次向后移动

    M->data[p].i = i;

    M->data[p].j = j;

    M->data[p].e = e;

    }

    int row,x;

    int num[MAXRC + 1];

    for(row = 1; row <= M->mu; ++row) num[row] = 0;

    for(x = 1; x <= M->tu; ++x) ++num[M->data[x].i];

    M->rpos[1] = 1;

    for(row = 2; row<=M->mu; ++row) M->rpos[row] = M->rpos[row-1] + num[row-1];

    return 1;

    }

    int PrintSMatrix(RLSMatrix M){

    int row,col,t = 1;

    for(row = 1; row <= M.mu; row++){

    for(col = 1; col <= M.nu; col++){

    if(M.data[t].i == row && M.data[t].j == col){

    printf("%d\t",M.data[t].e);

    t++;

    }else{

    printf("0\t");

    }

    }

    printf("\n");

    }

    return 1;

    }

    int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

    int arow;

    int p,q,s = 1;

    int tp,tq;

    if(M.mu != N.mu || M.nu != N.nu) return 0;

    Q->mu = M.mu; Q->nu = M.nu;

    for(arow = 1; arow <= M.mu; ++arow){

    Q->rpos[arow] = Q->tu + 1;

    p = M.rpos[arow]; q = N.rpos[arow];

    if(arow < M.mu){

    tp = M.rpos[arow + 1];

    tq = N.rpos[arow + 1];

    }

    else{

    tp = M.tu + 1;

    tq = N.tu + 1;

    }

    while(p < tp && q < tq){

    if(M.data[p].j != N.data[q].j){ // 列号不等

    if(M.data[p].j < N.data[q].j){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    s++; p++; Q->tu++;

    }else{

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = N.data[q].e;

    s++; q++; Q->tu++;

    }

    }else{ // 列号相等

    if(M.data[p].e + N.data[q].e != 0){ // 结果非零

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e + N.data[q].e;

    s++; q++; p++; Q->tu++;

    }else{q++; p++;}

    }

    }

    while(p < tp){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    p++; s++; Q->tu++;

    }

    while(q < tq){

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = N.data[q].e;

    q++; s++; Q->tu++;

    }

    }

    return 1;

    }

    int SubSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

    int arow;

    int p,q,s = 1;

    int tp,tq;

    if(M.mu != N.mu || M.nu != N.nu) return 0;

    Q->mu = M.mu; Q->nu = M.nu;

    for(arow = 1; arow <= M.mu; ++arow){

    Q->rpos[arow] = Q->tu + 1;

    p = M.rpos[arow]; q = N.rpos[arow];

    if(arow < M.mu){

    tp = M.rpos[arow + 1];

    tq = N.rpos[arow + 1];

    }

    else{

    tp = M.tu + 1;

    tq = N.tu + 1;

    }

    while(p < tp && q < tq){

    if(M.data[p].j != N.data[q].j){ // 列号不等

    if(M.data[p].j < N.data[q].j){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    s++; p++; Q->tu++;

    }else{

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = - N.data[q].e;

    s++; q++; Q->tu++;

    }

    }else{ // 列号相等

    if(M.data[p].e - N.data[q].e != 0){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e - N.data[q].e;

    s++; q++; p++; Q->tu++;

    }else{q++; p++;}

    }

    }

    while(p < tp){

    Q->data[s].i = arow;

    Q->data[s].j = M.data[p].j;

    Q->data[s].e = M.data[p].e;

    p++; s++; Q->tu++;

    }

    while(q < tq){

    Q->data[s].i = arow;

    Q->data[s].j = N.data[q].j;

    Q->data[s].e = - N.data[q].e;

    q++; s++; Q->tu++;

    }

    }

    return 1;

    }

    int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

    // 求矩阵乘积Q=M×N,采用行逻辑链接储存表示

    int arow,brow;

    int p,q,t,tp;

    int ccol;

    int ctemp[MAXRC + 1];

    if(M.nu != N.mu) return 0;

    Q->mu = M.mu; Q->nu = N.nu; Q->tu = 0; // Q初始化

    if(M.tu * N.tu != 0){ // Q是非零矩阵

    for(arow = 1; arow <= M.mu; ++arow){ // 处理M的每一行

    for(int i = 1; i <= N.nu; i++) ctemp[i] = 0; // 当前行各元素累加器清零

    Q->rpos[arow] = Q->tu + 1;

    if(arow < M.mu) tp = M.rpos[arow + 1];

    else{tp = M.tu + 1;}

    for(p = M.rpos[arow]; p

    brow = M.data[p].j; // 找到对应元所在N中的行号

    if(brow < N.mu) t = N.rpos[brow + 1];

    else{t = N.tu + 1;}

    for(q = N.rpos[brow]; q

    ccol = N.data[q].j; // 乘积元素在Q中的列号

    ctemp[ccol] += M.data[p].e * N.data[q].e;

    }// for q

    }// 求得Q中第crow(=arow)行的非零元

    for(ccol = 1; ccol <= Q->nu; ++ccol){ //压缩储存改行非零元

    if(ctemp[ccol]){

    if(++Q->tu > MAXSIZE) return 0;

    Q->data[Q->tu].i = arow;

    Q->data[Q->tu].j = ccol;

    Q->data[Q->tu].e = ctemp[ccol];

    }// if

    } // for ccol

    }// for arow

    }// if

    return 1;

    }// MultSMatrix

    int main(){

    int num;

    RLSMatrix M, N, Q;

    do{

    printf("操作:1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出\n");

    scanf("%d",&num);

    if(num == 1 || num == 2 || num == 3){

    printf("请输入矩阵1\n");

    CreateSMatrix(&M);

    printf("请输入矩阵2\n");

    CreateSMatrix(&N);

    printf("两矩阵为:\n");

    PrintSMatrix(M);

    printf("\n");

    PrintSMatrix(N);

    switch(num){

    case 1:

    {

    if(AddSMatrix(M,N,&Q)){

    printf("结果:\n");

    PrintSMatrix(Q);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 2:

    {

    if(SubSMatrix(M,N,&Q)){

    printf("结果:\n");

    PrintSMatrix(Q);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 3:

    {

    if(MultSMatrix(M,N,&Q)){

    printf("结果:\n");

    PrintSMatrix(Q);

    }

    else {printf("参数错误\n");}

    break;

    }

    default: break;

    }

    }

    }while(num == 1 || num == 2 || num == 3);

    return 1;

    }

    crosmatrix.c

    #include

    #include

    #define MAXSIZE 400

    #define MAXRC 20

    typedef struct OLNode{

    int i,j;

    int e;

    struct OLNode *right, *down;

    }OLNode, *OLink;

    typedef struct {

    OLink *rhead, *chead;

    int mu, nu, tu;

    }CrossList;

    int CreateSMatrix_OL(CrossList *M){

    if(M) free(M);

    int c;

    int m,n,t;

    int i,j,k,e;

    OLink p,q;

    do{

    printf("输入矩阵行数,列数和非零元数目,用空格隔开\n");

    scanf("%d %d %d", &m, &n, &t);

    if(m < 0 || n < 0 || t < 0 || t > m*n){

    printf("参数错误 \n");

    }

    }while(m < 0 || n < 0 || t < 0 || t > m*n);

    M->mu = m; M->nu = n; M->tu = t;

    if(!(M->rhead = (OLink*)malloc((m+1)*sizeof(OLink)))) exit(-2);

    if(!(M->chead = (OLink*)malloc((n+1)*sizeof(OLink)))) exit(-2);

    for(c = 1; c <= M->mu; c++) M->rhead[c]=NULL;

    for(c = 1; c <= M->nu; c++) M->chead[c]=NULL;

    for(k = 1; k <= t; k++){

    do{

    printf("输入第%d个非零元的行号 列号 值, 用空格隔开\n",k);

    scanf("%d %d %d", &i, &j, &e);

    if(i <= 0 || j <= 0 || i > m || j > n|| e==0){

    printf("参数错误\n");

    }

    }while(i <= 0 || j <= 0 || i > m || j > n|| e==0);

    if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p->i = i; p->j = j; p ->e = e;

    if(M->rhead[i] == NULL || M->rhead[i]->j > j){

    p->right = M->rhead[i];

    M->rhead[i] = p;

    }else{

    for(q = M->rhead[i]; (q->right) && (q->right->j < j); q = q->right);

    p->right = q->right;

    q->right = p;

    }

    if(M->chead[j] == NULL || M->chead[j]->i > i){

    p->down = M->chead[j];

    M->chead[j] = p;

    }else{

    for(q = M->chead[j]; (q->down) && (q->down->i < i); q = q->down);

    p->down = q->down;

    q->down = p;

    }

    }

    return 1;

    }

    int PrintSMatrix_OL(CrossList M){

    OLink p;

    int row,col;

    for(row = 1; row <= M.mu; row++){

    if(M.rhead[row]){

    p = M.rhead[row];

    for(col = 1; col <= M.nu; col++){

    if(p->i == row && p->j == col && p != NULL){

    printf("%d\t",p->e);

    if(p->right) p = p->right;

    }else{printf("0\t");}

    }

    }else{for(col = 1; col <= M.nu; col++) printf("0\t");}

    printf("\n");

    }

    return 1;

    }

    int AddSMatrix_OL(CrossList *A, CrossList *B){

    OLink pa, pb, pre, p, hl[MAXRC + 1];

    int i, j;

    if(A->mu != B->mu || A->nu != B->nu) return 0;

    for(j = 1; j <= A->nu; j++) hl[j] = A->chead[j];

    for(i = 1; i <= A->mu; i++){

    pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL;

    while(pb){

    if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p->i = pb->i; p->j = pb->j; p->e = pb->e;

    if(pa == NULL || pa->j > pb->j){

    if(pre == NULL) A->rhead[p->i] = p;

    else{pre->right = p; }

    p->right = pa;

    pre = p;

    if(A->chead[p->j] == NULL || A->chead[p->j]->i > p->i){

    p->down = A->chead[p->j];

    A->chead[p->j] = p;

    }else{

    p->down = hl[p->j]->down;

    hl[p->j]->down = p;

    }

    hl[p->j] = p;

    pb = pb->right;

    A->tu++;

    }else if(pa && pa->j < pb->j){

    pre = pa;

    pa = pa->right;

    }else if(pa->j == pb->j){

    pa->e += pb->e;

    if(pa->e == 0){

    if(pre == NULL) A->rhead[pa->i] = pa->right;

    else{pre->right = pa->right; }

    p = pa; pa = pa->right;

    if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down;

    else{hl[p->j]->down = p->down; }

    free(p);

    pb = pb->right;

    A->tu--;

    }else{pre = pa; pa = pa->right; pb = pb->right; }

    }

    }

    }

    return 1;

    }

    int SubSMatrix_OL(CrossList *A, CrossList *B){

    OLink pa, pb, pre, p, hl[MAXRC + 1];

    int i, j;

    if(A->mu != B->mu || A->nu != B->nu) return 0;

    for(j = 1; j <= A->nu; j++) hl[j] = A->chead[j];

    for(i = 1; i <= A->mu; i++){

    pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL;

    while(pb){

    if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p->i = pb->i; p->j = pb->j; p->e = - pb->e;

    if(pa == NULL || pa->j > pb->j){

    if(pre == NULL) A->rhead[p->i] = p;

    else{pre->right = p; }

    p->right = pa;

    pre = p;

    if(A->chead[p->j] == NULL || A->chead[p->j]->i > p->i){

    p->down = A->chead[p->j];

    A->chead[p->j] = p;

    }else{

    p->down = hl[p->j]->down;

    hl[p->j]->down = p;

    }

    hl[p->j] = p;

    pb = pb->right;

    A->tu++;

    }else if(pa && pa->j < pb->j){

    pre = pa;

    pa = pa->right;

    }else if(pa->j == pb->j){

    pa->e -= pb->e;

    if(pa->e == 0){

    if(pre == NULL) A->rhead[pa->i] = pa->right;

    else{pre->right = pa->right; }

    p = pa; pa = pa->right;

    if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down;

    else{hl[p->j]->down = p->down; }

    free(p);

    pb = pb->right;

    A->tu--;

    }else{pre = pa; pa = pa->right; pb = pb->right; }

    }

    }

    }

    return 1;

    }

    int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C){

    int i, j, e;

    OLink p, q, p1, rpre, cpre;

    if(A.nu != B.mu) return 0;

    C->mu = A.mu; C->nu = B.nu; C->tu = 0;

    if(!(C->rhead = (OLink*)malloc((C->mu+1)*sizeof(OLink)))) exit(-2);

    if(!(C->chead = (OLink*)malloc((C->nu+1)*sizeof(OLink)))) exit(-2);

    for(i = 1; i <= C->mu; i++) C->rhead[i] = NULL;

    for(j = 1; j <= C->nu; j++) C->chead[j] = NULL;

    for(i = 1; i <= C->mu; i++){

    for(j = 1; j <= C->nu; j++){

    p = A.rhead[i]; q = B.chead[j]; e = 0;

    while(p && q){

    if(p->j > q->i){

    q = q->down;

    }else if(p->j < q->i){

    p = p->right;

    }else{

    e += p->e * q->e;

    q = q->down;

    p = p->right;

    }

    }

    if(e){

    C->tu++;

    if(!(p1 = (OLNode*)malloc(sizeof(OLNode)))) exit(-2);

    p1->i = i; p1->j = j; p1->e = e;

    p1->right = NULL; p1->down = NULL;

    // 行插入

    if(C->rhead[i] == NULL) {C->rhead[i] = p1; rpre = p1;}

    else{rpre->right = p1; rpre = p1; }

    // 列插入

    if(C->chead[j] == NULL) {C->chead[j] = p1; cpre = p1;}

    else{cpre->down = p1; cpre = p1; }

    }

    }

    }

    return 1;

    }

    int main(){

    int num;

    CrossList M, N, Q;

    do{

    printf("操作:1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出\n");

    scanf("%d",&num);

    if(num == 1 || num == 2 || num == 3){

    printf("请输入矩阵1\n");

    CreateSMatrix_OL(&M);

    printf("请输入矩阵2\n");

    CreateSMatrix_OL(&N);

    printf("两矩阵为:\n");

    PrintSMatrix_OL(M);

    printf("\n");

    PrintSMatrix_OL(N);

    switch(num){

    case 1:

    {

    if(AddSMatrix_OL(&M, &N)){

    printf("结果:\n");

    PrintSMatrix_OL(M);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 2:

    {

    if(SubSMatrix_OL(&M, &N)){

    printf("结果:\n");

    PrintSMatrix_OL(M);

    }

    else {printf("参数错误\n");}

    break;

    }

    case 3:

    {

    if(MultSMatrix_OL(M,N,&Q)){

    printf("结果:\n");

    PrintSMatrix_OL(Q);

    }

    else {printf("参数错误\n");}

    break;

    }

    default: break;

    }

    }

    }while(num == 1 || num == 2 || num == 3);

    return 1;

    }

    展开全文
  • 实现一个能进行稀疏矩阵基本运算运算器,具体功能有:以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个稀疏矩阵相加、相减、相乘的功能。稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的...

    设计要求

    稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算准备效率。实现一个能进行稀疏矩阵基本运算的运算器,具体功能有:

    • 以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个稀疏矩阵相加、相减、相乘的功能。
    • 稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。
    • 稀疏矩阵采用带行逻辑链接信息的三元组顺序存储。

    需求分析

    • 设计函数建立稀疏矩阵,初始化值。
    • 设计函数输出稀疏矩阵的值。
    • 构造函数进行两个稀疏矩阵相加,输出最终的稀疏矩阵。
    • 构造函数进行两个稀疏矩阵相减,输出最终的稀疏矩阵。
    • 构造函数进行两个稀疏矩阵的相乘,输出最终的稀疏矩阵。
    • 构造函数进行稀疏矩阵的转置,并输出结果。
    • 退出系统。

    概要设计

    (1)主界面设计为了实现对稀疏矩阵的多种算法功能的管理,首先设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能,方便用户交互式使用本系统。本系统主控菜单运行界面如图:
    菜单
    (2)存储结构设计本系统采用单链表结构存储稀疏矩阵的具体信息。其中:全部结点的信息用头结点为指针数组的单链表存储。
    (3)系统功能设计本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。建立稀疏矩阵用void Creat()实现,依据读入的行数和列数以及非零元素的个数,分别设定每个非零元素的信息。4个子功能的设计描述如下:

    • 稀疏矩阵的加法:此功能由函数void add( )实现,当用户选择该功能,系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法,最后输出结果。
    • 稀疏矩阵的减法:此功能由函数void sub( )实现。当用户选择该功能,系统提示输入要进行相减的两个矩阵的详细信息。然后进行相减,最后得到结果。
    • 稀疏矩阵的乘法:此功能由函数void mult( )实现。当用户选择该功能,系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘,最后得到结果。
    • 系统程序的退出:即退出稀疏矩阵的应用系统。用户选择此功能时,系统会提示计算器已关闭,按任意键退出。

    模块设计

    • void creat(TSMatrix *T) /由用户输入创建稀疏矩阵/
    • void print(TSMatrix A) /输出稀疏矩阵/
    • void add(TSMatrix A,TSMatrix B) /加法运算/
    • void sub(TSMatrix A,TSMatrix B) /减法运算/
    • void mult(TSMatrix A,TSMatrix B,TSMatrix *c) /乘法运算/
    • char menu() /计算器主界面(菜单)/
    • int main() /功能主函数/

    C语言源程序——建议使用Devc ++ 运行

    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<conio.h>
    #include<malloc.h>
    #include<string.h>
    #define MAXSIZE 100          /*假设非零元个数的最大值为100*/
    #define MAXMU 20              /*稀疏矩阵最大行列值为20*/
    int count = 1;
    typedef struct
    {
    	int i,j;                 /*该非零元的行下标和列下标*/
    	int v;
    }Triple;
    typedef struct            /*稀疏矩阵是由三元组的顺序存储*/
    {   int rpos[MAXMU+1];	     /*各行第一个非零元素的位置表*/
    	Triple data[MAXSIZE+1];  /*非零元三元组顺序表,data[0]未使用*/
    	int mu,nu,tu;            /*矩阵的行数,列数和非零元个数*/
    }TSMatrix;
     
    void creat(TSMatrix *T) /*由用户输入创建稀疏矩阵*/
    {
    	int row,num,k;
    	do
    	{
    		system("cls");
    		printf("\n 请输入第%d个矩阵!\n",count);
    		count = count + 1;
    		printf("*********************************\n"); 
    		printf(" 请输入稀疏矩阵行数: "  );
    		scanf("%d", &T->mu);
    		if (T->mu<0 || T->mu>MAXMU)
    			printf("\n 行数超出定义范围,请重新输入!\n");
    	} while (T->mu<0 || T->mu>MAXMU);
    	do
    	{
    		printf(" 请输入稀疏矩阵列数: ");
    		scanf("%d", &T->nu);
    		if (T->nu<0 || T->nu>MAXMU)
    			printf("\n 列数超出定义范围,请重新输入!\n"); 
    	} while (T->nu<0 || T->nu>MAXMU);
    	do
    	{
    		printf(" 请输入稀疏矩阵的非零元素个数: ");
    		scanf("%d", &T->tu);
    		if (T->tu>MAXSIZE || (T->tu>T->mu*T->nu))
    			printf("\n 非零元素个数超出定义范围,请重新输入!\n");
    	} while (T->tu>MAXSIZE || (T->tu>T->mu*T->nu));
    	printf("**********************************\n");
    	printf(" 请按行从小到大依次输入结点信息!\n");
    	for (k=1; k<=T->tu; k++)
    	{
    		do
    		{
    			printf(" 请按三元组存储输入第%d个非零元素的行数i:", k);
    			scanf("%d", &T->data[k].i);
    			if (!T->data[k].i || T->data[k].i>T->mu)
    				printf("\n 输入有误,请重新输入!\n");
    		} while ((!T->data[k].i || T->data[k].i>T->mu));
    		do
    		{
    			printf(" 请按三元组存储输入第%d个非零元素的列数j:", k);
    			scanf("%d", &T->data[k].j);
    			if (!T->data[k].j || T->data[k].j>T->nu)
    				printf("\n 输入有误,请重新输入!\n");
    		} while ((!T->data[k].j || T->data[k].j>T->nu));
    		do
    		{
    			printf(" 请按三元组存储输入第%d个非零元素的值v:", k);
    			scanf("%d", &T->data[k].v);
    			if (T->data[k].v==0)
    				printf("\n 输入有误,请重新输入!\n");
    		} while (T->data[k].v==0);
    		printf("***********************************\n");
    	}
    	for(row=1,num=1;row<=T->mu;row++)   /*行逻辑链接信息存储*/
    	{
    		T->rpos[row]=num;
    		while(T->data[num].i==row)
    			num++;
    	} 
    	return;
    }
     
    void print(TSMatrix A)   /*输出稀疏矩阵*/
    {
    	int q,n,k,a=0;
        system("cls");
        printf("\n\n经过稀疏矩阵运算器运算,所得结果为:\n");
        printf("***********************************\n");
        printf("***********************************\n");
    	for(n=1;n<=A.mu;n++)
    	{
    	 for(k=1;k<=A.nu;k++)
           {
    		 for(q=1;q<=A.tu;q++)
    			 if(A.data[q].i==n && A.data[q].j==k)
    			 {
    				 printf("\t%-3d",A.data[q].v);break;
    			 }
    		 if(q>A.tu)
    			 printf("\t%-3d",a);		 
    	   }
    	 printf("\n");
    	} 
    	printf("***********************************\n");
    	printf("***********************************\n");
     }
     
    void add(TSMatrix A,TSMatrix B)   /*加法运算*/
    {
    	int n,k;
    	if(A.mu!=B.mu || A.nu!=B.nu)
    	{ 
    		printf("\n          不满足矩阵相加条件!"); 
            printf("\n 需满足两矩阵的行数、列数均对应相等方可进行加法运算!!");
    	}
    	else  
    	{
    		for(n=1;n<=A.tu;n++)
    	         for(k=1;k<=B.tu;k++)   /*将矩阵A的非零元接至B中*/
    				 if(A.data[n].i==B.data[k].i && A.data[n].j==B.data[k].j)
    				 {
    					 A.data[n].v+=B.data[k].v;
    			         B.data[k].v=0;
    				 }
    		for(k=1;k<=B.tu;k++)
    			if(B.data[k].v!=0)
    			{
    				A.data[A.tu+1].i=B.data[k].i;
    				A.data[A.tu+1].j=B.data[k].j;
    				A.data[A.tu+1].v=B.data[k].v;
    				A.tu++;	
    			}
    		print(A);
         }
    }
     
    void sub(TSMatrix A,TSMatrix B)   /*减法运算*/
    {
    	int n,k;
        if(A.mu!=B.mu || A.nu!=B.nu)
    	{
    		printf("\n    不满足矩阵相减条件!"); 
    		printf("\n 需要满足两矩阵的行数、列数均对应相等方可进行减法运算!!");
    	}
    	else
    	{
    	    for(n=1;n<=A.tu;n++)
    	        for(k=1;k<=B.tu;k++)   /*将矩阵A的非零元接至B中*/
    				if(A.data[n].i==B.data[k].i && A.data[n].j==B.data[k].j)
    				{
    					A.data[n].v-=B.data[k].v;
    					B.data[k].v=0;
    				}
                for(k=1;k<=B.tu;k++)
    				if(B.data[k].v!=0)
    				{
    					A.data[A.tu+1].i=B.data[k].i;
    				    A.data[A.tu+1].j=B.data[k].j;
    				    A.data[A.tu+1].v=-B.data[k].v;
    				    A.tu++;
    				}
    		print(A);  
    	}
    }
     
    void mult(TSMatrix A,TSMatrix B,TSMatrix *c)   /*乘法运算*/
    {
    	int arow,tp,i,t;
    	int ccol,p,brow,q;
    	int ctemp[MAXMU+1];
    	if(A.nu!=B.mu)
    	{
    		printf(" 矩阵不满足相乘条件!");
    		return ;
    	}
    	c->mu=A.mu;
    	c->nu=B.nu;
    	c->tu=0;
    	if(A.tu==0||B.tu==0)
    	{
    		printf(" 结果矩阵为零!");
    		return ;
    	}
    	else
    	{
    		for(arow=1;arow<=A.mu;arow++)
    		{
    			for(i=0;i<MAXMU;i++)    /*存储器清零*/
    				ctemp[i]=0;
    			c->rpos[arow]=c->tu+1;
    			if(arow<A.mu)
    				tp=A.rpos[arow+1];
    			else
    				tp=A.tu+1;
    			for(p=A.rpos[arow];p<tp;p++)
    			{
    				brow=A.data[p].j;
    				if(brow<B.mu)
    					t=B.rpos[brow+1];
    				else
    					t=B.tu+1;
    				for(q=B.rpos[brow];q<t;q++)
    				{
    					ccol=B.data[q].j;
    					ctemp[ccol]+=A.data[p].v*B.data[q].v;
    				}
    			}
    			for(ccol=1;ccol<=c->nu;ccol++)
    				if(ctemp[ccol])
    				{
    					if(++(c->tu)>MAXSIZE)
    					{
    						printf("超出范围!");
    						return ;
    					}
    				    c->data[c->tu].v=ctemp[ccol];
    				    c->data[c->tu].i=arow;
    				    c->data[c->tu].j=ccol;
    				}
    		}
    	}
    	print(*c);
    }
     
    char menu()   /*计算器主界面(菜单)*/
    {
    	char n; 
    	system("title 稀疏矩阵运算器"); 
        system("cls");
    	system("mode con cols=70 lines=30");
        printf("\n");
        printf("\n                      课程设计-----*******班                 \n\n\n\n");
        printf("              ****************************************          \n");
        printf("              *                                      *          \n");
        printf("              *         稀 疏 矩 阵 运 算 器         *          \n");
        printf("              *                                      *          \n");
        printf("              *             实 现 运 算              *          \n");
        printf("              *                                      *          \n");
        printf("              *             1:矩阵相加               *          \n");
        printf("              *             2:矩阵相減               *          \n");
        printf("              *             3:矩阵相乘               *          \n");
    	printf("              *             4:选择退出               *          \n");
    	printf("              *                                      *          \n");
        printf("              ****************************************          \n");
        printf("                        请输入序号进行操作  :                \n");
        printf("                                 ");n=getchar();
    	 
        return n;
    }
     
    int main() /*功能主函数*/
    { 
    	TSMatrix A,B,C;
     
    	 for(;;)
    		 switch(menu())
    	 {case '1':creat(&A);
                   creat(&B);
    			   add(A,B);
    			   getch();
    			   break;
          case '2':creat(&A);
                   creat(&B);
    			   sub(A,B);
    			   getch();
    			   break;
          case '3':creat(&A);
                   creat(&B);
    			   mult(A,B,&C);
    			   getch();
    			   break;
          case '4':system("cls");
    			  printf("计算器已关闭,按任意键退出 :)\n");
    			  exit(0);
    	 }
    }
    

    简要说明

    • 输入第一个稀疏矩阵的行数,列数,非零个数
    • 依次输入非零数所在的具体坐标
    • 同理 输入第二个稀疏矩阵的行列非零个数
    • 通常以回车作为输入结束
    • 计算结果以矩阵的形式表现出来

    总结

    总通过本次实验,在我的学习理解上有很大的促进作用。单单对稀疏矩阵,我了解了由于矩阵在程序中常使用二维阵列表示,二维阵列的大小稀疏矩阵与使用的存储器空间成正比,如果多数的元素没有数据,则会造成存储器空间的浪费,为此,必须设计稀疏矩阵的阵列储存方式,利用较少的存储器空间储存完整的矩阵数据。二维数组Amn中有N个非零元素,若N<<m*n,则称A为稀疏矩阵。由于稀疏矩阵中含有很多的0元素,在计算机中存储会浪费很多的空间,因此我们通常采用压缩存储的方法。

    展开全文
  • 教学单位计算机科学与技术 学生学号_5 HUBEI ENGINEERING UNIVERSITY 数据结构 课程设计报告书 题 目稀疏矩阵运算器 学生 专业名称 指导教师 实验目的 深入研究数组的存储表示和实现技术熟悉广义表存储结构的特性 ...
  • 输入要求:稀疏矩阵的行、列和非零元素个数 以及每个非零元素在矩阵的位置 以三元组格式存储稀疏矩阵 输出要求:根据选项输出 稀疏矩阵的转置、加法、减法、乘法
  • 稀疏运算(用于向量和矩阵) 复数 张量结构 命名张量尺寸(将):2x2算子在自旋和极化之间存在差异。 它有助于捕获错误。 文档: (由生成 )。 安装 最简单的方法是从安装: npm install quantum-tensors 或者...
  • python 稀疏矩阵计算

    千次阅读 2020-11-04 13:46:19
    稀疏矩阵运算库 官方文档 2 稀疏矩阵的实现 code # coding = utf-8 from scipy.sparse import rand '''生成随机稀疏矩阵''' A = rand(4, 4, density=0.25, format="csc", random_state=42) B = rand(4, 4, density=...
  • 数据结构|稀疏矩阵运算

    千次阅读 2019-12-10 00:20:34
    稀疏矩阵运算器 一、需求分析 1、稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 2、以“带行逻辑链接信息...
  • 置换与重新排序可以通过以下两种方式表示稀疏矩阵 S 的行和列置换:置换矩阵 P 对作为 P*S 的 S 有效,或对作为 S*P' 的列有效。置换向量 p 是包含 1:n 置换的满向量。对作为 S(p,:) 的 S 行有效,或对作为 S(:,p) ...
  • 稀疏矩阵运算器.rar

    2021-04-01 12:00:26
    实现任意两个稀疏矩阵的加、减和乘运算和任一稀疏矩阵的转置运算
  • 简单的运算器,可以满足加法减法和乘法,采用的三元组逻辑链接结构。
  • 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算准备效率。实现一个能进行稀疏矩阵基本运算运算器。
  • C语言实现的稀疏矩阵运算器,通过用数据结构来实现(一部分),主要是矩阵的实现
  • (数据结构课程设计)稀疏矩阵运算

    千次阅读 多人点赞 2017-05-24 22:53:48
     具体功能有:(1)以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个稀疏矩阵相加、相减、相乘和求逆的运算。(2)稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。2. 本...
  • 特殊矩阵、稀疏矩阵的表示实现与运算
  • 根据用户输入的矩阵,实现稀疏矩阵的求和运算,并输出结果。 2、输入要求:的数据在程序运行的时候由用户提供,先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数,输入这些非零元,还需要用户为这些...
  • 稀疏矩阵运算——矩阵相加

    千次阅读 2022-04-13 18:30:15
    课程名称: 数据结构A 实验名称: 实验五 稀疏矩阵运算 班 级: XXX 学生姓名: XXX 学号: XXXXX 指导教师评定: XXX 签 名: XXX 一、实验目的 数组是一种常用的数据类型,本实验是有关两个稀疏矩阵进行相加...
  • 稀疏矩阵是指那些多数元素为零的矩阵,利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算运算器 基本要求 以“带行逻辑连接信息”的三元组顺序表表示系数矩阵,...
  • 稀疏矩阵运算器,以“带行逻辑链接信息”的三元组 顺序表表示稀疏矩阵, ~实现两个矩阵相加,相减或者相乘的运算。 ~稀疏矩阵的输入形式 采用三元组表示,运算结果矩阵 以通常阵列形式列出 CODE: /* 稀疏矩阵...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,766
精华内容 25,906
关键字:

稀疏矩阵的运算

友情链接: fengneng_v89.zip