若矩阵采用三元组顺序表表示,请用C语言设计并验证找出所有马鞍点的算法
时间: 2024-05-02 21:16:27 浏览: 21
下面是基于三元组顺序表的矩阵查找所有马鞍点的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 三元组顺序表的最大长度
typedef struct {
int row, col, val; // 行号、列号、元素值
} Triple;
typedef struct {
Triple data[MAX_SIZE + 1]; // 三元组顺序表
int rows, cols, nums; // 行数、列数、非零元素个数
} Matrix;
// 创建矩阵
void createMatrix(Matrix *mat) {
printf("请输入矩阵的行数、列数和非零元素个数:\n");
scanf("%d%d%d", &mat->rows, &mat->cols, &mat->nums);
printf("请输入矩阵的非零元素的行号、列号和元素值:\n");
for (int i = 1; i <= mat->nums; i++) {
scanf("%d%d%d", &mat->data[i].row, &mat->data[i].col, &mat->data[i].val);
}
}
// 找到矩阵的所有马鞍点
void findSaddlePoint(Matrix *mat) {
int row_min[MAX_SIZE], col_max[MAX_SIZE];
// 初始化row_min和col_max数组
for (int i = 0; i < mat->rows; i++) {
row_min[i] = MAX_SIZE;
}
for (int i = 0; i < mat->cols; i++) {
col_max[i] = -MAX_SIZE;
}
// 找到每行的最小值和每列的最大值
for (int i = 1; i <= mat->nums; i++) {
int row = mat->data[i].row - 1;
int col = mat->data[i].col - 1;
int val = mat->data[i].val;
if (val < row_min[row]) {
row_min[row] = val;
}
if (val > col_max[col]) {
col_max[col] = val;
}
}
// 找到马鞍点
for (int i = 1; i <= mat->nums; i++) {
int row = mat->data[i].row - 1;
int col = mat->data[i].col - 1;
int val = mat->data[i].val;
if (val == row_min[row] && val == col_max[col]) {
printf("马鞍点坐标为 (%d,%d),值为 %d\n", row + 1, col + 1, val);
}
}
}
int main() {
Matrix mat;
createMatrix(&mat);
findSaddlePoint(&mat);
return 0;
}
```
该算法的思路是先找到每行的最小值和每列的最大值,然后再找到满足同时为行最小值和列最大值的元素,即为马鞍点。由于马鞍点的个数不确定,因此直接输出坐标和值。