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