c - 在二维数组中查找子字符串（拼图）
问题描述
我一直在尝试制作一个单词拼图（不使用任何库函数），就像您在报纸上看到的那样：
15 rows 12 colums
X T Z M Q Y K C E C F H -->12 chars
S H O U T E X O E A P I
X G T L Q B E L T N F K
'
'
'
正如您在第二行中看到的那样，有一个单词 SHOUT。现在拼图的设计使用户可以逐行输入他们想要的任何类型的字符集。
我想要做的是当一个词被搜索（如 SHOUT）时，我会返回它的起始索引。我想象的索引将从 0 开始并以 180 结束，因为 12*15=180 就像这样清楚：
X T Z M Q Y K C E C F H
0 1 2 3 4 5 6 7 8 9 10 11
S H O U T E X O E A P I
12 13 14 15 16 17 18 19 20 21 22 23
'
'
'
'''''''''''''''''''179
没有图片很难解释，希望你能理解。
现在棘手的是单词可以在各个方向（从上到下，从下到上，从左到右，从右到左）。我已经编写了大部分代码，但不断出错，它只能检查单词是否从左到右存在。
#include <stdio.h>
#define COLUNM 12
#define ROW 15
int computeLength (char str[50]) {
int i;
for (i = 0; str[i] != '\0'; ++i) {
}
return i;
}
int findString(char matrix[ROW][COLUNM], char string[], int length) {
int i = 0, j, k = 0, searchlenght = 0;
length = computeLength(string);
for (j = 0; j < ROW; j++) {
if (matrix[j][k] == string[k]) {
searchlenght++;
}
}
i++;
if (searchlength == length) {
return i;
}
}
int main() {
int i, j = 0;
char matrix[ROW][COLUNM];
char string[50];
int b = 1;
for (i = 0; i < ROW; i++) {
printf("Enter line %d of the puzzle :\n", i + 1);
scanf("%s", &matrix[j][i]);
j++;
}
while (b > 0) {
printf("Enter the string to be searched in the puzzle:\n");
scanf("%s", &string[50]);
if ((string[0] != 'q') || (string[0] != 'Q')) {
b = 0;
}
}
return 0;
}
我不认为这很难用 python 实现，但我对 C 非常不熟悉，以至于我不断收到错误和警告。
唯一需要工作的部分是 findString 函数。不要打扰输入，因为我会自己测试它。
能否请你帮忙？
**唯一不起作用的部分是length=computeLength(str1); thşs 当我输入 computeLength("Shout") 它返回 5 但在这段代码中它返回 2 这弄乱了结果**
int findString(char matrix[ROW][COLUNM],char str1[],int length){
int i,j,wordcounting;
int true=1;
length=computeLength(str1);
printf("%d",length);
for(j=0;j<ROW;j++){
if(matrix[i][j]==str1[0]){
for(wordcounting=1;wordcounting<length;wordcounting++){
if((matrix[i][j+wordcounting]!=str1[wordcounting])){
true=0;
break;
}
}
}
i++;}
if(true==1){return (i-length);}
}
当我说 printf("%d",computeLength(string)); 甚至在我输入一个字符串之前它变成了 2
解决方案
这是一个 loooooooog 的答案，我会在其中尽可能多地解释您的问题，如何解决它们，最后如何逐步实施搜索以达到最终解决方案。
好好读书！
你的代码有很多问题，首先它无法编译。
第29行无效，替换
int findString(char matrix[ROW][COLUNM],char string[15],int computeLength(string[15])){
经过
int findString(char matrix[ROW][COLUNM], char string[15])
另请注意，大小 15 是无用的，您可以使用char string[]或char * string作为参数字符串
第39行无效，替换
if(count==computeLength(string[15])){
经过
if(count==computeLength(string)){
现在您可以编译您的程序，但这还不够。
main中的一些问题。
您交换了行中的索引
scanf("%s",&matrix[j][i]);
它可以替换为
scanf("%s",&matrix[i][0]);
（我使用 0 而不是j，因为它更清楚，不要求我们检查j值 0）
但这还不够，如果输入无效， scanf可以读取超过COLUNM 个字符，甚至输入是 12 个字符，正如您所期望的那样，您忘记了scanf也会写入空字符来完成字符串，因此它写入 13 个字符。
一种方法是读取比COLUMN more 2 长的字符串并检查输入字符串的长度。所以你的for可以替换为：
for(i = 0 ; i < ROW ; i++)
{
printf("Enter line %d of the puzzle :\n",i+1);
if ((scanf("%49s", string) != 1) ||
(strlen(string) != COLUMN)) {
puts("invalid line");
return -1;
}
memcpy(&matrix[i][0], string, COLUMN);
i++;
}
还要注意最后i增加而不是j。
在while循环中
scanf("%s",&string[50]);
无效，因为它将结果放在string之后，索引必须为 0，实际上您可以只给出string。
和以前一样，如果输入超过 49 个字符， scanf将写出字符串，所以这样做
scanf("%49s", string);
如果您想允许在不计算最后一个空字符的情况下搜索 50 个字符的字符串，则必须将其大小设置为 51 并将 49 替换为 50。
打印和读取while循环什么都不做，很可能您想在其中调用findString并写入返回值，直到第一个读取的字符是 q 或 Q。例如：
for (;;) {
puts("Enter the string to be searched in the puzzle:");
if ((scanf("%49s", string) != 1) || (string[0] =='q') || (string[0] == 'Q'))
break;
printf("position in the puzzle: %d\n", findString(matrix, string));
}
在main的末尾，该行的兴趣是模糊的：
printf("%d",computeLength("küfür"));
在printPuzzle中，您在打印PUZZLE后错过了引入换行符，您可以将printf替换为puts。请注意，当您知道没有 % 等时，要求printf搜索是没有用的。
在查找字符串中
第一个问题是，如果count==computeLength(string)为真，您只返回一个值，您需要始终返回一个值。如果字符串不在拼图中，通常可以返回 -1，所以
return (count==computeLength(string)) ? i : -1;
但这也是错误的，有两个原因：
- 当您到达测试时，我总是将值设为 180，而不是字符串所在的位置
- 这不是因为count==computeLength(string)是真的，因为您使用递增计数的方式和下一个错误找到了字符串：
您没有正确搜索拼图中的字符串，因为您在 i 上的第一个循环通过了字符串（string[i]），最糟糕的是会访问其中的 180 个字符，而它的长度只有 49 个（没有最后的空字符）。即使找到字符串，您也不会停止搜索。并且在您的算法中，您忘记了字符串的字符必须连续放置在矩阵中，每次您（错误地）在矩阵中的任何位置找到字符串的字符时都会增加count。
考虑到您从左到右水平搜索字符串：
字符串上的循环必须是更嵌入的循环，以检查其字符在矩阵中是否连续。
您在行上有一个循环，在列上有一个循环，这是无用的，只会使工作变得复杂。因为matrix是一个数组，所以matrix[r][COLUMN]处的字符是matrix[r+1][0]处的字符，这意味着您可以通过矩阵，就像它是一串ROW*COLUMN字符一样。
我让你重写findString，它就像strstr ，除了你返回索引或 -1 而不是子字符串的地址或 NULL
[编辑搜索功能的建议]
为了解释，我将使用更易于查看的小矩阵：
#define COLUMN 3
#define ROW 5
char Matrix[ROW][COLUMN] = { { 'a', 'b' , 'c' },
{ 'd', 'e' , 'f' },
{ 'g', 'h' , 'i' },
{ 'j', 'k' , 'l' },
{ 'm', 'n' , 'o' } };
让我们从从左到右搜索开始，这类似于经典的strstr函数，除了返回值和矩阵末尾有一个回滚。如果找不到字符串，则决定值为 -1，否则它的第一个字符的位置乘以它最后一个字符的位置的 1000 倍。定义可以是：
int search_left2right(char * matrix, char * word)
{
int i;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
char * w = word;
while (*w == matrix[j]) {
if (!*++w)
return i * 1000 + j;
if (++j == ROW*COLUMN)
j = 0;
}
}
return -1;
}
使用该 main 编译和执行：
int main()
{
printf("%d\n", search_left2right((char *) Matrix, "cde"));
printf("%d\n", search_left2right((char *) Matrix, "noa"));
printf("%d\n", search_left2right((char *) Matrix, "cdf"));
return 0;
}
pi@raspberrypi:/tmp $ ./a.out
2004
13000
-1
pi@raspberrypi:/tmp $
2004 if for 2 and 4, 13000 if for 13 and 0, the string is not found in the last case, this ok
从右到左搜索。
第一个明显的方法是重用前一个函数并在搜索之前反转字符串。如果在结果中找到字符串，则第一个和最后一个字符的位置也会颠倒过来。
另一种方法是迭代字符串以反向搜索，让我们选择这种方式。
从右到左或从左到右搜索。
为了指示方向，添加了参数wstep，从左到右的值为 1，否则为 -1。定义可以是：
/* manual strlen, you want to define all string functions */
int strLen(char * s)
{
char * p = s;
while (*p)
p += 1;
return p - s;
}
int search_horiz(char * matrix, char * word, int wstep)
{
int i;
int wbegin = (wstep == 1) ? 0 : strLen(word) - 1;
int wend = (wstep == 1) ? strLen(word) - 1 : 0;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
int k = wbegin;
while (word[k] == matrix[j]) {
if (k == wend)
return (wstep == 1) ? i * 1000 + j : j * 1000 + i;
k += wstep;
if (++j == ROW*COLUMN)
j = 0;
}
}
return -1;
}
使用该 main 编译和执行：
int main()
{
printf("%d\n", search_horiz((char *) Matrix, "cde", 1));
printf("%d\n", search_horiz((char *) Matrix, "edc", -1));
printf("%d\n", search_horiz((char *) Matrix, "noa", 1));
printf("%d\n", search_horiz((char *) Matrix, "aon", -1));
printf("%d\n", search_horiz((char *) Matrix, "cdf", 1));
printf("%d\n", search_horiz((char *) Matrix, "fdc", -1));
return 0;
}
pi@raspberrypi:/tmp $ gcc -g -Wall m.c
pi@raspberrypi:/tmp $ ./a.out
2004
4002
13000
13
-1
-1
pi@raspberrypi:/tmp $
从上到下搜索。
当我们从左到右搜索时，我们将字符 from 到 string 与矩阵中的连续字符（步长为 1）进行比较，更多的是回滚。
要从上到下搜索，我们不必查看矩阵中的连续字符，我们希望保持在同一垂直方向，因此步骤为COLUMN。当然，当我们在最后一行时，情况并非如此，在这种情况下，我们回到第一行并向右移动，除了从矩阵的最后一个字符开始，我们必须回滚到第一个字符。定义可以是：
int search_top2down(char * matrix, char * word)
{
int i;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
char * w = word;
while (*w == matrix[j]) {
if (!*++w)
return i * 1000 + j;
if ((j += COLUMN) >= ROW*COLUMN)
j = (j - ROW*COLUMN + 1) % COLUMN;
}
}
return -1;
}
使用该 main 编译和执行：
int main()
{
printf("%d\n", search_top2down((char *) Matrix, "dgj"));
printf("%d\n", search_top2down((char *) Matrix, "knc"));
printf("%d\n", search_top2down((char *) Matrix, "oad"));
return 0;
}
pi@raspberrypi:/tmp $ gcc -g -Wall m.c
pi@raspberrypi:/tmp $ ./a.out
3009
10002
14003
pi@raspberrypi:/tmp $
从左到右或从上到下搜索
但是比较search_left2right和search_top2down可以看到它们的定义几乎相同，唯一的变化是矩阵中步长的值以及步长不能单独应用时的校正。所以可以有：
int search_left2right_top2down(char * matrix, char * word, int step, int correct)
{
int i;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
char * w = word;
while (*w == matrix[j]) {
if (!*++w)
return i*100 + j;
if ((j += step) >= ROW*COLUMN)
j = (j - ROW*COLUMN + correct) % COLUMN;
}
}
return -1;
}
做从左到右的步骤是1，正确的是0，做从上到下的步骤是COLUMN，正确的是1。
搜索所有四个方向
从下到上从上到下搜索所需的修改就像从左到右从右到左搜索一样。
这意味着我们可以很容易地只使用一个搜索功能来管理从左到右、从右到左、从上到下和从下到上。例如 ：
int search(char * matrix, char * word, int wstep, int step, int correct)
{
int i;
int wbegin = (wstep == 1) ? 0 : strLen(word) - 1;
int wend = (wstep == 1) ? strLen(word) - 1 : 0;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
int k = wbegin;
while (word[k] == matrix[j]) {
if (k == wend)
return (wstep == 1) ? i * 1000 + j : j * 1000 + i;
k += wstep;
if ((j += step) >= ROW*COLUMN)
j = (j - ROW*COLUMN + correct) % COLUMN;
}
}
return -1;
}
通过该主要编译和执行：
int main()
{
printf("%d\n", search((char *) Matrix, "cde", 1, 1, 0));
printf("%d\n", search((char *) Matrix, "noa", 1, 1, 0));
printf("%d\n", search((char *) Matrix, "cdf", 1, 1, 0));
putchar('\n');
printf("%d\n", search((char *) Matrix, "edc", -1, 1, 0));
printf("%d\n", search((char *) Matrix, "aon", -1, 1, 0));
printf("%d\n", search((char *) Matrix, "fdc", -1, 1, 0));
putchar('\n');
printf("%d\n", search((char *) Matrix, "dgj", 1, COLUMN, 1));
printf("%d\n", search((char *) Matrix, "knc", 1, COLUMN, 1));
printf("%d\n", search((char *) Matrix, "oad", 1, COLUMN, 1));
putchar('\n');
printf("%d\n", search((char *) Matrix, "jgd", -1, COLUMN, 1));
printf("%d\n", search((char *) Matrix, "cnk", -1, COLUMN, 1));
printf("%d\n", search((char *) Matrix, "dao", -1, COLUMN, 1));
return 0;
}
pi@raspberrypi:/tmp $ gcc -Wall m.c
pi@raspberrypi:/tmp $ ./a.out
2004
13000
-1
4002
13
-1
3009
10002
14003
9003
2010
3014
pi@raspberrypi:/tmp $
让我们注意给出 3 个参数来指示如何处理不是一个漂亮的方式，我使用它们是因为我认为最好让它们来解释，但是因为总是相同的所以很容易改进：
#include <stdio.h>
#define COLUMN 3
#define ROW 5
/* manual strlen, you want to define all string functions */
int strLen(const char * s)
{
const char * p = s;
while (*p)
p += 1;
return p - s;
}
typedef struct SearchParameters {
int wstep;
int step;
int correct;
} SearchParameters;
const SearchParameters Left2Right = { 1, 1, 0 };
const SearchParameters Right2Left = { -1, 1, 0 };
const SearchParameters Top2Bottom = { 1, COLUMN, 1 };
const SearchParameters Bottom2Top = { -1, COLUMN, 1 };
int search(const char * matrix, const char * word, SearchParameters how)
{
int i;
int wbegin = (how.wstep == 1) ? 0 : strLen(word) - 1;
int wend = (how.wstep == 1) ? strLen(word) - 1 : 0;
for (i = 0; i != ROW*COLUMN; ++i) {
int j = i;
int k = wbegin;
while (word[k] == matrix[j]) {
if (k == wend)
return (how.wstep == 1) ? i * 1000 + j : j * 1000 + i;
k += how.wstep;
if ((j += how.step) >= ROW*COLUMN)
j = (j - ROW*COLUMN + how.correct) % COLUMN;
}
}
return -1;
}
/* */
typedef struct TestCase {
const char * str;
const SearchParameters * how;
const char * strHow;
} TestCase;
void test(const char (*m)[3], const TestCase * tc)
{
int r = search((char *) m, tc->str, *(tc->how));
if (r == -1)
printf("cannot found '%s' in '%s'\n", tc->str, tc->strHow);
else
printf("'%s' found in '%s', start at %d, end at %d\n",
tc->str, tc->strHow, r / 1000, r % 1000);
}
int main()
{
static const char matrix[ROW][COLUMN] = { { 'a', 'b' , 'c' },
{ 'd', 'e' , 'f' },
{ 'g', 'h' , 'i' },
{ 'j', 'k' , 'l' },
{ 'm', 'n' , 'o' } };
static const TestCase tests[] = {
{ "cde", &Left2Right, "Left2Right" },
{ "noa", &Left2Right, "Left2Right" },
{ "cdf", &Left2Right, "Left2Right" },
{ "edc", &Right2Left, "Right2Left" },
{ "aon", &Right2Left, "Right2Left" },
{ "fdc", &Right2Left, "Right2Left" },
{ "dgj", &Top2Bottom, "Top2Bottom" },
{ "knc", &Top2Bottom, "Top2Bottom" },
{ "oad", &Top2Bottom, "Top2Bottom" },
{ "jgd", &Bottom2Top, "Bottom2Top" },
{ "cnk", &Bottom2Top, "Bottom2Top" },
{ "dao", &Bottom2Top, "Bottom2Top" }
};
int t;
for (t = 0; t != sizeof(tests) / sizeof(TestCase); t += 1)
test(matrix, &tests[t]);
return 0;
}
编译和执行：
pi@raspberrypi:/tmp $ gcc -Wall mm.c
pi@raspberrypi:/tmp $ ./a.out
'cde' found in 'Left2Right', start at 2, end at 4
'noa' found in 'Left2Right', start at 13, end at 0
cannot found 'cdf' in 'Left2Right'
'edc' found in 'Right2Left', start at 4, end at 2
'aon' found in 'Right2Left', start at 0, end at 13
cannot found 'fdc' in 'Right2Left'
'dgj' found in 'Top2Bottom', start at 3, end at 9
'knc' found in 'Top2Bottom', start at 10, end at 2
'oad' found in 'Top2Bottom', start at 14, end at 3
'jgd' found in 'Bottom2Top', start at 9, end at 3
'cnk' found in 'Bottom2Top', start at 2, end at 10
'dao' found in 'Bottom2Top', start at 3, end at 14
pi@raspberrypi:/tmp $
推荐阅读
- spring - AWS：基于 Cognito 身份验证角色限制 API 对资源的访问
- autodesk-forge - 尝试对 Forge BIM360 API 进行 API 调用时出现错误？
- python - TypeError：“元组”对象不可调用？
- javascript - 如何获取 MOV 文件格式的 videoWidth、videoHeight？
- ruby - 在本地服务器上运行 jekyll 时，出现“多个 gemspecs 错误”
- docker - Jenkins 管道在 docker 中构建
- python-3.x - 尝试调用时 PJSUA2 断言失败
- json - 颤振：'列表
' 不是类型 'String' 的子类型 - php - 删除 PHP 中两个或多个字符串文本之间的重复单词
- angular - 自定义步进器中具有待处理状态的 FormGroup