数据结构试验报告-文学研究报告助手

1、. 实验报告：文学研究助手题目：编写一个统计特定单词在文本中出现的次数和位置的程序需求分析文本串非空并以文件的形式存放在根目录中，统计匹配的词非空。文件名和需要匹配的词集均有用户从键盘输入；单词都是由*种类型字符的序列组成，如字母字符序列区分大小写、数值常数整数或小数型实数字符序列, 界符分隔符，等、运算符等+，-，*，/等可独立构成单词，中间不含空格并且区分大小写；待统计的单词在文本串中不跨行出现，它或者从行首开场，或者前置假设干空格字符；在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，假设一个单词在同一行出现屡次只输出一个行号；测试数据：本次实验中的文本文件是Liter

2、atureAssitant.cpp；待统计的词集为：If char int else for return void概要设计：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已存在；操作结果：假设wd1wd

3、2，则返回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,E

4、lemType 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； Listpare(OrderList La,OrderList Lb,EqelemList *s) 初始条件：有序表La和Lb已存在；操作结果：以s返回其中一样元素； ADT

5、 OrderList3. 定义单词文本串文件类型如下：ADT Te*tString数据对象：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；E*tractWord(F

6、ILE *f,OrderList *ta)初始条件：文件f已翻开，文件指针指向文件f中*一行的第一个字符；操作结果：提取该行中所有单词，并构成单词的有序表ta，本操作完毕时，文件指针指向文件f中下一行的第一个字符；match(FILE *f,OrderList pat,ResultType rs)初始条件：文件f已翻开，文件指针指向文件f中第一个字符；pat为包含所有待查询单词的有序表；操作结果：rs为查询结果；ADT Te*tString4. 本程序包含四个模块：1主程序模块：主函数设计如下int main ( ) 输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和

7、位置；输出测试结果；2单词单元模块-实现单词类型；3有序表单元模块-实现有序表类型；4单词文本串文件单元模块-实现文本串文件类型；5、存储构造及存储映像为：6、函数的调用关系为： mainInitialization InputWord ListEmpty InitRList OutResult match DestroyListInitList MakeNode NewWord WordCmp InsertAfter PrintWordMakeNode CopyWord E*tractWord Listpare NewLength Felon GetAWord MakeNode Insert

8、After详细设计：/ LiteratureAssitant.cpp : Defines the entry point for the console application./#include stdaf*.h#include stdaf*.h/ LiteratureAssitant.cpp : 定义控制台应用程序的入口点。#include stdaf*.h#include stdio.h#include string.h#include #include #include #define MA*SIZE 10000 /字符空间的最大容量#define MA*LEN 20 /假设一个单词的

9、最大长度不超过20个字符#define MA*NUM 16 /假设文本文件中一行的单词数不超过16个#define FALSE 0 #define TRUE 1typedef int status; /*单词采用堆式存储构造，即分配一块较大的存储空间作为堆的存储空间，待分析的特定单词集放入堆空间中，文本文件中分解出的一行单词也放入堆空间中。由于一行单词分析完后就没有用途了，所以可以释放一行单词所占用的存储空间。*/typedef struct/堆构造的定义char storesMA*SIZE; int freep;/当前可用空间开场位置HeapSpace;HeapSpace sp; /由于堆操

10、作在该程序中是最频繁的操作，可以把表示堆空间的变量定义为全程变量,/单词所占的堆空间，初始化令sp.freep=0/*单词通常用其在堆存储空间中的存储映像来表示。一个单词的值尽管在堆空间中，如果丧失了其存储映像，也就相当于丧失了单词。单词在存储空间中的存储映像可以定义为：*/typedef struct/单词类型定义int stadr;/单词在堆空间中的位置int len; /单词长度WordType; typedef struct/一个单词可以用其一个字符数组和字符串的长度来表示char chMA*LEN;int size;Sequence;/*在实验中，待分析的单词构成一个单词集。文本文件

11、中的一行作为一个根本分析单位，一行中的单词也构成一个单词集。统计特定单词在文本文件中出现的次数和位置行号的根本方法是：用文本文件中分解出的一行的每个单词去查找待分析的特定单词集，假设该单词出现在特定单词集中，则该单词的统计次数加1，并记录下出现的行号。为了便于单词查找，可以把单词集组织成一个按从小到大升序排列的有序表。由于单词的个数不固定，用链式存储构造来实现有序表。有序表的每个结点表示一个单词的存储映像。有序表类型定义: */ typedef WordType ElemType; /元素类型typedef struct NodeType/单词有序表结点定义ElemType data; str

12、uct NodeType *ne*t; NodeType,*LinkType;/结点类型，指针类型typedef struct /单词有序表定义LinkType head; /*有序表头指针*/ LinkType tail; /*有序表尾指针*/ int size; /*有序表结点个数*/ OrderList;typedef struct/单词在目标词汇表中的位置int eqelemMA*NUM; /数组eqelem中存放的是单词在特定单词集在有序表中结点序号，/该序号与分析结果链表的表头结点向量的序号一致，/表示要在对应链表中插入一个表示当前分析行的节点。int last; /整数last表

13、示在处理过程中要把匹配的单词结点的序号放入eqelem数组的位置，/最终表示有多少个单词获得匹配EqelemList; /*按照要求，程序的核心功能是要统计特定单词在文本文件中出现的次数和位置。因此次存放分析结果的数据构造中既要指明统计的是哪个单词，又要记录出现的次数和位置。要统计的单词已放防在堆空间中，其存储映像已由单词有序表表示。一个单词出现的位置的记录与出现的次数有关，但事先是无法估计一个单词在一个文本文件中约出现多少次，因此用链表构造来记录单词出现的位置是适宜的选择，即一个单词在文件中出现的位置用一个单链表来记录。假定，要统计的特定单词从键盘输入，不超过一行，即单词个数不超过MA*NU

14、M。为了表示分析结果的上述信息，又方便管理，可以将所有分析单词信息和链表的头指针信息共同构成一个向量构造。文件测试相关的数据类型定义 */ typedef struct Node /单词在文件中的位置int elem;/被测单词在文件中的行号struct Node *ne*t;/指向下一个行号结点的指针Node,*Link; typedef struct /单词统计分析记录构造定义WordType data; /被测试的单词int count; /在文件中出现的次数Link Ne*t; /记录出现的所有行号的链表头指针HeadNode; /*文本文件测试结果记录定义 */ typedef He

15、adNode ResultTypeMA*NUM; /*统计分析的总体思路1从键盘输入待统计分析的特定单词集，将单词放入堆存出空间中，并建立单词集的存储映像有序表。2从键盘输入待分析的文本文件名并翻开文件。3顺序分析文本文件的每一行，直到文件完毕。对每一行：识别出该行的每个单词，把单词放入堆空间中，并建立单词存储映像有序表。用该行分解出的单词与特定单词集中单词进匹配，记录下匹配的结果。建立结点记录相应单词出现的行号，插入到相应链表中，并累加统计次数。4输出统计结果数据。输出要统计的单词、单词在文件中出现的次数、单词出现的位置行号的集合。*/status NewWord(WordType *nw,

16、Sequence cha) /*算法的功能是把单词放入堆空间中，并建立单词在堆中的存储映像*/int i,k; if(sp.freep+cha.size=MA*SIZE) printf(Heap Full!n); getchar(); return 0; else i=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.hea

17、d-ne*t; while(p) if(mdata.stadr)m=p-data.stadr;q=p; p=p-ne*t; sp.freep=m+q-data.len; void CopyWord(WordType *nw,WordType oldw) nw-stadr=oldw.stadr; nw-len=oldw.len;/将单词信息拷贝到另一个结点上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+

18、k)return 1; else return -1; else if(wd1.lensp.storessj+k)return 1; elsereturn -1; else if(k=wd2.len)return 1; else if(sp.storessi+ksp.storessj+k)return 1; else return -1; void PrintWord(WordType wd) int i; for(i=0;idata.stadr=e.stadr; (*p)-data.len=e.len; (*p)-ne*t=NULL; return TRUE; /建立存储需查询的单词的链表的

19、结点status InitList(OrderList *L) ElemType wd; wd.len=0; if(MakeNode(&(L-head),wd) L-tail=L-head; L-head-ne*t=NULL; L-size=0; return TRUE; else L-head=NULL; return FALSE; /建立链表void DestroyList(OrderList *L) LinkType p,q; p=L-head; while(p) q=p;p=p-ne*t; free(q); L-head=L-tail=NULL;/销毁有序表status LocateE

20、lem(OrderList L,ElemType e,LinkType *q) LinkType p; p=L.head-ne*t;while(p) if(WordCmp(p-data,e)=0)*q=p;return TRUE; if(WordCmp(p-data,e)=-1)*q=p; p=p-ne*t; return FALSE; void InsertAfter(OrderList *L,LinkType q,LinkType s) if(L-head&q&s) s-ne*t=q-ne*t;q-ne*t=s; if(L-tail=q) L-tail=s; L-size+; void L

21、istpare(OrderList La,OrderList Lb,EqelemList *s) int pos,n; LinkType pa,pb; if(La.head&Lb.head) pa=La.head-ne*t; pb=Lb.head-ne*t; s-last=pos=0; while(pa&pb) n=WordCmp(pa-data,pb-data); if(n=0) s-eqelems-last+=pos+; pa=pa-ne*t; pb=pb-ne*t; else if(n=-1) pa=pa-ne*t; pos+; else pb=pb-ne*t; status ListE

22、mpty(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 ;int feoln(FILE *f) /判断文件中下一个字符是否为回车符/返回值：0-不是回车符；1-是回车符char cha; cha=fgetc(f); if(cha=n) return(TRUE); ungetc(cha,f); /将你读到的字符回退到输入流中return FALSE; void

23、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)

24、;ch= ;/*最后一个为回车键，文件指针回指*/ while(ch=a&ch=A&ch=0&chchk=ch;ch=fgetc(f);k+; if(ch=n) ungetc(ch,f); st-size=k; status E*tractWord(FILE *f,OrderList *ta) /*文件中以n作为行完毕符，每个单词之间空格符或界符隔开。每个单词或是字母字符序列、或是整数/小数型数字字符序列、或是界符，由此作为判断单词完毕的依据。在堆存储构造中，一行单词组成一个有序表。假设一行中有多个一样单词，则只算一个。算法根本思想：顺序读入一个单词，把该单词存入堆空间中，通过查询确定该单词是

25、否是一个新单词，假设是新单词，则建立存放该单词存储映像的结点，把结点插入到有序表的指定位置。遇到行完毕符是则算法完毕。*/int i; Sequence str; WordType nwd; LinkType p,q; LinkType s; if(!InitList(ta)return FALSE; 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);/生成一个单词

26、节点if(ta-head-ne*t) while(p!=NULL & WordCmp(p-data,s-data)=-1)q=p;p=p-ne*t; p=q; InsertAfter(ta,p,s); p=ta-head-ne*t;q=ta-head; status match(FILE *f,OrderList pat,ResultType rs) /*前提：文件已经翻开，文件指针指向文件中的一个字符。算法根本思想：每次读入一行单词，把单词放入堆中，并建立该行单词的存储映像有序表；用该行单词与指定单词集进展匹配，记录下指定单词集中被匹配单词的存储映像结点序号；在被匹配单词结果链表中插入结点记

27、录匹配的行号。*/int i,linenum; OrderList sa; EqelemList eqlist; Link p; if(!pat.head)return FALSE; linenum=1; while(!feof(f) E*tractWord(f,&sa); Listpare(pat,sa,&eqlist); i=0; if(eqlist.last) while(ine*t=rseqlist.eqelemi.Ne*t; rseqlist.eqelemi.Ne*t=p; p-elem=linenum; rseqlist.eqelemi.count+; i+;/*层while*/

28、linenum+;/*行数加1*/ DestroyList(&sa); NewLength(pat); /*外层while*/ fclose(f); return TRUE; status Initialization(FILE *fr) char FileName30=LiteratureAssitant.cpp; /默认字符串文件为LiteratureAssitant.cpp/*printf(Input file name:); do scanf(%s,FileName); while(strlen(FileName)=0); */*fr=fopen(FileName,r); if(*fr

29、) printf(file open!n); return TRUE; else printf(file not open!n); return FALSE; /判断输入的文件是否为空文件void InputWord(OrderList *pt) /*假定：单词从键盘输入，每个单词之间由一个或多个空格隔开。在堆存储构造中，单词由字符序列组成，由单词长度值指示单词的长度，不用C语言的串完毕符来表示串的完毕. 读单词时，必须首先跳过单词前面的空格符号，直到读到一个非空格符号是该单词才开场。当读到一个空格符号或行完毕符n时，一个单词完毕。当遇到行完毕符时，输入单词完毕。由于本函数建立一个独立的有序表

30、，所以初始时，有序表必须为空。算法根本思想：顺序读入一个单词，把该单词存入堆空间中，通过查询确定该单词是否是一个新单词，假设是新单词，则建立存放该单词存储映像的结点，把结点插入到有序表的指定位置，使其保持单词有序表的有序性。*/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+; else ws.size=i;NewWord(&nwd,ws); MakeNod

31、e(&s,nwd); if(pt-head-ne*t) while(p!=NULL & WordCmp(p-data,s-data)=-1) q=p;p=p-ne*t; p=q; /判断是否为新单词InsertAfter(pt,p,s); /将新单词插入到有序表p=pt-head-ne*t; q=pt-head; i=0; if(cc=n)return; void InitRList(ResultType rs,OrderList pat) int k; LinkType p; p=pat.head-ne*t; for(k=0;kdata); rsk.Ne*t=NULL; rsk.count=

32、0; p=p-ne*t; void OutResult(ResultType rslist,int n) int i,j; Link p; for(i=0;in;i+) printf(nThe word: ); PrintWord(rslisti.data); printf( appeared in the file %d timesn,rslisti.count); if(rslisti.count!=0) printf(and in line:); p=rslisti.Ne*t; for(j=0;jrslisti.count;j+) if(jelem); p=p-ne*t; else pr

33、intf(%dn,p-elem); else printf(nn); void FreeResult(ResultType rs,int n) int i; Link p,q; for(i=0;in;i+) if(rsi.Ne*t!=NULL)break; if(rsi.Ne*t!=NULL) for(i=0;ine*t; free(q); rsi.Ne*t=NULL; rsi.count=0; else return; int main() int flag=0;/承受键盘命令sp.freep=0; /sp为全局变量FILE *fp=NULL; OrderList *pt; pt=(Orde

34、rList *)malloc(sizeof(OrderList); pt-head=NULL; ResultType rs; do Initialization(&fp); /*输入文件名并翻开文件*/ printf(input search wordsn); getchar(); InputWord(pt); /*输入查询的单词并建立有序链表pt*/ if(fp & !ListEmpty(pt) InitRList(rs,*pt); /初始化统计结果线性表rsif(match(fp,*pt,rs)OutResult(rs,ListLength(pt);/输出统计结果else DestroyList(pt); /释放待匹配单词表的空间printf(nnDo you want to have a seach again(YES-1/NO-0)n); scanf(%d,&flag);f