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

1、数据结构课程设计报告 n 维矩阵乘法数据结构 课程设计报告 设计题目：n 维矩阵乘法：A B1 专 业 计算机科学与技术 班 级 计本 学 生 学 号 指导教师 起止时间 2007.X.3-2007.X.11 学年第 I 学期 一、具体任务 功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵 a，b 的内容，并输出两个矩阵，输出 ab1 结果。分步实施：1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低要求：建立一个文件，可完成 2 维矩阵的情况；3.进一步要求：通过键盘输入维数 n。有兴趣的同学可以自己扩充系统功能。要求：1.界面友好，函数功能要划分好 2.总体

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

3、条件：|A|!=0 判断矩阵是否可逆，若矩阵的行列式|A|=0 则提示该矩阵为不可逆的；若|A|!=0 则求其逆矩阵，并在终端显示其逆矩阵。四、算法设计思想及流程图 1抽象数据类型 ADT MatrixMulti 数据对象：D=a(I,j)|i=1,2,3,n;j=1,2,n;a(i,j)ElemSet,n 为矩阵维数数据关系:R=Row,Col Row=|1=i=n,1=j=n-1 Col=|1=i=n-1,1=j 0?是 输入矩阵维数 n 输入矩阵 A,B 输出矩阵维数n system(“pause”);通过键盘输入需对哪个矩阵求逆,求出相应该的逆阵,并显示求得的逆阵 system(“pa

4、use”);若矩阵不可逆则返回主菜单 case 4:R=A*B 并显示矩阵 R system(“pause”);case 5:是 否 是 R=A*B(-1)显示矩阵 R system(“pause”);若 B 不可逆,则返回主菜单 case 6:从指定文件中读入矩阵数据 case 0:exit(0);结果 否 五、源代码#include#include#include#include#include#include#define YES 1#define NO 0 typedeffloat ElemType;ElemType*A;/矩阵 A ElemType*B;/矩阵 B ElemType*

5、R;/矩阵 R,用于存放运算结果 ElemType*V;/矩阵 V,存放逆矩阵 intn=0;/矩阵维数 int flag=-1;/标记 void swap(ElemType*a,ElemType*b)/交换记录 a,b 的值 ElemType c;c=*a;*a=*b;*b=c;ElemType*CreateMatrix(int n)/创建 n 维矩阵,返回该矩阵 int i,j;ElemType*M;M=(ElemType*)malloc(sizeof(ElemType*)*n);if(M=NULL)exit(1);for(i=0;in;i+)*(M+i)=(ElemType*)mallo

6、c(sizeof(ElemType)*n);for(j=0;jn;j+)*(*(M+i)+j)=0;return M;ElemType MatrixDeterm(ElemType*M,int n)/*递归法求 n 维矩阵行列式的值,返回运算结果*/int i,j,k,l,s;ElemType*T1;ElemType*T2;T1=CreateMatrix(n);T2=CreateMatrix(n);ElemType u;ElemType value=0;/运算结果 for(i=0;in;i+)for(j=0;jn;j+)T1ij=Mij;T2ij=Mij;if(n=2)/若为 2 维矩阵,则直接

7、运算并返回运算结果 value=T200*T211-T201*T210;return value;else for(j=0;jn;j+)/将矩阵的行列式以第一行展开 u=T10j;for(i=1,l=0;in;i+)/求矩阵行列式的余子式 M(0,j)for(k=0,s=0;kn;k+)if(k=j)continue;else T2ls=T1ik;s+;l+;value=value+u*(int)pow(-1,j)*MatrixDeterm(T2,n-1);/*行列式等于某一行的各个元素与其代数余子式的乘积之和*/returnvalue;int DinV(ElemType*M,ElemType

8、*V)/*全选主元法求矩阵 M 的逆矩阵,结果存入矩阵 V 中*/int i,j,k;ElemType d;ElemType u;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;in;i+)for(j=0;jn;j+)Vij=Mij;for(k=0;kn;k+)d=0;for(i=k;in;i+)/找出矩阵 M 从 Mkk开始绝对值最大的元素 for(j=k;jd)d=fabs(Vij

9、);/d 记录绝对值最大的元素的值/*把绝对值最大的元素在数组中的行、列坐标分别存入 ISK,JSK*/ISk=i;JSk=j;if(d+1.0=1.0)return 0;/所有元素都为 0 if(ISk!=k)/*若绝对值最大的元素不在第 k 行,则将矩阵 ISK行的元素与 k 行的元素相交换*/for(j=0;jn;j+)swap(&Vkj,&VISkj);if(JSk!=k)/*若绝对值最大的元素不在第 k 列,则将矩阵 JSK列的元素与 k 列的元素相交换*/for(i=0;in;i+)swap(&Vik,&ViJSk);Vkk=1/Vkk;/绝对值最大的元素求倒 for(j=0;jn

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

11、iISk);free(IS);free(JS);return 0;voidMultMatrix(ElemType*M1,ElemType*M2,ElemType*R)/*矩阵 M1 乘 M2结果存入矩阵 R*/int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)Rij=0;for(i=0;in;i+)for(j=0;jn;j+)for(k=0;kn;k+)Rij=Rij+M1ik*M2kj;voidInput(ElemType*M)/输入矩阵 M 的各个元素值 int i,j;char str10;char c=A;if(flag=1)c=B;system(“cls“)

12、;printf(“nn输入矩阵%c(%d*%d)n“,c,n,n);for(i=0;in;i+)for(j=0;jn;j+)scanf(“%f“,*(M+i)+j);flag=1;gets(str);/吸收多余的字符 void Print(ElemType*M)/显示矩阵 M 的各个元素值 int i,j;printf(“t“);for(i=0;in;i+)for(j=0;jn;j+)printf(“%.3f“,Mij);puts(“);printf(“tt“);int Menu_Select()char c;do system(“cls“);puts(“tt*n 维矩阵乘法器*“);puts

13、(“tt|1.通过键盘输入各项数据|“);puts(“tt|2.显示矩阵 A,B|“);puts(“tt|3.矩阵求逆,并显示逆矩阵|“);puts(“tt|4.求矩阵运算 A*B,并显示运算结果|“);puts(“tt|5.求矩阵运算 A*B(-1),并显示运算结果|“);puts(“tt|6.从文件读入矩阵 A,B 与维数 n|“);puts(“tt|0.退出|“);puts(“tt*“);printf(“tt 请选择(0-6):“);c=getchar();while(c6);return(c-0);void ReadFromFile()/从指定文件读入矩阵的维数及矩阵各元素的值 int

14、i,j;FILE*fp;if(fp=fopen(“tx.txt“,“r“)=NULL)puts(“无法打开文件!“);system(“pause“);exit(0);fscanf(fp,“%d“,&n);/读入矩阵维数 A=CreateMatrix(n);/创建矩阵 A B V R B=CreateMatrix(n);V=CreateMatrix(n);R=CreateMatrix(n);for(i=0;in;i+)/读入矩阵 A for(j=0;jn;j+)fscanf(fp,“%f“,&Aij);for(i=0;in;i+)/读入矩阵 A for(j=0;j0)break;else pri

15、ntf(“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 不存在任何矩阵数据,请先输入数据“);system(“pause“);break;puts(“n“);printf(“tA=“);Print(A);puts(“n“);printf(“tB=“);Print(B);puts(“);

16、system(“pause“);break;case 3:system(“cls“);if(flag=-1)puts(“nnt 不存在任何矩阵数据,请先输入数据“);system(“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“);print

17、f(“A(-1)=“);Print(V);puts(“);system(“pause“);break;else if(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(“B(-1)=“);Print(V);puts(“);system(“pause“);break;else puts(“nnt 输入有误,请重新输入!n“);break;case 4:system(“cls“);if(flag=-1)put

18、s(“nnt 不存在任何矩阵数据,请先输入数据“);system(“pause“);break;MultMatrix(A,B,R);printf(“nntA*B=“);Print(R);puts(“);system(“pause“);break;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);pri

19、ntf(“nnA*B(-1)=“);Print(R);puts(“);system(“pause“);break;case6:system(“cls“);ReadFromFile();puts(“);system(“pause“);break;case 0:puts(“tt 正常退出“);exit(0);break;return0;六、运行结果 1主界面：2输入 6，回车，从文本文件 tx.txt 中读入矩阵数据：3回车，回到主菜单界面；输入 2 回车，显示从文件读入的矩阵数据：4回车，回到主菜单界面；输入 3 回车，对指定矩阵求逆：（由于这里矩阵 A 是不可逆的，因此仅以矩阵B 为例）5回车

20、，回到主菜单界面；输入 4 回车，求矩阵运算 A*B：6回车回到主菜单界面，输入 5 回车，求 A*B(-1)的值：7回车回到主菜单界面，输入 0 回车，退出程序；如果需要自定矩阵维数及各元素值，请利用主菜单里的 1 号功能自行输入数据，再进行以上几种运算操作。七、收获及体会 通过这次课程设计，让我再次复习了线性代数里矩阵的相关知识，比如 n 维矩阵的求逆、矩阵可逆的充分必要条件（|A|！=0）、矩阵与矩阵的乘法运算、行列式求值方法等。同样的，还让我复习了大量 C 语言里有关数组的一些重要概念，比如多维数组的动态分配问题、数组与指针的关系等。记得在这个学期新开设的单片机基础课上，吴涛老师曾多次

21、强调，让我们一定要经常锻炼自己的编程能力，他常对我们说：“编程是思维的体操。”尽管我在这方面的能力 和实力非常得有限，也远远不及班上的其他同学，但我通过这次课程设计充分体会到了这句话的精华。电脑程序作为人体大脑思维的延伸，程序的功能也会因为大脑思维的不断完善而变得更加强大，所以我决定今后要加强在这方面的锻炼和学习，以此来激励自己不断前进！八、参考文献 数据结构（C 语言版）严蔚敏，吴伟民 编著 清华大学出版社 C 语言程序设计洪维恩 编著 中国铁道出版社 C 语言程序设计教程谭浩强 张基温 唐永炎 编著 高等教育出版社 工程数学线性代数 第四版同济大学应用数学系 编 高等教育出版社 计本 2007-12