问题 I: 单词检查(Ⅰ)- 顺序表实现

题目描述

许多应用程序，如字处理软件，邮件客户端等，都包含了单词检查特性。单词检查是根据字典，找出输入文本中拼错的单词，我们认为凡是不出现在字典中的单词都是错误单词。不仅如此，一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成：
bake cake main rain vase
如果输入文件中有词vake ，检查程序就能发现其是一个错误的单词，并且给出 bake, cake或vase做为修改建议单词。
修改建议单词可以采用如下生成技术：
(1)在每一个可能位置插入‘a-‘z’中的一者
(2)删除单词中的一个字符
(3)用‘a’-'z’中的一者取代单词中的任一字符
很明显拼写检查程序的核心操作是在字典中查找某个单词，如果字典很大，性能无疑是非常关键的。
你写的程序要求读入字典文件，然后对一个输入文件的单词进行检查，列出其中的错误单词并给出修改建议。

课程设计必须采用如下技术完成并进行复杂度分析及性能比较。
(1)朴素的算法,用线性表维护字典
(2)使用二叉排序树维护字典
(3)采用hash技术维护字典

本题要求使用顺序表实现。

输入

输入分为两部分。
第一部分是字典，每个单词占据一行，最后以仅包含’#'的一行表示结束。所有的单词都是不同的，字典中最多10000个单词。

输入的第二部分包含了所有待检测的单词，单词数目不超过50。每个单词占据一行，最后以仅包含’#'的一行表示结束。

字典中的单词和待检测的单词均由小写字母组成，并且单词最大长度为15。

输出

按照检查次序每个单词输出一行，该行首先输出单词自身。如果单词在字典中出现，接着输出" is correct"。如果单词是错误的，那么接着输出’:’，如果字典中有建议修改单词，则按照字典中出现的先后次序输出所有的建议修改单词（每个前面都添加一个空格），如果无建议修改单词，在’:'后直接换行。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me

解题过程

思路

首先我们来分析题目要求，本题要求我们用线性表来维护字典，所以我们首先就要创建一个符合要求的线性表

typedef struct
{
    char elem[17];  //用于储存单词
    int length;     //用于储存该字符串的长度
}Wqlist;
Wqlist  L[10001], S; //L是字典，S是要检测的词 

接下来我们来构造用于检查单词的函数 InitList

1. 判断是否完全匹配

for (i = 0; i < n; i++) //判断是否完全匹配（也就是判断输入的单词是完全正确的）
    {
        //(常见错误）if (L[i].elem == S.elem)   //字符串不能这么比较，要用strcmp函数对比
        if (strcmp(L[i].elem, S.elem) == 0)
        {
            printf("%s is correct\n", S.elem);
            flag = 0;  //flag是标志，若flag = 1则说明不完全匹配，要寻找近似项，否则完全匹配，直接输出correct
            break;
        }
    }

2） 若不完全匹配则分别考虑三种情况

1. 寻找比不完全匹配项多一个字符的近似项

		if (S.length == L[i].length + 1)//寻找比不完全匹配项多一个字符的近似项
            {
                sum = 0;  
                //每次判断结束后要把 sum 初始化，要不然第一次循环以后 sum 就变了，要放到for循环的外面
                //注意是判断结束后 sum 初始化，不是循环中每次都初始化，那sum就失去意义了
                //错误示范：for（j = 0,t = 0.sum = 0; L[i].elem[j] != '\0'; j++, t++)
                //否则每进行一次循环sum就初始化一次，那就实现不了 sum 计数的目的了
                for (j = 0, t = 0; L[i].elem[j] != '\0'; j++, t++)  //因为近似项比匹配项短，所以循环的截止条件是近似项（字典中的项）结束
                {
                    if (L[i].elem[j] != S.elem[t])//记录有几个字符不匹配
                    { 
                        sum++;  //计数 
                        j--;    //用于比较的匹配字符的那个字母不变，为了应对have与behave的类似情况匹配
                    }
                    if (sum >= 2) //超过2个就不用比较了
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);  //输出符合条件的字符
            }

2. 寻找比匹配项少一个字符的近似项

		 if (S.length == L[i].length - 1) //寻找比匹配项少一个字符的近似项
            {
                sum = 0;  //初始化sum
                for (j = 0, t = 0; S.elem[t] != '\0'; j++, t++)//因为匹配项比近似项短，所以循环的截止条件是匹配项（参与比较判断的项）结束
                {
                    if (L[i].elem[j] != S.elem[t]) //记录有几个字符不匹配
                    { 
                        sum++; 
                        t--;
                    }
                    if (sum >= 2) 
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);
            }

3. 寻找长度相同但只有一个字符不同的匹配项

       if (S.length == L[i].length) //寻找长度相同但只有一个字符不同的匹配项
            {
                sum = 0;
                for (j = 0, t = 0;  L[i].elem[j] != '\0'; j++, t++)
                {
                    if (L[i].elem[j] != S.elem[t]) //记录有几个字符不匹配
                        sum++;
                    //因为一样长所以只要有超过2个匹配不上就直接错了，不存在匹配项是近似项子串的问题
                    if (sum >= 2) 
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);
            }

最终实现代码（AC通过，严禁复制）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable:4996)
#define MAXN 10001
typedef struct
{
    char elem[MAXN];
    int length;
}Wqlist;
Wqlist  L[MAXN], S; //L是字典，S是要检测的词 
int n = 0, m = 0;
void InitList(Wqlist S)//查验函数
{
    int i, j, t, sum, flag = 1;
    for (i = 0; i < n; i++) //判断是否完全匹配（也就是判断输入的单词是完全正确的）
    {
        /*
        if (L[i].elem == S.elem)   //字符串不能这么比较，要用strcmp函数对比
        {
            printf("%s is correct\n", S.elem);
            flag = 0;
            break;
        }
        */
        if (strcmp(L[i].elem, S.elem) == 0)
        {
            printf("%s is correct\n", S.elem);
            flag = 0;  //flag是标志，若flag = 1则说明不完全匹配，要寻找近似项，否则完全匹配，直接输出correct
            break;
        }
    }
    if (flag)
    {
        printf("%s:", S.elem);
        for (i = 0; i < n; i++)
        {
            // printf("%s:", S.elem);//这句话要放到for循环的外面，因为这个for循环只是针对一个单词进行的，所以只需要输出一个标题
            if (S.length == L[i].length + 1)//寻找比不完全匹配项多一个字符的近似项
            {
                sum = 0;  //每次判断结束后要把 sum 初始化，要不然第一次循环以后 sum 就变了，要放到for循环的外面
                //注意是判断结束后 sum 初始化，不是循环中每次都初始化，那sum就失去意义了
                //你写的for（j = 0,t = 0.sum = 0; L[i].elem[j] != '\0'; j++, t++)每进行一次循环sum就初始化一次，那就实现不了 sum 计数的目的了
                for (j = 0, t = 0; L[i].elem[j] != '\0'; j++, t++)  //因为近似项比匹配项短，所以循环的截止条件是近似项（字典中的项）结束
                {
                    if (L[i].elem[j] != S.elem[t])//记录有几个字符不匹配
                    { 
                        sum++;  //计数 
                        j--;    //用于比较的匹配字符的那个字母不变，为了应对have与behave的类似情况匹配
                    }
                    if (sum >= 2) //超过2个就不用比较了
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);  //输出符合条件的字符
            }
            if (S.length == L[i].length - 1) //寻找比匹配项少一个字符的近似项
            {
                sum = 0;  //初始化sum
                for (j = 0, t = 0; S.elem[t] != '\0'; j++, t++)  //因为匹配项比近似项短，所以循环的截止条件是匹配项（参与比较判断的项）结束
                {
                    if (L[i].elem[j] != S.elem[t]) //记录有几个字符不匹配
                    { 
                        sum++; 
                        t--;
                    }
                    if (sum >= 2) 
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);
            }
            if (S.length == L[i].length) //寻找长度相同但只有一个字符不同的匹配项
            {
                sum = 0;
                for (j = 0, t = 0;  L[i].elem[j] != '\0'; j++, t++)
                {
                    if (L[i].elem[j] != S.elem[t]) //记录有几个字符不匹配
                        sum++;
                    //因为一样长所以只要有超过2个匹配不上就直接错了，不存在匹配项是近似项子串的问题
                    if (sum >= 2) 
                        break;
                }
                if (sum <= 1)  
                    printf(" %s", L[i].elem);
            }
        }
        printf("\n");
    }

}
int main()
{
    while (scanf("%s", L[n].elem) != EOF)//要添加截止条件，要不然就输出超限
    {
        if (L[n].elem[0] == '#')  
            break;
        L[n].length = strlen(L[n].elem);
        n++;
    }
    while (scanf("%s", S.elem) != EOF)
    {
        if (S.elem[0] == '#')  
            break;
        S.length = strlen(S.elem);
        InitList(S);
    }

    return 0;
}

算法分析

后续补充，敬请关注

声明：本文由博主原创，请同学们自己借鉴思考后，独立完成课程设计的有关题目，请勿直接复制粘贴，祝同学们课程设计顺利（课程设计后的期末考试也要加油哦！）

如果发现本文有那些错误和问题请及时私信博主，感谢各位大佬批评指正！

看都看了，点个赞再走吧！