文学研究助手(数据结构课程设计)

1文学研究助手一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。二、需求分析：1、文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输入；2、“单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；3、待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；5、测试数据：文本文件为本次实习中的word.txt:待统计的词集：hesheithastoherecannotiswas三、概要设计：拟采用对两个有序表进行相互比较的策略进行“单词匹配”。程序中将涉及下列三个抽象数据类型：1.定义“单词”类型：ADTAword{数据对象：D={Si|Si∈标准c字符串集合,i=1,2,3,…….,n,n≥0}数据关系：R1={Si-1,Si}|Si-1,Si∈D,i=1,2,3,…..,n}基本操作：NewWord(WordType*nw,Sequencecha)初始条件：cha为字符序列；操作结果：生成一个其值为给定字符序列的单词；WordCmp(WordTypewd1,WordTypewd2)初始条件：单词wd1和单词wd2已存在；操作结果：若wd1wd2，则返回-1；若wd1=wd2，则返回0；若wd1wd2，则返回1；2PrintWord(WordTypewd)初始条件：单词wd已存在；操作结果：在计算机终端上显示单词wd；}ADTAWord2.定义有序表类型：ADTOrderList{数据对象：D={Si|Si∈AWord,i=1,2,3,…….,n,n≥0}数据关系：R1={Si-1,Si}|Si-1,Si∈D,Si-1S,i=1,2,3,…..,n}基本操作：InitList(OrderList*L)操作结果：构造一个空的有序表；DestroyList(OrderList*L)初始条件：有序表L已存在；操作结果：销毁L的结构，并释放所占空间；LocateElem(OrderListL,ElemTypee,LinkType*q)初始条件：有序表L已存在；操作结果：若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值FRUE；否则q指示第一个大于e的元素的前驱的位置，并返回函数值FALSE；InsertAfter(OrderList*L,LinkTypeq,LinkTypes)初始条件：有序表L已存在，q指示L中一个元素；操作结果：在有序表L中q指示的元素之后插入元素s；ListCompare(OrderListLa,OrderListLb,EqelemList*s)初始条件：有序表La和Lb已存在；操作结果：以s返回其中相同元素；}ADTOrderList3.定义单词文本串文件类型如下：ADTTextString{数据对象：D={Si|Si∈标准c字符集,i=1,2,3,…….,n,n≥0}；数据关系：D中字符被“换行符”分割成若干行，每一行的字符间满足下列关系：R1={Si-1,Si}|Si-1,Si∈D,i=1,2,3,…..,n}基本操作：3Initialization(FILE**fr)初始条件：文件fr已存在；操作结果：打开文件fr，设定文件指针指向文件中第一行第一个字符；GetAWord(FILE*f,Sequence*st)初始条件：文件f已打开；操作结果：从文件指针所指字符起提取一个“单词st”；ExtractWord(FILE*f,OrderList*ta)初始条件：文件f已打开，文件指针指向文件f中某一行的第一个字符；操作结果：提取该行中所有单词，并构成单词的有序表ta，本操作结束时，文件指针指向文件f中下一行的第一个字符；match(FILE*f,OrderListpat,ResultTypers)初始条件：文件f已打开，文件指针指向文件f中第一个字符；pat为包含所有待查询单词的有序表；操作结果：rs为查询结果；}ADTTextString4.本程序包含四个模块：1）主程序模块：主函数设计如下intmain(){输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和位置；输出测试结果；}；2）单词单元模块-------实现单词类型；3）有序表单元模块--------实现有序表类型；4）单词文本串文件单元模块------实现文本串文件类型；各模块间的调用关系如下：主程序模块文本文件单元模块有序表单元模块-单词单元模块4四、详细设计1、主程序中的宏定义：#defineMAXSIZE1000//字符空间的最大容量#defineMAXLEN20//单词的最大长度#defineMAXNUM16//一行中单词最多个数#defineFALSE0#defineTRUE12、存储结构/***堆结构的定义*/typedefstruct{charstores[MAXSIZE];intfreep;/*当前可用空间开始位置*/}HeapSpace;HeapSpacesp;/***单词数据类型定义*/typedefstruct{//单词在堆中的位置描述intstadr;/*单词在对空间中的开始位置*/intlen;/*单词长度*/}WordType;typedefstruct{//单词描述charch[MAXLEN];/*单词字符串*/intsize;/*单词长度*/}Sequence;/***有序表类型定义*/typedefWordTypeElemType;typedefstructNodeType{//单词有序表结点定义ElemTypedata;structNodeType*next;}NodeType,*LinkType;typedefstruct{//单词有序表定义LinkTypehead;/*有序表头指针*/LinkTypetail;/*有序表尾指针*/intsize;/*有序表结点个数*/}OrderList;5/***记录一行中匹配成功单词在目标词汇表中的位置*/typedefstruct{inteqelem[MAXNUM];/*单词在目标词汇表中的位置*/intlast;/*匹配成功单词的个数*/}EqelemList;/***文件测试相关的数据类型定义*/typedefstructNode{//单词在文件中的位置intelem;/*被测单词在文件中的行号*/structNode*next;/*指向下一个行号结点的指针*/}Node,*Link;typedefstruct{//单词统计分析记录结构定义WordTypedata;/*被测试的单词*/intcount;/*在文件中出现的次数*/LinkNext;/*记录出现的所有行号的脸表头指针*/}HeadNode;/***文本文件测试结果记录定义*/typedefHeadNodeResultType[MAXNUM];typedefintstatus;3、主要算法设计：/*---------------------与单词相关的函数---------------------*//*------------------------------------------------------------------*//*定义新单词函数*//*功能：把新单词放入堆中*//*参数：WordType*nw--单词描述信息指针*//*Sequencecha--单词信息*//*返回值：操作成功与否的状态信息*//*0--操作失败，空间不足；1--操作成功*//*--------------------------------------------------------------*/statusNewWord(WordType*nw,Sequencecha){inti,k;if(sp.freep+cha.size=MAXSIZE){printf(HeapFull!\n);getchar();return0;6}else{i=sp.freep;sp.freep=sp.freep+cha.size;for(k=0;kcha.size;k++)sp.stores[i+k]=cha.ch[k];nw-stadr=i;nw-len=cha.size;return1;}}/*------------------------------回到最初空间-------------------*/voidNewLength(OrderListrs){intm=0;LinkTypep,q;p=rs.head-next;while(p){if(m=p-data.stadr){m=p-data.stadr;q=p;}p=p-next;}sp.freep=m+q-data.len;}/*------------------------------------------------------------------*//*复制单词信息函数*//*功能：把一个单词信息复制到另一个变量中*//*参数：WordType*nw--新单词描述信息指针*//*WordType*oldw--旧单词描述信息指针*//*返回值：无*//*----------------------------------------------------------------*/voidCopyWord(WordType*nw,WordTypeoldw){nw-stadr=oldw.stadr;nw-len=oldw.len;}/*------------------------------------------------------------------*//*单词比较函数*//*功能：比较堆中两单词的大小*//*参数：WordTypewd1--第一个单词描述信息*//*WordTypewd2--第二个单词描述信息*/7/*返回值：-1--小于；0--等于；1--大于*//*--------------------------------------------------------------*/intWordCmp(WordTypewd1,WordTypewd2){intk,si,sj,m;si=wd1.stadr;sj=wd2.stadr;for(k=0;k=wd1.len&&k=wd2.len;k++){m=fabs((float)(sp.stores[si+k]-sp.stores[sj+k]));if(m!=0&&m!=32)break;if(k==wd1.len||k==wd2.len)break;}if(wd1.len==wd2.len){if(k==wd1.len)return0;elseif(sp.stores[si+k]sp.stores[sj+k])return1;elsereturn-1;}elseif(wd1.lenwd2.len){if(k==wd1.len)return-1;elseif(sp.stores[si+k]sp.stores[sj+k])return1;elsereturn-1;}else{if(k==wd2.len)return1;elseif(sp.stores[si+k]sp.stores[sj+k])return1;elsereturn-1;}}/*------------------------------------------------------------------*//*打印单词函数*//*功能：打印堆中一个单词*//*参数：Wor