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

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

2、出的結(jié)果是：單詞，出現(xiàn)的次數(shù)，出現(xiàn)的位置所在行的行號，同一行出現(xiàn)兩次的只輸出一個行號；5、 測試數(shù)據(jù)：文本文件為本次實習(xí)中的word.txt:待統(tǒng)計的詞集： he she it has to here can not is was三、概要設(shè)計： 擬采用對兩個有序表進行相互比較的策略進行“單詞匹配”。程序中將涉及下列三個抽象數(shù)據(jù)類型：1. 定義“單詞”類型：adt aword數(shù)據(jù)對象：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é)果：生成一個其值為給定字符序列的單詞； wordcmp(wordtype wd1,wordtype wd2) 初始條件：單詞wd1和單詞wd2已存在； 操作結(jié)果：若wd1<wd2，則返回-1；若wd1=wd2，則返回0；若wd1>wd2，則返 回1； printword(wordtype wd) 初始條件：單詞wd已存在； 操作結(jié)果：在計算機終端上顯示單詞wd；adt aword2. 定義有序表類型：adt orderlist數(shù)據(jù)對象：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)造一個空的有序表； destroylist(orderlist *l) 初始條件：有序表l已存在； 操作結(jié)果：銷毀l的結(jié)構(gòu)，并釋放所占空間； locateelem(orderlist l,elemtype e,linktype *q) 初始條件：有序表l已存在； 操作結(jié)果： 若有序表l中存在元素e，則q指示l中第一個值為e的元素的位置， 并返回函數(shù)值frue；否則q指示第一個大于e的元素的前驅(qū)的位置， 并返回函數(shù)值

5、false； insertafter(orderlist *l,linktype q,linktype s) 初始條件：有序表l已存在，q指示l中一個元素； 操作結(jié)果：在有序表l中q指示的元素之后插入元素s； listcompare(orderlist la,orderlist lb,eqelemlist *s) 初始條件：有序表la和lb已存在； 操作結(jié)果：以s返回其中相同元素； adt orderlist3. 定義單詞文本串文件類型如下：adt textstring數(shù)據(jù)對象：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è)定文件指針指向文件中第一行第一個字符；getaword(file *f,sequence *st) 初始條件：文件f已打開； 操作結(jié)果：從文件指針?biāo)缸址鹛崛∫粋€“單詞st”；extractword(file *f,orderlist *ta) 初始條件：文件f已打開，文件指針指向文件f中某一行的第一個字符； 操作結(jié)果：提取該行中所有單詞，并構(gòu)成單詞的有序表ta

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

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

9、單詞在堆中的位置描述 int stadr; /*單詞在對空間中的開始位置*/ int len; /*單詞長度*/ wordtype;typedef struct /單詞描述 char chmaxlen; /*單詞字符串*/ int size; /*單詞長度*/ sequence;/*有序表類型定義*/typedef wordtype elemtype;typedef struct nodetype /單詞有序表結(jié)點定義 elemtype data; struct nodetype *next; nodetype,*linktype;typedef struct /單詞有序表定義 linktyp

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

11、,*link;typedef struct /單詞統(tǒng)計分析記錄結(jié)構(gòu)定義 wordtype data; /*被測試的單詞*/ int count; /*在文件中出現(xiàn)的次數(shù)*/ link next; /*記錄出現(xiàn)的所有行號的臉表頭指針*/ headnode;/*文本文件測試結(jié)果記錄定義*/typedef headnode resulttypemaxnum;typedef int status;3、主要算法設(shè)計：/*-與單詞相關(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ù) */* 功能：把一個單詞信息復(fù)制到另一個變量中 */* 參數(shù)：wordtype *nw-新單詞描述信息指針 */* wordtype *oldw-舊單詞描述

14、信息指針 */* 返回值：無 */*-*/void copyword(wordtype *nw,wordtype oldw) nw->stadr=oldw.stadr; nw->len=oldw.len;/*-*/* 單詞比較函數(shù) */* 功能：比較堆中兩單詞的大小 */* 參數(shù)：wordtype wd1-第一個單詞描述信息 */* wordtype wd2-第二個單詞描述信息 */* 返回值：-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ù) */* 功能：打印堆中一個單詞 */* 參數(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é)點生成函數(shù) */* 功能：生成一個單詞在堆中存儲信息的結(jié)點 */* 參數(shù)：linktype *p-生成的新結(jié)點指針 */* elemtype e-單詞存儲信息 */* 返回值：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ù) */* 功能：申請頭結(jié)點，初始化有序表 */* 參數(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é)點，撤銷有序表 */* 參數(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é)點指針 */* 查找成功，q指向具有e值的結(jié)點 */* 查找失敗，q指向小于e的結(jié)點 */* 返回值：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é)點q后插入一個結(jié)點s */* 參數(shù)：orderlist *l-有序表指針 */* linktype q-指定結(jié)點指針 */* linktype s-待查入結(jié)點指針 */* 返回值：無 */*-*/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)計單詞的有序表 */* 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ù) */* 功能：判斷文件中下一個字符是否為回車符 */* 參數(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ù) */* 功能：從文件中讀取一個單詞 */* 參數(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=' '/*最后一個為回車鍵，文件指針回指*/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-操作失??；1-操作成功 */*-*/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);/*從文件中讀出一個單詞*/ newword(&nwd,str);/*將單詞放入堆存儲空間*/ makenode(&s,nwd);/*生成一個單詞節(jié)點*/ 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)計指定單詞在文件中出現(xiàn)的次數(shù)和位置 */* 參數(shù)：file *f-文件指針 */* orderlist pat-指定統(tǒng)計的單詞有序表 */* resulttype rs-統(tǒng)計結(jié)果列表 */* 返回值：0-統(tǒng)計失??；1-統(tǒng)計成功 */*-*/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)/*計算出單詞出現(xiàn)行號以及一行出現(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)計的詞集函數(shù) */* 功能：輸入待統(tǒng)計的詞集并建立起數(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)計結(jié)果表函數(shù) */* 功能：用待統(tǒng)計詞集初始化統(tǒng)計結(jié)果表 */* 參數(shù)：resulttype rs-統(tǒng)計結(jié)果數(shù)組 */* orderlist pt-待統(tǒng)計的詞集表 */* 返回值：無 */*-*/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)計結(jié)果函數(shù) */* 功能：輸出統(tǒng)計的結(jié)果 */* 參數(shù)：resulttype rs-統(tǒng)計結(jié)果數(shù)組 */* int n-待統(tǒng)計的詞集個數(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)計結(jié)果數(shù)據(jù)空間函數(shù) */* 功能：釋放存放統(tǒng)計結(jié)果數(shù)據(jù)的動態(tài)存儲空間 */* 參數(shù)：resulttype rs-統(tǒng)計結(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 t