数据结构课程设计稀疏矩阵实现与应用

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 稀疏矩阵实现与应用 专业 计算机科学与技术 班级 学号姓名 联系方式 指导教师20 11 年 12 月 25 日目 录1、数据结构课程设计任务书1.1、题目-1.2、要求-2、总体设计 -2.1、功能模块设计-12.2、所有功能模块的流程图-23、详细设计-33.1、程序中所采用的数据结构及存储结构的说明-103.2、算法的设计思想-103.3、稀疏矩阵各种运算的性质变换-104、调试与测试：-104.1、调试方法与步骤： -104.2、测试结果的分析与讨论：-115、时间复杂度的分析：-126、源程序清单和执行结果-

2、127、c程序设计总结-208、致谢-209、参考文献-201、数据结构课程设计任务书1.1、题目 实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。1.2、要求 (1).设计函数建立稀疏矩阵，初始化值； (2).设计函数输出稀疏矩阵的值； (3).构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵； (4).构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵； (5).构造函数进行稀疏矩阵的转置，并输出结果； (6).退出系统。2、总体设计2.1、功能模块设计输入矩阵1矩阵相加输入矩阵2计算结果矩阵相减输入矩阵1输入矩阵2计算结果矩阵转置输入矩阵计算结果退出2.2、所有功能模块的流程图3、详细

3、设计1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；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; / 定义带链接信息的三元组对象typedef struct olnode / 定义十字链表元素 int i,

4、 j; int e; struct olnode *right, *down; / 该非零元所在行表和列表的后继元素 olnode, *olink; / 定义十字链表元素typedef struct / 定义十字链表对象结构体 olink *rhead, *chead; int mu, nu, tu; / 系数矩阵的行数，列数，和非零元素个数 crosslist; / 定义十字链表对象结构体2主函数int main() int t; cout.fill(*); cout setw(80) *; cout.fill( ); cout setw(50) *欢迎使用矩阵运算程序* endl; /输出

5、头菜单 cout.fill(*); cout setw(80) *; cout.fill( ); cout 请选择要进行的操作： endl; cout 1:矩阵的转置。 endl; cout 2:矩阵的加法。 endl; cout 3:矩阵的乘法。 endl; cout 4:退出程序。 endl;while(t)cout请输入您要进行的操作：t;switch(t)case 1:transposesmatrix(); /调用矩阵转置函数break;case 2:addsmatrix(); /调用矩阵相加函数break;case 3: multsmatrix(); /调用矩阵相乘函数break;c

6、ase 4:t=0;break;return 0;矩阵的转置函数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+) numcol = 0; for (t = 1; t = m.tu; t

7、+) +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 = m.datap.j; t.dataq.j = m.datap.i; t.dataq.e = m.datap.e; +cpotcol; cout 输入矩阵的转置矩阵为 endl; outputsmatrix(t); return tr

8、ue;bool count(rlsmatrix &t) int nummaxrow + 1; for (int row = 1; row = t.mu; row+) numrow = 0; for (int col = 1; col = t.tu; col+) +numt.datacol.i; t.rpos1 = 1; for (int i = 2; i = t.mu; i+) t.rposi = t.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元组中出现的位置 return true;矩阵的乘法函数bool multsmatrix() / 两个矩阵相乘 rlsma

9、trix m, n, q; / 构建三个带“链接信息”的三元组表示的数组 inputtsmatrix(m, 1); / 用普通三元组形式输入数组 inputtsmatrix(n, 1); count(m); count(n); cout 输入的两矩阵的乘矩阵为： endl; 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.tu * n.tu) / q是非零矩

10、阵 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; / 在n中找

11、到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 =

12、ccol; outputsmatrix(q); return true;矩阵的加法函数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

13、; k e = pb-e; p-i = pb-i; p-j = pb-j; if (null = pa | pa-j pb-j) / 当m此行已经检查完或者pb因该放在pa前面 if (null = pre) m.rheadp-i = p; else pre-right = p; p-right = pa; pre = p; if (null = m.cheadp-j) / 进行列插入 m.cheadp-j = p; p-down = null; else p-down = hlp-j-down; hlp-j-down = p; hlp-j = p; pb = pb-right; else i

14、f (null != pa) & pa-j j) / 如果此时的pb元素因该放在pa后面，则取以后的pa再来比较 pre = pa; pa = pa-right; else if (pa-j = pb-j) / 如果pa，pb位于同一个位置上，则将值相加 pa-e += pb-e; if (!pa-e) / 如果相加后的和为0，则删除此节点，同时改变此元素坐在行，列的前驱元素的相应值 if (null = pre) / 修改行前驱元素值 m.rheadpa-i = pa-right; else pre-right = pa-right; p = pa; pa = pa-right; if (m

15、.cheadp-j = p) m.cheadp-j = hlp-j = p-down; / 修改列前驱元素值 else hlp-j-down = p-down; free(p); pb = pb-right; else pa = pa-right; pb = pb-right; outputsmatrix_ol(m); return true;创建十字链表bool createsmatrix_ol(crosslist & m)/ 创建十字链表 int x, y, m; cout 请输入矩阵的行，列，及非零元素个数 m.mu m.nu m.tu; if (!(m.rhead = (olink*)

16、 malloc(m.mu + 1) * sizeof (olink) exit(0); if (!(m.chead = (olink*) malloc(m.nu + 1) * sizeof (olink) exit(0); for (x = 0; x = m.mu; x+) m.rheadx = null; / 初始化各行，列头指针，分别为null for (x = 0; x = m.nu; x+) m.cheadx = null; cout 请按三元组的格式输入数组： endl; for (int i = 1; i x y m; / 按任意顺序输入非零元，（普通三元组形式输入） olink

17、p, q; if (!(p = (olink) malloc(sizeof (olnode) exit(0); / 开辟新节点，用来存储输入的新元素p-i = x; p-j = y; p-e = m; if (m.rheadx = null | m.rheadx-j y) p-right = m.rheadx; m.rheadx = p; else for (q = m.rheadx; (q-right) & (q-right-j right); / 查找节点在行表中的插入位置 p-right = q-right; q-right = p; / 完成行插入 if (m.cheady = nul

18、l | m.cheady-i x) p-down = m.cheady; m.cheady = p; else for (q = m.cheady; (q-down) & (q-down-i down); / 查找节点在列表中的插入位置 p-down = q-down; q-down = p; / 完成列插入 return true;十字链表的输出bool outputsmatrix_ol(crosslist t)/ 输出十字链表，用普通数组形式输出 for (int i = 1; i = t.mu; i+) olink p = t.rheadi; for (int j = 1; j j) c

19、out setw(3) e; p = p-right; else cout setw(3) 0; cout endl; return true;3.1、程序中所采用的数据结构的说明adt sparsematrix 数据对象：d=aij | i=1,2,m; j=1,2,.,n;aijelemset, m和n分别称为矩阵的行数和列数。数据关系：r=row,colrow= | 1=i=m, 1=j=n-1 col= | 1=i=m-1, 1=j=n基本操作：createsmatrix(&m)； 操作结果：创建稀疏矩阵m。destroysmatrix(&m)； 初始条件：稀疏矩阵m存在。 操作结果：

20、销毁稀疏矩阵m。printsmatrix(m)； 初始条件：稀疏矩阵m存在。 操作结果：输出稀疏矩阵m。addsmatrix(m，n，&q)； 初始条件：稀疏矩阵m与n的行数和列数对应相等 操作结果：求稀疏矩阵的和q=m+n。multsmatrix(m，n，q)； 初始条件：稀疏矩阵m的列数等于n的行数。 操作结果：求稀疏矩阵乘积q=m*n。 transposesmatrix(m，t)； 初始条件：稀疏矩阵m存在。 操作结果：求稀疏矩阵m的转置矩阵t。 adt sparsematrix3.2、算法的设计思想本实验要求在三元组，十字链表下实现稀疏 矩阵的加、转、乘。首先要进行矩阵的初始化操作，定

21、义三元组和十字链表的元素对象。写出转置，加法，乘法的操作函数。通过主函数调用实现在一个程序下进行矩阵的运算操作。3.3、稀疏矩阵各种运算的性质变换a)加法运算两个稀疏矩阵的加和矩阵仍然是稀疏矩阵b）乘法运算两个稀疏矩阵的乘积矩阵不是稀疏矩阵c）转置运算一个稀疏矩阵的转置矩阵仍然是稀疏矩阵4、调试与测试：4.1、调试方法与步骤：1. 实际完成的情况说明（完成的功能，支持的数据类型等）； 完成了稀疏矩阵的建立，初始化及输出值的操作。 实现三元组，十字链表下的稀疏矩阵的加法，乘法以及转置运算。2.程序的性能分析，包括时空分析；能应对一般小的错误输入，如果复杂则自动退出程序。3.上机过程中出现的问题及

22、其解决方案； 1.起始有错误,设定的变量名相同。经检查，改正。2一些逻辑错误。经讨论改正。运行出现部分语法错误修正4.程序中可以改进的地方说明；程序在运行中一旦出现矩阵数据格式错误如输入汉字，则程序自动退出。需要重新启动。更新程序对更多错误输入情况的分析能力。5.程序中可以扩充的功能及设计实现假想。对退出操作的扩充在主菜单下，用户输入4回车选择退出程序是，询问是否真的退出系统，如果是，则即退出系统，否则显示continue并且返回主菜单。为了方便由于误按导致程序退出。在退出时可以增加一段感谢使用本程序的结束语。4.2、测试结果的分析与讨论：系统运行主界面输入需要执行的操作1矩阵的转置输入需要执

23、行的操作2矩阵的加法输入需要执行的操作3矩阵的乘法输入错误操作时需要重新选择退出操作5、时间复杂度的分析：a)加法运算由于两矩阵行列相等，故时间复杂度为o（行*列）b）乘法运算设m是m1*n1矩阵，n是m2*n2矩阵，则时间复杂度是o（m1*n1*n2）c）转置运算时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即o（mu*nu）6、 源程序清单和执行结果#include #include using namespace std;const int maxsize = 100; / 定义非零元素的对多个数const int maxrow = 10; / 定义数组的行数的最大值 typede

24、f 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; / 定义带链接信息的三元组对象typedef struct olnode / 定义十字链表元素 int i, j; int e; struct olnode *right, *down;

25、/ 该非零元所在行表和列表的后继元素 olnode, *olink; / 定义十字链表元素typedef struct / 定义十字链表对象结构体 olink *rhead, *chead; int mu, nu, tu; / 系数矩阵的行数，列数，和非零元素个数 crosslist; / 定义十字链表对象结构体template bool inputtsmatrix(p & t, int y) /输入矩阵，按三元组格式输入 cout 输入矩阵的行，列和非零元素个数: t.mu t.nu t.tu; cout 请输出非零元素的位置和值: endl; for (int k = 1; k t.dat

26、ak.i t.datak.j t.datak.e; return true;template 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); cout t.datak+.e; else cout.width(4); cout 0; cout endl; return true;/ 输出矩阵，按标准格式输出bool transposesmatrix

27、() / 求矩阵的转置矩阵 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+) numcol = 0; for (t = 1; t = m.tu; t+) +numm.datat.j; cpot1 = 1; for (int i = 2; i = m.nu

28、; i+) cpoti = cpoti - 1 + numi - 1; / 求出每一列中非零元素在三元组中出现的位置 for (p = 1; p = m.tu; p+) int col = m.datap.j; q = cpotcol; t.dataq.i = m.datap.j; t.dataq.j = m.datap.i; t.dataq.e = m.datap.e; +cpotcol; cout 输入矩阵的转置矩阵为 endl; outputsmatrix(t); return true;bool count(rlsmatrix &t) int nummaxrow + 1; for (i

29、nt row = 1; row = t.mu; row+) numrow = 0; for (int col = 1; col = t.tu; col+) +numt.datacol.i; t.rpos1 = 1; for (int i = 2; i = t.mu; i+) t.rposi = t.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元组中出现的位置 return true;bool multsmatrix() / 两个矩阵相乘 rlsmatrix m, n, q; / 构建三个带“链接信息”的三元组表示的数组 inputtsmatrix(m, 1); /

30、用普通三元组形式输入数组 inputtsmatrix(n, 1); count(m); count(n); cout 输入的两矩阵的乘矩阵为： endl; 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.tu * n.tu) / q是非零矩阵 for (arow = 1; arow = m.mu; arow+) /memset(ctemp,0,n.nu);

31、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; / 在n中找到i值也操作元素的j值相等的行 if (brow n.mu) t = n.rposbrow + 1; else t =

32、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 = ccol; outputsmatrix(q); return true;bool createsmatrix_ol(cr

33、osslist & m)/ 创建十字链表 int x, y, m; cout 请输入矩阵的行，列，及非零元素个数 m.mu m.nu m.tu; if (!(m.rhead = (olink*) malloc(m.mu + 1) * sizeof (olink) exit(0); if (!(m.chead = (olink*) malloc(m.nu + 1) * sizeof (olink) exit(0); for (x = 0; x = m.mu; x+) m.rheadx = null; / 初始化各行，列头指针，分别为null for (x = 0; x = m.nu; x+) m.cheadx = null; cout 请按三元组的格式输入数组： endl; for (int i = 1; i x y m; / 按任意顺序输入非零元，（普通三元组形式输入） olink p, q; if (!(p = (olink) malloc(sizeof (olnode) exit(0); / 开辟新节点，用来存储输入的新元素p-i = x; p-j = y; p-e = m; if (m.rheadx = null | m.rheadx-j y) p-right = m.rheadx; m.rhea