數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(散列表計(jì)算程序相近度)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

對(duì)于兩個(gè)C程序，設(shè)計(jì)并實(shí)現(xiàn)兩種不同的基于散列表的檢測(cè)算法,

計(jì)算兩個(gè)程序的相近度，并分析比較兩種算法的效率。

—散列表

班級(jí)：軟件112班

姓名：劉路峰

指導(dǎo)教師：蘭紅

成績(jī)：

立月理J大學(xué)信息工程學(xué)院

2013年1月6日

目錄

1需求分析........................................................3

1.1主要任務(wù)...............................................................3

1.2課題要求...............................................................3

1.3主要功能...............................................................3

1.4主要工作...............................................................3

1■5重點(diǎn)解決問(wèn)題......................................................3

2概要設(shè)計(jì)..................................................4

2.1抽象數(shù)據(jù)...............................................................4

2.2頭文件及宏、結(jié)構(gòu)體定義................................................6

2.3主程序流程.............................................................7

2.4各程序模塊層次關(guān)系....................................................7

3詳細(xì)設(shè)計(jì)........................................................8

3.1模塊實(shí)現(xiàn)..............................................................8

3.1.1主要模塊(函數(shù))................................................8

3.2主程序流程圖..........................................................12

4調(diào)試分析........................................................13

4.1遇到的問(wèn)題...........................................................13

4.1.1關(guān)于程序運(yùn)行時(shí)間的計(jì)算........................................13

4.2程序代碼改進(jìn)..........................................................14

4.2.1打開(kāi)文件接收字符部分..........................................14

4.3算法時(shí)空分析........................................................16

4.3.1SortKeyO復(fù)雜度.................................................16

4.3.20Find()函數(shù)復(fù)雜度..............................................17

4.3.3CheckKeyword()函數(shù)復(fù)雜度.......................................17

4.4程序設(shè)計(jì)回顧........................................................17

4.5經(jīng)馬僉和體會(huì)..........................................................18

5測(cè)試結(jié)果.......................................................20

5.1簡(jiǎn)單程序測(cè)試........................................................20

5.1.1測(cè)試文件內(nèi)容....................................................20

5.1.2程序輸入界面....................................................20

5.1.3測(cè)試運(yùn)行結(jié)果....................................................21

5.2復(fù)雜程序測(cè)試..........................................................22

5.2.1測(cè)試文件內(nèi)容....................................................22

5.2.2程序輸入界面....................................................23

5.2.3測(cè)試運(yùn)行結(jié)果....................................................23

參考文獻(xiàn)...........................................................25

附錄：源代碼.......................................................25

1需求分析

1.1主要任務(wù)

對(duì)于兩個(gè)C程序，設(shè)計(jì)并實(shí)現(xiàn)兩種不同的基于散列表的檢測(cè)算法，計(jì)算兩

個(gè)程序的相近度，并分析比較兩種算法的效率。

1.2課題要求

1.分別讀取兩個(gè)C程序文件(InFilel.cpp,lnFile2.cpp),識(shí)別其中的關(guān)鍵字

并統(tǒng)計(jì)頻度，分別生成兩個(gè)文件，保存關(guān)鍵字名稱和對(duì)應(yīng)頻度(OutFilel.txt,

OutFile2.txt)；

2.自行設(shè)計(jì)散列函數(shù)，分別利用開(kāi)放地址法和鏈地址法構(gòu)建C語(yǔ)言關(guān)鍵字

的散列表。在掃描源程序的過(guò)程中，每遇到關(guān)鍵字就查找相應(yīng)散列表，并累加相

應(yīng)關(guān)鍵字出現(xiàn)的頻度；

3.根據(jù)統(tǒng)計(jì)的兩個(gè)程序中關(guān)鍵字不同頻度，可以得到兩個(gè)向量。

1.3主要功能

計(jì)算兩個(gè)程序的相近度，并比較開(kāi)放地址法和鏈地址法兩種算法的效率

1.4主要工作

1.讀取文件中的字符，并對(duì)讀到的字符串就是否是關(guān)鍵字進(jìn)行判別；

2.使用散列表存儲(chǔ)從文件中讀到的關(guān)鍵字；

3.向指定文件中寫(xiě)入得到的關(guān)鍵字和頻度；

4.根據(jù)公式計(jì)算出向量相對(duì)距離s；

5.計(jì)算相對(duì)距離s所用的時(shí)間。

1.5重點(diǎn)解決問(wèn)題

1.過(guò)濾注釋?zhuān)?/p>

2.讀取字符并判斷讀取到的字符串是否是關(guān)鍵字；

3.關(guān)鍵字的存儲(chǔ)。

2概要設(shè)計(jì)

2.1抽象數(shù)據(jù)

抽象數(shù)據(jù)類(lèi)型定義：

ADT

{

數(shù)據(jù)對(duì)象：兩個(gè)C程序(文件路徑需給出)

基本操作：

InitKey(keykeys[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組keys己聲明

操作結(jié)果：初始化關(guān)鍵字結(jié)構(gòu)體數(shù)組

OInit(HashTable&HT)

初始條件：開(kāi)放地址法散列表HT已聲明

操作結(jié)果：開(kāi)放地址法初始化散列表

Unit(HashLink&HL)

初始條件：鏈地址法散列表HL已聲明

操作結(jié)果：鏈地址法初始化散列表

CheckKeyword(char*s)

初始條件：字符串?dāng)?shù)組s已存在，預(yù)設(shè)關(guān)鍵字?jǐn)?shù)組已存在

操作結(jié)果：檢查字符串?dāng)?shù)組s是否是關(guān)鍵字

OFind(HashTable&HT,char*keyword,intkey)

初始條件：開(kāi)放地址法散列表HT和關(guān)鍵字字符數(shù)組keyword已存在

操作結(jié)果：返回關(guān)鍵字字符數(shù)組keyword的存放位置

OCreateHashList(HashTable&HT,char*keyword)

初始條件：開(kāi)放地址法散列表HT和關(guān)鍵字字符數(shù)組keyword已存在

操作結(jié)果：開(kāi)放地址法將關(guān)鍵字加入哈希表

LCreateHashList(HashLink&HL,char*keyword)

初始條件：鏈地址法散列表HL和關(guān)鍵字字符數(shù)組keyword已存在

操作結(jié)果：鏈地址法將關(guān)鍵字加入哈希表

OpenFile(HashTable&HT,HashLink&HL,charfilename口，intop)

初始條件：開(kāi)放地址法散列表HT和鏈地址法散列表HL已初始化，字符數(shù)組

filename已指定

操作結(jié)果：使用指定的方法構(gòu)造對(duì)應(yīng)的哈希表(方法由。p變量指定)

OFileWrite(HashTableHT,charfilename口，keykeys[])

初始條件：開(kāi)放地址法散列表HT已構(gòu)造，字符數(shù)組filename已指定，關(guān)鍵字結(jié)

構(gòu)體數(shù)組keys已初始化

操作結(jié)果：關(guān)鍵字和其頻度寫(xiě)入指定文件同時(shí)存儲(chǔ)到關(guān)鍵字結(jié)構(gòu)體數(shù)組keys中

LFileWrite(HashLinkHL,charfilename[]?keykeys[])

初始條件：開(kāi)放地址法散列表HL已構(gòu)造，字符數(shù)組filename已指定，關(guān)鍵字結(jié)

構(gòu)體數(shù)組keys已初始化

操作結(jié)果：關(guān)鍵字和其頻度寫(xiě)入指定文件同時(shí)存儲(chǔ)到關(guān)鍵字結(jié)構(gòu)體數(shù)組keys中

SortKey(keykeys[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組已存在

操作結(jié)果：對(duì)關(guān)鍵字結(jié)構(gòu)體數(shù)組進(jìn)行排序

ShowKey(keykeyl[],keykey2[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組keyl和key2已存在

操作結(jié)果：顯示關(guān)鍵字信息

KeySub(keykeyl口，keykey2[],keykey3[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組keyl和key2已存在，key3已聲明

操作結(jié)果：計(jì)算keyl和key2構(gòu)成的兩個(gè)向量之間的差值并存儲(chǔ)于key3中

CalKey(keykeys[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組keys已存在

操作結(jié)果：計(jì)算keys構(gòu)成的向量值

KeySimilar(keykeyl[],keykey2[]jkeykey3[])

初始條件：關(guān)鍵字結(jié)構(gòu)體數(shù)組keyl、key2和key3已存在

操作結(jié)果：計(jì)算keyl和key2構(gòu)成的向量之間的相對(duì)距離s

}ADT

2.2頭文件及宏、結(jié)構(gòu)體定義

#include<iostream>

#include<fstream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

usingnamespacestd;

#defineHASHLEN100〃哈希表長(zhǎng)度

#defineKEYMAXLEN5〃關(guān)鍵字最大長(zhǎng)度

char*keywords[HASHLEN]={"char'\"do","else","float","for","if","int",

"void","while");

typedefstructHash{〃開(kāi)放地址法散列表的存儲(chǔ)表示

charkeyword[KEYMAXLEN];〃關(guān)鍵字名字

intcount;〃關(guān)鍵字頻度

}HTNode,*HashTable;

HashTableHT[HASHLEN];

typedefstructHashNode{〃鏈地址法散列表的存儲(chǔ)表示

charkeyword[KEYMAXLEN];〃關(guān)鍵字名字

intcount;〃關(guān)鍵字頻度

structHashNode*next;

}*HashLink;

HashLinkHLfHASHLEN];

typedefstructkey{〃定義關(guān)鍵字結(jié)構(gòu)體

charkeyword[KEYMAXLEN];

intcount;

}；

keykeyl[HASHLEN],key2[HASHLEN],key3[HASHLEN];

2.3主程序流程

圖2.3-1主程序流程

2.4各程序模塊層次關(guān)系

圖2.4-1各程序模塊層次關(guān)系

3詳細(xì)設(shè)計(jì)

3.1模塊實(shí)現(xiàn)

3.1.1主要模塊(函數(shù))

3.1.1.1檢查字符數(shù)組是否是關(guān)鍵字

在檢查是否是關(guān)鍵字前，需要預(yù)設(shè)一個(gè)關(guān)鍵字?jǐn)?shù)組，因?yàn)檫@里采用

二分查找法，因此要求關(guān)鍵字是有序的。由于程序中預(yù)設(shè)關(guān)鍵字有9個(gè),

在此函數(shù)中，聲明begin變量和end變量并分別置為0和8,即begin代

表第一個(gè)關(guān)鍵字,end代表最后一個(gè)關(guān)鍵字，先取begin和end的中位數(shù),

如果待檢查字符數(shù)組大于該中位數(shù)代表的關(guān)鍵字，則將begin置為中位

數(shù)加1,否則，置end為該中位數(shù)，之后重復(fù)以上步驟，如果最后比較

的關(guān)鍵字仍不等于待檢查字符數(shù)組，說(shuō)明待檢查字符數(shù)組不是關(guān)鍵字，

返回0,如果相等，說(shuō)明是關(guān)鍵字，返回1。

模塊代碼如下：

intCheckKeyword(char*s)//檢查$字符數(shù)組是否為關(guān)鍵字

{

intiJbegin=0Jend=8;

while(begin<=end)〃折半查找法

(

i=(begin+end)/2;

if(strcmp(keywords[i],s)==0)return1;〃找到返回1

elseif(strcmp(keywords[i]s)>0)

end=i-l;

elseif(strcmp(keywords[i],s)<0)

begin=i+l;

)

return。；//未找到返回。

}

3.1.1.2開(kāi)放地址法構(gòu)造哈希表

首先，我們需要構(gòu)造一個(gè)哈希函數(shù)，這里構(gòu)造的哈希函數(shù)為：

key=strlen(keyword)%47(即關(guān)鍵字長(zhǎng)度對(duì)47取余數(shù))

之后，我們需要找到關(guān)鍵字存儲(chǔ)的位置，這里調(diào)用OFind函數(shù)尋找

哈希表中可以存放關(guān)鍵字的位置，找到位置后，接下來(lái)需要進(jìn)行判斷，

該位置是否為空(即沒(méi)有關(guān)鍵字)，因?yàn)槭鞘褂瞄_(kāi)放地址法構(gòu)造，因此，

如果當(dāng)前位置已有關(guān)鍵字，則必與待存儲(chǔ)的關(guān)鍵字相同，因此只需關(guān)鍵

字頻度加1即可；如果此位置沒(méi)有關(guān)鍵字，則需將待存儲(chǔ)關(guān)鍵字存儲(chǔ)到

該位置，同時(shí)對(duì)應(yīng)的頻度加1。

模塊代碼如下：

voidOCreateHashList(HashTable&HT,char"keyword)〃開(kāi)放地址法構(gòu)

造哈希表

(

intkey,i,temp;

key=strlen(keyword)%47;〃哈希函數(shù)

temp=OFind(HTjkeyword,key);//尋找關(guān)鍵字存放位置

〃如果當(dāng)前哈希值位置已有元素且當(dāng)前關(guān)鍵字與其相同

if(temp==key&&strlen(HT[temp].keyword)>0)HT[key].count++;

else

{〃否則將關(guān)鍵字存放于OFind函數(shù)返回的te叩值對(duì)應(yīng)位置，同時(shí)對(duì)應(yīng)計(jì)

數(shù)器加1

strcpy(HT[temp].keywordjkeyword);

HT[temp].count++;

)

)

調(diào)用的OFind函數(shù)代碼如下：

intOFind(HashTable&HT,char"keyword,intkey)〃尋找關(guān)鍵字存放

位置

{

inti,flag;

for(i=0;i<HASHLEN;i++)//由于可能有多種情況，所以必須全部比較

.次

{

if(strcmp(HT[i].keywordjkeyword)==0)returni;〃如果找到

相同關(guān)鍵字則返回位置

)

for(i=key;i<HASHLEN;i++)〃未找到則向后搜索空位

if(strlen(HT[i].keyword)==0)returni;〃返回空位的位置

for(i=0;i<key;i++)〃向后搜索未找到空位則從頭開(kāi)始搜索

if(strlen(HT[i].keyword)==0)returni;〃返回空位的位置

)

3.1.1.3鏈地址法構(gòu)造哈希表

鏈地址法構(gòu)造哈希表的前幾步步驟與開(kāi)放地址法構(gòu)造哈希表相同，

不同的是，因?yàn)殒湹刂贩?gòu)造哈希表中每個(gè)元素必定是存儲(chǔ)在其哈希值

對(duì)應(yīng)的位置上的，如果其哈希值對(duì)應(yīng)的位置已有關(guān)鍵字，但該關(guān)鍵字與

待存儲(chǔ)關(guān)鍵字不同，這時(shí)我們需要在該位置申請(qǐng)一個(gè)結(jié)點(diǎn)，使用鏈?zhǔn)酱?/p>

儲(chǔ)的形式把待存儲(chǔ)關(guān)鍵字存儲(chǔ)起來(lái)。

模塊代碼如下：

voidLCreateHashList(HashLink&HL,char"keyword)〃鏈地址法構(gòu)造

哈希表

{

intkey,key=strlen(keyword)%47;〃哈希函數(shù)

HashNode*p,*q;p=&HL[key],q=NULL;

if(strlen(p->keyword)!=0)〃當(dāng)前keyword已存字符

(

while(p!=NULL)//尋找此位置鏈表是否有與當(dāng)前關(guān)鍵字相同元素

{

if(strcmp(p->keyword,keyword)==0)〃如果相同

(

p->count++;〃對(duì)應(yīng)計(jì)數(shù)器加1

return;

)

q=p；〃存儲(chǔ)前一個(gè)

p=p_>next;〃下一個(gè)

}

)

if(p!=&HL[key])p=(HashNode*)malloc(sizeof(HashNode));//$n

果沒(méi)有相同的，則申請(qǐng)一個(gè)空間存放關(guān)鍵字

p->count=i;〃計(jì)數(shù)器為1

p->next=NULL;〃next指針初始化為空

strcpy(p->keyword,keyword);〃復(fù)制字符

if(q!=NULL)q->next=p;〃如果前一個(gè)不為空，則前一個(gè)next指針指向

P

)

3.1.1.4讀取程序文件字符

讀取程序文件字符時(shí)，需要使用一個(gè)字符數(shù)組臨時(shí)存儲(chǔ)接收到的字

符，每接收到一個(gè)字符就判斷此時(shí)的字符串是否是關(guān)鍵字，如果不是，

則繼續(xù)接收，由于關(guān)鍵字是由字母組成的，因此，一旦接收到不是字母

的字符，就需要對(duì)數(shù)組進(jìn)行清空，同時(shí)應(yīng)注意注釋的忽略。注釋忽略方

法為：如果接收到"/"字符，則使用一個(gè)字符變量接收下一個(gè)字符，如果

是說(shuō)明是行注釋?zhuān)酉聛?lái)則使用該變量不斷接收字符，直到接收到

換行符為止，如果該字符變量接收到"*"字符，說(shuō)明是塊注釋?zhuān)酉聛?lái)則

使用該變量不斷接收字符，直到接收到"*"字符為止。

說(shuō)明：這里傳入?yún)?shù)op接收選擇的方法，開(kāi)地址法為1,鏈地址法

為2o

模塊代碼如下：

voidOpenFile(HashTable&HT,HashLink&HL,charfilename口，int

op)〃打開(kāi)文件

{

intn,i=0,j=0;FILE*rf;chartemp[100],c;

memset(tempj'\0',sizeof(temp));〃初始化temp數(shù)組

rf=fopen(filename,"r");〃讀取文件

if(rf==NULL)〃文件讀取失敗

{printf("%s文件打開(kāi)失敗！\n'\filename);exit(0);)

while(!feof(rf))

{

c=fgetc(rf);if(c<0)break;

if(c=='/，)〃去除注釋

{〃讀取下一個(gè)字符，如果是/說(shuō)明是行注釋?zhuān)绻?則是塊注釋

c=fgetc(rf);

if(c=='/，)〃如果是/

{

while"!=10)〃除非讀到換行符，否則繼續(xù)循環(huán)

c=fgetc(rf);

}

elseif(c=='*')〃如果是*字符

{

while(l)

{

if(c==，*')〃如果是*字符

(

c=fgetc(rf);〃判斷下一個(gè)字符是否是/字符

if(c=='/")break;

)

c=fgetc(rf);

)

}

)

if((c>64&&c<91)||(c>96&&c<123))〃關(guān)鍵字由字母組成

{

temp[i++]=c;temp[i]='\0'；

if(strlen(temp)<=KEYMAXLEN)〃如果當(dāng)前字符串長(zhǎng)度小于

等于關(guān)鍵字最大長(zhǎng)度

{

if(CheckKeyword(temp)==l)//是關(guān)鍵字

{

開(kāi)放地址法

elseLCreateHashList(HL,temp);〃鏈地址法

memset(temp,',sizeof(temp));〃字符數(shù)組清空

i=0;

)

}

}

if(!((c>64&&c<91)||(c>96&&c<123)))

{//讀到不是字母，則字符數(shù)組清空

memset(temp,'\0',sizeof(temp));i=0;

}

3.2主程序流程圖

返回主界而

圖3.2主程序流程圖

4調(diào)試分析

4.1遇到的問(wèn)題

4.1.1關(guān)于程序運(yùn)行時(shí)間的計(jì)算

由于是調(diào)用clock。函數(shù)獲取當(dāng)前時(shí)間，通過(guò)計(jì)算前后時(shí)間差得到程序運(yùn)行時(shí)間，但

是后來(lái)發(fā)現(xiàn)，當(dāng)測(cè)試的程序代碼比較短時(shí)，計(jì)算得到的時(shí)間差為0（圖4.1.1-1）。

圖4.1.1-1執(zhí)行時(shí)間為。

在網(wǎng)上查找資料后，我發(fā)現(xiàn)了一種更精確的方法：利用內(nèi)聯(lián)匯編計(jì)算時(shí)間差

（圖4.1.1-2）,它可以精確到納秒（圖4.1.1-3）。

36inlineunsigned_int64GetCycleCount()

37{

38_asm_emit0x0F

39asmemit0x31

40}|一

圖4.1.1-2內(nèi)聯(lián)匯編代碼

圖4.1.1-3時(shí)間差精確到納秒

不過(guò)，內(nèi)聯(lián)匯編只能在VisualC++中使用（好像只有VisualC++）,因?yàn)閂isualC++

內(nèi)置了內(nèi)聯(lián)匯編編譯器，如果在或中編譯會(huì)報(bào)錯(cuò)（圖）

C-FreeCodeblocks4.1.1-40

檜查文件依賴性...

正在編詔E:\資料\作業(yè)\效據(jù)結(jié)構(gòu)\基于做列表的程序相近度檢測(cè)系綾.cpp...______________________________________________________

[Error]E：\資料'作業(yè)'數(shù)據(jù)結(jié)構(gòu)'基于散列表的程序相近度檢弼系統(tǒng).cpp：38：error：expected'Cbefore"_e?iL

[Error]更：\資料\作:It\數(shù)據(jù)結(jié)構(gòu),基于散列表的程序相近度檢剜系綾.cpp：38：error：expectedasnbodybefore

[Error]E：\資料,作業(yè)\敖據(jù)結(jié)構(gòu),基于做列表的程序相近度檢剜系統(tǒng).cpp：38：error：wasnotdeclaredinthisscope

[Error]E：\夷料，作業(yè),數(shù)據(jù)結(jié)構(gòu),基于散列恚的程序相近度檢弱系統(tǒng).cpp：38：error：expected'/beforenumericconstant

圖4.1.1-4

4.2程序代碼改進(jìn)

4.2.1打開(kāi)文件接收字符部分

一開(kāi)始我使用的方法是先接收字符，如果字符為字母，則利用一個(gè)循環(huán)

并設(shè)置一個(gè)臨時(shí)字符數(shù)組接收后面的字母，當(dāng)接收到不是字母的字符時(shí)，退

出循環(huán)并清空臨時(shí)字符數(shù)組，每接收到一個(gè)字符就判斷臨時(shí)字符數(shù)組里的字

符串是否是關(guān)鍵字，當(dāng)達(dá)到最大關(guān)鍵字字符長(zhǎng)度但此時(shí)又不是關(guān)鍵字時(shí)清空

臨時(shí)字符數(shù)組。對(duì)于注釋過(guò)濾，則先判斷讀取的字符是否為‘7''字符，如果

是，則讀取下一個(gè)字符進(jìn)行判斷屬于哪一種注釋?zhuān)绻?*",說(shuō)明接下來(lái)的

內(nèi)容是塊注釋的內(nèi)容；如果是說(shuō)明接下來(lái)的內(nèi)容是行注釋的內(nèi)容，之后

進(jìn)行相應(yīng)的處理即可。代碼如下(主要部分)：

while(!feof(rf))

c=fgetc(rf);if(c<0)break;

if(c=="，)〃去除注釋

{〃讀取下一個(gè)字符，如果是/說(shuō)明是行注釋,如果是*則是塊注祥

t=fgetc(rf);

if(t=='/，)//如果是/

{

t=fgetc(rf);〃讀取字符

while(t!=10)〃除非讀到換行符，否則繼續(xù)循環(huán)

t=fgetc(rf);

}

elseif(t=='*')//如果是*

(

t=fgetc(rf);

while(t!='*')//除非讀到*字符，否則繼續(xù)循環(huán)

t=fgetc(rf);

1=千86k(肝)；〃接收'/'字符

}

)

while((c>64&&c<91)||(c>96&&c<123))〃關(guān)鍵字由字母組成

(

temp[i++]=c;〃臨時(shí)存儲(chǔ)字符

if(strlen(temp)<=KEYMAXLEN)〃如果當(dāng)前字符串長(zhǎng)度小于等于

關(guān)鍵字最大長(zhǎng)度

{

if(CheckKeyword(temp)==1)〃是關(guān)鍵字

if(op==l)0CreateHashList(HT,temp);〃22為1,表示

使用開(kāi)放地址法

elseLCreateHashList(HL,temp);〃否則是鏈地址法

memset(temp'\0',sizeof(temp))"/清空字符數(shù)組

i=0;

}

}

c=fgetc(rf);//接收字符

if(!((c>64&&c<91)||(c>96&&c<123)))

{〃讀到不是字母，則字符數(shù)組清空

memset(temp,'\0',sizeof(temp));i=0;

)

if(c=='/，)〃去除性釋

{〃讀取下一個(gè)字符，如果是/說(shuō)明是行注釋?zhuān)绻?則是塊注釋

t=fgetc(rf);

if(t==7-〃如果是/

{

t=fgetc(rf);〃讀取字符

while(t!=10)〃除非讀到換行符，否則繼續(xù)循環(huán)

t=fgetc(rf);

}

elseif(t=='*')〃如果是*

{

t=fgetc(rf);

while(t!=，*，)〃除非讀到*字符，否則繼續(xù)循環(huán)

t=fgetc(rf);

t=干868(訐)；〃接收'/'字符

}

}

)

}

不難發(fā)現(xiàn)，上面這一段程序中，存在這一個(gè)很大的不足，函數(shù)一開(kāi)始位

置和while循環(huán)位置的接收字符語(yǔ)句后都有排除注釋的操作，重復(fù)的代碼使

得這一模塊顯得很臃腫，而且，其中還有一個(gè)漏洞：在判斷塊注釋結(jié)尾時(shí)，

只判斷是否出現(xiàn)"*"字符是行不通的，因?yàn)樽⑨屩锌赡苡兄羔樎暶骰蚨x，如

(int*a;)o因此，為使該模塊顯得更簡(jiǎn)潔并糾正其中的錯(cuò)誤，我做了如下更

改：

1.字符接收語(yǔ)句只在函數(shù)開(kāi)始位置，while循環(huán)中不添加字符接收語(yǔ)句。

2.使用while循環(huán)控制塊注釋結(jié)尾的判斷，一旦接收到"*"字符，就判斷

下一個(gè)字符是否是〃/，，字符

修改代碼如下：

while())

-

c=fgetc(rf);if(c<0)break;

if(c=='/')〃去除注釋

{〃讀取下一個(gè)字符，如果是/說(shuō)明是行注釋?zhuān)绻?則是塊注釋

c=fgetc(rf);

if(c=='/，)〃如果是/

{

while(c!=10)〃除非讀到換行符，否則繼續(xù)循環(huán)

c=fgetc(rf);

)

elseif(c=='*')〃如果是*

{

while(l)

{

if(c=='*')

{

c=fgetc(rf);if(c=='/')break;

}

c=fgetc(rf);

}

)

}

if((c>64&&c<91)||(c>96&&c<123))〃關(guān)鍵字由字母組成

(

temp[i++]=c;〃臨時(shí)存儲(chǔ)字符

if(strlen(temp)<=KEYMAXLEN)〃如果當(dāng)前字符串長(zhǎng)度小于等于關(guān)鍵字

最大長(zhǎng)度

{

if((：110d<1<6丫00「6|(1：611^)==：1)〃是關(guān)鍵字一

{

if(op==l)0CreateHashList(HT,teinp);〃2￡ZH，表示使川開(kāi)

放地址法

elseLCreateHashList(HL,temp);〃否則是鏈地址法

memset(temp,'\0',sizeof(temp，S；〃清空字符數(shù)組

i=0;

}

)

}

if(!((c>64&&c<91)||(c>96&&c<123)))

{〃讀到不是字母，則字符數(shù)組清空

memset(temp,'\0',sizeof(temp));i=0;

}

}

修改之后，模塊代碼顯得更簡(jiǎn)潔，易于理解。

4.3算法時(shí)空分析

4.3.1SortKeyO復(fù)雜度

由于函數(shù)中采用的方法為冒泡排序算法，因此時(shí)間復(fù)雜度為：0(M2),

空間復(fù)雜度為S(M2)。模塊代碼如下：

voidSortKey(keykeys[])

(

intijjjn=0;keytemp;

while(strlen(keys[n].keyword)!=0)n++;

for(i=0;i<n-l;i++)

{

for(j=0;j<n-l-i;j++)

(

if(strcmp(keys[j].keyword,keys[j+1],keyword)>0)

temp=keys[j];keys[j]=keys[j+1];keys[j+l]=temp;

)

)

)

}

4.3.2OFind()函數(shù)復(fù)雜度

由于函數(shù)中有for循環(huán)，且層數(shù)最多為1,因此模塊時(shí)間復(fù)雜度為0(n),

空間復(fù)雜度為S(n)。模塊代碼如下：

〃尋找關(guān)鍵字存放位置

intOFind(HashTable&HT,char*keywordJintkey)

{

inti.flag;

for(i=0;i<HASHLEN;i++)//由于可能仃多種情況，所以必須全部比較一次

if(strcmp(HT[i].keyword,keyword)==0)returni;〃如果找到相同關(guān)鍵

字則返回位置

for(i=key;i<HASHLEN;i++)//未找到則向后搜索空位

if(strlen(HT[i].keyword)==0)returni;〃返回空位的位置

for(i=0;i<key;i++)//向后搜索未找到空位則從頭開(kāi)始搜索

if(strlen(HT[i].keyword)==0)returni;//返回空位的位置

}

4.3.3CheckKeyword()函數(shù)復(fù)雜度

檢查關(guān)鍵字模塊中采用的方法是折半查找法，因此，模塊時(shí)間復(fù)雜度為

O(log(n)),空間復(fù)雜度為S(log(n))。模塊代碼如下：

intCheckKeyword(char*s)〃檢查s"?：符數(shù)組是否為關(guān)鍵字

{

intiJbegin=0Jend=8;

while(begin<=end)〃折半查找法

{

i=(begin+end)/2;

if(strcmp(keywords[i],s)==0)return1;〃找到返回1

elseif(strcmp(keywords[i],s)>0)end=i-l;

elseif(strcmp(keywords[i],s)<0)begin=i+l;

)

return0;〃未找到返回0

}

4.4程序設(shè)計(jì)回顧

第一步，從程序文件中讀取并存儲(chǔ)關(guān)鍵字。由于關(guān)鍵字是由字母組成的，因

此當(dāng)遇到字母時(shí)，就需要臨時(shí)把它存儲(chǔ)起來(lái)，這里使用一個(gè)字符數(shù)組來(lái)接收它，

從而方便判斷得到的字符串是否是關(guān)鍵字，如果遇到不為字母的字符，說(shuō)明字母

串已結(jié)束，因此，此時(shí)應(yīng)清空臨時(shí)接收字符的數(shù)組。在接收字母的同時(shí)，應(yīng)進(jìn)行

關(guān)鍵字的核對(duì)，如果是關(guān)鍵字，則應(yīng)存儲(chǔ)該關(guān)鍵字，否則繼續(xù)接收，一旦超過(guò)了

關(guān)鍵字最大長(zhǎng)度，就應(yīng)清空臨時(shí)接收字符數(shù)組。同時(shí)，應(yīng)特別注意注釋的問(wèn)題，

由于注釋中可能存在關(guān)鍵字，所以需要過(guò)濾注釋?zhuān)唧w方法為：如果接收到

字符，則使用一個(gè)字符變量接收下一個(gè)字符，如果是說(shuō)明是行注釋?zhuān)酉?/p>

來(lái)則使用該變量不斷接收字符，直到接收到換行符為止，如果該字符變量接收

至1*"字符，說(shuō)明是塊注釋?zhuān)酉聛?lái)則使用該變量不斷接收字符，直到接收到"*"

字符為止。

第二步，寫(xiě)入得到的關(guān)鍵字信息。依次將關(guān)鍵字信息寫(xiě)入到指定的文件中，

根據(jù)使用方法的不同，寫(xiě)入的操作會(huì)不相同，具體可參考附錄：源代碼。

第三步，計(jì)算相對(duì)距離S。由于散列表中可能存在一些位置中沒(méi)有關(guān)鍵字存

儲(chǔ)的情況，因此，需要過(guò)濾沒(méi)有存儲(chǔ)關(guān)鍵字的位置，可以另外定義一個(gè)關(guān)鍵字結(jié)

構(gòu)體數(shù)組，來(lái)存儲(chǔ)真正有效的關(guān)鍵字。存儲(chǔ)完成后，應(yīng)進(jìn)行排序，可按從小到大

的順序進(jìn)行排序，便于計(jì)算其構(gòu)成向量的差值，最后根據(jù)所給公式計(jì)算出相對(duì)距

離S即可。

第四步，統(tǒng)計(jì)執(zhí)行時(shí)間。在用戶選擇某種方法后，就應(yīng)使用一個(gè)變量記錄此

時(shí)的時(shí)間，可以調(diào)用clock。函數(shù)記錄當(dāng)前時(shí)間，調(diào)用該函數(shù)需要添加頭文件

time.ho在程序執(zhí)行完該方法的所需步驟后，記錄下此時(shí)的時(shí)間，二者相減即可

得到該方法執(zhí)行時(shí)間。

4.5經(jīng)驗(yàn)和體會(huì)

相比于第一次的課程設(shè)計(jì)，這次較簡(jiǎn)單些，散列表的知識(shí)比較淺顯易懂，因

此，在上次課程設(shè)計(jì)后不久，我就把這題的代碼寫(xiě)出來(lái)了，雖然后來(lái)修改了很多

次，但是這次是靠自己寫(xiě)出來(lái)的，沒(méi)像第一次課程設(shè)計(jì)那樣，得依賴資料才能勉

勉強(qiáng)強(qiáng)寫(xiě)出來(lái)。應(yīng)該是因?yàn)樽约旱乃竭€不足吧，對(duì)于調(diào)試中的一些問(wèn)題，自己

還是沒(méi)能解決，在幫室友調(diào)試這道題的程序時(shí)，用C-Free遇到一個(gè)段錯(cuò)誤（圖

4.5-1），但是程序放在VisualC++里編譯運(yùn)行卻沒(méi)有問(wèn)題（圖4.5-2）。

圖4.5-1段錯(cuò)誤

圖4.5-2VC++下程序運(yùn)行沒(méi)有問(wèn)題

雖然現(xiàn)在還沒(méi)能找到原因，但是我會(huì)努力調(diào)試，找出其中的問(wèn)題，以后也有

可能會(huì)面對(duì)這樣的程序，我相信，通過(guò)不斷地調(diào)試，一定能找到問(wèn)題的所在。

這次的課程設(shè)計(jì)，我收獲了許多，對(duì)于程序的編寫(xiě)、改進(jìn)和調(diào)試能力有了一

些進(jìn)步，但這些是遠(yuǎn)遠(yuǎn)不夠的，唯有通過(guò)不斷地練習(xí)、做題，才能真正提高自己

的編程能力。所以，在即將到來(lái)的寒假，我將利用一些時(shí)間去做題，努力強(qiáng)化自

己，爭(zhēng)取在編程之路上走得更遠(yuǎn)!

加油!!!

5測(cè)試結(jié)果

5.1簡(jiǎn)單程序測(cè)試

（vc++編譯，有內(nèi)聯(lián)匯編部分代碼）

5.1.1測(cè)試文件內(nèi)容

程序1文件名：l.cpp

程序1文件路徑：f：\

程序1文件內(nèi)容：圖5.1；

-Icpp2CPP

V**C++SourceFile忙:C++SourceFile

I~I104字方I---I83字花

圖5.1-1程序1和程序2文件信息

程序2文件名：2.cpp

程序2文件路徑：f:\

程序2文件內(nèi)容：圖5.1-1

5.1.2程序輸入界面

圖5.1-2程序輸入界面

5.1.3測(cè)試運(yùn)行結(jié)果

5.1.3.1開(kāi)放地址法測(cè)試結(jié)果

圖5.1-3識(shí)別并統(tǒng)計(jì)關(guān)鍵字頻度結(jié)果

睛

題

井

L識(shí)

翁

計(jì)

2.址

別r

3.主

界

放

4請(qǐng).

需

識(shí)

開(kāi)

行

間

瞿

:3址

天

洋

并

字

1.回

離

相S

2.時(shí)

返

執(zhí)

可

行

3.地

擇

界面

4.請(qǐng)

遺

王

■：

圖5.1-5開(kāi)放地址法執(zhí)行時(shí)間結(jié)果

5.1.3.2鏈地址法測(cè)試結(jié)果

圖5.1-6識(shí)別并統(tǒng)計(jì)關(guān)鍵字頻度結(jié)果

圖5.1-7計(jì)算相對(duì)距離S結(jié)果

1?G:\13\Debug\13.exe.

一

關(guān)

頻

計(jì)

字

統(tǒng)

鍵

度

謝

離S

計(jì)

時(shí)

間

行

號(hào)

選

放

執(zhí)

行

識(shí)

計(jì)

關(guān)

計(jì)

距

高

鏈

執(zhí)

行

返

主