精华内容
下载资源
问答
  • 项目简介 word-checker 用于英文单词拼写检查 创作目的 平时工作学习中对于单词拼写检查也是很常见的需求 一直没找到特别好用的版本就自己写一个方便以后拓展和他人使用 自定义单词检查实现类 如果你看了 单词检查...
  • 课程设计 - 单词检查

    千次阅读 多人点赞 2017-06-13 15:01:40
    hnust 单词查找 许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给...

    前言

    各位在做课程设计的学弟学妹,请保持独立思考的能力!

    复制粘贴满足自己的虚荣心,却永远解决不了你是“菜鸟”的事实。


    题目描述

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

    课程设计必须采用如下技术完成并进行性能比较(也就是,同学要提交多份采用不同技术实现的代码,而不仅仅是一份AC的代码)。
    (1)朴素的算法,用线性表维护字典
    (2)使用AVL树维护字典
    (3)采用hash技术维护字典
    hash函数建议自行设计一个,然后和成熟的hash函数比较,比如下面的ELF hash函数。

    /* UNIX ELF hash
     * Published hash algorithm used in the UNIX ELF format for object files
     */
    unsigned long hash(char *name)
    {
    unsigned long h = 0, g;
    
    while ( *name ) {
    h = ( h << 4 ) + *name++;
    if ( g = h & 0xF0000000 )
    h ^= g >> 24;
    h &= ~g;
    }
    return h;
    }
    

    另外,请比较线性地址法和链地址法两种冲突处理方法的性能,以及调整hash表大小对性能的影响。
    注意:平衡二叉树和hash的实现必须由同学们编码完成,不能采用C++或JAVA的泛型库。

    输入

    输入分为两部分。
    第一部分是字典,每个单词占据一行,最后以仅包含'#'的一行表示结束。所有的单词都是不同的,字典中最多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

    实验设计

    方法一.用线性表维护字典

    题解:模糊匹配单词时,这里有三个条件能匹配成功,即对单词一个字符增,删,替能与字典库单词匹配。
    这里用线性表,定义一个结构体数组,由字符串和字符串长度信息组成。
    如何增删替呢?

    • 替:对于上述样例,只要两个字符串长度相等,且只有一个字符不相等,我们就认为他可以替换,如m和i。
    • 增:对于上述样例,相当于单词只能增加一个字母,所以字典串只能比该单词串长度大1才能满足,即单词与字典单词全都顺序匹配,只有其中一个位置需要添加一个单词,如oo与too。
    • 减:与增相同,只要我们的单词串按顺序匹配,只有一个与字典单词不一样即可。
      对于变量cnt,主要起到一个记录当前比较的位置,两者单词不相等的次数。具体看代码理解。
      对于增和减,i,j都有特别处理,就是保持不动的处理。例如减的时候,单词串bc,字典串abc,i=0,j=0,字符不相等,i不动,j++,这样的操作!!
      大佬就直接看代码吧,别听上面瞎比比,是不是说晚了? -。-
    #include<stdio.h>
    #include<string.h>
    struct node
    {
        char ch[16];
        int len=0;
    }dic[10005],al;//dic数组为存在字典单词
    int n=0,int ans[10005];
    void pp(node T)
    {
        int i=1,j=1;
        int p=0;//表示有多少与之匹配,记录其字典中序号
        for(int cse=0;cse<n;cse++)
        {
            int cnt=0;
            if(T.len==dic[cse].len){//完美匹配或模糊匹配-替
                for(i=0;i<T.len;i++){
                    if(T.ch[i]!=dic[cse].ch[i]){
                        cnt++;
                        if(cnt>1) break;
                    }
                }
                if(cnt==0){//既完美匹配
                    printf("%s is correct\n",T.ch);
                    return;
                }
            }else if(T.len==dic[cse].len+1){//减
                for(i=0,j=0;i<T.len;i++,j++){
                    if(T.ch[i]!=dic[cse].ch[j]){
                        cnt++;
                        j--;
                        if(cnt>1) break;
                    }
                }
            }else if(T.len==dic[cse].len-1){//增
                for(j=0,i=0;j<dic[cse].len;i++,j++){
                    if(T.ch[i]!=dic[cse].ch[j]){
                        cnt++;
                        i--;
                        if(cnt>1) break;
                    }
                }
            }
            if(cnt==1)
                ans[p++]=cse;
        }
        printf("%s:",T.ch);
        for(i=0;i<p;i++)
            printf(" %s",dic[ans[i]].ch);
        printf("\n");
        return ;
    }
    int main()
    {
        while(~scanf("%s",dic[n].ch)){//输入字典单词
    
            if(dic[n].ch[0]=='#') break;
            dic[n].len=strlen(dic[n].ch);
            n++;
        }
        while(~scanf("%s",al.ch)){//输入查找的单词
            if(al.ch[0]=='#') break;
            al.len=strlen(al.ch);
            pp(al);
        }
        return 0;
    }
    
    

    方法二.用AVL树维护字典

    • AVL:即平衡二叉树,这里主要是建树和查找树。建平衡树是关键。
    • 要我用AVL做,我一开始考虑的就是就不能AC,答案顺序不一样。
    • 后来想想,不就是要用AVL查字典单词怎么样快嘛,当然O(log2n)了。当然没有查到呢,我们就只能乖乖模糊匹配整个字典咯。这里做了一个花式操作,就是录入的时候,不止录入字典单词,单词长度,还加一个录入时的序号。
    • 具体要做的:建平衡二叉树(先学建排序二叉树吧),再查找,查不到就是模糊匹配整颗树了。
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    
    using namespace std;
    struct node
    {
        char ch[16];
        int len=0;
        int num=0;
    }dic[10005],al;
    int n=0;//当前字典数
    int p=0;//记录当前模糊单词数
    int ans[10005];
    int flag=0;//是否存在正确匹配的单词
    typedef struct tree
    {
        node dic;
        int bf;
        tree *l,*r;
    }BiTNode, *BiTree;
    void R_Rotate(BiTree &p)
    {
        BiTree L;
        L=p->l;p->l=L->r;L->r=p;
        p=L;
    }
    void L_Rotate(BiTree &p)
    {
        BiTree R;
        R=p->r;p->r=R->l;R->l=p;
        p=R;
    }
    void LeftBalance(BiTree &T)
    {
        BiTree L,Lr;
        L=T->l;
        switch(L->bf)
        {
            case 1:T->bf=L->bf=0;
                R_Rotate(T);
                    break;
            case -1:Lr=L->r;
                switch(Lr->bf)
                {
                    case 1:T->bf=-1;
                        L->bf=0;
                        break;
                    case 0:
                        T->bf=L->bf=0;
                        break;
                    case -1:
                        T->bf=0;
                        L->bf=1;
                        break;
                }
                Lr->bf=0;
                L_Rotate(T->l);
                R_Rotate(T);
        }
    }
    void RightBalance(BiTree &T)
    {
        BiTree R,Rl;
        R=T->r;
        switch(R->bf)
        {
            case -1:T->bf=R->bf=0;
                L_Rotate(T);
                break;
            case 1:Rl=R->l;
                switch(Rl->bf)
                {
                    case -1:T->bf=1;
                        R->bf=0;
                        break;
                    case 0:T->bf=R->bf=0;
                        break;
                    case 1:T->bf=0;
                        R->bf=-1;
                        break;
                }
                Rl->bf=0;
                R_Rotate(T->r);
                L_Rotate(T);
        }
    }
    int InsertBIT(BiTree &T,node e,int &tel)
    {
        BiTree s;
        if(!T){
            T=new BiTNode;
            T->dic=e;
            T->l=T->r=NULL;
            T->bf=0;
            tel=1;
        }else{
            if (e.len<T->dic.len)
            {
                if (!InsertBIT(T->l,e,tel)) return 0;
                if (tel)
                    switch(T->bf)
                    {
                        case 1:LeftBalance(T); tel=0; break;
                        case 0:T->bf=1; tel=1; break;
                        case -1:T->bf=0; tel=0; break;
                    }
            }
            else{
                if (!InsertBIT(T->r,e,tel)) return 0;
                if (tel)
                    switch(T->bf)
                    {
                        case 1:T->bf=0; tel=0; break;
                        case 0:T->bf=-1; tel=1; break;
                        case -1:RightBalance(T); tel=0; break;
                    }
            }
        }
        return 1;
    }
    int p=0;//记录当前模糊单词数
    int ans[10005];
    int flag=0;//是否存在正确匹配的单词
    int pp(node S,node T)
    {
        int i=1,j=1;
        int cnt=0;
        if(T.len==S.len){//完美匹配或模糊匹配-替
            for(i=0;i<T.len;i++){
                if(T.ch[i]!=S.ch[i]){
                    cnt++;
                    if(cnt>1) break;
                }
            }
            if(cnt==0){//既完美匹配
                printf("%s is correct\n",T.ch);
                flag=1;
                return 2;
            }
        }else if(T.len==S.len+1){//减
            for(i=0,j=0;i<T.len;i++,j++){
                if(T.ch[i]!=S.ch[j]){
                    cnt++;
                    j--;
                    if(cnt>1) break;
                }
            }
        }else if(T.len==S.len-1){//增
            for(j=0,i=0;j<S.len;i++,j++){
                if(T.ch[i]!=S.ch[j]){
                    cnt++;
                    i--;
                    if(cnt>1) break;
                }
            }
        }
        return cnt;
    }
    void FindBIT(BiTree T,node e)
    {
        if(flag)
            return;
        if (T){
            if(abs(T->dic.len-e.len)<=1){
                if(pp(T->dic,e)==1) ans[p++]=T->dic.num;
            }
            if (T->dic.len-e.len>1) FindBIT(T->l,e);
            else if (T->dic.len-e.len<-1) FindBIT(T->r,e);
            else{
                FindBIT(T->l,e);
                FindBIT(T->r,e);
            }
        }
    }
    int main()
    {
        BiTree T=NULL;//定义一颗树
        int tel;
        while(~scanf("%s",dic[n].ch))//输入字典单词
        {
            if(dic[n].ch[0]=='#') break;
            dic[n].len=strlen(dic[n].ch);
            dic[n].num=n;
            InsertBIT(T,dic[n],tel);
            n++;
        }
        while(~scanf("%s",al.ch))//输入查找的单词
        {
            if(al.ch[0]=='#') break;
            al.len=strlen(al.ch);
            flag=p=0;
            FindBIT(T,al);
            if(!flag){
                printf("%s:",al.ch);
                sort(ans,ans+p);
                for(int i=0;i<p;i++)
                    printf(" %s",dic[ans[i]].ch);
                printf("\n");
            }
        }
        return 0;
    }
    

    方法三.采用hash技术维护字典

    • 采用题目提供的hash值生成法的话,我们可以开一个hash[1005]的数组,如果生成的hash值超过1000,就把它压缩至1000以内的数,这当然会导致hash[]数组冲突了,解决冲突的办法是在hash[]内再加个数组或链表,把冲突值都写一起。这样一般查找下来,时间复杂度为O(1)。但是对于模糊单词的搜索,我们只能查找整个表咯。怪我咯,我太菜,-。-,找模糊匹配单词O(n)。
    • 当然我之前还考虑了一种方便的,就是以字符串长度为单位的hash数组,这样数组可以定义为a[16]就好了,当然长度相同的就存在链表或数组里咯,这样有个好处,我们模糊匹配单词时,只要查三个表,len,len-1,len+1。最坏的情况就是所有字符都是一个长度大小,查找下来和方法一,线性表方法没区别了。
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    struct node
    {
        char ch[16];
        int len=0;
    }dic[10005],al;
    struct hhash
    {
        int *ch=NULL;
        int cnt=0;
    }h[1005];
    int n=0;//字典数
    unsigned long ELFhash(char *name)//哈希值计算
    {
        unsigned long h = 0, g;
    
        while ( *name ) {
        h = ( h << 4 ) + *name++;
        if ( g = h & 0xF0000000 )
        h ^= g >> 24;
        h &= ~g;
        }
        while(h>1000) h/=10;//我限制了hash值范围。
        return h;
    }
    int pp(node T)
    {
        int hh=ELFhash(T.ch);
        int i=1,j=1;
        if(h[hh].cnt>=1){
            for(int cse=0;cse<h[hh].cnt;cse++){
                if(strcmp(dic[h[hh].ch[cse]].ch,al.ch)==0){
                   printf("%s is correct\n",al.ch);
                   return 1;
                }
            }
        }
        /*找不到就搜索整个表*/
        printf("%s:",T.ch);
        for(int cse=0;cse<n;cse++)
        {
            int cnt=0;
            if(T.len==dic[cse].len){//完美匹配或模糊匹配-替
                for(i=0;i<T.len;i++){
                    if(T.ch[i]!=dic[cse].ch[i]){
                        cnt++;
                        if(cnt>1) break;
                    }
                }
            }else if(T.len==dic[cse].len+1){//减
                for(i=0,j=0;i<T.len;i++,j++){
                    if(T.ch[i]!=dic[cse].ch[j]){
                        cnt++;
                        j--;
                        if(cnt>1) break;
                    }
                }
            }else if(T.len==dic[cse].len-1){//增
                for(j=0,i=0;j<dic[cse].len;i++,j++){
                    if(T.ch[i]!=dic[cse].ch[j]){
                        cnt++;
                        i--;
                        if(cnt>1) break;
                    }
                }
            }
            if(cnt==1)
                printf(" %s",dic[cse].ch);
        }
        printf("\n");
        return 1;//success
    }
    int main()
    {
    	while(~scanf("%s",dic[n].ch)){//输入字典单词
            if(dic[n].ch[0]=='#') break;
            dic[n].len=strlen(dic[n].ch);
            int hh=ELFhash(dic[n].ch);
            if(h[hh].cnt==0)//没有则建立
                h[hh].ch=new int[50];
            h[hh].ch[h[hh].cnt++]=n;
            n++;
        }
        while(~scanf("%s",al.ch)){//输入查找的单词
            if(al.ch[0]=='#') break;
            al.len=strlen(al.ch);
            pp(al);
        }
    	return 0;
    }
    
    展开全文
  • 数据结构课程设计-单词检查

    千次阅读 多人点赞 2019-07-02 20:44:45
    问题 I: 单词检查(Ⅰ)- 顺序表实现 时间限制: 1 Sec 内存限制: 128 MB 提交: 2227 解决: 736 [提交][状态][讨论版] 题目描述 许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典...

    问题 I: 单词检查(Ⅰ)- 顺序表实现
    时间限制: 1 Sec  内存限制: 128 MB
    提交: 2227  解决: 736
    [提交][状态][讨论版]
    题目描述
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成:
     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

    单词检查I,数据量不大,直接暴力就行。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+5;
    struct node
    {
        char a[200];
        int len;
    }t[maxn];
    char a[20];
    int main()
    {
        int len=0;
        while(scanf("%s",t[len].a)==1&&t[len].a[0]!='#')
        {
            int k=0;
            long long ans=0;
            for(int i=0;t[len].a[i]!='\0';i++) k++;
            t[len].len=k;
            len++;
        }
        while(scanf("%s",a)==1&&a[0]!='#')
        {
            printf("%s",a);
            int n=strlen(a);
            int f=0;
            for(int i=0;i<len;i++)
            {
                if(t[i].len==n)
                {
                    int b=0;
                    for(int j=0;j<n;j++)
                    {
                        if(a[j]!=t[i].a[j]) break;
                        else b++;
                    }
                    if(b==n)
                    {
                        f=1;
                        break;
                    }
                }
            }
            if(f==1)
            {
                printf(" is correct\n");
                continue;
            }
            printf(":");
            for(int i=0;i<len;i++)
            {
                if(t[i].len-n==1||n-t[i].len==1||t[i].len==n)
                {
                    int h=0,flag=0;
                    int p1=0,k1=0;
                    while(p1<n&&k1<t[i].len)
                    {
                        if(a[p1]==t[i].a[k1]) p1++,k1++,h++;
                        else if(t[i].len-n==1) k1++;
                        else if(n-t[i].len==1) p1++;
                        else p1++,k1++;
                    }
                    if(t[i].len-n==1)
                    {
                        if(h==n) flag=1;
                    }
                    else if(n-t[i].len==1)
                    {
                        if(h==t[i].len) flag=1;
                    }
                    else
                    {
                        if(h==(n-1)) flag=1;
                    }
                    if(flag) printf(" %s",t[i].a);
                }
            }
            printf("\n");
        }
    }
    

    问题 J: 单词检查(Ⅱ)- 二叉排序树实现
    时间限制: 2 Sec  内存限制: 128 MB
    提交: 322  解决: 107
    [提交][状态][讨论版]
    题目描述
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成:
     bake cake main rain vase
    如果输入文件中有词vake ,检查程序就能发现其是一个错误的单词,并且给出 bake, cake或vase做为修改建议单词。
    修改建议单词可以采用如下生成技术:
     (1)在每一个可能位置插入‘a-'z'中的一者
     (2)删除单词中的一个字符
     (3)用‘a'-'z'中的一者取代单词中的任一字符
    很明显拼写检查程序的核心操作是在字典中查找某个单词,如果字典很大,性能无疑是非常关键的。
    你写的程序要求读入字典文件,然后对一个输入文件的单词进行检查,列出其中的错误单词并给出修改建议。

    本题要求使用使用二叉排序树维护字典。为了防止有些人取巧,本题要求输出相应的二叉排序树后序遍历。

    输入
    输入分为两部分。
    第一部分是字典,每个单词占据一行,最后以仅包含'#'的一行表示结束。所有的单词都是不同的,字典中最多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
    #
    样例输出
    award contest be have has if me more too my is i 
    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

    单词检查II,用string会方便不少,树结点的结构也需要有所变化,因为输出要求的是字典的输入先后次序!

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5;
    typedef struct node
    {
        string data;
        int d;
        struct node *lc;
        struct node *rc;
    } node,*link;
    int a[maxn];
    string e,key;
    int dex,cnt,dd;
    int n;
    struct nod
    {
        string ss;
    }t[maxn];
    void Insert(link &root,int dex)
    {
        if(!root)
        {
            link s=new node;
            s->data=e;
            s->d=dex;
            s->lc=s->rc=NULL;
            root=s;
        }
        else if(e<root->data) Insert(root->lc,dex);
        else if(e>root->data) Insert(root->rc,dex);
    }
    void creat(link &root)
    {
        cin>>e;
        cnt=0;
        while(e[0]!='#')
        {
            t[cnt].ss=e;
            Insert(root,cnt);
            cnt++;
            cin>>e;
        }
    }
    void display(link root)
    {
        if(root)
        {
            display(root->lc);
            display(root->rc);
            cout<<root->data<<' ';
        }
    }
    link Find(link root)
    {
        if(!root||key==root->data) return root;
        else if(key<root->data) Find(root->lc);
        else Find(root->rc);
    }
    void Search(link root)
    {
        if(root)
        {
            int len=(root->data).size();
            int h=0,flag=0;
            int p1=0,k1=0;
            if(n-len==1||len-n==1||len==n)
            {
                while(p1<n&&k1<len)
                {
                    if(key[p1]==root->data[k1]) p1++,k1++,h++;
                    else if(len-n==1) k1++;
                    else if(n-len==1) p1++;
                    else p1++,k1++;
                }
                if(len-n==1)
                {
                    if(h==n) flag=1;
                }
                else if(n-len==1)
                {
                    if(h==len) flag=1;
                }
                else
                {
                    if(h==(n-1)) flag=1;
                }
                if(flag) a[dd++]=root->d;
            }
            Search(root->lc);
            Search(root->rc);
        }
    }
    int main()
    {
        link root;
        root=NULL;
        creat(root);
        display(root);
        cout<<"\n";
        while(cin>>key&&key[0]!='#')
        {
            cout<<key;
            int flag=0;
            if(Find(root)!=NULL)
            {
                cout<<" is correct"<<endl;
                continue;
            }
            cout<<':';
            n=key.size();
            dd=0;
            Search(root);
            sort(a,a+dd);
            for(int i=0;i<dd;i++) cout<<' '<<t[a[i]].ss;
            cout<<"\n";
        }
    }
    

    问题 K: 单词检查(Ⅲ)- Hash表实现
    时间限制: 1 Sec  内存限制: 128 MB
    提交: 201  解决: 24
    [提交][状态][讨论版]
    题目描述
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成:
     bake cake main rain vase
    如果输入文件中有词vake ,检查程序就能发现其是一个错误的单词,并且给出 bake, cake或vase做为修改建议单词。

    修改建议单词可以采用如下生成技术:

     (1)在每一个可能位置插入‘a-'z'中的一者
     (2)删除单词中的一个字符
     (3)用‘a'-'z'中的一者取代单词中的任一字符
       很明显拼写检查程序的核心操作是在字典中查找某个单词,如果字典很大,性能无疑是非常关键的。
    你写的程序要求读入字典文件,然后对一个输入文件的单词进行检查,列出其中的错误单词并给出修改建议。

    本题要求采用hash技术维护字典,hash的实现必须由同学们编码完成,不能采用C++或JAVA的泛型库。
    hash函数建议自行设计一个,然后和成熟的hash函数比较,比如下面的ELF hash函数。
    /* UNIX ELF hash
     * Published hash algorithm used in the UNIX ELF format for object files
     */
    unsigned long hash(char *name)
    {
    unsigned long h = 0, g;

    while ( *name ) {
    h = ( h << 4 ) + *name++;
    if ( g = h & 0xF0000000 )
    h ^= g >> 24;
    h &= ~g;
    }
    return h;
    }
    另外,请比较线性地址法和链地址法两种冲突处理方法的性能,以及调整hash表大小对性能的影响。
    输入
    输入分为两部分。
    第一部分是字典,每个单词占据一行,最后以仅包含'#'的一行表示结束。所有的单词都是不同的,字典中最多500000个单词。

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

    字典中的单词和待检测的单词均由小写字母组成,并且单词最大长度为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

    去年这题的数据量是10000,今年改成了500000,时间卡得很紧,TLE很多次,MLE也不少,考虑问题的时候,对于复杂度的分析真的非常关键,学会转化思考问题的角度,换一种视角,问题便能迎刃而解……

    此题的正确解法是:枚举所有的建议单词,在以该单词的哈希值为索引的邻接表中查找即可!!!

    #include<bits/stdc++.h>
    using namespace std;
    char ww[27]="abcdefghijklmnopqrstuvwxyz";
    const int maxn=5e5+1;
    int key[100];
    struct node
    {
        char a[16];
        int d;
    } t[maxn];
    struct nod
    {
        int len;
        int a[100];
    } vis[10005];
    int Hash(char *name)
    {
        long long h=0,g;
        while(*name)
        {
            h=(h<<4)+*name++;
            if(g=h&0xF0000000) h^=g>>24;
            h&=~g;
        }
        h%=10000;
        return (int)h;
    }
    bool check(char a[],int ans,int n)
    {
        for(int i=0; i<vis[ans].len; i++)
        {
            int k=vis[ans].a[i];
            if(strcmp(a,t[k].a)==0) return true;
        }
        return false;
    }
    int checkall(char a[],int ans,int n)
    {
        for(int i=0; i<vis[ans].len; i++)
        {
            int k=vis[ans].a[i];
            if(strcmp(t[k].a,a)==0)
            {
                return k;
            }
        }
        return -1;
    }
    int main()
    {
        int len=0;
        char a[20];
        for(int i=0; i<10005; i++) vis[i].len=0;
        while(scanf("%s",t[len].a)==1&&t[len].a[0]!='#')
        {
            int ans=Hash(t[len].a);
            t[len].d=len;
            vis[ans].a[vis[ans].len]=len;
            vis[ans].len++;
            len++;
        }
        while(scanf("%s",a)==1&&a[0]!='#')
        {
            printf("%s",a);
            int n=strlen(a);
            int ans=Hash(a);
            //if(!vis[ans].len) continue;
            if(check(a,ans,n))
            {
                printf(" is correct\n");
                continue;
            }
            int dd=0;
            printf(":");
            for (int i=0; i<n; i++)//修改
            {
                char e = a[i];
                for(int qq=0; qq<26; qq++)
                {
                    a[i]=ww[qq];
                    ans=Hash(a);
                    int du=checkall(a,ans,n);
                    if(du>=0) key[dd++]=du;
                }
                a[i]=e;
            }
            if(n<15)
            {
                for(int i=0; i<=n; i++) //增加一个字母
                {
                    char e[20];
                    int r = i;
                    strcpy(e,a);
                    for(int qq=0; qq<26; qq++)
                    {
    
                        for(int t=n; t>r; t--) a[t] = a[t-1];
                        a[r] = ww[qq];
                        a[n+1] = '\0';
                        ans=Hash(a);
                        int du=checkall(a,ans,n+1);
                        if(du>=0) key[dd++]=du;
                        strcpy(a,e);
                    }
                }
            }
            if(n>1)
            {
                for(int i=0; i<n; i++)//删除
                {
                    char e[20];
                    int r = i;
                    strcpy(e,a);
                    for(int t=r; t<n; t++) a[t] = a[t+1];
                    a[n-1]='\0';
                    ans=Hash(a);
                    int du=checkall(a,ans,n-1);
                    if(du>=0) key[dd++]=du;
                    strcpy(a,e);
                }
            }
            sort(key,key+dd);
            int k=dd;
            dd=unique(key,key+k)-key;
            for(int i=0; i<dd; i++) printf(" %s",t[key[i]].a);
            printf("\n");
        }
    }
    展开全文
  • 快速拼写单词检查程序,有源码,UML综合实验。 界面美观,操作简单。
  • 单词检查(Ⅰ)- 顺序表实现

    千次阅读 多人点赞 2019-06-27 23:13:32
    问题 I: 单词检查(Ⅰ)- 顺序表实现 时间限制: 1 Sec 内存限制: 128 MB 提交: 3348 解决: 1103 [提交][状态][讨论版] 题目描述 许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典...

    问题 I: 单词检查(Ⅰ)- 顺序表实现
    时间限制: 1 Sec 内存限制: 128 MB
    提交: 3348 解决: 1103
    [提交][状态][讨论版]
    题目描述
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成:
    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

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define max 10000
    
    typedef struct
    {
        char elem[max];
        int length;
    }Sqlist;
    
    Sqlist  L[ max ] , T;  int n = 0,m = 0;
    
    void IF_simple( Sqlist S )
    {
        int i = 0, j ,t ,sum ,flag = 1;
        for(  ; i < n ; i++ )
        {
            if( ! strcmp( L[i].elem , S.elem ) )
            {
                printf("%s is correct\n",S.elem);
                flag = 0 ;
                break;
            }
        }
        if( flag )
        {
             printf("%s:",S.elem);
        for( i = 0; i < n ; i++ )
        {
    
             if( S.length == L[i].length + 1)
                {
                    for( j = 0,t = 0,sum = 0; L[i].elem[j] != '\0' ; j++,t++ )
                    {
                        if( L[i].elem[j] != S.elem[t] ) { sum++; j--; }
                        if( sum > 1) break;
                    }
                    if( sum <= 1 )  printf(" %s",L[i].elem);
                }
    
                if( S.length == L[i].length - 1)
                {
                    for( j = 0,t = 0,sum = 0; S.elem[t] != '\0' ; j++,t++ )
                    {
                        if( L[i].elem[j] != S.elem[t] ) { sum++; t--; }
                        if( sum > 1) break;
                    }
                    if( sum <= 1 )  printf(" %s",L[i].elem);
                }
    
                if( S.length == L[i].length )
                {
                    for( j = 0,t = 0,sum = 0; S.elem[t] != '\0' ; j++,t++ )
                    {
                        if( L[i].elem[j] != S.elem[t] ) sum++;
                        if( sum > 1) break;
                    }
                    if( sum <= 1 )  printf(" %s",L[i].elem);
                }
        }
         printf("\n");
        }
    
    }
    
    int main()
    {
        while(  gets(L[n].elem) )
        {
            if( L[n].elem[0] == '#')  break;
            L[n].length = strlen( L[n].elem );
            n++;
        }
        while(  gets(T.elem) )
        {
            if( T.elem[0] == '#')  break;
            T.length = strlen( T.elem );
            IF_simple( T );
        }
    
        return 0;
    }
    

    数据结构真的是敲一天,整个人都是糊的,树的创建,输入值是真的太不熟练了,还是要多敲敲。。

    展开全文
  • 单词检查(Ⅱ)- 二叉排序树实现

    千次阅读 2020-06-18 16:23:57
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的...

    题目描述
    许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅如此,一些检查程序还能给出类似拼错单词的修改建议单词。 例如字典由下面几个单词组成:
    bake cake main rain vase
    如果输入文件中有词vake ,检查程序就能发现其是一个错误的单词,并且给出 bake, cake或vase做为修改建议单词。
    修改建议单词可以采用如下生成技术:
    (1)在每一个可能位置插入‘a-‘z’中的一者
    (2)删除单词中的一个字符
    (3)用‘a’-'z’中的一者取代单词中的任一字符

    很明显拼写检查程序的核心操作是在字典中查找某个单词,如果字典很大,性能无疑是非常关键的。

    你写的程序要求读入字典文件,然后对一个输入文件的单词进行检查,列出其中的错误单词并给出修改建议。

    本题要求使用使用二叉排序树维护字典。为了防止有些人取巧,本题要求输出相应的二叉排序树后序遍历。

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

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

    字典中的单词和待检测的单词均由小写字母组成,并且单词最大长度为15。
    输出
    第一行输出二叉排序树字典的后序遍历,每一个单词后面跟一个空格。

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

    样例输入 Copy
    i
    is
    has
    have
    be
    my
    more
    contest
    me
    too
    if
    award

    me
    aware
    m
    contest
    hav
    oo
    or
    i
    fi
    mre

    样例输出 Copy
    award contest be have has if me more too my is i
    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

    本题与上一题多了排序树的创建与输出

    #include<iostream>
    #include<cstring>//C++调用字符串函数 
    using namespace std;
    #define MAXSIZE 10001//顺序表可能达到的最大长度
    typedef char ElemType;
    typedef struct List{
    	ElemType elem[20];
    	int length;
    }SqList;
    typedef struct BiTNode{
    	ElemType data[20];
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    SqList L[MAXSIZE];//全局变量,用于保存字典内容 
    int n=0;//用于统计输入字典单词个数 
    BiTree T;//定义一棵树 
    void protect(SqList S)
    {
    	int i,flag=0;
    	for(i=0;i<n;i++){
    		if(strcmp(L[i].elem,S.elem)==0){//与字典一样 
    	       cout << S.elem <<" is correct"<<endl; 
    	       flag=1;//定义一个标志
    		   break;//比较完毕,退出循环 
    		}
    	} 
    	if(flag==0){//不相等情况 
    		cout << S.elem << ":";
    		for(i=0;i<n;i++){
    			if(S.length-L[i].length==1){//输入比字典多一个字母 
    				int count=0;//统计字母不相同的个数 
    				for(int j=0,k=0;L[i].elem[j]!='\0';j++,k++){//逐个字母比较
    					if(L[i].elem[j]!=S.elem[k]){
    					count++; j--;//比较输入字符后面的字母 
    				    } 
    				    if(count>=2)  break;//没有可以修改的字典单词 
    			    }
    			    if(count<=1)  cout<<" "<<L[i].elem; 
    		    }
    		    if(L[i].length-S.length==1){//输入比字典少一个字母 
    				int count=0;//统计字母不相同的个数 
    				for(int j=0,k=0;S.elem[k]!='\0';j++,k++){//逐个字母比较
    					if(L[i].elem[j]!=S.elem[k]){
    					count++; k--;//比较字典字符后面的字母 
    				    } 
    				    if(count>=2)  break;//没有可以修改的字典单词 
    			    }
    			    if(count<=1)  cout<<" "<<L[i].elem; 
    	        }
    	        if(S.length-L[i].length==0){//输入与字典字母数量相等
    				int count=0;//统计字母不相同的个数 
    				for(int j=0,k=0;L[i].elem[j]!='\0';j++,k++){//逐个字母比较
    					if(L[i].elem[j]!=S.elem[k]){
    					count++;
    				    } 
    				    if(count>=2)  break;//没有可以修改的字典单词 
    			    }
    			    if(count<=1)  cout<<" "<<L[i].elem; 
                }
            }
            cout<<endl; 
        } 
    }
    //后序递归输出二叉排序树 
    void Print(BiTree T){
    	if(T!=NULL){
    		Print(T->lchild);
    		Print(T->rchild);
    		cout<<T->data<<" ";
    	}
    }
    //建立二叉排序树
    BiTree CreateBitree(char *a,BiTree T){
    //参数:字典字符串,二叉排序树
    //返回值:二叉排序树 
    	if(T==NULL){//为空,放入一个字符串作为根结点进行后续比较 
    		T=new BiTNode;
    		strcpy(T->data,a);
    		T->lchild=T->rchild=NULL; 
    	}
    	else if(strcmp(a,T->data)>0)//大于根结点,置为右子树 
            T->rchild=CreateBitree(a,T->rchild);
    	else
    	    T->lchild=CreateBitree(a,T->lchild);
        return T;
    } 
    int main(){
    	while(cin>>L[n].elem){
    		if(L[n].elem[0]=='#') break;//输入字典完毕
    		L[n].length=strlen(L[n].elem);
    		T=CreateBitree(L[n].elem,T);
    		n++;
    	}
    	Print(T);
    	cout<<endl;
    	SqList S;
    	while(cin>>S.elem){
    		if(S.elem[0]=='#')  break;
    		S.length=strlen(S.elem);
    		protect(S);
    	}
    }  
    
    展开全文
  • 2020数据结构课程设计之单词检查单词检查(Ⅰ)- 顺序表实现 许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的...
  • txt格式 只有英文词库 包含一些复数 过去式 做单词检查还不错
  • 问题 J: 单词检查(Ⅱ)- 二叉排序树实现 许多应用程序,如字处理软件,邮件客户端等,都包含了单词检查特性。单词检查是根据字典,找出输入文本中拼错的单词,我们认为凡是不出现在字典中的单词都是错误单词。不仅...
  • 更有解释、翻译、词典以及英文写作辅助等实用功能来辅助用户快速改正错误,能极大地提高用户写作准确率的成文质量,是非常理想的英文写作和校对助手以及单词检查软件,除此之外易改还提供1Checker Word插件,支持MS ...
  • 上下文单词检查器可提供更好的建议 拼写错误的类型 必须理解,识别候选人是否是拼写错误是一项艰巨的任务。 您可以从研究论文中看到以下引文: 拼写错误大致分为非单词错误(NWE)和真实单词错误(RWE)。 如果...
  • C语言---单词检查

    千次阅读 2018-06-10 19:25:03
    且全为小写字母,按照字典序由小到大排列,每个单词独占一行),编写程序利用该单词表对某一英文文章(保存在当前目录下的另一个文件in.txt中)进行单词正确性检查,若该英文文章中出现的单词(只有连续字母组成)...
  • 关闭eclipse或MyEclipse的单词检查

    千次阅读 2016-07-02 14:07:08
    在编写xml文档的时候,有些命名不符合规则就会有红色波浪线提示,是在是有点烦人,那么如何把MyEcplise的语法拼写检查给关闭呢?window-preference-General-Editor-TextEditors-Spelling 面板里有个Enable spelling...
  • 单词拼写检查

    2017-05-17 21:31:20
    单词拼写检查 输入 n个单词(n 输入m个单词,查找是否在单词库里 输出 无法查找见的单词的个数 输入  5 apple be love down 3 up down bee 输出 1 #include #include #include using ...
  • 主要介绍了Python实现单词拼写检查,本文讲解了单词拼写检查的一些知识并给出两种实现方法,需要的朋友可以参考下
  • 单词拼写检查的程序

    2019-01-06 00:47:04
    可以使用该程序进行单词的拼写检查,该程序可以很好的进行检查工作。
  • 英文单词拼写检查

    2013-12-11 09:23:07
    基于贝叶斯框架的单词拼写检查代码,只实现了识别小写
  • Visual C++单词拼写检查器,以命令提示符窗口的形式运行,运行后你可以根据提示输入一段英文字母,本程序会检查你输入的单词拼写是否正确,暂时只支持英文单词检查,不支持中文拼写检查。 运行环境:Windows/...
  • 纯英文单词表 13W单词及其变形 适用于做拼写检查
  • 前两天,有位同事提到她做过的一个功能,在线实现单词检查,若单词有误,给出建议清单,她使用的方法是下载单词库,转为xml,在VB.NET中使用查找与loop,并且要支持多语种。我当时听到,觉得应该有更快的方法,就查...
  • 1.快速拼写检查程序,即检查英语文章的单词,列出所有错误单词的位置(java实现)以前上大学时的课程设计,代码写得很乱,没怎么注释,请多多原谅。由于那时候对java不熟,词典搜索自己写了个二叉排序搜索完成,比较...
  • IDEA关闭单词拼写检查

    千次阅读 2018-06-08 15:02:49
    IDEA里面的单词拼写检查是默认开启的,有时候看着不是单词的拼写下面出现波浪线感觉很难受,可以关闭单词拼写如下图将typo后面的勾去掉即可。
  • python的单词拼写检查库pyenchant,支持python3,版本3.1.1,wheel安装包
  • 相当详尽的文档,完全测试过的程序,指导文档尤其具有借鉴意义,仔细研究的话会有很大的收获!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,309
精华内容 58,123
关键字:

单词检查