文學(xué)研究助手?jǐn)?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、 文學(xué)研究助手一、問題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。二、需求分析：1、 文本串非空且以文件形式存放，統(tǒng)計(jì)匹配的詞集非空。文件名和詞集均由用戶從鍵盤輸入；2、 “單詞”定義：由字母構(gòu)成的字符序列，中間不含空格字符且區(qū)分大小寫；3、 待統(tǒng)計(jì)的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置若干空格字符；4、 在計(jì)算機(jī)終端輸

2、出的結(jié)果是：單詞，出現(xiàn)的次數(shù)，出現(xiàn)的位置所在行的行號(hào)，同一行出現(xiàn)兩次的只輸出一個(gè)行號(hào)；5、 測(cè)試數(shù)據(jù)：文本文件為本次實(shí)習(xí)中的word.txt:待統(tǒng)計(jì)的詞集： he she it has to here can not is was三、概要設(shè)計(jì)： 擬采用對(duì)兩個(gè)有序表進(jìn)行相互比較的策略進(jìn)行“單詞匹配”。程序中將涉及下列三個(gè)抽象數(shù)據(jù)類型：1. 定義“單詞”類型：ADT Aword數(shù)據(jù)對(duì)象：D=Si | Si 標(biāo)準(zhǔn)c字符串集合,i = 1,2,3,.,n,n 0數(shù)據(jù)關(guān)系：R1=<Si-1,Si> | Si-1,Si D,i = 1,2,3,.,n基本操作： NewWord(WordType

3、 *nw,Sequence cha) 初始條件：cha為字符序列； 操作結(jié)果：生成一個(gè)其值為給定字符序列的單詞； WordCmp(WordType wd1,WordType wd2) 初始條件：單詞wd1和單詞wd2已存在； 操作結(jié)果：若wd1<wd2，則返回-1；若wd1=wd2，則返回0；若wd1>wd2，則返 回1； PrintWord(WordType wd) 初始條件：單詞wd已存在； 操作結(jié)果：在計(jì)算機(jī)終端上顯示單詞wd；ADT AWord2. 定義有序表類型：ADT OrderList數(shù)據(jù)對(duì)象：D=Si | Si AWord,i = 1,2,3,.,n,n 0數(shù)據(jù)關(guān)系

4、：R1=<Si-1,Si> | Si-1,Si D,Si-1<S,i = 1,2,3,.,n 基本操作： InitList(OrderList *L) 操作結(jié)果：構(gòu)造一個(gè)空的有序表； DestroyList(OrderList *L) 初始條件：有序表L已存在； 操作結(jié)果：銷毀L的結(jié)構(gòu)，并釋放所占空間； LocateElem(OrderList L,ElemType e,LinkType *q) 初始條件：有序表L已存在； 操作結(jié)果： 若有序表L中存在元素e，則q指示L中第一個(gè)值為e的元素的位置， 并返回函數(shù)值FRUE；否則q指示第一個(gè)大于e的元素的前驅(qū)的位置， 并返回函數(shù)值

5、FALSE； InsertAfter(OrderList *L,LinkType q,LinkType s) 初始條件：有序表L已存在，q指示L中一個(gè)元素； 操作結(jié)果：在有序表L中q指示的元素之后插入元素s； ListCompare(OrderList La,OrderList Lb,EqelemList *s) 初始條件：有序表La和Lb已存在； 操作結(jié)果：以s返回其中相同元素； ADT OrderList3. 定義單詞文本串文件類型如下：ADT TextString數(shù)據(jù)對(duì)象：D=Si | Si 標(biāo)準(zhǔn)c字符集,i = 1,2,3,.,n,n 0；數(shù)據(jù)關(guān)系：D中字符被“換行符”分割成若干行，每

6、一行的字符間滿足下列關(guān)系： R1=<Si-1,Si> | Si-1,Si D,i = 1,2,3,.,n 基本操作： Initialization(FILE *fr) 初始條件：文件fr已存在； 操作結(jié)果：打開文件fr，設(shè)定文件指針指向文件中第一行第一個(gè)字符；GetAWord(FILE *f,Sequence *st) 初始條件：文件f已打開； 操作結(jié)果：從文件指針?biāo)缸址鹛崛∫粋€(gè)“單詞st”；ExtractWord(FILE *f,OrderList *ta) 初始條件：文件f已打開，文件指針指向文件f中某一行的第一個(gè)字符； 操作結(jié)果：提取該行中所有單詞，并構(gòu)成單詞的有序表ta

7、，本操作結(jié)束時(shí)，文件指針 指向文件f中下一行的第一個(gè)字符；match(FILE *f,OrderList pat,ResultType rs) 初始條件：文件f已打開，文件指針指向文件f中第一個(gè)字符；pat為包含所有待查 詢單詞的有序表； 操作結(jié)果：rs為查詢結(jié)果； ADT TextString4. 本程序包含四個(gè)模塊：1） 主程序模塊：主函數(shù)設(shè)計(jì)如下int main ( ) 輸入信息和文件初始化；生成測(cè)試目標(biāo)詞匯表；統(tǒng)計(jì)文件中每個(gè)待測(cè)單詞出現(xiàn)的次數(shù)和位置；輸出測(cè)試結(jié)果；2） 單詞單元模塊-實(shí)現(xiàn)單詞類型；3） 有序表單元模塊-實(shí)現(xiàn)有序表類型；4） 單詞文本串文件單元模塊-實(shí)現(xiàn)文本串文件類型；

8、主程序模塊各模塊間的調(diào)用關(guān)系如下： 文本文件單元模塊 有序表單元模塊- 單詞單元模塊四、詳細(xì)設(shè)計(jì)1、主程序中的宏定義：#define MAXSIZE 1000/字符空間的最大容量#define MAXLEN 20 /單詞的最大長度#define MAXNUM 16 /一行中單詞最多個(gè)數(shù)#define FALSE 0#define TRUE 12、存儲(chǔ)結(jié)構(gòu)/*堆結(jié)構(gòu)的定義*/typedef struct char storesMAXSIZE; int freep; /*當(dāng)前可用空間開始位置*/ HeapSpace;HeapSpace sp;/*單詞數(shù)據(jù)類型定義*/typedef struct /

9、單詞在堆中的位置描述 int stadr; /*單詞在對(duì)空間中的開始位置*/ int len; /*單詞長度*/ WordType;typedef struct /單詞描述 char chMAXLEN; /*單詞字符串*/ int size; /*單詞長度*/ Sequence;/*有序表類型定義*/typedef WordType ElemType;typedef struct NodeType /單詞有序表結(jié)點(diǎn)定義 ElemType data; struct NodeType *next; NodeType,*LinkType;typedef struct /單詞有序表定義 LinkTyp

10、e head; /*有序表頭指針*/ LinkType tail; /*有序表尾指針*/ int size; /*有序表結(jié)點(diǎn)個(gè)數(shù)*/ OrderList;/*記錄一行中匹配成功單詞在目標(biāo)詞匯表中的位置*/typedef struct int eqelemMAXNUM; /*單詞在目標(biāo)詞匯表中的位置*/ int last; /*匹配成功單詞的個(gè)數(shù)*/ EqelemList;/*文件測(cè)試相關(guān)的數(shù)據(jù)類型定義*/typedef struct Node /單詞在文件中的位置 int elem; /*被測(cè)單詞在文件中的行號(hào)*/ struct Node *next;/*指向下一個(gè)行號(hào)結(jié)點(diǎn)的指針*/ Node

11、,*Link;typedef struct /單詞統(tǒng)計(jì)分析記錄結(jié)構(gòu)定義 WordType data; /*被測(cè)試的單詞*/ int count; /*在文件中出現(xiàn)的次數(shù)*/ Link Next; /*記錄出現(xiàn)的所有行號(hào)的臉表頭指針*/ HeadNode;/*文本文件測(cè)試結(jié)果記錄定義*/typedef HeadNode ResultTypeMAXNUM;typedef int status;3、主要算法設(shè)計(jì)：/*-與單詞相關(guān)的函數(shù)-*/*-*/* 定義新單詞函數(shù) */* 功能：把新單詞放入堆中 */* 參數(shù)：WordType *nw-單詞描述信息指針 */* Sequence cha-單詞信息

12、*/* 返回值：操作成功與否的狀態(tài)信息 */* 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;/*-*/* 復(fù)制單詞信息函數(shù) */* 功能：把一個(gè)單詞信息復(fù)制到另一個(gè)變量中 */* 參數(shù)：WordType *nw-新單詞描述信息指針 */* WordType *oldw-舊單詞描述

14、信息指針 */* 返回值：無 */*-*/void CopyWord(WordType *nw,WordType oldw) nw->stadr=oldw.stadr; nw->len=oldw.len;/*-*/* 單詞比較函數(shù) */* 功能：比較堆中兩單詞的大小 */* 參數(shù)：WordType wd1-第一個(gè)單詞描述信息 */* WordType wd2-第二個(gè)單詞描述信息 */* 返回值：-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; /*-*/* 打印單詞函數(shù) */* 功能：打印堆中一個(gè)單詞 */* 參數(shù)：WordType wd-單詞描述信息 */* 返回值：無 */*-*/void PrintWord(WordType wd) int i; for(i=0;i<wd.len;i+) p

17、utchar(sp.storeswd.stadr+i); /*-與有序表相關(guān)的函數(shù)-*/*-*/* 結(jié)點(diǎn)生成函數(shù) */* 功能：生成一個(gè)單詞在堆中存儲(chǔ)信息的結(jié)點(diǎn) */* 參數(shù)：LinkType *p-生成的新結(jié)點(diǎn)指針 */* ElemType e-單詞存儲(chǔ)信息 */* 返回值：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; /*-*/* 有序表初始化函數(shù) */* 功能：申請(qǐng)頭結(jié)點(diǎn)，初始化有序表 */* 參數(shù)：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;/*-*/* 撤銷有序表函數(shù) */* 功能：釋放有序表所有結(jié)點(diǎn)，撤銷有序表 */* 參數(shù)：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;/*-*/* 有序表查找函數(shù) */* 功能：確定給定單詞e在有序表中的位置 */* 參數(shù)：OrderList

20、 L-有序表 */* ElemType e-給定要查找的數(shù)據(jù)e */* LinkType *q-有序表結(jié)點(diǎn)指針 */* 查找成功，q指向具有e值的結(jié)點(diǎn) */* 查找失敗，q指向小于e的結(jié)點(diǎn) */* 返回值：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; /*-*/* 有序表插入函數(shù) */* 功能：在制定結(jié)點(diǎn)q后插入一個(gè)結(jié)點(diǎn)s */* 參數(shù)：OrderList *L-有序表指針 */* LinkType q-指定結(jié)點(diǎn)指針 */* LinkType s-待查入結(jié)點(diǎn)指針 */* 返回值：無 */*-*/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+; /*-*/* 表匹配函數(shù) */* 功能：把Lb表中匹配La表成功的元素放入s表 */* 參數(shù)：OrderList La-存放統(tǒng)計(jì)單詞的有序表 */* 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;/*-*/* 判表空函數(shù) */* 功能：判斷表L是否是空表 */* 參數(shù)：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 ;/*-與文本文件有關(guān)的函數(shù)-*/*-*/* 字符判斷函數(shù) */* 功能：判斷文件中下一個(gè)字符是否為回車符 */* 參數(shù)：FILE *f-文件指針 */* 返回值：0-不是回車符；1-是回車符 */*-*/int feoln(FILE *f) char

25、cha; cha=fgetc(f); if(cha='n') return(TRUE); ungetc(cha,f); return FALSE;/*-*/* 讀取單詞函數(shù) */* 功能：從文件中讀取一個(gè)單詞 */* 參數(shù)：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=' '/*最后一個(gè)為回車鍵，文件指針回指*/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;/*-*/* 讀取文件當(dāng)前行單詞函數(shù) */* 功能：提取文件指針?biāo)感兴袉卧~ */* 參數(shù)：FILE *f-文件指針 */* OrderList *ta-存放單詞有序表的指針 */* 返回值：0-操作失?。?-操作成功 */*-*/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);/*從文件中讀出一個(gè)單詞*/ NewWord(&nwd,str);/*將單詞放入堆存儲(chǔ)空間*/ MakeNode(&s,nwd);/*生成一個(gè)單詞節(jié)點(diǎn)*/ 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;/*-*/* 文件單詞匹配函數(shù) */* 功能：統(tǒng)計(jì)指定單詞在文件中出現(xiàn)的次數(shù)和位置 */* 參數(shù)：FILE *f-文件指針 */* OrderList pat-指定統(tǒng)計(jì)的單詞有序表 */* ResultType rs-統(tǒng)計(jì)結(jié)果列表 */* 返回值：0-統(tǒng)計(jì)失??；1-統(tǒng)計(jì)成功 */*-*/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)/*計(jì)算出單詞出現(xiàn)行號(hào)以及一行出現(xiàn)次數(shù)*/p=(Link)malloc(sizeof(Node); p->next=rseqlist.eqelemi.Next; rseqlist.eqelemi.Next=p; p->elem=linenum; rseqlist.eqelemi.count+; i+;/*內(nèi)層while*/linenum

31、+;/*行數(shù)加1*/DestroyList(&sa); NewLength(pat);/*外層while*/fclose(f); return TRUE;/*-*/* 初始化文件函數(shù) */* 功能：輸入指定的文件名并打開文件 */* 參數(shù)：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; /*-*/* 輸入統(tǒng)計(jì)的詞集函數(shù) */* 功能：輸入待統(tǒng)計(jì)的詞集并建立起數(shù)據(jù)結(jié)構(gòu) */* 參數(shù)：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; /*-*/* 初始化統(tǒng)計(jì)結(jié)果表函數(shù) */* 功能：用待統(tǒng)計(jì)詞集初始化統(tǒng)計(jì)結(jié)果表 */* 參數(shù)：ResultType rs-統(tǒng)計(jì)結(jié)果數(shù)組 */* OrderList pt-待統(tǒng)計(jì)的詞集表 */* 返回值：無 */*-*/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; /*-*/* 輸出統(tǒng)計(jì)結(jié)果函數(shù) */* 功能：輸出統(tǒng)計(jì)的結(jié)果 */* 參數(shù)：ResultType rs-統(tǒng)計(jì)結(jié)果數(shù)組 */* int n-待統(tǒng)計(jì)的詞集個(gè)數(shù) */* 返回值：無 */*-*/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");/*-*/* 撤銷統(tǒng)計(jì)結(jié)果數(shù)據(jù)空間函數(shù) */* 功能：釋放存放統(tǒng)計(jì)結(jié)果數(shù)據(jù)的動(dòng)態(tài)存儲(chǔ)空間 */* 參數(shù)：ResultType rs-統(tǒng)計(jì)結(jié)果數(shù)組 */* 返回值：無 */*-*/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