在二维数组中查找子串（谜题）
Finding Substring in 2D Array(Puzzle)
我一直在尝试制作一个单词拼图（不使用任何库函数），就像您在报纸上看到的一样：
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）我会 return 它的起始索引。我想象的索引会从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] != '[=12=]'; ++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") 它 returns 5 但在这段代码中它 returns 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
只看提到的编译错误（而且只是编译错误），我建议你这样做：
int findString(char matrix[ROW][COLUNM],char string[15])
{
int length = computeLength(string);
...
}
你不能像你那样声明函数。现在稍微进一步推荐...
已经有一个可以计算 C 字符串长度的 C 函数：
#include <string.h>
...
const char* string = "hello";
int length = strlen(string);
...
这是一个 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多2的string，检查输入字符串的长度。所以你的 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会写出string，所以
scanf("%49s", string);
如果要允许搜索 50 个字符的字符串而不计算最后的空字符，则必须将其大小设置为 51 并将 49 替换为 50。
打印和读取 while 循环什么都不做，很可能您想在其中调用 findString 并写入returned 值，直到第一个读取字符为 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。请注意，当您知道有 none.
时，要求 printf 搜索 % 等是没有用的
在findString
第一个问题是如果 count==computeLength(string) 为真，你只有 return 一个值，你需要始终 return a价值。通常，如果字符串不在拼图中，您可以 return -1，因此
return (count==computeLength(string)) ? i : -1;
但这也是错误的，原因有二：
- 当你到达测试时 i 总是值 180，而不是字符串所在的位置
- 这不是因为 count==computeLength(string) 是真的，因为你使用递增 count[=223 的方式找到了字符串=] 和下一个错误：
您没有正确搜索拼图中的字符串，因为您在 i 上的第一个循环遍历了字符串 (string[i] ), 最坏的情况下将访问其中的 180 个字符，而其长度仅为 49（没有最后的空字符）。即使找到字符串，您也不会停止搜索。在你的算法中，你忘记了字符串的字符必须连续放置在矩阵中，你每次（错误地）在你递增的矩阵中的任何地方找到字符串的字符 count.
考虑到您从左到右水平搜索字符串：
string 上的循环必须是更嵌入的循环，以检查其字符在矩阵中是否连续。
你在行上有一个循环，在列上有一个循环，这是没有用的，只会让工作变得复杂。因为 matrix 是一个数组，所以 matrix[r][COLUMN] 处的字符是 matrix[r+1] 处的字符[0]，这意味着您可以像 ROW*COLUMN 个字符一样遍历 matrix。
我让你重写 findString，它就像 strstr 除了你 return 索引或-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函数，除了return值并且在矩阵的末尾有一个回滚。如果未找到字符串，则确定值为 -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,最后一个case找不到字符串，这样就可以了
从 从右到左搜索 。
第一个明显的方法是重用以前的函数并在搜索之前反转字符串。如果在结果中找到字符串，则第一个字符和最后一个字符的位置也会颠倒。
另一种方法是在字符串上迭代以相反的顺序搜索，让我们选择这种方式。
从从右到左或从左到右搜索。
为了指示方向，添加了参数 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 $
从从上到下搜索。
当我们从左到右搜索时，我们将字符串中的字符与矩阵中的连续字符进行比较（步长为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可以看出它们的定义几乎相同，唯一change 是矩阵中步长的值，是步长不能单独应用时的修正值。所以有可能有：
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;
}
从左到右step是1，correct是0，从上到下step 是 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;
}
随着 main 编译和执行 :
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 $
我一直在尝试制作一个单词拼图（不使用任何库函数），就像您在报纸上看到的一样：
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）我会 return 它的起始索引。我想象的索引会从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] != '[=12=]'; ++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") 它 returns 5 但在这段代码中它 returns 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
只看提到的编译错误（而且只是编译错误），我建议你这样做：
int findString(char matrix[ROW][COLUNM],char string[15])
{
int length = computeLength(string);
...
}
你不能像你那样声明函数。现在稍微进一步推荐...
已经有一个可以计算 C 字符串长度的 C 函数：
#include <string.h>
...
const char* string = "hello";
int length = strlen(string);
...
这是一个 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多2的string，检查输入字符串的长度。所以你的 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会写出string，所以
scanf("%49s", string);
如果要允许搜索 50 个字符的字符串而不计算最后的空字符，则必须将其大小设置为 51 并将 49 替换为 50。
打印和读取 while 循环什么都不做，很可能您想在其中调用 findString 并写入returned 值，直到第一个读取字符为 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。请注意，当您知道有 none.
时，要求 printf 搜索 % 等是没有用的在findString
第一个问题是如果 count==computeLength(string) 为真，你只有 return 一个值，你需要始终 return a价值。通常，如果字符串不在拼图中，您可以 return -1，因此
return (count==computeLength(string)) ? i : -1;
但这也是错误的，原因有二：
- 当你到达测试时 i 总是值 180，而不是字符串所在的位置
- 这不是因为 count==computeLength(string) 是真的，因为你使用递增 count[=223 的方式找到了字符串=] 和下一个错误：
您没有正确搜索拼图中的字符串，因为您在 i 上的第一个循环遍历了字符串 (string[i] ), 最坏的情况下将访问其中的 180 个字符，而其长度仅为 49（没有最后的空字符）。即使找到字符串，您也不会停止搜索。在你的算法中，你忘记了字符串的字符必须连续放置在矩阵中，你每次（错误地）在你递增的矩阵中的任何地方找到字符串的字符 count.
考虑到您从左到右水平搜索字符串：
string 上的循环必须是更嵌入的循环，以检查其字符在矩阵中是否连续。
你在行上有一个循环，在列上有一个循环，这是没有用的，只会让工作变得复杂。因为 matrix 是一个数组，所以 matrix[r][COLUMN] 处的字符是 matrix[r+1] 处的字符[0]，这意味着您可以像 ROW*COLUMN 个字符一样遍历 matrix。
我让你重写 findString，它就像 strstr 除了你 return 索引或-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函数，除了return值并且在矩阵的末尾有一个回滚。如果未找到字符串，则确定值为 -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,最后一个case找不到字符串，这样就可以了
从 从右到左搜索 。
第一个明显的方法是重用以前的函数并在搜索之前反转字符串。如果在结果中找到字符串，则第一个字符和最后一个字符的位置也会颠倒。
另一种方法是在字符串上迭代以相反的顺序搜索，让我们选择这种方式。
从从右到左或从左到右搜索。
为了指示方向，添加了参数 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 $
从从上到下搜索。
当我们从左到右搜索时，我们将字符串中的字符与矩阵中的连续字符进行比较（步长为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可以看出它们的定义几乎相同，唯一change 是矩阵中步长的值，是步长不能单独应用时的修正值。所以有可能有：
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;
}
从左到右step是1，correct是0，从上到下step 是 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;
}
随着 main 编译和执行 :
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 $