技術(shù)應(yīng)用論文：基于單鏈表和散列表比較的詞頻統(tǒng)計(jì)研究摘要:針對(duì)操作系統(tǒng)課程中的詞頻統(tǒng)計(jì)實(shí)驗(yàn),介紹兩種分別采用單鏈表和散列表進(jìn)行詞頻統(tǒng)計(jì)的方法,并著重說明后一種方法在效率方面的優(yōu)越性。

關(guān)鍵詞:單鏈表;散列表;詞頻統(tǒng)計(jì);效率

在操作系統(tǒng)課程中,詞頻統(tǒng)計(jì)實(shí)驗(yàn)具有重要的理論價(jià)值和實(shí)用價(jià)值,一直受到廣大師生的重視。該實(shí)驗(yàn)要求編寫程序,讀取一個(gè)文件,對(duì)該文件中的英文文章進(jìn)行詞頻統(tǒng)計(jì),并把統(tǒng)計(jì)結(jié)果存放到另一個(gè)文件中。程序的功能并不復(fù)雜,大多數(shù)學(xué)生都能完成,但是程序的效率往往不盡如人意。采用單鏈表和散列表進(jìn)行詞頻統(tǒng)計(jì)都是該實(shí)驗(yàn)常用的方法。從效率方面來看,后一種方法明顯優(yōu)于前一種方法。

1采用單鏈表進(jìn)行詞頻統(tǒng)計(jì)

1.1概述

在該實(shí)驗(yàn)中,大多數(shù)學(xué)生采用單鏈表進(jìn)行詞頻統(tǒng)計(jì)。這種方法簡潔明了,易于理解,但是程序每次從文件中讀取一個(gè)單詞后,都要在單鏈表中順序查找該單詞,這就大大降低了程序的效率。下面通過程序流程圖和部分代碼來說明采用單鏈表進(jìn)行詞頻統(tǒng)計(jì)的具體過程。

1.2解決方案

1.2.1數(shù)據(jù)結(jié)構(gòu)

由于程序最后要輸出各單詞及其出現(xiàn)的次數(shù),因此要聲明一個(gè)結(jié)構(gòu)體類型。分別使用char型數(shù)組和int型變量存儲(chǔ)單詞及其出現(xiàn)的次數(shù)。這樣在輸出統(tǒng)計(jì)結(jié)果時(shí),只要遍歷單鏈表即可。

typedefstructwordNode

{

charword[length];

intiWordCount;

wordNode*pNext;

}wordNode;

1.2.2程序流程圖

程序每次從文件中讀取一個(gè)單詞,刪除該單詞末尾可能帶有的標(biāo)點(diǎn)符號(hào)后,在單鏈表中順序查找該單詞。如果查找到該單詞,那么把該單詞出現(xiàn)的次數(shù)加1,不再繼續(xù)查找。如果沒有查找到該單詞,那么把該單詞插入到單鏈表的尾部,并把該單詞出現(xiàn)的次數(shù)置1。等到文件中的所有單詞都處理完畢后,輸出統(tǒng)計(jì)結(jié)果。程序流程圖如圖1所示。

1.2.3處理單詞細(xì)節(jié)

按照英文書寫習(xí)慣,標(biāo)點(diǎn)符號(hào)一般緊跟在前一個(gè)單詞之后。當(dāng)程序從文件中讀取一個(gè)單詞時(shí),由于一旦遇到空格或換行即認(rèn)為單詞讀取完畢,因此會(huì)出現(xiàn)單詞和標(biāo)點(diǎn)符號(hào)一并讀取的情況。所以要定義一個(gè)函數(shù)Clip(),刪除單詞末尾的標(biāo)點(diǎn)符號(hào)。對(duì)讀取的單詞,要判斷最后一個(gè)字符是否為字母,若不是字母則將其刪除。不過單詞末尾的標(biāo)點(diǎn)符號(hào)也存在一些特殊情況。例如,“a.m.”和“Mr.”等是特定的縮寫,最后的“.”不能刪除;“students’”最后的“’”表示復(fù)數(shù)所有格,也不能刪除。以下是函數(shù)Clip()的具體代碼,對(duì)有些特殊情況無法一一列舉,這也是該函數(shù)不完善之處。

voidClip(char*current)

{

inti;

i=strlen(current);

if(!strcmp(current,"a.m."))return;

elseif(!strcmp(current,"Dr."))

return;

elseif(!strcmp(current,"Mr."))

return;

elseif(!strcmp(current,"Mrs."))

return;

elseif(!strcmp(current,"Ms."))

return;

elseif(!strcmp(current,"p.m."))

return;

elseif((!isalpha(current[i-1]))&&(current[i-1]!='\''))

{

current[i-1]='\0';

}

}

此外,當(dāng)某個(gè)單詞出現(xiàn)在句首和句中時(shí),首字母有大小寫之分,這會(huì)導(dǎo)致使用函數(shù)strcmp()判斷它們是否相同時(shí),把它們誤判為不相同。所以要定義一個(gè)函數(shù)Change(),把單詞中的大寫字母轉(zhuǎn)化為小寫字母,以消除由于大小寫不一致而導(dǎo)致的誤判。以下是函數(shù)Change()的具體代碼。

voidChange(char*current)

{

for(;*current!='\0';current++)

{

if((*current>='A')&&(*current<='Z'))

{

*current+=32;

}

}

}

1.3分析

采用單鏈表進(jìn)行詞頻統(tǒng)計(jì)的主要操作是在單鏈表中進(jìn)行順序查找和在單鏈表尾部進(jìn)行插入。程序每次從文件中讀取一個(gè)單詞后,都要在單鏈表中順序查找該單詞。反復(fù)在單鏈表中進(jìn)行順序查找,會(huì)大大降低程序的效率。以一篇300詞的英文文章為例,在最壞情況下,即300個(gè)單詞都不一樣,單詞之間所進(jìn)行的比較次數(shù)達(dá)到0+1+2+…+298+299=44850。在該實(shí)驗(yàn)中,發(fā)現(xiàn)大多數(shù)學(xué)生使用短篇英文文章來測試程序,所以雖然