求马鞍点实验报告资料.docx
《求马鞍点实验报告资料.docx》由会员分享，可在线阅读，更多相关《求马鞍点实验报告资料.docx（21页珍藏版）》请在冰点文库上搜索。
求马鞍点实验报告资料
1、实验内容和要求
2、若矩阵采用三元组顺序表表示，设计并验证找出矩阵中所有马鞍点的算法。
2、实验过程及结果
1、需求分析
1、将随机生成的数定义为int型（为方便起见设定范围为-20至19（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。
实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。
2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。
3、程序能实现的功能包括：
①初始化矩阵；②产生新的随机矩阵；③手动输入新的矩阵；④输出阵列形式的矩阵；⑤找出矩阵的马鞍点；
输出矩阵的马鞍点的三元组形式；
清空矩阵；
清空马鞍点；
2、概要设计
1、矩阵的抽象数据类型定义：
ADTMatrix{
数据对象：
D={aij|i=1,2,…,m,j=1,2,…,n;
Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}
数据关系：
R={Row，Col}
Row={|1≤i≤m,1≤j≤n-1}
Col={|1≤i≤m-1,1≤j≤n}
基本操作:
InitMatrix（&M）
操作结果：
初始化矩阵M
CreateTSMatrix（&M）
操作结果：
创建一个随机矩阵M
CreateMatrixSelf（&M）
操作结果：
手动创建一个矩阵M
PrintTSMatrix（M）
初始条件：
矩阵M已存在
操作结果：
以阵列形式输出矩阵
GetSaddlePoint（M,&saddle）
初始条件：
矩阵M已存在
操作结果：
找出矩阵M的马鞍点用三元组形式存储到saddle中
PrintSaddlePoint（M,&saddle）
初始条件：
矩阵M已存在，其马鞍点存储在三元组saddle中
操作结果：
输出矩阵M的马鞍点,即saddle中的元素
ClearMatrix（&M）
初始条件：
矩阵M已存在
操作结果：
清空矩阵
ClearSaddlePoint（&saddle）
初始条件：
saddle中存储了矩阵的马鞍点三元组形式
操作结果：
清空马鞍点
}ADTMatrix；
⒊本程序模块结构
1主函数模块
voidmain（）{
while（命令不是退出）{
printf（"选项：
\n"）;
printf（"YourChoice:
"）;
if（创建新的矩阵）{
清空之前的矩阵和马鞍点；
}
switch（choice）{
case1:
自己创建新矩阵；
case2:
创建随机的新矩阵；
case3:
输出创建的矩阵；
case4:
找出马鞍点并输出；
default:
退出；
}
}
｝
三、详细设计
1、基本数据类型操作
⑴typedefintElemType;
typedefstruct{
inti,j;
ElemTypee;
}Triple;//数据类型三元组
typedefstruct{
Triple*base;//矩阵基址
intMatrixSize;//当前的矩阵大小
intmu,nu;//当前长度
}Matrix;//矩阵抽象数据类型
2、参数设置：
#defineMAXMATRIXSIZE10000
//----------基本操作的算法描述--------------------
StatusInitMatrix（Matrix*M）{
M->base=（Triple*）malloc（MAXMATRIXSIZE*sizeof（Triple））;
if（!
M->base）
exit（OVERFLOW）;
M->mu=M->nu=0;
M->MatrixSize=MAXMATRIXSIZE;
returnOK;
}
StatusCreateMatrix（Matrix*M）{
//创建一个随机矩阵，p从1开始
srand（（int）time（NULL））;
printf（"PleaseInputTheLinesAndColumnsOfTheMatrix:
\n"）;
scanf（M->mu，M->nu）;
for（m=1;m<=M->mu;m++）{
for（n=1;n<=M->nu;n++）{
if（rand（）%2）
M->base[p].e=rand（）%20;
else
M->base[p].e=rand（）%20-20;
M->base[p].i=m;
M->base[p].j=n;
p++;
}
}
returnOK;
}
StatusCreateMatrixSelf（Matrix*M）{
//手动创建一个矩阵，即手动输入，p从1开始
srand（（int）time（NULL））;
printf（"PleaseInputTheLinesAndColumnsOfTheMatrix:
\n"）;
scanf（M->mu，M->nu）;
for（m=1;m<=M->mu;m++）{
for（n=1;n<=M->nu;n++）{
scanf（"%d",&M->base[p].e）;
M->base[p].i=m;
M->base[p].j=n;
p++;
}
}
returnOK;
}
voidClearMatrix（Matrix*M）{
//将矩阵行数和列数置为0，即清空矩阵M
M->mu=M->nu=0;
}
StatusPrintMatrix（MatrixM）{
//按阵列形式输出矩阵M
if（M.mu==0&&M.nu==0）{
printf（"矩阵为空!
\n"）;
returnFALSE;
}
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"）;
returnTRUE;
}
StatusGetSaddlePoint（MatrixM,Triple*saddle）{
//找出矩阵M的马鞍点存入saddle中
for（row=1;row<=M.mu;row++）{
p=（row-1）*M.nu;//行首元素的下标
l_min[row]=M.base[p].e;//令每行的第一个元素为最大值
for（col=2;col<=M.nu;col++）{//从每行的第二个元素开始遍历
p++;//同一行元素存储位置连续，下标下移
if（l_min[row]>M.base[p].e）
l_min[row]=M.base[p].e;
}
}
for（col=1;col<=M.nu;col++）{
w_max[col]=M.base[col-1].e;//令每列的第一个元素为最大值
for（row=2;row<=M.mu;row++）{//从每列的第二个元素开始遍历
q=（row-1）*M.nu+col-1;//col列的第row个元素的下标，完成同一列元素的依次遍历
if（w_max[col]w_max[col]=M.base[q].e;
}
}
for（p=1;p<=M.mu;p++）{
for（q=1;q<=M.nu;q++）{
if（l_min[p]==w_max[q]）{//第p行的最小元素等于第q列的最大元素，则（p,q）为马鞍点位置
saddle[order].i=p;
saddle[order].j=q;
saddle[order++].e=l_min[p];
}
}
}
saddle[order].i=0;
saddle[order].j=0;
saddle[order].e=0;//将0作为封闭条件，0以前的全部为马鞍点
returnOK;
}
StatusPrintSaddlePoint（MatrixM,Triple*saddle）{
//依次输出M的全部马鞍点
Triple*p=saddle;
if（M.mu==0&&M.nu==0）{
printf（"矩阵为空!
\n"）;
returnFALSE;
}
if（p->i==0&&p->j==0）{
printf（"无马鞍点!
\n"）;
returnFALSE;
}
printf（"各马鞍点的坐标及值:
\n\n"）;
printf（"行列元素值\n"）;
while（p->i>0）{
printf（"%3d%4d%6d\n",p->i,p->j,p->e）;
p++;
}
printf（"\n"）;
returnTRUE;
}
voidClearSaddlePoint（Triple*saddle）{
//清空马鞍点
Triple*p=saddle;
while（p->i>0）{
p->e=0;
p->i=0;
p->j=0;
p++;
}
}
⑶主函数算法：
voidmain（）{
while（status!
=OK）{
printf（"**************************************************\n"）;
printf（"1、CreateNewMatrixByYourself\n"）;
printf（"2、CreateNewMatrixRandomly\n"）;
printf（"3、PrintMatrix\n"）;
printf（"4、PrintSaddlePoint\n"）;
printf（"5、Exit\n"）;
printf（"YourChoice:
"）;
scanf（"%d",&choice）;
if（choice==1||choice==2）{
ClearMatrix（&M）;
ClearSaddlePoint（saddle）;
}
switch（choice）{
case1:
CreateMatrixSelf（&M）;
break;
case2:
CreateMatrix（&M）;
break;
case3:
PrintMatrix（M）;
break;
case4:
GetSaddlePoint（M,saddle）;
PrintSaddlePoint（M,saddle）;
break;
default:
status=OK;
break;
}
}
}
四、调试分析
1、矩阵采用三元组顺序表表示，设计存储结构时，给矩阵一个首地址及初始大小，由初始化分配内存空间。
2、寻找马鞍点时采取的算法是分别求出每行最小值和每列最大值用两个数组存储，再用两层for循环控制两个数组的每个元素进行比较，当值相同时，对应的行标和列标即为马鞍点位置。
开始将行最小值和列最大值分别赋为对应行行首元素值和对应列列首元素值，向后遍历时应从行或列的第二个元素开始。
3、由于马鞍点的情况较少，一般情况下都不存在马鞍点，尤其是对随机生成的矩阵，因此又设计了手动创建矩阵的功能，便于验证，同时在主函数中设计了循环，提供创建新矩阵命令时则才会将之前的矩阵和马鞍点清空，提供退出命令时才退出。
五、用户说明
1、本程序的运行环境为windows7（64位）操作系统，执行文件为求马鞍点.exe；
2、进入演示程序后，即显示可进行操作的菜单，根据菜单输入相应的操作序号即可进行相应的操作。
如图所示：
选项1：
手动创建新矩阵
按提示依次输入行数、列数和相应的所有元素值
选项2：
创建随机新矩阵
按提示输入行数和列数后自动完成矩阵的创建
选项3：
输出创建的矩阵
输出m行n列的矩阵
选项4：
输出矩阵的马鞍点
依次输出各马鞍点的三元组形式
选项5：
退出
按任意键退出
六、测试结果
1、手动创建一个存在马鞍点的矩阵
2、创建一个随机矩阵
七、附录（源代码及部分注释）
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#defineMAXMATRIXSIZE10000
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineOVERFLOW-1
#defineINIT0
typedefintElemType;
typedefintStatus;
typedefstruct{
inti,j;
ElemTypee;
}Triple;//数据类型三元组
typedefstruct{
Triple*base;//矩阵基址
intMatrixSize;//当前的矩阵大小
intmu,nu;//当前长度
}Matrix;//矩阵抽象数据类型
StatusInitMatrix（Matrix*M）;//初始化矩阵M
StatusCreateMatrix（Matrix*M）;//创建随机矩阵
StatusCreateMatrixSelf（Matrix*M）;//手动创建矩阵
voidClearMatrix（Matrix*M）;//清空矩阵
voidClearSaddlePoint（Triple*saddle）;//清空马鞍点
StatusPrintMatrix（MatrixM）;//以阵列形式输出矩阵
StatusPrintSaddlePoint（MatrixM,Triple*saddle）;//输出矩阵的马鞍点
StatusGetSaddlePoint（MatrixM,Triple*saddle）;//求矩阵M的马鞍点
voidmain（）
{
MatrixM;
InitMatrix（&M）;
Triplesaddle[25];
intchoice;
Statusstatus=INIT;
while（status!
=OK）{
printf（"**************************************************\n"）;
printf（"1、CreateNewMatrixByYourself\n"）;
printf（"2、CreateNewMatrixRandomly\n"）;
printf（"3、PrintMatrix\n"）;
printf（"4、PrintSaddlePoint\n"）;
printf（"5、Exit\n"）;
printf（"YourChoice:
"）;
scanf（"%d",&choice）;
if（choice==1||choice==2）{
ClearMatrix（&M）;
ClearSaddlePoint（saddle）;
}
switch（choice）{
case1:
CreateMatrixSelf（&M）;
break;
case2:
CreateMatrix（&M）;
break;
case3:
PrintMatrix（M）;
break;
case4:
GetSaddlePoint（M,saddle）;
PrintSaddlePoint（M,saddle）;
break;
default:
status=OK;
break;
}
}
}
StatusInitMatrix（Matrix*M）{
M->base=（Triple*）malloc（MAXMATRIXSIZE*sizeof（Triple））;
if（!
M->base）
exit（OVERFLOW）;
M->mu=M->nu=0;
M->MatrixSize=MAXMATRIXSIZE;
returnOK;
}
StatusCreateMatrix（Matrix*M）{
intm,n,p=0;
intvalue;
srand（（int）time（NULL））;
printf（"PleaseInputTheLinesAndColumnsOfTheMatrix:
\n"）;
printf（"TheLineNumber:
"）;
scanf（"%d",&M->mu）;
printf（"TheColumnNumber:
"）;
scanf（"%d",&M->nu）;
for（m=1;m<=M->mu;m++）{
for（n=1;n<=M->nu;n++）{
if（rand（）%2）
M->base[p].e=rand（）%20;
else
M->base[p].e=rand（）%20-20;
M->base[p].i=m;
M->base[p].j=n;
p++;
}
}
returnOK;
}
StatusCreateMatrixSelf（Matrix*M）{
intm,n,p=0;
intvalue;
srand（（int）time（NULL））;
printf（"PleaseInputTheLinesAndColumnsOfTheMatrix:
\n"）;
printf（"TheLineNumber:
"）;
scanf（"%d",&M->mu）;
printf（"TheColumnNumber:
"）;
scanf（"%d",&M->nu）;
for（m=1;m<=M->mu;m++）{
for（n=1;n<=M->nu;n++）{
scanf（"%d",&M->base[p].e）;
M->base[p].i=m;
M->base[p].j=n;
p++;
}
}
returnOK;
}
voidClearMatrix（Matrix*M）{
M->mu=M->nu=0;
}
StatusPrintMatrix（MatrixM）{
inti,j,k=0;
Triple*p=M.base;
if（M.mu==0&&M.nu==0）{
printf（"矩阵为空!
\n"）;
returnFALSE;
}
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"）;
returnTRUE;
}
StatusGetSaddlePoint（MatrixM,Triple*saddle）{
introw,col;
intp=0,q=0,order=0;
intl_min[25],w_max[25];
for（row=1;row<=M.mu;row++）{
p=（row-1）*M.nu;//行首元素的下标
l_min[row]=M.base[p].e;//令每行的第一个元素为最大值
for（col=2;col<=M.nu;col++）{//从每行的第二个元素开始遍历
p++;//同一行元素存储位置连续，下标下移
if（l_min[row]>M.base[p].e）
l_min[row]=M.base[p].e;
}
}
for（col=1;col<=M.nu;col++）{
w_max[col]=M.base[col-1].e;//令每列的第一个元素为最大值
for（row=2;row<=M.mu;row++）{//从每列的第二个元素开始遍历
q=（row-1）*M.nu+col-1;//col列的第row个元素的下标，完成同一列元素的依次遍历
if（w_max[col]w_max[col]=M.base[q].e;
}
}
for（p=1;p<=M.mu;p++）{
for（q=1;q<=M.nu;q++）{
if（l_min[p]==w_max[q]）{
saddle[order].i=p;
saddle[order].j=q;
saddle[order++].e=l_min[p];
}
}
}
saddle[order].i=0;
saddle[order].j=0;
saddle[order].e=0;
returnOK;
}
StatusPrintSaddlePoint（MatrixM,Triple*saddle）{
Triple*p=saddle;
if（M.mu==0&&M.nu==0）{
printf（"矩阵为空!
\n"）;
returnFALSE;
}
if（p->i==0&&p->j==0）{
printf（"无马鞍点!
\n"）;
returnFALSE;
}
printf（"各马鞍点的坐标及值:
\n\n"）;
printf（"行列元素值\n"）;
while（p->i>0）{
printf（"%3d%4d%6d\n",p->i,p->j,p->e）;
p++;
}
printf（"\n"）;
returnTRUE;
}
voidClearSaddlePoint（Triple*saddle）{
Triple*p=saddle;
while（p->i>0）{
p->e=0;
p->i=0;
p->j=0;
p++;
}
}
升级会员 