【問題描述】

從標(biāo)準(zhǔn)輸入中讀入一個英文單詞及查找方式，在一個給定的英文常用單詞字典文件dictionary3000.txt中查找該單詞，返回查找結(jié)果（查找到返回1，否則返回0）和查找過程中單詞的比較次數(shù)。查找前，先將所有字典中單詞讀入至一個單詞表（數(shù)組）中，然后按要求進行查找。字典中單詞總數(shù)不超過3500，單詞中的字符都是英文小寫字母，并已按字典序排好序（可從課件下載區(qū)下載該字典文件）。字典中的單詞和待查找單詞的字符個數(shù)不超過20。

查找方式說明：查找方式以1~4數(shù)字表示，每個數(shù)字含義如下：

1：在單詞表中以順序查找方式查找，因為單詞表已排好序，遇到相同的或第一個比待查找的單詞大的單詞，就要終止查找；

2：在單詞表中以折半查找方式查找；

3：在單詞表中通過索引表來獲取單詞查找范圍，并在該查找范圍中以折半方式查找。索引表構(gòu)建方式為：以26個英文字母為頭字母的單詞在字典中的起始位置和單詞個數(shù)來構(gòu)建索引表，如：

字母

起始位置

單詞個數(shù)

a

0

248

b

248

167

…

…

…

該索引表表明以字母a開頭的單詞在單詞表中的開始下標(biāo)位置為0，單詞個數(shù)為248。

4：按下面給定的hash函數(shù)為字典中單詞構(gòu)造一個hash表，hash沖突時按字典序依次存放單詞。hash查找遇到?jīng)_突時，采用鏈地址法處理，在沖突鏈表中找到或未找到(遇到第一個比待查找的單詞大的單詞或鏈表結(jié)束)便結(jié)束查找。

/* compute hash value for string */

#define NHASH? 3001

#define MULT? 37

unsigned int hash(char *str)

{

?????? unsigned int h=0;

?????? char *p;

?

?????? for(p=str; *p!='\0'; p++)

????????????? h = MULT*h + *p;

?????? return h % NHASH;

}

提示：hash表可以構(gòu)建成指針數(shù)組，hash沖突的單詞形成一有序鏈表。

【輸入形式】

單詞字典文件dictionary3000.txt存放在當(dāng)前目錄下，待查找單詞和查找方式從標(biāo)準(zhǔn)輸入讀取。待查找單詞只包含英文小寫字母，與表示查找方式的整數(shù)之間以一個空格分隔。

【輸出形式】

將查找結(jié)果和單詞比較次數(shù)輸出到標(biāo)準(zhǔn)輸出上，兩整數(shù)之間以一個空格分隔。
【樣例輸入與輸出】
單詞字典文件dictionary3000.txt與課件下載中提供的相同，下面兩列中，左側(cè)為待查找單詞與查找方式，右側(cè)為對應(yīng)的輸出結(jié)果：

wins 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0 3314

wins 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0 12

wins 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0 7

wins 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0 2

yes 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 3357

yes 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 10

yes 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 4

yes 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 1
【樣例說明】

wins在單詞字典中不存在，4種查找方式都輸出結(jié)果0，順序查找、折半查找、索引查找和hash查找的單詞比較次數(shù)分別為：3314、12、7和2次（wins的hash位置與字典中physics和suggest相同）。

yes在單詞字典中存在，4種查找方式都輸出結(jié)果1，順序查找、折半查找、索引查找和hash查找的單詞比較次數(shù)分別為：3357、10、4和1。

【評分標(biāo)準(zhǔn)】

該題要求輸出查找結(jié)果和查找過程中的單詞比較次數(shù)，提交程序名為find.c。

我tm好菜啊，巨難受。