Как проверить, что конкретная строка в одном массиве находится в другом массиве

Question

У меня есть массив, называемый головоломкой, который состоит из слов/букв/случайных строк, и я хочу проверить, имеет ли он какие-либо из тех же строк в другом массиве, называемом словарем (строки в словаре перечислены в алфавитном порядке)

Итак, я считаю, что моя проблема - это двоичный поиск в моей программе, я не совсем уверен, как обойти это с помощью строк. Я пытался использовать некоторые strcmp(), но я не думаю, что это путь?

Когда программа запускается, она не получает выход. что нет совпадений, но есть.

вот мой двоичная функция поиска:

int binsearch(char **dictionary, char *puzzle) { 
    int start = 1; //excluded first string of dictionary array bC# 
    int end = listlength; 
    while (start < end) { 
     int mid = (start + end)/2; 
     int temp = strcmp(dictionary[mid], puzzle); 
     if (temp < 0) { 
      start = mid + 1; //it is in upper half 
     } else 
     if (temp > 0) { //check lower half 
      end = mid; 
     } else 
      return 1; //found a match hopefully 
    } 
    return 0; 
} 

и весь мой код здесь, если возможно, то, что вам нужно, чтобы увидеть

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define listlength 149256 
#define maxWordLen 19 

char **getWords(int rows, int cols); 
void freeArray(char **array, int rows); 
char **makeGridArray(int rows, int cols); 
int binsearch(char **dictionary, char *puzzle); 
void wordSearch(char **dictionary, char **puzzle, int row, int col); 
const int DX_SIZE = 8; 
const int DX[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; 
const int DY[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; 

int main() { 

    //read in dictionary 
    int i, j, x = 0, numCases, gridRow, gridCol; 
    char **words = getWords(listlength, maxWordLen); 

    //Get number of cases. 
    printf("enter number of cases:\n"); 
    scanf("%d", &numCases); 

    //process each case. 
    while (x < numCases) { 
     scanf("%d%d", &gridRow, &gridCol); 

     //make word search grid 
     char **grid = makeGridArray(gridRow + 1, gridCol); 

     /* for testing if grid is storing properly 
     for (i = 0; i < gridRow + 1; i++) { 
      printf("%s\n", grid[i]); 
     } 
     */ 

     printf("Words Found Grid #%d:\n", x + 1); 
     wordSearch(words, grid, gridRow + 1, gridCol); 
     x++; 
     freeArray(grid, gridRow + 1); 
    } 
    freeArray(words, listlength); 
} 

char **getWords(int rows, int cols) { 
    int i; 

    //allocate top level of pointers. 
    char **words = malloc(sizeof(char*) * rows); 

    //allocate each individual array 
    for (i = 0; i < rows; i++) { 
     words[i] = malloc(sizeof(char) * cols + 1); 
    } 

    //read dictionary.txt 
    FILE *dictionary = fopen("dictionary.txt", "r"); 
    for (i = 0; i < rows; i++) { 
     fgets(words[i], cols + 1,dictionary); 
    } 
    fclose(dictionary); 
    return words; 
} 

char **makeGridArray(int rows, int cols) { 
    //allocate top level of pointers. 
    char **grid = malloc(sizeof(char*) * rows); 
    int i, j; 

    //allocate each individual array 
    for (i = 0; i < rows; i++) { 
     grid[i] = malloc(sizeof(char) * cols + 1); 
    } 
    //read in user input grid 
    for (i = 0; i < rows; i++) { 
     gets(grid[i]); 
    } 
    return grid; 
} 

int binsearch(char **dictionary, char *puzzle) { 
    int start = 1; //excluded first string of dictionary array bC# 
    int end = listlength; 
    while (start < end) { 
     int mid = (start + end)/2; 
     int temp = strcmp(dictionary[mid], puzzle); 
     if (temp < 0) { 
      start = mid + 1; //it is in upper half 
     } else 
     if (temp > 0) { //check lower half 
      end = mid; 
     } else 
      return 1; //found a match hopefully 
    } 
    return 0; 
} 

void wordSearch(char **dictionary, char **puzzle, int row, int col) { 
    int i, X, Y, dir; 
    char wordsfound[19] = { '\0' }; 
    for (X = 0; X < row + 1; X++) { 
     for (Y = 0; Y < col; Y++) { 
      for (dir = 0; dir < DX_SIZE; dir++) //check every direction 
       for (i = 0; i < 19; i++) { 
        //will continue in direction DX,DY starting at x,y 
        int nextX = X + DX[dir] * i; 
        int nextY = Y + DY[dir] * i; 
        if (nextX < 0 || nextX >= row) break; //keep in bounds 
        if (nextY < 0 || nextY >= col) break; 
        //store the string of letters to check 
        wordsfound[i] = (puzzle[nextX][nextY]); 
        if (i > 3) { //minimum word is 4 
         wordsfound[i + 1] = '\0'; 
         //if the string of letters is actually a word, print 
         int bin = binsearch(dictionary, wordsfound); 
         if (bin) { 
          printf("%s\n", wordsfound); 
         } 
        } 
       } 
     } 
    } 
    return; 
} 

void freeArray(char **array, int rows) { 
    //free arrays 
    int i; 
    for (i = 0; i < rows; i++) { 
     free(array[i]); 
    } 
    free(array); 
} 

Answer 1

Проблема заключается в функции getwords(): вы читаете слова из словаря с fgets() но забыл удалить trailing \n. Все слова в словаре имеют завершающий \n, поэтому ни один из них не соответствует вашим поисковым запросам.

Вот исправленный вариант:

char **getWords(int rows, int cols) { 
    char line[256]; 
    int i; 

    //allocate top level of pointers. 
    char **words = malloc(sizeof(char*) * rows); 

    //read dictionary.txt 
    FILE *dictionary = fopen("dictionary.txt", "r"); 
    for (i = 0; i < rows; i++) { 
     if (!fgets(line, sizeof line, dictionary)) 
      line[0] = '\0'; 
     line[strcspn(line, "\n")] = '\0'; 
     words[i] = strdup(line); 
    } 
    fclose(dictionary); 
    return words; 
} 

Обратите внимание, что было бы лучше не полагаться на известном волшебном listlength. Вы также можете игнорировать комментарии и пустые строки при чтении словаря.