测试五-文学研究助手

71实验五文学研究助手实验指导书一、实验目的帮助学生熟练掌握串的基本操作，并通过文学研究助手的设计过程深刻领会串的基本应用方法和堆存储结构的实现技术。二、实验内容文学研究人员需要统计某篇英文文章中某些单词出现的次数和位置，编写一个实现这一目标的文字统计程序，称为“文学研究助手”。假设需要统计的单词集合称为特定单词集。英文文章是由回车符（‘\n’）隔开的一行一行的文本字符串组成，位置用单词所在行的行号来表示。则程序的功能是统计特定单词集中每个单词在指定文件中出现的次数和出现的行号。基本要求：1、单词集和文件名均由用户从键盘终端输入。2、单词都是由某种类型字符的序列组成，如字母字符序列（区分大小写）、数值常数（整数或小数型实数）字符序列。3、界符（分隔符（‘（’，‘）’，‘，’等）、运算符等（‘+’，‘-’，‘*’，‘/’等）可独立构成单词。4、文本文件中的单词在文件中不垮行出现，它或出现在行首，或用空格隔开，或由单词的构成规则区分（如由字母构成的单词，遇到非字母字符即表示单词结束，数值单词由数字开头，遇到不是小数点或非数字字符则表示单词结束），或由界符隔开。5、若一个单词在同一行出现多次只输出一个行号。6、输出结果为：单词、出现的次数、出现的位置（行号）。四、实验原理1、假设（1）一个单词的昀大长度不超过20个字符。（2）文本文件中一行的单词数不超过16个。可以用宏常量定义为：#defineMAXLEN20#defineMAXNUM162、单词的结构描述一个单词可以用其一个字符数组和字符串的长度来表示，其结构类型定义如下：typedefstruct{72charch[MAXLEN];//单词字符串intsize;//单词长度}Sequence;3、单词的存储表示单词采用堆式存储结构，即分配一块较大的存储空间作为堆的存储空间，待分析的特定单词集放入堆空间中，文本文件中分解出的一行单词也放入堆空间中。由于一行单词分析完后就没有用途了，所以可以释放一行单词所占用的存储空间。堆的存储空间可定义为：#defineMAXSIZE1000typedefstruct{charstores[MAXSIZE];intfreep;//当前可用空间开始位置}HeapSpace;由于堆操作在该程序中是昀频繁的操作，可以把表示堆空间的变量定义为全程变量：HeapSpacesp;单词通常用其在堆存储空间中的存储映像来表示。一个单词的值尽管在堆空间中，如果丢失了其存储映像，也就相当于丢失了单词。单词在存储空间中的存储映像可以定义为：typedefstruct{intstadr;//单词在堆空间中的开始位置intlen;//单词长度}WordType;4、单词集的存储表示在实验中，待分析的单词构成一个单词集。文本文件中的一行作为一个基本分析单位，一行中的单词也构成一个单词集。统计特定单词在文本文件中出现的次数和位置（行号）的基本方法是：用文本文件中分解出的一行的每个单词去查找待分析的特定单词集，若该单词出现在特定单词集中，则该单词的统计次数加1，并记录下出现的行号。为了便于单词查找，可以把单词集组织成一个按从小到大升序排列的有序表。由于单词的个数不固定，用链式存储结构来实现有序表。有序表的每个结点表示一个单词的存储映像。有序表结点结构定义如下：typedefWordTypeElemType;typedefstructNodeType{ElemTypedata;structNodeType*next;}NodeType,*LinkType;73有序表结构定义如下：typedefstruct{LinkTypehead;//有序表头指针LinkTypetail;//有序表尾指针intsize;//有序表结点个数}OrderList;假设待统计的特定单词集为：ifelseforreturnvoidintchar其存储结构及存储映像如图5-1所示。单词在有序表中的顺序为：charelseforifintreturnvoid012345678910111213141516171819202122232425ifelseforreturnvoidintchar5、统计分析结果的表示按照要求，程序的核心功能是要统计特定单词在文本文件中出现的次数和位置。因此次存放分析结果的数据结构中既要指明统计的是哪个单词，又要记录出现的次数和位置。要统计的单词已放防在堆空间中，其存储映像已由单词有序表表示。一个单词出现的位置的记录与出现的次数有关，但事先是无法估计一个单词在一个文本文件中药出现多少次，因此用链表结构来记录单词出现的位置是合适的选择，即一个单词在文件中出现的位置用一个单链表来记录。假定，要统计的特定单词从键盘输入，不超过一行，即单词个数不超过MAXNUM。为了表示分析结果的上述信息，又方便管理，可以将所有分析单词信息和链表的头指针信息共同构成一个向量结构。链表结点结构的定义：typedefstructNode{intelem;//被测单词在文件中的行号structNode*next;//指向下一个行号结点的指针02246396154NULLL1932247图5-1单词集有序表存储结构示意图74}Node,*Link;链表头结点结构的定义：typedefstruct{WordTypedata;//被测试的单词的存储映像intcount;//在文件中出现的次数Linknext;//记录出现的所有行号的链表头指针}HeadNode;链表头结点向量的存储结构定义如下：typedefHeadNodeResultType[MAXNUM];对应单词头结点在向量结构中的位置（下标）与其在存储映像有序表中结点出现的序号相同。在上面例子中，其分析结果数据的存储结构如图5-2所示。在图5-2中，第三个元素头结点的值为（6，3，4）表示在堆中从下标6开始的连续3个字符对应的单词“for”在文件文件中出现4次，其位置分别是第14行，第11行，第9行和第7行。6、统计分析的总体思路（1）从键盘输入待统计分析的特定单词集，将单词放入堆存出空间中，并建立单词集的存储映像有序表。224324263402119359621543651^32^7^141194^5^92117132319^181412^图2分析结果数据存储结构示意图75（2）从键盘输入待分析的文本文件名并打开文件。（3）顺序分析文本文件的每一行，直到文件结束。对每一行：①识别出该行的每个单词，把单词放入堆空间中，并建立单词存储映像有序表。②用该行分解出的单词与特定单词集中单词进匹配，记录下匹配的结果。匹配的结果可用下面数据类型的变量记录：typedefstruct{inteqelem[MAXNUM];intlast;}EqelemList;数组eqelem中存放的是单词在特定单词集在有序表中结点序号，该序号与分析结果链表的表头结点向量的序号一致，表示要在对应链表中插入一个表示当前分析行的节点。整数last表示在处理过程中要把匹配的单词结点的序号放入eqelem数组的位置，昀终表示有多少个单词获得匹配。③建立结点记录相应单词出现的行号，插入到相应链表中，并累加统计次数。（3）输出统计结果数据。输出要统计的单词、单词在文件中出现的次数、单词出现的位置（行号）的集合。四、实现1、基本功能(3)输入待统计分析的单词集并建立有序表(4)输入待分析的文件名并打开文件(5)统计分析文件(6)输出分析结果2、辅助功能（1）菜单选择：选择要操作的基本功能。（2）定义新单词：把一个新单词放入堆中。（3）复制单词：把单词的存储映向信息赋给另一个同类型变量。（4）单词比较：比较两个单词的大小（5）输出单词：在显示终端上显示单词的所有字符（单词在堆中无结束标制）（6）结点生成：生成一个有序表的节点（申请结点空间并未结点赋值）（7）有序表初始化：建立有序表头结点并初始化有序表指针。（8）撤销有序表：释放有序表的所有结点空间。（9）有序表定位：在有序表中查找指定值的结点。（10）有序表结点插入：把一个新结点插入到有序表的制定结点后面。（11）表匹配：确定一个表（从表）中元素是否在另一个表（主表）中，并记录匹配76元素在主表中的位置（序号）。（12）判表空：判断一个有序表是否为空表（13）判断行结束：判断下一个字符是否为回车符。（14）读单词：从文件中读取一个单词。（15）处理文件行：从文件中读一行单词，放入堆中并建立存储映像有序表（16）初始化统计结果表：用待统计单词集初始化统计结果表（17）撤销统计结果链表：释放匹配的行信息结点的空间。3、程序结构该程序由22个函数组成，其中主函数1个，基本功能函数4个，辅助功能函数17个。函数间的调用关系图5-3所示。mainnemuInitializationmatchNewWordPrintWordInitListGetAWordInsertAfterLocateElemfeolnListEmptyListCompareMakeNodeDestroyListInputWordOutResultCopyWordWordCmpExtractWordInitRListFreeResult图5-3程序结构图776、函数说明（1）主函数main功能：根据菜单选择确定要操作的内容：输入待统计分析的单词集并建立有序表输入待分析的文件名并打开文件统计分析文件输出分析结果退出系统（退出前要释放动态申请的存储空间）（2）菜单选择函数：menu功能：构造功能菜单，并选择下一步要操作的功能。格式：intmenu(void)参数：无参数。返回值：1～5中的一个序号。可供选择的功能如下：1--Inputmatchedwords输入用于统计的单词集2---Inputmatchfile输入需要分析的文件3---Procesfile分析文件4---OutputResult输出分析结果5---Quit表示退出系统，结束程序的运行（3）输入统计单词函数：InputWord功能：输入用于统计的单词集，建立堆存储映像格式：voidInputWord(OrderList*pt)参数：OrderList*pt—记录单词集存储映像的有序表指针返回值：无（4）文件初始化函数：Initialization功能:从键盘输入待统计分析的文件名，并打开文件格式：statusInitialization(FILE**fr)参数：FILE**fr—返回指向文件的指针返回值：1—文件初始化成功0—文件初始化失败（5）文件统计分析函数：match功能：统计分析单词集匹配情况格式：statusmatch(FILE*f,OrderListpat,ResultTypers)参数：FILE*f—待分析的文件指针OrderListpat—指定单词集（存储映像）有序表78ResultTypers—统计分析结果链表头结点向量返回值：1—分析成功0—分析失败（6）统计结果输出函数：OutResult功能：输出统计分析结果格式：voidOutResult(ResultTypers,intn)参数：ResultTypers—统计分析结果链表头结点向量intn—指定统计分析单词数目返回值：无（7）定义新单词函数：NewWord功能：把一个新单词放入堆空间中，建立新单词的存储映像格式：statusNewWord(WordType*nw,Sequencecha)参数：WordType*nw—指向新单词存储映像的指针Sequencecha—需放入堆中的单词数据变量返回值：1—操作成功0—操作失败（8）复制单词函数：CopyWord功能：把指定的单词的存储映像复制到另一个存储单元中格式：voidCopyWord(WordType*nw,WordTypeoldw)参数：WordType*nw—需要复制到的存储单元指针WordTypeoldw—指定的单词存储映像返回值：无（9）比较单词函数：WordCmp功能：比较两个单词的大小格式：intWordCmp(WordTypewd1,WordTypewd2)参数：WordT