文學研究助手數(shù)據(jù)結構報告.doc

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