文學(xué)研究助手?jǐn)?shù)據(jù)結(jié)構(gòu)報(bào)告.doc

專(zhuān)業(yè)資料學(xué)號(hào) 武漢理工大學(xué)華夏學(xué)院課 程 設(shè) 計(jì)課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) 題 目 文學(xué)研究助手 專(zhuān) 業(yè) 班 級(jí) 姓 名 _ _ _ 成 績(jī) _ 年 月 日文學(xué)研究助手設(shè)計(jì)目的 （1）使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類(lèi)型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?（2）使學(xué)生掌握數(shù)據(jù)庫(kù)設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。 （3）使學(xué)生學(xué)會(huì)使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。問(wèn)題描述文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱(chēng)為“文學(xué)研究助手”?；疽笥⑽男≌f(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì)。算法思想 本次課程設(shè)計(jì)使用的是串模式匹配的KMP算法，模式匹配算法KMP為普通模式匹配的改進(jìn)，優(yōu)點(diǎn)在與時(shí)間復(fù)雜度由原來(lái)的O（n*m）變?yōu)镺（n+m）,即是說(shuō)統(tǒng)計(jì)時(shí)間大大縮短。當(dāng)要統(tǒng)計(jì)的詞匯量很大時(shí)，計(jì)算機(jī)統(tǒng)計(jì)所需時(shí)間將很漫長(zhǎng)，如果使用者急需使用統(tǒng)計(jì)結(jié)果，這是又因?yàn)榻y(tǒng)計(jì)太慢導(dǎo)致研究受阻，這樣就得不償失了。而本程序?qū)⒋蟠蟾纳七@種狀況，讓計(jì)算機(jī)在短時(shí)間內(nèi)統(tǒng)計(jì)出使用者想要的統(tǒng)計(jì)結(jié)果。本程序雖然精簡(jiǎn)，但是對(duì)模式匹配算法KMP的使用極其靈活，需靈活調(diào)用模式匹配算法KMP的函數(shù)來(lái)快速解決問(wèn)題。該算法的核心思想是：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不需要回測(cè)指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。模塊劃分本次課程設(shè)計(jì)所用到的程序主要包含四個(gè)模塊，分別是主程序模塊、有序表單元模塊、單詞單元模塊和單詞文本串文件單元模塊。其中主程序模塊需要實(shí)現(xiàn)的功能是，輸入文本并統(tǒng)計(jì)文件中每個(gè)需要測(cè)試的單詞出現(xiàn)的次數(shù)和位置，并輸出結(jié)果。源程序#include #include #define MAXSTRLEN 255 /最大串長(zhǎng)typedef char SStringMAXSTRLEN+1; int nextMAXSTRLEN; /KMP算法中用到的nextint Index(SString S,SString T,int pos) /KMP算法int i=pos,j=1; while(i=S0&jT0) return (i-T0); else return 0;int lenth(SString str) /求串長(zhǎng)int i=1;while(stri) i+;return(i-1);void find(char name,SString keys) /查找函數(shù) SString text; /用于存放從小說(shuō)文件讀取的一行字符串 int i=1,j=0,k,q=0; /i用于存放行號(hào)，j用于存放列號(hào),k用于輸出格式的控制,q用于統(tǒng)計(jì)出現(xiàn)次數(shù)FILE *fp;if (!(fp=(fopen(name,r) /打開(kāi)小說(shuō)文件printf(打開(kāi)文件出錯(cuò)!n);exit(0); keys0=lenth(keys); /求關(guān)鍵字的長(zhǎng)度printf(n%sn,&keys1); /打印關(guān)鍵字while (!feof(fp) /如果還沒(méi)到小說(shuō)文件末尾，則繼續(xù)循環(huán)k=0;fgets(&text1,MAXSTRLEN,fp); /從小說(shuō)文件中讀取一行字符串，存入text串中text0=lenth(text); /求讀入的串的長(zhǎng)度j=Index(text,keys,j+1); /調(diào)用KMP算法，統(tǒng)計(jì)關(guān)鍵字在該行出現(xiàn)的位置，若匹配不成功則返回0if (j!=0)printf(行=%d,列=%d,i,j); k+; /若匹配成功則打印行號(hào)和列號(hào)while(j!=0) /若該行找到了關(guān)鍵字，則繼續(xù)尋找看是否還能匹配成功j=Index(text,keys,j+1); /調(diào)用KMP算法從剛找到的列號(hào)后一字符起匹配if (j!=0) printf(,%d,j);k+; /若匹配成功，則打印列號(hào)i+; /行號(hào)加1，在下一行中尋找q+=k; /累加k以統(tǒng)計(jì)關(guān)鍵字出現(xiàn)次數(shù)if (k)printf(n);/輸出格式控制printf(%s出現(xiàn)%d次。n,&keys1,q);/打印關(guān)鍵字出現(xiàn)次數(shù)void main()char name50; /存儲(chǔ)輸入的小說(shuō)路徑字符串SString words10; /定義字符串?dāng)?shù)組，用于存儲(chǔ)輸入的關(guān)鍵字int m,n,i;printf(-歡迎使用文學(xué)研究助手-);/打印標(biāo)題while(1)/不停循環(huán)，直至完成查詢(xún)或者退出服務(wù)printf(是否需要為你服務(wù)：需要輸入1，不需要輸入0。n);scanf(%d,&m);/輸入判斷是否需要服務(wù)if(m=1)/需要服務(wù)時(shí)執(zhí)行printf(輸入你想查詢(xún)的文檔名字:n);scanf(%s,name);/輸入文件名printf(輸入查詢(xún)字符串的個(gè)數(shù)：n);scanf(%d,&n);/輸入查詢(xún)字符串個(gè)數(shù)printf(輸入你要查詢(xún)的字符串:n);for (i=0;in;i+)scanf(%s,&wordsi1); /用戶(hù)一次性輸入要查找的關(guān)鍵字，wordsi0用于存放字符串的長(zhǎng)度f(wàn)or (i=0;in;i+)find(name,wordsi); /對(duì)于每一個(gè)關(guān)鍵字，調(diào)用查找函數(shù)進(jìn)行查找統(tǒng)計(jì)break;else if(m=0)/不需要服務(wù)時(shí)執(zhí)行break;else printf(輸入錯(cuò)誤!nn);/輸入不合規(guī)范時(shí)執(zhí)行system(pause);程序測(cè)試將所設(shè)計(jì)的程序輸入c+軟件，經(jīng)組建編譯后結(jié)果如下：程序能正常編譯，說(shuō)明程序沒(méi)有問(wèn)題。程序運(yùn)行結(jié)果如下： 程序能夠正常運(yùn)行，各功能也能正常實(shí)現(xiàn)。總結(jié)和體會(huì) 通過(guò)本次課程設(shè)計(jì)，我掌握了數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫(xiě)等基本方法，并學(xué)會(huì)了如何設(shè)計(jì)完整的程序，利用數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序來(lái)解決問(wèn)題。本次課程設(shè)計(jì)中，使用的算法主要為KMP算法，程序的執(zhí)行流程大概為，先輸入文章到文件中去，在將文件中的文章付給全局?jǐn)?shù)組，然后輸入你想測(cè)試的單詞個(gè)數(shù)，然后在輸入測(cè)試的單詞，最后用KMP算法進(jìn)行模式匹配。在編寫(xiě)程序的過(guò)程中，我遇到了一些問(wèn)題，在翻閱資料以及請(qǐng)教同學(xué)后，終于完整的設(shè)計(jì)出這個(gè)程序。在程序中，盡量注釋每個(gè)語(yǔ)句的含義，這樣既方便別人查看程序，也方便自己能夠快速發(fā)現(xiàn)程序中出