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

数据结构课程设计报告n维矩阵乘法 数据结构 课程设计报告 设计题目：‎ n维矩阵乘法：A B－1专 计算机科学与技术 计本学 指导教师起止时间 ‎2007.X.3-2007.X.11‎ 学年第 学期 一、‎ 具体任务 功能：‎ 设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab－1结果。‎ 分步实施：‎ ‎1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；‎ ‎2.完成最低要求：建立一个文件，可完成2维矩阵的情况；‎ ‎3.进一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。‎ 要求：‎ ‎1.界面友好，函数功能要划分好 ‎2.总体设计应画一流程图 ‎3.程序要加必要的注释 ‎4.要提供程序测试方案 ‎5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。‎ 二、‎ 软件环境 Microsoft Visual C++‎ ‎6.0‎ 三、‎ 问题的需求分析程序以二维数组作为矩阵的存储结构，通过键盘输入矩阵维数n，动态分配内存空间，创建n维矩阵。矩阵建立后再通过键盘输入矩阵的各个元素值；也可以通过文件读入矩阵的各项数据（维数及各元素值）。‎ 当要对矩阵作进一步操作（AxB或AxB^(-1)）时，先判断内存中是否已经有相关的数据存在，若还未有数据存在则提示用户先输入相关数据。‎ 当要对矩阵进行求逆时，先利用矩阵可逆的充要条件：|A|‎ ‎!=‎ 判断矩阵是否可逆，若矩阵的行列式 ‎|A|‎ 则提示该矩阵为不可逆的；若 ‎|A|‎ ‎!=0‎ 则求其逆矩阵，并在终端显示其逆矩阵。‎ 四、‎ 算法设计思想及流程图1．抽象数据类型ADT MatrixMulti{‎ 数据对象：D ‎{a(I,j)|i ‎1,2,3,…,n;j ‎1,2,…,n;a(i,j)∈ElemSet,n为矩阵维数}‎ 数据关系:‎ ‎{Row,Col}‎ Row ‎{|‎ ‎<=‎ ‎<=‎ ‎<=‎ ‎<=‎ n-1}‎ Col ‎{|‎ ‎<=‎ ‎<=‎ n-1‎ ‎<=‎ ‎<=‎ 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的行列式的值。‎ ADT MatrixMulti ‎2．矩阵求逆算法设计思想算法采用高斯-约旦法（全选主元）求逆，主要思想如下：‎ 首先，对于k从0到n-1作如下几步：‎ 从第k行、第k列开始的右下角子阵中选取绝对值最大的元素，并记住此元素所在的行号与列号，再通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。‎ 主元求倒：M(k,k)‎ M(k,k)‎ M(k,j)‎ M(k,j)‎ M(k,k)；j ‎0,1,…,n-1;j ‎!=‎ M(i,j)‎ M(i,j)‎ M(i,k)‎ M(k,j)；i,j ‎0,1,…,n-1;i,j!=k M(i,k)‎ M(i,k)‎ M(k,k)，i ‎0,1…,n-1；i ‎!=‎ 最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复原则如下：‎ 在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。3.矩阵行列式求值运算算法设计思想利用行列式的性质：行列式等于它的任一行（列）各元素与其对应的代数余子式乘积，即D ‎∑a(i,k)xA(i,k)‎ ‎;k ‎1,2,…,n;‎ ‎∑a(k,j)xA(k,j)‎ ‎;k ‎1,2,…,n;‎ 再利用函数的递归调用法实现求其值。4．各函数间的调用关系 Main()‎ ReadFromFile()‎ DinV()‎ Swap ‎()‎ Print()‎ Menu_Select()‎ MatrixDeterm()‎ CreateMatrix()‎ MultMatrix()‎ Input()‎ ‎5.流程图 开始 switch(Menu_Select())‎ case ‎1:‎ case ‎3:‎ case ‎2:‎ ‎>‎ 输入矩阵维数n 输入矩阵A,B 输出矩阵维数n system(“pause”);‎ 通过键盘输入需对哪个矩阵求逆,求出相应该的逆阵,并显示求得的逆阵system(“pause”);若矩阵不可逆则返回主菜单 case ‎4:‎ R=AxB并显示矩阵R system(“pause”);‎ case ‎5:‎ R=AxB^(-1)显示矩阵R system(“pause”);若B不可逆,则返回主菜单 case ‎6:‎ 从指定文件中读入矩阵数据 case ‎0:‎ exit(0);‎ 结果 否五、‎ 源代码#include ‎‎ ‎#include ‎‎ ‎#include ‎‎ ‎#include ‎‎ ‎#include ‎‎ ‎#include ‎‎ ‎#define YES ‎#define NO typedef float ElemType;‎ ElemType xxA;‎ ‎//矩阵A ElemType xxB;‎ ‎//矩阵B ElemType xxR;‎ ‎//矩阵R,用于存放运算结果 ElemType xxV;‎ ‎//矩阵V,存放逆矩阵 int n=0;//矩阵维数 int flag=-1;//标记 void swap(ElemType xa,ElemType xb)‎ ‎//交换记录a,b的值 ElemType c;‎ c=xa;‎ xa=xb;‎ xb=c;‎ ElemType xxCreateMatrix(int n)‎ ‎//创建n维矩阵,返回该矩阵 int i,j;‎ ElemType xxM;‎ ‎(ElemType xx)malloc(sizeof(ElemType x)xn);‎ if(M ‎==‎ NULL)exit(1);‎ for(i=0;id)‎ d=fabs(V[i][j]);‎ ‎//d记录绝对值最大的元素的值 ‎/x把绝对值最大的元素在数组中的行、列坐标分别存入IS[K],JS[K]x/‎ IS[k]=i;JS[k]=j;‎ ‎}}if(d+1.0‎ ‎==‎ ‎1.0)‎ return ‎0;‎ ‎//所有元素都为0if(IS[k]‎ ‎!=‎ k)‎ ‎/x若绝对值最大的元素不在第k行,则将矩阵IS[K]行的元素与k行的元素相交换x/‎ for(j=0;j=0;k--)/x根据上面记录的行IS[k],列JS[k]信息恢复元素x/‎ ‎{for(j=0;j＇6＇);‎ return ‎(c-＇0＇);‎ void ReadFromFile()‎ ‎//从指定文件读入矩阵的维数及矩阵各元素的值 int i,j;‎ FILE xfp;‎ if((fp=fopen(“tx.txt“,“r“))==NULL)‎ ‎{puts(“无法打开文件!!!“);system(“pause“);exit(0);‎ fscanf(fp,“%d“,&n);‎ ‎//读入矩阵维数 A=CreateMatrix(n);‎ ‎//创建矩阵A B=CreateMatrix(n);‎ V=CreateMatrix(n);‎ R=CreateMatrix(n);‎ for(i=0;i0)‎ 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;‎ case ‎2:‎ 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;‎ case ‎3:‎ 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;}else if(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;}else puts(“＼n＼n＼t输入有误,请重新输入!＼n“);‎ break;‎ case ‎4:‎ system(“cls“);‎ if(flag==-1)‎ ‎{puts(“＼n＼n＼t不存在任何矩阵数据,请先输入数据“);system(“pause“);break;‎ MultMatrix(A,B,R);‎ printf(“＼n＼n＼tAxB ‎“);‎ Print(R);‎ puts(““);‎ system(“pause“);‎ break;‎ case ‎5:‎ 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＼nAxB^(-1)‎ ‎“);‎ Print(R);‎ puts(““);‎ system(“pause“);‎ break;‎ case ‎6:‎ system(“cls“);‎ ReadFromFile();‎ puts(““);‎ system(“pause“);‎ break;‎ case ‎0:‎ puts(“＼t＼t正常退出“);‎ exit(0);‎ break;}‎ return ‎0;‎ ‎}六、‎ 运行结果1．主界面：2．输入6，回车，从文本文件tx.txt中读入矩阵数据：‎ ‎3．回车，回到主菜单界面；输入2回车，显示从文件读入的矩阵数据：‎ ‎4．回车，回到主菜单界面；输入3回车，对指定矩阵求逆：（由于这里矩阵A是不可逆的，因此仅以矩阵B为例）‎ ‎5．回车，回到主菜单界面；输入4回车，求矩阵运算AxB：‎ ‎6．回车回到主菜单界面，输入5回车，求AxB^(-1)的值：‎ ‎7．回车回到主菜单界面，输入0回车，退出程序；如果需要自定矩阵维数及各元素值，请利用主菜单里的1号功能自行输入数据，‎ 再进行以上几种运算操作。‎ 七、‎ 收获及体会 通过这次课程设计，让我再次复习了线性代数里矩阵的相关知识，比如n维矩阵的求逆、矩阵可逆的充分必要条件（|A|‎ ‎！=‎ ‎0）、矩阵与矩阵的乘法运算、行列式求值方法等。同样的，还让我复习了大量C语言里有关数组的一些重要概念，比如多维数组的动态分配问题、数组与指针的关系等。‎ 记得在这个学期新开设的单片机基础课上，吴涛老师曾多次强调，让我们一定要经常锻炼自己的编程能力，他常对我们说：“编程是思维的体操。”尽管我在这方面的能力 和实力非常得有限，也远远不及班上的其他同学，但我通过这次课程设计充分体会到了这句话的精华。‎ 电脑程序作为人体大脑思维的延伸，程序的功能也会因为大脑思维的不断完善而变得更加强大，所以我决定今后要加强在这方面的锻炼和学习，以此来激励自己不断前进！‎ 八、‎ 参考文献 ‎《数据结构（C语言版）》‎ 严蔚敏，吴伟民 编著清华大学出版社 ‎《C语言程序设计》‎ 洪维恩 编著中国铁道出版社 ‎《C语言程序设计教程》‎ 谭浩强 张基温 唐永炎 编著高等教育出版社 ‎《工程数学——线性代数 第四版》‎ 同济大学应用数学系 高等教育出版社计本2007-12‎