首页 > 其他分享 >问题 I: 单词检查(Ⅰ)- 顺序表实现

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

时间:2024-06-23 08:58:50浏览次数:28  
标签:顺序 word 检查 int Dic 单词 phrase data

问题 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"。如果单词是错误的,那么接着输出’:‘,如果字典中有建议修改单词,则按照字典中出现的先后次序输出所有的建议修改单词(每个前面都添加一个空格),如果无建议修改单词,在’:'后直接换行。

在这里插入图片描述

样例输出

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

实现过程

顺序表
1)什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表:可动态增长的数组,要求数据是连续存储的

2)顺序表的定义
1、静态顺序表:使用定长数组存储元素

缺陷:给小了不够用,给大了可能浪费,非常不实用

#define N 10
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType array[N];  //定长数组
	size_t size;          //有效数据个数
}SeqList;

2、动态顺序表:使用动态开辟的数组存储元素

动态顺序表可根据我们的需要分配空间大小
size 表示当前顺序表中已存放的数据个数
capacity 表示顺序表总共能够存放的数据个数
typedef int SLDataType; //类型重命名,后续要存储其它类型时方便更改

typedef int SLDataType; //类型重命名,后续要存储其它类型时方便更改

typedef struct SeqList
{
	SLDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数
	size_t capacity;  //容量大小
}SeqList;

以上顺序表定义原文链接:https://blog.csdn.net/weixin_48025315/article/details/119778068

此题实现过程:
1.定义顺序表用于存储单词及长度
2.创建单词表并计算其长度
3.判断长度相同的两个单词是否相等
4.删除字母进行比对
5.添加字母进行比对
6.改变字母进行比对
7.得出结果right or wrong

下面是对代码的详细解析:

  1. 头文件和命名空间

    • 包含 <iostream><cstdio><cstring> 头文件。
    • 使用 using namespace std; 来避免在标准库类型和函数前加 std::
  2. 单词结构体定义

    • 定义了一个结构体 word,包含一个字符数组 data 用于存储单词,和一个整型 length 用于存储单词的长度。
  3. 全局变量

    • Dic 是一个大小为 10001 的 word 类型数组,用作单词字典。
    • num 是一个整型变量,用作单词在字典中的下标。
  4. 创建单词表函数 creat

    • 使用 cin 读取单词直到遇到 # 符号,将每个单词存储到 Dic 数组中,并更新 num
  5. 判断单词是否相等函数 judge

    • 接收两个 word 类型的参数,判断它们是否完全相同。
  6. 删除字母进行对比函数 found1

    • 尝试删除一个字母来比较输入的单词 x 和字典中的单词 y 是否相等。
  7. 添加字母进行对比函数 found2

    • 尝试添加一个字母来比较输入的单词 x 和字典中的单词 y 是否相等。
  8. 改变字母进行对比函数 found3

    • 尝试改变一个字母来比较输入的单词 x 和字典中的单词 y 是否相等。
  9. 检查单词函数 found

    • 接收一个 word 类型的参数 phrase
    • 遍历字典,使用 judge 函数检查 phrase 是否与字典中的单词完全相同。
    • 如果 phrase 的长度比字典中的单词长度多1、少1或相等,分别调用 found1found2found3 函数进行检查。
    • 输出检查结果。
  10. 主函数 main

    • 首先调用 creat 函数创建单词表。
    • 然后读取用户输入的单词,直到遇到 # 符号。
    • 对每个输入的单词调用 found 函数进行检查,并输出结果。
  11. 程序结束

    • 返回 0,表示程序正常结束。

代码逻辑分析

  • 这段代码实现了一个基于控制台的单词检查工具,它可以检查用户输入的单词是否正确,或者是否可以通过简单的字母变换(添加、删除、替换)来形成正确的单词。
  • 它首先读取一个单词列表到字典中,然后读取用户输入的单词,通过一系列的函数来判断单词的正确性。

改进建议

  • 对用户输入进行检查,确保不会超过 word 结构体中 data 数组的大小。
  • 为了提高代码的健壮性,可以考虑使用异常处理来捕获和处理潜在的错误。

部分实现

定义单词及长度 ,创建单词字典 ,初始化单词下标

typedef struct word{
    char data[15];
    int length=0;
}word;//定义单词及长度 
word Dic[10001];//创建单词字典 
int num=0;//初始化单词下标

2.创建单词表并计算其长度

void creat(){//创建单词表 
    while(cin>>Dic[num].data){
    if(Dic[num].data[0]=='#')break;
    Dic[num].length=strlen(Dic[num].data);//计算单词长度 
       num++;
    } 
}

3.判断长度相同的两个单词是否相等

int judge(word x,word y){
  int flag=1;
  for(int i=0;i<x.length;i++)if(x.data[i]!=y.data[i]){
      flag=0;break;
  }
  return flag;
}

4.删除字母进行比对

void found1(word x,word y){
  word phrase1=x;
   int flag=1;int count=0;
      for(int i=0,j=0;i<y.length;i++,j++){
          if (count>1)break;
          if(phrase1.data[j]!=y.data[i]){
              j--;count++;
          }
      }
  if(count==1){
  cout<<" "<<x.data;flag=0;
  }
}

5.添加字母进行比对

void found2(word x,word y){
      word phrase2=y;int flag=1;int count=0;
      for(int i=0,j=0;i<x.length;i++,j++){
          if (count>1)break;
          if(phrase2.data[j]!=x.data[i]){
              j--;count++;
          }
      }
  if(count==1){
  cout<<" "<<x.data;flag=0;
  }
}

6.改变字母进行比对

void found3(word x,word y){
      word phrase3=y;int flag=1;int count=0;
      for(int i=0,j=0;i<x.length;i++,j++){
          if (count>1)break;
          if(phrase3.data[j]!=x.data[i]){
          count++;
          }
      }
  if(count==1){
  cout<<" "<<x.data;flag=0;
  }
}

7.将上述所有函数组合到一起实现单词的检查并得出结果

void found(word phrase){
  int flag=1;
  for(int i=0;i<num&&flag==1;i++){
      if(flag){
          if(phrase.length==Dic[i].length)if(judge(phrase,Dic[i])) {
              cout<<phrase.data<<" is correct";flag=0;
          }
      }
  }
   if(flag)cout<<phrase.data<<":";
  if(flag)for(int i=0;i<num;i++){
  if(phrase.length-1==Dic[i].length)found1(Dic[i],phrase);
          if(phrase.length+1==Dic[i].length)found2(Dic[i],phrase);
              if(phrase.length==Dic[i].length)    found3(Dic[i],phrase);
  }   cout<<endl;
   
}

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
 
typedef struct word{
    char data[15];
    int length=0;
}word;//定义单词及长度 
 
 
word Dic[10001];//创建单词字典 
 
 
int num=0;//初始化单词下标
 
 
 void creat(){//创建单词表 
     while(cin>>Dic[num].data){
     if(Dic[num].data[0]=='#')break;
     Dic[num].length=strlen(Dic[num].data);//计算单词长度 
        num++;
     } 
 }
  
  
 int judge(word x,word y){//判断长度相同的两个单词是否相等 
    int flag=1;
    for(int i=0;i<x.length;i++)if(x.data[i]!=y.data[i]){
        flag=0;break;
    }
    return flag;
 }
  
  
 void found1(word x,word y){//删除字母进行对比 
    word phrase1=x;
     int flag=1;int count=0;
        for(int i=0,j=0;i<y.length;i++,j++){
            if (count>1)break;
            if(phrase1.data[j]!=y.data[i]){
                j--;count++;
            }
        }
    if(count==1){
    cout<<" "<<x.data;flag=0;
    }
 }
  
  
 void found2(word x,word y){//添加字母进行对比 
        word phrase2=y;int flag=1;int count=0;
        for(int i=0,j=0;i<x.length;i++,j++){
            if (count>1)break;
            if(phrase2.data[j]!=x.data[i]){
                j--;count++;
            }
        }
    if(count==1){
    cout<<" "<<x.data;flag=0;
    }
 }
  
  
 void found3(word x,word y){//改变字母进行对比 
        word phrase3=y;int flag=1;int count=0;
        for(int i=0,j=0;i<x.length;i++,j++){
            if (count>1)break;
            if(phrase3.data[j]!=x.data[i]){
            count++;
            }
        }
    if(count==1){
    cout<<" "<<x.data;flag=0;
    }
 }
  
  
 void found(word phrase){
     //将上述所有函数组合到一起实现单词的检查
    int flag=1;
    for(int i=0;i<num&&flag==1;i++){
        if(flag){
            if(phrase.length==Dic[i].length)if(judge(phrase,Dic[i])) {
                cout<<phrase.data<<" is correct";flag=0;
            }
        }
    }
     if(flag)cout<<phrase.data<<":";
    if(flag)for(int i=0;i<num;i++){
    if(phrase.length-1==Dic[i].length)found1(Dic[i],phrase);
            if(phrase.length+1==Dic[i].length)found2(Dic[i],phrase);
                if(phrase.length==Dic[i].length)    found3(Dic[i],phrase);
    }   cout<<endl;
     
 }
  
  
int main(){
    creat();
    word phrase;
    while(cin>>phrase.data){
        if(phrase.data[0]=='#')break;
        phrase.length=strlen(phrase.data);
        found(phrase);
    } 
    return 0;
}

标签:顺序,word,检查,int,Dic,单词,phrase,data
From: https://blog.csdn.net/weixin_50950742/article/details/139788024

相关文章

  • 【数据结构】顺序表实操——通讯录项目
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • def init(parameterlist),是用来创建类的方法,其中parameterlist是方法所需要传入的属性
    问题描述:definit(parameterlist),是用来创建类的方法,其中parameterlist是方法所需要传入的属性参数。请问参数是按照顺序排列的吗?问题解答:是的,在Python中,__init__(self,parameterlist)方法的参数是按照顺序排列的。这意味着在创建类的实例时,传递给构造函数的参数需要按......
  • 使用Kubesec检查YAML文件安全
    目录一.系统环境二.前言三.Kubesec简介四.使用Kubesec检查YAML文件安全五.总结一.系统环境本文主要基于Kubernetes1.22.2和Linux操作系统Ubuntu18.04。服务器版本docker软件版本Kubernetes(k8s)集群版本CPU架构Ubuntu18.04.5LTSDockerversion20.10.14v1.22.2......
  • 数据结构:为什么说链表是顺序表的升级版(c语言实现)
    前言:  我们在之前的几篇文章中详细的讲解了顺序表的特点,增删改查操作和动态顺序表的优点,并使用顺序表的底层结构实现了通讯录项目,似乎顺序表是一个非常完美的数据结构,它可以实现按照需求实现增删查改,对内存的控制也较为合理,空间都是在需要时手动开辟的。但是顺序表真的完......
  • 在Linux中,keepalive工作原理是什么及如何做到健康检查?
    Keepalived是一个用于Linux系统的高可用性解决方案,它主要通过VirtualRouterRedundancyProtocol(VRRP)协议来实现网络服务的高可用性和故障转移。其核心功能包括故障切换和健康检查,广泛应用于LVS负载均衡集群以及其他需要高可用性的场景。下面是Keepalived工作原理及......
  • 1v1视频源码,你知道如何实现多线程的顺序执行吗?
    1v1视频源码,你知道如何实现多线程的顺序执行吗?1、在子线程中通过join()方法指定顺序通过join()方法使当前线程“阻塞”,等待指定线程执行完毕后继续执行。举例:在线程thread2中,加上一句thread1.join(),其意义在于,当前线程2运行到此行代码时会进入阻塞状态,直到线程thread1执......
  • c/c++ 数据结构 顺序栈
    本文是以c语言的风格编写的c++程序。栈的特点:先进后出,后进先出。顺序栈的结构定义:一个数组以及一个”指针“(不是真正的指针,而是位置变化的说明)#include<stdio.h>#include<malloc.h>#defineMaxsize20typedefstruct{ intdata[Maxsize]; inttop;}SqStack; 初......
  • 【CSS in Depth2精译】1.1.4 源码顺序
    解决层叠冲突的最后一环叫做源码顺序,有时又称为出现顺序(orderofappearance)。如果其他判定规则均一致,则样式表中后出现的、或者在页面较晚引入的样式表声明,将最终胜出。也就是说,可以通过控制源码出现的顺序来给示例中的特色链接添加样式。如果两个存在冲突的选择器优先......
  • 华为电脑BIOS设置系统启动顺序
        最近在华为电脑上装了Windows和Ubuntu双系统后,由于安装失误,导致每次开机后都会进入grub界面。    为了正常进入Windows和Ubuntu系统,在开机进入grub界面前,可以按F12进入bootmanager界面,在此界面下可以选择需要启动的系统。(请原谅我使用手机拍摄屏幕的方......
  • Java-英语字符串进行单词分割
    (摘自头歌)任务描述将一段英语字符串进行单词分割。相关知识需要掌握:如何将字符串进行分割。String.split()拆分字符串lang包String类的split()方法publicString[]split(Stringregex)publicString[]split(Stringregex,intlimit)//limit参数控制模式应用的次数,因......