题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_1/ 第一周 字符串与文件输入输出 题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_1/

练习一

关键词检测 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]). 文章中是否存在关键字“programming”？ 背景？敏感词过滤？ 完成程序从文本文件article.txt中读入一段英文短文，并从 标准输入中读入一个单词，输出文中该单词是否出现。若 单词出现，输出True，否则输出False。

样例输入输出 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]). Input: computer Output: True

要求 仅大小写不同视作相同的单词。单词可能会被空格、换行、标点、数 字或其他非字母字符隔开，你可能需要逐字符读入之后按照非字母字 符分词。 本周的习题目标为复习字符串和数组的操作，不允许使用一切有关字 符串处理的库函数，包括但不限于strcmp、strcpy、strlen、strcat 等。单词不会超过200个字符。 背景？敏感词过滤？

实现要求 请注意程序的模块化实现，并将下面两个功能单独实现成函数： void to_lower(char *s)：实现将字符串转为小写的功能，以 此完成大小写不敏感的字符串比较。 int/bool str_equal(char *s1, char *s2)：当两个字符串相同 时输出1/True，否则输出0/False。 在今后的编程中，也请注意程序的模块化。

题目参考：文件输入输出 1. 输出输出重定向：freopen 把”input.txt”的内容当作屏幕输入： freopen("input.txt", "r", stdin); 用完之后关闭文件： fclose(stdin); 详细内容请见片头链接 把屏幕输出存到”output.txt”： freopen("output.txt", "w", stdout); 用完之后关闭文件： fclose(stdout);

题目参考：文件输入输出 2.更通用的文件打开方法：fopen 使用文件指针： FILE *fp_in = fopen("input.txt", "r"); 需要调用相应的文件读入函数，并在读取完成后关闭文件。 相应地，输出则使用： FILE *fp_out = fopen("output.txt", "w");

题目参考：文件输入输出 2.更通用的文件打开方法：fopen

题目参考：文件输入输出 3. C++的文件输入输出流：fstream C++可以使用文件输入输出流。 ifstream fin("input.txt"); ofstream fout("output.txt"); 之后，你可以像使用cin/cout一样使用fin/fout。

练习二

多次字典查询 现实问题：词典规模大，查询频繁 如何优化程序性能？

样例输入输出 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]). Input & Output: computer True program Nanjing False

多次字典查询 – 哈希表（散列表） 哈希表（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()的值，然后直接去表格的对应位置检索即可。

多次字典查询 – 哈希表（散列表） 冲突：不同单词占用表格同一行。 一种解决方案：使用链表存储

多次字典查询 – 哈希表（散列表） 哈希函数设计关键：将字符串均匀地映射到表格的各个位置 例如：将由小写字母组成的字符串视为26进制的数字，对一个 大素数P（例如23333）取模。这是一种对字符串进行哈希的常 用方式。（你可以在作业中直接使用这个函数）

多次字典查询 – 哈希表（散列表） 请根据自己的掌握情况，选择是否使用链表解决冲突： 如果你还不能熟练实现链表，请实现一个不考虑冲突的哈希表并完成题目。由于冲突导 致可能查询出错，你可能会丢到约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)