稀疏矩阵的转置论文,数据结构课程设计论文.doc

广州大学数据结构课程设计数据结构课 程 设 计题 目稀疏矩阵的转置专 业网络工程班 级姓 名指导教师2013年6月27日12课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题 目: 稀疏矩阵的转置 初始条件：（1）稀疏矩阵采用三元组表示，输入一个稀疏矩阵A。（2）求出A的转置矩阵D，输出D。测试数据： 要求完成的主要任务: 课程设计报告按学校规定格式用A4纸打印，并应包含如下内容： 1. 问题描述 简述题目要解决的问题是什么。2. 设计 存储结构设计、主要算法设计（用C语言或用框图描述）、测试用例设计。3. 调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4. 程序运行结果（包括对算法改进的设想）5. 经验与体会6. 参考文献说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第17周完成。2、2011年6月28号提交打印版课程设计，源程序刻录光盘。指导教师签名： 年 月 日 目录1问题分析与任务定义12.结构设计13.算法思想14.模块划分25.算法实现25.1对矩阵进行定义25.2创建稀疏矩阵25.3求矩阵的快速转置36.系统运行结果57.经验与体会58.参考文献5广州大学松田学院数据结构课程设计稀疏矩阵的转置1问题分析与任务定义稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置。求出稀疏矩阵A的转置矩阵D，输出D。1.1稀疏矩阵采用三元组表示，输入一个稀疏矩阵A。1.2求出A的转置矩阵D，输出D。测试数据： 2.结构设计2.1.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。 2.2.稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。2.3.首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。2.4.程序可以对三元组的输入顺序加以限制，例如，按行优先。研究教材的算法，以便提高计算效率。2.5.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放3.算法思想3.1主函数设置循环和选择语句进行运算循环和选择，进行稀疏矩阵的转置和是否继续运算2个分支开关进行选择。3.2设置函数分别实现稀疏矩阵的输入，输出。3.3在数组结构体中设置存放每行第一个非零元在其数组存储结构单元的位置的存储单元，若该行无非零元，则存为04.模块划分4.1typedef struct存放各行第一个非零元在存储数组中的位置，若该行无非零元，则其rpos值为零4.2 createsmatrix(rlsmatrix *M) 矩阵输入函数，输入各行非零元及其在矩阵中的行列数4.3 FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q) 矩阵快速转置5.算法实现5.1对矩阵进行定义首先定义非零元个数的最大值和存放各行第一个非零元在存储数组中的位置#include #define MAXSIZE 100 /* 非零元个数的最大值 */ typedef struct triple int i,j; /* 行下标,列下标 */ int e; /* 非零元素值 */ triple; typedef struct tsmatrix triple dataMAXSIZE+1; /* 非零元三元组表,data0未用 */ int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */ /* 各列第一个非零元的位置表rpos0未用 */ rlsmatrix; 5.2创建稀疏矩阵创建稀疏矩阵矩阵的行数，列数，和非零元素的个数并按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值。createsmatrix(rlsmatrix *M) /* 创建稀疏矩阵M */ int e,i,m,n; M-data0.i=0; /* 为以下比较顺序做准备 */ printf(请输入矩阵的行数，列数，和非零元素的个数:); scanf(%d,&M-mu);scanf(%d,&M-nu);scanf(%d,&M-tu); for(i=1;itu;i+) printf(请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值：,i,M-mu,M-nu); scanf(%d,&m);scanf(%d,&n);scanf(%d,&e); if(mM-mu|nM-nu) /*行或列超出范围 */ printf(行或列超出范围);getch();exit(); if(mdatai-1.i|m=M-datai-1.i&ndatai-1.j) /*行或列的顺序有错*/ printf(行或列的顺序有错);getch();exit(); M-datai.i=m; M-datai.j=n; M-datai.e=e; 5.3求矩阵的快速转置 cpos为存放每列的第一个非零元素的地址，temp为中间变量对cpos对初始化，判断初值为0则为cpos赋值，然后进行转置。void transposesmatrix(rlsmatrix M,rlsmatrix *T) /* cpos存放每列的第一个非零元素的地址，temp中间变量 */ int i,m,*cpos,*temp,k=0; T-mu=M.nu; T-nu=M.mu; T-tu=M.tu; cpos=(int *)malloc(M.mu*sizeof(int); if(cpos=NULL)exit(); temp=(int *)malloc(M.mu*sizeof(int); if(temp=NULL)exit(); /* 对cpos对初始化，初值为0 */ *(cpos+1)=0; for(i=1;i=M.nu;i+) for(m=1;m1) *(cpos+i)=*(temp+i-1)+1; free(temp); for(i=1;idata*(cpos+M.datai.j).i=M.datai.j; T-data*(cpos+M.datai.j).j=M.datai.i; T-data*(cpos+M.datai.j).e=M.datai.e; (*(cpos+M.datai.j)+; free(cpos); 6.系统运行结果图3矩阵A的转置矩阵D7.经验与体会通过一周的课程设计使我对数据结构有了更深的理解，对以前学习中不明白的，不理解的都有了进一步的理解。在实际操作中遇到了很多困难，但通过找资料，请教同学和老师，使我的动手能力和沟通能力都有了提高。在整个课程设计中总是在编写程序中发生错误，有时会很没耐性，但都被我一一克服了，编程一定要有耐心，同时还有认真仔细，尽量保证不出现错误。编程要有条理，不仅使自己要看懂 ，别人也能看懂，这样有利于程序的改正。在做完这个课程设计时，心里有种说不出来的高兴，自己动手完成的设计有一种成就感，增强了自己的自信心，我相信在今后的学习中，我会保持这种良好的心情投入到各科的学习中，使我的成绩不断提高。8.参考文献1 严蔚敏 吴伟名 编著，数据结构M.，清华大学出版社