数据结构课程设计(稀疏矩阵运算器)

计算机科学技术学院学生课程设计（论文）题目：学生姓名：学号：所在院(系)：专业：班级：指导教师：职称：年月日计算机科学技术学院本科学生课程设计任务书注：任务书由指导教师填写。

课程设计（论文）指导教师成绩评定表稀疏矩阵的操作1.课程设计的目的本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。

利用三元组实现稀疏矩阵的有关算法。

2．问题描述2.1稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。

2.2求出A的转置矩阵D，输出D。

3. 基本要求稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。

稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。

4.结构设计4.1.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。

4.2.稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。

4.3.首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

可设矩阵的行数和列数均不超过20。

4.4.程序可以对三元组的输入顺序加以限制，例如，按行优先。

注意研究教材的算法，以便提高计算效率。

5.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放5.算法思想5.1．主函数设置循环和选择语句进行运算循环和选择，进行稀疏矩阵的加法，减法，乘法，转置和是否继续运算5个分支开关进行运算选择。

5.2．设置函数分别实现稀疏矩阵的输入，输出，加法，减法，乘法。

5.3．在数组结构体中设置存放每行第一个非零元在其数组存储结构单元的位置的存储单元，若该行无非零元，则存为06.模块划分6.1typedef struct存放各行第一个非零元在存储数组中的位置，若该行无非零元，则其rpos[]值为零6.2 createsmatrix(rlsmatrix *M) 矩阵输入函数，输入各行非零元及其在矩阵中的行列数6.3 FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q) 矩阵快速转置6.4 HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩阵求和6.5 ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩阵求差6.6 JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) 矩阵求积7.算法实现7.1首先定义非零元个数的最大值和存放各行第一个非零元在存储数组中的位置#include<stdio.h>#define MAXSIZE 100 /* 非零元个数的最大值*/typedef struct triple{int i,j; /* 行下标,列下标*/int e; /* 非零元素值*/}triple;typedef struct tsmatrix{triple data[MAXSIZE+1]; /* 非零元三元组表,data[0]未用*/int mu,nu,tu; /* 矩阵的行数、列数和非零元个数*//* 各列第一个非零元的位置表rpos[0]未用*/}rlsmatrix;7.2创建稀疏矩阵矩阵的行数，列数，和非零元素的个数并按行序顺序输入第%d 个非零元素所在的行(1～%d),列(1～%d),元素值。

实习4、稀疏矩阵运算器一、需求分析1. 问题描述稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

2. 基本要求以带“行逻辑连接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘运算。

稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

3. 实现提示(1)首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。

可设聚矩阵的行数和列数不超过20。

(2)程序可以对三元组的输入顺序加以限制，例如，按行优先。

注意研究教科书5.3.2节中的算法，以便提高计算效率。

(3)在用三元组表示稀疏矩阵时，相加或者相减所得的结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。

二、概要设计ADT SparseMatrix{数据对象：D={a ij |i=1,2,3……m;j = 1,2,3……n;a i,j ∈intSet,m 和n 分别称为矩阵的行数和列数}数据关系：R ={ Row,col}Row ={<a i,j ,a i,j+1>|1≤i ≤m ，1≤j ≤n-1}Col = {< a i,j ,a i,j+1>|1≤i ≤m-1，1≤j ≤n}基本操作：CreateSMatrix(*T);操作结果：创建稀疏矩阵T 。

AddRLSMatrix(M,N,*Q);初始条件：稀疏矩阵M 和N 的行数列数对应相等。

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

SubRLSSMatrix(M,N,*Q);初始条件：稀疏矩阵M 和N 的行数列数对应相等。

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

SMatrixrpos(*T)初始条件：稀疏矩阵T 存在。

操作结果：求稀疏矩阵的各行第一个非零元的位置表。

MulTSMatrix(M,N,*Q);初始条件：稀疏矩阵M 的列数与N 的行数对应相等。

1.稀疏矩阵运算器数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：1、熟悉系统实现工具和上机环境。

2、根据课程设计任务，查阅相关资料。

3、针对所选课题完成以下工作：（1）需求分析（2）概要分析（3）详细设计（4）编写源程序（5）静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。

3.课程设计报告目录4.正文（1）问题描述稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算频率。

实现一个能进行稀疏矩阵基本运算的运算器。

（2）需求分析本课程设计的稀疏矩阵运算器在visual studio 2013下运行调试成功，可以实现的功能有：1.矩阵运算方式选择2.根据提示输入相应数据3.显示最终结果使用的主要存储结构为三元组，并用三元组形式进行运算。

所有参与运算数据类型为整形，因此输入的数据应为整形数据。

为了节省存储空间使用三元组数据进行运算，可以通过多次扫描三元组数据来实现，即使用嵌套循环函数。

输出结果为通常的阵列形式，因此使用了右对齐，保证输出形式的整齐。

（3）概要分析本次课程设计中定义的结构体typedef struct {int i, j;//矩阵元素所在行列int v;//元素的值}triple;typedef struct {triple data[MAXSIZE];triple cop[MAXSIZE];//辅助数组int m, n, t;//矩阵的行列数}tripletable;Main函数调用子函数时输入1为调用int Push_juzhen(int m, int n, int count)函数，可以实现矩阵相加功能输入2为调用int Dec_juzhen(int m, int n, int count)函数，可实现矩阵相减功能输入3为调用int Mul_juzhen()函数，可以实现矩阵相乘功能（4）详细分析（流程图伪代码）加法函数int Push_juzhen(int m, int n, int count)//矩阵相加（行，列，矩阵数）{// p行，q列，s非零元素个数，v元素值//ucount对数组下标计数的变量，与变量x实现多个矩阵相加for (int c = 0; c < count; c++){int x = 0;cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl;cin >> s;cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl;for (; x< s; x++)//传递行列及元素值{cin >> p >> q >> v;a.cop[x].i = p;//将p赋值给data[x].ia.cop[x].j = q;//将q赋值给data[x].ja.cop[x].v = v;//将v赋值给data[x].v}//g行//h列for (int g = 1; g <= m;g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++)//对辅助存储中的三元组进行行逻辑排序，将数据存入a.data{if (a.cop[l].i == g&&a.cop[l].j == h){a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v = a.cop[l].v;u++;}}}}//矩阵相加//k为行数//h为列数for (int k = 0; k < u; k++){for (int h = 0; h <= ucount; h++){if (a.data[k].i == b.data[h].i&&a.data[k].j == b.data[h].j)//判断行列是否相等b.data[h].v += a.data[k].v;else{b.data[ucount].i = a.data[k].i;b.data[ucount].j = a.data[k].j;b.data[ucount].v = a.data[k].v;ucount++;//存储空间增加计数}break;//增加一组数据时跳出循环，避免重复计算}}return 0;}相减函数int Dec_juzhen(int m, int n, int count){for (int c = 0; c < count; c++){int x = 0;cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl;cin >> s;cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl;for (; x< s; x++)//传递行列及元素值{cin >> p >> q >> v;a.cop[x].i = p;//将p赋值给data[x].ia.cop[x].j = q;//将q赋值给data[x].ja.cop[x].v = v;//将v赋值给data[x].v}//g行//h列if (c != 0){for (int g = 1; g <= m; g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++)//行逻辑排列{if (a.cop[l].i == g&&a.cop[l].j == h){ a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v =- a.cop[l].v;//c>0时为减数矩阵u++;}}}}else{for (int g = 1; g <= m; g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++){if (a.cop[l].i == g&&a.cop[l].j == h){a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v = a.cop[l].v;u++;}}}}}//矩阵减法计算for (int k = 0; k < u; k++){for (int h = 0; h <= ucount; h++){if (a.data[k].i == b.data[h].i&&a.data[k].j == b.data[h].j)//判断行列相等b.data[h].v += a.data[k].v;else{b.data[ucount].i = a.data[k].i;b.data[ucount].j = a.data[k].j;b.data[ucount].v = a.data[k].v;ucount++;}break;}}return 0;}相乘函数int Mul_juzhen(){cout << "请输入第一个矩阵的行列数" << endl;cin >> m >> n;cout << "请输入第一个矩阵的非零元素个数" << endl;cin >> t1;a.m = m;a.n = n;a.t = t1;cout << "请输入第一个矩阵的非零元素所在的行、列、数值并以空格间隔" << endl;for (i=0; i < t1; i++){cin >> p >> q >> v;a.data[i].i = p;//将p赋值给data[x].ia.data[i].j = q;//将q赋值给data[x].ja.data[i].v = v;//将v赋值给data[x].v}cout << "则第二个矩阵的行数为" << a.n << "行" << endl<<endl;cout << "请输入第二个矩阵的列数" << endl;cin >> n;cout << "请输入第二个矩阵的非零元素个数" << endl;cin >> t2;b.m = a.n;b.n = n;b.t = t2;cout << "请输入第二个矩阵的非零元素所在的行、列、数值并以空格间隔" << endl;for (i = 0; i < t2; i++){cin >> p >> q >> v;b.data[i].i = p;//将p赋值给data[x].ib.data[i].j = q;//将q赋值给data[x].jb.data[i].v = v;//将v赋值给data[x].v}i = 0;//i为a、b数组标记，另设k为矩阵相乘元素扫描标记//n为检测相加元素扫描标记，z为存储标记while (i < a.t){int k;for (k = 0; k < b.t; k++){if (a.data[i].j == b.data[k].i)if (i>0){for (n = 0; n < z; n++){if (a.data[i].i == c.data[n].i&&b.data[k].j == c.data[n].j)//判断是否符合相加条件c.data[n].v += a.data[i].v*b.data[k].v;else{c.data[z].i = a.data[i].i;c.data[z].j = b.data[k].j;c.data[z].v = a.data[i].v*b.data[k].v;z++;}}}else{c.data[z].i = a.data[i].i;c.data[z].j= b.data[k].j;c.data[z].v = a.data[i].v*b.data[k].v;z++;}}i++;}return 0;}（5）调试分析（遇到的问题，修改，解决办法，时空复杂度）刚开始，程序仅使用三元组存储，计算过程使用了二维数组，但矩阵相乘会出现错误，矩阵乘法时间复杂度为矩阵一的行数乘以矩阵二的列数（m1*n2）。

数据结构----稀疏矩阵运算器课程设计目录稀疏矩阵运算器设计............................................................................................ I摘要................................................................................................................ ... II第一章需求分析 (1)第二章概要设计 (2)第三章设计步骤 (6)3.1 函数说明 (6)3.2 设计步骤 (7)第四章设计理论分析方法 (20)4.1 算法一：矩阵转置.....................................................................204.2 算法二：矩阵加法.....................................................................204.3 算法三：矩阵乘法 (21)第五章程序调试 (23)第六章心得体会 (25)参考文献 (26)第一章需求分析1．稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

2．以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。

稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。

3．演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。

4．由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

5．程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。

数据结构课程设计说明书题目: 稀疏矩阵的运算院系：计算机科学与工程学院专业班级：计算机10-**班学号： 201030****学生姓名： ******指导教师： ******2011年 12 月 28 日安徽理工大学课程设计（论文）任务书计算机科学与工程学院2011年 11 月 8 日安徽理工大学课程设计（论文）成绩评定表目录1 问题描述 (1)2 需求分析 (1)3 总体设计 (2)3.1 Matrix结构的定义 (2)3.2 系统流程图 (3)4 详细设计 (4)4.1 “菜单”界面 (4)4.2 建立矩阵 (4)4.3 显示矩阵 (6)4.4 矩阵的转置 (7)4.5 矩阵的加法运算 (8)4.6 矩阵的减法运算 (9)4.7 矩阵的乘法运算 (9)5 程序运行 (11)5.1 输入矩阵 (11)5.2 矩阵转置 (11)5.3 矩阵加法 (12)5.4 矩阵减法 (12)5.5 矩阵乘法 (12)5.6 退出及错误提示 (13)6 总结 (13)参考文献 (14)1 问题描述(1)题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以及转置操作。

(2)基本要求：①存储结构选择三元组存储方式；②实现一个稀疏矩阵的转置运算；③实现两个稀疏矩阵的加法运算；④实现两个稀疏矩阵的减法运算；⑤实现两个稀疏矩阵的乘法运算。

(3)设计目的：通过本次课程设计，了解稀疏矩阵的一些基本运算操作，并通过相关的程序代码实现。

2 需求分析经过本次的课程设计，我认为稀疏矩阵运算系统主要实现的功能如下：(1)建立矩阵：只有先建立了矩阵，才能够对矩阵进行运算操作，包括建立矩阵A和矩阵B；(2)转置运算操作：对矩阵A或者矩阵B进行转置运算，输出相应的转置矩阵；(3)四则运算操作：该步骤由两个矩阵同时参与，对其进行加法运算(A+B)、减法运算(A-B)以及乘法运算(A*B和B*A)；(4)退出：当做完矩阵的运算操作之后，就可以点击它退出该界面。

稀疏矩阵运算器一．实验目的使读者能深入研究数组的存储表示和实现技术二．实验内容【问题描述】稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

【基本要求】以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。

稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的陈列形式列出。

【实现提示】1、首先应先输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求做的运算是否相匹配，可设矩阵的行数和列数不超过20；2、程序可以对三元组的输入顺序加以限制，例如，按行优先。

3、在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。

三．实验步骤（可选）#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;#define MAXSIZE 100#define MAXROW 100#define OK 1#define ERROR -1typedef struct{int row; //行数int col; //列数int v; //非零元素值}triplenode;typedef struct{triplenode data[MAXSIZE+1]; //非零元三元组int rowtab[MAXROW+1];//各行第一个非零元的位置表int mu,nu,tu; //矩阵的行数、列数和非零元个数}rtripletable;void creat(rtripletable &A){ //创建稀疏矩阵int k=1,sum=1,loop,p,t;int num[MAXROW+1];cout<<"请输入矩阵的行数和列数:"<<endl;cout<<"行数:";cin>>A.mu;cout<<"列数:";cin>>A.nu;cout<<"非零元素个数:";cin>>A.tu;cout<<"请输入该矩阵的非零元:格式行+列+值.(ps:以输入全零为结束标记!）"<<endl;for(loop=1;loop<=A.tu;loop++){//输入三元组的行数，列数和非零元素值cin>>A.data[loop].row;cin>>A.data[loop].col;cin>>A.data[loop].v;}for(p=1;p<=A.mu;p++) num[p]=0;//A三元组每一列的非零元素个数for(t=1;t<=A.tu;t++) ++num[A.data[t].row];//求A中每一列含非零元个数A.rowtab[1]=1;//求第p列中第一个非零元在A.data中的序号for(t=2;t<=A.mu;t++) A.rowtab[t]=A.rowtab[t-1]+num[t-1];return;}void print(rtripletable A){ //输出稀疏矩阵int result[MAXROW+1][MAXROW+1];//定义一个二维数组int i,j;for(i=1;i<=A.mu;i++)for(j=1;j<=A.nu;j++)result[i][j]=0; //初始化为0for(i=1;i<=A.tu;i++)result[A.data[i].row][A.data[i].col]=A.data[i].v;for(i=1;i<=A.mu;i++){//输出所做运算的结果for(j=1;j<=A.nu;j++)cout<<result[i][j]<<"\t";cout<<endl;}}int addsmatrix(rtripletable M, rtripletable N){//矩阵相加if(M.mu!=N.mu) //行数相等才能相加cout<<"ERROR";rtripletable Q;Q.mu=M.mu;Q.nu=N.nu;int p,q,k;p=1;q=1;k=1;while(p<=M.tu&&q<=N.tu){//两个稀疏矩阵存在if(M.data[p].row==N.data[q].row){//两个稀疏矩阵的行数相等if(M.data[p].col==N.data[q].col){//两个稀疏矩阵的列数相等if(M.data[p].v+N.data[q].v!=0){//两个稀疏矩阵相加的结果不为0Q.data[k].row=M.data[p].row;Q.data[k].col=M.data[p].col;Q.data[k].v=M.data[p].v+N.data[q].v;++k;}++q;++p;}else if(M.data[p].col<N.data[q].col){//第一个稀疏矩阵列数小于第二个稀疏矩阵列数Q.data[k]=M.data[p];//把M中的所有信息都赋给Q++p;++k;}else{ //第一个稀疏矩阵列数大于第二个稀疏矩阵的列数Q.data[k]=N.data[q];++q;++k;}}else if(M.data[p].row<N.data[q].row){ //第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.data[k]=M.data[p];++p;++k;}else{ //第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.data[k]=N.data[q];++q;++k;}}while(p<=M.tu){ //只有M并且符合条件Q.data[k]=M.data[p];++p;++k;}while(q<=N.tu){ //只有N并且符合条件Q.data[k]=N.data[q];++q;++k;}Q.tu=k-1;cout<<"矩阵相加结果是:"<<endl;print(Q); //调用print()return OK;}int subsmatrix(rtripletable M, rtripletable N){ //稀疏矩阵相减if(M.mu!=N.mu) //行数相等才能相加cout<<"出错";rtripletable Q;Q.mu=M.mu;Q.nu=N.nu;int p,q,k;p=1;q=1;k=1;while(p<=M.tu&&q<=N.tu){ //两个稀疏矩阵存在if(M.data[p].row==N.data[q].row){ //两个稀疏矩阵的行数相等if(M.data[p].col==N.data[q].col){ //两个稀疏矩阵的列数相等if(M.data[p].v-N.data[q].v!=0){ //两个稀疏矩阵相减的结果不为0Q.data[k].row=M.data[p].row;Q.data[k].col=M.data[p].col;Q.data[k].v=M.data[p].v-N.data[q].v;++k;}++q;++p;}if(M.data[p].col<N.data[q].col){ //第一个稀疏矩阵列数小于第二个稀疏矩阵的列数Q.data[k]=M.data[p];++p;++k;}if(M.data[p].col>N.data[q].col){ //第一个稀疏矩阵列数大于第二个稀疏矩阵的列Q.data[k].row=N.data[q].row;Q.data[k].col=N.data[q].col;Q.data[k].v=-N.data[q].v;++q;++k;}}if(M.data[p].row<N.data[q].row){//第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.data[k]=M.data[p];++p;++k;}if(M.data[p].row>N.data[q].row){//第一个稀疏矩阵行列数大于第二个稀疏矩阵行数Q.data[k].row=N.data[q].row;Q.data[k].col=N.data[q].col;Q.data[k].v=-N.data[q].v;++q;++k;}}while(p<=M.tu){//只有M并且符合条件Q.data[k]=M.data[p];++p;++k;}while(q<=N.tu){//只有N并且符合条件Q.data[k].row=N.data[q].row;Q.data[k].col=N.data[q].col;Q.data[k].v=-N.data[q].v;++q;++k;}Q.tu=k-1;cout<<"矩阵相减结果为:"<<endl;print(Q); //调用print()return OK;}void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q){//稀疏矩阵相乘int arow,brow;int p,q,tp,t;int ccol;int ctemp[MAXROW+1]; //定义累加器if(M.nu!=N.mu)return;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(p=1;p<=Q.nu;p++) //处理M的每一列ctemp[p]=0; //当前行各元素累加器清零Q.rowtab[arow]=Q.tu+1;if(arow<M.mu) tp=M.rowtab[arow+1];else tp=M.tu+1;for(p=M.rowtab[arow];p<tp;++p){//对当前行中每一个非零元brow=M.data[p].col; //找到对应元N中的行号if(brow<N.nu) t=N.rowtab[brow+1];else t=N.tu+1;for(q=N.rowtab[brow];q<t;++q){ccol=N.data[q].col; //乘积元素在Q中列数ctemp[ccol]+=M.data[p].v*N.data[q].v;}} //求得Q中第crow(=arow)行的非零元for(ccol=1;ccol<=Q.nu;ccol++){//压缩存储该行非零元if(ctemp[ccol]){if(++Q.tu>MAXSIZE)return ;Q.data[Q.tu].row=arow; //行数Q.data[Q.tu].col=ccol; //列数Q.data[Q.tu].v=ctemp[ccol];}}}}//累加非零元素值cout<<"乘法结果为:"<<endl;print(Q);} //调用print()void main(){char choice;rtripletable A,B,Q;cout<<"**********************************"<<endl;cout<<"*****欢迎使用稀疏矩阵运算器******"<<endl;cout<<"**********************************"<<endl;cout<<"A、输入矩阵1"<<"\t";cout<<"B、输入矩阵2"<<"\t";cout<<"C、矩阵相加"<<endl;cout<<"D、矩阵相减"<<"\t";cout<<"E、矩阵相乘"<<"\t";cout<<"F、退出本系统"<<endl;cout<<"请选择所需要的操作功能(A，B，C，D，E，F):";do{cin>>choice;switch(choice){case'A':creat(A);break;case'B':creat(B);break;case'C':addsmatrix(A,B);break;case'D':subsmatrix(A,B);break;case'E':multsmatrix(A,B,Q);break;case'F':exit(0);}cout<<"请选择所需要的操作功能(A，B，C，D，E，F):";}while(1);} 四．实验的结果及分析。

数据结构——稀疏矩阵运算器数据结构——稀疏矩阵运算器---简介稀疏矩阵是一种具有很多零元素的矩阵，通常用于表示大规模数据中的稀疏性。

由于稀疏矩阵中大部分元素为零，传统的矩阵运算会浪费大量的时间和空间。

为了解决这个问题，稀疏矩阵运算器应运而生。

本文将介绍稀疏矩阵运算器的数据结构和实现方式，并演示其在稀疏矩阵加法和乘法运算中的应用。

数据结构稀疏矩阵运算器主要使用三元组存储稀疏矩阵的非零元素。

三元组由行、列和元素值组成，其中行和列表示非零元素的位置，元素值表示非零元素的值。

对于一个m行n列的稀疏矩阵，若其中k 个元素非零，则使用k个三元组来存储。

以一个3x3的稀疏矩阵为例，假设四个非零元素分别为2、4、6和8，其位置分别为(0, 0)、(1, 1)、(1, 2)和(2, 0)，则对应的三元组表示为：```(0, 0, 2)(1, 1, 4)(1, 2, 6)(2, 0, 8)```三元组存储结构可以使用数组来实现。

数组的每个元素表示一个三元组，通过遍历数组可以访问稀疏矩阵中的所有非零元素。

稀疏矩阵加法运算稀疏矩阵加法运算的基本思想是将两个稀疏矩阵的非零元素进行合并。

具体步骤如下：1. 创建一个新的稀疏矩阵，其行数和列数与两个被加数矩阵相同。

2. 初始化一个空的三元组数组来存储结果矩阵的非零元素。

3. 通过遍历两个被加数矩阵的三元组数组，比较行和列是否相等：- 若行和列相等，则将两个非零元素相加，并将结果添加到结果矩阵的三元组数组中。

- 若行和列不相等，则分别将两个非零元素添加到结果矩阵的三元组数组中。

4. 返回结果稀疏矩阵。

稀疏矩阵乘法运算稀疏矩阵乘法运算的基本思想是利用稀疏矩阵的特性进行优化。

具体步骤如下：1. 创建一个新的稀疏矩阵，其行数和列数分别与被乘数的行数和乘数的列数相同。

2. 初始化一个空的三元组数组来存储结果矩阵的非零元素。

3. 遍历被乘数的三元组数组，对于每个被乘数的非零元素，遍历乘数的三元组数组，找出所有与被乘数的列相等的乘数元素，并将它们的乘积添加到结果矩阵的三元组数组中。

数据结构课程设计之稀疏矩阵运算器#include#include#define maxsize 200typedef struct{int i,j;//i为非零元素在行，j为非零元所在列int e;//非零元}Tripe;typedef struct{Tripe data[maxsize];int h,l,total;//稀疏矩阵的行数列数及非零元个数}TSMatrix;void Creat(TSMatrix &M){//创建一个稀疏矩阵int a,b,c,x;scanf("%d,%d,%d",&M.h,&M.l,&M.total);for(x=1;x<=M.total;x++){printf("请输入第%d个稀疏矩阵的非零元素所在的行数列数用逗号隔开输完按回车键:\",x);scanf("%d,%d,%d",&a,&b,&c);M.data[x].i=a;M.data[x].j=b;M.data[x].e=c;}}void Print(TSMatrix &S){//输出稀疏矩阵int x;int c,b,a[maxsize][maxsize];for(c=1;c<=S.h;c++)for(b=1;b<=S.l;b++)a[c][b]=0;//全部初始化为零for(x=1;x<=S.total;x++){a[S.data[x].i][S.data[x].j]+=S.data[x].e;//在矩阵的相应位置附上非零元素}for(c=1;c<=S.h;c++)for(b=1;b<=S.l;b++){printf("%4d",a[c][b]);if(b==S.l)printf("\");}}void Add(TSMatrix T,TSMatrix V,TSMatrix &M){//加法运算int p=1,q=1;int b=1;if(T.h!=V.h||T.l!=V.l){printf("两矩阵行数或列数不同无法进行相加:\"); exit(0);}while(p<=T.total&&q<=V.total){if(T.data[p].i==V.data[q].i){if(T.data[p].j==V.data[q].j){M.data[b].i=T.data[p].i;M.data[b].e=T.data[p].e+V.data[q].e; p++;b++;q++;}else if(T.data[p].j<v.data[q].j)< p=""> {M.data[b].i=T.data[p].i;M.data[b].j=T.data[p].j;M.data[b].e=T.data[p].e;b++;p++;}else if(T.data[p].j>V.data[q].j){M.data[b].i=V.data[q].i;M.data[b].j=V.data[q].j;M.data[b].e=V.data[q].e;b++;q++;}}else if(T.data[p].i<v.data[q].i)< p=""> {M.data[b].i=T.data[p].i;M.data[b].j=T.data[p].j;M.data[b].e=T.data[p].e;b++;p++;}else if(T.data[p].i>V.data[q].i){M.data[b].i=V.data[q].i;M.data[b].j=V.data[q].j;b++;q++;}}//下面两个循环是把上面循环中未处理的数据添加到M中while(p<=T.total){M.data[b].i=T.data[p].i;M.data[b].j=T.data[p].j;M.data[b].e=T.data[p].e;b++;p++;}while(q<=V.total){M.data[b].i=V.data[q].i;M.data[b].j=V.data[q].j;M.data[b].e=V.data[q].e;b++;q++;}M.h=T.h;M.l=T.l;M.total=b-1; //b最后要减一，因为上面处理最后一个数时b也增加1了}void TransposTSMtrix(TSMatrix A,TSMatrix &B) //完成矩阵的转置，一次快速定位法{int j,t,p,q;int num[maxsize],position[maxsize];//num矩阵某列非零元个数，positionB.h=A.l;B.l=A.h;B.total=A.total;if(B.total){for(j=1;j<=A.l;j++)num[j]=0;for(t=1;t<=A.total;t++)num[A.data[t].j]++;position[1]=1;for(j=2;j<=A.l;j++)position[j]=position[j-1]+num[j-1];for(p=1;p<=A.total;p++){j=A.data[p].j;q=position[j];B.data[q].i=A.data[p].j;B.data[q].j=A.data[p].i;B.data[q].e=A.data[p].e;position[j]++;}}}void Jiansmatrix(TSMatrix M,TSMatrix N,TSMatrix &T){ int m=1,n=1,t=1;if(M.h!=N.h||M.l!=N.l){printf("两矩阵行数或列数不同无法进行相减");exit(0);} T.h=M.h;T.l=M.l;while(m<=M.total&&n<=N.total){{if(M.data[m].i==N.data[n].i)if(M.data[m].j==N.data[n].j){if(M.data[m].e==N.data[n].e){T.data[t].i=M.data[m].i;T.data[t].j=M.data[m].j;m++;n++;}else{T.data[t].e=M.data[m].e-N.data[n].e; T.data[t].i=M.data[m].i;T.data[t].j=M.data[m].j;t++;m++;n++;}}else if(M.data[m].j<n.data[n].j)< p=""> {T.data[t].e=M.data[m].e;T.data[t].i=M.data[m].i;T.data[t].j=M.data[m].j;t++;m++;}else if(M.data[m].j>N.data[n].j){T.data[t].e=0-N.data[n].e;T.data[t].i=N.data[n].i;T.data[t].j=N.data[n].j;t++;n++;}else{if(M.data[m].i<n.data[n].i)< p=""> {T.data[t].i=M.data[m].i;T.data[t].j=M.data[m].j;T.data[t].e=M.data[m].e;t++;m++;}else {T.data[t].e=0-N.data[n].e;T.data[t].i=N.data[n].i;T.data[t].j=N.data[n].j;t++;n++;}}}}while(M.total==(m-1)&&n<=N.total) {T.data[t].i=N.data[n].i;T.data[t].j=N.data[n].j;T.data[t].e=N.data[n].e;t++;n++;}while(N.total==(n-1)&&m<=M.total) {T.data[t].i=M.data[m].i;T.data[t].j=M.data[m].j;T.data[t].e=M.data[m].e;t++;m++;}T.total=t-1;}void Multsmatrix(TSMatrix M,TSMatrix N,TSMatrix &T) { int p,q,Qn=0;int a[200][200];if(M.l!=N.h){printf("两矩阵无法相乘");exit(0);}T.h=M.h;T.l=N.l;for(p=1;p<=M.h;p++)for(q=1;q<=N.l;q++)a[p][q]=0;for(p=1;p<=M.total;p++)for(q=1;q<=N.total;q++)if(M.data[p].j==N.data[q].i){a[M.data[p].i][N.data[q].j]+=M.data[p].e*N.data[q].e;}for(p=1;p<=M.h;p++)for(q=1;q<=N.l;q++)if(a[p][q]!=0){Qn++;T.data[Qn].e=a[p][q];T.data[Qn].i=p;T.data[Qn].j=q;}T.total=Qn;}void main(){TSMatrix ts1,ts2,ts3;int choice;do{printf("1.矩阵的转置!\");printf("2.两个矩阵相加!\");printf("3.两个矩阵相减!\");printf("4.两个矩阵相乘!\");printf("5.退出程序!\");printf("请输入您的选择:\");scanf("%d",&choice);switch(choice){case 1:printf("请输入矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts1);Print(ts1);TransposTSMtrix(ts1,ts2);printf("转置后的矩阵为:\");Print(ts2);break;case 2:printf("请输入第一个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts1);printf("第一个矩阵为:\");Print(ts1);printf("请输入第二个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts2);printf("第二个矩阵为:\");Print(ts2);Add(ts1,ts2,ts3);printf("以上两个矩阵相加后为:\");Print(ts3);break;case 3:printf("请输入第一个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts1);printf("第一个矩阵为:\");Print(ts1);printf("请输入第二个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts2);printf("第二个矩阵为:\");Print(ts2);Jiansmatrix(ts1,ts2,ts3);printf("以上两个矩阵相减后为:\");Print(ts3);break;case 4:printf("请输入第一个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts1);printf("第一个矩阵为:\");Print(ts1);printf("请输入第二个矩阵的行和列及非零元个数用逗号隔开:\"); Creat(ts2);printf("第二个矩阵为:\");Print(ts2);Multsmatrix(ts1,ts2,ts3);printf("以上两个矩阵相乘后为:\");Print(ts3);break;case 5:exit(0);break;}}while(choice!=0); scanf("%d",&choice); }</n.data[n].i)<></n.data[n].j)<></v.data[q].i)<></v.data[q].j)<>。

数据结构稀疏矩阵运算器引言：稀疏矩阵是指在一个二维矩阵中，绝大多数元素为0或者没有意义的元素。

与之相对，稠密矩阵则是指大部分元素都有意义且不为0的矩阵。

稀疏矩阵在很多实际问题中经常出现，例如图论、网络分析、自然语言处理等领域。

为了高效地处理稀疏矩阵的运算，我们可以使用稀疏矩阵运算器。

一、稀疏矩阵的表示方法对于一个m×n的稀疏矩阵，我们可以使用三元组(Triplet)的方式进行表示。

三元组表示法包括三个数组：行数组row、列数组col 和值数组value。

其中，row[i]和col[i]分别表示第i个非零元素的行和列，value[i]表示第i个非零元素的值。

通过这种方式，我们可以用较少的空间来表示一个稀疏矩阵，从而提高运算效率。

二、稀疏矩阵的加法运算稀疏矩阵的加法运算可以通过遍历两个稀疏矩阵的非零元素，并将相同位置的元素相加得到结果。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数和列数与原始稀疏矩阵相同。

2. 遍历两个稀疏矩阵的非零元素，将相同位置的元素相加，并将结果存储在result中。

3. 返回result作为加法运算的结果。

三、稀疏矩阵的乘法运算稀疏矩阵的乘法运算可以通过矩阵的数学定义来实现。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数等于第一个稀疏矩阵的行数，列数等于第二个稀疏矩阵的列数。

2. 遍历第一个稀疏矩阵的每个非零元素，将其与第二个稀疏矩阵相应位置的元素相乘，并将结果累加到result中。

3. 返回result作为乘法运算的结果。

四、稀疏矩阵的转置运算稀疏矩阵的转置运算可以通过交换行数组row和列数组col来实现。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数等于原始稀疏矩阵的列数，列数等于原始稀疏矩阵的行数。

2. 将原始稀疏矩阵的行数组row赋值给result的列数组col，将原始稀疏矩阵的列数组col赋值给result的行数组row。

教学单位计算机科学与技术学生学号************数据结构课程设计报告书题目稀疏矩阵运算器学生姓名秦豹专业名称软件工程指导教师李志敏实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。

需要分析：稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。

输入以三元组表示，输出以通常的阵列形式列出。

软件平台：Windows 2000，Visual C＋＋6.0或WINTC概要设计：ADT Array {数据对象:D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}数据关系:R = { ROW, COL }ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1}COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤j≤b2-2}基本操作：CreateSMatrix(&M); //操作结果:创建稀疏矩阵M.Print SMatrix(M);//初始化条件: 稀疏矩阵M存在.//操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M的列数等于N的行数.//操作结果:求稀疏矩阵的乘积Q=M*N.} ADT Array调试测试：初始界面矩阵的加法矩阵的减法矩阵的转置矩阵的乘法程序源码：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAXSIZE 40 //假设非零元素个数的最大值为40#define MAXRC 20 //假设矩阵的最大行数为20typedef int ElemType;typedef struct{int i,j; //非零元的行下标和列下标ElemType e; //非零元的值}Triple;typedef struct{Triple data[MAXSIZE+1];int rpos[MAXRC+1]; //各行第一个非零元在三元组的位置表int hs,ls,fls;}TSMatrix,*Matrix;void Creat(TSMatrix &M){int i,k;for(i=1;i<=MAXRC+1;i++)M.rpos[i]=0;printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");scanf("%d %d %d",&M.hs,&M.ls,&M.fls);for(i=1;i<=M.fls;i++){printf("请用三元组形式输入矩阵的元素(行列非零元素):");scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);}for(i=1,k=1;i<=M.hs;i++){M.rpos[i]=k;while(M.data[k].i<=i && k<=M.fls)k++;}}void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n){int a,b,temp,l;C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a<=A.fls && b<=B.fls){if(A.data[a].i==B.data[b].i){if(A.data[a].j<B.data[b].j)C.data[l++]=A.data[a++];else if(A.data[a].j>B.data[b].j){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}else{temp=A.data[a].e+n*B.data[b].e;if(temp){C.data[l]=A.data[a];C.data[l].e=temp;l++;}a++;b++;}}else if(A.data[a].i<B.data[b].i)C.data[l++]=A.data[a++];else {C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;} }while(a<=A.fls)C.data[l++]=A.data[a++];while(b<=B.fls){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}C.fls=l-1;}int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q){int arow,brow,ccol,tp,p,q,t;int ctemp[MAXRC+1];if(A.ls!=B.hs) return 0;Q.hs=A.hs;Q.ls=B.ls;Q.fls=0;if(A.fls*B.fls){for(arow=1;arow<=A.hs;arow++){for(ccol=1;ccol<=Q.ls;ccol++)ctemp[ccol]=0;Q.rpos[arow]=Q.fls+1;if(arow<A.hs) tp=A.rpos[arow+1];else tp=A.fls+1;for(p=A.rpos[arow];p<tp;p++){brow=A.data[p].j;if(brow<B.hs) t=B.rpos[brow+1];else t=B.fls+1;for(q=B.rpos[brow];q<t;q++){ccol=B.data[q].j;ctemp[ccol]+=A.data[p].e*B.data[q].e;}}for(ccol=1;ccol<=Q.ls;ccol++){if(ctemp[ccol]){if(++Q.fls>MAXSIZE) return 0;Q.data[Q.fls].i=arow;Q.data[Q.fls].j=ccol;Q.data[Q.fls].e=ctemp[ccol];}}}}return 1;}void Print_SMatrix(TSMatrix M){int k,l,n;Matrix p;p=&M;for(k=1,n=1;k<=p->hs;k++){for(l=1;l<=p->ls;l++){if(p->data[n].i==k && p->data[n].j==l){printf("%5d",p->data[n].e);n++;}elseprintf("%5d",0);}printf("\n");}printf("\n");}void Zhuanzhi(TSMatrix *a,TSMatrix *b){int q,col,p;b->hs=a->ls;b->ls=a->hs;b->fls=a->fls;if(b->fls){q=1;for(col=1;col<=a->ls;col++)for(p=1;p<=a->fls;p++)if(a->data[p].j==col){b->data[q].i=a->data[p].j;b->data[q].j=a->data[p].i;b->data[q].e=a->data[p].e;++q;}}}void Destory_SMatrix(TSMatrix &M){M.hs=M.ls=M.fls=0;}void main(){TSMatrix A,B,C;TSMatrix *p=&A,*q=&B;int flag,n;while(1){system("cls");printf("\n\n\n");printf("\t┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("\t┃*** 稀疏矩阵的加、减、转、乘*** ┃\n");printf("\t┣━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");printf("\t┃1、稀疏矩阵的加法┃\n");printf("\t┃2、稀疏矩阵的减法┃\n");printf("\t┃3、稀疏矩阵的转置┃\n");printf("\t┃4、稀疏矩阵的乘法┃\n");printf("\t┃5、退出该应用程序┃\n");printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf("输入要进行的项目的编号:");scanf("%d",&flag);if(flag==5) break;Creat(A);printf("矩阵A:\n"); Print_SMatrix(A);switch(flag){case 1: Creat(B);n=1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A+B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 2: Creat(B);n=-1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A-B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 3: printf("A->B:\n");Zhuanzhi(p,q);Print_SMatrix(B);break;case 4: Creat(B);printf("矩阵B:\n");Print_SMatrix(B);printf("A*B:\n");n=Xiangcheng(A,B,C);if(!n) printf("错误!行列不匹配\n");else Print_SMatrix(C);break;default: printf("输入错误!\n");}Destory_SMatrix(A);Destory_SMatrix(B);Destory_SMatrix(C);getchar();getchar();}printf("\n\t\t\t ***程序已经退出***\n");getchar();}小结：。