数据结构课程设计报告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维矩阵。矩阵建立后再通过键盘输入矩阵的各个元素值；也可以通过文件读入矩阵的各项数据（维数及各元素值）。

当要对矩阵作进一步操作（A*B或A*B^(-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

n-1}

Col

n-1,1

基本操作:

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,k)；j

0,1,…,n-1;j

④

M(i,j)

–

M(i,k)

M(k,j)；i,j

0,1,…,n-1;i,j!=k

⑤

M(i,k)

M(k,k)，i

0,1…,n-1；i

最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复原则如下：

在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。

3.矩阵行列式求值运算算法设计思想

利用行列式的性质：行列式等于它的任一行（列）各元素与其对应的代数余子式乘积，即

∑a(i,k)*A(i,k)

;

1,2,…,n;

∑a(k,j)*A(k,j)

;

1,2,…,n;

再利用函数的递归调用法实现求其值。

4．各函数间的调用关系

Main()

ReadFromFile()

DinV()

Swap

()

Print()

Menu_Select()

MatrixDeterm()

CreateMatrix()

MultMatrix()

Input()

5.流程图

否

是

否

是

否

是

否

是

开始

switch(Menu_Select())

case

是

输入矩阵维数n

输入矩阵A,B

输出矩阵维数n

system(“pause”);

通过键盘输入需对哪个矩阵求逆,求出相应该的逆阵,并显示求得的逆阵system(“pause”);若矩阵不可逆则返回主菜单

case

R=A*B并显示矩阵R

system(“pause”);

case

是

否

是

R=A*B^(-1)显示矩阵R

system(“pause”);若B不可逆,则返回主菜单

case

从指定文件中读入矩阵数据

case

exit(0);

结果

否

五、源代码

#include

#define

YES

#define

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=*a;

*a=*b;

*b=c;

}

ElemType

**CreateMatrix(int

//创建n维矩阵,返回该矩阵

{

int

i,j;

ElemType

**M;

(ElemType

**)malloc(sizeof(ElemType

*)*n);

if(M

NULL)

exit(1);

for(i=0;i

{

*(M+i)

(ElemType

*)malloc(sizeof(ElemType)*n);

for(j=0;j

*(*(M+i)+j)

}

return

}

ElemType

MatrixDeterm(ElemType

**M,int

/*递归法求n维矩阵行列式的值,返回运算结果*/

{

int

i,j,k,l,s;

ElemType

**T1;

ElemType

**T2;

T1=CreateMatrix(n);

T2=CreateMatrix(n);

ElemType

value=0;

//运算结果

for(i=0;i

{

for(j=0;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

//将矩阵的行列式以第一行展开

{

u=T1[0][j];

for(i=1,l=0;i

//求矩阵行列式的余子式M(0,j)

{

for(k=0,s=0;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

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

for(j=0;j

V[i][j]=M[i][j];

for(k=0;k

{

d=0;

for(i=k;i

//找出矩阵M从M[k][k]开始绝对值最大的元素

{

for(j=k;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

if(IS[k]

/*若绝对值最大的元素不在第k行,则将矩阵IS[K]行的元素与k行的元素相交换*/

for(j=0;j

swap(&V[k][j],&V[IS[k]][j]);

if(JS[k]!=k)

/*若绝对值最大的元素不在第k列,则将矩阵JS[K]列的元素与k列的元素相交换*/

for(i=0;i

swap(&V[i][k],&V[i][JS[k]]);

V[k][k]=1/V[k][k];

//绝对值最大的元素求倒

for(j=0;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

/*矩阵除第k行的所有元素与第k列的所有元素外,都拿本身减去M[i][k]*M[k][j],其中i,j为元素本身在矩阵的位置坐标*/

if(i!=k)

for(j=0;j

if(j!=k)

V[i][j]=V[i][j]-V[i][k]*V[k][j];

for(i=0;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

if(JS[k]!=k)

swap(&V[k][j],&V[JS[k]][j]);

for(i=0;i

if(IS[k]!=k)

swap(&V[i][k],&V[i][IS[k]]);

}

free(IS);

free(JS);

return

}

void

MultMatrix(ElemType

**M1,ElemType

**M2,ElemType

**R)

/*矩阵M1乘M2

结果存入矩阵R*/

{

int

i,j,k;

for(i=0;i

{

for(j=0;j

{

R[i][j]=0;

}

for(i=0;i

{

for(j=0;j

{

for(k=0;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

{

for(j=0;j

{

scanf(“%f“,*(M+i)+j);

}

flag=1;

gets(str);

//吸收多余的字符

}

void

Print(ElemType

**M)

//显示矩阵M的各个元素值

{

int

i,j;

printf(“＼t“);

for(i=0;i

{

for(j=0;j

{

printf(“

%.3f“,M[i][j]);

}

puts(““);

printf(“＼t＼t“);

}

int

Menu_Select()

{

char

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=CreateMatrix(n);

V=CreateMatrix(n);

R=CreateMatrix(n);

for(i=0;i

//读入矩阵A

{

for(j=0;j

{

fscanf(fp,“%f“,&A[i][j]);

}

for(i=0;i

//读入矩阵A

{

for(j=0;j

{

fscanf(fp,“%f“,&B[i][j]);

}

puts(“＼n＼n读文件成功“);

fclose(fp);

flag=1;

}

int

main()

{

int

char

c,h;

char

str[10];

for(;;)

{

switch(Menu_Select())

{

case

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

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

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

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

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

system(“cls“);

ReadFromFile();

puts(““);

system(“pause“);

break;

case

puts(“＼t＼t正常退出“);

exit(0);

break;

}

return

}

六、运行结果

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

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

相关范文推荐

数据结构课程设计(矩阵的运算)

C++课程设计报告--矩阵乘法计算

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告