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

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

《数据结构课程设计文学研究助手.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计文学研究助手.docx（31页珍藏版）》请在冰点文库上搜索。

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

一、问题描述：

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。

试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

英文小说存于一个文本文件中。

待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。

程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

二、需求分析：

1、文本串非空且以文件形式存放，统计匹配的词集非空。

文件名和词集均由用户从键盘输入；

2、“单词”定义：

由字母构成的字符序列，中间不含空格字符且区分大小写；

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

4、在计算机终端输出的结果是：

单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；

5、测试数据：

文本文件为本次实习中的word.txt:

待统计的词集：

hesheithastoherecannotiswas

三、概要设计：

拟采用对两个有序表进行相互比较的策略进行“单词匹配”。

程序中将涉及下列三个抽象数据类型：

1.定义“单词”类型：

ADTAword{

数据对象：

D={Si|Si∈标准c字符串集合,i=1,2,3,…….,n,n≥0}

数据关系：

R1={}|Si-1,Si∈D,i=1,2,3,…..,n}

基本操作：

NewWord（WordType*nw,Sequencecha）

初始条件：

cha为字符序列；

操作结果：

生成一个其值为给定字符序列的单词；

WordCmp（WordTypewd1,WordTypewd2）

初始条件：

单词wd1和单词wd2已存在；

操作结果：

若wd1wd2，则返

回1；

PrintWord（WordTypewd）

初始条件：

单词wd已存在；

操作结果：

在计算机终端上显示单词wd；

}ADTAWord

2.定义有序表类型：

ADTOrderList{

数据对象：

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（OrderListL,ElemTypee,LinkType*q）

初始条件：

有序表L已存在；

操作结果：

若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，

并返回函数值FRUE；否则q指示第一个大于e的元素的前驱的位置，

并返回函数值FALSE；

InsertAfter（OrderList*L,LinkTypeq,LinkTypes）

初始条件：

有序表L已存在，q指示L中一个元素；

操作结果：

在有序表L中q指示的元素之后插入元素s；

ListCompare（OrderListLa,OrderListLb,EqelemList*s）

初始条件：

有序表La和Lb已存在；

操作结果：

以s返回其中相同元素；

}ADTOrderList

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

ADTTextString{

数据对象：

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,OrderListpat,ResultTypers）

初始条件：

文件f已打开，文件指针指向文件f中第一个字符；pat为包含所有待查

询单词的有序表；

操作结果：

rs为查询结果；

}ADTTextString

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

1）主程序模块：

主函数设计如下

intmain（）{

输入信息和文件初始化；

生成测试目标词汇表；

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

输出测试结果；

}；

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

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

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

各模块间的调用关系如下：

四、详细设计

1、主程序中的宏定义：

#defineMAXSIZE1000//字符空间的最大容量

#defineMAXLEN20//单词的最大长度

#defineMAXNUM16//一行中单词最多个数

#defineFALSE0

#defineTRUE1

2、存储结构

/**

*堆结构的定义

*/

typedefstruct{

charstores[MAXSIZE];

intfreep;/*当前可用空间开始位置*/

}HeapSpace;

HeapSpacesp;

/**

*单词数据类型定义

*/

typedefstruct{//单词在堆中的位置描述

intstadr;/*单词在对空间中的开始位置*/

intlen;/*单词长度*/

}WordType;

typedefstruct{//单词描述

charch[MAXLEN];/*单词字符串*/

intsize;/*单词长度*/

}Sequence;

/**

*有序表类型定义

*/

typedefWordTypeElemType;

typedefstructNodeType{//单词有序表结点定义

ElemTypedata;

structNodeType*next;

}NodeType,*LinkType;

typedefstruct{//单词有序表定义

LinkTypehead;/*有序表头指针*/

LinkTypetail;/*有序表尾指针*/

intsize;/*有序表结点个数*/

}OrderList;

/**

*记录一行中匹配成功单词在目标词汇表中的位置

*/

typedefstruct{

inteqelem[MAXNUM];/*单词在目标词汇表中的位置*/

intlast;/*匹配成功单词的个数*/

}EqelemList;

/**

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

*/

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

intelem;/*被测单词在文件中的行号*/

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

}Node,*Link;

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

WordTypedata;/*被测试的单词*/

intcount;/*在文件中出现的次数*/

LinkNext;/*记录出现的所有行号的脸表头指针*/

}HeadNode;

/**

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

*/

typedefHeadNodeResultType[MAXNUM];

typedefintstatus;

3、主要算法设计：

/*---------------------与单词相关的函数---------------------*/

/*------------------------------------------------------------------*/

/*定义新单词函数*/

/*功能：

把新单词放入堆中*/

/*参数：

WordType*nw--单词描述信息指针*/

/*Sequencecha--单词信息*/

/*返回值：

操作成功与否的状态信息*/

/*0--操作失败，空间不足；1--操作成功*/

/*--------------------------------------------------------------*/

statusNewWord（WordType*nw,Sequencecha）

{

inti,k;

if（sp.freep+cha.size>=MAXSIZE）

{

printf（"HeapFull!

\n"）;

getchar（）;

return0;

}

else

{

i=sp.freep;

sp.freep=sp.freep+cha.size;

for（k=0;k

nw->stadr=i;

nw->len=cha.size;

return1;

}

}

/*------------------------------回到最初空间-------------------*/

voidNewLength（OrderListrs）

{

intm=0;

LinkTypep,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--旧单词描述信息指针*/

/*返回值：

无*/

/*----------------------------------------------------------------*/

voidCopyWord（WordType*nw,WordTypeoldw）

{

nw->stadr=oldw.stadr;

nw->len=oldw.len;

}

/*------------------------------------------------------------------*/

/*单词比较函数*/

/*功能：

比较堆中两单词的大小*/

/*参数：

WordTypewd1--第一个单词描述信息*/

/*WordTypewd2--第二个单词描述信息*/

/*返回值：

-1--小于；0--等于；1--大于*/

/*--------------------------------------------------------------*/

intWordCmp（WordTypewd1,WordTypewd2）

{

intk,si,sj,m;

si=wd1.stadr;sj=wd2.stadr;

for（k=0;k<=wd1.len&&k<=wd2.len;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）return0;

else

if（sp.stores[si+k]>sp.stores[sj+k]）return1;

elsereturn-1;

}

elseif（wd1.len

{

if（k==wd1.len）return-1;

else

if（sp.stores[si+k]>sp.stores[sj+k]）return1;

elsereturn-1;

}

else

{

if（k==wd2.len）return1;

else

if（sp.stores[si+k]>sp.stores[sj+k]）return1;

elsereturn-1;

}

}

/*------------------------------------------------------------------*/

/*打印单词函数*/

/*功能：

打印堆中一个单词*/

/*参数：

WordTypewd--单词描述信息*/

/*返回值：

无*/

/*------------------------------------------------------------------*/

voidPrintWord（WordTypewd）

{

inti;

for（i=0;i

}

/*-------------------与有序表相关的函数----------------------*/

/*-------------------------------------------------------------------*/

/*结点生成函数*/

/*功能：

生成一个单词在堆中存储信息的结点*/

/*参数：

LinkType*p--生成的新结点指针*/

/*ElemTypee--单词存储信息*/

/*返回值：

TRUE--成功；FALSE--失败*/

/*-----------------------------------------------------------------*/

statusMakeNode（LinkType*p,ElemTypee）

{

*p=（LinkType）malloc（sizeof（NodeType））;

if（!

（*p））returnFALSE;

（*p）->data.stadr=e.stadr;

（*p）->data.len=e.len;

（*p）->next=NULL;

returnTRUE;

}

/*------------------------------------------------------------------------*/

/*有序表初始化函数*/

/*功能：

申请头结点，初始化有序表*/

/*参数：

OrderList*L--有序表指针*/

/*返回值：

TRUE--初始化成功；FALSE--初始化失败*/

/*------------------------------------------------------------------------*/

statusInitList（OrderList*L）

{

ElemTypewd;

wd.len=0;

if（MakeNode（&（L->head）,wd））

{

L->tail=L->head;

L->head->next=NULL;

L->size=0;

returnTRUE;

}

else

{

L->head=NULL;

returnFALSE;

}

}

/*------------------------------------------------------------------*/

/*撤销有序表函数*/

/*功能：

释放有序表所有结点，撤销有序表*/

/*参数：

OrderList*L--有序表指针*/

/*返回值：

无*/

/*------------------------------------------------------------------*/

voidDestroyList（OrderList*L）

{

LinkTypep,q;

p=L->head;

while（p）{

q=p;p=p->next;

free（q）;

}

L->head=L->tail=NULL;

}

/*-------------------------------------------------------------------*/

/*有序表查找函数*/

/*功能：

确定给定单词e在有序表中的位置*/

/*参数：

OrderListL--有序表*/

/*ElemTypee--给定要查找的数据e*/

/*LinkType*q--有序表结点指针*/

/*查找成功，q指向具有e值的结点*/

/*查找失败，q指向小于e的结点*/

/*返回值：

int型，1--查找成功；0--查找失败*/

/*-----------------------------------------------------------------*/

statusLocateElem（OrderListL,ElemTypee,LinkType*q）

{

LinkTypepre,p;

p=L.head->next;

while（p）{

if（WordCmp（p->data,e）==0）{*q=p;returnTRUE;}

if（WordCmp（p->data,e）==-1）*q=p;

p=p->next;

}

returnFALSE;

}

/*------------------------------------------------------------------*/

/*有序表插入函数*/

/*功能：

在制定结点q后插入一个结点s*/

/*参数：

OrderList*L--有序表指针*/

/*LinkTypeq--指定结点指针*/

/*LinkTypes--待查入结点指针*/

/*返回值：

无*/

/*---------------------------------------------------------------*/

voidInsertAfter（OrderList*L,LinkTypeq,LinkTypes）

{

if（L->head&&q&&s）{

s->next=q->next;q->next=s;

if（L->tail==q）L->tail=s;

L->size++;

}

}

/*------------------------------------------------------------------------*/

/*表匹配函数*/

/*功能：

把Lb表中匹配La表成功的元素放入s表*/

/*参数：

OrderListLa--存放统计单词的有序表*/

/*OrderListLb--存放待匹配单词的有序表*/

/*EqelemList*s--存放匹配成功单词信息表指针*/

/*返回值：

无*/

/*-------------------------------------------------------------------------*/

voidListCompare（OrderListLa,OrderListLb,EqelemList*s）

{

intpos,n;

LinkTypepa,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;

}

elseif（n==-1）{

pa=pa->next;

pos++;

}

elsepb=pb->next;

}

}

}

/*--------------------------------------------------------*/

/*判表空函数*/

/*功能：

判断表L是否是空表*/

/*参数：

OrderListL--有序表*/

/*返回值：

0--非空表；1--空表*/

/*--------------------------------------------------------*/

statusListEmpty（OrderList*L）

{

if（L->size==0）returnTRUE;

returnFALSE;

}

intListLength（OrderList*L）{/*返回判表长度*/

if（L->head==L->tail）return0;

elsereturnL->size;

}

/*-----------与文本文件有关的函数-----------------------*/

/*---------------------------------------------------------------*/

/*字符判断函数*/

/*功能：

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

/*参数：

FILE*f--文件指针*/

/*返回值：

0--不是回车符；1--是回车符*/

/*---------------------------------------------------------------*/

intfeoln（FILE*f）

{

charcha;

cha=fgetc（f）;

if（cha=='\n'）return（TRUE）;

ungetc（cha,f）;

returnFALSE