数据结构——稀疏矩阵运算器.doc

数据结构 课程设计报告 设计题目：稀疏矩阵运算器 年 级 班 级 姓 名 学 号 指导教师 起止时间 2010 年 二 学期 一、实验目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 二、问题描述（具体任务） 设计、实现两个稀疏矩阵在十字链表表示方法下的相加、相减、相乘。稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行储存和计算可以大大节省储存空间，提高计算效率。实现一个能进行称稀疏矩阵基本运算的运算器。 三、需求分析 该程序所做的工作的是稀疏矩阵运算器，实现两个稀疏矩阵的基本运算。此程序规定： 1、按照压缩存储的概念，只存储稀疏矩阵的非零元，以两个三元组｛i,j,e}来表示矩阵的非零元的行，列和数值，就确定了一个非零元．由此，稀疏矩阵可由表示非零元的三元数组及行列数确定 2、用户输入数据作为三元组的行，列和非零元的个数，用空格隔开．并输入非零元的行，列和数值 3、本程序只对两个矩阵进行四则运算，所的结果矩阵应该另生成，用十字链表存放，并放入新的矩阵中，只要对矩阵求解就能求出答案． 四、算法设计思想及流程图 用十字链表存储方式实现稀疏矩阵的基本运算，此程序用到以下函数： void CreateSMatrix(CrossList R) //创建储存稀疏矩阵 void PrintSMatrix(CrossList R) //输出十字链表的函数 void MultSMatrix(CrossList M,CrossList N,CrossList Q) //实现矩阵乘法 int AddMatrix(CrossList M,CrossList N,CrossList Q) //实现矩阵加法 int SubtSMatrix(CrossList M,CrossList N,CrossList Q) //实现矩阵减法 void main()//主函数调用以上函数来实现其功能： 首先调用CreateSMatrix()创建矩阵M和N，并输入稀疏矩阵的行数，列数，非零元素个数，通过PrintSMatrix()输出矩阵M和N，根据提示选择相应的运算，当进行加或减运算时，如果两个矩阵的行和列不相等时，就无法得到结果，并出现提示错误信息，当进行乘法运算时，要求矩阵M的列数必须等于矩阵N的行数，否则无法进行乘法运算，为了进行多种运算通过主函数的Do----While循环来实现，退出循环条件是输入”+”、”-”、”*”以外的任意字符即可退出循环。 五、C语言源代码 #includestdio.h #includestdlib.h #define OVERFLOW -1 #define OK 1 #define NULL 0 //建立十字链表 typedef struct OLNode { int row,col; //该非零元的行和列下标 int e; struct OLNode *right,*down; //该非零元所在行表和列表的后继链域 }OLNode,*OLink; typedef struct{ OLink *rhead,*chead; //行和列链表头指针向量基址由CreateSMatrix分配 int mu,nu,tu; //系数矩阵的行数，列数和非零元个数 }CrossList; // 创建储存稀疏矩阵 void CreateSMatrix(CrossList R) { int m,n,t,i,j,k,a; OLink p,q; if(R.rhead) { R.rhead=NULL; R.chead=NULL; R.mu=0; R.nu=0; R.tu=0; } printf(\n请输入稀疏矩阵的行数 列数 非零元个数:); scanf(%d %d %d,m,n,t); R.mu=m; R.nu=n; R.tu=t; if(!(R.rhead=(OLink *)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW); i