求馬鞍點實驗報告

1、1、 實驗內(nèi)容和要求2、若矩陣采用三元組順序表表示，設(shè)計并驗證找出矩陣中所有馬鞍點的算法。2、 實驗過程及結(jié)果1、 需求分析1、將隨機生成的數(shù)定義為int型（為方便起見設(shè)定范圍為-20至19（不含0），可修改），三元組存儲的元素分別為非零元的行下標(biāo)、列下標(biāo)及該位置的元素值，零元不進行存儲。實際上在生成稀疏矩陣時是隨機選取一些位置生成非零元然后存入三元組中。2、從鍵盤輸入矩陣的行數(shù)和列數(shù)后應(yīng)能輸出三元組順序表及相應(yīng)矩陣（按行和列排列形式輸出）。3、 程序能實現(xiàn)的功能包括：初始化矩陣；產(chǎn)生新的隨機矩陣；手動輸入新的矩陣；輸出陣列形式的矩陣；找出矩陣的馬鞍點；輸出矩陣的馬鞍點的三元組形式；清空矩陣；

2、清空馬鞍點； 2、 概要設(shè)計1、矩陣的抽象數(shù)據(jù)類型定義：ADT Matrix數(shù)據(jù)對象：D= aij|i=1,2,m,j=1,2,n;Ai,jElemSet,m和n分別稱為矩陣的行數(shù)和列數(shù)數(shù)據(jù)關(guān)系：R=Row，ColRow=<ai,j，ai,j+1>|1im, 1jn-1Col =<ai,j，ai+1,j>|1im-1, 1jn基本操作: InitMatrix(&M)操作結(jié)果：初始化矩陣MCreateTSMatrix(&M)操作結(jié)果：創(chuàng)建一個隨機矩陣MCreateMatrixSelf(&M)操作結(jié)果：手動創(chuàng)建一個矩陣MPrintTSMatrix(M

3、)初始條件：矩陣M已存在操作結(jié)果：以陣列形式輸出矩陣GetSaddlePoint(M,&saddle)初始條件：矩陣M已存在操作結(jié)果：找出矩陣M的馬鞍點用三元組形式存儲到saddle中PrintSaddlePoint(M,&saddle)初始條件：矩陣M已存在，其馬鞍點存儲在三元組saddle中操作結(jié)果：輸出矩陣M的馬鞍點,即saddle中的元素ClearMatrix(&M)初始條件：矩陣M已存在操作結(jié)果：清空矩陣ClearSaddlePoint(&saddle)初始條件：saddle中存儲了矩陣的馬鞍點三元組形式操作結(jié)果：清空馬鞍點ADT Matrix； 本程

4、序模塊結(jié)構(gòu)1 主函數(shù)模塊void main()while(命令不是退出)printf(" 選項：n");printf("Your Choice:");if(創(chuàng)建新的矩陣)清空之前的矩陣和馬鞍點；switch(choice)case 1:自己創(chuàng)建新矩陣；case 2:創(chuàng)建隨機的新矩陣；case 3:輸出創(chuàng)建的矩陣；case 4:找出馬鞍點并輸出；default:退出； 三、詳細設(shè)計1、基本數(shù)據(jù)類型操作typedef int ElemType;typedef struct int i,j; ElemType e;Triple;/數(shù)據(jù)類型 三元組typedef

5、 struct Triple *base; /矩陣基址 int MatrixSize;/當(dāng)前的矩陣大小 int mu,nu;/當(dāng)前長度Matrix;/矩陣抽象數(shù)據(jù)類型2、參數(shù)設(shè)置：#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)/創(chuàng)建一個隨機矩陣，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)/手動創(chuàng)建一個矩陣，即手動輸入，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)/將矩陣行數(shù)和列數(shù)置為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;/行首元素的下標(biāo)l_minrow=M.basep.e; /令每行的第一個元素為最大值for(col=2;col<=M.nu;col+)/從每行的第二個元素開始遍歷p+; /同一行元素存儲位置連續(xù)

10、，下標(biāo)下移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個元素的下標(biāo)，完成同一列元素的依次遍歷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("各馬鞍點的坐標(biāo)及值: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+; 主函數(shù)算法：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; 四、調(diào)試分析1、矩陣采用三元組順序表表示，設(shè)計存儲結(jié)構(gòu)時，給矩陣一個首地址及初始大小，由初始化分配內(nèi)存空間。2、尋找馬鞍點時采取的算法是分別求出每行最小值和每列最大值用兩個數(shù)組存儲，再用兩層for循環(huán)控制兩個數(shù)組的每個元素進行比較，當(dāng)值相同時，對應(yīng)的行標(biāo)和列標(biāo)即為馬鞍點位置。開始將行最小值和列最大值分別賦為對應(yīng)行行首元素值和對應(yīng)列列首元素值，向后遍歷時應(yīng)從行或列的第二個元素開始。3、由于馬鞍點的情況較少，一般情

16、況下都不存在馬鞍點，尤其是對隨機生成的矩陣，因此又設(shè)計了手動創(chuàng)建矩陣的功能，便于驗證，同時在主函數(shù)中設(shè)計了循環(huán)，提供創(chuàng)建新矩陣命令時則才會將之前的矩陣和馬鞍點清空，提供退出命令時才退出。 五、用戶說明1、 本程序的運行環(huán)境為windows 7（64位）操作系統(tǒng)，執(zhí)行文件為求馬鞍點.exe；2、 進入演示程序后，即顯示可進行操作的菜單，根據(jù)菜單輸入相應(yīng)的操作序號即可進行相應(yīng)的操作。如圖所示： 選項1：手動創(chuàng)建新矩陣按提示依次輸入行數(shù)、列數(shù)和相應(yīng)的所有元素值選項2：創(chuàng)建隨機新矩陣按提示輸入行數(shù)和列數(shù)后自動完成矩陣的創(chuàng)建選項3：輸出創(chuàng)建的矩陣輸出m行n列的矩陣選項4：輸出矩陣的馬鞍點依次輸出各馬鞍點

17、的三元組形式選項5：退出按任意鍵退出 六、測試結(jié)果1、手動創(chuàng)建一個存在馬鞍點的矩陣2、創(chuàng)建一個隨機矩陣七、附錄（源代碼及部分注釋）#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;/數(shù)據(jù)類型 三元組typedef struct Triple *base; /矩陣基址 int MatrixSize;/當(dāng)前的矩陣大小int mu,nu;/當(dāng)前長度Matrix;/矩陣抽象數(shù)據(jù)類型Status InitMatrix(Matrix *M);/初始化矩陣MStatus CreateMatrix(Matrix *M);/創(chuàng)建隨機矩陣Status CreateMatrixSelf(Matrix *M);/手動創(chuàng)建矩陣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;/行首元素的下標(biāo)l_minrow=M.basep.e; /令每行的第一個元素為最大值for(col=2;col<=M.nu;col+)/從每行的第二個元素開始遍歷p+; /同一行元素存儲位置連續(xù)，下標(biāo)下移if(l_minrow>M.basep.e)