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

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

2、个行号；5. 测试数据：本次实验中的文本文件是LiteratureAssitant.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 w

3、d2) 初始条件：单词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已存在； 操作

4、结果：销毁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,

5、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,Seque

6、nce *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. 本程序包含四个

7、模块：1）主程序模块：主函数设计如下int main ( ) 输入信息和文件初始化；生成测试目标词汇表；统计文件中每个待测单词出现的次数和位置；输出测试结果；2）单词单元模块-实现单词类型；3）有序表单元模块-实现有序表类型；4）单词文本串文件单元模块-实现文本串文件类型；5、存储结构及存储映像为：6、函数的调用关系为： mainInitialization InputWord ListEmpty InitRList OutResult match DestroyListInitList MakeNode NewWord WordCmp InsertAfter PrintWordMakeNod

8、e CopyWord ExtractWord ListCompare NewLength Felon GetAWord MakeNode InsertAfter三、 详细设计：/ LiteratureAssitant.cpp : Defines the entry point for the console application./#include stdafx.h#include stdafx.h/ LiteratureAssitant.cpp : 定义控制台应用程序的入口点。#include stdafx.h#include stdio.h#include string.h#includ

9、e #include #include #define MAXSIZE 10000 /字符空间的最大容量 #define MAXLEN 20 /假设一个单词的最大长度不超过20个字符#define MAXNUM 16 /假设文本文件中一行的单词数不超过16个#define FALSE 0 #define TRUE 1typedef int status; /*单词采用堆式存储结构，即分配一块较大的存储空间作为堆的存储空间，待分析的特定单词集放入堆空间中，文本文件中分解出的一行单词也放入堆空间中。由于一行单词分析完后就没有用途了，所以可以释放一行单词所占用的存储空间。*/typedef stru

10、ct/堆结构的定义 char storesMAXSIZE; int freep;/当前可用空间开始位置HeapSpace;HeapSpace sp; /由于堆操作在该程序中是最频繁的操作，可以把表示堆空间的变量定义为全程变量,/单词所占的堆空间，初始化令sp.freep=0/*单词通常用其在堆存储空间中的存储映像来表示。一个单词的值尽管在堆空间中，如果丢失了其存储映像，也就相当于丢失了单词。单词在存储空间中的存储映像可以定义为：*/typedef struct/单词类型定义 int stadr;/单词在堆空间中的位置int len; /单词长度WordType; typedef struct/

11、一个单词可以用其一个字符数组和字符串的长度来表示 char chMAXLEN;int size;Sequence;/*在实验中，待分析的单词构成一个单词集。文本文件中的一行作为一个基本分析单位，一行中的单词也构成一个单词集。 统计特定单词在文本文件中出现的次数和位置（行号）的基本方法是：用文本文件中分解出的一行的每个单词去查找待分析的特定单词集，若该单词出现在特定单词集中，则该单词的统计次数加1，并记录下出现的行号。 为了便于单词查找，可以把单词集组织成一个按从小到大升序排列的有序表。由于单词的个数不固定，用链式存储结构来实现有序表。 有序表的每个结点表示一个单词的存储映像。有序表类型定义:

12、*/ 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; /数组eqelem中

13、存放的是单词在特定单词集在有序表中结点序号，/该序号与分析结果链表的表头结点向量的序号一致，/表示要在对应链表中插入一个表示当前分析行的节点。 int last; /整数last表示在处理过程中要把匹配的单词结点的序号放入eqelem数组的位置，/最终表示有多少个单词获得匹配EqelemList; /*按照要求，程序的核心功能是要统计特定单词在文本文件中出现的次数和位置。因此次存放分析结果的数据结构中既要指明统计的是哪个单词，又要记录出现的次数和位置。 要统计的单词已放防在堆空间中，其存储映像已由单词有序表表示。 一个单词出现的位置的记录与出现的次数有关，但事先是无法估计一个单词在一个文本文件

14、中约出现多少次，因此用链表结构来记录单词出现的位置是合适的选择，即一个单词在文件中出现的位置用一个单链表来记录。 假定，要统计的特定单词从键盘输入，不超过一行，即单词个数不超过MAXNUM。为了表示分析结果的上述信息，又方便管理，可以将所有分析单词信息和链表的头指针信息共同构成一个向量结构。文件测试相关的数据类型定义 */ typedef struct Node /单词在文件中的位置 int elem;/被测单词在文件中的行号 struct Node *next;/指向下一个行号结点的指针 Node,*Link; typedef struct /单词统计分析记录结构定义 WordType da

15、ta; /被测试的单词int count; /在文件中出现的次数Link Next; /记录出现的所有行号的链表头指针 HeadNode; /*文本文件测试结果记录定义 */ typedef HeadNode ResultTypeMAXNUM; /*统计分析的总体思路 （1）从键盘输入待统计分析的特定单词集，将单词放入堆存出空间中，并建立单词集的存储映像有序表。（2）从键盘输入待分析的文本文件名并打开文件。 （3）顺序分析文本文件的每一行，直到文件结束。对每一行： 识别出该行的每个单词，把单词放入堆空间中，并建立单词存储映像有序表。 用该行分解出的单词与特定单词集中单词进匹配，记录下匹配的结果

16、。 建立结点记录相应单词出现的行号，插入到相应链表中，并累加统计次数。（4）输出统计结果数据。输出要统计的单词、单词在文件中出现的次数、单词出现的位置（行号）的集合。 */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; sp.freep=sp.freep+cha.size; for(k=0;kstad

17、r=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; void CopyWord(WordType *nw,WordType oldw) nw-stadr=oldw.stadr; nw-len=oldw.len;/将单词信息拷贝到另一个结点上int Wor

18、dCmp(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; elsereturn -1; else if(k=wd2.len)return 1; else if(sp.storessi+ksp.storessj+k)return 1; else return -1; void PrintWord

19、(WordType wd) int i; for(i=0;idata.stadr=e.stadr; (*p)-data.len=e.len; (*p)-next=NULL; return TRUE; /建立存储需查询的单词的链表的结点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; /建立链表void Destro

20、yList(OrderList *L) LinkType p,q; p=L-head; while(p) q=p;p=p-next; free(q); L-head=L-tail=NULL;/销毁有序表status LocateElem(OrderList L,ElemType e,LinkType *q) LinkType 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; void InsertAft

21、er(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+; 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-dat

22、a); 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; 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 ;int feoln(FILE *f) /判断文件中下一个字符是否为

23、回车符/返回值：0-不是回车符；1-是回车符char cha; cha=fgetc(f); if(cha=n) return(TRUE); ungetc(cha,f); /将你读到的字符回退到输入流中return FALSE; void GetAWord(FILE *f,Sequence *st) /*假定文件中单词或是字母字符序列、或是整数/小数型数字字符序列、或是界符，由此作为判断单词结束的依据。 算法基本思想：首先读掉单词前面的所有空格。若单词第一个字符是字母，则连续读取后面所有字母字符组成一个单词；若单词第一个字符是数字，则连续读取后面包括小数点在内的所有字母字符组成一个单词；若是界符

24、，则有单个界符字符组成一个单词。*/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; status ExtractWord(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;!

26、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; 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) ExtractWord(f,&sa); ListCompare(pat,sa,&eqlist); i=0; if(e

28、qlist.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; status Initialization(FILE *fr) char FileName30=LiteratureAssitant.cpp; /默认字符串文件为Lit

29、eratureAssitant.cpp/*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; /判断输入的文件是否为空文件void InputWord(OrderList *pt) /*假定：单词从键盘输入，每个单词之间由一个或多个空格隔开。 在堆存储结构中，单词由字符序列组成

30、，由单词长度值指示单词的长度，不用C语言的串结束符来表示串的结束. 读单词时，必须首先跳过单词前面的空格符号，直到读到一个非空格符号是该单词才开始。当读到一个空格符号或行结束符（n）时，一个单词结束。当遇到行结束符时，输入单词结束。 由于本函数建立一个独立的有序表，所以初始时，有序表必须为空。 算法基本思想：顺序读入一个单词，把该单词存入堆空间中，通过查询确定该单词是否是一个新单词，若是新单词，则建立存放该单词存储映像的结点，把结点插入到有序表的指定位置，使其保持单词有序表的有序性。*/char cc; int i=0; Sequence ws; LinkType p,q,s; WordTyp

31、e 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); 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

32、=n)return; 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; 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 times

33、n,rslisti.count); if(rslisti.count!=0) printf(and in line:); p=rslisti.Next; for(j=0;jrslisti.count;j+) if(jelem); p=p-next; else printf(%dn,p-elem); else printf(nn); 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(

34、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); /*输入查询的单词并

35、建立有序链表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);fflush(stdin); /清空键盘缓冲区 while(flag); system(pause); return 0; 四、 调试分析：