寻找矩阵中的马鞍点

设计任务:矩阵A中的元素若满足:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称元素A[i,j]为该矩阵的一个马鞍点。求出m*n矩阵的所有马鞍点。

要求:使用二维数组、堆分配数组、三元组、十字链表完成上述操作并比较效率。

  1. 设计题目与设计任务(设计任务书)

用不同的存储结构实现寻找m*n的矩阵中的马鞍点的算法。

  1. 前言(绪论)(设计的目的、意义等)

鞍点(Saddle point)在微分方程中,沿着某一方向是稳定的,另一条方向是不稳定的奇点,叫做鞍点。在泛函中,既不是极大值点也不是极小值点的临界点,叫做鞍点。在矩阵中,一个数在所在行中是最大值,在所在列中是最小值,则被称为鞍点。在物理上要广泛一些,指在一个方向是极大值,另一个方向是极小值的点。所以,寻找马鞍点的算法研究是十分有必要的。

  1. 设计主体(各部分设计内容、分析、结论等)

3.1需求分析

该程序主要功能是在一个m*n的矩阵中寻找马鞍点,如果马鞍点存在,则输入该马鞍点的位置信息以及该点的值;如果马鞍点不存在,则输出“没有马鞍点”的提示信息。

程序流程图:

输入形式:

首先输入两个数字,代表矩阵的行数m和列数n。

然后输入m行n列的矩阵。

输出形式:如果马鞍点存在,则输出马鞍点的位置和值,否则输出“没有马鞍点”。

测试样例1:

输入:

4 4

9 7 6 8

20 26 22 25

28 36 25 30

12 4 2 6

输出:

第3行第3列的25为马鞍点

 

测试样例2:

输入:

5 5

9 5 3 4 8

8 4 5 1 7

5 4 7 2 3

5 8 6 2 1

4 5 7 6 9

输出:

没有马鞍点

 

3.2系统实现

通过O(n2)时间复杂度的对数组的遍历,寻找出数组中每一行的最小的数字,并存储在数组minn中,寻找出数组中每一列的最大的数字,并存储在数组maxx中,如果minn和maxx数组中存在相同的数则说明该数为该矩阵的马鞍点。

3.3用户手册

此时输入两个数字,代表行和列

此时输入我们的2行2列的矩阵

3.4测试

测试样例1:

测试样例2:

3.5效率比较

下面四种方法的时间复杂度均为O(n2)。

二维数组法:定义方便,但不能灵活的控制内存空间。

堆分配数组法:能灵活的控制内存空间,能自由的控制数组的生存时间。

三元组法:在该程序中代码较为复杂,且花费了更多的空间。

十字链表法:在稀疏矩阵的时候能够省下较多的存储空间,但代码较为复杂。

 

二维数组法代码:

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int m ,n;
    bool flag = false;
    cout<<"请输入行数m和列数n:"<<endl;
    cin>>m>>n;
    cout<<"请输入m行n列的矩阵:"<<endl;
    flag = false;
    int minn[n+1];
    int maxx[m+1];
    memset(minn,0,sizeof(minn));//把数组置为0
    memset(maxx,0,sizeof(maxx));//把数组置为0
    int a[m+1][n+1];
    for(int i = 0; i<m; i++)
    {
        for(int j = 0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0; i<m; i++) //求出每行最小数,存在minn数组中
    {
        minn[i]=a[i][0];
        for(int j=1; j<n; j++)
            if(minn[i]>a[i][j])
                minn[i]=a[i][j];
    }
    for(int j=0; j<n; j++) //求出每列最大数,存在maxx数组中
    {
        maxx[j]=a[0][j];
        for(int i=1; i<m; i++)
            if(maxx[j]<a[i][j])
                maxx[j]=a[i][j];
    }
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(minn[i]==maxx[j])//找到马鞍点
            {
                cout<<"第"<<i+1<<"行第"<<j+1<<"列的"<<a[i][j]<<"为马鞍点"<<endl;//i+1 j+1原因:第几行第几列从1开始,而数组从0开始
                flag  = true;
            }
        }
    }
    if(flag == false)
    {
        cout<<"没有马鞍点"<<endl;
    }
}

 

堆分配数组法代码:

#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
int main()
{
    int m ,n;
    bool flag = false;
        cout<<"请输入行数m和列数n:"<<endl;
        cin>>m>>n;
        cout<<"请输入m行n列的矩阵:"<<endl;
        flag = false;
        int *minn = (int*)malloc(n*sizeof(int));
        int *maxx = (int*)malloc(m*sizeof(int));
        memset(minn,0,sizeof(minn));//把数组置为0
        memset(maxx,0,sizeof(maxx));//把数组置为0
        int **a=(int**)malloc(sizeof(int*)*m);
        for(int i=0; i<m; i++)
        {
            a[i]=(int*)malloc(sizeof(int)*n);
        }
        for(int i = 0; i<m; i++)
        {
            for(int j = 0; j<n; j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=0; i<m; i++) //求出每行最小数,存在minn数组中
        {
            minn[i]=a[i][0];
            for(int j=1; j<n; j++)
                if(minn[i]>a[i][j])
                    minn[i]=a[i][j];
        }
        for(int j=0; j<n; j++) //求出每列最大数,存在maxx数组中
        {
            maxx[j]=a[0][j];
            for(int i=1; i<m; i++)
                if(maxx[j]<a[i][j])
                    maxx[j]=a[i][j];
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(minn[i]==maxx[j])//找到马鞍点
                {
                    cout<<"第"<<i+1<<"行第"<<j+1<<"列的"<<a[i][j]<<"为马鞍点"<<endl;//i+1 j+1原因:第几行第几列从1开始,而数组从0开始
                    flag  = true;
                }
            }
        }
        if(flag == false)
        {
            cout<<"没有马鞍点"<<endl;
        }
        free(minn);
        free(maxx);
        free(a);
}

 

三元组法代码:

#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;

typedef struct
{
    int i,j,e;
} Triple; //数据类型 三元组

typedef struct
{
    Triple *base; //矩阵基址
    int MatrixSize;	//当前的矩阵大小
    int mu,nu;	//当前长度
} Matrix; //矩阵抽象数据类型

int main()
{
    while(1)
    {
        bool flag = false;
        int m,n,p=0;
        int value;
        Matrix a;
        cout<<"请输入行数m和列数n:"<<endl;
        cin>>a.mu>>a.nu;
        a.base=(Triple *)malloc(a.mu*a.nu*sizeof(Triple));
        cout<<"请输入m行n列的矩阵:"<<endl;
        flag = false;
        int minn[a.mu];
        int maxx[a.nu];
        memset(minn,0,sizeof(minn));//把数组置为0
        memset(maxx,0,sizeof(maxx));//把数组置为0
        for(int i = 0; i<a.mu; i++)
        {
            for(int j = 0; j<a.nu; j++)
            {
                cin>>a.base[p].e;
                a.base[p].i = i;
                a.base[p].j = j;
                p++;
            }
        }
        p = 0;
        int row,col;
        int q=0,order=0;
        for(row=1; row<=a.mu; row++)
        {
            p=(row-1)*a.nu;//行首元素的下标
            minn[row]=a.base[p].e; //令每行的第一个元素为最小值
            for(col=2; col<=a.nu; col++) //从每行的第二个元素开始遍历
            {
                p++; //同一行元素存储位置连续,下标下移
                if(minn[row]>a.base[p].e)
                    minn[row]=a.base[p].e;
            }
        }
        for(col=1; col<=a.nu; col++)
        {
            maxx[col]=a.base[col-1].e;//令每列的第一个元素为最大值
            for(row=2; row<=a.mu; row++) //从每列的第二个元素开始遍历
            {
                q=(row-1)*a.nu+col-1;//col列的第row个元素的下标,完成同一列元素的依次遍历
                if(maxx[col]<a.base[q].e)
                    maxx[col]=a.base[q].e;
            }
        }
        for(p=1; p<=a.mu; p++)
        {
            for(q=1; q<=a.nu; q++)
            {
                if(minn[p]==maxx[q])
                {
                    cout<<"第"<<p<<"行第"<<q<<"列的"<<minn[p]<<"为马鞍点"<<endl;
                    flag  = true;

                }
            }
        }

        if(flag == false)
        {
            cout<<"没有马鞍点"<<endl;
        }
    }
}

 

十字链表法代码:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<limits.h>
#define   TRUE                    1
#define   FALSE                    0
#define   OK                    1
#define   ERROR                    0
#define   OVERFLOW                -2
#define   INFEASIBLE            -1

using namespace std;

typedef int ElemType;

typedef struct  OLNode
{
    int i,j;
    ElemType e;
    struct OLNode  *right, *down;
} OLNode, *OLink;
typedef struct
{
    OLink *rhead, *chead;
    int mu,nu,tu;
} CrossList;
int CreateSMatrix_OL(CrossList *M)
{
    if(M)  free(M);
    int m,n,t=0;
    printf("请输入行数m和列数n:\n");
    scanf("%d%d",&m,&n);
    printf("请输入m行n列的矩阵:\n");
    M->mu=m;
    M->nu=n;
    if(!(M->rhead=(OLink *)malloc((m+1)*sizeof(OLink))))   return ERROR;
    if(!(M->chead=(OLink *)malloc((n+1)*sizeof(OLink))))   return ERROR;
    int a,b;
    for (a=1; a<=m; a++)   M->rhead[a]=NULL;
    for (b=1; b<=n; b++)   M->chead[b]=NULL;
    int i,j,e;
    for(i=1; i<=m; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%d",&e);
            if(e!=0)
            {
                t++;
                OLNode *p,*q;
                if(!(p=(OLNode *)malloc(sizeof(OLNode))))   return ERROR;
                p->i=i;
                p->j=j;
                p->e=e;
                p->down=NULL;
                p->right=NULL;
                if(M->rhead[i]==NULL||M->rhead[i]->j>j)
                {
                    p->right=M->rhead[i];
                    M->rhead[i]=p;
                }
                else
                {
                    for(q=M->rhead[i]; (q->right)&&q->right->j<j; q=q->right);
                    p->right=q->right;
                    q->right=p;
                }
                if(M->chead[j]==NULL||M->chead[j]->i>i)
                {
                    p->down=M->chead[j];
                    M->chead[j]=p;
                }
                else
                {
                    for(q=M->chead[j]; (q->down)&&q->down->i<i; q=q->down);
                    p->down=q->down;
                    q->down=p;
                }
            }
        }
    }
    M->tu=t;
    return OK;
}
void print(CrossList M)
{
    int p,q;
    OLNode *pTemp;
    for(p=1; p<=M.mu; p++)
    {
        pTemp=M.rhead[p];
        for(q=1; q<=M.nu; q++)
        {
            if(pTemp!=NULL&&pTemp->j==q)
            {
                printf("%d ",pTemp->e);
                pTemp=pTemp->right;
            }
            else
                printf("0 ");
        }
        printf("\n");
    }
}

void findPoint(CrossList M)
{
    bool flag = false;
    int p,q;
    int minn[M.mu];
    int maxx[M.nu];
    maxx[0] = INT_MIN;
    minn[0] = INT_MAX;
    OLNode *pTemp;


    for(p=1; p<=M.mu; p++)
    {
        pTemp=M.rhead[p];
        minn[p-1] = INT_MAX;
        for(q=1; q<=M.nu; q++)
        {
            if(pTemp!=NULL&&pTemp->j==q)
            {
                if(pTemp->e < minn[p-1])
                {
                    minn[p-1] = pTemp->e;
                }
                pTemp=pTemp->right;
            }
            else
            {
                if(minn[p-1]>0){
                    minn[p-1] = 0;
                }
            }
        }
    }

    for(p=1; p<=M.nu; p++)
    {
        pTemp=M.chead[p];
        maxx[p-1] = INT_MIN;
        for(q=1; q<=M.mu; q++)
        {
            if(pTemp!=NULL&&pTemp->i==q)
            {
                if(pTemp->e > maxx[p-1])
                {
                    maxx[p-1] = pTemp->e;
                }
                pTemp=pTemp->down;
            }
            else
            {
                if(maxx[p-1]<0){
                    maxx[p-1] = 0;
                }
            }
        }
    }
    for(p=1; p<=M.nu; p++){
        cout<<maxx[p-1]<<" ";
    }
    for(int i=0; i<M.mu; i++)
        {
            for(int j=0; j<M.nu; j++)
            {
                if(minn[i]==maxx[j])//找到马鞍点
                {
                    cout<<"第"<<i+1<<"行第"<<j+1<<"列的"<<minn[i]<<"为马鞍点"<<endl;//i+1 j+1原因:第几行第几列从1开始,而数组从0开始
                    flag  = true;
                }
            }

        }
        if(flag == false)
        {
            cout<<"没有马鞍点"<<endl;
        }
}

int main()
{
    while(1){
    CrossList M;
    CreateSMatrix_OL(&M);
    findPoint(M);
    return 0;
    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注