《数据结构实验报告（稀疏矩阵）》由会员分享，可在线阅读，更多相关《数据结构实验报告（稀疏矩阵）（20页珍藏版）》请在金锄头文库上搜索。
1、一需求分析 输入要求：稀疏矩阵的行、列和非零元素个数输出要求：稀疏矩阵的转置、加法、减法、乘法二算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系1抽象数据类型：ADT List 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R=Row,ColRow=|1=i=m,1=j=n-1Col=|1=i=m-1,1=j=n基本操作:Status CreateSMatrix(TSMatrix &M)操作结果：初始化稀疏数组void PrintSMatrix(TSMatrix M)初始条件：稀疏数组M已经存在操作结果：打印矩阵Mvoi
2、d DestroySMatrix(TSMatrix &M)初始条件：稀疏数组M已经存在操作结果：销毁矩阵Mvoid CopySMatrix(TSMatrix M, TSMatrix &T)初始条件：稀疏数组M已经存在操作结果：复制矩阵M到TStatus AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)初始条件：稀疏数组M、N已经存在操作结果：求矩阵的和Q=M+NStatus SubSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)初始条件：稀疏数组M、N已经存在操作结果：求矩阵的差Q=M-NStatus Tra
3、nsposeSMatrix(TSMatrix M, TSMatrix & T)初始条件：稀疏数组M已经存在操作结果：求矩阵M的转置TStatus MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)初始条件：稀疏数组M已经存在操作结果：求矩阵的积Q=M*N ADT List2. 本程序有二个模块：（1）主程序模块 main()初始化；接受命令；显示结果；（2）三元组表单元模块：实现矩阵抽象数据类型。三程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等
4、。1、程序基本结构：2、稀疏矩阵的三元组顺序表存储表示：typedef struct / 定义三元组的元素 int i, j; int e; Triple;typedef struct / 定义普通三元组对象 Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix;typedef struct / 定义带链接信息的三元组对象 Triple dataMAXSIZE + 2; int rposMAXROW + 1; int mu, nu, tu; RLSMatrix;3、 基本函数：1)输入矩阵，按三元组格式输入bool InPutTSMatrix(P &
5、 T, int y) cout 输入矩阵的行，列和非零元素个数: T.mu T.nu T.tu; cout 请输出非零元素的位置和值: endl; int k = 1; for (; k T.datak.i T.datak.j T.datak.e; return true;2) 输出矩阵，按标准格式输出bool OutPutSMatrix(P T) int m, n, k = 1; for (m = 0; m T.mu; m+) for (n = 0; n T.nu; n+) if (T.datak.i - 1) = m & (T.datak.j - 1) = n) cout.width(4)
6、; cout T.datak+.e; else cout.width(4); cout 0; cout endl; return true;3) 求矩阵的转置矩阵bool TransposeSMatrix() TSMatrix M, T; /定义预转置的矩阵 InPutTSMatrix(M, 0); /输入矩阵 int numMAXROW + 1; int cpotMAXROW + 1; /构建辅助数组 int q, p, t; T.tu = M.tu; T.mu = M.nu; T.nu = M.mu; if (T.tu) for (int col = 1; col = M.nu; col+
7、) numcol = 0; for (t = 1; t = M.tu; t+) +numM.datat.j; cpot1 = 1; for (int i = 2; i = M.nu; i+) cpoti = cpoti - 1 + numi - 1; for (p = 1; p = M.tu; p+) int col = M.datap.j; q = cpotcol; T.dataq.i = col; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol; cout 输入矩阵的转置矩阵为 endl; OutPutSMatrix(T); r
8、eturn true;4) 两个矩阵相乘bool MultSMatrix() RLSMatrix M, N, Q; / 构建三个带“链接信息”的三元组表示的数组 InPutTSMatrix(M, 1); /用普通三元组形式输入数组 InPutTSMatrix(N, 1); Count(M); Count(N); if (M.nu != N.mu) return false; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; /Q初始化 int ctempMAXROW + 1; /辅助数组 int arow, tp, p, brow, t, q, ccol; if (M.t
9、u * N.tu) / Q是非零矩阵 for (arow = 1; arow = M.mu; arow+) /memset(ctemp,0,N.nu); for (int x = 1; x = N.nu; x+) ctempx = 0; Q.rposarow = Q.tu + 1; / 当前行的首个非零元素在三元组中的位置为此行前所有非零元素+1 if (arow M.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p = M.rposarow; p tp; p+) / 对当前行每个非零元素进行操作 brow = M.datap.j; / 在
10、N中找到i值也操作元素的j值相等的行 if (brow N.mu) t = N.rposbrow + 1; else t = N.tu + 1; for (q = N.rposbrow; q t; q+) / 对找出的行当每个非零元素进行操作 ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e; / 将乘得到对应值放在相应的元素累加器里面 for (ccol = 1; ccol MAXSIZE) return false; Q.dataQ.tu.e = ctempccol; Q.dataQ.tu.i = arow; Q.dataQ.tu.j
11、 = ccol; OutPutSMatrix(Q); return true;5) 矩阵的加法bool AddSMatrix() CrossList M, N; / 创建两个十字链表对象，并初始化 CreateSMatrix_OL(M); CreateSMatrix_OL(N); cout 输入的两矩阵的和矩阵为： endl; OLink pa, pb, pre, hlMAXROW + 1; /定义辅助指针，pa，pb分别为M,N当前比较的元素，pre为pa的前驱元素 for (int x = 1; x = M.nu; x+) hlx = M.cheadx; for (int k = 1; k = M.mu; k+) / 对M的每一行进行操作 pa = M.rheadk; pb = N.rheadk; pre = NULL; while (pb) / 把N中此行的每个元素取出， OLink p;
