C语言实现的基于查找表的单词检索软件

BoyMeetsGirl

发布日期: 2019-03-01 09:40:19 浏览量: 1661
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1 引言

1.1 课题背景与意义

数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课,牢固掌握数据结构的基础知识,熟练地运用数据结构的思想与技术方法解决实际应用问题是本课程学习的基本任务与目标。而课程设计是实现这一学习目标的重要环节和组成部分。通过课程设计的联系,学生加深对数据结构知识的理解,牢固掌握其应用方法,并灵活地解决一定实际问题,增强和提高综合分析问题与解决问题的能力。

1.1.1 课题背景

当今社会,大数据的研究与发展突飞猛进,这同样也推动了搜索引擎的进步,对于习惯了百度、谷歌等搜索工具的我们来说,查找与搜索看起来不是一件很难的事,但是要知道搜索引擎的发展也经历了一段艰难的历程。在单词查找和在线翻译上,现在比较成熟的有有道词典和百度翻译等。抛弃传统的搜索查找思想,用大数据的思维研究单词查找软件,不失为顺应时代潮流的做法。

1.1.2 课题意义

作为计算机专业的学生,应该跟上信息时代的变化节奏。以大数据为基础的查找统计算法算是必修课,必须掌握才能适应环境。随着数据的井喷,数据的处理软件也同样如雨后春笋,层出不穷。以单词检索为例,在线的检索网站就有百度等,检索软件更是有金山词霸、有道词典等,还包括现今流行的记单词软件、驾考宝典、打车软件等,都与单词检索软件有着相似的算法思想。因此,在课程设计中研究检索算法是很有必要的,是为了将来的发展进行一次知识储备,或者说一次演习。

1.2 国内外研究现状

1.2.1 国内现状

我国全文检索技术的研究起步于20世纪80年代,但发展速度较快。汉字激光照排技术的发明和使用,为全文数据库的开发奠定了基础。至此我国全文数据库进入大规模研制时期基于汉语自身特点,我国学者已提出了自己的全文检索模式——单汉字无标引全文检索系统和全文后控检索系统,并不断深入研究构造新的全文检索模式。

1.2.2 国外现状

全文检索这种情报检索技术最早出现于20世纪50年代的美国。80年代以来,英文全文检索发展得较为迅速和完善,如今已成为国外文字型信息检索的主流。主要有分词技术和自动标引技术等。发展趋势上,智能检索、知识检索和基于XML的信息检索将成为将来检索技术的主流。

1.3 课程设计的主要研究工作

人工智能是很目前热门的一个研究方向。站在用户的角度来考虑,我们的单词检索软件也应该尽量智能。但是由于水平有限,并不能做到真正的智能,而只能利用现有的知识,把界面做得尽可能地友好。

在功能实现方面,主要分为读取电子书、创建查找表、保存查找表和查找等模块。要求准确无误地读取电子书的内容,并以此为根据建立查找表,查找表又分为静态查找表和哈希表两种方式,都要完整地实现,在此过程中,选择合适的数据结构相当重要,这与我们数据结构课程紧密相关。保存查找表和恢复查找表是相辅相成的,只实现其中一个,另一个就没有意义,因此必须同步实现。在单词查找上,分别用静态查找表和哈希表实现查找,将结果完整地反馈给用户。此外还可以根据自己的想法增加一些有意义的功能。

2 系统需求分析与总体设计

2.1 系统需求分析

用户提供一个电子书文档,软件要能够打开并读取电子书的内容,根据书中的单词,创建查找表。在创建表的过程中要分别创建静态查找表和哈希表。创建表以后还要能够遍历输出表的内容,以及销毁表。

以上这些都只是查找表框架的构建,系统最重要的功能是单词查找。由于一个单词有多个关键字:单词、页码、行数、出现次数,故可以根据这些关键字分别查询单词,也可以用其中若干个关键字组合来查询,所以能够实现多种方式查询,具体实现步骤较为灵活。查询之外还需要能够增删单词,以及对单词的某些关键字进行修改,修改以后可以调用查询功能进行验证。

上述是必须实现的功能,此外还可以自行增加功能模块。比如可以选择以适当的方式保存查找表,具体方式自由选择,但要求重启系统后能够根据保存的文件恢复查找表。还可以按照单词出现次数等关键字进行统计,比如统计出现频率最高的100个单词等,可以自由发挥。

2.2 系统总体设计

根据查找表的存储结构,可将系统主要分为两大块:静态查找表部分和哈希表部分。

2.2.1 共有功能

两个部分有很多功能都是相同的,只是在内存和算法上有些许不同。共有的功能有:创建查找表、保存查找表至文件、从文件导入查找表、单词查找、销毁查找表、遍历查找表。其中各模块具体功能为:

  • 创建查找表是根据用户输入的电子书名称,以只读方式打开相应电子书,读取其中的单词,当创建静态查找表时则直接存入静态表中,创建哈希表时则需要先计算单词的哈希函数值,再存入相应的位置。文件读取完毕,查找表也就创建完毕。

  • 保存查找表是指将已经创建的查找表保存至文件中,下一次打开系统时不必再次创建查找表,而可以直接从文件导入。将查找表的结点信息按照一定的顺序依次存入文件,然后再用同样的规则读入文件,达到恢复查找表的目的。保存和导入函数配套使用,方可完成这一功能。

  • 销毁查找表就是将查找表所占的内存空间全部释放,由于静态查找表和哈希表在存储上稍有不同,因此销毁函数也有区别,但大体原理相同。

  • 遍历查找表把查找表中的所有单词遍历输出,原则上要输出每个单词的所有出现次数,等于把电子书的原文输出,但是考虑到电子书有几万个单词,全部输出工作量太大,因此只输出所有不重复的单词,以及该单词在文中的出现次数。

  • 单词查找用户输入需要查找的单词,系统在查找表中找到该单词并输出该单词所有出现次数以及每次出现的页码和行号。在查找时,静态查找表采用遍历顺序表的方式查找,而哈希表则先根据系统的哈希函数计算出单词对应的哈希函数值,在表中相应位置找到该单词并输出。

2.2.2 静态查找表特有功能

静态查找表采用线性表形式存储,因此排序后可以进行二分查找,并用来与静态查找进行对比,分析两种查找方式的性能优劣。为了保留原有的静态查找表,在排序前,先将原有的静态表复制一份,在新建的查找表中进行排序和二分查找操作。用计时器计算查找所用的时间,通过时间长短来衡量查找方法的效率。

2.2.3 哈希表特有功能

哈希表特有功能为:插入哈希表和删除哈希表。

  • 插入哈希表,用户输入想要插入的单词以及单词出现的页码和行号,无论原来的表中是否存在该单词,都将进行插入,但是会提示用户该单词是否已经存在于哈希表中。

  • 删除哈希表,可以选择删除单词的所有出现位置和特定出现位置。选择前者时,用户只需输入待删除的单词,系统会删除该单词的所有结点。若选择后者,则还需要输入待删除位置的页码和行号。删除以后可以调用查询功能进行验证。

2.2.4 附加功能

在静态查找表和哈希表模块中都可以自行增加功能。由于两种查找表的算法思想基本相似,所以只在静态查找表模块自行设计了功能。分别为:单词出现次数统计、子串查找、按给定页码和行数遍历、在给定页码中查找、单词替换。

  • 单词出现次数统计:在静态查找表的基础上,按照单词在全文的出现次数进行统计。用户输入想要统计的个数,系统根据用户输入,统计输出出现次数前若干位的单词。

  • 子串查找,类似于单词查找,相当于广义的单词查找,遍历静态查找表,将所有单词中出现了待查找子串的单词按照出现次数输出。

  • 按给定页码和行数的遍历,相当于侠义的遍历查找表,在遍历查找表的基础上给定了限制条件只遍历输出特定的页或者行。

  • 在给定页码中查找,相当于缩小了查找范围的单词查找功能,具体的查找位置由用户输入。

  • 单词替换,是在单词查找的基础上,找到了单词所在位置以后,将单词用输入的单词替换。

综上所述,可以用流程图将系统总体设计表示如下图:

3 系统详细设计

3.1 有关数据结构的定义

电子书读入时需要存储的关键字有:单词、页码、行号、单词总出现次数等,所以无论是静态查找表还是哈希表的数据结点中都必须有这些元素。下面分别讨论静态查找表和哈希表的数据结构定义。

3.1.1 静态查找表

初始化静态查找表的思路是:用一定长度的顺序表来存储单词,单词第一次出现时先将单词、页码和行号等信息存放到顺序表中,第二次以及更多次出现时,在顺序表后接单链表,存储新的出现情况,此时不必再存储单词,而只需要存储页码和行号。如果不考虑节省空间,可以用同一个数据结点实现这一功能,只是单链表中用来存储单词的存储空间浪费了。

为了提高结点中的空间利用率,为单链表单独定义一个数据类型,相比顺序表的数据结构类型少了存储单词的字符数组,还少了单词出现次数的变量,因为单词总的出现次数只需要存储一次,即存储在顺序表中,在单链表中不必要再次存储。数据结构定义用表格表示如下:

顺序表结点结构变量,名称Elemtype1:

变量名 类型 功能 备注
word char* 存储单词
page int 页码
line int 行号
times int 出现次数
next Elemtype1 指向下一同类结点
next2 Elemtype2* 指向单链表的指针

单链表中结点结构变量,名称Elemtype2:

变量名 类型 功能 备注
page int 页码
line int 行号
next Elemtype2* 指向下一结点

两种数据结构关系可用图表示,其中elemtype1是静态表,构成一级存储结构,初始化表时的长度为5500,假如不够用,则一次增加500个存储单元。读入新单词时从第0个单元开始寻找未被占用的结构,找到以后将单词和页码等存入,并将出现次数置为1,当后来再次出现该单词时,在相应的一级存储结构后面创建二级结点,在其中存储出现的页码和行号,并将一级结构中的出现次数变量加一。即一个单词对应一个一级结构,一个单词的多次出现对应一个二级单链表。

3.1.2 哈希表

系统采用的哈希函数是,将单词所有字母的ASCⅡ码相加,再平方,然后对5483取余。由于初始化的表长是5500,小于5500的最大质数是5483,因此使用5483当作取余的除数,这样可以使单词在表中近似均匀分布。

由于会有多个单词对应同一个存储位置,所以要用一定的方法处理冲突,本系统使用了链地址法,即一个地址对应一个哈希函数值,所有具有同一个哈希函数值的单词被存储到该地址后接的单链表中,一个单词对应一个结点。有多个单词有同一个哈希函数值时,这些单词就构成了一个单链表。在二级单链表的后面还要接三级单链表,来表示一个单词的多次出现。

从数据结构上来说,哈希表与静态查找表没有太大区别,要存储的信息都相同,只是为了处理冲突,又加了一级链表,相比静态查找表的二级存储结构,哈希表采用三级存储结构,数据结构类型与静态查找表的类型完全相同。

顺序表结点和一级链表结点结构变量相同,名称Elemtype1:

变量名 类型 功能 备注
word char* 存储单词
page int 页码
line int 行号
times int 出现次数
next Elemtype1 指向下一同类结点
next2 Elemtype2* 指向单链表的指针

第三极链表中结点结构变量,名称Elemtype2:

变量名 类型 功能 备注
page int 页码
line int 行号
next Elemtype2* 指向单链表下一结点

数据结构之间的关系如图,第一级存储结构对应各个哈希函数值,具有同一哈希函数值的单词在第一个结构中在同一个位置,他们都接在第一级结构的后面形成第二级的单链表,如单词1-1到1-m。每一个单词又可能出现多次,此时将多次出现接在第二级单链表的后面形成第三级的单链表。

3.2 主要算法设计

3.2.1 创建静态查找表

这是静态查找表一切有关算法的基础,必须先初始化静态查找表才能进行后续功能。系统不断地从电子书中读取字符,每当碰到空格或者换行符表示着一个单词的结束,此时遍历整个静态查找表中已经存在的单词,如果找到与该单词相同的单词,则将其接到已经存在单词的后面形成单链表;若不存在,则将单词添加到线性表中。上述过程执行完一个单词的操作,然后继续读取字符,存储下一个单词,直到读到文档的结束。

创建静态查找表的算法思想流程图如图:

3.2.2 保存静态查找表&恢复静态查找表

仅仅保存静态查找表是相当简单的,只需要将所有结点都存入文件即可,但是我们还要考虑到读取文件并恢复查找表的需要,所以需要用一定的规则存储查找表,恢复查找表时以同样的规则读取才能完整地恢复。

先将表头结点存入文件,因为表头中存储了静态表的长度,单词总数以及不重复的单词总数,这些指标都是读取文件的依据,假如没有表头结点,后面的读取都无法进行。然后将静态表一次性存入,其中存储了所有不重复的单词。最后,遍历静态表,以及将各个单词对应的单链表存入文件。至此,保存查找表结束。

恢复静态查找表,打开存储查找表的文件,先以表头结点的格式读取一个结构,结构中有后续需要读取的静态表长度。然后一次性读取表头中静态表长度变量值对应的静态表长度,比如表长为5000,则从文件中读取5000个静态表结点。然后文件中剩下的都是单链表结点。遍历静态表,假如其Elemtype2指针不为空,说明原来的静态表中该位置接有单链表,所以需要继续从文件中读取结点接到该位置的后面形成单链表,直到读取的结点中Elemtype2指针为空,说明该单链表结束,此时可以移向静态表的下一结点,再次为其恢复单链表,直到文件中的内容读取完毕。

保存单链表的算法设计流程图如图:

恢复静态查找表的思想与保存静态查找表思路基本相同,只需要将写文件操作改成读文件操作即可。

3.2.3 静态查找

根据用户输入的单词,遍历静态查找表,假如找到就将单词的所有出现次数输出,未找到则返回false。算法思想流程图如图:

3.2.4 二分查找

将静态查找表按照字典序排序以后,即可进行二分查找,假定表长为length,首先low=0,high=length,mid=(low+high)/2,访问第mid个结点,假如与给定单词相等则返回;若不想等,假如该单词大于给定单词,说明给定词在该词前面,所以high=mid-1,否则low=mid+1。当low>high时说明未找到,返回false。算法思想流程图如图:

3.2.5遍历静态查找表

遍历查找表与静态查找的思想类似,甚至更简单,只需要遍历静态表,将每个位置对应单词及其关键字输出即可。考虑到电子书单词量有接近10万,将每个单词的每次出现都输出会使屏幕上信息太多,反而不便于查看,因此每个单词只输出一次,并输出其出现次数,不将每次出现都遍历。

遍历静态查找表的算法思想流程图:

3.2.6 销毁静态查找表

销毁静态查找表首先遍历静态表,将其后所跟的单链表依次销毁,最后再销毁静态表,算法流程图如图:

3.2.7 初始化哈希表

与哈希表有关的操作与静态查找表都很相似,区别在于,首先要计算单词的哈希函数值才能确定其存储位置,后续操作与静态查找表就基本相同了。

初始化哈希表的思路是,从文件读取字符并存入中间变量,当读到空格或者换行符时表示一个单词结束,应该将其存入哈希表。存入之前需要对单词求哈希函数值,然后进入表中对应位置的单链表中查找是否已经存在该单词,假如已经存在,就在已经存在的二级单链表上添加一个三级单链表结点表示该单词的本次出现;假如不存在,则在二级单链表上添加一个结点表示该单词的首次出现。算法思想与静态查找表基本相同,流程图可以参照图4的静态查找表流程图,不再赘述。

3.2.8 保存&恢复哈希表

保存与恢复函数不能单独存在,必须先保存再恢复,两者配套使用。恢复查找表时用与保存查找表相同的规则,即可完整地恢复查找表。

  • 保存哈希表时,先将表头结点存入文件,其中记录了静态表的表长。然后将静态表一次性存入文件,静态表的每一个存储单元对应一个哈希函数值,哈希函数值相同的单词都以二级单链表的形式接在该位置的后面。然后遍历静态表,将每个位置的二级单链表存入文件,最后遍历二级单链表,将所有二级单链表后跟的三级单链表存入文件。

  • 恢复哈希表时,打开存储文件,先读取表头结点,其中存储了静态表的长度。然后根据静态表的长度读取length个长度的结点作为静态表,这一步恢复了原有的静态表。然后要恢复第二级的单链表:遍历已经恢复的静态表,假如静态表中Elemtype1指针不为空,说明原有哈希表中该位置后接有单链表,所以从文件中读取一个结点恢复单链表,直到读取的结点Elemtype1指针为空,说明该单链表结束,可以进入静态表中下一位置继续上述操作。恢复了二级单链表以后,恢复三级单链表的思路基本相同,从文件中一次读取一个结点,接到二级单链表的后面,直到文件的结束,至此,静态表和二级、三级单链表都恢复成功。

3.2.9 哈希查找

哈希查找,根据用户输入的单词,计算单词的哈希函数值,根据函数值进入静态表中对应的位置。由于采用了链地址法处理冲突,所以要遍历二级链表才能确定表中是否存在该单词。假如在二级链表中找到该单词,则遍历单词对应结点后跟的三级链表,输出单词的每一次出现页码和行数。理论上最坏的情况下,需要遍历的二级单链表长度为n,找到以后需要将所有出现次数输出,时间复杂度也为n,所以查找的时间复杂度为n,输出时间复杂度为n,总的复杂度为n^2。算法思想流程图如图:

3.2.10 遍历哈希表

遍历哈希表总共分为二级遍历,先遍历静态表,在静态表的每一个位置,都要进入其后链接的二级单链表,二级单链表中的每个结点都要遍历输出其中存储的单词以及该单词的出现次数。实际上哈希表总共有三级结构,但是只遍历了两层,原因与遍历静态查找表时一样:总的单词数太多,每个单词只输出一次。算法思想与遍历静态查找表相似,只是多了一层循环。算法思想流程图如图11:

3.2.11 销毁哈希表

销毁哈希表,需要先销毁链表再销毁静态表,假如先销毁静态表,则会因为找不到静态表链接的单链表而无法释放单链表结点所占空间。遍历静态表,对每个位置,进入其后的二级单链表;对单链表的每个结点,连同其后的三级链表看作一个整体,从第一个结点开始销毁,销毁时要注意必须先用中间变量保存待销毁结点的后继结点,否则在销毁下一结点时会找不到,导致程序崩溃。销毁完第一个二级结点极其后继三级链表,继续销毁第二个结点及其后继链表,以此类推,直到销毁所有的单链表。最后,只剩下静态表占有存储空间,只需一次性销毁静态表即可。算法思想与销毁静态查找表相似,流程图可参考图,不再赘述。

3.2.12 插入哈希表

插入哈希表是根据用户输入的信息进行插入,用户输入待插入的单词以及想要插入的页码和行数。系统在哈希表中查找该单词,假如找到,就在该单词对应三级链表中添加一个结点存储插入单词的页码和行号。假如未找到,说明原本不存在该单词,需要在二级链表中新增结点存储该单词。算法调用了哈希查找函数,可以简化不少步骤,总的时间复杂度为n^2。算法流程图如图:

3.2.13 删除哈希表

删除哈希表是指删除哈希表中的特定结点,系统提供了两种删除功能:第一是输入一个单词,删除该单词的所有出现次数,即删除以后该单词不复存在;第二种是删除单词的特定出现位置,这一功能需要用户输入单词所在的页码和行号。两种功能都需要调用哈希查找函数,先根据用户输入的单词找到单词在哈希表中的位置,然后在进行删除结点的操作,两种功能的算法思想基本相同,只是前者删除所有的结点,后者只删除特定的结点。插入哈希表的流程图,虽然插入和删除是截然不同的操作,但是思路没有太多不同。

4 系统实现与测试

4.1 系统实现

4.1.1 软硬件环境

系统在windows10系统,intel i5系列CPU上实现,使用Code Blocks16.01生成可执行文件,代码的可移植较好,可以在其他类型的编译器以及系统下运行。

4.1.2 定义数据类型

数据类型的定义在3.1节中已经说明,静态查找表和哈希表共用两种数据类型Elemtype1和Elemtype2,以及表头结点Sqlist,Elemtype1中有单词、页码、行数、出现次数、后继指针等数据项,Elemtype2中只有页码、行数、后继指针数据项,表头中存有静态表的长度以及单词总数。具体的定义参照附录中的代码。

4.1.3 系统中的函数

  • 创建静态查找表LoadTxt_Static:输入参数为表头指针、电子书名称、电子书文件指针。从电子书中读取所有单词,以此为基础创建静态查找表。

  • 保存静态查找表SaveStatic:输入参数为表头指针,待保存文件名,待保存文件指针。函数将表头指针所指的静态查找表按一定规则以此存入文件,其中文件名由用户输入。

  • 恢复静态查找表RestoreStatic:输入参数为表头指针,待导入文件名,待导入文件指针。函数是与保存函数配合使用的,上一步中保存的文件在这里被用于恢复查找表,函数用一定的规则从文件读取数据,恢复原有的查找表。

  • 静态查找SearchStatic:输入参数为表头指针和待查找的单词。遍历静态查找表,逐个比较是否为待查找的单词,找到则输出,未找到则返回false提示用户。

  • 静态查找表排序SortStatic:输入参数为表头指针。功能为对静态查找表按照字典序进行升序排序,这是二分查找之前的必要步骤。

  • 二分查找SearchBinary:输入参数为表头指针和待查找的单词。实现的功能与SearchStatic完全相同,只是算法思想不同,需要先对查找表进行排序,排序以后用折半查找法查找,其他操作与SearchStatic相同。

  • 遍历静态查找表TraverseStatic:输入参数为表头指针。函数遍历输出静态表中所有存储单元对应的单词和出现次数。

  • 销毁静态查找表DestroyStatic:输入参数为表头指针。函数遍历静态查找表的所有单链表并逐一释放其存储空间,最后释放静态表的存储空间,完成静态查找表的销毁。

  • 子串查找SearchStr:输入参数为表头指针,待查找的子串。函数类似于静态查找函数SearchStatic,都是根据输入进行查找,将查找结果输出。但是该函数查找的是查找表中所有含有待查找子串的单词,比SearchStatic范围更大。

  • 单词替换ReplaceWord:输入参数为表头指针,被替换的单词,以及新单词。函数通过调用查找函数,在静态查找表中找到被替换的单词的位置,然后将该位置的单词换成新单词。

  • 根据出现次数排序SortTimes:输入参数为表头指针。根据单词的出现次数按照降序次序排列。这是单词次数统计功能的先决条件。

  • 单词出现次数统计TopWords:输入参数为表头指针和待统计的单词个数n。根据用户想要统计的单词数n,输出已经按照出现次数排序的静态表中前n个单词,极为电子书中出现次数前n位的单词。

  • 初始化哈希表LoadTxt_Hash:与初始化静态查找表类似,参数也相同,从电子书中读取单词创建哈希表。

  • 保存哈希表SaveHash:参数与保存静态查找表函数相同,功能也相似,将创建好的哈希表存入文件。

  • 恢复哈希表RestoreHash:参数与恢复静态查找表函数相同,功能相近,从文件中恢复哈希表。

  • 哈希查找SearchHash:参数与静态查找函数相同,功能相同,根据输入的单词在表中查找并输出结果,不同的是这里是在哈希表中查找。

  • 插入哈希表InsertHash:输入参数为表头指针,待插入的单词,待插入的页码和行数。函数调用哈希查找函数在哈希表中找到单词所在位置并将新的出现位置插入表中。

  • 删除哈希表DeleteHash:输入参数为表头指针,待删除单词,待删除的页码和行数。函数与插入哈希表函数一样先查找单词位置再进行结点删除。

  • 遍历哈希表TraverseHash:参数与遍历静态查找表相同,功能也相同,将表中所有单词遍历输出,不同的是这里遍历的是哈希表。

  • 销毁哈希表DestroyHash:参数和功能都与销毁静态查找表相同,将表中所有结点所占的存储空间释放,不同的是这里销毁的是哈希表。

4.1.4 函数间调用关系

经过很多尝试也未能用一个流程图来很好地展现各个函数之间的关系,因为很多函数都是独立的,只有少数函数之间存在调用关系,这样会使得流程图各元素之间过于松散,联系太少,所以借用了系统总体设计的流程图,并加以改进,在各个功能模块后添加该模块所调用的函数,假如模块使用了多个函数,则按照调用的顺序给出。系统的函数调用关系如图:

4.2 系统测试

4.2.1 常用软件测试方法

常见的软件测试方法有:α测试、β测试、可移植性测试、随机测试、国际化测试、静态测试和动态测试等。α测试是一个用户在开发环境下的测试;β测试是多个用户在一个或多个用户的实际使用环境下的测试;可移植性测试是测试软件是否可以成功移植到指定软硬件平台上;随机测试指没用书面测试用例的测试;国际化测试用来检测软件的国际化支持能力,保证软件在世界不同地区都可以运行;静态测试指测试不运行的部分;动态测试是指通过运行软件来检验软件的动态行为和运行结果的正确性。

4.2.2 系统测试方案

系统主要包含静态查找表和哈希表两大块,两部分在功能上基本相同,只是在数据结构定义和算法实现上有些许不同,在测试时主要选取静态查找表的算法模块,这并不失一般性。此外静态查找表的部分附加功能也将进行测试。具体的功能模块为:

创建静态查找表、保存静态查找表、恢复静态查找表、静态查询、二分查找、遍历静态查找表、销毁静态查找表、子串查找、单词出现次数统计。

为了操作简便,测试的顺序如下:

创建静态查找表->保存静态查找表->退出系统->重新启动系统->恢复静态查找表->静态查找->二分查找->遍历静态查找表->子串查找->单词出现次数统计->销毁静态查找表;

系统测试所需的电子书与系统可执行文件在同一个目录下,电子书名称为Flipped,不需要输入后缀名。电子书总次数约60000,能够满足系统需要。

4.2.3 功能测试

  • 创建静态查找表
    • 模块功能:输入电子书名称,从电子书中读取单词创建静态查找表。创建成功则提示成功,文件不存在则提示文件打开失败。
    • 正常测试用例:选择功能1,创建静态查找表,输入文件名flipped,运行结果如下图所示。
    • 分析:将电子书复制到word文档中显示的单词数为57602个,考虑到word与本系统的计数规则可能有些许不同,某些字符没有算作单词,本系统读取的59134个单词与word的误差在可接受的范围内,可以认为系统读取电子书成功。
    • 异常测试用例:输入一个不存在的文件名,运行结果如图:
    • 分析:输入的文件名不存在时提示文件打开失败,运行结果正确。

  • 保存静态查找
    • 模块功能:将已经创建的静态查找表存入文件。
    • 测试:选择功能2,保存静态查找表,待保存文件名为static,运行结果:

  • 恢复静态查找表
    • 功能分析:从文件中读取并恢复静态查找表
    • 测试:先退出系统,然后重新打开系统,选择功能3,从文件static恢复查找表,运行结果:
    • 分析:恢复静态查找表成功,可以认为模块功能得到实现,但是还无法严格地验证,可以在后续步骤中验证导入的查找表能够执行一切功能。

  • 静态查找
    • 模块功能:输入待查找的单词,输出该单词的所有出现次数
    • 正常测试用例:查找单词“during”,本系统和word软件运行结果:
    • 分析:系统查找结果与word查找结果都是出现6次,满足设计目标。
    • 异常测试用例:输入单词“holiday”,系统和word运行结果:
    • 分析:对于表中不存在的单词,会提示用户该单词不存在,满足设计目标。

  • 二分查找
    • 模块功能:功能与静态查找相同,只是算法思想不同,平均时间复杂度较低。
    • 测试用例:同样查找单词“during”,运行结果:
    • 分析:二分查找是用来与静态查找对比查找效率的,理论上静态查找的时间复杂度为n,而二分查找的时间复杂度为logn,优于静态查找。由于下载了几次微秒计时器都不可用,所以最终被迫选择了毫秒计时器,精确度不太高。以单词during为例,静态查找时间为1ms,二分查找时间为0ms,抛开偶然性不说,这可以说明二分查找用时少于静态查找,但是计时不够精确的问题得不到解决,说服力不是很强。至于用时的偶然性问题,在系统测试过程中大量地查找比较之后发现,绝大多数情况下都是二分查找更优。当然,要更具有说服力,只能找到可用的微秒计时器。不过在理论上可以认为系统满足设计目标。

  • 遍历静态查找表
    • 模块功能:遍历输出表中所有不重复的单词以及出现次数。
    • 测试:选择功能6,运行结果:
    • 分析:优于单词个数太多,屏幕显示不下,所以只能截取一部分结果,可以认为模块功能达标。如果要严格验证遍历的结果,可以将遍历输出的单词一一在word文档中进行检索,可以发现查找结果数与系统输出的单词出现次数相同。

  • 按子串查找
    • 模块功能:输入字符串,查找输出表中所有含有该字符串的单词。
    • 测试:输入字符传“dur”,系统运行结果:
    • 分析:系统输出了含有字符串“dur”的三个单词:during、endurance和procedures,三个单词共计出现9次;用word查找的结果同样是9次,可认为程序满足设计要求。

  • 单词出现次数统计
    • 模块功能:用户输入一个整数n,系统输出表中出现次数前n位的单词。
    • 测试:选择功能10,统计单词出现次数。输入50,系统运行结果:
    • 分析:统计结果符合我们的常识,排名前列的是“i”、“the”、“and”和“to”这样最常见的代词、介词和冠词,可以认为程序满足设计要求。

  • 销毁静态查找表
    • 模块功能:销毁已经存在的静态查找表,假如表不存在则提示用户。
    • 正常测试用例:选择功能7,销毁查找表,运行结果如图:
    • 分析:两次调用综合可知静态表销毁成功,程序功能满足设计目标。之所以把销毁表放在最后检验,是因为销毁表以后不方便测试其他功能,而需要重新创建表,比较麻烦。

重新调用功能7,运行如图:

至此,测试计划中的功能测试完毕,剩余哈希表的所有功能未测试。哈希表的函数功能和测试方法都基本上和静态查找表相同,在实现测试系统时已经测试过多次,在此不再测试。

5 总结与展望

5.1 全文总结

对自己的工作做个总结,主要工作如下:

  • 采用静态表和单链表相结合的方式解决了单词的存储问题,其中静态表方便排序,单链表非常灵活,方便增删,比较熟练地运用了数据结构课程中静态表和单链表的知识。

  • 第一次尝试自主地写出了二分查找的代码并且运行成功,以往都是从课本上了解二分查找的思想,这次实践以后更深刻地理解了算法的精髓。

  • 在哈希函数的选择上,考虑了多种方法,比如各字符的ASCⅡ码相加,但是大多数单词字母个数相近,这样相加的结果很集中,无法使哈希表中的元素均匀分布,因此选择将其平方再取余,能有使结果较为均匀。

  • 单词查找以及子串查找算法的实现锻炼了对字符函数以及查找方法的运用。

  • 读取文件看起来很简单,但是操作起来也容易出错,一开始总是会有漏洞。而且,读取单词并且创建查找表的过程要用到多重循环,每个循环中又要考虑多种情况,比如读入换行符、读取连续的多个空格等等,要做到每种情况都不遗漏,是相当困难的。在经过多次观察代码以及编译器调试以后,程序基本能够处理所有类型的字符,保证单词准确无误地读入。这个过程出不得差错,因为读取文件是后续所有操作的基础,假如读取的单词有误,查询和遍历这些功能也就失去了意义。写好创建查找表函数的时候感觉像做成了一件大事。

  • 保存和恢复查找表也和读取电子书的函数一样,看起来简单实现起来有点难。当一个功能得到实现的时候,可能会觉得理所当然就该是那样。但是功能实现背后真的花了很大功夫。保存查找表可以有很多方式,但是为了后面恢复查找表的时候方便,必须认真考虑保存的顺序。在内存中的查找表各个结点的指针都指向确定的位置,但是在保存到文件以后,指针的值就失去了意义,造成恢复查找表的困难。所以能够利用的就是null指针,因为它在存入文件以后也仍然是null,在恢复查找表时可以用null作为标志,每读到null所在结点就表示一个单链表结束。

  • 做这些东西并没有用到多少新知识,但是有了很多新收获,哪怕是很常规的读取文件、链表操作,都可能让人想不清楚,而真正弄清楚了一个问题的时候,感慨和收获是非常大的。

5.2 工作展望

在今后的研究中,围绕着如下几个方面开展工作:

  • 系统的人机交互界面不够友好,以后将尽量使界面更加友好

  • 没能使用图形化界面,曾尝试使用图形库写界面,但最终还是选择了较为熟练的C语言,导致界面很低端,以后需要学习方便写图形界面的语言。

  • 在排序算法上仍然使用了较原始的冒泡排序法,对于快速排序法一类的算法不太熟练,应该学习使用先进的排序算法。

  • 附加功能的设计上没能做得特别好,往后需要多发挥创造力,不过说到底更重要的是提高编程的能力。

上传的附件 cloud_download 基于查找表的单词检索软件.7z ( 1.10mb, 32次下载 )
error_outline 下载需要8点积分

发送私信

抓不住的东西,伸手都显得多余

10
文章数
13
评论数
最近文章
eject