西安交通大学2008级软件工程数据结构与算法课程综合训练题目.pdfVIP

2008级软件工程专业数据结构与算法课程综合训练

第一部分：实验题目

实验一．WordSearchPuzzle

问题描述：

WordSearchPuzzle（以下简称WSP）是一个由字母组成的二维数组和单词列表构成

的单词游戏。该游戏的目标就是要在这个字符数组中寻找单词列表中的单词。这些单词在二

维数组中可以以水平、垂直和斜线这三种形式出现（注意：对于斜线方式，则本身就含有两

种不同角度的斜线形式，即从左上向右下和从右上向左下），同时对于任何一种形式都可以

有两种方向（例如，水平形式则可以从左向右的方向，也可以是从右向左的方向）。图1则

是一个具体的WSP的示意图：

badmintonbaseball

boccebowling

boxingfencing

footballgolf

hockeypolo

rugbyskiing

soccertennis

图1

现在我们要改变WSP的构成部分，也就是只出现字母组成的二维数组，而不提供候选的

单词列表。这样做的目的是让我们能够在给定的字母数组中去探索或者发现里面都有什么单

词。也就是说原有的WSP的单词候选列表中的单词个数是少量的，而现在我们则将单词候选

列表扩展为整个英语词典。可以想象，这将带来大量的有哪些信誉好的足球投注网站操作。怎么解决？这需要我们从

数据结构的选择和算法的设计上下功夫。

输入:

一个文本文件，这个文件是由如下形式构成：

第一行为两个数组构成，该数字表明字符矩阵的行数和列数，数字之间用空格分开；

从第二行开始就是一行行的字母了。

参看：example1.txt

输出：

一个文本文件，这个文件是由若干行构成，每行都是一个单词发现的结果，该行是由如

下格式构成：

单词（行数，列数）（行数，列数）形式

注：其中第一组坐标代表单词的开始位置，第二组坐标代表单词的结束位置

形式由如下三个单词表示：horizon、vertical、diagonal

例如例子中的部分结果表示如下：

golf(1,5)(1,2)horizon

football(4,14)(11,14)vertical

bowling(7,12)(13,6)diagonal

要求：

1、用图形界面的方式或者控制台界面的方式来完成都可以；

2、时间性能尽可能控制好。

实验二．复杂记事本

问题描述：

“记事本”是一个用来创建简单文档的文本编辑器。“记事本”最常用来查看或编辑文本

(.txt)文件，在我们开发的这个记事本中，需要支持的功能如下：

1、常规编辑，不需要支持格式；

2、支持查找的简单逻辑表达式；

3、替换特定的字符或词；

4、具有英文单词的拼写检查能力；

5、具有自动提示输入功能（仅限于英语单词）。

要求：

1、界面必须是图形界面

2、关于“支持查找的简单逻辑表达式”的说明：

1）当输入一个词时，能够标记出出现这个词的所有地方；

2）当输入超过一个词时，可能会出现如下形式：

a)word1word2:代表了在一个句子中既要出现word1，也要出现word2，并且

word1要先于word2；

b)word1ANDword2:代表了在一个句子中既要出现word1，也要出现word2，

出