中山大学编译器构造实验报告：字符串排序与集合去重

"中山大学数据科学与计算机学院的本科生实验报告，涵盖了两个关于编译器构造实验的题目，涉及字符串处理和字典树的构建。" 实验报告中的第一个任务是处理字符串集合并按升序输出不重复的字符。该程序通过初始化一个大小为256的数组来标记输入字符串中出现的字符。遍历字符串时，如果某个字符出现，则在对应的数组索引处设置标记。最后，遍历整个数组，如果发现已被标记的元素，就将其ASCII值转换回对应的字符并输出。这样，输出的字符序列就是按照升序排列的。 程序清单展示了如何实现这个功能。首先，通过`scanf`读取字符串，然后使用一个for循环遍历字符串并更新标记数组。最后，再次遍历数组并打印出标记的字符。 第二个任务是处理多个字符串集合，输出按升序排列且不重复的字符串集合。此部分引入了字典树（Trie）的概念，对每个输入的字符串构建集合，并将其插入字典树。字典树是一种特殊的树形数据结构，用于高效地存储和检索字符串。在程序中，定义了一个`Node`结构体表示字典树的节点，包含256个子节点指针以及一个终端标志位，用于判断节点是否为字符串的结尾。 在处理每个字符串时，先清零标记数组，然后遍历字符串并将字符标记。接着，将字符串插入字典树，同时检查是否已存在相同的集合。这里，`first`和`top`变量可能用于管理字典树的节点栈，以帮助插入过程。 虽然代码没有完全显示，但可以推断，对于每个字符串，会逐个字符地查找字典树中的对应节点，如果不存在，就创建新节点。如果遇到已经存在的字符序列，说明遇到了重复的集合，此时可以跳过插入。最后，遍历字典树以输出所有不同的字符串集合。 这两个实验展示了基础的字符串处理技巧和数据结构的应用，是理解和实现编译器构造中字符串处理和搜索算法的重要练习。通过这样的实验，学生可以深入理解字符集的表示、字符排序的逻辑以及如何利用数据结构优化字符串操作。