I completed the week 5 speller cs50x today. The code was not giving the correct output when I used recursion, but normally, it worked

huangapple
go评论74阅读模式
英文:

I completed the week 5 speller cs50x today. The code was not giving the correct output when I used recursion, but normally, it worked

问题

以下是您提供的代码部分的翻译：

这是问题集的链接（拼写器）[speller](https://cs50.harvard.edu/x/2023/psets/5/speller/)
我发现递归条件是正确的。问题出在检查函数中，根据输出来看。所以当我改变它时，代码就起作用了。
以下是dictionary.c中的代码（第一个带递归，第二个不带递归的）

### 带递归
- 在这里，我定义了两个自己的函数，以便递归遍历列表...
```c
// 实现字典的功能

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
// 在哈希表中表示一个节点
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

bool search(node *s, const char *wod);
void frr(node *ptr);

int sije = 0;

// TODO：选择哈希表中的桶数
// 答案-我会选择一个2D数组，它是[26][LENGTH + 1]
const unsigned int N = 26;

// 2D哈希表
node *table[N][LENGTH];

// 如果单词在字典中，返回true；否则返回false
bool check(const char *word)
{
    // 查找单词的哈希值
    int h = hash(word);
    // 查找单词的长度
    int len = strlen(word) - 1;
    // 为了迭代而创建另一个指针
    node *tmp = table[h][len];
    return search(tmp, word);
}

bool search(node *s, const char *wod)
{
    if (s == NULL)
    {
        return false;
    }

    if (!strcasecmp(s->word, wod))
    {
        return true;
    }
    else
    {
        s = s->next;
        bool c = search(s, wod);
    }
    return false;
}

// 将单词哈希为数字
unsigned int hash(const char *word)
{
    // TODO：改进这个哈希函数
    return toupper(word[0]) - 'A';
}

// 加载字典到内存中，成功返回true，否则返回false
bool load(const char *dictionary)
{
    // 使哈希表不包含垃圾值
    for (int i = 0; i < 26; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            table[i][j] = NULL;
        }
    }

    // TODO
    // 打开字典文件
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }
    // 读取字符数组中的单词
    char n[LENGTH + 1];
    while (fscanf(dict, "%s", n) != EOF)
    {
        // 调用哈希函数并获取哈希码
        int h = hash(n);
        // 这将返回0到25之间的某个值
        int len = strlen(n) - 1;
        // 这将有单词的长度

        // 让我们加载到哈希表中
        // 创建一个新节点
        node *no = malloc(sizeof(node));
        if (no == NULL)
        {
            return false;
        }
        // 将单词从n复制到no
        strcpy(no->word, n);
        // 在节点内部声明指针为空
        no->next = NULL;
        // 插入节点到哈希表中
        if (table[h][len] == NULL)
        {
            table[h][len] = no;
        }
        // 如果位置已经被占用
        else
        {
            no->next = table[h][len];
            table[h][len] = no;
        }
        sije += 1;
    }
    return true;
}

// 如果已加载，返回字典中的单词数；否则返回0
unsigned int size(void)
{
    // TODO
    return sije;
}

// 从内存中卸载字典，成功返回true，否则返回false
bool unload(void)
{
    for (int i = 0; i < 26; i++)
    {
        for (int j = 0; j < LENGTH; j++)
        {
            // 如果该索引处的表不为空，
            // 这意味着该表的该索引处有一个链表
            if (table[i][j] != NULL)
            {
                frr(table[i][j]);
            }
        }
    }
    return true;
}

void frr(node *ptr)
{
    if (ptr == NULL)
    {
        return;
    }
    frr(ptr->next);
    free(ptr);
}

没有递归（有效的那个）

// 实现字典的功能

#include <ctype.h>
#include <stdbool.h>
#include <string.h>
#include "dictionary.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
// 在哈希表中表示一个节点
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

void frr(node *ptr);

int sije = 0;

// TODO：选择哈希表中的桶数
// 答案-我会选择一个2D数组，它是[26][LENGTH]
const unsigned int N = 26;

// 2D哈希表
node *table[N][LENGTH];

// 如果单词在字典中，返回true；否则返回false
bool check(const char *word)
{
    // 查找单词的哈希值
    int h = hash(word);
    // 查找单词的长度
    int len = strlen(word) - 1;
    // 为了迭代而创建另一个指针
    node *tmp = table[h][len];
    while (true)
    {
        if (tmp == NULL)
        {
            return false;
        }
        if (!strcasecmp(tmp->word, word))
        {
            return true;
        }
        tmp = tmp->next;
    }
}

// 将单词哈希为数字
unsigned int hash(const char *word)
{
    // TODO：改进这个哈希函数
    return toupper(word[0]) - 'A';
}

// 加

<details>
<summary>英文:</summary>

Here is the link to the question (problem set)[speller](https://cs50.harvard.edu/x/2023/psets/5/speller/)
I find the recursion conditions correct. the problem is in the check function, according to the outputs. So when I changed it, the code worked.
Here are the codes from dictionary.c (first one with recursion and the second one without it)
### with recursion  
- here I defined two functions of my own in order to recursively go through the lists...
```c
// Implements a dictionary&#39;s functionality

#include &lt;ctype.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;string.h&gt;
#include &quot;dictionary.h&quot;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;strings.h&gt;
// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

bool search(node *s, const char *wod);
void frr(node *ptr);

int sije = 0;

// TODO: Choose number of buckets in hash table
// ans - i would choose a 2d array which is [26][LENGTH + 1]
const unsigned int N = 26;

// 2d Hash table
node *table[N][LENGTH];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // finding the hash for the word
    int h = hash(word);
    // finding the length for the word
    int len = strlen(word) - 1;
    // creating another pointer for the sake of iterating
    node *tmp = table[h][len];
    return search(tmp, word);
}

bool search(node *s, const char *wod)
{
    if (s == NULL)
    {
        return false;
    }

    if (!strcasecmp(s -&gt; word, wod))
    {
        return true;
    }
    else
    {
        s = s -&gt; next;
        bool c = search(s, wod);
    }
    return false;
}





// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - &#39;A&#39;;
}







// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // make the hash table free of garbage values
    for (int i = 0; i &lt; 26; i++)
    {
        for (int j = 0; j &lt; 10; j++)
        {
            table[i][j] = NULL;
        }
    }



    // TODO
    // open the dictionary file
    FILE *dict = fopen(dictionary, &quot;r&quot;);
    if (dict == NULL)
    {
        return false;
    }
    // read the word inside a char array
    char n[LENGTH + 1];
    while (fscanf(dict, &quot;%s&quot;, n) != EOF)
    {
        // call the hash function and get the hach code
        int h = hash(n);
        // this will return something from 0 till 25
        int len = strlen(n) - 1;
        // this will have the length of the word

        // let&#39;s load it to the hach table
        // create a new node
        node *no = malloc(sizeof(node));
        if (no == NULL)
        {
            return false;
        }
        // copy the word from n to no
        strcpy(no -&gt; word, n);
        // declare the pointer inside the node to null
        no -&gt; next = NULL;
        // insert the node inside the hach table
        if (table[h][len] == NULL)
        {
            table[h][len] = no;
        }
        // else if the spot is populated
        else
        {
            no -&gt; next = table[h][len];
            table[h][len] = no;
        }
        sije += 1;

    }
    return true;

}





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





// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i &lt; 26; i++)
    {
        for (int j = 0; j &lt; LENGTH; j++)
        {
            // if table at that inces in not null,
            // that means that there is a linked list at that index of the table
            if (table[i][j] != NULL)
            {
                frr(table[i][j]);
            }
        }
    }
    return true;
}



void frr(node *ptr)
{
    if (ptr == NULL)
    {
        return;
    }
    frr(ptr -&gt; next);
    free(ptr);
}

without recursion (the one which worked)

// Implements a dictionary&#39;s functionality

#include &lt;ctype.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;string.h&gt;
#include &quot;dictionary.h&quot;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;strings.h&gt;
// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

void frr(node *ptr);

int sije = 0;

// TODO: Choose number of buckets in hash table
// ans - i would choose a 2d array which is [26][LENGTH]
const unsigned int N = 26;

// 2d Hash table
node *table[N][LENGTH];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // finding the hash of the code
    int h = hash(word);
    // finding the length of the code
    int len = strlen(word) - 1;
    // creating another pointer for the sake of iterating
    node *tmp = table[h][len];
    while (true)
    {
        if (tmp == NULL)
        {
            return false;
        }
        if (!strcasecmp(tmp -&gt; word, word))
        {
            return true;
        }
        tmp = tmp -&gt; next;
    }

}






// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - &#39;A&#39;;
}







// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // make the hash table free of garbage values
    for (int i = 0; i &lt; 26; i++)
    {
        for (int j = 0; j &lt; 10; j++)
        {
            table[i][j] = NULL;
        }
    }



    // TODO
    // open the dictionary file
    FILE *dict = fopen(dictionary, &quot;r&quot;);
    if (dict == NULL)
    {
        return false;
    }
    // read the word inside a char array
    char n[LENGTH + 1];
    while (fscanf(dict, &quot;%s&quot;, n) != EOF)
    {
        // call the hash function and get the hach code
        int h = hash(n);
        // this will return something from 0 till 25
        int len = strlen(n) - 1;
        // this will have the length of the word
        // let&#39;s load it to the hach table
        // create a new node
        node *no = malloc(sizeof(node));
        if (no == NULL)
        {
            return false;
        }
        // copy the word from n to no
        strcpy(no -&gt; word, n);
        // declare the pointer inside the node to null
        no -&gt; next = NULL;
        // insert the node inside the hach table
        if (table[h][len] == NULL)
        {
            table[h][len] = no;
        }
        // else if the spot is populated
        else
        {
            no -&gt; next = table[h][len];
            table[h][len] = no;
        }
        sije += 1;

    }
    fclose(dict);
    return true;

}





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





// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i &lt; 26; i++)
    {
        for (int j = 0; j &lt; LENGTH; j++)
        {
            // if table at that inces in not null,
            // that means that there is a linked list at that index of the table
            if (table[i][j] != NULL)
            {
                frr(table[i][j]);
            }
        }
    }
    return true;
}



void frr(node *ptr)
{
    if (ptr == NULL)
    {
        return;
    }
    frr(ptr -&gt; next);
    free(ptr);
}

What could be the reason. All others are correct, only the checking part ...

答案1

得分: 1

I've translated the provided text:

"我认为我应该进一步调查这个问题，因为在我看来，在“else”块中添加一个返回语句应该可以解决这个问题。可能是我在注释中没有明确地说明答案，所以我继续获取了课程代码，使用非递归检查函数实现了您的代码解决方案，在一组选择的文本文件上执行了一些测试，然后尝试了带有递归搜索函数的代码以及我已经注意到的代码调整。

在“aca.txt”文件上执行非递归解决方案时，以下是要用作基准的终端输出。

拼写错误的单词数：17062
字典中的单词数：143091
文本中的单词数：376904
载入时间：0.08
检查时间：3.61
大小时间：0.00
卸载时间：0.01
总时间：3.70

然后，我修改了程序“dictionary.c”，将检查/搜索函数调用与其原始状态的代码一起包括在内。

// 如果单词在字典中，则返回true，否则返回false
bool check(const char *word)
{
// 找到单词的哈希值
int h = hash(word);
// 找到单词的长度
int len = strlen(word) - 1;
// 为了迭代而创建另一个指针
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -> word, wod))
{
return true;
}
else
{
s = s -> next;
bool c = search(s, wod);
}
return false;
}

执行此版本的代码在相同文件上运行时会产生一些多余的拼写错误值。

拼写错误的单词数：359710
字典中的单词数：143091
文本中的单词数：376904
载入时间：0.07
检查时间：4.85
大小时间：0.00
卸载时间：0.01
总时间：4.93

我猜这可能是您所经历的行为类型。

然后，我修改了搜索函数，在“else”块中提供了一个返回语句，就像我在注释中指出的那样。以下是重构后的代码。

// 如果单词在字典中，则返回true，否则返回false
bool check(const char *word)
{
// 找到单词的哈希值
int h = hash(word);
// 找到单词的长度
int len = strlen(word) - 1;
// 为了迭代而创建另一个指针
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -> word, wod))
{
return true;
}
else
{
s = s -> next;
return search(s, wod);      /* 添加了这行代码 */
//bool c = search(s, wod);  /* 停用了这行代码 */
}
return false;
}

当重新编译并在相同文本文件上运行该程序时，将获得以下统计输出。

拼写错误的单词数：17062
字典中的单词数：143091
文本中的单词数：376904
载入时间：0.08
检查时间：4.14
大小时间：0.00
卸载时间：0.01
总时间：4.23

这与使用程序的非递归版本列出的值一致。

我将这个重构后的版本与其他选择的文本文件进行了对比，所有的结果都与使用程序的非递归版本运行时的值相符。

顺便说一下，我使用了gcc编译器。这是我系统上使用的编译器，而不是Clang。我还要指出，为了成功构建这个程序，我需要做另外一件事。在编译时，编译器抱怨“table”数组的变量大小定义。

const unsigned int N = 26;

为了解决这个问题，我不得不将“N”的赋值/定义移到与头文件中“LENGTH”的定义相同的位置。

// 单词的最大长度
// （例如，pneumonoultramicroscopicsilicovolcanoconiosis）
#define LENGTH 45
#define N 26

我认为这些额外的调整对于使用递归函数的功能没有任何影响，但我希望能够充分透明。

无论如何，希望通过这个扩展的解释，您可以尝试一下代码调整，看看递归函数是否现在可以工作。"

英文:

I thought I would investigate this issue further as it seemed to me that adding in a return within the "else" block should address the issue. Possibly, I was not making the answer clear enough via the comments so I went ahead and acquired the lesson code, implemented your code solution with the non-recursive check function performing some test over a select set of text files, and then trying out the code with the recursive search function along with the code tweak I had noted.

Executing the non-recursive solution over the "aca.txt" file, the following was the terminal output to be used as the baseline.

WORDS MISSPELLED:     17062
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        376904
TIME IN load:         0.08
TIME IN check:        3.61
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        3.70

I then revised the program, dictionary.c, to include the check/search function calls with the code in its original state.

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash for the word
int h = hash(word);
// finding the length for the word
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -&gt; word, wod))
{
return true;
}
else
{
s = s -&gt; next;
bool c = search(s, wod);
}
return false;
}

Executing this version of the code did give some superfluous misspelling values when run over the same file.

WORDS MISSPELLED:     359710
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        376904
TIME IN load:         0.07
TIME IN check:        4.85
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        4.93

My guess is that this is the type of behavior you were experiencing.

I then revised the search function to provide a return statement within the "else" block as I had noted in the comments. Following is the refactored code.

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// finding the hash for the word
int h = hash(word);
// finding the length for the word
int len = strlen(word) - 1;
// creating another pointer for the sake of iterating
node *tmp = table[h][len];
return search(tmp, word);
}
bool search(node *s, const char *wod)
{
if (s == NULL)
{
return false;
}
if (!strcasecmp(s -&gt; word, wod))
{
return true;
}
else
{
s = s -&gt; next;
return search(s, wod);      /* Added this line of code */
//bool c = search(s, wod);  /* Deactivated this line of code */
}
return false;
}

When the program was recompiled and executed over the same text file, the following statistical output was acquired.

WORDS MISSPELLED:     17062
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        376904
TIME IN load:         0.08
TIME IN check:        4.14
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        4.23

This agrees with the values listed with the non-recursive version of the program.

I checked this refactored version against the other selected text files and all agreed with the values run using the non-recursive version of the program.

FYI, I utilized the gcc compiler. That is the compiler that I have on my system in lieu of Clang. And I will point out one other thing I needed to do to make successfully build this program. When compiling, the compiler complained about having a variable size definition for the "table" array.

const unsigned int N = 26;

To get around this issue with my compiler, I had to move the assignment/definition of "N" to the same spot as the "LENGTH" definition in the header file.

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45
#define N 26

I don't think these additional tweaks had any bearing on the functionality of using a recursive function, but I wanted to be fully transparent.

Anyway, hopefully with this expanded explanation, you might try out the code tweaks to see if the recursive function would now work.

huangapple
  • 本文由 发表于 2023年1月6日 10:29:46
  • 转载请务必保留本文链接：https://go.coder-hub.com/75026362.html
  • c
  • cs50
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定