数据结构----稀疏矩阵运算器课程设计目录稀疏矩阵运算器设计............................................................................................ 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．程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。
6．在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。
7．程序在VC6.0环境下设计。
程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出的工作。
第二章概要设计1．抽象数据类型稀疏矩阵的定义如下：ADT SparseMatrix{数据对象：D={a|i=1,2,…,m; j=1,2,…,n;ij a∈ElemSet, m和n分别为矩阵的行数和列ij数} 数据关系：R={Row,Col }Row={﹤a, a﹥| 1≤i≤m, 1≤j≤n-1} i,j+1i,jCol = {﹤a, a﹥| 1≤i≤m-1, 1≤j≤n} i+1,ji,j基本操作：create(TSMatrix &TM)操作结果：创建稀疏矩阵矩阵TMLocateELem(TSMatrix M,int i,int j,int e)初始条件：稀疏矩阵M存在操作结果：稀疏矩阵中是否存在非零元素A[i][j]，若存在返回edisp(TSMatrix TM)初始条件：稀疏矩阵TM存在操作结果：通常形式输出稀疏矩阵InsertSortMatrix(TSMatrix &TM)存在TM初始条件：稀疏矩阵操作结果：根据对矩阵的行列，三元组TM作直接插入排序TransposeSMatrix(TSMatrix M,TSMatrix &T)初始条件：稀疏矩阵M和T存在操作结果：求稀疏矩阵M转置的稀疏矩阵TAddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)初始条件：稀疏矩阵A，B和C存在操作结果：稀疏矩阵的加法运算:C=A+BSubTSM(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在操作结果：稀疏矩阵的减法运算:C=A-B MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)初始条件：稀疏矩阵A，B和C存在操作结果：稀疏矩阵的乘法运算:C=A×BNiMatrix(TSMatrix &TM)初始条件：稀疏矩阵TM存在操作结果：稀疏矩阵求逆}ADT SparseMatrix;2. 主程序：void main( ){初始化；do {接受命令；选择处理命令；}while(命令！=“退出”)}3. 本程序有四个模块，调用关系如下：主程序模块矩阵输入模块矩阵运算模块矩阵输出模块图 2.1 本程序的流程图4开始选择要执行的操作结束2.2图设计步骤第三章函数说明3.1稀疏矩阵的三元组顺序表存储表示：定义三元组的元素typedef struct //{int i,j;int v;}Triple;class tripletable设计类来描述稀疏矩阵及其操作// {public:aaa *pdata;triple data[maxsize];tripletable(); int rpos[maxsize];~tripletable();void convert() ;void add( );void multi ( );private:int m ;int n ;int t ;int a ;};主要函数：tripletable();~tripletable();void convert( ) ;void add( );void multi ( );void main( );3.2设计步骤：设计一个矩阵类实现矩阵的运算：class tripletable(包含矩阵的各种运算函数)。
输入矩阵（以三元组形式输入非零元）{int k;tripletable A,B;;的行数，列数和非零元个数：A输入稀疏矩阵潣瑵?cin>>A.m>>A.n>>A.t;for(k=1;k<=A.t;k++){牰湩晴尨输入第%d个非0元素的行数，列数和值:,k);cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; }输出矩阵：int c[100][100]={0};for(k=1;k<=B.t;k++){c[B.data[k].i][B.data[k].j]=B.data[k].v;}潣瑵?转置（加法，乘法）结果为：<<endl; for(k=1;k<=B.n;k++){for(int l=1;l<=B.m;l++)cout<<c[k][l]<< ;cout<<endl;}}转置矩阵：矩阵的转置// void tripletable::convert( ) {int k;tripletable A,B;潣瑵?输入稀疏矩阵A的行数，列数和非零元个数：; cin>>A.m>>A.n>>A.t;for(k=1;k<=A.t;k++){牰湩晴尨输入第%d个非0元素的行数，列数和值:,k); cin>>A.data[k].i>>A.data[k].j>>A.data[k].v;}B.m=A.m;B.n=A.n;B.t=A.t;if(B.t){int q=1,col;for(col=1;col<=A.n;++col)for(int p=1;p<=A.t;++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].v=A.data[p].v;++q;}}int shuru[100][100]={0};for(k=1;k<=B.t;k++){shuru[B.data[k].j][B.data[k].i]=B.data[k].v; }潣瑵?输入为：<<endl;for(k=1;k<=B.m;k++){for(int l=1;l<=B.n;l++)cout<<shuru[k][l]<< ;cout<<endl;}int result[100][100]={0};for(k=1;k<=B.t;k++){result[B.data[k].i][B.data[k].j]=B.data[k].v; }潣瑵?结果为：<<endl;for(k=1;k<=B.n;k++){for(int l=1;l<=B.m;l++)cout<<result[k][l]<< ;cout<<endl;}}以上主要设计思想：通过三元组输入一个矩阵A，为了找到A的每一列中所有非零元素，需要对其三元组表A.data从第一行起整个扫描一遍，由于A.data是以A的行序为主序来存放每个非零元的，由此得到的恰是B.data的应有的顺序。
加法矩阵：void tripletable::add( ) //矩阵的加法{int k;tripletable A,B;潣瑵?输入稀疏矩阵A的行数，列数和非零元个数：;cin>>A.m>>A.n>>A.t;for(k=1;k<=A.t;k++){牰湩晴尨输入第%d个非0元素的行数，列数和值:,k);cin>>A.data[k].i>>A.data[k].j>>A.data[k].v;}潣瑵?输入稀疏矩阵B的行数，列数和非零元个数：;cin>>B.m>>B.n>>B.t;for(k=1;k<=B.t;k++){牰湩晴尨输入第%d个非0元素的行数，列数和值:,k);cin>>B.data[k].i>>B.data[k].j>>B.data[k].v;}if(A.m!=B.m||A.n!=B.n){潣瑵?输入错误：A与B的行数或列数不相同，请重新输入<<endl; return;}int a[100][100]={0};for(k=1;k<=A.t;k++){a[A.data[k].i][A.data[k].j]=A.data[k].v;}cout<<A输入为：<<endl;for(k=1;k<=A.m;k++){for(int l=1;l<=A.n;l++)cout<<a[k][l]<< ;cout<<endl;}int b[100][100]={0};for(k=1;k<=B.t;k++){b[B.data[k].i][B.data[k].j]=B.data[k].v; }cout<<B输入为：<<endl;for(k=1;k<=B.m;k++){for(int l=1;l<=B.n;l++)cout<<b[k][l]<< ;cout<<endl;}int c[100][100]={0};for(k=1;k<=A.m;k++){for(int l=1;l<=A.n;l++){c[k][l]=a[k][l]+b[k][l];}}潣瑵?加法结果C为：<<endl;for(k=1;k<=A.m;k++){for(int l=1;l<=A.n;l++)cout<<c[k][l]<< ;cout<<endl;}}以上主要设计思想：此功能由函数add( )实现，当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。