稀疏矩阵的应用

稀疏矩阵的应用 稀疏矩阵的应用 数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目: 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2013 年 12 月 16 日 完 成 时 间: 2013 年 12 月 31 日 课程设计成绩: 学习态度及平技术水平与实 说明书,计算书、图纸、总 分 创新,5, 时成绩,30, 际能力,20, 分析报告,撰写质量,45, ,100, 指导教师签名: 年 月 日 I 稀疏矩阵的应用 目 录 1 需求分析 ................................ 1 1.1任务与分析 ......................................................... 1 1.2测试数据............................................................. 1 2 概要设计 ................................ 1 2.1存储结构设计 ..................................................... 1 2.2程序模块结构 ..................................................... 2 2.3 各功能模块 ...................................................... 3 3 详细设计 ................................ 4 3.1结构体定义 ......................................................... 4 3.2 插入操作............................................................ 4 4 调试分析 ................................16 5 用户使用说明 ............................16 6 测试结果 ................................16 6.1系统运行主界 .................................................... 16 6.2 各子功能测试运行结果 ................................... 17 结 论 ....................................20 I 稀疏矩阵的应用 摘 要, 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵～并对稀疏矩阵进行转置～相加～相乘等操作～最后输出运算后的结果。考虑到难易程度～先用三元组实现稀疏矩阵的输入～输出～及其转置～相加～相乘等操作的方法～再在十字链表下实现。程序通过调试运行～结果与预期一样～初步实现了设计目标。 关键词:程序设计,稀疏矩阵,三元组,十字链表 II 稀疏矩阵的应用 引 言 1 需求分析 其目的是让我们在学习完C++、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 1.1任务与分析 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个稀疏矩阵A和B的和为矩阵C，并输出C; 求出A的转置为矩阵D，输出D; 求两个稀疏矩阵A和B的相乘为矩阵E，并输出E。 1.2测试数据 5 4 5 1 1 3 1 4 7 2 3 -1 3 1 2 5 4 -8 5 4 10 1 3 1 1 4 2 2 2 2 2 3 1 2 4 1 3 4 3 4 1 1 4 2 6 4 4 1 5 1 2 2 概要设计 2.1存储结构设计 三元组结构体定义: struct element 1 稀疏矩阵的应用 { int i,j; ElemType item; }; const int MaxTerm = 100; struct Sparsematrix { element data[MaxTerm]; int mu, nu, tu; //行数、列数、非零元个数 }; 十字链表结构体定义: typedef struct MLnode { int i;//结点的行下标 int j; //结点的列下标 ElemType e; //非零元的值 struct MLnode *right, *down; //该非零元所在行表和列表的后继元素 }MLnode; 2.2程序模块结构 2.2.1 结构体定义 三元组结构体定义: struct element { int i,j; ElemType item; }; const int MaxTerm = 100; struct Sparsematrix { element data[MaxTerm]; int mu, nu, tu; //行数、列数、非零元个数 }; 十字链表结构体定义: typedef struct MLnode { int i;//结点的行下标 2 稀疏矩阵的应用 int j; //结点的列下标 ElemType e; //非零元的值 struct MLnode *right, *down; //该非零元所在行表和列表的后继元素 }MLnode; 2.3 各功能模块 本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储结构下，由函数 void creatT()实现，在十字链表存储结构下，由函数void CreateL(Sparsematrix &X)依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 (1)稀疏矩阵的转置: 此功能在三元组存储结构下，有两种方法:按行转置和按列转置，分别由函数void zhuanzT(Sparsematrix X,Sparsematrix &b)和sqmatrix transmattwo()实现，在十字链表存储结构下，由函数void zhuanzhi( )实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。 (2)稀疏矩阵的加法: 此功能在三元组存储结构下，由函数void addT(Sparsematrix a, Sparsematrix b, Sparsematrix &c)实现，在十字链表存储结构下，由函数void addL(CrossList &a, CrossList &b)实现。当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 (3)稀疏矩阵的乘法: 此功能在三元组存储结构下，由函数void cheng(sqmatrix a,sqmatrix b)实现。在十字链表存储结构下，由函数void chengfa()实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 (4)退出: 即退出稀疏矩阵的应用系统，由switch语句实现。当用户选择相应序号，则退出该稀疏矩阵的应用系统。 3 稀疏矩阵的应用 3 详细设计 3.1结构体定义 …三元组结构体定义: struct element { int i,j; ElemType item; }; const int MaxTerm = 100; struct Sparsematrix { element data[MaxTerm]; int mu, nu, tu; //行数、列数、非零元个数 }; 十字链表结构体定义: typedef struct MLnode { int i;//结点的行下标 int j; //结点的列下标 ElemType e; //非零元的值 struct MLnode *right, *down; //该非零元所在行表和列表的后继元素 }MLnode; 3.2 插入操作 A. 主程序模块设计: Sparsematrix s1, s2, s3; CrossList c1,c2;//两个链表储存的矩阵 int k; do{ cout << endl; 4 稀疏矩阵的应用 cout << "***********稀疏矩阵应用**************" << endl << endl; cout << "请你选择创建两个稀疏矩阵的方法 " << endl; cout << "1、用三元组顺序表创建稀疏矩阵" << endl; cout << "2、用十字链表创建稀疏矩阵" << endl; cout << "3、退出程序" << endl << endl; cout << "请选择:"; cin >> k; cout << endl; switch (k){ case 1: { createT(s1); //三元组顺序表创建矩阵 printT(s1); createT(s2); printT(s2); } break; case 2:{ createL(c1); //十字链表创建矩阵 printL(c1); createL(c2); printL(c2);}break; } switch (k) { case 1: cout << "**********欢迎进入《三元组操作》矩阵系统**********" << endl << endl; cout << "\n 1、两矩阵求和" << endl; cout << "\n 2、两矩阵相乘" << endl; cout << "\n 3、矩阵按行转置" << endl; cout << "\n 4、退出程序" << endl << endl; int kk=0; cout << "请选择:"; cin >> kk; 5 稀疏矩阵的应用 switch (kk) { case 1: {addT(s1, s2, s3); printT(s3); } break; case 2: break; case 3: { cout << "转置第一个矩阵"; Sparsematrix s4; zhuanzT(s1, s4); printT(s4); } break; case 4: break; } } break; cout << endl; case 2: { cout << "**********欢迎进入《十字链表操作》矩阵系统**********" << endl << endl; cout << "\n 1、两矩阵求和" << endl; cout << "\n 2、两矩阵相乘" << endl; cout << "\n 3、矩阵按行转置" << endl; cout << "\n 4、矩阵按列转置" << endl; cout << "\n 5、退出程序" << endl << endl; int kk=0; cout << "请选择:"; cin >> kk; switch (kk) { case 1: {addL(c1, c2); printL(c1); } break; case 2: break; case 3: break; case 4: break; } cout << endl; }break; } } while (k == 1 || k == 2); 6 稀疏矩阵的应用 cout << endl; } B. 稀疏矩阵操作各子函数的定义: (1)建立与初始化稀疏矩阵: 采用三元组建立稀疏矩阵，输入非零元素的行号、列号和值，关键代码如下: cout << "请输入稀疏矩阵的行数、列数、非零元值个数:"<> X.mu >> X.nu >> X.tu; cout << "行号i 列号j 非零元素值item" << endl; for (int p = 0; p> ii>> jj>> element; X.data[p].i = ii; X.data[p].j = jj; X.data[p].item = element; } 采用十字链表建立稀疏矩阵，输入非零元素的行号、列号和值，给新结 点申请空间，按列循环链表和行循环链表形式插入到十字链表中关键代码如下: void createL(CrossList &X) { int i, j, e, k; MLnode *p, *q; // if(X) delete X; cout << "请输入矩阵的行数、列数和非零元素个数:"<> X.m >> X.n >> X.t; X.rhead = (MLnode **) new MLnode[X.m + 1]; //按行数申请动态MLnode* 类型的数组;并赋值全为空 for (k = 1; k <= X.m; k++) X.rhead[k] = 0; X.chead = (MLnode **) new MLnode[X.n + 1]; //按列数申请动态MLnode* 7 稀疏矩阵的应用 类型的数组;并赋值全为空 for (k = 1; k <= X.n; k++) X.chead[k] = 0; int r = X.t; cout << "请输入结点的行号、列号和非零元素值" << endl; cin >> i >> j >> e; while (i) { --r; p = new MLnode; p->i = i; p->j = j; p->e = e; if (X.rhead[i] == 0 || X.rhead[i]->j>j) //若链表为空或者该行头头指针所在列大于输入的非零元所在列号小于号，前插，后移动头指针 { p->right = X.rhead[i]; X.rhead[i] = p; } else //否则如果该行头指针所在列小于或等于输入的非零元所在列号，后插，不移动头指针 { for (q = X.rhead[i]; (q->right) && q->right->jright); //寻找插入点 p->right = q->right; q->right = p; } if (X.chead[j] == 0 ||X.chead[j]->i>i) { p->down = X.chead[j]; X.chead[j] = p; } else { for (q = X.chead[j]; (q->down) && q->down->idown); p->down = q->down; q->down = p; } if (r ==0)break; 8 稀疏矩阵的应用 cin >> i >> j >> e; } } (2)输出稀疏矩阵: 用三元组输出矩阵元素时，若稀疏矩阵所对应的元素在三元组中有该元素，则输出三元组中的这个元素的值，否则，输出零。其关键代码如下: if(data[p].i==i&&data[p].j==j) {isfound=true;foundindex=p; } if(isfound==true) cout<j) { cout <e ; p = p->right; } else cout << setw(5) << "0"; } cout << endl; } (3)实现矩阵的转置: 用三元组和十字链表实现矩阵转置，都采用元素所对应的行号变为新矩阵的列号，所对应的列号变为新矩阵的行号，所对应的值不变，在这个过程中采用一个for循环使待转置的元素所对应的列号较小者先转置到新矩阵中，其关键代码如下: void zhuanzT(Sparsematrix X,Sparsematrix &b) { int k = 1; for (int i = 1; i <= X.mu; i++) 9 稀疏矩阵的应用 { for (int j = 1; j <= X.nu; j++) { bool isfound = false; int foundindex; for (int p = 0; p < X.tu; p++) { if (X.data[p].i == i&&X.data[p].j == j) { isfound = true; foundindex = p; break; } } if (isfound == true){ b.data[k].i = j; b.data[k].j = i; b.data[k].item = X.data[foundindex].item; ++k; } } b.mu = X.nu; b.nu = X.mu; b.tu = k; } } (4)实现两个矩阵的相加: 采用三元组实现两矩阵相加时，先判断被加的两矩阵所对应的位置是否有 非零元素，若没有或两矩阵元素相加为零，则新三元组表中不进行任何操作，若 只有一个为非零元素，则新三元组表中对应位置元素值就为该非零元素的值，若 两矩阵相同位置元素和k不为零，则新三元组表中对应应位置元素值就为k。其 10 稀疏矩阵的应用 关键代码如下: //三元组顺序表矩阵的相加 void addT(Sparsematrix a, Sparsematrix b, Sparsematrix &c) { int i = 1, j = 1, k = 1; while (i <= a.tu &&j < b.tu) { if (a.data[i].i == b.data[j].i) { if (a.data[i].j == b.data[i].j) { c.data[k].i = a.data[i].i; c.data[k].j = a.data[i].j; c.data[k].item = a.data[i].item+b.data[j].item; j++; k++; } if (a.data[i].j < b.data[i].j) { c.data[k].i = a.data[i].i; c.data[k].j = a.data[i].j; c.data[k].item = a.data[i].item; i++; k++; } if (a.data[i].j> b.data[i].j) { c.data[k].i =b.data[j].i; c.data[k].j = b.data[j].j; c.data[k].item = b.data[j].item; j++; k++; } } else if (a.data[i].i < b.data[j].i) { c.data[k].i = a.data[i].i; c.data[k].j = a.data[i].j; c.data[k].item = a.data[i].item; i++; k++; } else if (a.data[i].i >b.data[j].i) { c.data[k].i = b.data[j].i; c.data[k].j = b.data[j].j; c.data[k].item = b.data[j].item; j++; k++; 11 稀疏矩阵的应用 } } c.mu = a.mu; c.nu = a.nu; c.tu = k; }采用十字链表实现两矩阵相加时，和三元组实现两矩阵相加类似，不同点就是元素相加后转向被加的两个元素结点向下移动，新三元组的指针也向下移动其关键代码如下: void addL(CrossList &a, CrossList &b) //矩阵a与矩阵b相加，用b插入a { int max = a.n; MLnode**hl; hl = (MLnode**)new MLnode[max]; MLnode *pa, *pb, *pre, *insert, *keep; for (int i =1; i <= a.m; i++) { pa = a.rhead[i]; //初始化指向首结点，以后逐个向后移动 pb = b.rhead[i]; pre = NULL; for (int j = 1; j < max; j++) //n为矩阵列数,hl的作用是等同于pre指针，追踪竖向上新插入的结点 hl[j] = a.chead[j]; while (pb != NULL) { if (pa == NULL || pa->j >pb->j) //横插 { insert = new MLnode; insert->i = pb->i; insert->j = pb->j; insert->e = pb->e; if (pre == NULL) a.rhead[i] = insert; 12 稀疏矩阵的应用 else pre->right = insert; insert->right = pa; pre = insert; //pre用于最终新插入的结点 if (a.chead[insert->j] == NULL || a.chead[insert->j]->i > insert->i) // 竖插(拿新插入结点的所在列的头结点行数与新插入结点行数比较) { insert->down = a.chead[insert->j]; a.chead[insert->j] = insert; } else { insert->down = hl[insert->j]->down; hl[insert->j]->down=insert; } hl[insert->j] = insert; pb = pb->right; } else if (pa->j == pb->j) { pa->e += pb->e; if (pa->e == 0) //如果相加不为0，不用操作，pa已经改动; { keep = pa; if (pre == NULL){ a.rhead[i] = pa->right; } //pre不一定一定等于0当前一 种情况的时候pre指向有可能改变 else{ pre->right = pa->right; } //pre指向行首结点? pa = pa->right; delete keep; 13 稀疏矩阵的应用 } pb = pb->right; } else //pa->jj 这种情况m不动， pa指向下一个结点让它和pb再比较 { pre = pa; pa = pa->right; } } } (5)实现两个矩阵的相乘: } 三元组实现两矩阵相乘和三元组实现两矩阵相加类似，不同就是新矩阵非 零元素所在行和列的值是两矩阵所对应行元素与所对应列元素相乘后相加，其主 要代码如下: int ctemp[max]; t=0; m=a.m; n=a.n; if(a.t*b.t!=0) {for(arow=1; arow<=a.m; arow++) {for(ii=1; ii<=a.n; ii++) ctemp[ii]=0; rpos[arow]=t;Mlim=arowe=pb->e; p->i=pb->i; p->j=pb->j; if(NULL==pa||pa->j>pb->j) { if(NULL==pre) M.rhead[p->i]=p; else pre->right=p; p->right=pa; pre=p; if(NULL==M.chead[p->j]){ M.chead[p->j]=p; p->down=NULL; } else { p->down=hl[p->j]->down; hl[p->j]->down=p; } hl[p->j]=p; pb=pb->right; } else if((NULL!=pa)&&pa->jj) { pre=pa; pa=pa->right; } else if(pa->j==pb->j) { pa->e *= pb->e; if(!pa->e) {if(NULL==pre) M.rhead[pa->i]=pa->right; else pre->right=pa->right; p=pa; pa=pa->right; if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down; else hl[p->j]->down=p->down; free(p); pb=pb->right; } else{ pa=pa->right; pb=pb->right; } 15 稀疏矩阵的应用 4 调试分析 用C++语言写代码实现所要求的功能过程中，用三元组实现矩阵相乘，有一定的难度，我通过多次调试，系统始终提示出错，通过参考网友的代码和同学的提示，原来两矩阵的第i行非零元素个数不一定等于另一矩阵的第i列非零元素个数，最后，我通过控制一矩阵的非零元素所在的i行、j列位置与另一个矩阵所对应的i列j行元素相乘，然后在相加。通过测试，功能能够实现了;在用十字链表实现各功能时，由于指针很多，写出的代码最初基本上都是指针指向出错，通过自己经验以及老师的指导、朋友的帮助，最后解决了各个问题。 5 用户使用说明 该系统具有简单、明了、使用等特点，能够方便、准确的计算出矩阵的部分操作，适用于学校老师、同学对矩阵方面的研究。当使用该系统时，系统会给出相关的提示信息， 用户只需根据提示信息，即可完成系统提供的所有功能 6 测试结果 6.1系统运行主界 系统运行主界面如图6.1所示: …… 图6.1主界面 16 稀疏矩阵的应用 6.2 各子功能测试运行结果 (1)稀疏矩阵的相加: 在主菜单下，用户输入1回车，是用三元组对矩阵的操作，用户再按1回车， 根据屏幕提示操作，运行结果如图6.2所示。 图6.2两个三元表矩阵的建立 17 稀疏矩阵的应用 图6.3两份矩阵相加后的输出 (2)稀疏矩阵的转置: 用三元组创建稀疏矩阵后，用户在三元组操作下输入3或4回车，便显示该 矩阵的转置矩阵，运行结果如图6.4所示。 图6.4 转置的输出 (3)十字链表稀疏矩阵的相加: 18 稀疏矩阵的应用 十字链表操作下输入2回车，按屏幕提示操作， 图6.5十字链表储存的加法运算 (5)退出: 在主菜单下，用户输入3回车，或者在下级菜单中输入5回车，退出程序。运行结果如图 图6.6退出界面 19 稀疏矩阵的应用 结 论 由于本程序要求用两种办法对稀疏矩阵进行运算，特别是用十字链表这种形式来对稀疏矩阵进行运算，是实现起来有很多困难，主要包括: 1、书上这种方面的东西不多，资料少，可以参考的东西不是很多; 2、用十字链表进行运算比较复杂，难度较大，需要对指针掌握较好; 3、在书写课程设计报告时，没有具体的详细的

模板

个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载

，感觉有一点无从下手，害怕写错。 针对上述困难，自己对症下药，通过网络，图书馆找资料，请老师指点，借鉴别人的已往的优秀的课程设计报告，以及老师给的报告要求书，和同学们一起讨论，逐步地解决自己的问题。 在做这个课程设计的过程我也学到了许多知识。懂得了用三元组表和十字链表存储稀疏矩阵的元素不仅可以操作数组能操作的大部分重要功能外，他们还能避免空间浪费。而采用十字链表和采用三元组各有各的优缺点。三元组在实现各功能时操作简单、易懂，但算法的时间复杂度较十字链表的要大(例如:用三元组实现行转置的算法时间复杂度大于O(m*n)，而用十字链表来实现时间复杂度则接近O(m+n))。当矩阵非零元素的位置或个数经常变动时，采用十字链表可以避免大量移动数据元素，但用十字链表算法复杂、难懂，很容易把指针的指向弄错。除此之外，我也懂得了一个软件实验报告的大概写法。 通过此次课程设计，使我对本学期学的《数据结构》有了更深的了解，也使自己的所学更加牢固，并能够把更多方面的知识综合起来运用 20 稀疏矩阵的应用 参考文献 ,1,杨宝刚.开展企业管理信息化工作的步骤,J,.企业管理.2002.(11).12~15 ,2,Islamabad. Software tools for forgery detection,J,. Business line.2001. (5). 29~32 [3] 王立柱.C/C++与数据结构.北京:清华大学出版社，2002 [4] 顾元刚.数据结构简明教程.南京:东南大学出版社等，2003 [5] 郭福顺，王晓芬，李莲治《数据结构》(修订本)，大连理工大学出版社，1997 [6] [美]Mark Allen Weiss，数据结构与算法分析——C语言描述(英文版•第2版)，人民邮电出版社，2005.8 [7] 李春葆著，数据结构教程，清华大学出版社，2005.1 21 稀疏矩阵的应用 22