Week 1 - Strings and Arrays

题目 1 - 关键词检测

1 题目要求

完成程序从标准输入中读入一个单词，从文本文件article.txt中读入一段英文短文，输出文中该单词是否出现。若单词出现，输出True，否则输出False。

仅大小写不同视作相同的单词。单词可能会被空格、换行、标点、数字或其他非字母字符隔开，你可能需要逐字符读入之后按照非字母字符分词。

本周的习题目标为复习字符串和数组的操作，不允许使用一切有关字符串处理的库函数，包括但不限于strcmp、strcpy、strlen、strcat等。单词不会超过200个字符。

关于处理文件的方法，请参阅题目最后“题目参考：文件输入输出”部分。

2 样例输入输出

article.txt

Computer programming is the process of designing and building an executable computer program for accomplishing a specific computing task. Programming involves tasks such as analysis, generating algorithms, profiling algorithms' accuracy and resource consumption, and the implementation of algorithms in a chosen programming language (commonly referred to as coding[1][2]).

输入：

computer

输出：

True

3 实现要求

请注意程序的模块化实现，并将下面两个功能单独实现成函数：

• void to_lower(char *s)：实现将字符串转为小写的功能，以此完成大小写不敏感的字符串比较。
• int/bool str_equal(char *s1, char *s2)：当两个字符串相同时输出1/True，否则输出0/False。

在今后的编程中，也请注意程序的模块化。

4 题目参考：文件输入输出

4.1 输出输出重定向

如果你编写的程序只从一个文件读入，并且没有从命令行读入（从命令行读入称作“标准输入”）的需求，最简便的方法是将“标准输入”重定向至一个文件。在主函数中调用：

freopen("input.txt", "r", stdin);

即可将标准输入重定向至input.txt。调用此函数后，所有的从命令行输入的命令将会变成在文件中读入的命令（包括C++的cin）。其中，第一个参数是文件名，第二个参数是文件打开模式，r表示读取，第三个参数是重定向的输入流，stdin表示标准输入。在读取结束后，调用

fclose(stdin);

以关闭文件。

相应地，对标准输出进行重定向请使用：

freopen("output.txt", "w", stdout);

在此之后，所有向命令行输出的命令将会输出至output.txt中。此处，w表示写入，stdout表示标准输出。使用w作为文件打开模式将会清空文件现有内容，如果想向文件中追加内容，需要使用a。在输出结束后，使用

fclose(stdout);

关闭文件。以下是一个例程：

#include <stdio.h>

int main() {
  freopen("myfile.txt", "w", stdout);
  printf("This sentence is redirected to a file.");
  fclose(stdout);
  return 0;
}

更多关于freopen函数的用法，请参考这里。该函数被包含在标准库stdio.h/cstdio中。

在这道例题中，你可以先从命令行读取目标单词后，将标准输入重定向至article.txt，读入文件内容。

4.2 更通用的文件打开方法

许多时候我们需要交替从命令行和/或多个文件中输入输出，这时更加方便的方式是使用fopen函数。若要读入，使用：

FILE *fp_in = fopen("input.txt", "r");

打开文件。在此文件读入时，需要调用相应的文件读入函数，并在读取完成后关闭文件。例如：

#include <stdio.h>

int main() {
    FILE *fp;
    char buff[255];

    fp = fopen("/tmp/test.txt", "r");
  
    fscanf(fp, "%s", buff);
    printf("1 : %s\n", buff);

    fgets(buff, 255, (FILE*)fp);
    printf("2: %s\n", buff);
   
    fgets(buff, 255, (FILE*)fp);
    printf("3: %s\n", buff);
  
    fclose(fp);

    return 0;
}

相应地，输出则使用：

FILE *fp_out = fopen("output.txt", "w");

例如：

#include <stdio.h>

int main() {
    FILE *fp;

    fp = fopen("/tmp/test.txt", "w+");
    fprintf(fp, "This is testing for fprintf...\n");
    fputs("This is testing for fputs...\n", fp);
    fclose(fp);

    return 0;
}

更多关于fopen函数和相应文件输入输出函数的用法，请参考这里。该函数也被包含在标准库stdio.h/cstdio中。

4.3 C++的文件输入输出流

C++提供文件输入输出流。下列类和函数包含在头文件iostream和fstream中。如果你会使用cin/cout进行输入输出，这种方法会很容易上手。

若要读入文件，调用

ifstream fin("input.txt");

之后，你可以像使用cin一样使用fin。类似地，调用

ofstream fout("output.txt");

之后，你可以像使用cout一样使用fout。文件处理完毕后，调用

fin.close();
fout.close();

关闭文件。

更多关于文件输入输出流的信息请参阅这里。

题目2 - 多次字典查询：哈希表

1 题目要求

现实问题中，很多时间我们需要从大量的语料库中将出现的单词存储成词典以备查询，且查询任务将产生多次。

朴素的实现方法需要将关键词与词典单词一一进行匹配。由于词典很大，待匹配单词（字符串）可能极长，逐一匹配时间开销十分巨大，难以负担。

例如，一些IDE的代码搜索功能需要记录在已经编写好的代码库中出现的单词（变量名等）出现的位置；搜索引擎需要对网页中出现的单词查表以将其归类。

本题目要求大家用哈希表实现跟上一题相同的功能。我们下面对哈希表进行简单的介绍。

2 题目参考：哈希表简介

哈希表（Hash Table）是一种支持快速查询的数据结构。其通过设计一个哈希函数，将数据映射到表中的一个位置来进行查询。

例如，int f(string s)接受字符串输入并输出0-99的整数。f("apple")=20, f("computer")=7。通过维护一个大小为100行的表（数组），当单词"apple"出现时，我们在表格第20行的位置进行标记；当单词"computer"出现时，在表格第7行的位置进行标记。当查询关键词"computer"时，计算f("computer")=7，查表第7行，即可知道该单词已经出现过。通过使用哈希表，我们在查询时避免了待查字符串与词典中的字符串进行一一比较，仅需计算一次f()的值，然后直接去表格的对应位置检索即可。

很显然，由于表格只有100行，不同单词占用表格同一行的情况将有可能发生。（例如，当词典里有超过100个单词，必定会有若干单词计算出的f()函数值相等。单词数目不超过100时，这种情况也有可能发生。）这种情况被称作冲突。为了解决冲突，一种常用的方法是将表格的每一行实现成为链表，链表的每一个节点存储一个字符串或指向字符串的指针，如下图所示。此时，若查询单词"computer"，则先计算f("computer")=7，然后沿链表向后一一比较。

可以发现，虽然此时还是需要进行字符串比较，若f()函数能将字符串比较均匀地映射到0～99，平均意义下字符串比较所花费的时间将能减小大约100倍（表格大小），仅附加一次计算f()函数的开销（通常较小），大大加快了查询速度。为此，在设计哈希函数f()时我们希望它能尽可能地将字符串尽可能均匀地映射到表格的每一行。本周任务中，我们不要求同学们自己实现哈希函数。这里提供一个现成的哈希函数：

int f(char *s) {
    int res = 0;
    for (char *c = s; *c != '\0'; ++c) {
        res = res * 26 + (*c - 'a');
        res = res % 2333;
    }
    return res;
}

该函数实现将由小写字母组成的字符串视为26进制的数字（额外阅读），对一个大素数P（此处为2333）取模。相应的，此时哈希表的大小应该为2333。这是一种对字符串进行哈希的常用方式。为什么建议对素数取模，请自行参阅相关资料。

3 样例输入输出

article.txt

Computer programming is the process of designing and building an executable computer program for accomplishing a specific computing task. Programming involves tasks such as analysis, generating algorithms, profiling algorithms' accuracy and resource consumption, and the implementation of algorithms in a chosen programming language (commonly referred to as coding[1][2]).

输入：

computer
program
Nanjing

输出：

True
True
False

4 实现要求

请根据自己的掌握情况，选择是否使用链表解决冲突：

• 如果你还不能熟练实现链表，请实现一个不考虑冲突的哈希表并完成题目。由于可能会发生冲突导致结果错误，你可能会丢掉这道题约10%的分数。
• 如果你能够实现链表，请实现一个使用链表解决冲突的哈希表并完成题目。

在题目一要求的两个函数以外，请实现下列函数：

• int hash(char *s)：哈希函数，上文中的函数f()；
• void ht_insert(char *s)：向哈希表中添加字符串；
• int/bool ht_find(char *s)： 当哈希表中存在字符串s时输出1/True，否则输出0/False。

如果你已经能够初步掌握类的使用，你可以将哈希表实现为一个类。相应地，上述函数可以实现成类的成员函数：

• int HashTable::hash(char *s)
• void HashTable::insert(char *s)
• bool HashTable::find(char *s)

题目 3 - 多次字典查询：布隆过滤器 （附加题，不算分）

题目要求

使用哈希表存储字典并（使用链表）解决冲突时，仍旧需要将每个单词都存储下来，空间开销较大；若忽略冲突，则可能有较大的出错概率。

布隆过滤器（Bloom Filter）不通过将所有字符串进行记录来解决冲突，而是使用多个不同的哈希函数进一步减小出错的概率。具体而言，通过设计多个哈希函数f1(s)、f2(s)、…、fk(s)，一个字符串将被多个表记录。此时表的每一行仅记录哈希值为对应值的字符串是否出现过。若一个字符串在每个表格中都记录存在，则认为字符串出现过，否则认为没有出现过。可以看出，与（忽略冲突的）哈希表一样，布隆过滤器不会把出现过的字符串判定为没出现过，但有可能把没出现过的字符串判定为出现过。相比于（忽略冲突的）哈希表，增加不同的哈希函数可以使布隆过滤器出错的概率降低。

请基于上一题（不处理冲突的哈希表），通过多加入几个不同的哈希函数，实现布隆过滤器。功能要求同上一题相同。你可以借助不同的素数构建不同的哈希函数（素数表）。

实现要求

在题目一要求的两个函数以外，类比题目2，请实现下列函数（若实现为类，则设计相应的成员函数并完成）：

• void bf_insert(char *s)：向布隆过滤器中添加字符串；
• int/bool bf_find(char *s)：当布隆过滤器中存在字符串s时输出1/True，否则输出0/False。

多个不同但相似的哈希函数使得代码行数剧增，可维护性下降。试思考如何改善这一问题？