数据结构课程设计报告n维矩阵乘法

1、数据结构课程设计报告水嘎小(j)呼设计题目：n维矩阵乘法：AB1专业计算机科学与技术班级计051本学生林垂敏学号29指导教师潘豪起止时间2007.12.3-2007.12.112007-2008学年第I学期具体任务功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a,b的内容，并输出两个矩阵，输出at>1结果。分步实施：1 .初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数;2 .完成最低要求：建立一个文件，可完成2维矩阵的情况；3 .进一步要求：通过键盘输入维数n0有兴趣的同学可以自己扩充系统功能。要求：1 .界面友好，函数功能要划分好2 .总体设计应画一流程图3 .程序

2、要加必要的注释4 .要提供程序测试方案5 .程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。软件环境MicrosoftVisualC+6.0三、问题的需求分析程序以二维数组作为矩阵的存储结构，通过键盘输入矩阵维数n,动态分配内存空间，创建n维矩阵。矩阵建立后再通过键盘输入矩阵的各个元素值；也可以通过文件读入矩阵的各项数据（维数及各元素值）。当要对矩阵作进一步操作（A*B或A*BA（-1）时，先判断内存中是否已经有相关的数据存在，若还未有数据存在则提示用户先输入相关数据。当要对矩阵进行求逆时，先利用矩阵可逆的充要条件：|A|!=0判断矩阵是否可逆，若矩阵的行列式

3、|A|=0则提示该矩阵为不可逆的；若|A|!二0则求其逆矩阵，并在终端显示其逆矩阵。四、算法设计思想及流程图1 .抽象数据类型ADTMatrixMulti数据对象：D=a(I,j)|i=1,2,3,n;j=1,2,n;a(i,j)£ElemSet,n为矩阵维数数据关系：R=Row,ColRow=<a(i,j),a(i,j+1)>|1<=i<=n,1<=j<=n-1Col=<a(i,j),a(i+1,j)>|1<=i<=n-1,1<=j<=n基本操作：Swap(&a,&b);初始条件：记录a,b已存

4、在。操作结果：交换记录a,b的值。CreateMatrix(n);操作结果：创建n维矩阵，返回该矩阵。Input(&M);初始条件：矩阵M已存在。操作结果：从终端读入矩阵M的各个元素值。Print(&M)初始条件：矩阵M已存在。操作结果：在终端显示矩阵M的各个元素值。ReadFromFile();操作结果：从文件读入矩阵的相关数据。Menu_Select();操作结果：返回菜单选项。MultMatrix(&M1,&M2,&R);初始条件：矩阵M1,M2R已存在。操作结果：矩阵M1,M2作乘法运算，结果放在R中DinV(&M,&V);初始条

5、件：矩阵MV已存在。操作结果：求矩阵M的逆矩阵，结果放入矩阵V中。MatrixDeterm(&M,n);初始条件：矩阵M已存在。操作结果：求矩阵M的行列式的值。ADTMatrixMulti2 .矩阵求逆算法设计思想算法采用高斯-约旦法(全选主元)求逆，主要思想如下：首先，对于k从0到n-1作如下几步： 从第k行、第k列开始的右下角子阵中选取绝对值最大的元素，并记住此元素所在的行号与列号，再通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。 主元求倒：M(k,k)=1/M(k,k)M(k,j)=M(k,j)*M(k,k)MM(i,j)=M(i,j)-M(i,k)M(i,k)=

6、-M(i,k)*M(k,k);j=0,1,n-1;j!=k*M(k,j);i,j=0,1,n-1;i,j!=k,i=0,1,n-1；i!=k最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复原则如下：在全选主元过程中，先交换的行(列)后进行恢复；原来的行(列)交换用列(行)交换来恢复。3 .矩阵行列式求值运算算法设计思想(列)各元素与其对应的代数余,n;,n;利用行列式的性质：行列式等于它的任一行子式乘积，即D=Ea(i,k)*A(i,k);k=1,2,D=Ea(k,j)*A(k,j);k=1,2,再利用函数的递归调用法实现求其值。4 .各函数间的调用关系5 .流程图否五、源代码

7、#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<malloc.h>#include<string.h>#defineYES1#defineNO0typedeffloatElemType;ElemType*A;/矩P$AElemType*B;/矩P$BElemType*R;/矩P$R,用于存放运算结果ElemType*V;/矩P$V,存放逆矩阵intn=0;/矩阵维数intflag=-1;/标记voidswap(Elem

8、Type*a,ElemType*b)/交换记录a,b的值(ElemTypec;c=*a;*a=*b;*b=c;)ElemType*CreateMatrix(intn)/创建n维矩阵，返回该矩阵(inti,j;ElemType*M;M=(ElemType*)malloc(sizeof(ElemType*)*n);if(M=NULL)exit(1);for(i=0;i<n;i+)(*(M+i)=(ElemType*)malloc(sizeof(ElemType)*n);for(j=0;j<n;j+)*(*(M+i)+j)=0;)returnM;)ElemTypeMatrixDeterm

9、(ElemType*M,intn)/*递归法求n维矩阵行列式的值，返回运算结果*/(inti,j,k,l,s;ElemType*T1;ElemType*T2;T1=CreateMatrix(n);T2=CreateMatrix(n);ElemTypeu;ElemTypevalue=0;运算结果for(i=0;i<n;i+)(for(j=0;j<n;j+)(T1ij=Mij;T2ij=Mij;if(n=2)/若为2维矩阵，则直接运算并返回运算结果(value=T200*T211-T201*T210;returnvalue;else(for(j=0;j<n;j+)/将矩阵的行列式

10、以第一行展开(u=T10j;for(i=1,l=0;i<n;i+)求矩阵行列式的余子式M(0,j)(for(k=0,s=0;k<n;k+)(if(k=j)continue;else(T2ls=T1ik;s+;l+;value=value+u*(int)pow(-1,j)*MatrixDeterm(T2,n-1);*/*行列式等于某一行的各个元素与其代数余子式的乘积之和returnvalue;intDinV(ElemType*M,ElemType*V)/*全选主元法求矩阵M的逆矩阵，结果存入矩阵V中*/inti,j,k;ElemTyped;ElemTypeu;int*JS,*IS;J

11、S=(int*)malloc(sizeof(int)*n);IS=(int*)malloc(sizeof(int)*n);u=MatrixDeterm(M,n);/返回货1阵A的行列式值if(u=0)return-1;for(i=0;i<n;i+)for(j=0;j<n;j+)Vij=Mij;for(k=0;k<n;k+)(d=0;for(i=k;i<n;i+)/找出矩阵M从Mkk开始绝对值最大的元素(for(j=k;j<n;j+)(if(fabs(Vij)>d)(d=fabs(Vij);/d记录绝对值最大的元素的值/*把绝对值最大的元素在数组中的行、列坐标

12、分别存入ISK,JSK*/ISk=i;JSk=j;if(d+1.0=1.0)return0;/所有元素都为0if(ISk!=k)/*若绝对值最大的元素不在第k行，则将矩阵ISK行的元素与k行的元素相交换*/for(j=0;j<n;j+)swap(&Vkj,&VISkj);if(JSk!=k)/*若绝对值最大的元素不在第k歹九则将矩阵JSK列的元素与k列的元素相交换*/for(i=0;i<n;i+)swap(&Vik,&ViJSk);Vkk=1/Vkk;/绝对值最大的元素求倒for(j=0;j<n;j+)/*矩阵M第k行除元素Mkk本身外都乘以M

13、kk*/if(j!=k)Vkj=Vkj*Vkk;for(i=0;i<n;i+)/*矩阵除第k行的所有元素与第k列的所有元素外,都拿本身减去Mik*Mkj,其中i,j为元素本身在矩阵的位置坐标*/if(i!=k)for(j=0;j<n;j+)if(j!=k)Vij=Vij-Vik*Vkj;for(i=0;i<n;i+)/*矩阵M第k列除元素Mkk本身外都乘以-Mkk*/if(i!=k)Vik=-Vik*Vkk;)for(k=n-1;k>=0;k-)/*根据上面记录的行ISk,列JSk信息恢复元素*/for(j=0;j<n;j+)if(JSk!=k)swap(&

14、;Vkj,&VJSkj);for(i=0;i<n;i+)if(ISk!=k)swap(&Vik,&ViISk);)free(IS);free(JS);return0;)voidMultMatrix(ElemType*M1,ElemType*M2,ElemType*R)/*矩阵M1乘M2结果存入矩阵R*/inti,j,k;for(i=0;i<n;i+)for(j=0;j<n;j+)Rij=0;)for(i=0;i<n;i+)for(j=0;j<n;j+)for(k=0;k<n;k+)(Rij=Rij+M1ik*M2kj;)voidInp

15、ut(ElemType*M)/输入矩阵M的各个元素值(inti,j;charstr10;charc='A'if(flag=1)c='B'system("cls");printf("nn输入矩阵c(%d*%d)n”,c,n,n);for(i=0;i<n;i+)(for(j=0;j<n;j+)(scanf("%f",*(M+i)+j);)flag=1;gets(str);吸收多余的字符)voidPrint(ElemType*M)/显示夕!阵M的各个元素值(inti,j;printf("t&quo

16、t;);for(i=0;i<n;i+)(for(j=0;j<n;j+)(printf("%.3f",Mij);)puts("");printf("tt");)intMenu_Select()charc;dosystem("cls");puts("tt*puts("tt|puts("tt|puts("tt|puts("tt|puts("tt|puts("tt|puts("tt|puts("tt*n维矩阵乘法器*&qu

17、ot;1.2.3.4.5.6.通过键盘输入各项数据显示矩阵A,B矩阵求逆，并显示逆矩阵求矩阵运算A*B,并显示运算结果);|");|");|");|");求矩阵运算A*BA(-1),并显示运算结果|");从文件读入矩阵A,B与维数n0.退出*");|");|");printf("tt请选择(0-6):");c=getchar();while(c<'0'|c>'6');return(c-'0');voidReadFromFile()/从指

18、定文件读入矩阵的维数及矩阵各元素的值inti,j;FILE*fp;if(fp=fopen("tx.txt","r")=NULL)puts("无法打开文件!");system("pause");exit(0);/读入矩阵维数/创建夕!阵ABVR/读入矩阵Afscanf(fp,"%d",&n);A=CreateMatrix(n);B=CreateMatrix(n);V=CreateMatrix(n);R=CreateMatrix(n);for(i=0;i<n;i+)for(j=0;j&

19、lt;n;j+)fscanf(fp,"%f",&Aij);for(i=0;i<n;i+)读入矩阵A(for(j=0;j<n;j+)(fscanf(fp,"%f",&Bij);)puts("nn读文件成功");fclose(fp);flag=1;)intmain()(inti;charc,h;charstr10;for(;)(switch(Menu_Select()(case 1: flag=-1;for(;)(system("cls");printf("nnt矩阵维数n:&qu

20、ot;);scanf("%d",&n);gets(str);if(n>0)break;else(printf("nt输入有误，请重新输入！n");puts("");system("pause");)A=CreateMatrix(n);B=CreateMatrix(n);V=CreateMatrix(n);R=CreateMatrix(n);Input(A);Input(B);break;case 2: system("cls");if(flag=-1)puts("nnt不

21、存在任何矩阵数据，请先输入数据");system("pause");break;puts("n");printf("tA=");Print(A);puts("n");printf("tB=");Print(B);puts("");system("pause");break;case 3: system("cls");if(flag=-1)puts("nnt不存在任何矩阵数据，请先输入数据");system(

22、"pause");break;for(;)printf("nnt输入需要求逆的矩阵(A/B):");h=getchar();c=getchar();/h=getchar();if(c='A'|c='a')i=DinV(A,V);if(i=-1)puts("nnt矩阵A的行列式等于0,不可逆!");system("pause");break;printf("tA=");Print(A);puts("n");printf("AA(-1)=

23、");Print(V);puts("");system("pause");break;)elseif(c='B'|c='b')(i=DinV(B,V);if(i=-1)(puts("nnt矩阵B的行列式等于0,不可逆!");system("pause");break;)printf("tB=");Print(B);puts("n");printf("BA(-1)=");Print(V);puts("&qu

24、ot;);system("pause");break;)elseputs("nnt输入有误，请重新输入！n");)break;case 4: system("cls");if(flag=-1)(puts("nnt不存在任何矩阵数据，请先输入数据");system("pause");break;)MultMatrix(A,B,R);printf("nntA*B=");Print(R);puts("");system("pause");br

25、eak;case 5: system("cls");if(flag=-1)(puts("nnt不存在任何矩阵数据，请先输入数据");system("pause");break;)i=DinV(B,V);if(i=-1)(puts("nnt矩阵B的行列式等于0,不可逆!)system("pause");break;)MultMatrix(A,V,R);printf("nnA*BA(-1)=");Print(R);puts("");system("pause&

26、quot;);break;case 6: system("cls");ReadFromFile();puts("");system("pause");break;case0:puts("tt正常退出");exit(0);break;)return0;)六、运行结果1.主界面:2.输入6,回车，从文本文件tx.txt中读入矩阵数据:3 .回车，回到主菜单界面；输入2回车，显示从文件读入的矩阵数据:A*C：,DocuaentsandSettinrg0T7iertnff234f-£ttDebufflatrixlult,eve"A=1.0002.0003.0904.0005.B006.0907.0008.9009,000D5,60SG.0004.0003.Q&S8.0697.000l.QSe2.0B09.B90，按任意健继续.4 .回车，回到主菜单界面；输入3回车，对指定矩阵求逆：（由于