数据结构+课程设计+稀疏矩阵的操作(计算机学院)

计算机科学技术学院学生课程设计（论文）题目：学生姓名：学号：所在院(系)：专业：班级：指导教师：职称：年月日计算机科学技术学院本科学生课程设计任务书题目稀疏矩阵的操作1、课程设计的目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）基本功能要求：（1）稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。（2）求出A的转置矩阵D，输出D。测试数据：0908070000045010A0000010906007002B3、主要参考文献［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003．［2］《数据结构题集》，严蔚敏，清华大学出版社，2005．［3］《数据结构》（C语言版），刘大有，高等教育出版社，2004．［4］《DataStructurewithC++》，WilliamFord．WilliamTopp，清华大学出版社，2003．4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分析和结果第5天课程设计报告和总结指导教师（签字）日期年月日教研室意见：年月日学生（签字）：接受任务时间：年月日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能力水平35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。06设计（实验）能力，方案的设计能力5能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析能力（综合分析能力、技术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、设计（论文）规范化程度5符合本专业相关规范或规定要求；规范化符合本文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名：年月日稀疏矩阵的操作1.课程设计的目的本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。利用三元组实现稀疏矩阵的有关算法。2．问题描述2.1稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。2.2求出A的转置矩阵D，输出D。3.基本要求稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。4.结构设计4.1.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。4.2.稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。4.3.首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。4.4.程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教材的算法，以便提高计算效率。5.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放5.算法思想5.1．主函数设置循环和选择语句进行运算循环和选择，进行稀疏矩阵的加法，减法，乘法，转置和是否继续运算5个分支开关进行运算选择。5.2．设置函数分别实现稀疏矩阵的输入，输出，加法，减法，乘法。5.3．在数组结构体中设置存放每行第一个非零元在其数组存储结构单元的位置的存储单元，若该行无非零元，则存为06.模块划分6.1typedefstruct存放各行第一个非零元在存储数组中的位置，若该行无非零元，则其rpos[]值为零6.2createsmatrix(rlsmatrix*M)矩阵输入函数，输入各行非零元及其在矩阵中的行列数6.3FasttransposeRLSMatrix(RLSMatrixM,RLSMatrix*Q)矩阵快速转置6.4HeRLSMatrix(RLSMatrix*M,RLSMatrix*N,RLSMatrix*Q)矩阵求和6.5ChaRLSMatrix(RLSMatrix*M,RLSMatrix*N,RLSMatrix*Q)矩阵求差6.6JiRLSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix*Q)矩阵求积7.算法实现7.1首先定义非零元个数的最大值和存放各行第一个非零元在存储数组中的位置#includestdio.h#defineMAXSIZE100/*非零元个数的最大值*/typedefstructtriple{inti,j;/*行下标,列下标*/inte;/*非零元素值*/}triple;typedefstructtsmatrix{tripledata[MAXSIZE+1];/*非零元三元组表,data[0]未用*/intmu,nu,tu;/*矩阵的行数、列数和非零元个数*//*各列第一个非零元的位置表rpos[0]未用*/}rlsmatrix;7.2创建稀疏矩阵矩阵的行数，列数，和非零元素的个数并按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值。createsmatrix(rlsmatrix*M){/*创建稀疏矩阵M*/inte,i,m,n;M-data[0].i=0;/*为以下比较顺序做准备*/printf(请输入矩阵的行数，列数，和非零元素的个数:);scanf(%d,&M-mu);scanf(%d,&M-nu);scanf(%d,&M-tu);for(i=1;i=M-tu;i++){printf(请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：,i,M-mu,M-nu);scanf(%d,&m);scanf(%d,&n);scanf(%d,&e);if(m1||mM-mu||n1||nM-nu)/*行或列超出范围*/{printf(行或列超出范围);getch();exit();}if(mM-data[i-1].i||m==M-data[i-1].i&&n=M-data[i-1].j)/*行或列的顺序有错*/{printf(行或列的顺序有错);getch();exit();}M-data[i].i=m;M-data[i].j=n;M-data[i].e=e;}}7.3求矩阵的快速转置cpos为存放每列的第一个非零元素的地址，temp为中间变量对cpos对初始化，判断初值为0则为cpos赋值，然后进行转置。voidtransposesmatrix(rlsmatrixM,rlsmatrix*T){/*cpos存放每列的第一个非零元素的地址，temp中间变量*/inti,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;m=M.tu;m++){if(M.data[m].j==i)k++;}temp[i]=k;if(i==1&&k!=0)*(cpos+i)=1;/*为cpos赋值*/if(i1)*(cpos+i)=*(temp+i-1)+1;}free(temp);for(i=1;i=M.tu;i++)/*进行转置*/{T-data[*(cpos+M.data[i].j)].i=M.data[i].j;T-data[*(cpos+M.data[i].j)].j=M.data[i].i;T-data[*(cpos+M.data[i].j)].e=M.data[i].e;(*(cpos+M.data[i].j))++;}free(cpos);}7.3矩阵的相乘设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零元。定义Qe为矩阵Q的临时数组，矩阵Q的第i行j列的元素值存于*(Qe+(M.data[i].i-1)*N.nu+N.data[j].j)中，初值为0，结果累加到Qe，*Qe矩阵中，因为M的每一行和N的每一列相乘都是T的一个元素，不管它是零或非零，当M的第一行和N的第一列相乘则得T的第一个元素；当M的第一行和N的第二列相乘则得T的第二个元素，M的第i行和N的第j列相乘则得T的第p个元素；根据归纳法得p=(i-1)*N的列数+j。multsmatrix(rlsmatrixM,rlsmatrixN,rlsmatrix*T){inti,j,Qn=0;int*Qe;if(M.nu!=N.mu){printf(两矩阵无法相乘);getch();exit();}T-mu=M.mu;T-nu=N.nu;Qe=(int*)malloc(M.mu*N.nu*sizeof(int));/*Qe为矩阵Q的临时数组*/for(i=1;i=M.mu*N.nu;i++)*(Qe+i)=0;/*矩阵Q的第i行j列的元素值存于*(Qe+(M.data[i].i-1)*N.nu+N.data[j].j)中，初值为0*/for(i=1;i=M.tu;i++)/*结果累加到Qe*/for(j=1;j=N.tu;j++)if(M.data[i].j==N.data[j].i)*(Qe+(M.data[i].i-1)*N.nu+N.data[j].j)+=M.data[i].e*N.data[j].e;for(i=1;i=M.mu;i++)/*Qe矩阵中，因为M的每一行和N的每一列相乘都是T的一个元素，不管它是零或非零*/for(j=1;j=N.nu;j++)/*当M的第一行和N的第一列相乘则得T的第一个元素；当M的第一行和N的第二列相乘则得T的第二个元素；……*/if(*(Qe+(i-1)*N.nu+j)!=0)/*……当M的第i行和N的第j列相乘则得T的第p个元素；根据归纳法得p=(i-1)*N的列数+j*/{Qn++;//非零元个数加一T-data[Qn].e=*(Qe+(i-1)*N.nu+j);T-data[Qn].i=i;T-data[Qn].j=j;}free(Qe);T-tu=Qn;return;}7.4矩阵的相加编写一个求两个对称矩阵相加运算的函数。设对称矩阵的数据元素为整数类型，对称矩阵采用压缩存储方法存储，要求和矩阵采