【正文】 表已滿}void ResetHX() //重置哈希表，{ int i。 return find。find++) //再找前面的位置 { tem++。 } } for(find=0。 if(strlen(HS[find].keyword)==0){ HS[find].con=tem。findHASHLEN。 if(key0||key=HASHLEN) return 1。 } return 1。 } else //該位置為空，直接將關鍵字插入該位置中 { strcpy(HS[key].keyword,keyword)。 //將關鍵字插入哈希表 } if(key0) return 1。 if(key0) return 1。 } key=FindHX(keyword)。 //計算哈希值 if(strlen(HS[key].keyword)0) //判斷關鍵字表中該位置是否存在關鍵字 { //已經存在有關鍵字 if(strcmp(HS[key].keyword,keyword)==0) { //再判斷哈希表中該位置的關鍵字是否相同 HS[key].count++。 if(!isKeyWords(keyword)) return 1。 } } return 1。 if(strcmp(HS[find].keyword,keyword)==0){ HS[find].con=tem。findkey。 return find。find++) { //線性探查法順序查找哈希表中是否已存在關鍵字 tem++。 for(find=key+1。 key=GetKey(keyword)。 //是字母就返回1，否則返回0值} int FindHX(char *keyword) //查找哈希表，分塊查找{ int key,find,tem=0。) ) return 1。ch=39。amp。)||(ch=39。ch=39。amp。}int isLetter(char ch) //判斷是否是字母，因為關鍵字都是英文單詞{ if( (ch=39。 jiemian()。 } } fclose(read)。\039。 ch=fgetc(read)。 break。 feof(read)==0) { ch=fgetc(read)。 feof(read)==0 ) { if(i==MAXLEN) { while(isLetter(ch)==1amp。 //如果不是字母的話接著讀取 while(isLetter(ch)==1 amp。amp。 ch=fgetc(read)。 } ResetHX()。 if( (read=fopen(filename,r))==NULL ) //只讀方式打開一個文本文件,只允許讀數(shù)據(jù) { cout文件不存在,請確認好再輸入!endl。 int i。 return。 case 7: break。 case 6: jiemian()。 Select(Input())。 if((i+1)%5==0) coutendl。iTOTAL。 case 5: cout C語言中的關鍵字和其在哈希表的位置:endl。 Select(Input())。 } } } if(count==0) cout沒有沖突endl。 cout\t[哈希表當前位置]: iendl。 if(key!=i) { count++。iHASHLEN。 count=0。 break。 Show(FindHX(word))。 cinword。 break。 //為了清晰，每次顯示5行 } cout關鍵字總數(shù)為：contendl。i++) { Show(i)。 for(i=0。 break。 Read(filename)。 cinfilename。 int i,key,count。 cont++。 return 。 return。 return choice。 continue。 } while(!isspace(())) //功能：判斷字符是否為空白符 //說明：當字符為空白符時，返回非零值，否則返回零。 } else { cout輸入錯誤，請重新輸入endl。 while(true) //確保輸入的為數(shù)字 { int choice=0。639。}int Input(){ coutendl。 cout\t\endl。 cout\t\endl。 cout\t\(關鍵字總數(shù)，沖突次數(shù))endl。} void jiemian()//主菜單函數(shù){ coutendl。 Select(Input())。 cout\t=================================================================endlendl。 cout\t* *endl。 cout\t* 該程序功能是統(tǒng)計一個文件中C語言關鍵字的頻度 *endl。 //先清空哈希表 cout\t=================================================================endl。 HASH HS[HASHLEN]。 //出現(xiàn)次數(shù)（頻度） int con。/****************************************************************************/class HASH //哈希表類{public: char keyword[MAXLEN]。 //出現(xiàn)次數(shù)（頻度） int con。/***********************************************************************typedef struct HASH{char keyword[MAXLEN]。int GetKey(char *keyword)。int GetFreePos(int key)。int FindHX(char *keyword)。 int isLetter(char ch)。int Read(char *filename)。void Show(int key)。 //哈希表長度int cont=0。 //39個關鍵字const int MAXLEN=10。 //max為Hash表長度函數(shù)說明：nod *creat()：讀關鍵字文件，按照關鍵字中字符字母先后順序建立二叉排序樹，每個節(jié)點中保存一個關鍵字；void init(node *head)：初始化Hash表各節(jié)點數(shù)據(jù)域；void deal(node *head,nod *parent,char filename[])：掃描源文件，分離出每個單詞，檢驗是否為關鍵字；并根據(jù)檢驗結果來決定是否調用strdeal函數(shù)，以對Hash做適當更改；void strcp(node *head,char s[],int k)：將新查找到的關鍵字復制到Hash表中第k個節(jié)點存儲單元；void strdeal(node *head,char s[],int k)：判斷Hash表中第k個單元中有無關鍵字，若無則將當前關鍵字存入該單元，返回；否則比較兩關鍵字是否相等，相等則將該單元頻數(shù)加一，返回；不相等則將該單元沖突數(shù)加一并循環(huán)線性探測下一個存儲單元；int strcmp(char t[],char s[])：字符串比較；void prin(nod *head)：以左根右的順序將二叉排序樹打印在屏幕上；
四、實現(xiàn)部分 include include stringinclude using namespace std。}nod。//二叉排序樹結構定義typedef struct nod //定義{ char s[20]。 int num,time。編寫本程序時，使用了二叉樹創(chuàng)建、二叉樹查找、Hash表的建立和操作及文件操作等基本算法。同時創(chuàng)建一Hash表，每個節(jié)點除應保存關鍵字字符串外，還應保存關鍵字頻數(shù)及該存儲單元沖突次數(shù)。用線性探測法解決Hash沖突。11一、需求分析說明本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能。5五． 程序測試4四． 實現(xiàn)部分3三． 詳細設計：利用哈希技術統(tǒng)計C源程序關鍵字出現(xiàn)頻度 目錄一． 需求分析說明3二． 總體設計10六． 總結1)題目內容：利用Hash技術統(tǒng)計某個C源程序中的關鍵字出現(xiàn)的頻度2)基本要求：掃描一個C源程序，用Hash表存儲該程序中出現(xiàn)的關鍵字，并統(tǒng)計該程序中的關鍵字出現(xiàn)的頻度。設Hash函數(shù)為：Hash(key)[(key的第一個字母序號)*100+(key的最后一個字母序號)] MOD 41二、總體設計一． 算法思想描述首先讀取關鍵字文件以建立二叉排序樹以供后續(xù)查詢，每個樹節(jié)點保存一個關鍵字字符串及指向左右子樹的指針。然后掃描一個C源程序，每次掃描一行，從中循環(huán)分離出每個單詞，每次均查找其是否為關鍵字，若是，則按計算公式計算其KEY值并在Hash表中進行相應操作，若該節(jié)點為空則插入否者比較其是否與現(xiàn)有關鍵字相同，若相同則增加其頻數(shù)，否則增加其沖突次數(shù)并繼續(xù)線性探測下一個存儲單元，完了繼續(xù)操作下一個分離出來的單詞，如此循環(huán)運行直至掃描結束。二． 三、詳細設計
(程序結構//Hash表存儲結構typedef struct node //定義{ char s[20]。 //num為頻數(shù)，time為沖突次數(shù)}node。 struct nod *left,*right。 int max。 const int TOTAL=39。 //關鍵字長度const int HASHLEN=41。 //統(tǒng)計哈希表中的關鍵字個數(shù)void jiemian()。void Select(int choice)。int Input()。int isKeyWords(char *word)。int CreatHX(char *keyword)。void ResetHX()。char KeyWords[TOTAL][MAXLEN]= //構造二維數(shù)組存儲39個關鍵字{ asm,auto,break,case,cdecl, char,const,continue,default,do, double,else,enum,extern,far, float,for,goto,huge,if, int,interrupt,long,near,pascal, register,return,short,signed,sizeof, static,struct,switch,typedef,union, unsigned,void,volatile,while, }。 int count。 //沖突次數(shù)}HASH HS[HASHLEN]。 int count。 //沖突次數(shù)}。 int main(){ ResetHX()。 cout\t* 歡迎使用該軟件，請按提示操作 *endl。 cout\t* 統(tǒng)計開始前請先讀取一個文件 *endl。 cout\t* by 黃耀廣 *endl。 jiemian()。 return(0)。 cout\t\endl。 cout\t\endl。 cout\t\(作為對照)endl。 cout\t\endl。 cout按39。回主菜單，請輸入你的