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

实验报告：文学研究助手

题目：编写一个统计特定单词在文本中出现的次数和位置的程序

一、 需求分析

1. 文本串非空并以文件的形式存放在根目录中，统计匹配的词非空。文件名和需要匹配的词集均有用户从键盘输入；

2. 单词都是由某种类型字符的序列组成，如字母字符序列（区分大小写）、数值常数（整数或小数型实数）字符序列, 界符（分隔符（‘（’，‘）’，‘，’等）、运算符等（‘+’，‘-’，‘*’，‘/’等）可独立构成单词，中间不含空格并且区分大小写；

3. 待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；

4. 在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号， 若一个单词在同一行出现多次只输出一个行号；

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 wd2)

初始条件：单词wd1和单词wd2已存在；

操作结果：若wd1wd2，则返 回1；

PrintWord(WordType wd)

初始条件：单词wd 已存在；

操作结果：在计算机终端上显示单词wd ；

}ADT AWord

2. 定义有序表类型：

ADT OrderList{

数据对象：D={Si | Si ∈AWord,i = 1,2,3,„„.,n,n ≥ 0}

数据关系：R1={} | Si-1,Si ∈ D,Si-1

基本操作：

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 OrderList

3. 定义单词文本串文件类型如下：

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 TextString

4. 本程序包含四个模块：

1） 主程序模块：主函数设计如下

int main ( ) {

输入信息和文件初始化；

生成测试目标词汇表；

统计文件中每个待测单词出现的次数和位置；

输出测试结果；

}；

2） 单词单元模块-------实现单词类型；

3） 有序表单元模块--------实现有序表类型；

4） 单词文本串文件单元模块------实现文本串文件类型；

5、存储结构及存储映像为：

6、函数的调用关系为：

// 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"

#include

#include

#include

#define MAXSIZE 10000 //字符空间的最大容量

#define MAXLEN 20 //假设一个单词的最大长度不超过20个字符

#define MAXNUM 16 //假设文本文件中一行的单词数不超过16个

#define FALSE 0

#define TRUE 1

typedef int status;

/*

单词采用堆式存储结构，即分配一块较大的存储空间作为堆的存储空间，

待分析的特定单词集放入堆空间中，文本文件中分解出的一行单词也放入堆空间中。 由于一行单词分析完后就没有用途了，所以可以释放一行单词所占用的存储空间。 */

typedef struct //堆结构的定义

{

char stores[MAXSIZE];

int freep;//当前可用空间开始位置

}HeapSpace;

HeapSpace sp; //由于堆操作在该程序中是最频繁的操作，可以把表示堆空间的变量定义为全程变量,

//单词所占的堆空间，初始化令sp.freep=0

/*

单词通常用其在堆存储空间中的存储映像来表示。

一个单词的值尽管在堆空间中，如果丢失了其存储映像，也就相当于丢失了单词。 单词在存储空间中的存储映像可以定义为：

*/

typedef struct //单词类型定义

{

int stadr;//单词在堆空间中的位置

int len; //单词长度

}WordType;

typedef struct //一个单词可以用其一个字符数组和字符串的长度来表示

{

char ch[MAXLEN];

int size;

}Sequence;

/*在实验中，待分析的单词构成一个单词集。

文本文件中的一行作为一个基本分析单位，一行中的单词也构成一个单词集。

统计特定单词在文本文件中出现的次数和位置（行号）的基本方法是：

用文本文件中分解出的一行的每个单词去查找待分析的特定单词集，

若该单词出现在特定单词集中，则该单词的统计次数加1，并记录下出现的行号。 为了便于单词查找，可以把单词集组织成一个按从小到大升序排列的有序表。

由于单词的个数不固定，用链式存储结构来实现有序表。

有序表的每个结点表示一个单词的存储映像。有序表类型定义: */

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 eqelem[MAXNUM]; //数组eqelem 中存放的是单词在特定单词集在有序表中结点序号，

//该序号与分析结果链表的表头结点向量的序号一致，

//表示要在对应链表中插入一个表示当前分析行的节点。

int last; //整数last 表示在处理过程中要把匹配的单词结点的序号放入eqelem 数组的位置，

//最终表示有多少个单词获得匹配

}EqelemList;

/*按照要求，程序的核心功能是要统计特定单词在文本文件中出现的次数和位置。

因此次存放分析结果的数据结构中既要指明统计的是哪个单词，又要记录出现的次数和位置。 要统计的单词已放防在堆空间中，其存储映像已由单词有序表表示。

一个单词出现的位置的记录与出现的次数有关，

但事先是无法估计一个单词在一个文本文件中约出现多少次，

因此用链表结构来记录单词出现的位置是合适的选择，

即一个单词在文件中出现的位置用一个单链表来记录。

假定，要统计的特定单词从键盘输入，不超过一行，即单词个数不超过MAXNUM 。 为了表示分析结果的上述信息，又方便管理，

可以将所有分析单词信息和链表的头指针信息共同构成一个向量结构。

文件测试相关的数据类型定义 */

typedef struct Node

{ //单词在文件中的位置

int elem; //被测单词在文件中的行号

struct Node *next; //指向下一个行号结点的指针

}Node,*Link;

typedef struct

{ //单词统计分析记录结构定义

WordType data; //被测试的单词

int count; //在文件中出现的次数

Link Next; //记录出现的所有行号的链表头指针

}HeadNode;

/*文本文件测试结果记录定义 */

typedef HeadNode ResultType[MAXNUM];

/*

统计分析的总体思路

（1）从键盘输入待统计分析的特定单词集，将单词放入堆存出空间中，并建立单词集的存储映像有序表。

（2）从键盘输入待分析的文本文件名并打开文件。

（3）顺序分析文本文件的每一行，直到文件结束。对每一行：

① 识别出该行的每个单词，把单词放入堆空间中，并建立单词存储映像有序表。 ② 用该行分解出的单词与特定单词集中单词进匹配，记录下匹配的结果。

③ 建立结点记录相应单词出现的行号，插入到相应链表中，并累加统计次数。

（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;k

sp.stores[i+k]=cha.ch[k];

nw->stadr=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 WordCmp(WordType wd1,WordType wd2) //判断是否为新单词 {

int k,si,sj,m;

si=wd1.stadr;

sj=wd2.stadr;

for(k=0;k

{

m=fabs((float)(sp.stores[si+k]-sp.stores[sj+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.stores[si+k]>sp.stores[sj+k])

return 1;

else

return -1;

}

else if(wd1.len

{

if(k==wd1.len)

return -1;

else if(sp.stores[si+k]>sp.stores[sj+k])

return 1;

else

return -1;

} else

{

if(k==wd2.len)

return 1;

else if(sp.stores[si+k]>sp.stores[sj+k])

return 1;

else

return -1;

}

}

void PrintWord(WordType wd)

{

int i;

for(i=0;i

putchar(sp.stores[wd.stadr+i]);

}

status MakeNode(LinkType *p,ElemType e)

{

*p=(LinkType)malloc(sizeof(NodeType));

if(!(*p))

return FALSE;

(*p)->data.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 DestroyList(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 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++;

}

}

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->eqelem[s->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)

{ //判断文件中下一个字符是否为回车符

//返回值：0--不是回车符；1--是回车符

char cha;

cha=fgetc(f);

if(cha=='\n')

return(TRUE);

ungetc(cha,f); //将你读到的字符回退到输入流中

return FALSE;

}

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'&&ch

st->ch[k]=ch;

ch=fgetc(f);

k++;

}

if(ch=='\n')

ungetc(ch,f);

st->size=k;

}

status ExtractWord(FILE *f,OrderList *ta)

{ /*文件中以‘\n’作为行结束符，每个单词之间空格符或界符隔开。

每个单词或是字母字符序列、或是整数/小数型数字字符序列、或是界符， 由此作为判断单词结束的依据。

在堆存储结构中，一行单词组成一个有序表。若一行中有多个相同单词，则只算一个。 算法基本思想：顺序读入一个单词，把该单词存入堆空间中，

通过查询确定该单词是否是一个新单词，若是新单词，

则建立存放该单词存储映像的结点，把结点插入到有序表的指定位置。

遇到行结束符是则算法结束。*/

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);//生成一个单词节点 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)

{ /*前提：文件已经打开，文件指针指向文件中的一个字符。

算法基本思想：每次读入一行单词，把单词放入堆中，

并建立该行单词的存储映像有序表；用该行单词与指定单词集进行匹配，

记录下指定单词集中被匹配单词的存储映像结点序号；

在被匹配单词结果链表中插入结点记录匹配的行号。*/

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(eqlist.last)

while(inext=rs[eqlist.eqelem[i]].Next; rs[eqlist.eqelem[i]].Next=p; p->elem=linenum; rs[eqlist.eqelem[i]].count++; i++; }/*内层while*/ linenum++;/*行数加1*/ DestroyList(&sa); NewLength(pat);

}/*外层while*/

fclose(f);

return TRUE;

}

status Initialization(FILE **fr)

{

char FileName[30]="LiteratureAssitant.cpp"; //默认字符串文件为LiteratureAssitant.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)

{

/*

假定：单词从键盘输入，每个单词之间由一个或多个空格隔开。

在堆存储结构中，单词由字符序列组成，由单词长度值指示单词的长度，

不用C 语言的串结束符来表示串的结束.

读单词时，必须首先跳过单词前面的空格符号，

直到读到一个非空格符号是该单词才开始。

当读到一个空格符号或行结束符（‘\n’）时，一个单词结束。

当遇到行结束符时，输入单词结束。

由于本函数建立一个独立的有序表，所以初始时，有序表必须为空。

算法基本思想：顺序读入一个单词，把该单词存入堆空间中，

通过查询确定该单词是否是一个新单词，若是新单词，

则建立存放该单词存储映像的结点，把结点插入到有序表的指定位置，

使其保持单词有序表的有序性。

*/

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.ch[i]=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=='\n')

return;

}

}

void InitRList(ResultType rs,OrderList pat)

{

int k;

LinkType p;

p=pat.head->next;

for(k=0;k

{

CopyWord(&rs[k].data,p->data);

rs[k].Next=NULL;

rs[k].count=0;

p=p->next;

}

}

void OutResult(ResultType rslist,int n)

{

int i,j;

Link p;

for(i=0;i

{

printf("\nThe word: [");

PrintWord(rslist[i].data);

printf("] appeared in the file %d times\n",rslist[i].count);

if(rslist[i].count!=0)

{

printf("and in line:");

p=rslist[i].Next;

for(j=0;j

if(j

{

printf("%d,",p->elem);

p=p->next;

}

else

printf("%d\n",p->elem);

}

else

printf("\n\n");

}

}

void FreeResult(ResultType rs,int n)

{

int i;

Link p,q;

for(i=0;i

if(rs[i].Next!=NULL)

break;

if(rs[i].Next!=NULL)

for(i=0;i

{

p=rs[i].Next;

while(p)

{

q=p;

p=p->next;

free(q);

}

rs[i].Next=NULL;

rs[i].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 words\n"); getchar(); InputWord(pt); /*输入查询的单词并建立有序链表pt*/ if(fp && !ListEmpty(pt)) { InitRList(rs,*pt); //初始化统计结果线性表rs if(match(fp,*pt,rs)) OutResult(rs,ListLength(pt));//输出统计结果 else DestroyList(pt); //释放待匹配单词表的空间 } printf("\n\nDo you want to have a seach again?(YES--1/NO--0)\n"); scanf("%d",&flag); fflush(stdin); //清空键盘缓冲区 }while(flag); system("pause"); return 0;

四、 调试分析：

1) 本次编写程序的代码比较多，函数的调用关系也相当复杂。因此在编程的过程中，容易

出现各种各样的问题，例如：由于粗心导致程序的语法问题、堆结构的设置不够完善、函数的调用关系不能明确等等；

2) 本次编程中默认的查询文件为LiteratureAssitant.cpp ，它是通过在创建文件时命名并构

建的，因此在输入文件名时应注意一定得输入LiteratureAssitant ；当然，也可以在c 语言文件的根目录中建立需要查询的文件，然后通过相关代码来查找到该文件从而达到实验目的；

3) 从这次实验中可以看出线性表的应用十分广泛。查询的单词可以包含四种元素类型（字

符、整数等）

4) 主要算法的时空分析：

假设每个单词的平均长度为s ，待统计的单词数为m ，每一行中不同单词的平均数为k ，文件中含有n 行。

a) WordCmp 的时间复杂度为O （s ）；LocateElem 的时间复杂度为）O （ms ）或O(ks)，

ListCompare 的时间复杂度为O （ms+ks）；

b) InputWord 的时间复杂度为O(m^2*s)；ExtractWords 的时间复杂度为O(k^2*s)；

c) Match 的时间复杂度为O(n(k^2*s+ms))或O(lk)；其中：l>n,ks为文件长度（文件中的字

符数）；因此，和KMP 算法（时间复杂度为线性）相比，本次实习中的策略不是一种高效的方法，其主要的缺点是必须先建立单词的有序表。

d) 程序中占用的辅助空间主要用于链表和串值，因此，空间复杂度为O((m+k)s)，在本程

序中，虽然在每一行的检测结束后，释放的链表空间时首先释放结点的元素，但实际上，只是摧毁了单词结构，并没有回收串值所占的堆空间。

5) 本次算法中存在的问题：由于本程序只对同一行中出现的单词统计一次，若一行中出现

了多个需要统计的单词，那么最终的统计结果会出现纰漏。

五、 用户手册：

1) 本程序的运行环境为DOS 操作系统，执行文件为：match.exe ；

2) 本程序的运行界面为：

3)

4)

5)

6)

进入程序运行界面后，提示输入查询的单词，单词之间用空格分开，enter 键表示输入结束； 输入结束之后，程序即进行统计。随后输出统计结果； 本次输入结束后将会输出提示信息：Do you want to have a seach again?(YES--1/NO--0)，输入1后进行下一次统计，否则退出 本程序只统计由字母字符构成的连续字符数列。

六、 测试结果

输入本次测试数据：If char int else for return void后出现的输入结果为：

七、 附录：

源程序名单：

Bse.H //全程常量、类型和变量说明单元 AWord.H //单词类型单元

List.H //有序链表类型单元

Txt.H //文本串类型单元

Match.C //主程序文件