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

1、回 1;1文学研究助手一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。二、需求分析：1、 文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输 入；2、单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；3、 待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、 在计算机终

2、端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出 现两次的只输出一个行号；5、 测试数据：文本文件为本次实习中的word.txt :待统计的词集：he she it has to here can not is was三、概要设计：拟采用对两个有序表进行相互比较的策略进行“单词匹配”。程序中将涉及下列三个抽象数据类型：1.定义“单词”类型：ADT Aword(数据对象：D=Si | Si 标准 c 字符串集合,i = 1,2,3,；,n；n法0数据关系：R1= | Si-1,Si D,i = 1,2,3,.,n基本操作：NewWord(WordType *nw,Sequenc

3、e cha)初始条件：cha 为字符序列；操作结果：生成一个其值为给定字符序列的单词；WordCmp(WordType wd1,WordType wd2)初始条件：单词 wd1和单词 wd2 已存在；操作结果：若 wd1wd2 ,则返PrintWord(WordType wd)2初始条件：单词 wd已存在；操作结果：在计算机终端上显示单词wd;ADT AWord2. 定义有序表类型：ADT OrderList(数据对象：D=(Si | Si AWord,i = 1,2,3,-：,n；n 0数据关系：R1= | Si-1,Si D,Si-1S, i = 1,2,3,.,n基本操作：InitLis

4、t(OrderList *L)操作结果：构造一个空的有序表；DestroyList(OrderList *L)初始条件：有序表L已存在；操作结果：销毁 L的结构，并释放所占空间；LocateElem(OrderList L,ElemType e,LinkType *q)初始条件：有序表L已存在；操作结果： 若有序表 L中存在元素 e,则 q指示 L中第一个值为 e的元素的位置,并返回函数值 FRUE;否则 q 指示第一个大于 e 的元素的前驱的位置， 并返回函数值 FALSE ;InsertAfter(OrderList *L,LinkType q,LinkType s)初始条件：有序表L已存

5、在，q指示 L中一个元素；操作结果：在有序表L 中 q指示的元素之后插入元素s；ListCompare(OrderList La,OrderList Lb,EqelemList *s)初始条件：有序表La和 Lb 已存在；操作结果：以 s返回其中相同元素；ADT OrderList3.定义单词文本串文件类型如下：ADT TextString数据对象：D=Si | Si 标准 c 字符集,i = 1,2,3,.,n, nA 0；3数据关系：D中字符被“换行符”分割成若干行，每一行的字符间满足下列关系：R1= | Si-1,Si D,i = 1,2,3,.,n基本操作:Initialization

6、(FILE *fr)初始条件：文件 fr已存在；操作结果：打开文件 fr,设定文件指针指向文件中第一行第一个字符；GetAWord(FILE *f,Sequence *st)初始条件：文件 f 已打开；操作结果：从文件指针所指字符起提取一个“单词st”；ExtractWord(FILE *f,OrderList *ta)初始条件：文件 f 已打开，文件指针指向文件 f中某一行的第一个字符；操作结果：提取该行中所有单词，并构成单词的有序表ta,本操作结束时，文件指针指向文件 f 中下一行的第一个字符；match(FILE *f,OrderList pat,ResultType rs)初始条件：文

7、件 f 已打开，文件指针指向文件 f中第一个字符；pat 为包含所有待查询单词的有序表；操作结果：rs为查询结果；ADT TextString4.本程序包含四个模块：1)主程序模块：主函数设计如下int main ( ) 输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和位置；输出测试结果；2)单词单元模块实现单词类型；3)- 有序表单元模块实现有序表类型；4)单词文本串文件单元模块-实现文本串文件类型；各模块间的调用关系如下：45四、详细设计1、主程序中的宏定义:#defineMAXSIZE1000字符空间的最大容量#defineMAXLEN20/单词的取大长度#d

8、efineMAXNUM16/一行中单词最多个数#defineFALSE0#defineTRUE12、存储结构*堆结构的定义*/typedef struct(char storesMAXSIZE;int freep;/*当前可用空间开始位置 */HeapSpace;HeapSpace sp;/*单词数据类型定义*/单词在堆中的位置描述/*单词在对空间中的开始位置 */*单词长度*/单词描述/*单词字符串*/*单词长度*/*有序表类型定义*/typedef WordType ElemType;typedef struct NodeType(单词有序表结点定义ElemType data;struct

9、 NodeType *next;NodeType,*LinkType;typedef struct(单词有序表定义LinkType head;/*有序表头指针*/LinkType tail;/*有序表尾指针*/int size;/*有序表结点个数*/OrderList;typedef struct(int stadr;int len;WordType;typedef struct(char chMAXLEN;int size;Sequence;/*6/*记录一行中匹配成功单词在目标词汇表中的位置*/typedef structint eqelemMAXNUM; /*单词在目标词汇表中的位置 *

10、/int last;/*匹配成功单词的个数*/EqelemList;/*文件测试相关的数据类型定义*/typedef struct Node单词在文件中的位置int elem;/*被测单词在文件中的行号*/struct Node *next;/*指向下一个行号结点的指针*/Node,*Link;typedef structWordType data;int count;Link Next;HeadNode;/*文本文件测试结果记录定义*/typedef HeadNode ResultTypeMAXNUM;typedef int status;3、主要算法设计:/*- 与单词相关的函数 -*/*

11、-*/*定义新单词函数*/*功能：把新单词放入堆中*/*参数：WordType *nw-单词描述信息指针*/*Sequence cha-耳词信息*/*返回值：操作成功与否的状态信息*/*0-操作失败，空间不足；1-操作成功*/*-*/ status NewWord(WordType *nw,Sequence cha) int i,k;if(sp.freep+cha.size=MAXSIZE)printf(Heap Full!n);getchar();return 0;else(i=sp.freep;/单词统计分析记录结构定义/*被测试的单词*/*在文件中出现的次数*/*记录出现的所有行号的脸表

12、头指针*/7sp.freep=sp.freep+cha.size;for(k=0;kstadr=i;nw-len=cha.size;return 1;/*- 回到最初空间- */void NewLength(OrderList rs)(int m=0;LinkType p,q;p=rs.head-next;while(p)(if(mdata.stadr)m=p-data.stadr;q=p; p=p-next;sp.freep=m+q-data.len;/*- */*复制单词信息函数*/*功能：把一个单词信息复制到另一个变量中*/*参数：WordType *nw-新单词描述信息指针*/* Wo

13、rdType *oldw- I日单词描述信息指针*/*返回值：无*/*- */ void CopyWord(WordType *nw,WordType oldw)nw-stadr=oldw.stadr;nw-len=oldw.len;/*- */*单词比较函数*/*功能：比较堆中两单词的大小*/*参数：WordType wd1-第一个单词描述信息*/* WordType wd2-第二个单词描述信息*/8/*-*/int WordCmp(WordType wd1,WordType wd2)(int k,si,sj,m;si=wd1.stadr;sj=wd2.stadr;for(k=0;k=wd1

14、.len&ksp.storessj+k)return 1; elsereturn -1;else if(wd1.lensp.storessj+k)return 1; elsereturn -1;else(if(k=wd2.len)return 1;elseif(sp.storessi+ksp.storessj+k)return 1; else return-1;/*-*/*打印单词函数*/*功能：打印堆中一个单词*/*参数：WordType wd-单词描述信息*/*返回值：无*/*-*/void PrintWord(WordType wd)(int i;for(i=0;idata.st

15、adr=e.stadr;(*p)-data.len=e.len;(*p)-next=NULL;return TRUE;/*-*/*有序表初始化函数*/*功能：申请头结点，初始化有序表*/*参数：OrderList *L-有序表指针*/*返回值：TRUE-初始化成功；FALSE-初始化失败*/*-*/ statusInitList(OrderList *L)ElemType wd;wd.len=0;if(MakeNode(&(L-head),wd)L-tail=L-head;L-head-next=NULL;L-size=0;return TRUE;elseL-head=NULL;ret

16、urn FALSE;10/*-*/*撤销有序表函数*/*功能：释放有序表所有结点，撤销有序表*/*参数：OrderList *L-有序表指针*/*返回值：无*/*-*/ voidDestroyList(OrderList *L) (LinkType p,q;p=L-head;while(p)(q=p;p=p-next;free(q);L-head=L-tail=NULL;/*-*/*有序表查找函数*/*功能：确定给定单词 e在有序表中的位置*/*参数：OrderList L-有序表*/*ElemTypee-给定要查找的数据 e*/*LinkType *q-有序表结点指针*/*查找成功，q 指向

17、具有 e 值的结点*/*查找失败，q 指向小于 e 的结点*/*返回值：int型，1-查找成功；0-查找失败*/*-*/ statusLocateElem(OrderList L,ElemType e,LinkType *q)(LinkType pre,p;p=L.head-next;while(p)(if(WordCmp(p-data,e)=0)*q=p;return TRUE;if(WordCmp(p-data,e)=-1)*q=p;p=p-next;return FALSE;*/* 功能：在制定结点 q 后插入一个结点 s*/* 参数：OrderList *L-有序表指针*/*LinkT

18、ype q-指定结点指针*/*LinkType s-待查入结点指针*/* 返回值：无*/*/*有序表插入函数*/11/*-*/void InsertAfter(OrderList *L,LinkType q,LinkType s) (if(L-head&q&s)s-next=q-next;q-next=s;if(L-tail=q) L-tail=s;L-size+;/*- */*表匹配函数*/*功能：把 Lb 表中匹配 La 表成功的元素放入 s 表 */*参数：OrderList La-存放统计单词的有序表*/*OrderList Lb-存放待匹配单词的有序表*/*Eqele

19、mList *s-存放匹配成功单词信息表指针*/*返回值：无*/*- */ voidListCompare(OrderList La,OrderList Lb,EqelemList *s) int pos,n;LinkType pa,pb;if(La.head&Lb.head)pa=La.head-next;pb=Lb.head-next;s-last=pos=0;while(pa&pb)n=WordCmp(pa-data,pb-data);if(n=0)s-eqelems-last+=pos+;pa=pa-next;pb=pb-next;else if(n=-1)pa=pa-

20、next;pos+;else pb=pb-next;12/*-*/*判表空函数*/*功能：判断表 L是否是空表*/* 参数：OrderList L-有序表*/*返回值：0-非空表；1-空表*/*-*/status ListEmpty(OrderList * L)(if(L-size=0) return TRUE;return FALSE;int ListLength(OrderList* L)(/* 返回判表长度 */if(L-head =L-tail) return 0;else return L-size ;/*- 与文本文件有关的函数 -*/*-*/*字符判断函数*/*功能：判断文件中下

21、一个字符是否为回车符*/*参数：FILE *f-文件指针*/*返回值：0-不是回车符；1-是回车符*/*-*/int feoln(FILE *f)(char cha;cha=fgetc(f);if(cha=n) return(TRUE);ungetc(cha,f);return FALSE;/*-*/*读取单词函数*/*功能：从文件中读取一个单词*/*参数：FILE *f-文件指针*/*Sequence *st-指向单词的指针*/*返回值：无*/*-*/void GetAWord(FILE *f,Sequence *st)char ch;int k=0;ch=fgetc(f);while(ch

22、= )(ch=fgetc(f);if(ch=n)break;/*去掉空格和回车 */13if(ch=n)(ungetc(ch,f);ch= ;/*最后一个为回车键，文件指针回指*/while(ch=a&ch=A&ch=0&chchk=ch;ch=fgetc(f);k+; if(ch=n) ungetc(ch,f);st-size=k;/*-*/*读取文件当前行单词函数*/*功能：提取文件指针所指行所有单词*/*参数：FILE *f-文件指针*/* OrderList *ta-存放单词有序表的指针*/*返回值：0-操作失败；1-操作成功*/*-*/ status Extr

23、actWord(FILE*f,OrderList *ta)int i;char lendc;Sequence str;WordType nwd;LinkType p,q;LinkType s;InitList(ta);p=ta-head;q=ta-head;for(i=0;!feof(f);i+)if(feoln(f)return(TRUE);GetAWord(f,&str);/*从文件中读出一个单词 */ NewWord(&nwd,str);/*将单词放入堆存储空间*/MakeNode(&s,nwd);/* 生成一个单词节点 */ if(ta-head-next) w

24、hile(p!=NULL&WordCmp(p-data,s-data)=-1)q=p;p=p-next; p=q;InsertAfter(ta,p,s);p=ta-head-next; q=ta-head;/*- */*文件单词匹配函数*/*功能：统计指定单词在文件中出现的次数和位置*/*参数：FILE *f-文件指针*/*OrderList pat-指定统计的单词有序表*/*ResultType rs-统计结果列表*/*返回值：0-统计失败；1-统计成功*/*- */ status match(FILE *f,OrderListpat,ResultType rs)int i,k,li

25、nenum,failed,fsp;OrderList sa;14EqelemList eqlist;Link p,q;if(!pat.head)return FALSE;linenum=1;while(!feof(f)ExtractWord(f,&sa);ListCompare(pat,sa,&eqlist);i=0;if(eqlist.last)while(inext=rseqlist.eqelemi.Next;rseqlist.eqelemi.Next=p;p-elem=linenum;rseqlist.eqelemi.count+; i+;/* 内层 while*/lin

26、enum+;/* 行数加 1*/ DestroyList(&sa); NewLength(pat);/* 外层 while*/fclose(f);return TRUE;/*- */*初始化文件函数*/*功能：输入指定的文件名并打开文件*/*参数：FILE *f-返回的文件指针*/15/*-*/status Initialization(FILE *fr)(char FileName30;printf(Input file name:);do(scanf(%s”,FileName);while(strlen(FileName)=0);*fr=fopen(FileName,r);if(*

27、fr)(printf(file open!n);return TRUE;else(printf(file not open!n);return FALSE;/*-*/*输入统计的词集函数*/*功能：输入待统计的词集并建立起数据结构*/*参数：OrderList *pt-返回的词集有序表指针*/*返回值：无*/*-*/void InputWord(OrderList *pt)(char cc;int i=0;Sequence ws;LinkType p,q,s;WordType nwd;InitList(pt);p=pt-head;q=pt-head;while(cc=getchar()(if(

28、cc!= &cc!=n)ws.chi=cc;i+;else(ws.size=i;NewWord(&nwd,ws);MakeNode(&s,nwd);if(pt-head-next)(while(p!=NULL&WordCmp(p-data,s-data)=-1)q=p;p=p-next;p=q;/*返回值：0-初始化失败；1-初始化成功*/16InsertAfter(pt,p,s);p=pt-head-next;q=pt-head;i=0;if(cc=n)return;/*-*/*初始化统计结果表函数*/*功能：用待统计词集初始化统计结果表*/*参数：Resul

29、tType rs-统计结果数组*/* OrderList pt-待统计的词集表*/*返回值：无*/*-*/ voidInitRList(ResultType rs,OrderList pat)int k;LinkType p;p=pat.head-next;for(k=0;kdata);rsk.Next=NULL;rsk.count=0;p=p-next;/*-*/*输出统计结果函数*/*功能：输出统计的结果*/*参数：ResultType rs-统计结果数组*/* intn-待统计的词集个数*/*返回值：无*/*-*/ voidOutResult(ResultType rslist,int

30、n)17int i,j;Link p;for(i=0;in;i+)(printf(The word );PrintWord(rslisti.data);printf( appeared in the file %d times”,rslisti.count);if(rslisti.count!=0) printf( and on );p=rslisti.Next;for(j=0;jrslisti.count;j+)if(jelem);p=p-next;else printf(%dn”,p-elem);else printf(n);/*-*/*撤销统计结果数据空间函数*/*功能：释放存放统计结果

31、数据的动态存储空间*/*参数：ResultType rs-统计结果数组*/*返回值：无*/*-*/ void FreeResult(ResultType rs,int n) int i;Link p,q;for(i=0;in;i+) if(rsi.Next!=NULL)break;if(rsi.Next!=NULL) for(i=0;inext; free(q); rsi.Next=NULL; rsi.count=0;else return;int main()(int flag=0;sp.freep=0; /*sp 为全局变量 */FILE *fp=NULL;OrderList *pt;pt

32、=(OrderList *)malloc(sizeof(OrderList);pt-head=NULL;ResultType rs;do(18Initialization(&fp);/*输入文件名并打开文件 */printf(input search wordsn);getchar();InputWord(pt);/*输入查询的单词*/if(fp&!ListEmpty(pt)InitRList(rs,*pt);if(match(fp,*pt,rs)OutResult(rs,ListLength(pt);elseDestroyList(pt);printf(Do you want

33、 to have a seach again?(YES-1/NO-0)n); scanf(%d,&flag);fflush(stdin);while(flag);system(pause);return 0;五、调试分析：1、 在编程的过程中，对设计做了如下修改：1)考虑到堆空间可能设置不够大，以至可能引起数组出界的错误，因此将NewWord改为 status类型函数，返回堆空间分配成功与否的信息。2)在原来的设计中，由于考虑避免重复，故没有将待统计的单词放入统计结果的线性表中，编程时发现最后的输出比较麻烦，并且信息的封装也不够好，后修改设计为 现在的结构。由于本题中的单词串采用的事堆

34、式存储结构，因此在结果信息的线性 表中增添单词信息可以实现“串值共享”，并不增加单词的存储空间，为此在WordType类型中增添了一个“复制”的函数。2、 主要算法的时空分析：假设每个单词的平均长度为s,待统计的单词数为m,每一行中不同的单词平均数为 k,文件含有 n行。(1)WordCmp 的时间复杂度为 O(s); LocateElem 的时间复杂度为 O(ms)或 O(ks);ListCompare的时间复杂度为 O(ms+ks);(2)InputWord的时间复杂度为 O(m2*s) ; Extractwords 的时间复杂度为 O(kA2*s);(3)Match 的时间复杂度为 O(

35、n(kA2*s+ms)或 O(lk);其中： ln,ks为文件长度(文件 中的字符数)；因此，和 KMP算法(时间复杂度为线性)相比，本次实习中的策 略不是一种高效的方法，其主要的缺点是必须先建立单词的有序表。(4)程序中占用的辅助空间主要用于链表和串值，因此，空间复杂度为 O(m+k)s),在 本程序中，虽然在每一行的检测结束后，释放的链表空间时首先释放结点的元素， 但实际上，只是摧毁了单词结构，并没有回收串值所占的堆空间。3、对照需求分析，本程序还有一个问题是，对同一行中出现多次的单词只统计了一次。由于在进行需求分析时，对这种情况只强调了只输出一个行号，而没有明确写明统计次数，故出现此纸漏

36、。194、程序的扩展方向：程序还不能完全处理汉字串的情况，可以向着类似 office和一般的文本编辑工具所提供的全字匹配查找与一般查找方向拓展，真正做到“一查即得，一查即准” 。同时，针对统计 延时，可以在参考 KMP 算法的同时，加以优化改良。六、经验体会：1)理解分析问题的能力得到提高。设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽象，问题的脉络就清晰了。接下来，如何读取，读取后如何映射， 映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。逐个解析， 整个程序的框架就了然

37、于胸了。特别要指出的是，对整个程序的把握，随着编程工作的深入，是越来越深刻，而且新的思路也是层出不穷。2)创新意识和创新能力的提高。 本程序的设计，我最开始的想法是 KMP 算法，后来， 我放弃了 KMP算法，原因有两个，其一是 KMP 算法的缺陷，就我的了解来看，getlength中 含有一部分是 length，若用 KMP算法来检索 length，肯定会认为 getlength也算作 length 的 出处。这显然不合单词的定义要求。 其二是我想自己设计一种新的算法来挑战自己，挑战自己的数据结构与算法设计能力，这也是最重要的原因。3)对程序设计语言的细微之处又了更深刻的理解。由于字符串的操

38、作是很原始的基于原子的操作，所以更能看清楚平时我们所用的字符串操作函数在底层的实现机制。同时，对指针也有了新的认识。七、用户手册：1)本程序的运行环境为 DOS 操作系统，执行文件为match.exe;2)进入主程序后即显示提示信息：Input file name: ”；若文件输入为空，则会一直提示Input file name:,直到输入文件为止；如果文件打开，则显示 file open!,否 则显示file notopen!。3)输入文件后，屏幕再次提示：inputsearch words:(输入待统计的单词集合)，单 词之间输入空格键，输入完毕后，以回车键结束；4)输入结束后，程序即进行统计。随后输出统计信息：The word 待统计单词appeared in the file 次数times and on 第几行 所有待统计单词将连续输出。5)本次统计结束