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

数据结构课程设计设计题目：n维矩阵乘法：AB－1专业计算机科学与技术班级计本学生学号指导教师起止时间2007.X.3-2007.X.112007-2008学年第I学期1、具体任务功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab－1结果。分步实施：1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低：建立一个文件，可完成2维矩阵的情况；3.进一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。要求：1.界面友好，函数功能要划分好2.总体设计应画一图3.程序要加必要的注释4.要提供程序测试5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。2、软件环境MicrosoftVisualC++6.03、问题的需求分析程序以二维数组作为矩阵的存储结构，通过键盘输入矩阵维数n，动态分配内存空间，创建n维矩阵。矩阵建立后再通过键盘输入矩阵的各个元素值；也可以通过文件读入矩阵的各项数据（维数及各元素值）。当要对矩阵作进一步操作（A*B或A*B^(-1)）时，先判断内存中是否已经有相关的数据存在，若还未有数据存在则提示用户先输入相关数据。当要对矩阵进行求逆时，先利用矩阵可逆的充要条件：|A|!=0判断矩阵是否可逆，若矩阵的行列式|A|==0则提示该矩阵为不可逆的；若|A|!=0则求其逆矩阵，并在终端显示其逆矩阵。4、算法设计思想及流程图1．抽象数据类型ADTMatrixMulti{数据对象：D={a(I,j)|i=1,2,3,…,n;j=1,2,…,n;a(i,j)∈ElemSet,n为矩阵维数}数据关系:R={Row,Col}Row={<a(i,j),a(i,j+1)>|1<=i<=n,1<=j<=n-1}Col={<a(i,j),a(i+1,j)>|1<=i<=n-1,1<=j<=n}基本操作:Swap(&a,&b);初始条件：a,b已存在。操作结果：交换记录a,b的值。CreateMatrix(n);操作结果：创建n维矩阵，返回该矩阵。Input(&M);初始条件：矩阵M已存在。操作结果：从终端读入矩阵M的各个元素值。Print(&M)初始条件：矩阵M已存在。操作结果：在终端显示矩阵M的各个元素值。ReadFromFile();操作结果：从文件读入矩阵的相关数据。Menu_Select();操作结果：返回菜单选项。MultMatrix(&M1,&M2,&R);初始条件：矩阵M1，M2，R已存在。操作结果：矩阵M1，M2作乘法运算，结果放在R中。DinV(&M,&V);初始条件：矩阵M，V已存在。操作结果：求矩阵M的逆矩阵,结果放入矩阵V中。MatrixDeterm(&M,n);初始条件：矩阵M已存在。操作结果：求矩阵M的行列式的值。}ADTMatrixMulti2．矩阵求逆算法设计思想算法采用高斯-约旦法（全选主元）求逆，主要思想如下：首先，对于k从0到n-1作如下几步：1从第k行、第k列开始的右下角子阵中选取绝对值最大的元素，并记住此元素所在的行号与列号，再通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。2主元求倒：M(k,k)=1/M(k,k)3M(k,j)=M(k,j)*M(k,k)；j=0,1,…,n-1;j!=k4M(i,j)=M(i,j)–M(i,k)*M(k,j)；i,j=0,1,…,n-1;i,j!=k5M(i,k)=-M(i,k)*M(k,k)，i=0,1…,n-1；i!=k最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复原则如下：在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。3.矩阵行列式求值运算算法设计思想利用行列式的性质：行列式等于它的任一行（列）各元素与其对应的代数余子式乘积，即D=∑a(i,k)*A(i,k);k=1,2,…,n;D=∑a(k,j)*A(k,j);k=1,2,…,n;再利用函数的递归调用法实现求其值。4．各函数间的调用关系5.流程图5、源代码#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<malloc.h>#include<string.h>#defineYES1#defineNO0typedeffloatElemType;ElemType**A;//矩阵AElemType**B;//矩阵BElemType**R;//矩阵R,用于存放运算结果ElemType**V;//矩阵V,存放逆矩阵intn=0;//矩阵维数intflag=-1;//标记voidswap(ElemType*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(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++){T1[i][j]=M[i][j];T2[i][j]=M[i][j];}}if(n==2)//若为2维矩阵,则直接运算并返回运算结果{value=T2[0][0]*T2[1][1]-T2[0][1]*T2[1][0];returnvalue;}else{for(j=0;j<n;j++)//将矩阵的行列式以第一行展开{u=T1[0][j];for(i=1,l=0;i<n;i++)//求矩阵行列式的余子式M(0,j){for(k=0,s=0;k<n;k++){if(k==j)continue;else{T2[l][s]=T1[i][k];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;JS=(int*)malloc(sizeof(int)*n);IS=(int*)malloc(sizeof(int)*n);u=MatrixDeterm(M,n);//返回矩阵A的行列式值if(u==0)return-1;for(i=0;i<n;i++)for(j=0;j<n;j++)V[i][j]=M[i][j];for(k=0;k<n;k++){d=0;for(i=k;i<n;i++)//找出矩阵M从M[k][k]开始绝对值最大的元素{for(j=k;j<n;j++){if(fabs(V[i][j])>d){d=fabs(V[i][j]);//d记录绝对值最大的元素的值/*把绝对值最大的元素在数组中的行、列坐标分别存入IS[K],JS[K]*/IS[k]=i;JS[k]=j;}}}if(d+1.0==1.0)return0;//所有元素都为0if(IS[k]!=k)/*若绝对值最大的元素不在第k行,则将矩阵IS[K]行的元素与k行的元素相交换*/for(j=0;j<n;j++)swap(&V[k][j],&V[IS[k]][j]);if(JS[k]!=k)/*若绝对值最大的元素不在第k列,则将矩阵JS[K]列的元素与k列的元素相交换*/for(i=0;i<n;i++)swap(&V[i][k],&V[i][JS[k]]);V[k][k]=1/V[k][k];//绝对值最大的元素求倒for(j=0;j<n;j++)/*矩阵M第k行除元素M[k][k]本身外都乘以M[k][k]*/if(j!=k)V[k][j]=V[k][j]*V[k][k];for(i=0;i<n;i++)/*矩阵除第k行的所有元素与第k列的所有元素外,都拿本身减去M[i][k]*M[k][j],其中i,j为元素本身在矩阵的位置坐标*/if(i!=k)for(j=0;j<n;j++)if(j!=k)V[i][j]=V[i][j]-V[i][k]*V[k][j];for(i=0;i<n;i++)/*矩阵M第k列除元素M[k][k]本身外都乘以-M[k][k]*/if(i!=k)V[i][k]=-V[i][k]*V[k][k];}for(k=n-1;k>=0;k--)/*根据上面记录的行IS[k],列JS[k]信息恢复元素*/{for(j=0;j<n;j++)if(JS[k]!=k)swap(&V[k][j],&V[JS[k]][j]);for(i=0;i<n;i++)if(IS[k]!=k)swap(&V[i][k],&V[i][IS[k]]);}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++){R[i][j]=0;}}for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++){R[i][j]=R[i][j]+M1[i][k]*M2[k][j];}}}}voidInput(ElemType**M)//输入矩阵M的各个元素值{inti,j;charstr[10];charc='A';if(flag==1)c='B';system("cls");printf("\n\n输入矩阵%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");for(i=0;i<n;i++){for(j=0;j<n;j++){printf("%.3f",M[i][j]);}puts("");printf("\t\t");}}intMenu_Select(){charc;do{system("cls");puts("\t\t*************n维矩阵乘法器*************");puts("\t\t|1.通过键盘输入各项数据|");puts("\t\t|2.显示矩阵A,B|");puts("\t\t|3.矩阵求逆,并显示逆矩阵|");puts("\t\t|4.求矩阵运算A*B,并显示运算结果|");puts("\t\t|5.求矩阵运算A*B^(-1),并显示运算结果|");puts("\t\t|6.从文件读入矩阵A,B与维数n|");puts("\t\t|0.退出|");puts("\t\t***************************************");printf("\t\t请选择(0-6):");c=getchar();}while(c<'0'||c>'6');return(c-'0');}voidReadFromFile()//从指定文件读入矩阵的维数及矩阵各元素的值{inti,j;FILE*fp;if((fp=fopen("tx.txt","r"))==NULL){puts("无法打开文件!!!");system("pause");exit(0);}fscanf(fp,"%d",&n);//读入矩阵维数A=CreateMatrix(n);//创建矩阵ABVRB=CreateMatrix(n);V=CreateMatrix(n);R=CreateMatrix(n);for(i=0;i<n;i++)//读入矩阵A{for(j=0;j<n;j++){fscanf(fp,"%f",&A[i][j]);}}for(i=0;i<n;i++)//读入矩阵A{for(j=0;j<n;j++){fscanf(fp,"%f",&B[i][j]);}}puts("\n\n读文件成功");fclose(fp);flag=1;}intmain(){inti;charc,h;charstr[10];for(;;){switch(Menu_Select()){case1:flag=-1;for(;;){system("cls");printf("\n\n\t矩阵维数n:");scanf("%d",&n);gets(str);if(n>0)break;else{printf("\n\t输入有误,请重新输入!\n");puts("");system("pause");}}A=CreateMatrix(n);B=CreateMatrix(n);V=CreateMatrix(n);R=CreateMatrix(n);Input(A);Input(B);break;case2:system("cls");if(flag==-1){puts("\n\n\t不存在任何矩阵数据,请先输入数据");system("pause");break;}puts("\n");printf("\tA=");Print(A);puts("\n");printf("\tB=");Print(B);puts("");system("pause");break;case3:system("cls");if(flag==-1){puts("\n\n\t不存在任何矩阵数据,请先输入数据");system("pause");break;}for(;;){printf("\n\n\t输入需要求逆的矩阵(A/B):");h=getchar();c=getchar();//h=getchar();if(c=='A'||c=='a'){i=DinV(A,V);if(i==-1){puts("\n\n\t矩阵A的行列式等于0,不可逆!");system("pause");break;}printf("\tA=");Print(A);puts("\n");printf("A^(-1)=");Print(V);puts("");system("pause");break;}elseif(c=='B'||c=='b'){i=DinV(B,V);if(i==-1){puts("\n\n\t矩阵B的行列式等于0,不可逆!");system("pause");break;}printf("\tB=");Print(B);puts("\n");printf("B^(-1)=");Print(V);puts("");system("pause");break;}elseputs("\n\n\t输入有误,请重新输入!\n");}break;case4:system("cls");if(flag==-1){puts("\n\n\t不存在任何矩阵数据,请先输入数据");system("pause");break;}MultMatrix(A,B,R);printf("\n\n\tA*B=");Print(R);puts("");system("pause");break;case5:system("cls");if(flag==-1){puts("\n\n\t不存在任何矩阵数据,请先输入数据");system("pause");break;}i=DinV(B,V);if(i==-1){puts("\n\n\t矩阵B的行列式等于0,不可逆!");system("pause");break;}MultMatrix(A,V,R);printf("\n\nA*B^(-1)=");Print(R);puts("");system("pause");break;case6:system("cls");ReadFromFile();puts("");system("pause");break;case0:puts("\t\t正常退出");exit(0);break;}}return0;}6、运行结果1．主界面：2．输入6，回车，从文本文件tx.txt中读入矩阵数据：3．回车，回到主菜单界面；输入2回车，显示从文件读入的矩阵数据：4．回车，回到主菜单界面；输入3回车，对指定矩阵求逆：（由于这里矩阵A是不可逆的，因此仅以矩阵B为例）5．回车，回到主菜单界面；输入4回车，求矩阵运算A*B：6．回车回到主菜单界面，输入5回车，求A*B^(-1)的值：7．回车回到主菜单界面，输入0回车，退出程序；如果需要自定矩阵维数及各元素值，请利用主菜单里的1号功能自行输入数据，再进行以上几种运算操作。7、收获及体会通过这次课程设计，让我再次复习了线性代数里矩阵的相关知识，比如n维矩阵的求逆、矩阵可逆的充分必要条件（|A|！=0）、矩阵与矩阵的乘法运算、行列式求值方法等。同样的，还让我复习了大量C语言里有关数组的一些重要概念，比如多维数组的动态分配问题、数组与指针的关系等。记得在这个学期新开设的单片机基础课上，吴涛老师曾多次强调，让我们一定要经常锻炼自己的编程能力，他常对我们说：“编程是思维的体操。”尽管我在这方面的能力和实力非常得有限，也远远不及班上的其他同学，但我通过这次课程设计充分体会到了这句话的精华。电脑程序作为人体大脑思维的延伸，程序的功能也会因为大脑思维的不断完善而变得更加强大，所以我决定今后要加强在这方面的锻炼和学习，以此来激励自己不断前进！8、参考文献《数据结构（C语言版）》严蔚敏，吴伟民编著清华大学出版社《C语言程序设计》洪维恩编著中国铁道出版社《C语言程序设计教程》谭浩强张基温唐永炎编著高等教育出版社《工程数学——线性代数第四版》同济大学应用数学系编高等教育出版社计本2007-12Main()ReadFromFile()DinV()Swap()Print()Menu_Select()MatrixDeterm()CreateMatrix()MultMatrix()Input()否否是否是是否是否否是开始switch(Menu_Select())case1:case3:case2:n>0?是输入矩阵维数n输入矩阵A,B输出矩阵维数nsystem(“pause”);通过键盘输入需对哪个矩阵求逆,求出相应该的逆阵,并显示求得的逆阵system(“pause”);若矩阵不可逆则返回主菜单case4:R=A*B并显示矩阵Rsystem(“pause”);case5:是否是R=A*B^(-1)显示矩阵Rsystem(“pause”);若B不可逆,则返回主菜单case6:从指定文件中读入矩阵数据case0:exit(0);结果否PAGE13