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

＃＃大学 数据结构课程设计报告 题目：稀疏矩阵实现与应用 学生姓名: 　　 班级： 　　 学号:　　　　　　 起迄日期: 2011.6.20-2011.6.29 指导教师: 　 2010—2011年度 第 2 学期 一、需求分析 1.问题描述： 要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。 实现三元组，十字链表下的转置，乘法，加法运算。 3.输入输出 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （5）构造函数进行稀疏矩阵的转置，并输出结果。 （6）退出系统。 二、 概要设计 1.设计思路： 本实验要求在三元组，十字链表下实现稀疏矩阵的加、转、乘 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ ??????数据对象：D={aij | i=1,2,…,m; j=1,2,..,n;aij∈Elemset, m和n分别称为矩阵的行数和列数。}?数据关系：R={Row,Col}????????Row={ai,j , ai,j+1 | 1=i=m, 1=j=n-1} Col= {ai,j , ai+1,j | 1=i=m-1, 1=j=n}基本操作：??????CreateSMatrix(M)； ????????操作结果：创建稀疏矩阵M。??????DestroySMatrix(M)； ????????初始条件：稀疏矩阵M存在。 操作结果：销毁稀疏矩阵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 SparseMatrix 3.软件结构设计： （1）主程序模块：Void main（）{ 初始化； do { 接受命令； 处理命令； }while（“命令”=“退出”）； } （2）稀疏矩阵模块 ｛ 实现矩阵的相加bool AddSMatrix()； 实现矩阵的相乘bool MultSMatrix()； 实验矩阵的转置bool TransposeSMatrix()； ｝ （3）十字链表模块 ｛ 创建十字链表bool CreateSMatrix_OL(CrossList M)； 输出十字链表bool OutPutSMatrix_OL(CrossList T)； ｝ (4) 主程序模块 稀疏矩阵模块 十字链表模块 三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，基本操作typedef struct { int i, j; int e; } Triple; // 定义三元组的元素 typedef struct { Triple data[MAXSIZE + 1]; int mu, nu, tu; } TSMatrix; // 定义普通三元组对象 typedef struct { Triple data[MAXSIZE + 2]; int rpos[MAXROW + 1]; int mu, nu, tu; } RLSMatrix; // 定义带链接信息的三元组对象 typedef struct OLNode { // 定义十字链表元素 int i, j; int e; struct OLNode *right, *down; // 该非零元所在行表和列表的后继元素 } OLNode, *OLink; // 定义十字链表元素 typedef struct { // 定义十字链表对象结构体 OLink *rhead, *chead; int