数据结构与C语言综合训练实习
imove[7] = -1 jmove[7] = 0 蟑螂向其相邻的八个方格的随机漫步通过产生一个随机数值k(0≤k≤7)来模拟。当然，蟑螂不能爬出屋外，所以应该去掉通往墙壁的坐标值并形成一个新的随机组合。蟑螂每次进入一个方格，该方格的计数器就增加一，从而计数器的一个非零元素就表示蟑螂到达对应方格的次数。当每一个方格被至少进入一次时，试验就完成了。试编写程序进行上述规定的模拟试验。 （2）设计目的 利用二维数组解决复杂的实际问题； 了解实际问题到计算机问题的转化； 了解算法设计中边界条件的重要性 (3) 基本要求 你的程序必须： （a）能够处理所有的n和m值, n和m满足：2 数据结构与C语言综合训练实习 a) 对任意给定的字符串S，建立其后缀数组； b) 查找一个字符串S是否包含子串T； c) 统计S中出现T的位置和次数； d) 找出S中最长的重复子串。所谓重复子串是指出现了两次以上的子串； （4）实现提示 利用基数分类对所有子串进行排序来构造后缀数组。 (1) 问题描述 本设计需完成两部分工作：一个是定义并实现一称为CatalogTree的ADT，用它来表达字符串集合组成的有序树；另一个是一个Shell的应用程序，用它来模拟文件目录系统，并提供模拟操作界面。 CatalogTree的组织结构如下图(带父结点指针的儿子—兄弟链树)： 104 模拟文件目录系统 CatalogTree的结构示意图 针对于目录系统，CatalogTree的结点存放的数据内容为字符串，每个结点对应一个目录项，该目录项可以是目录，也可以是文件，如果是目录就可以再存放其它目录或文件，即非叶结点；如果是文件就是叶结点。从根结点到该结点路经所有结点的字符串用“/”进行组合后就是该目录项的绝对路径，用来唯一的标识该目录。例如：/usr/li/email/student/。 32 数据结构与C语言综合训练实习 目录系统具有如下基本操作： 1) dir ——列出当前目录下的所有目录项 2) cd ——打出当前目录的绝对路经 3) cd ..——当前目录变为当前目录的父目录 4) cd str——当前目录变为str所表示路径的目录 5) mkdir str ——在(当前目录下)创建一个子目录(名为str) 6) mkfile str ——在(当前目录下)创建一个文件(名为str) 7) delete str ——删除(当前目录下)名为str的目录或文件 (2) 课程设计目的 应用树知识模拟一个目录管理系统。 (3) 基本要求 ① 描述并实现CatalogTree的ADT，包括其上的基本操作：如插入一个结点，寻找一个结点，返回一个结点的最左儿子等（具体情况依据应用自定）。 ② 应用CatalogTree的ADT实现一个完成文件目录系统的Shell应用程序。 ③ 该Shell是一个不断等待用户输入命令的解释程序，根据用户输入的命令完成相关操作，直到退出（quit）。命令名及其含义如上所述。 ④ 目录树结构可以保存（save）到文件中，也可从文件中读出（load *.dat）。 ⑤ dir命令的结果应能够区分是子目录和还是文件。 ⑥ 应对命令4)~7)中的str区分是绝对路经，还是相对路径。 (4) 实现提示 关键是树上基本操作的实现。 33