2020数据结构课程设计之单词检查：
单词检查(Ⅰ)- 顺序表实现
许多应用程序，如字处理软件，邮件客户端等，都包含了单词检查特性。单词检查是根据字典，找出输入文本中拼错的单词，我们认为凡是不出现在字典中的单词都是错误单词。不仅如此，一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成：
bake cake main rain vase
如果输入文件中有词vake ，检查程序就能发现其是一个错误的单词，并且给出 bake, cake或vase做为修改建议单词。
修改建议单词可以采用如下生成技术：
(1)在每一个可能位置插入‘a-‘z’中的一者
(2)删除单词中的一个字符
(3)用‘a’-‘z’中的一者取代单词中的任一字符
很明显拼写检查程序的核心操作是在字典中查找某个单词，如果字典很大，性能无疑是非常关键的。
你写的程序要求读入字典文件，然后对一个输入文件的单词进行检查，列出其中的错误单词并给出修改建议。
1
2
3
4
5
6
| 课程设计必须采用如下技术完成并进行复杂度分析及性能比较。
朴素的算法,用线性表维护字典
使用二叉排序树维护字典
采用hash技术维护字典
本题要求使用顺序表实现。
|
基本思路：
1）本题难点以及重点都在字符串的匹配问题上。如果完美匹配或需要替换一个字符，说明字符串长度与字典单词长度一致。又或者，字符串长度与字典单词长度差为±1，少一个或多一个，而且只能有一个字母的差异，其余的字母按顺序都相同，说明需要增或者减字母。
2）有了上述思路，就要想办法用顺序表实现这个功能。从宏观的角度，要开一个大数组（大小>=字典单词），其功能为储存匹配到的单词（建议修改成的）在字典中的序号。
3）在遍历字典中的过程，开始匹配（模糊搜索）。每个字典单词都要与输入的字符串进行匹配（首先判断长度是否相等或差是否为±1）。
4）如果长度相等，那么可能完美匹配，如何判断是否完美匹配呢？可以设置一个变量count，赋初值为0。用它来记录字符的失配次数。如果失配次数等于零，那么便是完美匹配啦！如果失配次数等于1，说明要替换单词。但如果失配次数大于1，便说明字符串无缘修改，直接break跳出单词字符的遍历。
5）如果字符串长度大于字典单词长度，那么可能需要删减一个字符。同4的思路，需要设置一个记录失配次数的count变量，来判断是否真的需要删减一个字符（如果count>1就没必要继续匹配了）。所以，在一开始判断字典单词与字符串长度的时候，我们需要利用if与else if语句分别处理三种长度比较的情况，count变量便可设置在if语句之外。但，如何在长度不相同的情况下来进行匹配字符呢？我们可以利用i，j两个变量，来记录匹配位置。（利用i来记录字符串的位置，利用j来记录字典单词的位置。遍历字符时，截至条件为长度较大的长度。如果两个字符失配，那么j–，这样便可继续按顺序匹配）。
6）如果字符串长度小于字典单词长度，那么可能需要增加一个字符。思路同上，但需要注意的是，在记录匹配位置时有变化。
7）因为自己太菜，输入问题困惑了好久（对我来说也是一个难题嘻嘻），下面贴上输入代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| while (cin >> Node[n].character)
{
if (Node[n].character[0] == '#')
break;
Node[n].len = strlen(Node[n].character);
n++;
}
while (cin >> search.character)
{
if (search.character[0] == '#')
break;
search.len = strlen(search.character);
match(search);
}
|
常见错误：
1）输出的全部都是correct。判断是否完美匹配的代码放错了位置，因为当长度不满足上述三个情况时（相对于字典单词，字符串长度过大或过小），此时count也为0。所以如果把判断代码放在了末尾，那么势必会出错。
2）答案部分正确。如果思路正确，大概率是格式错误。
解决方案（第一个错误）：
1.将判断语句紧跟在当长度相等if语句后。
2.设置一个flag标识符，在判断是否为完美匹配时，加上flag条件。
下面是源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <iostream>
#include<cstring>
using namespace std;
struct Node {
char character[16];
int len;
}Node[10001],search;
int n = 0;
int match_flag[10001];
void match(struct Node search)
{
int i, j;
int p=0;
for (int k = 0; k < n; k++)
{
int flag = 0;
int count = 0;
if (search.len == Node[k].len)
{
for (i = 0; i < search.len; i++)
{
if (search.character[i] != Node[k].character[i])
{
count++;
if (count > 1)
break;
}
}
if (!count)
flag = 1;
}
else if (search.len == Node[k].len + 1)
{
for (i = 0, j = 0; i < search.len; i++, j++)
{
if (search.character[i] != Node[k].character[j])
{
j--;
count++;
if (count > 1)
break;
}
}
}
else if (search.len == Node[k].len - 1)
{
for (i = 0, j = 0; j < Node[k].len; i++, j++)
{
if (search.character[i] != Node[k].character[j])
{
i--;
count++;
if (count > 1)
break;
}
}
}
if (count == 0 && flag == 1)
{
cout << search.character << " is correct" << endl;
return;
}
if (count == 1)
match_flag[p++] = k;
}
cout << search.character << ": ";
for (i = 0; i < p; i++)
{
cout << Node[match_flag[i]].character << " ";
}
cout << endl;
}
int main()
{
while (cin >> Node[n].character)
{
if (Node[n].character[0] == '#')
break;
Node[n].len = strlen(Node[n].character);
n++;
}
while (cin >> search.character)
{
if (search.character[0] == '#')
break;
search.len = strlen(search.character);
match(search);
}
return 0;
}
|
