第四关-基于顺序表的顺序查找

【任务分析】

输入修改类型（0表示养生保健食谱，1表示食疗验方）、食材中文名称、数量以及食谱，从文件food.txt中读取数据，修改并保存到新文件中，输出已修改食材对应的全部信息。（需要判断该中文名称是否存在于 food.txt 中，若存在，则执行修改操作，否则，输出“修改失败”。）

如何将数据从文件中读取并存入顺序表？

文件food.txt的格式比较复杂，在读取文件时，首先读取一行数据，然后循环以“#”为分隔符间隔读取字符串，每次循环分别获取食材的中文名称、英文名称、养生功效、营养与功效、专家提醒、相关链接、食谱数量、养生保健食谱、验方数量和食疗验方信息。当读取“食疗验方”信息时，继续以“#”为分隔符间隔读取字符串，保存在“食疗验方”字符串数组中。循环结束后，将食材信息作为新的数据元素插入到数组的末尾。

【算法步骤】

1. 从文件food.txt中读取数据，并存入数组。

2. 修改食材，如果type是0，则修改养生保健食谱，否则修改食疗验方信息。如果修改成功，返回true，否则，返回false

3. 保存修改过的食材信息到文件，注意循环以“#”为分隔符间隔读取字符串，所以保存时要给每个食材信息末尾加“#”。

4. 从文件newfood.txt中读取数据，并存入数组。

5. 获取修改后的食材信息，输出该食材全部信息，则表示修改成功。

第九关-基于字典树的查找

【任务分析】

输入食材英文名称后，实现基于字典树的查找，根据食材数据，构建一棵基于英文名称的字典树，每个结点保存1个字符。

如何将数据从文件中读取并存入顺序表？

文件food.txt的格式比较复杂，在读取文件时，首先读取一行数据，然后循环以“#”为分隔符间隔读取字符串，每次循环分别获取食材的中文名称、英文名称、养生功效、营养与功效、专家提醒、相关链接、食谱数量、养生保健食谱、验方数量和食疗验方信息。当读取“食疗验方”信息时，继续以“#”为分隔符间隔读取字符串，保存在“食疗验方”字符串数组中。循环结束后，将食材信息作为新的数据元素插入到数组的末尾。

【算法步骤】

1. 从文件中读取食材信息，将其按顺序存入L.elem指向的数组中

2. 构建基于链式存储的Trie树，先初始化Trie树所有孩子结点为空

3. 每遍历L的一个节点，新建一个指向根的指针并且遍历每个英文名字的字母

4. 如果其ASCLL码是在a到z间，则新变量赋值为原本的值减去a的ASCLL码

5. 如果在A到Z间则赋值为原本的值减去A的ASCLL码再加上26

6. 其他情况则赋值位52

7. 如果一个指向根的指针的孩子节点的指针数组为空则初始化该节点，不为空则该指针等于指针的孩子节点的指针数组。

8. 构建成功后返回指向根节点的指针

9. 输入要查找的英文名

10. 基于字典树的查找，如果查找成功则返回指向该食材的指针，如果查找失败则返回NULL

11. 返回不为空时，输出食材信息

12. 计算查找成功时的平均查找长度ASL，即所有英文名称的长度除以L表的长度

 第十关-基于开放地址法的散列查找

【任务分析】

从 food.txt 中读取食材的基本信息，实现基于开放地址法（线性探测法）的散列查找。输入食材英文名称后，若查找成功，则输出该食材对应的全部信息，并输出查找成功时的平均查找长度 ASL，否则，输出“查找失败”。

如何将数据从文件中读取并存入顺序表？

文件food.txt的格式比较复杂，在读取文件时，首先读取一行数据，然后循环以“#”为分隔符间隔读取字符串，每次循环分别获取食材的中文名称、英文名称、养生功效、营养与功效、专家提醒、相关链接、食谱数量、养生保健食谱、验方数量和食疗验方信息。当读取“食疗验方”信息时，继续以“#”为分隔符间隔读取字符串，保存在“食疗验方”字符串数组中。循环结束后，将食材信息作为新的数据元素插入到数组的末尾。

【算法步骤】

1. 从文件中读取食材信息，调用HTInsert函数将每条食材数据插入散列表，注意这里处理冲突的方法我用的是线性探测法。

2. 输入要查找的食材英文名称

3. 在散列表HT中查找食材英文名称等于key的元素，若找到，则返回散列表的单元标号，否则返回-1

4. 找到单元标号后输出食材信息并计算ASL，即在插入的过程中统计总的比较次数sumCmp除以HT.length

第十一关-基于链地址法的散列查找

【任务分析】

从 food.txt 中读取食材的基本信息，实现基于链地址法的散列查找。输入食材英文名称后，若查找成功，则输出该食材对应的全部信息，并输出查找成功时的平均查找长度 ASL，否则，输出“查找失败”。

如何将数据从文件中读取并存入顺序表？

文件food.txt的格式比较复杂，在读取文件时，首先读取一行数据，然后循环以“#”为分隔符间隔读取字符串，每次循环分别获取食材的中文名称、英文名称、养生功效、营养与功效、专家提醒、相关链接、食谱数量、养生保健食谱、验方数量和食疗验方信息。当读取“食疗验方”信息时，继续以“#”为分隔符间隔读取字符串，保存在“食疗验方”字符串数组中。循环结束后，将食材信息作为新的数据元素插入到数组的末尾。

【算法步骤】

1.从文件中读取食材信息，调用HTInsert函数（往散列表中插入新的食材f并在插入的过程中统计总的比较次数sumCmp，注意这里的比较次数p移动一次要加一，插入一次也要加一）将每条食材数据尾插法插入散列表

2.输入要查找的食材英文名称

3.查找成功，将p指向单链表头结点

4.输出食材信息并计算ASL，即在插入的过程中统计总的比较次数sumCmp除以C++ount