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

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> | Si-1,Si D,i = 1,2,3,.,n基本操作： NewWord(WordType

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

4、：R1=<Si-1,Si> | Si-1,Si D,Si-1<S,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的元素的前驱的位置， 并返回函数值

5、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中字符被“换行符”分割成若干行，每

6、一行的字符间满足下列关系： R1=<Si-1,Si> | 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

7、，本操作结束时，文件指针 指向文件f中下一行的第一个字符；match(FILE *f,OrderList pat,ResultType rs) 初始条件：文件f已打开，文件指针指向文件f中第一个字符；pat为包含所有待查 询单词的有序表； 操作结果：rs为查询结果； ADT TextString4. 本程序包含四个模块：1） 主程序模块：主函数设计如下int main ( ) 输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和位置；输出测试结果；2） 单词单元模块-实现单词类型；3） 有序表单元模块-实现有序表类型；4） 单词文本串文件单元模块-实现文本串文件类型；

8、主程序模块各模块间的调用关系如下： 文本文件单元模块 有序表单元模块- 单词单元模块四、详细设计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 /

9、单词在堆中的位置描述 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 /单词有序表定义 LinkTyp

10、e head; /*有序表头指针*/ LinkType tail; /*有序表尾指针*/ int size; /*有序表结点个数*/ OrderList;/*记录一行中匹配成功单词在目标词汇表中的位置*/typedef struct int eqelemMAXNUM; /*单词在目标词汇表中的位置*/ int last; /*匹配成功单词的个数*/ EqelemList;/*文件测试相关的数据类型定义*/typedef struct Node /单词在文件中的位置 int elem; /*被测单词在文件中的行号*/ struct Node *next;/*指向下一个行号结点的指针*/ Node

11、,*Link;typedef struct /单词统计分析记录结构定义 WordType data; /*被测试的单词*/ int count; /*在文件中出现的次数*/ Link Next; /*记录出现的所有行号的脸表头指针*/ HeadNode;/*文本文件测试结果记录定义*/typedef HeadNode ResultTypeMAXNUM;typedef int status;3、主要算法设计：/*-与单词相关的函数-*/*-*/* 定义新单词函数 */* 功能：把新单词放入堆中 */* 参数：WordType *nw-单词描述信息指针 */* Sequence cha-单词信息

12、*/* 返回值：操作成功与否的状态信息 */* 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;k<cha.size;k+) sp.storesi+k=cha.chk; nw->stadr=i; nw->

13、;len=cha.size; return 1; /*-回到最初空间-*/void NewLength(OrderList rs) int m=0; LinkType p,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-旧单词描述

14、信息指针 */* 返回值：无 */*-*/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.

15、stadr;for(k=0;k<=wd1.len&&k<=wd2.len;k+)m=fabs(float)(sp.storessi+k-sp.storessj+k);if(m!=0&&m!=32)break;if(k=wd1.len|k=wd2.len)break; if(wd1.len=wd2.len) if(k=wd1.len)return 0; else if(sp.storessi+k>sp.storessj+k)return 1; else return -1;else if(wd1.len<wd2.len)if(k=wd1.l

16、en)return -1; else if(sp.storessi+k>sp.storessj+k)return 1; else return -1; elseif(k=wd2.len)return 1;elseif(sp.storessi+k>sp.storessj+k)return 1;else return -1; /*-*/* 打印单词函数 */* 功能：打印堆中一个单词 */* 参数：WordType wd-单词描述信息 */* 返回值：无 */*-*/void PrintWord(WordType wd) int i; for(i=0;i<wd.len;i+) p

17、utchar(sp.storeswd.stadr+i); /*-与有序表相关的函数-*/*-*/* 结点生成函数 */* 功能：生成一个单词在堆中存储信息的结点 */* 参数：LinkType *p-生成的新结点指针 */* ElemType e-单词存储信息 */* 返回值：TRUE-成功；FALSE-失败 */*-*/status MakeNode(LinkType *p,ElemType e) *p=(LinkType)malloc(sizeof(NodeType); if(!(*p) return FALSE; (*p)->data.stadr=e.stadr; (*p)->

18、;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; re

19、turn 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

20、 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)*

21、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-

22、>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->

23、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-空表 */*-*/

24、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

25、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;/*去

26、掉空格和回车*/ if(ch='n')ungetc(ch,f);ch=' '/*最后一个为回车键，文件指针回指*/while(ch>='a'&&ch<='z')|(ch>='A'&&ch<='Z')|(ch>='0'&&ch<='9')&&!feof(f) st->chk=ch;ch=fgetc(f);k+;if(ch='n') ungetc(ch

27、,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=

28、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-

29、>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;

30、 linenum=1; while(!feof(f)ExtractWord(f,&sa); ListCompare(pat,sa,&eqlist); i=0;if(eqlist.last)while(i<eqlist.last)/*计算出单词出现行号以及一行出现次数*/p=(Link)malloc(sizeof(Node); p->next=rseqlist.eqelemi.Next; rseqlist.eqelemi.Next=p; p->elem=linenum; rseqlist.eqelemi.count+; i+;/*内层while*/linenum

31、+;/*行数加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(str

32、len(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; S

33、equence 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)

34、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->ne

35、xt; for(k=0;k<pat.size;k+) CopyWord(&rsk.data,p->data); 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;i<n;i+)printf("The word &

36、quot;); 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;j<rslisti.count;j+)if(j<rslisti.count-1) printf("%d,",p->elem);p=p->next;else printf("%dn",p-&g

37、t;elem);else printf("n");/*-*/* 撤销统计结果数据空间函数 */* 功能：释放存放统计结果数据的动态存储空间 */* 参数：ResultType rs-统计结果数组 */* 返回值：无 */*-*/void FreeResult(ResultType rs,int n) int i; Link p,q;for(i=0;i<n;i+)if(rsi.Next!=NULL)break;if(rsi.Next!=NULL)for(i=0;i<n;i+)p=rsi.Next;while(p)q=p; p=p->next; free(q)

38、;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