課設(shè)報告統(tǒng)計英文單詞數(shù)

1、“程序設(shè)計基礎(chǔ)”課程設(shè)計報告設(shè)計題目 統(tǒng)計英文單詞數(shù) 姓 名 學(xué) 號 專 業(yè) 班 級 （一） 需求和規(guī)格說明該系統(tǒng)的功能是給定一個英文段落（單詞個數(shù)100），利用哈希表（表長最大為20）統(tǒng)計單詞出現(xiàn)的頻度，并能根據(jù)要求顯示出給定單詞在段落中出現(xiàn)的位置。執(zhí)行程序時由用戶在鍵盤上輸入程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。 該系統(tǒng)的實現(xiàn)是通過哈希函數(shù)的建立和查找分析，用線性探測再散列來處理沖突，從而得到哈希表并實現(xiàn)哈希表的查找。該文章對哈希函數(shù)的應(yīng)用方法是使用除留余數(shù)法構(gòu)造，使用鏈地址法進行沖突處理。2.1技術(shù)可行性 哈希查找是通過計算數(shù)據(jù)元素的存儲地址進行查找的一種方法。 哈希

2、查找的操作步驟：用給定的哈希函數(shù)構(gòu)造哈希表；根據(jù)選擇的沖突處理方法解決地址沖突；在哈希表的基礎(chǔ)上執(zhí)行哈希查找。2.2需求可行性 世界上的事物都是有發(fā)展的，企圖跨越階段或者停滯，一切生命就都沒有存在的理由了。頻率就是一個既動態(tài)又靜態(tài)的東西，我們能肯定的是很多古詞和今詞是不一樣的，今日被淘汰了，也就是說，今天的頻率的統(tǒng)計是一定有確定的結(jié)論的。也有一些古詞仍在今日用著，或者在淘汰之中，所以頻率難以確定。我們知道黑天和白天是有區(qū)別的，但它們的交界點，卻不是那么容易分辨了，恐怕需要經(jīng)過科學(xué)家的精密研究。交界點不容易確定，并不意味著事物之間沒有區(qū)別。世界上的事物都是有區(qū)別又有聯(lián)系的。有些人讀書讀傻了，鉆了

3、牛角尖，他弄不清兩個事物之間的區(qū)別應(yīng)該劃在哪里，后來就連兩個事物之間有區(qū)別也不敢認定了。頻率的統(tǒng)計是為了區(qū)別常用詞和非常用詞，方法可能不準(zhǔn)確，但不至于否定常用詞和非常用詞之間的區(qū)別吧。我們應(yīng)該使統(tǒng)計精密起來?；疖嚱裉觳挥没鹆耍绻?dāng)初也不用，就沒有今天的“火車”了。事物的變化是不可能停止的，但總還有個靜態(tài)的定位，否則人們就無法認識任何事物了。頻率雖然是個復(fù)雜的問題，但科學(xué)的研究是必要的。3 需求分析 給定一個英文段落（單詞個數(shù)100），利用哈希表（表長最大為20）統(tǒng)計單詞出現(xiàn)的頻度，并能根據(jù)要求顯示出給定單詞在段落中出現(xiàn)的位置。 執(zhí)行程序時由用戶在鍵盤上輸入程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)

4、據(jù)和運算結(jié)果顯示在其后。 測試數(shù)據(jù)：給定一個英文段落顯示出不同英文單詞的出現(xiàn)頻度。給定一個英文單詞，判斷段落中是否含有該單詞，如有，依次顯示出該單詞在段落中出現(xiàn)的位置?；疽螅汗：瘮?shù)使用除留余數(shù)法構(gòu)造，使用鏈地址法進行沖突處理。（二） 設(shè)計構(gòu)造哈希函數(shù)void initial() /哈希表的初始化 for(int i(0); i100; i+) haxilisti.head=NULL; haxilisti.tail= NULL; cout哈希表初始化完成,準(zhǔn)備讀入文件,請將需要操作的文件命名為file.txt放到文件夾中endl;讀取數(shù)據(jù)：void input() /讀入文件 cout開始

5、讀入文件.endl; fstream infile;infile.open(file.txt,ios:in); if(!infile) coutFile cant be openendl; /讀入失敗 abort(); /coutthe input is called endl; char csize; while(!infile.eof() char h; infile.get(h); couthendl; while( !(A=h & h=Z|a=h & h=z) /只讀英語單詞 if(infile.eof() return; infile.get(h); /couthendl; int

6、i; i=0; while(A=h & h=Z|a=h & h=z ) if(ha) h=h-A+a; /將大寫字母轉(zhuǎn)化為小寫 ci+=h; infile.get(h); ci=0; coutendl; char*s ; s=new chari; strncpy(s,c,i); couts; coutendl;insert(s,i); infile.close(); /結(jié)束讀入產(chǎn)生哈希表： void insert( char* w,int length) /哈希表的操作:搜索和插入 int k; k=0; for(int i(0);ilength & wi!=0;i+) k+=wi; cout

7、insert is calledendl; k=k%100; coutk ; /完成插入操作 if(haxilistk.head=NULL) /此時哈希表為空 coutis blank insertnext=NULL; haxilistk.head-frequency=0; haxilistk.head-frequency+; haxilistk.head-str=w; haxilistk.tail=haxilistk.head; else /此時哈希表不為空,搜索關(guān)鍵字 word * templ; for(templ=haxilistk.head; !(strcmp(w,templ-str)

8、&templ-next!=NULL; templ=templ-next ); /搜索完畢 if(!strcmp(templ-str,w) /沒有找到關(guān)鍵字 haxilistk.tail-next=new word; haxilistk.tail=haxilistk.tail-next; haxilistk.tail-frequency+; haxilistk.tail-str=w; haxilistk.tail-next=NULL; else delete w; templ-frequency+; 主函數(shù)void main () /主函數(shù) cout *endl; cout * *endl; c

9、out * 哈希表應(yīng)用-英語單詞頻度統(tǒng)計 *endl; cout * *endl; cout *endl; initial(); input(); coutendl; cout文件讀入完畢!; coutendl; int n=0; for(int i(0);i100;i+) if(haxilisti.head!=NULL) n+; cout單詞 str頻度為 ; coutfrequencyendl; cout 在讀入的文件中共搜索到n個不同的單詞endl; （三） 用戶手冊本程序包含四個模塊：主程序模塊：void main（） 構(gòu)造哈希表函數(shù)：void initial( )讀取英文段落函數(shù)vo

10、id input (ElemType *ST,int n )查找函數(shù)：void insert( char* w,int length) 單詞文本串文件類型：ADT TextString 數(shù)據(jù)對象：D=ai | ai 屬于字母字符集，i為正整數(shù) 數(shù)據(jù)關(guān)系：D中字符被“換行符”分割成若干行，每一行的字符間滿足下類關(guān)系： R1= | ai-1,ai屬于D，i為正整數(shù) 基本操作：Initiation（&f） 初始條件：文件f已存在。 操作結(jié)果：打開文件f，設(shè)定文件指針指向第一行第一個字符。GetAWord（f，&w） 初始條件：文件f打開。 操作結(jié)果：從文件指針?biāo)缸址鹛崛∫粋€“單詞w”。Extra

11、ctWord（f，&H） 初始條件：文件f已打開，文件指針指向文件f中某一行的第一個字符。 操作結(jié)果：提取該行中所有單詞，并構(gòu)成單詞的哈希表H；本操作結(jié)束時，文件指針指向文件f中下一行的第一個字符。Match（f，pat，&Result） 初始條件：文件已打開，文件指針指向文件f中某一行的第一個字符；pat為包含所有待查詢單詞的哈希表。 操作結(jié)果：Result為查詢結(jié)果。ADT TextStringADT HashTable 數(shù)據(jù)對象：D=ai | ai 屬于AWord，i為正整數(shù) 數(shù)據(jù)關(guān)系：R1= | ai-1,ai屬于D，i為正整數(shù) 基本操作： InitialHash(HashTable&

12、) 操作結(jié)果：初始化哈希表。 PrintHash(HashTable) 初始條件：哈希表H已存在。 操作結(jié)果： 顯示哈希表H中的所有元素。 SearchHash(HashTable,int,int&) 初始條件：哈希表H已存在。 操作結(jié)果： 在哈希表H中查找元素，成功返回1，否則返回0。 InsertHash(HashTable&,Record) 初始條件：哈希表H已存在。 操作結(jié)果： 在哈希表H中插入元素，成功返回1，否則返回0。 DeleteHash(HashTable&,Record) 初始條件：哈希表H已存在。 操作結(jié)果： 在哈希表H中刪除元素，成功返回1，否則返回0。ADT Hash

13、Table 算法實現(xiàn)及哈希表類型：ADT HashTable 數(shù)據(jù)對象：D=ai | ai 屬于AWord，i為正整數(shù) 數(shù)據(jù)關(guān)系：R1= | ai-1,ai屬于D，i為正整數(shù) 基本操作： InitialHash(HashTable&) 操作結(jié)果：初始化哈希表。 PrintHash(HashTable) 初始條件：哈希表H已存在。 操作結(jié)果： 顯示哈希表H中的所有元素。 SearchHash(HashTable,int,int&) 初始條件：哈希表H已存在。 操作結(jié)果： 在哈希表H中查找元素，成功返回1，否則返回0。 InsertHash(HashTable&,Record) 初始條件：哈希表H

14、已存在。 操作結(jié)果： 在哈希表H中插入元素，成功返回1，否則返回0。 DeleteHash(HashTable&,Record) 初始條件：哈希表H已存在。 操作結(jié)果： 在哈希表H中刪除元素，成功返回1，否則返回0。ADT HashTable（四） 調(diào)試及測試在程序運行時，根據(jù)界面提示，會得到以下結(jié)果：（五） 運行實例：（六）心得體會通過對本課題的研究和系統(tǒng)的詳細設(shè)計，再到系統(tǒng)開發(fā)運行，使我對應(yīng)用系統(tǒng)的開發(fā)流程有了深刻的認識，成功完成系統(tǒng)的開發(fā)首先必須要對系統(tǒng)進行規(guī)劃，對系統(tǒng)流程進行分析，對各個模塊的功能進行設(shè)計。在編寫該程序時，主要是哈希函數(shù)的建立和查找分析，用線性探測再散列來處理沖突，從而

15、得到哈希表并實現(xiàn)哈希表的查找。發(fā)現(xiàn)運行結(jié)果中出現(xiàn)了亂碼，而且是個別單詞的統(tǒng)計結(jié)果返回時才出現(xiàn)亂碼，懷疑是標(biāo)點符號的原因，去掉標(biāo)點后還是如此；又懷疑是回車符的原因，去掉回車符仍然如此。依然沒有解決；希望老師給我找到原因。 經(jīng)過三個星期的努力，在克服了許許多多的困難之后，終于完成了課程設(shè)計，其主要的目標(biāo)和任務(wù)基本上都實現(xiàn)了。這幾個星期是對我們大學(xué)所學(xué)知識，技能的一次真正、全面的考驗，是鍛煉我們動手能力、分析能力、創(chuàng)新能力的一次難得機會。這個學(xué)期是我大學(xué)最為繁忙的一個學(xué)期，但也是最有意義、過得最充實的一個學(xué)期。由于時間短暫,設(shè)計之中還有許多不足之處，有待于今后進一步的完善。在這期間中，我得到了老師的

16、幫助和指導(dǎo)，在此向老師表示衷心的感謝。因為水平有限，我的工作還有許多不足之處，希望老師指正。（七）附錄源程序（1）#include #include #include #include #include using namespace std;#define CLOCKS_PER_SEC (time_t)1000)typedef struct _link / 定義該鏈表是為了存儲不重復(fù)出現(xiàn)的單詞 char* ch; int num; _link* next; link; int main() clock_t t_start, t_end; t_start = clock() ; cout *e

17、ndl; cout * *endl; cout * 鏈表英語單詞頻度統(tǒng)計 *endl; cout * *endl; cout *endl; coutendl; cout文件讀入完畢!; cout=a&c=A&c0) wordpos = 0; / 鏈表遍歷，比較鏈表中的節(jié)點值與當(dāng)前單詞 ptmp = head; while (ptmp) if (strcmp(word, ptmp-ch)=0) ptmp-num+; break; ptmp = ptmp-next; / 如果鏈表中沒有當(dāng)前單詞，在鏈表末尾插入節(jié)點 if (ptmp = NULL) ptmp = (link*)malloc(size

18、of(link); /注意一下兩行的用法 ptmp-ch = (char*)malloc(pos); strcpy(ptmp-ch, word); ptmp-num=1; ptmp-next = NULL; if (pnow) / 插入當(dāng)前節(jié)點為末節(jié)點 pnow-next = ptmp; pnow = ptmp; else / 此處為第一次出現(xiàn)單詞的時候 head = pnow = ptmp; pos=0; fclose(fp); / 對文件進行操作，關(guān)閉文件 / 讀取鏈表，輸出單詞及其出現(xiàn)的個數(shù) ptmp = head; FILE *fp1 = fopen(result.txt,w); wh

19、ile (ptmp) fprintf(fp1,%dt%sn, ptmp-num, ptmp-ch); ptmp = ptmp-next; fclose(fp1); ptmp = head; int i=0;while (ptmp) i+; ptmp = ptmp-next; printf(單詞總數(shù)為%dn,i); t_end = clock() ; printf(time: %f sn, double(t_end -t_start)/CLOCKS_PER_SEC) ; return 0; （2）#include#includestring.h#include#include#include #

20、include #include #define CLOCKS_PER_SEC (time_t)1000)#define size 20struct wordint frequency; /單詞出現(xiàn)的頻度 char* str; /關(guān)鍵字 word* next;struct aword /不設(shè)首結(jié)點 word* head; word* tail;#define max 100000 /定義短文的最大長度struct aword haxilist100000; /哈希表/*+*/void initial() /哈希表的初始化 for(int i(0); i100000; i+) haxilisti

21、.head=NULL; haxilisti.tail= NULL; cout哈希表初始化完成,準(zhǔn)備讀入文件,請將需要操作的文件命名為file.txt放到文件夾中endl;/*+*/void insert( char* w,int length) /哈希表的操作:搜索和插入 int k; k=0; for(int i(0);ilength&wi!=0;i+) k+=wi; /coutinsert is calledendl; k=k%100000; /coutk ; /完成插入操作 if(haxilistk.head=NULL) /此時哈希表為空, /coutis blank insertnex

22、t=NULL; haxilistk.head-frequency=0; haxilistk.head-frequency+; haxilistk.head-str=w; haxilistk.tail=haxilistk.head; else /此時哈希表不為空,搜索關(guān)鍵字 word * templ; for(templ=haxilistk.head; !(strcmp(w,templ-str)&templ-next!=NULL; templ=templ-next ); /搜索完畢 if(!strcmp(templ-str,w) /沒有找到關(guān)鍵字 haxilistk.tail-next=new word; haxilistk.tail=haxilistk.tail-next; haxilistk.tail-frequency+; haxilistk.tail-str=w; haxilistk.tail-next=NULL; else delete w;templ-frequency+; /*+*/void input() /讀入文件 cout開始讀入文件.endl; fstream infile;infile.open(file.txt,ios: