求马鞍点实验报告

1、1、 实验内容和要求2、若矩阵采用三元组顺序表表示，设计并验证找出矩阵中所有马鞍点的算法。2、 实验过程及结果1、 需求分析1、将随机生成的数定义为int型（为方便起见设定范围为-20至19（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。3、 程序能实现的功能包括：初始化矩阵；产生新的随机矩阵；手动输入新的矩阵；输出阵列形式的矩阵；找出矩阵的马鞍点；输出矩阵的马鞍点的三元组形式；清空矩阵；

2、清空马鞍点； 2、 概要设计1、矩阵的抽象数据类型定义：ADT Matrix数据对象：D= aij|i=1,2,m,j=1,2,n;Ai,jElemSet,m和n分别称为矩阵的行数和列数数据关系：R=Row，ColRow=<ai,j，ai,j+1>|1im, 1jn-1Col =<ai,j，ai+1,j>|1im-1, 1jn基本操作: InitMatrix(&M)操作结果：初始化矩阵MCreateTSMatrix(&M)操作结果：创建一个随机矩阵MCreateMatrixSelf(&M)操作结果：手动创建一个矩阵MPrintTSMatrix(M

3、)初始条件：矩阵M已存在操作结果：以阵列形式输出矩阵GetSaddlePoint(M,&saddle)初始条件：矩阵M已存在操作结果：找出矩阵M的马鞍点用三元组形式存储到saddle中PrintSaddlePoint(M,&saddle)初始条件：矩阵M已存在，其马鞍点存储在三元组saddle中操作结果：输出矩阵M的马鞍点,即saddle中的元素ClearMatrix(&M)初始条件：矩阵M已存在操作结果：清空矩阵ClearSaddlePoint(&saddle)初始条件：saddle中存储了矩阵的马鞍点三元组形式操作结果：清空马鞍点ADT Matrix； 本程

4、序模块结构1 主函数模块void main()while(命令不是退出)printf(" 选项：n");printf("Your Choice:");if(创建新的矩阵)清空之前的矩阵和马鞍点；switch(choice)case 1:自己创建新矩阵；case 2:创建随机的新矩阵；case 3:输出创建的矩阵；case 4:找出马鞍点并输出；default:退出； 三、详细设计1、基本数据类型操作typedef int ElemType;typedef struct int i,j; ElemType e;Triple;/数据类型 三元组typedef

5、 struct Triple *base; /矩阵基址 int MatrixSize;/当前的矩阵大小 int mu,nu;/当前长度Matrix;/矩阵抽象数据类型2、参数设置：#define MAXMATRIXSIZE 10000/-基本操作的算法描述-Status InitMatrix(Matrix *M)M->base=(Triple *)malloc(MAXMATRIXSIZE*sizeof(Triple);if(!M->base)exit(OVERFLOW);M->mu=M->nu=0;M->MatrixSize=MAXMATRIXSIZE;retur

6、n OK;Status CreateMatrix(Matrix *M)/创建一个随机矩阵，p从1开始 srand(int)time(NULL);printf("Please Input The Lines And Columns Of The Matrix:n"); scanf(M->mu，M->nu); for(m=1;m<=M->mu;m+) for(n=1;n<=M->nu;n+)if(rand()%2)M->basep.e=rand()%20;elseM->basep.e=rand()%20-20;M->base

7、p.i=m;M->basep.j=n;p+; return OK;Status CreateMatrixSelf(Matrix *M)/手动创建一个矩阵，即手动输入，p从1开始 srand(int)time(NULL);printf("Please Input The Lines And Columns Of The Matrix:n"); scanf(M->mu，M->nu); for(m=1;m<=M->mu;m+) for(n=1;n<=M->nu;n+)scanf("%d",&M->base

8、p.e);M->basep.i=m;M->basep.j=n;p+; return OK;void ClearMatrix(Matrix *M)/将矩阵行数和列数置为0，即清空矩阵MM->mu=M->nu=0;Status PrintMatrix(Matrix M)/按阵列形式输出矩阵Mif(M.mu=0&&M.nu=0)printf("矩阵为空!n");return FALSE;printf("矩阵为:n"); for(i=1;i<=M.mu;i+) for(j=1;j<=M.nu;j+) print

9、f("%4d",p->e); p+; k+;printf("n"); printf("n");return TRUE;Status GetSaddlePoint(Matrix M,Triple *saddle)/找出矩阵M的马鞍点存入saddle中for(row=1;row<=M.mu;row+)p=(row-1)*M.nu;/行首元素的下标l_minrow=M.basep.e; /令每行的第一个元素为最大值for(col=2;col<=M.nu;col+)/从每行的第二个元素开始遍历p+; /同一行元素存储位置连续

10、，下标下移if(l_minrow>M.basep.e)l_minrow=M.basep.e;for(col=1;col<=M.nu;col+)w_maxcol=M.basecol-1.e;/令每列的第一个元素为最大值for(row=2;row<=M.mu;row+)/从每列的第二个元素开始遍历q=(row-1)*M.nu+col-1; /col列的第row个元素的下标，完成同一列元素的依次遍历if(w_maxcol<M.baseq.e)w_maxcol=M.baseq.e;for(p=1;p<=M.mu;p+)for(q=1;q<=M.nu;q+)if(l_

11、minp=w_maxq)/第p行的最小元素等于第q列的最大元素，则（p,q）为马鞍点位置saddleorder.i=p;saddleorder.j=q;saddleorder+.e=l_minp;saddleorder.i=0;saddleorder.j=0;saddleorder.e=0;/将0作为封闭条件， 0以前的全部为马鞍点return OK;Status PrintSaddlePoint(Matrix M,Triple *saddle)/依次输出M的全部马鞍点Triple *p=saddle;if(M.mu=0&&M.nu=0)printf("矩阵为空!n&

12、quot;);return FALSE;if(p->i=0&&p->j=0)printf("无马鞍点!n");return FALSE; printf("各马鞍点的坐标及值:nn"); printf(" 行 列 元素值n"); while(p->i>0) printf("%3d%4d%6dn",p->i,p->j,p->e);p+; printf("n");return TRUE;void ClearSaddlePoint(Triple

13、*saddle)/清空马鞍点Triple *p=saddle; while(p->i>0) p->e=0;p->i=0;p->j=0;p+; 主函数算法：void main()while(status!=OK)printf("*n");printf(" 1、Create New Matrix By Yourselfn");printf(" 2、Create New Matrix Randomlyn");printf(" 3、Print Matrixn");printf(" 4

14、、Print SaddlePointn");printf(" 5、Exitn");printf("Your Choice:");scanf("%d",&choice);if(choice=1|choice=2)ClearMatrix(&M);ClearSaddlePoint(saddle);switch(choice)case 1:CreateMatrixSelf(&M);break;case 2:CreateMatrix(&M);break;case 3:PrintMatrix(M);bre

15、ak;case 4:GetSaddlePoint(M,saddle);PrintSaddlePoint(M,saddle);break;default:status=OK;break; 四、调试分析1、矩阵采用三元组顺序表表示，设计存储结构时，给矩阵一个首地址及初始大小，由初始化分配内存空间。2、寻找马鞍点时采取的算法是分别求出每行最小值和每列最大值用两个数组存储，再用两层for循环控制两个数组的每个元素进行比较，当值相同时，对应的行标和列标即为马鞍点位置。开始将行最小值和列最大值分别赋为对应行行首元素值和对应列列首元素值，向后遍历时应从行或列的第二个元素开始。3、由于马鞍点的情况较少，一般情

16、况下都不存在马鞍点，尤其是对随机生成的矩阵，因此又设计了手动创建矩阵的功能，便于验证，同时在主函数中设计了循环，提供创建新矩阵命令时则才会将之前的矩阵和马鞍点清空，提供退出命令时才退出。 五、用户说明1、 本程序的运行环境为windows 7（64位）操作系统，执行文件为求马鞍点.exe；2、 进入演示程序后，即显示可进行操作的菜单，根据菜单输入相应的操作序号即可进行相应的操作。如图所示： 选项1：手动创建新矩阵按提示依次输入行数、列数和相应的所有元素值选项2：创建随机新矩阵按提示输入行数和列数后自动完成矩阵的创建选项3：输出创建的矩阵输出m行n列的矩阵选项4：输出矩阵的马鞍点依次输出各马鞍点

17、的三元组形式选项5：退出按任意键退出 六、测试结果1、手动创建一个存在马鞍点的矩阵2、创建一个随机矩阵七、附录（源代码及部分注释）#include "stdio.h"#include "stdlib.h"#include "time.h"#define MAXMATRIXSIZE 10000#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1#define INIT 0typedef int ElemType;typedef int St

18、atus;typedef struct int i,j; ElemType e;Triple;/数据类型 三元组typedef struct Triple *base; /矩阵基址 int MatrixSize;/当前的矩阵大小int mu,nu;/当前长度Matrix;/矩阵抽象数据类型Status InitMatrix(Matrix *M);/初始化矩阵MStatus CreateMatrix(Matrix *M);/创建随机矩阵Status CreateMatrixSelf(Matrix *M);/手动创建矩阵void ClearMatrix(Matrix *M);/清空矩阵void C

19、learSaddlePoint(Triple *saddle);/清空马鞍点Status PrintMatrix(Matrix M);/以阵列形式输出矩阵Status PrintSaddlePoint(Matrix M,Triple *saddle);/输出矩阵的马鞍点Status GetSaddlePoint(Matrix M,Triple *saddle);/求矩阵M的马鞍点void main()Matrix M;InitMatrix(&M);Triple saddle25;int choice;Status status=INIT;while(status!=OK)printf(

20、"*n");printf(" 1、Create New Matrix By Yourselfn");printf(" 2、Create New Matrix Randomlyn");printf(" 3、Print Matrixn");printf(" 4、Print SaddlePointn");printf(" 5、Exitn");printf("Your Choice:");scanf("%d",&choice);if(c

21、hoice=1|choice=2)ClearMatrix(&M);ClearSaddlePoint(saddle);switch(choice)case 1:CreateMatrixSelf(&M);break;case 2:CreateMatrix(&M);break;case 3:PrintMatrix(M);break;case 4:GetSaddlePoint(M,saddle);PrintSaddlePoint(M,saddle);break;default:status=OK;break;Status InitMatrix(Matrix *M)M->b

22、ase=(Triple *)malloc(MAXMATRIXSIZE*sizeof(Triple);if(!M->base)exit(OVERFLOW);M->mu=M->nu=0;M->MatrixSize=MAXMATRIXSIZE;return OK;Status CreateMatrix(Matrix *M) int m,n,p=0;int value; srand(int)time(NULL);printf("Please Input The Lines And Columns Of The Matrix:n"); printf("

23、;The Line Number:"); scanf("%d",&M->mu);printf("The Column Number:"); scanf("%d",&M->nu); for(m=1;m<=M->mu;m+) for(n=1;n<=M->nu;n+)if(rand()%2)M->basep.e=rand()%20;elseM->basep.e=rand()%20-20;M->basep.i=m;M->basep.j=n;p+; retur

24、n OK;Status CreateMatrixSelf(Matrix *M)int m,n,p=0;int value; srand(int)time(NULL);printf("Please Input The Lines And Columns Of The Matrix:n"); printf("The Line Number:"); scanf("%d",&M->mu);printf("The Column Number:"); scanf("%d",&M->

25、;nu); for(m=1;m<=M->mu;m+) for(n=1;n<=M->nu;n+)scanf("%d",&M->basep.e);M->basep.i=m;M->basep.j=n;p+; return OK;void ClearMatrix(Matrix *M)M->mu=M->nu=0;Status PrintMatrix(Matrix M) int i,j,k=0; Triple *p=M.base;if(M.mu=0&&M.nu=0)printf("矩阵为空!n&qu

26、ot;);return FALSE;printf("矩阵为:n"); for(i=1;i<=M.mu;i+) for(j=1;j<=M.nu;j+) printf("%4d",p->e); p+; k+;printf("n"); printf("n");return TRUE;Status GetSaddlePoint(Matrix M,Triple *saddle)int row,col;int p=0,q=0,order=0;int l_min25,w_max25;for(row=1;row<=M.mu;row+)p=(row-1)*M.nu;/行首元素的下标l_minrow=M.basep.e; /令每行的第一个元素为最大值for(col=2;col<=M.nu;col+)/从每行的第二个元素开始遍历p+; /同一行元素存储位置连续，下标下移if(l_minrow>M.basep.e)