#include"stdio.h"
#include"stdlib.h"
#define MAX 100
typedef struct OLNode
{
int row, col;
int v;
struct OLNode* right, * down;
}OLNode, * OLink;
typedef struct
{
OLNode* rhead[MAX], * chead[MAX];
int m, n, t;
}CrossList;
void CreateCrossList(CrossList* M)
{
int m, n, i, r, c;
OLNode* p, * q;
printf("请输入矩阵行数和列数:");
scanf_s("%d%d", &m, &n);
M->m = m;
M->n = n;
M->t = m * n;
for (i = 1; i <= m; i++)
M->rhead[i] = NULL;
for (i = 1; i <= n; i++)
M->chead[i] = NULL;
for (r = 1; r <= m; r++)
for (c = 1; c <= n; c++)
{
p = (OLNode*)malloc(sizeof(OLNode));
p->row = r;
p->col = c;
printf("输入第%d行,第%d列的值:", r, c);
scanf_s("%d", &p->v);
p->right = NULL;
p->down = NULL;
if (M->rhead[r] == NULL)
{
M->rhead[r] = p;
}
else
{
if (p->col < M->rhead[r]->col)
{
p->right = M->rhead[r];
M->rhead[r] = p;
}
else
{
for (q = M->rhead[r]; q->right != NULL && q->right->col < c; q = q->right);
p->right = q->right;
q->right = p;
}
}
if (M->chead[c] == NULL)
{
M->chead[c] = p;
}
else
{
if (p->row < M->chead[c]->row)
{
p->down = M->chead[c];
M->chead[c] = p;
}
else
{
for (q = M->chead[c]; q->down != NULL && q->down->row < r; q = q->down);
p->down = q->down;
q->down = p;
}
}
}
}
void ShowMatrix(CrossList* M)
{
int i, j;
OLNode* p;
int t = 1;
for (i = 1; i <= M->m; i++)
{
p = M->rhead[i];
if (M->rhead[i])
for (j = 1; j <= M->n; j++)
if (p->col == j)
{
printf("%-4d", p->v);
if (p->right)
p = p->right;
}
else
printf("0 ");
else
{
for (j = 1; j <= M->n; j++)
printf("0 ");
}
printf("\n");
}
}
void Saddle(CrossList* M)
{
int i, j = 0, t;
OLNode* q, * p, * max, ** Min, * s;
Min = &s;
s = (OLNode*)malloc(M->n + 1 * sizeof(OLNode));
for (i = 1; i <= M->m; i++)
{
for (t = 0; t < M->n; t++)
Min[t] = NULL;
t = 0;
Min[t] = M->rhead[i];
for (p = M->rhead[i]; p; p = p->right)
{
if (p->v < Min[t]->v)
{
Min[t] = p;
}
}
for (p = M->rhead[i]; p; p = p->right)
{
if (p->v == Min[t]->v && p != Min[t])
{
Min[++t] = p;
}
}
for (t=0;Min[t];t++)
{
max = M->chead[Min[t]->col];
for (q = M->chead[Min[t]->col]; q; q = q->down)
{
if (q->v > max->v) {
max = q;
}
}
if (max == Min[t])
{
j++;
printf("第%d个鞍点为:%-3d %-3d %-3d\n", j, max->row, max->col, max->v);
}
}
}
if (j == 0)printf("该矩阵不存在鞍点!\n");
}
void main()
{
CrossList A;
CreateCrossList(&A);
printf("第一个矩阵为:\n");
ShowMatrix(&A);
Saddle(&A);
}