Вот ответ «ооооооооооооооооооооо даюра», где я объясню, насколько я могу, ваши проблемы, как их решить, и, наконец, как реализовать поиск шаг за шагом к окончательному решению.
Хорошего чтения!
В вашем коде много проблем, сначала он не может быть скомпилирован.
Неверная строка 29, замените
int findString(char matrix[ROW][COLUNM],char string[15],int computeLength(string[15])){
by
int findString(char matrix[ROW][COLUNM], char string[15])
Обратите внимание, что размер 15 бесполезен, вы можете использовать char string [] или char * string для параметра 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 символов.
Можно прочитать в string , которая длиннее COLUMN more 2, и проверить длину входной строки. Таким образом, ваш для может быть заменен на:
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 l oop
scanf("%s",&string[50]);
недопустимо, так как результат будет помещен после string , индекса должно быть 0, и на самом деле вы можете просто дать string .
Как и раньше, если на входе более 49 символов scanf будет записывать из string , то же самое можно сделать
scanf("%49s", string);
Если вы хотите разрешить поиск строки из 50 символов без подсчета конечного нулевого символа, вы должны задать размер 51 и заменить 49 на 50.
Из печати и чтения , пока l oop ничего не делает, очень вероятно, что вы хотите вызвать 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 интерес этой строки неясен:
* 110 9 *
В printPuzzle вы пропустили ввод новой строки после печати PUZZLE , вы можете просто заменить printf на путы . Обратите внимание, что бесполезно просить printf искать% et c, пока вы знаете, что его нет.
В findString
Первая проблема заключается в том, что вы возвращаете значение только в том случае, если count == computeLength (string) имеет значение true, вам нужно всегда возвращать значение. Как правило, вы можете вернуть -1, если строка отсутствует в загадке, поэтому
return (count==computeLength(string)) ? i : -1;
, но это тоже неправильно, и по двум причинам:
- при прохождении теста i всегда значение 180, а не позиция, в которой была строка
- , это не потому, что count == computeLength (string) верно, что строка была найдена из-за как вы привыкли увеличивать считать и следующую ошибку:
Вы неправильно ищете строку в головоломке, потому что ваш первый l oop на i идет через строку ( string [i] ), и худший получит доступ к 180 символам, в то время как его длина составляет всего 49 (без последнего нулевого символа). Вы также не останавливаетесь, чтобы искать, даже если вы найдете строку. И в вашем алгоритме вы забудете, что символы строки должны быть последовательно расположены в матрице, вы каждый раз, когда вы (ошибочно) находите символ строки в любом месте матрицы, которую вы увеличиваете count .
Только учитывая, что вы ищете строку по горизонтали слева направо:
l oop в string должно быть более встроенным l oop, чтобы проверить, что его символы последовательны в матрице.
У вас есть один l oop в строке и один в столбце, это бесполезно и просто усложняет задачу. Поскольку matrix является массивом, символ в matrix [r] [COLUMN] является символом в matrix [r + 1] [0] , это означает, что вы может go до матрица как строка из 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' } };
Давайте начнем с поиска с слева направо , это похоже на функцию classi c 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;
}
Компиляция и выполнение с этим основным:
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, если для 2 и 4, 13000, если для 13 и 0, строка не найдена в в последнем случае это нормально
Поиск с справа налево .
Первый очевидный способ - повторно использовать предыдущую функцию и повернуть строку перед ее поиском. , В случае, если в результате найдена строка, позиция первого и последнего символов также меняется на противоположную.
Другой способ - выполнить итерацию по строке для поиска в обратном порядке, давайте выберем этот способ.
Поиск по справа налево или слева направо .
Для указания направления добавляется параметр 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;
}
Компиляция и выполнение с этим основным:
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 . Конечно, это не тот случай, когда мы находимся на последней строке, в этом случае мы go возвращаемся на первую строку и перемещаемся вправо, за исключением последнего символа матрицы, где мы должны выполнить откат к первому символу. , Определение может быть:
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;
}
Компиляция и выполнение с этим основным:
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, делать сверху вниз шаг - КОЛОННА, а правильное - 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 $