数据结构课程设计实验报告内容名称：稀疏矩阵的基本操作成员1：09213020-陈东成员2：09213040-蔡丹班级：09数31教师：***江苏师范大学数学科学学院目录1.序言 (3)1.1数据结构背景 (3)1.2课程设计目的 (3)1.3 课程名称 (3)1.4设计要求 (3)1.5设计说明 (3)2．课程任务设计说明书 (5)3.需求分析 (6)3.1题目名称 (6)3.2题目内容 (6)3.3题目分析 (6)4．概要设计 (7)4.1稀疏矩阵存储结构 (7)4.2.稀疏矩阵的基本操作 (7)4.3各模块设计要求 (8)4.4总体功能流程图 (9)4.4.1存储结构流程图 (9)4.4.2稀疏矩阵基本操作流程图 (10)5．详细设计 (11)5.1设计原理 (11)5.2基本函数实现流程图 (13)6．主要函数代码 (21)7．调试与操作说明 (27)7.1操作说明 (27)7.2调试结果………………………………………………………………………………. ..287.3结果分析 (31)8.设计体会 (32)9.参考文献 (32)10.分工说明 (33)1.序言1.1数据结构背景数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。
该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。
通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。
数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。
学习数据结构的最终目的是为了获得求解问题的能力。
对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。
基于此原因，我们开设了数据结构课程设计。
针对数据结构课程的特点，着眼于培养我们的实践能力。
实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。
相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。
1.2课程设计的目的巩固和深刻理解“数据结构（C语言版）”课程所讲解的C语言作为数据结构的算法的描述，掌握对数据的存储结构和算法进行描述时，尽量考虑C 语言的特色。
培养学生独立工作和创新思维的能力，取得设计与调试的实践经验。
提高和加强计算机应用及软件开发能力。
通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定义数据的抽象数据类型。
分模块对题目进行设计，强化学生对C语言的掌握和对数据结构的选择及掌握。
通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。
促使学生养成良好的编程习惯，以及让学生对书本上的知识进行了实践。
算法与数据结构这门课是计算机科学中一门综合性的专业基础课1.2课程名称：数据结构1.3设计要求学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，算法要求用C语言完成。
学生独立思考解决问题为主，教师指导为辅，结合上机操作，完成指定的任务，撰写课程设计报告。
要求源代码有足够的注释，能达到题目要求，并使人能看得懂你的代码。
1.5设计说明此课程设计着重在于让我们理解如何利用C语言来实现稀疏矩阵的一些具体操作，里面代码完全采用C语言描述，包括了稀疏矩阵的建立，稀疏矩阵的输出，两个稀疏矩阵的相加，以及如何求出相应矩阵的转置矩阵。
由于在我们课本中除了学习了稀疏矩阵的建立，相加，转置外，我们还接触了稀疏矩阵的销毁，稀疏矩阵的复制，稀疏矩阵的相减，稀疏矩阵的相乘，为了将有关稀疏矩阵的几个基本操作全部实现一遍，我们在完成原有题目的要求下，拓展了下题目内容，将稀疏矩阵的销毁，稀疏矩阵的复制，稀疏矩阵的相减，稀疏矩阵的相乘补充进去，这样我们更觉得此次课程设计的完整性。
而且，为了使读者更容易理解代码含义，程序的源代码基本与书本同步，思想方法也基本与书本介绍的吻合！2．课程设计任务书3．需求分析3.1题目名称：稀疏矩阵的操作3.2题目内容：1.稀疏矩阵采用三元组表示；2.求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；3.求出A的转置矩阵D，输出D；题目拓展：4.稀疏矩阵的销毁5.稀疏矩阵的快速转置6.求两个具有相同行列数的稀疏矩阵A和B的相减矩阵C，并输出C；7.求两个具有相同行列数的稀疏矩阵A和B的相乘矩阵C，并输出C；3.3题目分析：通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。
有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便。
然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素。
有的为了节省存储空间，可以对这类矩阵进行压缩存储。
所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。
我们可以运用压缩存储的方式来实现稀疏矩阵的几个基本操作。
4.概要设计4.1稀疏矩阵存储结构#define MAXSIZE 12500 //假设非零元个数的最大值为12500 typedef struct{int i ，j；//该非零元的行下标和列下标ElemeType e；}Triple;Typedef struct{Triple data[MAXSIZE+1]；//非零元三元组表，data[0]未用int mu ，nu，tu；//矩阵的行数，列数和非零元个数}TSMatrix；4.2.稀疏矩阵的基本操作CreateSMatrix(&M);操作结果：创建稀疏矩阵M。
DestroySMatrix(&M)；初始条件：稀疏矩阵M存在；操作结果：销毁稀疏矩阵M。
PrintSMatrix( M)初始条件：稀疏矩阵M存在。
操作结果：输出稀疏矩阵M。
CopySMatrix(TSMatrix M,TSMatrix *T)初始条件：稀疏矩阵M存在操作结果：由稀疏矩阵M复制得到T。
AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q=M+N.SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q=M-N.MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q=M*N.TransposeSMatrix(TSMatrix M,TSMatrix *T)初始条件：稀疏矩阵M存在操作结果：由稀疏矩阵M的转置矩阵T4.3.各模块设计要求1.初始函数建立稀疏矩阵及初始化稀疏矩阵本模块要求设计函数在三元组顺序表中建立稀疏矩阵并初始化。
首先要定义三元组表结构体类型，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别需要注意在三元组表存储稀疏矩阵的时候，要对变量进行动态的地址分配2.转置函数进行稀疏矩阵的转置本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏矩阵的转置只对一个矩阵进行操作，所以实现起来难度并不是很大，函数也比较容易编写。
在编写函数时，首先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。
3.和运算函数进行两个稀疏矩阵相加运算本模块要求设计加法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵相加要求两个矩阵一定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加的结果矩阵，这个结果矩阵的行数列数要综合多方面来确定。
4.积运算函数进行两个稀疏矩阵的乘法运算本模块要求设计乘法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，如果A矩阵的行（列）和B矩阵列（行）数值相等，则能完成相应的乘法运算，定义相应的矩阵类型用于存放两个稀疏矩阵相乘之后的结果矩阵，并且调用输出函数完成乘积的输出5输出函数完成矩阵的输出本模块要求完成对稀疏矩阵的输出功能，实现起来比较简单，完成矩阵的转置输出，矩阵的加法，减法，乘法运算输出相应的和，差，积，都要调用输出函数。
4.4总体功能流程图4.4.1存储结构流程图：4.4.2稀疏矩阵基本操作流程图：5．详细设计5.1设计原理1.三元组顺序表：假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式——我们称之为三元组顺序表。
因此，data域中表示非零的三元组是以行序为主序顺序排列的。
按照压缩存储的概念，只存储稀疏矩阵的非零元。
因此，除了存储非零元的值外，还必须同时记下它所在行和列的位置（i，j）。
反之，一个三元组（i，j，aij）唯一确定了矩阵A的一个非零元。
由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
例如，下列三元组表：（（1,2,1），（1,3,9），（3,1,3），（3,6,14），（4,3,4），（5,2,8），（6,1,5），（6,4,7）），于是稀疏矩阵A可以描述为：0 1 9 0 0 0 00 0 0 0 0 0 0A= 3 0 0 0 0 4 00 0 4 0 0 0 00 8 0 0 0 0 05 0 0 7 0 0 02.矩阵转置：转置运算是一种简单的矩阵运算。
对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T(i,j)=M(j,i)。
显然，一个稀疏矩阵的转置仍为稀疏矩阵：要想实现矩阵之间的转置，只要做到：(1)将矩阵的行列值相互交换；(2)将每个三元组中的i和j相互调换；(3)重排三元组之间的次序便可实现矩阵的转置。
前二条内容是容易做到的，关键是如何实现第三条，我们有2种方法，在这我们使用以下方法实现：我们按照矩阵M的列序来进行转置，为了找到M的每一列中所有的非零元素，需要对其三元组表a.data 从第一行起整个扫描一遍，由于a.data是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应用的顺序。
a.datab.data3 .两个稀疏矩阵相加：比较满足条件（行数及列数都相同的2个矩阵）的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素e相加，保持i，j不变存储在新的三元组中，不等的则分别储存在此新三元组中。