c - 另一个矩阵内的矩阵
问题描述
我应该使用什么方法来编写一个检查矩阵是否包含在另一个矩阵中的函数？例如：
matrix A matrix B
1 2. 3. 4 5 2 3
6 7. 8. 9 10 7 8
11 12. 13. 14 15 12 13
16 17 18 19 20
我添加了点以指出矩阵 A 中的矩阵 B。
到目前为止，我已经写了这个：
#include <stdio.h>
int matrica_sadrzana(int* m1, int v1, int s1, int* m2, int v2, int s2){
/* What needs to go here? */
return 0;
}
int main() {
int i,j,v1,v2,s1,s2,sadrzana;
int matricaA[100][100],matricaB[100][100];
printf("Unesite visinu i sirinu matrice A: ");
scanf("%d %d",&v1,&s1);
printf("Unesite visinu i sirinu matrice B: ");
scanf("%d %d",&v2,&s2);
for(i=0; i<v1; i++){
for(j=0; j<s1; j++){
scanf("%d",&matricaA[i][j]);
}
}
for(i=0; i<v2; i++){
for(j=0; j<s2; j++){
scanf("%d",&matricaB[i][j]);
}
}
sadrzana=matrica_sadrzana(matricaA,v1,s1,matricaB,v2,s2);
return 0;
}
解决方案
您可以使用固定长度数组或可变长度数组来执行此操作。
固定长度数组
你从固定长度的数组开始，所以第一个程序跟随你。您必须在传递数组时指定数组的第二维——否则，代码将访问错误的数据。您的编译器应该一直在抱怨对您的函数的调用。我使用初始化数据而不是从标准输入中读取。输入代码被注释掉（并且未经测试）。
#include <stdio.h>
static int matrica_subset(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
for (int m = 0; m < r2; m++)
{
for (int n = 0; n < c2; n++)
{
printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r1+m, c1+n, m1[r1+m][c1+n], m, n, m2[m][n]);
if (m1[r1+m][c1+n] != m2[m][n])
return 0;
}
}
return 1;
}
static int matrica_sadrzana(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
if (c1 < c2 || r1 < r2)
return 0;
int c_max = c1 - c2 + 1;
int r_max = r1 - r2 + 1;
for (int r = 0; r < r_max; r++)
{
for (int c = 0; c < c_max; c++)
{
printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
if (m1[r][c] == m2[0][0])
{
if (matrica_subset(m1, r, c, m2, r2, c2) != 0)
{
printf("match at m1[%d][%d]\n", r, c);
return 1;
}
}
}
}
return 0;
}
int main(void)
{
int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
int matricaA[100][100] =
{
{ 1, 2, 3, 4, 5, },
{ 6, 7, 8, 9, 10, },
{ 11, 12, 13, 14, 15, },
{ 16, 17, 18, 19, 20, },
};
int matricaB[100][100] =
{
{ 2, 3, },
{ 7, 8, },
{ 12, 13, },
};
//printf("rows and columns for matrix A: ");
//scanf("%d %d", &r1, &c1);
//printf("rows and columns for matrix B: ");
//scanf("%d %d", &r2, &c2);
//printf("data for matrix A:\n");
//for (int i = 0; i < r1; i++)
//{
// for (int j = 0; j < c1; j++)
// {
// scanf("%d", &matricaA[i][j]);
// }
//}
//printf("data for matrix B:\n");
//for (int i = 0; i < r2; i++)
//{
// for (int j = 0; j < c2; j++)
// {
// scanf("%d", &matricaB[i][j]);
// }
//}
sadrzana = matrica_sadrzana(matricaA, r1, c1, matricaB, r2, c2);
printf("sadrzana: %d\n", sadrzana);
return 0;
}
该matrica_subset()函数m1从 row r1、 column开始查找与大小活动行和活动列（在 中定义的 100x100 矩阵的一个小子集）的c1匹配。m2r2c2main()
坐标搜索，matrica_sadrzana()检查左上角是否m2与当前位置匹配，m1并在匹配时继续使用该matrica_subset()函数进行搜索。
样本输出：
sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 19; m2[2][1] = 13
sa: m1[0][2] = 3; m2[0][0] = 2
sa: m1[0][3] = 4; m2[0][0] = 2
sa: m1[1][0] = 6; m2[0][0] = 2
sa: m1[1][1] = 7; m2[0][0] = 2
sa: m1[1][2] = 8; m2[0][0] = 2
sa: m1[1][3] = 9; m2[0][0] = 2
sadrzana: 0
可变长度数组
使用可变长度数组的替代方法需要matrica_subset()函数的额外参数来指定数组的实际大小（r1和c1）以及数组中的搜索位置（r0和c0）。
#include <stdio.h>
static void dump_matrix(const char *tag, int r, int c, int m[r][c])
{
printf("%s (%dx%d):\n", tag, r, c);
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
printf(" %3d", m[i][j]);
putchar('\n');
}
}
static int matrica_subset(int r1, int c1, int m1[r1][c1], int r0, int c0, int r2, int c2, int m2[r2][c2])
{
for (int m = 0; m < r2; m++)
{
for (int n = 0; n < c2; n++)
{
printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r0+m, c0+n, m1[r0+m][c0+n], m, n, m2[m][n]);
if (m1[r0+m][c0+n] != m2[m][n])
return 0;
}
}
return 1;
}
static int matrica_sadrzana(int r1, int c1, int m1[r1][c1], int r2, int c2, int m2[r2][c2])
{
if (c1 < c2 || r1 < r2)
return 0;
int c_max = c1 - c2 + 1;
int r_max = r1 - r2 + 1;
for (int r = 0; r < r_max; r++)
{
for (int c = 0; c < c_max; c++)
{
printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
if (m1[r][c] == m2[0][0])
{
if (matrica_subset(r1, c1, m1, r, c, r2, c2, m2) != 0)
{
printf("match at m1[%d][%d]\n", r, c);
return 1;
}
}
}
}
return 0;
}
int main(void)
{
int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
int matricaA[4][5] =
{
{ 1, 2, 3, 4, 5, },
{ 6, 7, 8, 9, 10, },
{ 11, 12, 13, 14, 15, },
{ 16, 17, 18, 19, 20, },
};
int matricaB[3][2] =
{
{ 2, 3, },
{ 7, 8, },
{ 12, 13, },
};
//printf("rows and columns for matrix A: ");
//scanf("%d %d", &r1, &c1);
//printf("rows and columns for matrix B: ");
//scanf("%d %d", &r2, &c2);
//printf("data for matrix A:\n");
//for (int i = 0; i < r1; i++)
//{
// for (int j = 0; j < c1; j++)
// {
// scanf("%d", &matricaA[i][j]);
// }
//}
//printf("data for matrix B:\n");
//for (int i = 0; i < r2; i++)
//{
// for (int j = 0; j < c2; j++)
// {
// scanf("%d", &matricaB[i][j]);
// }
//}
dump_matrix("Matrix A", r1, c1, matricaA);
dump_matrix("Matrix B", r2, c2, matricaB);
sadrzana = matrica_sadrzana(r1, c1, matricaA, r2, c2, matricaB);
printf("sadrzana: %d\n", sadrzana);
return 0;
}
样本输出：
Matrix A (4x5):
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
Matrix B (3x2):
2 3
7 8
12 13
sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 13; m2[2][1] = 13
match at m1[0][1]
sadrzana: 1
惊喜，惊喜——它返回相同的结果。搜索功能适用于可变长度数组；数据仍然存储在固定大小的数组中（因为您不能对 VLA 使用初始化程序），但大小比原始代码中的要小得多。
VLA 代码还转储输入矩阵；FLA 代码没有。将转储代码添加到第一个程序中是相当容易的，但打印功能并不那么通用。可以安排转储 RxC 矩阵的 NxM 子段；这对代码来说有点繁琐，但非常通用，可以在两个程序中使用——但 VLA 程序会简单地设置 N 和 R 相等，M 和 C 相等。
推荐阅读
- c++ - 如何将字符串数组转换为 const char **？
- python - 如何使用以下代码在 connect 4 中进行移动功能？
- c - 在范围内和范围外定义外部变量
- bash - Bash - While 循环不会停止
- ios - ScrollView 的宽度和高度与其子元素重叠
- java - 有没有办法使用 Spring boot 在 postgres DB 中使用 pg_tye_advisory_lock？
- javascript - 如何获取用户的年龄（以年为单位）
- c - pcap_set_rfmon 成功但没有效果
- google-cloud-speech - 什么是谷歌云语音要求/先决条件
- assembly - 为什么 SIMD 比标量对应物慢