基于三元组表的存储结构实现稀疏矩阵的应用课程设计，实验报告

基于三元组的存储结构实现稀疏矩阵的应用课程设计，#实验# 数 据 结 构 课 程 设 计 设计题目:基于三元组表的存储结构实现稀疏矩阵的应用 学生姓名: 专业班级: 指导教师: 完成时间: 信息工程学 院 信科 系 课程设计成绩评定表(本科)课题名称 基于三元组表的存储结构实现稀疏矩阵的基本操作 院 系 年级专业 学 号 姓 名 成 绩 1、课题设计目的: (1)掌握稀疏矩阵三元组表的存储、创建、显示、转置。 (2)利用三元组表实现矩阵的相加、减。 (3)了解稀疏矩阵的相关应用。 2、课题设计意义: 本次课题设计可以使我们更熟练的掌握有关三元组表及稀疏课题设计 矩阵的相关知识，比一般存储方法节省了存储空间，基于三元组表目的与 的存储结构实现了稀疏矩阵的基本操作。 设计意义 本次课程设计是本组成员共同努力而完成的，第一次进行课程 设计是我们的探索过程，这个过程中，我们克服了一个个困难，在 摸索中前行，我们相信通过此次课程设计我们每个人都会对数据结 构这门课程有更深一步的了解。 指导教师: 年 月 日 目 录 一、课题设计目的及意义 ............................................ 1 1.1、课题设计目的............................................... 1 1.2、课程设计意义 ............................................... 1 二、需求分析....................................................... 1 2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值............. 1 2.2 构造函数进行稀疏矩阵的转置并输出结果 ........................ 1 2.3 构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵 ...... 1 2.4 退出系统 .................................................... 2 三、项目设计....................................................... 2 3.1结构设计..................................................... 2 3.2算法思想..................................................... 2 3.3模块图....................................................... 2 3.4图....................................................... 3 四、系统实现....................................................... 4 4.1主调函数..................................................... 4 4.2三元组表建立................................................. 4 4.3矩阵建立..................................................... 4 4.4矩阵相加减及转置............................................. 5 五、系统调试....................................................... 8 5.1主菜单输出................................................... 8 5.2矩阵相加..................................................... 9 5.3矩阵转置..................................................... 9 5.4矩阵相减.................................................... 10 六、实验...................................................... 10 七、附录 .......................................................... 11 一、课题设计目的及意义 1.1、课题设计目的 (1)掌握稀疏矩阵三元组表的存储，创建，显示，转置等方法。 (2)利用三元组表实现矩阵的相加，减。 (3)了解稀疏矩阵的相关应用。 1.2、课程设计意义 本次课题设计可以使我们更熟练的掌握有关三元组表及稀疏矩阵的相关知识，比一般存储方法节省了存储空间，基于三元组表的存储结构实现了稀疏矩阵的基本操作。 本次课程设计是本组成员共同努力而完成的，第一次进行课程设计是我们的探索过程，这个过程中，我们克服了一个个困难，在摸索中前行，我们相信通过此次课程设计我们每个人都会对数据结构这门课程有更深一步的了解。 二、需求分析 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。 2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值 本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化时，只输入非零元素的值和它所在的所在行及所在列。在对稀疏矩阵输出时，以矩阵的完整形式输出。 2.2 构造函数进行稀疏矩阵的转置并输出结果 本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。 2.3 构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵 本模块要求设计相加、减和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，定义相应的矩阵类型用于存放两个矩阵操作后的结果矩阵，这个结果矩阵的行、列数需要综合多方面情况来确定。这些函数也是整个程序的难点，需要灵活运用数组及指针的特点。 1 2.4 退出系统 本模块要求设置选项能随时结束程序的运行，本程序中采用do-while循环。程序在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。 三、项目设计 3.1结构设计 1、以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算 2、稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。 3.2算法思想 1、首先应输入矩阵的行数和列数。 2、 以“带行逻辑链接信息”的三元组顺序表表数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 3、程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教材的算法，以便提高计算效率。5.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。 4、主函数设置循环和选择语句进行运算循环和选择，进行稀疏矩阵的加法，减法和转置。 3.3模块图 建立主调函数 稀 疏 创建三元组表 矩 阵 输 出 的 基 创建矩阵函数 本 操 作 矩阵相加减、转置 2 3.4流程图 开 始 用户选择计算类型 键键 入入 A D 转置运算 加、减法运算 显示结果 Y 等待用户键入 N 继续计算 结束运算 3 四、系统实现 4.1主调函数 #include #define smax 16 typedef int datatype; typedef struct { int i, j; datatype v; } node; typedef struct() { int m ,n,t; node data[smax]; }spmatrix; 4.2三元组表建立 void print(spmatrix *a) { int k; for(k=0;kt;k++) printf("%d\t%d\t%d\n",a->data[k].i,a->data[k].j,a->dat a[k].v); } 4.3矩阵建立 void printjuzhen(spmatrix *a) { int k,p,l; int c[5][5]={{0},{0},{0},{0},{0}}; for(k=0;kt;k++) c[a->data[k].i][a->data[k].j]=a->data[k].v; for(p=0;pm;p++) 4 {for(l=0;ln;l++) printf("%d\t",c[p][l]); printf("\n"); } } 4.4矩阵相加减及转置 pmatrix * xiangjia(spmatrix *a,spmatrix *b) { spmatrix *c; int pa=0,pb=0,pc=0,sum=0; c=(spmatrix *)malloc(sizeof(spmatrix)); if((a->m==b->m)&&(a->n==b->n)) { c->m=a->m; c->n=a->n; while(pat&&pbt) { if(a->data[pa].i==b->data[pb].i) { if(a->data[pa].j==b->data[pb].j) { sum=a->data[pa].v+b->data[pb].v; if(sum) { c->data[pc].v=sum; c->data[pc].i=a->data[pa].i; c->data[pc].j=a->data[pa].j; pc++; } pa++; pb++; } else 5 { if(a->data[pa].jdata[pb].j) { if(a->data[pa].v) { c->data[pc].v=a->data[pa].v; c->data[pc].i=a->data[pa].i; c->data[pc].j=a->data[pa].j; pc++;pa++; } } else if(b->data[pb].v) { c->data[pc].v=b->data[pb].v; c->data[pc].i=b->data[pb].i; c->data[pc].j=b->data[pb].j; pc++;pb++; } } } else { if(a->data[pa].idata[pb].i) { if(a->data[pa].v) { c->data[pc].v=a->data[pa].v; c->data[pc].i=a->data[pa].i; c->data[pc].j=a->data[pa].j; pc++;pa++; } } else 6 if(b->data[pb].v) { c->data[pc].v=b->data[pb].v; c->data[pc].i=b->data[pb].i; c->data[pc].j=b->data[pb].j; pc++;pb++; } } } } else return(0); while(pat) { c->data[pc].v=a->data[pa].v; c->data[pc].i=a->data[pa].i; c->data[pc].j=a->data[pa].j; pc++;pa++; } while(pbt) { c->data[pc].v=b->data[pb].v; c->data[pc].i=b->data[pb].i; c->data[pc].j=b->data[pb].j; pc++;pb++; } c->t=pc; return(c); 7 五、系统调试 5.1主菜单输出 图1主菜单输出 8 5.2矩阵相加 图2 矩阵相加 5.3矩阵转置 图3 矩阵转置 9 5.4矩阵相减 图4矩阵相减 六、实验总结 稀疏矩阵这个课题在我们平时上课时我就感觉对于我而言这是比较困难的，矩阵的相关知识，三元组表的相关知识也一直让我比较惶恐，从拿到这个课题开始我就知道这次的课程设计必须用尽全力去认真对待。我深知团队合作的必要性，五个人的智慧总好过自己一个闭门造车，所以在课程设计过程中我们组进行了激烈地讨论，齐心协力地把这次课程设计做好。首先，我们根据课程设计所围绕的程序进行编程以及调试;其次，根据课程设计的要求进行实验目的以及实验意义的分析;再次之，进行需求分析的解决;然后将项目设计的算法思想，基本算法，主函数调用一一呈现出来。这是我们第一次进行比较专业的关于课程设计方面的运算，关于三元组表以及稀疏函数的相关应用，课程设计过程中，我在利用三元组表实现稀疏矩阵相加的程序编制中，出现了很多问题，导致最后编译、执行、链接时不能成功，后来我查找了资料，去图书馆借了相关书籍，询问老师及本组同学，经过了好多次的改进，最后，终于完成了程序的编制。 通过一周的课程设计使我对数据结构有了更深的理解，对以前学习中不明白的，不理解的都有了进一步的理解。在实际操作中遇到了很多困难，但通过找资料，请教同学 10 和老师，使我的动手能力和沟通能力都有了提高。在整个课程设计中总是在编写程序中发生错误，有时会很没耐性，但都被我一一克服了，编程一定要有耐心，同时还有认真仔细，尽量保证不出现错误。编程要有条理，不仅使自己要看懂 ，别人也能看懂，这样有利于程序的改正。 在做完这个课程设计时，心里有种说不出来的高兴，自己动手完成的设计有一种成就感，增强了自己的自信心，我相 信在今后的学习中，我会保持这种良好的心情投入学习。 七、附录 参考文献 [1]唐策善、李龙澍、黄刘生 . 数据结构——用C语言描述.高等教育出版 社.1994年12月 [2]严蔚敏、 吴伟民.数据结构第二版. 清华大学出版社. 1992 [3] 严蔚敏、 陈文博 .数据结构 .机械工业出版社.1990 11