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

文学研究助手一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。二、需求分析：1、 文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输入；2、 “单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；3、 待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、 在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；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,Sequence cha) 初始条件：cha为字符序列； 操作结果：生成一个其值为给定字符序列的单词； WordCmp(WordType wd1,WordType wd2) 初始条件：单词wd1和单词wd2已存在； 操作结果：若wd1wd2，则返 回1； PrintWord(WordType wd) 初始条件：单词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 基本操作： InitList(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已存在，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,n 0；数据关系：D中字符被“换行符”分割成若干行，每一行的字符间满足下列关系： R1= | Si-1,Si D,i = 1,2,3,.,n 基本操作： Initialization(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) 初始条件：文件f已打开，文件指针指向文件f中第一个字符；pat为包含所有待查 询单词的有序表； 操作结果：rs为查询结果； ADT TextString4. 本程序包含四个模块：1） 主程序模块：主函数设计如下int main ( ) 输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和位置；输出测试结果；2） 单词单元模块-实现单词类型；3） 有序表单元模块-实现有序表类型；4） 单词文本串文件单元模块-实现文本串文件类型； 主程序模块各模块间的调用关系如下： 文本文件单元模块 有序表单元模块- 单词单元模块四、详细设计1、主程序中的宏定义：#define MAXSIZE 1000/字符空间的最大容量#define MAXLEN 20 /单词的最大长度#define MAXNUM 16 /一行中单词最多个数#define FALSE 0#define TRUE 12、存储结构/*堆结构的定义*/typedef struct char storesMAXSIZE; int freep; /*当前可用空间开始位置*/ HeapSpace;HeapSpace sp;/*单词数据类型定义*/typedef struct /单词在堆中的位置描述 int stadr; /*单词在对空间中的开始位置*/ int len; /*单词长度*/ WordType;typedef struct /单词描述 char chMAXLEN; /*单词字符串*/ int size; /*单词长度*/ Sequence;/*有序表类型定义*/typedef WordType ElemType;typedef struct NodeType /单词有序表结点定义 ElemType data; struct NodeType *next; NodeType,*LinkType;typedef struct /单词有序表定义 LinkType head; /*有序表头指针*/ LinkType tail; /*有序表尾指针*/ int size; /*有序表结点个数*/ OrderList;/*记录一行中匹配成功单词在目标词汇表中的位置*/typedef struct int eqelemMAXNUM; /*单词在目标词汇表中的位置*/ int last; /*匹配成功单词的个数*/ EqelemList;/*文件测试相关的数据类型定义*/typedef struct Node /单词在文件中的位置 int elem; /*被测单词在文件中的行号*/ struct Node *next;/*指向下一个行号结点的指针*/ Node,*Link;typedef struct /单词统计分析记录结构定义 WordType data; /*被测试的单词*/ int count; /*在文件中出现的次数*/ Link Next; /*记录出现的所有行号的脸表头指针*/ HeadNode;/*文本文件测试结果记录定义*/typedef HeadNode ResultTypeMAXNUM;typedef int status;3、主要算法设计：/*-与单词相关的函数-*/*-*/* 定义新单词函数 */* 功能：把新单词放入堆中 */* 参数：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; elsei=sp.freep; sp.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-新单词描述信息指针 */* WordType *oldw-旧单词描述信息指针 */* 返回值：无 */*-*/void CopyWord(WordType *nw,WordType oldw) nw-stadr=oldw.stadr; nw-len=oldw.len;/*-*/* 单词比较函数 */* 功能：比较堆中两单词的大小 */* 参数：WordType wd1-第一个单词描述信息 */* WordType wd2-第二个单词描述信息 */* 返回值：-1-小于；0-等于；1-大于 */*-*/int WordCmp(WordType wd1,WordType wd2) int k,si,sj,m;si=wd1.stadr;sj=wd2.stadr;for(k=0;k=wd1.len&ksp.storessj+k)return 1; else return -1;else if(wd1.lensp.storessj+k)return 1; else return -1; elseif(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.stadr=e.stadr; (*p)-data.len=e.len; (*p)-next=NULL; return TRUE; /*-*/* 有序表初始化函数 */* 功能：申请头结点，初始化有序表 */* 参数：OrderList *L-有序表指针 */* 返回值：TRUE-初始化成功；FALSE-初始化失败 */*-*/status InitList(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; else L-head=NULL; return FALSE;/*-*/* 撤销有序表函数 */* 功能：释放有序表所有结点，撤销有序表 */* 参数：OrderList *L-有序表指针 */* 返回值：无 */*-*/void DestroyList(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-有序表 */* ElemType e-给定要查找的数据e */* LinkType *q-有序表结点指针 */* 查找成功，q指向具有e值的结点 */* 查找失败，q指向小于e的结点 */* 返回值：int型，1-查找成功；0-查找失败 */*-*/status LocateElem(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-有序表指针 */* LinkType q-指定结点指针 */* LinkType s-待查入结点指针 */* 返回值：无 */*-*/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-存放待匹配单词的有序表 */* EqelemList *s-存放匹配成功单词信息表指针 */* 返回值：无 */*-*/void ListCompare(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-next;pos+;else pb=pb-next;/*-*/* 判表空函数 */* 功能：判断表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 ;/*-与文本文件有关的函数-*/*-*/* 字符判断函数 */* 功能：判断文件中下一个字符是否为回车符 */* 参数：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= )ch=fgetc(f);if(ch=n)break;/*去掉空格和回车*/ if(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 ExtractWord(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)while(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,OrderList pat,ResultType rs) int i,k,linenum,failed,fsp; OrderList sa; EqelemList 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*/linenum+;/*行数加1*/DestroyList(&sa); NewLength(pat);/*外层while*/fclose(f); return TRUE;/*-*/* 初始化文件函数 */* 功能：输入指定的文件名并打开文件 */* 参数：FILE *f-返回的文件指针 */* 返回值：0-初始化失败；1-初始化成功 */*-*/status Initialization(FILE *fr) char FileName30;printf(Input file name:); do scanf(%s,FileName); while(strlen(FileName)=0); *fr=fopen(FileName,r); if(*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(cc!= &cc!=n)ws.chi=cc;i+;elsews.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;InsertAfter(pt,p,s); p=pt-head-next; q=pt-head; i=0;if(cc=n)return; /*-*/* 初始化统计结果表函数 */* 功能：用待统计词集初始化统计结果表 */* 参数：ResultType rs-统计结果数组 */* OrderList pt-待统计的词集表 */* 返回值：无 */*-*/void InitRList(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-统计结果数组 */* int n-待统计的词集个数 */* 返回值：无 */*-*/void OutResult(ResultType rslist,int n) int 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);/*-*/* 撤销统计结果数据空间函数 */* 功能：释放存放统计结果数据的动态存储空间 */* 参数：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=(OrderList *)malloc(sizeof(OrderList); pt-head=NULL; ResultType rs; do Initialization(&fp); /*输入文件名并打开文件*/ printf(input search wordsn); getchar(); InputWord(pt); /*输入查询的单词*/ if(fp&!ListEmpty(pt) InitRList(rs,*pt); if(match(fp,*pt,rs)OutResult(rs,ListLength(pt); else DestroyList(pt); printf(Do you want 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） 在原来的设计中，由于考虑避免重复，故没有将待统计的单词放入统计结果的线性表中，编程时发现最后的输出比较麻烦，并且信息的封装也不够好，后修改设计为现在的结构。由于本题中的单词串采用的事堆式存储结构，因此在结果信息的线性表中增添单词信息可以实现“串值共享”，并不增加单词的存储空间，为此在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(k2*s)；（3） Match的时间复杂度为O(n(k2*s+ms)或O(lk)；其中：ln,ks为文件长度（文件 中的字符数）；因此，和KMP算法（时间复杂度为线性）相比，本次实习中的策 略不是一种高效的方法，其主要的缺点是必须先建立单词的有序表。（4） 程序中占用的辅助空间主要用于链表和串值，因此，空间复杂度为O(m+k)s)，在 本程序中，虽然在每一行的检测结束后，释放的链表空间时首先释放结点的元素， 但实际上，只是摧毁了单词结构，并没有回收串值所占的堆空间。3、对照需求分析，本程序还有一个问题是，对同一行中出现多次的单词只统计了一次。由于在进行需求分析时，对这种情况只强调了只输出一个行号，而没有明确写明统计次数，故出现此纰漏。4、程序的扩展方向：程序还不能完全处理汉字串的情况，可以向着类似office和一般的文本编辑工具所提供的全字匹配查找与一般查找方向拓展，真正做到“一查即得，一查即准”。同时，针对统计延时，可以在参考KMP算法的同时，加以优化改良。六、经验体会：1)理解分析问题的能力得到提高。设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽象，问题的脉络就清晰了。接下来，如何读取，读取后如何映射，映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。逐个解析，整个程序的框架就了然于胸了。特别要指出的是，对整个程序的把握，随着编程工作的深入，是越来越深刻，而且新的思路也是层出不穷。2） 创新意识和创新能力的提高。本程序的设计，我最开始