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

数据结构
课程设计报告
设计题目：
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://m.gjknj.com/duwu/348453.html 转载请保留,谢谢!