首页 / 技术问答 / C++问答列表 / 问答详情

C++ cs50拼写器分配中的无限循环

我正在处理CS50拼写任务，一旦我完成了load函数的调试，程序就在无限循环中运行，不做任何事情或打印任何东西.

// Implements a dictionary's functionality

#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 26 * LENGTH;

// Hash table
node *table[N];

unsigned int word_count;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    node *tmp = table[hash(word)];
    while (tmp != NULL)
    {
        if (strcasecmp(tmp->word, word) == 0)
        {
            return true;
        }
        tmp = tmp->next;
    }
    return false;
}

// Hashes word to a number
int hash(const char *word)
{
    // TODO: Improve this hash function
    int total = 0;
    for (int i = 0; i < strlen(word); i++)
    {
        if (isalpha(word[i]))
        {
            total += (int)(tolower(word[i]) - 'a');
        }
    }
    return total;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }
    char *word = malloc(LENGTH + 1);
    if (word == NULL)
    {
        return false;
    }
    while (fscanf(dict, "%s", word) == 1)
    {
        node *new = malloc(sizeof *new);
        if (new == NULL)
        {
            return false;
        }
        strcpy(new->word, word);
        if (table[hash(word)] == NULL)
        {
            table[hash(word)] = new;
        }
        else
        {
            new->next = table[hash(word)];
            table[hash(word)]->next = new;
        }
        word_count++;
    }
    free(word);
    free(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    if (word_count)
    {
        return word_count;
    }
    else
    {
        return 0;
    }
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node *tmp;
    node *cursor;
    for (int i = 0; i < LENGTH * 25; i++)
    {
        tmp = table[i]->next;
        cursor = table[i]->next;
        while (tmp != NULL)
        {
            tmp = tmp->next;
            free(cursor);
            cursor = tmp;
        }
    }
    return true;
}

我在这个问题上有过许多错误，一旦我修复了负载，另一个函数中就出现了无限循环错误.我不确定如何准确定位它--有人能帮上忙吗？

无限循环打印出"拼写错误的单词"，然后再往下几行，它就会出现出现在控制台中的白色光标.我知道程序还在运行，因为没有出现$号.该程序不等待任何类型的输入，因为该项目不包括使用CS50 get_xxx函数或scanf的任何理由.

这些只是帮助器函数(分配只是为了实现它们)，其余的是为我编写的，放在一个单独的文件中:

// Implements a spell-checker

#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>

#include "dictionary.h"

// Undefine any definitions
#undef calculate
#undef getrusage

// Default dictionary
#define DICTIONARY "dictionaries/large"

// Prototype
double calculate(const struct rusage *b, const struct rusage *a);

int main(int argc, char *argv[])
{
    // Check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: ./speller [DICTIONARY] text\n");
        return 1;
    }
    // Structures for timing data
    struct rusage before, after;

    // Benchmarks
    double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;

    // Determine dictionary to use
    char *dictionary = (argc == 3) ? argv[1] : DICTIONARY;
    // Load dictionary
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // Exit if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // Calculate time to load dictionary
    time_load = calculate(&before, &after);

    // Try to open text
    char *text = (argc == 3) ? argv[2] : argv[1];
    FILE *file = fopen(text, "r");
    if (file == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // Prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // Prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH + 1];

    // Spell-check each word in text
    char c;
    while (fread(&c, sizeof(char), 1, file))
    {
        // Allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // Append character to word
            word[index] = c;
            index++;

            // Ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // Consume remainder of alphabetical string
                while (fread(&c, sizeof(char), 1, file) && isalpha(c));

                // Prepare for new word
                index = 0;
            }
        }

        // Ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // Consume remainder of alphanumeric string
            while (fread(&c, sizeof(char), 1, file) && isalnum(c));

            // Prepare for new word
            index = 0;
        }

        // We must have found a whole word
        else if (index > 0)
        {
            // Terminate current word
            word[index] = '\0';

            // Update counter
            words++;

            // Check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // Update benchmark
            time_check += calculate(&before, &after);

            // Print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // Prepare for next word
            index = 0;
        }
    }

    // Check whether there was an error
    if (ferror(file))
    {
        fclose(file);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // Close text
    fclose(file);

    // Determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // Calculate time to determine dictionary's size
    time_size = calculate(&before, &after);

    // Unload dictionary
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // Abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // Calculate time to unload dictionary
    time_unload = calculate(&before, &after);

    // Report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", time_load);
    printf("TIME IN check:        %.2f\n", time_check);
    printf("TIME IN size:         %.2f\n", time_size);
    printf("TIME IN unload:       %.2f\n", time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n",
           time_load + time_check + time_size + time_unload);

    // Success
    return 0;
}

// Returns number of seconds between b and a
double calculate(const struct rusage *b, const struct rusage *a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                  (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                 ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                  (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}

这个文件不是我写的，我也不完全理解它(我不应该理解它)，但它实际上是函数被调用的地方.

编辑:非常感谢Chqrlie对我的帮助！以下是我的更新代码:

#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"



// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Hash table
node *table[N];

unsigned int word_count;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    node *tmp = table[hash(word)];
    while (tmp != NULL)
    {
        if (strcasecmp(tmp -> word, word) == 0)
        {
            return true;
        }
        tmp = tmp -> next;
    }
    return false;
}

// Hashes word to a number
int hash(const char *word)
{
    // TODO: Improve this hash function
    int total = 0;
    unsigned char c;
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        c = word[i];
        if (isalpha(c))
        {
            total += (int) (tolower(c) - 'a');
        }
    }
    if (total >= 0 && total <= N - 1)
    {
        return total;
    }
    else
    {
        return N - 1;
    }
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }
    char *word = malloc(LENGTH + 1);
    if (word == NULL)
    {
        return false;
    }
    while (fscanf(dict, "%" STR(LENGTH) "s", word) == 1)
    {
        node *new = malloc(sizeof *new);
        if (new == NULL)
        {
            return false;
        }
        strcpy(new->word, word);
        if (table[hash(word)] == NULL)
        {
            table[hash(word)] = new;
            new->next = NULL;
        }
        else
        {
            new -> next = table[hash(word)];
            table[hash(word)] = new;
        }
        word_count++;
    }
    free(word);
    free(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    return word_count;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void) {
    for (int i = 0; i < N; i++) {
        while (table[i]) {
            node *tmp = table[i];
            table[i] = tmp->next;
            free(tmp);
        }
    }
    return true;
}

我只遇到了一个错误，我真的不知道这是怎么可能的.我的程序打印出它应该打印出来的所有东西(拼写错误的单词、词典中的单词等)，但在最后，它再次运行无限循环-没有出现$符号，白色光标永远留在那里.这尤其令人困惑，因为在完成所有这些printf语句之后，程序应该立即返回0.有人知道这会在哪里发生吗？

(注意-拼写程序文件与以前相同，我认为它一定是发生错误的地方.)

推荐答案

您的代码中存在多个问题:

  • 如果将N定义为const unsigned int N = 26 * LENGTH;，则不能定义长度为N的全局数组:node *table[N];不符合C标准.您应该这样写:

    • #define N (26 * LENGTH)或
    • 枚举{N=26*长度}；`

  • 函数hash应该返回值unsigned int，并且您应该确保返回值在0到N-1的范围内.

  • 在char是带符号类型的平台上，没有为所有char值定义函数/宏isalpha和tolower.您应该将char参数强制转换为(unsigned char)，或者使用unsigned char变量来避免未定义的行为:

    // Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    unsigned int total = 0;
    for (int i = 0; word[i]; i++)
    {
        unsigned char ch = word[i];
        if (isalpha(ch))
        {
            total += tolower(ch) - 'a';
        }
    }
    return total % N;
}

  • 如果输入文件的单词长度超过LENGTH，则fscanf(dict, "%s", word)将导致缓冲区溢出.您应该通过以下方式在空终止符之前传递要存储到目标数组中的最大字符数:

    #define STR(x)  xSTR(x)
#define xSTR(x) #x

while (fscanf(dict, "%" STR(LENGTH) "s", word) == 1)

  • table[hash(word)]->next = new;会导致无限循环，因为new->next刚才被设置为table[hash(word)].因此，如果哈希表中存在冲突，则在table[hash(word)]处将有一个2元素循环列表.相反，你应该写table[hash(word)] = new.在哈希表中插入new可以在没有测试的情况下完成，并且哈希码应该只计算一次:

        strcpy(new->word, word);
    unsigned int h = hash(word);
    new->next = table[h];
    table[h] = new;

  • size函数应简化为:

    unsigned int size(void) {
    return word_count;
}

  • unload函数也是假的:您应该迭代到i < N，并且应该释放所有元素，从table[i]而不是table[i]->next开始:

    // Unloads dictionary from memory, returning true if successful, else false
bool unload(void) {
    for (int i = 0; i < N; i++) {
        while (table[i]) {
            node *tmp = table[i];
            table[i] = tmp->next;
            free(tmp);
        }
    }
    return true;
}

I didn't write this other file, and I don't completely understand it (I'm not supposed to) but it's where the functions are actually called.个

祝贺你!main函数的风格并不完美，不推荐使用循环char c; while (fread(&c, sizeof(char), 1, file))而不是classic 的int c; while ((c = getc(file)) != EOF)，特别是当c要传递给<ctype.h>中定义的字符类函数时.另请注意，如果文本文件后面没有换行符或另一个单词分隔符，则不会判断文本文件的最后一个单词.

C++相关问答推荐

有什么方法可以检测SunOS上的SparcWorks吗？

带双指针的2D数组

想了解 struct 指针和空指针转换

__VA_OPT__(，)是否可以检测后面没有任何内容的尾随逗号？

为什么在函数内部分配内存空间时需要添加符号？

#If指令中未定义宏？

在C语言中，是否可以使枚举数向后计数？

实现简单字典时C语言中的段错误

&；(str[i])和(&；str)[i]有什么区别？

致命错误：ASM/rwan ce.h：没有这样的文件或目录.符号链接还不够

预处理器宏扩展(ISO/IEC 9899：1999(E)§；6.10.3.5示例3)

初始成员、公共初始序列、匿名联合和严格别名如何在C中交互？

Makefile无法将代码刷新到ATmega328p

'；malloc()：损坏的顶部大小'；分配超过20万整数后

GCC认为这是一个VLA是对的吗？

与指针的原始C数组或C++向量<；向量<；双>>；

10 个字节对于这个 C 程序返回后跳行的能力有什么意义

GDB 用内容初始化数组

为什么需要struct in_addr

在 C 中的 scanf() 格式说明符中使用宏获取字符串长度

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630