如何检查一个数组中的特定字符串是否在另一个数组中

Question

我有一个名为 puzzle 的数组，它由 words/letters/random 个字符串组成，我想检查它是否在另一个名为 dictionary 的数组中有任何相同的字符串（字典中的字符串按字母顺序列出）

所以我认为我的问题是程序中的二进制搜索，我不确定如何使用字符串来解决它。我尝试使用一些 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] = { '[=11=]' };
    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] = '[=11=]';
                        //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() 的单词，但忘记删除结尾的 \n。字典中的所有单词都有尾随 \n，因此其中 none 个匹配您的搜索。

这是更正后的版本：

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] = '[=10=]';
        line[strcspn(line, "\n")] = '[=10=]';
        words[i] = strdup(line);
    }
    fclose(dictionary);
    return words;
}

请注意，最好不要依赖已知的神奇列表长度。您也可以在阅读字典时忽略注释和空行。

如何检查一个数组中的特定字符串是否在另一个数组中

How to check if a particular string in one array is in another array

c

binary-search