精华内容
下载资源
问答
  • 稀疏矩阵计算器(三元组实现矩阵加减乘法)
    千次阅读 多人点赞
    2019-10-25 19:06:07

    一、问题描述:

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

    二、需求分析:

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

    三、代码实现

    #include <stdio.h>
    #include <iostream>
    
    #define ERROR -1
    #define MAXSIZE 12500    //非零元个数最大值MAXSIZE
    #define MAXRC 21         //各行第一个非零元位置最大值MAXRC
    #define OK 1
    
    typedef int ElemType;
    typedef struct         //同课本P98
    {
        int i,j;
        ElemType e;
    } Triple;
    
    typedef struct       //同课本P100
    {
        Triple data[MAXSIZE+1];             //非零元三元组表
        int rpos[MAXRC+1];                  //各行第一个非零元的位置表
        int mu,nu,tu;                       //矩阵的行数、列数和非零元个数
    } RLSMatrix;
    
    void CreatSMatrix(RLSMatrix &M)             //建立以“带行链接信息”的三元组顺序表示的稀疏矩阵
    {
        for(int i=1; i<=MAXRC+1; i++)
            M.rpos[i]=0;     //令所有的位置都为0
        printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");
        scanf("%d %d %d",&M.mu,&M.nu,&M.tu);
        for(int i=1; i<=M.tu; i++)
        {
            printf("请用三元组形式输入矩阵的元素(行 列 非零元素):");
            scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
        }
        for(int i=1,j=1; i<=M.mu; i++)     //求M.rpos[i]
        {
            M.rpos[i]=j;
            while(M.data[j].i==i && j<=M.tu)  j++;        //若某一行的元素多于1个时
        }
    }
    
    int MultsMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
    {
        int brow,ccol,p,q,t,tp,ctemp[MAXRC+1],i;
        Q.mu=M.mu;     //Q初始化
        Q.nu=N.nu;
        Q.tu=0;
        if(M.nu!=N.mu)return ERROR;
        if(M.tu*N.tu)        //Q是非零矩阵
        {
            for(int arow=1; arow<=M.mu; ++arow) //处理M的每一行
            {
                for( i=1; i<=MAXRC+1; 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<tp; ++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<t; ++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 ERROR;
                        Q.data[Q.tu].i=arow;
                        Q.data[Q.tu].j=ccol;
                        Q.data[Q.tu].e=ctemp[ccol];
                    }//if
            }//for arow
        }//if
        return 1;
    }
    
    bool AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)  //矩阵相加
    {
        if(M.mu!=N.mu||M.nu!=N.nu)return ERROR;
        int i,j,k=1;
        Q.mu=M.mu;
        Q.nu=M.nu;
        for(i=1,j=1; i<=M.tu&&j<=N.tu;)
        {
            //按行优先,故分以下几种情况
            if(M.data[i].i==N.data[j].i)          //两元素同一行
            {
                if(M.data[i].j==N.data[j].j)         //两元素同一行且同一列(同位置)
                {
                    Q.data[k].i=M.data[i].i;
                    Q.data[k].j=M.data[i].j;
                    Q.data[k].e=M.data[i].e+N.data[j].e;
                    i++;
                    j++;
                    k++;
                }
                else if(M.data[i].j<N.data[j].j)    //两元素同一行,但M中的元素列数较小
                {
                    Q.data[k].i=M.data[i].i;
                    Q.data[k].j=M.data[i].j;
                    Q.data[k].e=M.data[i].e;
                    k++;
                    i++;
                }
                else if(M.data[i].j>N.data[j].j)    //两元素同一行,但M中的元素列数较大
                {
                    Q.data[k].i=N.data[j].i;
                    Q.data[k].j=N.data[j].j;
                    Q.data[k].e=N.data[j].e;
                    k++;
                    j++;
                }
            }
            else if(M.data[i].i<N.data[j].i)        //M中的元素行数较小
            {
                Q.data[k].i=M.data[i].i;
                Q.data[k].j=M.data[i].j;
                Q.data[k].e=M.data[i].e;
                k++;
                i++;
            }
            else if(M.data[i].i>N.data[j].i)        //M中的元素行数较大
            {
                Q.data[k].i=N.data[j].i;
                Q.data[k].j=N.data[j].j;
                Q.data[k].e=N.data[j].e;
                k++;
                j++;
            }
        }
        if(i!=M.tu+1)                             //计算最后的元素
            for(; i<=M.tu; i++)
            {
                Q.data[k].i=M.data[i].i;
                Q.data[k].j=M.data[i].j;
                Q.data[k].e=M.data[i].e;
                k++;
            }
        if(j!=N.tu+1)
            for(; j<=N.tu; j++)
            {
                Q.data[k].i=N.data[j].i;
                Q.data[k].j=N.data[j].j;
                Q.data[k].e=N.data[j].e;
                k++;
            }
        for(i=1,j=1; i<=Q.mu; i++)      //求Q.rpos[i]
        {
            Q.rpos[i]=j;
            while(Q.data[j].i==i && j<=Q.tu)        //若某一行的元素多于1个时
                j++;
        }
        return OK;
    }
    void SubtSMatrix(RLSMatrix M,RLSMatrix &N,RLSMatrix &Q)
    {
        //矩阵减法
        int i=1;
        for(; i<=N.tu; i++)
        {
            N.data[i].e=-N.data[i].e;
        }
        AddSMatrix(M,N,Q);
    }
    
    void PrintSMatrix(RLSMatrix M)
    {
        //以通常阵列形式输出稀疏矩阵
        int k,l,n;
        for(k=1,n=1; k<=M.mu; k++)
        {
            for(l=1; l<=M.nu; l++)
            {
                if(M.data[n].i==k && M.data[n].j==l)
                {
                    printf("%5d",M.data[n].e);
                    n++;
                }
                else
                    printf("%5d",0);
            }
            printf("\n");
        }
        printf("\n");
    
    }
    int Destory_SMatrix(RLSMatrix &M)
    {
        M.mu=M.nu=M.tu=0;
        return 1;
    }
    
    int main()
    {
        RLSMatrix A,B,C;
        int flag;
        while(1)
        {
            printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
            printf("         稀疏矩阵的加、减、乘         \n");
            printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
            printf("           1、稀疏矩阵的加法                           \n");
            printf("           2、稀疏矩阵的减法                           \n");
            printf("           3、稀疏矩阵的乘法                           \n");
            printf("           4、退出程序                                        \n");
            printf("━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
            printf("输入要进行的运算功能的编号:");
            scanf("%d",&flag);
            if(flag==4)
            {
                printf("     \n程序已经退出!    \n");
                exit(0);
            }
            switch(flag)
            {
            case 1:	//加法
                CreatSMatrix(A);
                printf("矩阵A=\n");
                PrintSMatrix(A);
                CreatSMatrix(B);
                printf("矩阵B=\n");
                PrintSMatrix(B);
                if(A.mu==B.mu  && A.nu==B.nu)
                {
                    printf("A+B=\n");
                    AddSMatrix(A,B,C);
                    PrintSMatrix(C);
                }
                else
                    printf("错误!两矩阵的行列数不一致\n");
                break;
            case 2://减法
                CreatSMatrix(A);
                printf("矩阵A=\n");
                PrintSMatrix(A);
                CreatSMatrix(B);;
                printf("矩阵B=\n");
                PrintSMatrix(B);
                if(A.mu==B.mu  && A.nu==B.nu)
                {
                    printf("A-B=\n");
                    SubtSMatrix(A,B,C);
                    PrintSMatrix(C);
                }
                else
                    printf("错误!两矩阵的行列数不一致\n");
                break;
            case 3://乘法
                CreatSMatrix(A);
                printf("矩阵A=\n");
                PrintSMatrix(A);
                CreatSMatrix(B);
                printf("矩阵B=\n");
                PrintSMatrix(B);
                if(A.nu==B.mu)
                {
                    printf("A*B=\n");
                    MultsMatrix(A,B,C);
                    PrintSMatrix(C);
                }
                else
                    printf("错误!矩阵A的列数不等于矩阵B的行数\n");
                break;
            default:
                printf("输入错误!\n");
            }
            Destory_SMatrix(A);
            Destory_SMatrix(B);
            Destory_SMatrix(C);
        }
        return 0;
    }
    
    

     

    更多相关内容
  • 稀疏矩阵计算器

    2012-08-09 16:32:45
    稀疏矩阵计算器
  • 数据结构实验报告 稀疏矩阵计算器。稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储(只存储非零元)和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行...
  • 教育资料 实验报告 题目稀疏矩阵运算器 班级14电子商务平台建设班 完成日期2015.11.2 学号20141103468 姓名 孙少辉 学号20141103421 姓名 杨德龙 学号20141103407 姓名 柴益新 一需求分析 稀疏矩阵是指那些多数元素...
  • 数据结构实验。实现了对稀疏矩阵的加减乘运算,并制作了MFC界面。采用十字链表作为数据结构。 这个忘记上传.net2005的解决方案文件了。。。已经下载过得同学抱歉了。还是麻烦新建一个.net2005的项目。
  • 这个可以运行。。。 用MFC做的界面,使用了十字链表作为存储结构。
  • 稀疏矩阵运算器

    2017-03-14 22:48:22
    printf("输入稀疏矩阵A的行数,列数和非零元个数:"); scanf("%d %d %d",&A.m,&A.n,&A.t); for(k=1;k;k++) { printf("输入第%d个非0元素的行数,列数和值:",k); scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&...
  • 稀疏矩阵计算器,能够:⑴输入并建立稀疏矩阵;⑵输出稀疏矩阵;⑶执行两个矩阵相加;⑷求一个矩阵的转置矩阵;
  • c稀疏矩阵计算器c语言代码 矩阵 计算器 txt 简陋 见谅
  • 以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个矩阵的相加相减和相乘的运算。
  • C语言 数据结构 稀疏矩阵计算器 实验报告
  • 大型矩阵计算器

    2018-01-08 15:22:06
    计算器能够实现1000X1000的大型矩阵的加减乘以及求逆操作。同时可选择采用三元组和矩阵的形式输出。矩阵的输入可直接通过读取txt文件,文件中附有输入样板,即三元组形式。
  • 压缩存储输入矩阵,允许输入多种矩阵,进行矩阵加,减,乘,转置,求逆,行列式计算
  • 题目:设计一个程序,实现一个能进行稀疏矩阵基本运算的计算器。按照教科书《数据结构(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;

    }

    展开全文
  • 清华大学版《数据结构》第三次试验代码,原创
  • 稀疏矩阵是指那些多数元素为零的矩阵,利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器 基本要求 以“带行逻辑连接信息”的三元组顺序表表示系数矩阵,...

    问题描述

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

    基本要求

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

    运行截图

    数据输入

    在这里插入图片描述
    输出结果
    在这里插入图片描述

    代码实现

    import java.util.Arrays;
    import java.util.Scanner;
    
    public class matrixTest {
        public static void main(String[] args) throws Exception {
            Matrix M = new Matrix();
            System.out.println("创建矩阵M:");
            M.CreateMatrix();
            Matrix N = new Matrix();
            System.out.println("创建矩阵N:");
            N.CreateMatrix();
            System.out.println("M:");
            M.PrintMatrix();
            System.out.println("N: ");
            N.PrintMatrix();
            Matrix Q = Matrix.add(M,N);
            System.out.println("M+N:");
            Q.PrintMatrix();
            Q = Matrix.sub(M,N);
            System.out.println("M-N:");
            Q.PrintMatrix();
            Q = Matrix.multiply(M,N);
            System.out.println("M*N: ");
            Q.PrintMatrix();
        }
    }
    class  Triple{ //三元组
        int i,j;//非零元的行下标和列下标
        int e;//非零元的数值
    }
    class Matrix{
        Triple[] triples;//非零元三组表
        int mu,nu,tu;//矩阵的行数列数和非零元的个数
        int[] rops;//各行第一个非零元的在tripls数组里的位置表
        public void CreateMatrix() throws Exception{
            Scanner in = new Scanner(System.in);
            System.out.println("请输入矩阵的行数、列数,以及非零元的个数");
            mu = in.nextInt();
            nu = in.nextInt();
            tu = in.nextInt();
            if(tu>mu*nu) throw new Exception("输入非法,非零元个数大于矩阵元素的个数");
            triples = new Triple[tu+1];
            Arrays.fill(triples,null);
            rops = new int[mu+1];
            Arrays.fill(rops,0);//快速初始化rops数组,将rops数组里的值都致为0
            System.out.println("请依次输入非零元所在的行数、列数,以及数值,需要按照行的顺序输入");
            /** 这里规定非零元的顺序需要按照行的顺序输入的原因是:
            *要满足:
             *    rpos[row]指示的是矩阵的第row行的第一个非零元在triples里的序号,
             *    rpos[row+1]-1指向矩阵的第row行的最后一个非零元在triples里的序号
             * 这样就要满足非零元是按照行的顺序排列的
             */
            for (int k =1; k <=tu; k++) {
                Triple triple = new Triple();
                triple.i = in.nextInt();
                triple.j = in.nextInt();
                triple.e = in.nextInt();
                if(triple.i<=0||triple.j<=0) {
                    System.out.println("输入非法,行数和列数必须为正数,请重新输入");
                    k--;
                    continue;
                }
                else if (triple.e==0){
                    System.out.println("输入非法,非零元不能为0,请重新输入");
                    k--;
                    continue;
                }
                else{
                    triples[k]=triple;
                    if (rops[triple.i]==0)
                        rops[triple.i] =k;//记录每行第一个非零元的位置(只会在当前行有非零行的情况下记录)
                                                               //
                }
            }
            for (int k=mu;k>=1;k--){ //处理那些没有非零元的行
                if (rops[k]==0){
                    if (k==mu)
                        rops[k]=tu+1;//如果最后一行没有非零元,需要特殊处理
                    else
                        rops[k]=rops[k+1];
                }
            }
        }
        public void PrintMatrix(){
            //以行列式形式输出矩阵
            int k=1;
            for (int r=1;r<=mu;r++){
                for(int c=1;c<=nu;c++){
    
                    if (k<=tu&&r==triples[k].i&&c==triples[k].j){
                        System.out.printf("%4d ",triples[k].e);
                        k++;
                    }
                    else
                        System.out.print("   0 ");
                }
                System.out.println();
            }
            System.out.println();
        }
        public static Triple copy(Triple t){
            //赋值函数,把传进来的对象的数据域复制给一个新建的对象,并把新建的对象返回
            Triple copy = new Triple();
            copy.i = t.i;
            copy.j = t.j;
            copy.e = t.e;
            return  copy;
        }
        public static Matrix add(Matrix M,Matrix N){
            if (M.mu==N.nu&&M.nu==N.nu){ //两个矩阵的行数和列数相等才能相加
                Matrix Q = new Matrix();//Q存放 M+N 的结果
                Q.triples = new Triple[M.tu+N.tu+1];
                Q.mu=M.mu;
                Q.nu=M.nu;
                Q.tu=0;
                int m,n,k;
                m=n=k=1;
                while (m<=M.tu&&n<=N.tu) {//依次遍历M和N的三元组
                    if (M.triples[m].i < N.triples[n].i) { // 比较两个矩阵的行数,行数小的先放到Q的三元组里
                        Q.triples[k] = copy( M.triples[m]);
                        m++;
                    } else if (M.triples[m].i > N.triples[n].i) {
                        Q.triples[k] = copy(N.triples[n]);
                        n++;
                    } else { //行数都相等时,比较列的大小
                        if (M.triples[m].j < N.triples[n].j) { //列数小的放到Q的三元组里
                            Q.triples[k] = copy(M.triples[m]);
                            m++;
                        } else if (M.triples[m].j > N.triples[n].j) {
                            Q.triples[k] = copy(N.triples[n]);
                            n++;
                        } else { //行数、列数都相等的情况下
                            if (M.triples[m].e + N.triples[n].e != 0) { //如果对应位置的元素相加不等于0,则相加,并放到Q的三元组里
                                Q.triples[k] = copy(M.triples[m]);
                                Q.triples[k].e = M.triples[m].e + N.triples[n].e;
                                m++;
                                n++;
                            } else { //如果相加等于0,相当于该位置变为零元,则跳过
                                m++;
                                n++;
                                continue;
                            }
                        }
                    }
                    k++;
                    Q.tu++;
                }
                while (m<=M.tu){ //M中剩余的三元组逐一放进Q中
                    Q.triples[k] = copy(M.triples[m]);
                    m++;
                    k++;
                    Q.tu++;
                }
                while (n<=N.tu){//N中剩余的三元组逐一放进Q中
                    Q.triples[k]=copy(N.triples[n]);
                    n++;
                    k++;
                    Q.tu++;
                }
                return Q;
            }else{ //如果两个矩阵的行数和列数不相等
                System.out.println("这两个矩阵不能相加");
                return null;
            }
        }
        public static Matrix sub(Matrix M,Matrix N){ //M-N
            /*
            * 因为前面已经实现M+N的方法,而M-N可以看做 M+(-N)
            * 所以只要把N的非零元都置成相反数,然后在进行M+N,就能实现M-N了
            * */
            if (M.mu==N.mu&&M.nu==N.nu){
                Matrix newN = new Matrix();//用newN存放N的非零元置成相反数后的矩阵
                newN.mu = N.mu;
                newN.nu = N.nu;
                newN.tu = N.tu;
                newN.triples = new Triple[newN.tu+1];
                for (int k =1;k<=newN.tu;k++){
                    newN.triples[k]=copy(N.triples[k]);
                    newN.triples[k].e =-newN.triples[k].e;
                }
                return add(M,newN);
            }else{
                System.out.println("这两个矩阵不能相减");
                return null;
            }
        }
        public static  Matrix multiply(Matrix M,Matrix N){
            if (M.nu!=N.mu){ //如果M的列数不等于N的行数
                System.out.println("这两个矩阵不能相乘");
                return null;
            }
            Matrix Q = new Matrix();//初始化Q
            Q.mu = M.mu;
            Q.nu = N.nu;
            Q.triples = new Triple[Q.mu*Q.nu+1];//非零元的个数最多为矩阵的元素个数
            Q.tu = 0;
            if(M.tu*N.tu!=0){//如果M和N的非零元都不等于0
                int arow;//乘积元素在Q中的行号
                int ccol;//乘积元素在Q中的列号
                int brow;//对N当前行的每一个非零元对应在N中的行号
                int[] ctemp = new int[N.nu+1];//Q 中各行元素值累加器,ctemp[0]不用
                int tp,tq;
                for (arow=1;arow<=M.mu;arow++){//处理M的每一行
                    Arrays.fill(ctemp,0);//初始化Q中行元素值计数器
                    if(arow<M.mu)
                        tp = M.rops[arow+1];//tp指向M的当前行的下一行的第一个非零元的位置
                    else
                        tp = M.tu+1;
                    for (int p =M.rops[arow];p<tp;p++){ //p指向M的当前行的第一个非零元的位置,并开始累加,直到下一行的第一个非零元tp为止
                        brow = M.triples[p].j;//对N当前行的每一个非零元,找到对应在N中的行号
                        if (brow<N.mu)
                            tq = N.rops[brow+1];//tq指向N当前行的下一行第一个非零元位置
                        else
                            tq = N.tu+1;
                        for (int q = N.rops[brow];q<tq;q++){//q指向N的当前行的第一个非零元的位置,并开始累加,直到下一行的第一个非零元tq为止
                            ccol =N.triples[q].j;//乘积元素在Q中的列号
                            ctemp[ccol] +=M.triples[p].e*N.triples[q].e;
    
                        }
                    }//Q中第arow行元素已求出
                    for (ccol=1;ccol<=Q.nu;ccol++){ //设置Q中第arow的三元组
                        if (ctemp[ccol]!=0){ //如果不是零元
                            Q.tu++;
                            Triple triple = new Triple();
                            triple.i = arow;
                            triple.j = ccol;
                            triple.e = ctemp[ccol];
                            Q.triples[Q.tu] = triple;
                        }
                    }
                }
    
            }
            return Q;
        }
    
    }
    
    展开全文
  • 数据结构第五次作业-数组运算 数据结构第五次作业-----数组的运算 实验目的 掌握稀疏矩阵的压缩存储方法及主要运算的实现 实验内容与要求 设计一个稀疏矩阵计算器要求能够 输入并建立稀疏矩阵 输出稀疏矩阵 执行两个...
  • (1)以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个稀疏矩阵相加、相减、相乘、求逆以及矩阵转置和求矩阵对应行列式值的功能。 (2)稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的...
    1.设计内容
      稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算准备效率。实现一个能进行稀疏矩阵基本运算的运算器。
    具体功能有:
    (1)以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵,实现两个稀疏矩阵相加、相减、相乘、求逆以及矩阵转置和求矩阵对应行列式值的功能。
    (2)稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。
    2. 本设计所采用的数据结构
    稀疏矩阵采用带行逻辑链接信息的三元组顺序存储


    本设计最终代码实现如下(C语言):

    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<conio.h>
    #include<malloc.h>
    #include<string.h>
    #define MAXSIZE 100          /*假设非零元个数的最大值为100*/
    #define MAXMU 25              /*稀疏矩阵最大行列值为25*/
    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");
    		system("color 4f");
    		printf("\n 请输入矩阵!\n");
    		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");
        system("color 4f");
        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)   /*加法运算*/
    {
    	system("color 4f");
    	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)   /*减法运算*/
    {
    	system("color 4f");
    	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)   /*乘法运算*/
    {
    	system("color 4f");
    	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("color 4f"); 
    	system("title 稀疏矩阵运算器"); 
        system("cls");
    	system("mode con cols=70 lines=30");
        printf("\n");
        printf("\n            课程设计  ******班                      \n\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("              *             5:矩阵转置               *          \n");
        printf("              *             6:行列式值               *          \n");
    	printf("              *             7:选择退出               *          \n");
    	printf("              *                                      *          \n");
        printf("              ****************************************          \n");
        printf("                        请输入序号进行操作  :)                 \n");
        printf("                                 ");n=getchar();
    	 
        return n;
    }
    
    void zhuanzhi(TSMatrix A)   /*转置运算*/
    {
    	int p,q,m;
    	TSMatrix B;
    	B.mu=A.nu; /*将原矩阵的行列数及非零元个数赋给新矩阵*/
    	B.nu=A.mu;
    	B.tu=A.tu;
    	if(B.tu)
    	{
    		m=1;
    		for(p=1;p<=A.mu;p++)              /*将原非零元三元组的行列值交换后赋给新三元组,得到转置矩阵*/
    			for(q=1;q<=A.nu;q++)
    			{
    				B.data[m].i=A.data[m].j;
    				B.data[m].j=A.data[m].i;
    				B.data[m].v=A.data[m].v;
    				++m;
    			}
    	}
    	print(B);
    }
    
    int JsMatrix(int s[][MAXMU],int n) /*通过递归求矩阵对应行列式的值*/   
    {
    	int z,j,k,r,total=0;
    	int b[MAXMU][MAXMU];
    	if(n>2)
    	{
    		for(z=0;z<n;z++)
    			{for(j=0;j<n-1;j++)
    				for(k=0;k<n-1;k++)
    					if(k>=z) b[j][k]=s[j+1][k+1];
    					else b[j][k]=s[j+1][k];
    					if(z%2==0) r=s[0][z]*JsMatrix(b,n-1);
    					else r=(-1)*s[0][z]*JsMatrix(b,n-1);
    			total=total+r;
    			}
    	}
    	else if(n==2) total=s[0][0]*s[1][1]-s[0][1]*s[1][0];
    	return total;
    }
    
    void yuzishi(int s[][MAXMU],int b[][MAXMU],int n) /*求矩阵每个元素对应的余子式*/
    {
    	int z,j,k,m,l,g,a[MAXMU][MAXMU];
    	for(z=0;z<n;z++)
    	{
    		l=z;
    		for(j=0;j<n;j++)
    		{	
    			m=j;
    			for(k=0;k<n-1;k++)
    				for(g=0;g<n-1;g++)
    				{
    					if(g>=m&&k<l) a[k][g]=s[k][g+1];
    					else if(k>=l&&g<m)  a[k][g]=s[k+1][g];
    				    else if(k>=l&&g>=m) a[k][g]=s[k+1][g+1];
    				    else   a[k][g]=s[k][g];
    				}	
    			b[z][j]=JsMatrix(a,n-1);/*调用求行列式函数求出余子式*/
    		}
    	}
    }
    
    void qiuni(TSMatrix TM)   /*求逆运算*/
    {
    	system("color 4f");
    	int i,j,n,k;
    	n=TM.mu;
    	float temp;
    	int a[MAXMU][MAXMU];
    	int b[MAXMU][MAXMU];
    	float c[MAXMU][MAXMU];
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			a[i][j]=0;
    	for(i=1;i<=TM.tu;i++)
    		a[TM.data[i].i-1][TM.data[i].j-1]=TM.data[i].v;
    	k=JsMatrix(a,n); /*调用求行列式值的函数求出行列式的值*/
    	printf(" 矩阵的行列式的值为:|A|=%d\n",k);
    	if(k==0)
    		printf(" 行列式的值|A|=0,原矩阵无逆矩阵!");
    	else
    	{
    		yuzishi(a,b,n);
    
    		for(i=0;i<n;i++) /*由余子式得到代数余子式*/
    			for(j=0;j<n;j++)
    				if((i+j)%2!=0 && b[i][j]!=0) 
    					b[i][j]=-b[i][j];
    
    		for(i=0;i<n;i++) /*将代数余子式矩阵转置得到伴随矩阵*/
    			for(j=i+1;j<n;j++)
    			{
    				temp=b[i][j];
    				b[i][j]=b[j][i];
    				b[j][i]=temp;
    			}
    
    		printf(" 伴随矩阵A*为:\n");
    		for(i=0;i<n;i++) /*输出伴随矩阵*/
    		{
    			printf("\n");
    			for(j=0;j<n;j++)
    				printf("%6d",b[i][j]);
    			printf("\n");
    		}
    		for(i=0;i<n;i++)/*伴随矩阵除以行列式的值得到逆矩阵*/
    			for(j=0;j<n;j++)
    				c[i][j]=(float)b[i][j]/k;
    		printf(" 逆矩阵(A*)/|A|为:\n"); 
    		for(i=0;i<n;i++)/*输出逆矩阵*/
    		{
    			printf("\n");
    				for(j=0;j<n;j++)
    					printf("%1.1f\t",c[i][j]);		    
    			printf("\n");
    		}
    	}
    }
    void hlsz(TSMatrix TM)   /*求逆运算*/
    {
    	system("color 4f");
    	int i,j,n,k;
    	n=TM.mu;
    	float temp;
    	int a[MAXMU][MAXMU];
    	int b[MAXMU][MAXMU];
    	float c[MAXMU][MAXMU];
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			a[i][j]=0;
    	for(i=1;i<=TM.tu;i++)
    		a[TM.data[i].i-1][TM.data[i].j-1]=TM.data[i].v;
    	k=JsMatrix(a,n); /*调用求行列式值的函数求出行列式的值*/
    	printf("该稀疏矩阵对应行列式的值为%d",k);
    }
    void 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':creat(&A);
    		       qiuni(A);
    			   getch();
    			   break;
    	  case '5':creat(&A);
    		       zhuanzhi(A);
    			   getch();
    			   break;
    	  case '6':creat(&A);
    		       hlsz(A);
    			   getch();
    			   break;
          case '7':system("cls");
    			  system("color f2");
    			  printf("计算器已关闭,按任意键退出 :)\n");
    			  exit(0);
    	 }
    }
    



    转载于:https://www.cnblogs.com/youth-dream/p/7780202.html

    展开全文
  • 稀疏矩阵.zip

    2019-10-19 20:51:52
    稀疏矩阵计算器C++代码(中国石油大学《数据结构》课程设计),拥有稀疏矩阵加减乘及转置功能,所用软件为VC6.0++,打开可以直接用,计算器菜单可按照要求更改
  • 实验四 数组的运算

    2019-06-16 07:57:18
    设计一个稀疏矩阵计算器,要求能够:⑴输入并建立稀疏矩阵;⑵输出稀疏矩阵;⑶执行两个矩阵相加;⑷执行两个矩阵相乘;⑸求一个矩阵的转置矩阵;⑹(选做)求一个矩阵的逆矩阵。 这次上机代码不是我自己写的,就...
  • 稀疏矩阵运算器(c++)

    2009-06-22 21:09:47
    用c++语言编写的稀疏矩阵运算器(包括矩阵的加减乘法),并附课程设计报告.详细过程见原文.
  • 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间,提高计算准备效率。实现一个能进行稀疏矩阵基本运算的运算器,具体功能有:以“带行逻辑链接信息”的三元组顺序表示稀疏...
  • C++ QT 矩阵运算器

    2019-04-24 13:31:17
    C++ QT 矩阵运算器。 使用QT、C++开发的矩阵运算器,支持加减乘和转置(对左边矩阵进行转置),底层数据结构使用的是稀疏矩阵,用数组实现。 C++、QT
  • 数据结构课程设计----一元稀疏多项式计算器 用链表来实现多项式结构的加减乘法,求导,计算在x处的值
  • 数 据 结 构 课程设计报告 题 目 专 业 班 级 学 号 姓 名 指导老师 时 间 一课程设计题目及所涉及知识点 设计题目是矩阵的运算 所涉及的知识点主要是 1 利用数组的形式来储存数据在main函数里面实现对于数据的输入...
  • 数据结构课程设计-稀疏矩阵运算器,实现稀疏矩阵的加减乘除功能
  • 实现稀疏矩阵(采用三元组表示)的基本运算假设nxn的稀疏矩阵A采用三元组表示,设计一个程序exp4-2.cpp,完成如下功能。 (1)生成如下两个稀疏矩阵的三元组a和b a= 1 0 3 0 0 1 0 0 0 0 1 0 0 0 1 1 b= 3 0 0 0 0 4...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 539
精华内容 215
关键字:

稀疏矩阵计算器