数据结构
课程设计报告
设计题目:
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维矩阵。矩阵建立后再通过键盘输入矩阵的各个元素值;也可以通过文件读入矩阵的各项数据(维数及各元素值)。
当要对矩阵作进一步操作(AxB或AxB^(-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)
x
M(k,k);j
=
0,1,…,n-1;j
!=
k
④
M(i,j)
=
M(i,j)
–
M(i,k)
x
M(k,j);i,j
=
0,1,…,n-1;i,j!=k
⑤
M(i,k)
=
-
M(i,k)
x
M(k,k),i
=
0,1…,n-1;i
!=
k
最后,根据在全选主元过程中所记录的行、列交换的信息进行恢复,恢复原则如下:
在全选主元过程中,先交换的行(列)后进行恢复;原来的行(列)交换用列(行)交换来恢复。3.矩阵行列式求值运算算法设计思想利用行列式的性质:行列式等于它的任一行(列)各元素与其对应的代数余子式乘积,即D
=
∑a(i,k)xA(i,k)
;k
=
1,2,…,n;
D
=
∑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
>
0
?
是
输入矩阵维数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
<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
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;
M
=
(ElemType
xx)malloc(sizeof(ElemType
x)xn);
if(M
==
NULL)exit(1);
for(i=0;i<n;i++)
{x(M+i)
=
(ElemType
x)malloc(sizeof(ElemType)xn);for(j=0;j<n;j++)
x(x(M+i)+j)
=
0;
}
return
M;
}
ElemType
MatrixDeterm(ElemType
xxM,int
n)/x递归法求n维矩阵行列式的值,返回运算结果x/
{
int
i,j,k,l,s;
ElemType
xxT1;
ElemType
xxT2;
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]xT2[1][1]-T2[0][1]xT2[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+ux((int)pow(-1,j))xMatrixDeterm(T2,n-1);
/x行列式等于某一行的各个元素与其代数余子式的乘积之和x/
}
return
value;
}
}int
DinV(ElemType
xxM,ElemType
xxV)
/x全选主元法求矩阵M的逆矩阵,结果存入矩阵V中x/
{
int
i,j,k;
ElemType
d;
ElemType
u;
int
xJS,xIS;
JS=(int
x)malloc(sizeof(int)xn);
IS=(int
x)malloc(sizeof(int)xn);
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记录绝对值最大的元素的值
/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<n;j++)
swap(&V[k][j],&V[IS[k]][j]);if(JS[k]!=k)/x若绝对值最大的元素不在第k列,则将矩阵JS[K]列的元素与k列的元素相交换x/
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++)
/x矩阵M第k行除元素M[k][k]本身外都乘以M[k][k]x/
if(j!=k)
V[k][j]=V[k][j]xV[k][k];for(i=0;i<n;i++)
/x矩阵除第k行的所有元素与第k列的所有元素外,都拿本身减去M[i][k]xM[k][j],
其中i,j为元素本身在矩阵的位置坐标x/
if(i!=k)
for(j=0;j<n;j++)
if(j!=k)
V[i][j]=V[i][j]-V[i][k]xV[k][j];
for(i=0;i<n;i++)
/x矩阵M第k列除元素M[k][k]本身外都乘以-M[k][k]x/
if(i!=k)
V[i][k]=-V[i][k]xV[k][k];
}
for(k=n-1;k>=0;k--)/x根据上面记录的行IS[k],列JS[k]信息恢复元素x/
{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
xxM1,ElemType
xxM2,ElemType
xxR)
/x矩阵M1乘M2
结果存入矩阵Rx/
{
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]xM2[k][j];
}}
}
}void
Input(ElemType
xxM)
//输入矩阵M的各个元素值
{
int
i,j;
char
str[10];
char
c='A';
if(flag==1)c='B';
system(“cls“);
printf(“\n\n输入矩阵%c(%dx%d)\n“,c,n,n);
for(i=0;i<n;i++)
{for(j=0;j<n;j++){
scanf(“%f“,x(M+i)+j);}
}
flag=1;
gets(str);
//吸收多余的字符
}void
Print(ElemType
xxM)
//显示矩阵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\txxxxxxxxxxxxxn维矩阵乘法器xxxxxxxxxxxxx“);puts(“\t\t|
1.
通过键盘输入各项数据
|“);puts(“\t\t|
2.
显示矩阵A,B
|“);puts(“\t\t|
3.
矩阵求逆,并显示逆矩阵|“);puts(“\t\t|
4.
求矩阵运算AxB,并显示运算结果
|“);puts(“\t\t|
5.
求矩阵运算AxB^(-1),并显示运算结果|“);puts(“\t\t|
6.
从文件读入矩阵A,B与维数n
|“);puts(“\t\t|
0.
退出
|“);puts(“\t\txxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx“);printf(“\t\t请选择(0-6):“);c=getchar();
}while(c<'0'||c>'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
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\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
《数据结构课程设计报告n维矩阵乘法》由:卡耐基范文网整理
链接地址:http://www.gjknj.com/duwu/348453.html
转载请保留,谢谢!