c - 二进制搜索单词词典

Question

在此代码中：
我读取文件~/usr/share/dict/word的内容并将其存储在数组中。
然后开始对此数组执行二进制搜索算法，但问题是在将数组传递给第62行的二进制搜索函数并尝试将其与binary_search(string* dictionary, string key)方法中的键进行比较之后。
我发现它在比较key和这个未知字符串"��tudes"是出于某种原因，我不知道。
我确信数组包含正确的数据。
代码：

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

#define MAX 99171

// Prototype //
int binary_search(string*, string);

int main(int argc, string argv[])
{
    // Attributes // 
    string dictionary[MAX];
    FILE* dictionaryFile = fopen("words", "r");
    char output[256];
    string key = argv[1];

    // Check if their is a problem while reading the file //
    if (dictionaryFile == NULL)
    {
        // If everything got fouled up then close the file // 
        fclose(dictionaryFile);
        printf("couldn't read the file!!!\n");
        return 1;
    }

    // storing the information into an array to make it easy to read //
    for(int i = 0; i < MAX; i++)
    { 
        fgets(output, sizeof(output), dictionaryFile); 
        dictionary[i] = output;
    }

    // Binary Search a word //
    if(binary_search(dictionary, key) == 1)
    {
        printf("word was found !!!\n");
    }
    else if(binary_search == 0)
    {
        printf("word was not found !!!\n");
    }

    // If Everything goes just fine close the file //
    fclose(dictionaryFile);
    return 0;
}


// implementing prototype //

/**
    @arag dictionary 
        a string of english words 

    @arg key 
        a key we looking for

    @return 
        0 if didn't find the key and 1 otherwise
*/
int binary_search(string* dictionary, string key)
{
    // pointer to the start and the end of the array //
    int start = 0;
    int end = MAX - 1;
    int mid;

    // while end is greater than the start //
    while (end > start)
    {
        // Get The Middle Element //
        mid = (start + end) / 2;
        printf("%s\n", dictionary[mid]);

        // Check if the middle elemenet //
        if (strcmp(key, dictionary[mid]) == 0)
        {
            return 1;
        }

        // Check the left half //
        else if(strcmp(key, dictionary[mid]) < 0)
        {
            end = mid - 1;
        }

        // Check the right half //
        else if (strcmp(key, dictionary[mid]) > 0)
        {
            start = mid + 1;
        }
    }
    // didn't find the key //
    return 0;

}

注意：cs50.h库是由哈佛大学为像我这样的初学者制作的，我正在我的代码中使用它，这是一个指向它reference的链接。

Answer 1

cs50.h库是哈佛大学为初学者设计的一个训练轮。
如果是这样的话，这些训练轮是颠倒安装的，不要接触地面。我看不出你的联系，但我想

typedef char *string;

是cs50套件的一部分。但是C语言中没有字符串；表达式被松散地用于表示以空字符'\0'结尾的字符数组。
上面对string的定义使您相信string是一种正确的类型，它的内存是自动处理的。不是的。在你的程序中有一个字符串的位置，即数组

char output[256];

字典中的“字符串”只是指针；它们应该指向现有的字符数组或是NULL。通过分配

dictionary[i] = output;

将字典中的所有字符串设置为等于临时缓冲区output。该缓冲区在您所读的每一行中都被覆盖，并且只包含您所读的最后一行，可能"zulu"。
你可以在读完字典后把它打印出来来确认这一点。你应该在一个单独的循环中打印它，而不是在你读它的同一个循环中看到效果。
可以通过将指针数组声明为char数组来解决此问题：

char dictionary[MAX][LEN];

其中LEN是单词的最大长度，比如24。（这里的问题可能是分配的内存，MAX * LEN字节可能不适合堆栈。在这种情况下，必须使用malloc在堆上分配内存。我不想在这里打开那个虫子罐头。如果你马上发现了分词冲突，试着减少MAX，代价是只阅读字典的一部分。）
读单词时，必须抄写以下内容：

fgets(output, sizeof(output), dictionaryFile); 
strncpy(dictionary[i], output, sizeof(dictionary[i]);

或者，更好的是，直接把下一个单词读进字典：

fgets(dictionary[i], sizeof(dictionary[i]), dictionaryFile); 

不幸的是，fgets在结尾保留了换行符，因此它读取的是"word\n"而不是"word"。必须删除换行符，否则字符串将与输入不匹配，该输入是通过argv从命令行发出的，它没有尾随的换行符。
有几种方法可以摆脱不受欢迎的热线。一个简单的方法是用换行符作为分隔符标记字符串：

strtok(dictionary[i], "\n");

另一个问题是，对于dictionary的新定义，binary_search的签名是错误的。你不再有一个指向char的指针数组，你有一个由24个（或者说，一个固定的数字）char组成的数组。更改为：

int binary_search(char dictionary[][LEN], const char *key)

在C语言中，如果有数组数组（甚至是数组数组），那么除了最上面的维度之外，所有的维度都必须是已知的，这样编译器就可以布局内存。
还有其他（相当小的）问题：
如果无法打开文件，则尝试将其fclose。当文件为“cc>”时，没有打开的文件要关闭，只需退出即可。
您应该强制至少有一个参数，否则您可能会循环一个空键，这将导致在您尝试比较它时出现未定义的行为（即很可能发生崩溃）。
当你读单词时，不要依赖硬编码的单词计数。你不知道档案里有多少字。检查返回值NULL；当文件用完时返回fgets。NULL是估计单词数量的好方法，但是您应该将实际读取的单词数量保持在一个变量中。确保访问的字数不超过已读字数，并确保写入的字数不超过已分配的内存，即读取的字数不超过MAX字数。
如果没有硬编码的单词计数，则应将该计数作为MAX函数的参数。
在“not found”beanch中，您的测试是binary_search。首先，else if(binary_search == 0)aleady意味着二进制搜索没有返回1（这是else所指的条件），二进制搜索只能返回0和1，因此不需要其他条件。其次，else只是函数的地址，而不是结果；上面所写的考虑总是正确的。
二进制搜索函数中的binary_search调用也是如此：您要进行三次比较。您检查的结果是互斥的，因此最后一个条件可以是strcmp。（因为else每次都要进行逐个字符的比较，所以每个单词只需调用strcmp一次并存储结果可能是值得的。）
strcmp头中的string数据类型是为了提供一种简单的方法来读取字符串，而无需关心内存。一旦开始创建更复杂的（也称为真实的）数据结构，最好使用cs50数组和指针。无论如何，这是没有办法的，你可以看到每一个数据是什么。
很抱歉，我的答案看起来像是一张错误清单。C的字符串处理对于初学者来说不是很容易的，特别是如果你已经有高级语言的经验的话。好的一面是，当你理解C字符串时，你已经知道了很多关于C中的事情是如何做的。