数据结构课程设计(散列表计算程序相近度).docx

数据结构课程设计报告对于两个C程序，设计并实现两种不同的基于散列表的检测算法，计算两个程序的相近度,并分析比拟两种算法的效率。散列表班级：软件112班姓名：刘路峰指导教师：兰红成绩：2月3。大亨信息工程学院2013年1月6日目录1需求分析21. 1主要任务21.2 课题要求31.3 主要功能31.4 主要工作31.5 重点解决问题32概要设计32.1 抽象数据32.2 头文件及宏、结构体定义52.3 主程序流程62.4 各程序模块层次关系73详细设计73.1 模块实现73.1.1 主要模块函数)73.2 主程序流程图114调试分析124.1 遇到的问题124.1.1 关于程序运行时间的计算124.2 程序代码改良134. 2.1翻开文件接收字符局部134.3算法时空分析154. 3.1SortKey()复杂度155. 3.2OFind()函数复杂度166. 3.3CheCkKeyWord()函数复杂度166.4 程序设计回忆166.5 经验和体会175测试结果185.1简单程序测试185. 1.1测试文件内容187. 1.2程序输入界面198. 1.3测试运行结果195.2复杂程序测试211. 2.1测试文件内容215. 2.2程序输入界面216. 2.3测试运行结果21参考文献23附录：源代码231需求分析1.1 主要任务对于两个C程序，设计并实现两种不同的基于散列表的检测算法，计算两个程序的相近度，并分析比拟两种算法的效率。1.2 课题要求1 .分别读取两个C程序文件(InFiieLCPP,lnFile2.cpp),识别其中的关键字并统计频度,分别生成两个文件，保存关键字名称和对应频度(OutFilel.txt,0utFile2.txt)；2 .自行设计散列函数，分别利用开放地址法和链地址法构建C语言关键字的散列表。在扫描源程序的过程中，每遇到关键字就查找相应散列表，并累加相应关键字出现的频度;3 .根据统计的两个程序中关键字不同频度，可以得到两个向量。1.3 主要功能计算两个程序的相近度，并比拟开放地址法和链地址法两种算法的效率1.4 主要工作1 .读取文件中的字符，并对读到的字符串就是否是关键字进行判别；2 .使用散列表存储从文件中读到的关键字；3 .向指定文件中写入得到的关键字和频度；4 .根据公式计算出向量相对距离s；5 .计算相对距离S所用的时间。1.5重点解决问题1 .过滤注释；2 .读取字符并判断读取到的字符串是否是关键字；3 .关键字的存储。概要设计2.1 抽象数据抽象数据类型定义：ADT数据对象：两个C程序(文件路径需给出)根本操作：InitKey(keykeys)初始条件：关键字结构体数组keys已声明操作结果：初始化关键字结构体数组OInit(HashTable&HT)初始条件：开放地址法散列表HT已声明操作结果：开放地址法初始化散列表1.Init(HashLink&HL)初始条件：链地址法散列表HL已声明操作结果：链地址法初始化散列表CheckKeyword(char*s)初始条件：字符串数组S已存在，预设关键字数组已存在操作结果：检查字符串数组S是否是关键字OFind(HashTable&HT,Char*keyword,intkey)初始条件：开放地址法散列表HT和关键字字符数组keyword已存在操作结果：返回关键字字符数组keyword的存放位置OCreateHashList(HashTable&HT,Char*keyword)初始条件：开放地址法散列表HT和关键字字符数组keyword已存在操作结果：开放地址法将关键字参加哈希表1.CreateHashList(HashLink&HL,Char*keyword)初始条件：链地址法散列表HL和关键字字符数组keyword已存在操作结果：链地址法将关键字参加哈希表OpenFile(HashTableSHTjHashLink&HL,Charfilenamejintop)初始条件：开放地址法散列表HT和链地址法散列表HL已初始化，字符数组filename已指定操作结果：使用指定的方法构造对应的哈希表(方法由。P变量指定)OFileWrite(HashTableHT,charfilename,keykeys)初始条件：开放地址法散列表HT已构造，字符数组filename已指定，关键字结构体数组keys已初始化操作结果：关键字和其频度写入指定文件同时存储到关键字结构体数组keys中1.FileWrite(HashLinkHL,charfilename,keykeys)初始条件：开放地址法散列表HL已构造，字符数组filename已指定，关键字结构体数组keys已初始化操作结果：关键字和其频度写入指定文件同时存储到关键字结构体数组keys中SortKey(keykeys)初始条件：关键字结构体数组已存在操作结果：对关键字结构体数组进行排序ShowKey(keykey1,keykey2)初始条件：关键字结构体数组keyl和key2已存在操作结果：显示关键字信息KeySub(keykeyl,keykey2,keykey3)初始条件：关键字结构体数组keyl和key2已存在，key3已声明操作结果：计算keyl和key2构成的两个向量之间的差值并存储于key3中CalKey(keykeys)初始条件：关键字结构体数组keys已存在操作结果：计算keys构成的向量值KeySimilar(keykeyl,keykey2,keykey3)初始条件：关键字结构体数组keyl、key2和key3已存在操作结果：计算keyl和key2构成的向量之间的相对距离SADT2.2 头文件及宏、结构体定义#include<iostream>#include<fstream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>usingnamespacestd;#defineHASHLEN10。哈希表长度#defineKEYMAXLEN5关键字最大长度char+keywordsHASHLEN="char"j"do","else","float","for","if","inf,"void","while");typedefstructHaSh开放地址法散列表的存储表示charkeywordKEYMAXLEN;关键字名字intcount;关键字频度HTNode,*HashTable;HashTableHTHASHLEN;typedefstructHaShNode链地址法散列表的存储表示charkeywordKEYMAXLEN;关键字名字intcount;关键字频度structHashNode*ne×t;*HashLink;HashLinkHLHASHLEN;typedefstructkey定义关键字结构体charkeywordKEYMAXLEN;intcount;；keykeylHASHLEN,key2HASHLEN,ky3HASHLEN;2. 3主程序流程图2.3-1主程序流程2.4各程序模块层次关系程序模块层次关系3详细设计3.1 模块实现3.1.1 主要模块函数3.1.1.1 检查字符数组是否是关键字在检查是否是关键字前，需要预设一个关键字数组，因为这里采用二分查找法,因此要求关键字是有序的。由于程序中预设关键字有9个，在此函数中，声明begin变量和end变量并分别置为O和8,即begin代表第一个关键字，end代表最后一个关键字，先取begin和end的中位数，如果待检查字符数组大于该中位数代表的关键字，那么将begin置为中位数加1,否那么，置end为该中位数，之后重复以上步骤，如果最后比拟的关键字仍不等于待检查字符数组，说明待检查字符数组不是关键字，返回0,如果相等，说明是关键字，返回1。模块代码如下：intCheckKeyword(char*s)检查S字符数组是否为关键字inti,begin=0,end=8;while(begin<=end)折半查找法i=(begin+end)/2;if(strcmp(keywordsi,s)=0)return1;找到返回1elseif(strcmp(keywordsi,s)>0)end=i-l;elseif(strcmp(keywordsi,s)<0)begin=i+l;return0;未找到返回。3.1.1.2 开放地址法构造哈希表首先，我们需要构造一个哈希函数，这里构造的哈希函数为：key=strlen(keyword)%47即关键字长度对47取余数)之后，我们需要找到关键字存储的位置，这里调用OFind函数寻找哈希表中可以存放关键字的位置，找到位置后，接下来需要进行判断，该位置是否为空(即没有关键字)，因为是使用开放地址法构造，因此，如果当前位置已有关键字，那么必与待存储的关键字相同，因此只需关键字频度加1即可；如果此位置没有关键字,那么需将待存储关键字存储到该位置，同时对应的频度加Io模块代码如下：voidOCreateHashList(HashTable&HT,Char*keyword)开放地址法构造哈希表intkey,i,temp;key=strlen(keyword)%47;哈希函数temp=OFind(HT,keyword,key);寻找关键字存放位置如果当前哈希值位置已有元素且当前关键字与其相同if(temp=key&&strlen(HTtemp.keyword)>0)HTkey.count+;else否那么将关键字存放于OFind函数返回的te叩值对应位置，同时对应计数器加1strcpy(HTtemp.keyword,keyword);HTtemp.count+;)调用的OFind函数代码如下：intOFind(HashTable&HT,Char*keywordjintkey)寻找关键字存放位置int"flag;for(i=0；i<HASHLEN；i+)/由于可能有多种情况，所以必须全部比拟if(strcmp(HTi.keyword,keyword)=0)returni;如果找到相同关键字那么返回位置for(i=key;iHASHLEN;i+)未找到那么向后搜索空位if(strlen(HTi.keyword)=0)returni;返回空位的位置for(i=0;ikey;i+)向后搜索未找到空位那么从头开始搜索if(strlen(HTi.keyword)=0)returni;返回空位的位置3.1.1.3 错地址法构造哈希表链地址法构造哈希表的前几步步骤与开放地址法构造哈希表相同，不同的是，因为链地址法构造哈希表中每个元素必定是存储在其哈希值对应的位置上的，如果其哈希值对应的位置已有关键字，但该关键字与待存储关键字不同，这时我们需要在该位置申请一个结点，使用链式存储的形式把待存储关键字存储起来。模块代码如下：voidLCreateHashList(HashLink&HL,Char*keyword)链地址法构造哈希表intkey,i,temp;key=strlen(keyword)%47;哈希函数HashNode*p,*q;p=&HLkey,q=NULL;if(Strlen(p->keyword)!=0)当前keyword已存字符WhiIe(P!=NULL)/#找此位置链表是否有与当前关键字相同元素if(strcmp(p->keywordjkeyword)=0)如果相同P->count+;对应计数器加1return;)q=p；存储前一个p=p->nextjT个)if(p!=&HLkey)p=(HashNode*)malloc(sizeof(HashNode);如果没有相同的，那么申请一个空间存放关键字p->cOUnt=1;计数器为1p->next=NULL;next指针初始化为空StrCPy(P->keyword,keyword);复制字符if(q!=NULL)q->next=p;如果前一个不为空，那么前,个next指针指向P3.1.1.4 读取程序文件字符读取程序文件字符时，需耍使用一个字符数组临时存储接收到的字符，每接收到一个字符就判断此时的字符串是否是关键字，如果不是，那么继续接收，由于关键字是由字母组成的，因此，一旦接收到不是字母的字符，就需要对数组进行清空,同时应注意注释的忽略。注释忽略方法为：如果接收到/字符，那么使用一个字符变量接收下一个字符，如果是'7，说明是行注释，接下来那么使用该变量不断接收字符，直到接收到换行符为止，如果该字符变量接收到*字符，说明是块注释，接下来那么使用该变量不断接收字符，直到接收到*字符为止。说明：这里传入参数。P接收选择的方法，开地址法为L链地址法为2。模块代码如下：voidOpenFile(HashTable&HT,HaShLink&HL,CharfilenamejintOP)翻开文件intn,i=0jj=0;FILE*rfjchartemp100,c;memset(temp,'0',SiZeOf(temp);初始化temp数组rf=fopen(filename)；读取文件if(rf=NULL)/文件读取失败printf("%s文件翻开失败！n",filename)jexit(0);)while(!feof(rf)c=fgetc(rf);if(c<)break;if(c='/')去除注释读取下个字符,如果是/说明是行注释,如果是*那么是块注释c=fgetc(rf);if(c=f")如果是/While(C!=10)/除非读到换行符，否那么继续循环c=fgetc(rf);elseif(C='*,)如果是*字符while(l)if"=，*，)如果是*字符c=fgetc(rf);/判断下个字符是否是/字符if(c=,/')break;)c=fgetc(rf);)if(c>64&&c<91)II(c>96&&c<123)关键字由字母组成tempi+=c;tempi='0'if(strlen(temp)<=KEYMAXLEN)如果当前字符串长度小于等于关键字最大长度if(CheckKeyword(temp)=1)是关键字if(op=：I)OCreateHaShLiSt(HT,temp);OP为1,开放地址法elseLereateHaShLiSt(HL,temp);链地址法memset(tempj,'>sizeof(temp);字符数组清空i=0;if(!(c>64&&c<91)|I(c>96&&c<123)/读到不是字母，那么字符数组清空memset(temp,0,sizeof(temp);i=0;3.2主程序流程图返回主界面图3.2主程序流程图4调试分析4.1 遇到的问题关于程序运行时间的计算由于是调用clock。函数获取当前时间，通过计算前后时间差得到程序运行时间，但是后来发现,当测试的程序代码比拟短时，计算得到的时间差为。（图4.执行时间为0在网上查找资料后，我发现了一种更精确的方法：利用内联汇编计算时间差（图4.1.1- 2）,它可以精确到纳秒（图4.1.13）。36inlineunsigned_int64GetCycIeCount()3738_asm_emit0×0F39_asm_emit0x314。I图4.1.1-2内联汇编代码图4.1.1-3时间差精确到纳秒不过，内联汇编只能在ViSUaIC+中使用（好似只有ViSUaIC+）,因为ViSUaIC+内置了内联汇编编译器，如果在C-Free或Codeblocks中编译会报错（图4.1.1-4）o粉宣文件依<ft柱.正在编译E:资料作北数据结构基于触列去的程序相近度桧立系统.Opp.三rrrE：资料作业数据结掏'基于融列式的程序相近度桧剜系统CPP38:error：expectedCbefore、eit"ZrrrE：夷料作北载据结构基干散列表的程序相近度检别系统.cpp:38:error：expectedasbodybefore*-eit*ErrorE：爽料作北敦据结构基干散列表的程序相近度检则系绫.cpp：38:error:二eit'vasnetdeclaredinthis三epeZrrerE：资料作北数据结构基于散列表的程序相近度检测系统.cpp：38：error：expected,beforenaericconsta*t4.2 程序代码改良4.2.1- 翻开文件接收字符局部一开始我使用的方法是先接收字符，如果字符为字母，那么利用一个循环并设置一个临时字符数组接收后面的字母，当接收到不是字母的字符时，退出循环并清空临时字符数组，每接收到一个字符就判断临时字符数组里的字符串是否是关键字，当到达最大关键字字符长度但此时又不是关键字时清空临时字符数组。对于注释过滤，那么先判断读取的字符是否为7字符，如果是，那么读取下一个字符进行判断属于哪一种注释，如果是*，说明接下来的内容是块注释的内容；如果是/，说明接下来的内容是行注释的内容，之后进行相应的处理即可。代码如下(主要局部)：Whil.e(!feof(rf)c=fgetc(rf)jif(c<0)break;if(c=f")去除注释读取F一个字符,如果是/说明是行注释,如果是*那么是块注释t=fgetc(rf);if(t=f/如果是/(t=fgetc(rf);读取字符While(t!=10)除非读到换行符，否那么继续循环t=fgetc(rf);)elseif(t='*')如果是*t=fgetc(rf);while(t!='*')除非读到*字符，否那么继续循环t=fgetc(rf);t=fgetc(rf);接收7'字符)While(C>64&&c<91)II(c>96&&3：123)关键字由字母组成tempi+=c;临时存储字符if(strlen(temp)<=KEYMAXLEN)如果当前字符串长度小于等于关键字最大长度(if(CheckKeyword(temp)=1)是关键字址法if(op=l)0CreateHashList(HT,temp);22为l,表示使用开放地elseLCreateHaShLiSt(HL,temp);否那么是链地址法memset(tempj,0,>sizeof(temp);；青空字符数组i=0;)c=fgetc(rf);接收字符if(!(c>64&&c<91)II(c>96&&c<123)读到不是字母，那么字符数组清memset(tempJ0SiZeOf(temp);i=0;if(c='/')去除注释读取下一个字符：，如果是/说明是行注释，如果是*那么是块注释t=fgetc(rf);if(t=f")如果是/t=fgetc(rf);读取字符WhiIe(t!=10)除M读到换行符，否那么继续循“、t=fgetc(rf);elseif(t='*')如果是*t=fgetc(rf);while(t!='*')除非读到*字符，否那么继续循环t=fgetc(rf);t=fgetc(H=);接收,广字符)不难发现，上面这一段程序中，存在这一个很大的缺乏，函数一开始位置和While循环位置的接收字符语句后都有排除注释的操作，重复的代码使得这一模块显得很臃肿，而且，其中还有一个漏洞：在判断块注释结尾时，只判断是否出现*字符是行不通的，因为注释中可能有指针声明或定义，如(int*a;)o因此，为使该模块显得更简洁并纠正其中的错误，我做了如下更改：1.字符接收语句只在函数开始位置，while循环中不添加字符接收语句。2.使用WhiIe循环控制块注释结尾的判断，一旦接收到*字符，就判断下一个字符是否是/字符修改代码如下：While(!feof(rf)一c=fgetc(rf);if(c<0)break;if(c=i")去除注释/读取下一个字符，如果是/说明是行注释，如果是*那么是块注释c=fgetc(rf);if(c=fD如果是/WhiIe(C!=10)除非读到换行符，否那么继续循环c=fgetc(rf);elseif(c='*')如果是*While(I)if(c=*')c=fgetc(rf);if(c=*/,)break;)c=fgetc(rf);)if(c>64&&c<91)I|(c)96&&c<123)关键字由字母组成(tempi+=c;临时存储字符if(strlen(temp)<=KEYMAXLEN)如果当前字符串长度小于等于关键字最大长度if(CheckKeyword(temp)=1)是关键字(if(op=l)0CreateHashList(HT,temp);2，表不使用开放地址法elseLCreateHaShLiSt(HL,temp);否那么是链地址法memset(temp,0,4sizeof(temp);清空字符数组i=0;)if(!(c>64&&c<91)|I(c>96&&c<123)读到不是字母，那么字符数组清空memset(tempj,sizeof(temp);i=0;修改之后，模块代码显得更简洁，易于理解。4.3算法时空分析4. 3.1SOrtKey()复杂度由于函数中采用的方法为冒泡排序算法，因此时间复杂度为：0(廿2),空间复杂度为S(M2)0模块代码如下：voidSortKey(keykeys)inti>j,n=0jkeytemp;while(strlen(keysn.keyword)!=0)n+;for(i=0;i<n-l;i+)for(j=0;j<n-l-i;j+)if(strcmp(keysj.keyword,keysj+l.keyword)>0)temp=keysj;keysj=keysj+l;keysj+l=temp;4.3.2OFEd()函数复杂度由于函数中有for循环，且层数最多为1,因此模块时间复杂度为0(n),空间复杂度为S(n)。模块代码如下：intOFind(HashTable&HT,Char*keyword,intkey)寻找关键字存放位置inti,flag;for(i=0；i<HASHLEN；i+)由于可能有多种情况，所以必须全部比拟一次if(strcmp(HTi.keyword,keyword)=0)returni;如果找到相同关键字那么返回位置for(i=key;iHASHLEN;i+)未找到那么向后搜索空位if(strlen(HTi.keyword)=0)returni;返回空位的位置for(i=0;i<key;i+)向后搜索未找到空位那么从头开始搜索if(strlen(HTi.keyword)=0)returni;返回空位的位置4.3.3CheckKeyword()函数复杂度检查关键字模块中采用的方法是折半查找法，因此，模块时间复杂度为O(og(n),空间复杂度为S(IOg(n)。模块代码如下：intCheckKeyword(char*s)检查S字符数组是否为关键字(inti,begin=0,end=8;while(begin<=end)折半查找法i=(begin+end)/2;if(strcmp(keywordsi,s)=0)return1;找到返回1elseif(strcmp(keywordsi,s)>0)end=i-l;elseif(strcmp(keywordsi,s)<0)begin=i+l;return0;未找到返回04.4 程序设计回忆第一步，从程序文件中读取并存储关键字。由于关键字是由字母组成的，因此当遇到字母时，就需要临时把它存储起来，这里使用一个字符数组来接收它，从而方便判断得到的字符串是否是关键字，如果遇到不为字母的字符，说明字母串已结束，因此，此时应清空临时接收字符的数组。在接收字母的同时，应进行关键字的核对，如果是关键字，那么应存储该关键字，否那么继续接收，一旦超过了关键字最大长度，就应清空临时接收字符数组。同时，应特别注意注释的问题，由于注释中可能存在关键字，所以需要过滤注释，具体方法为：如果接收至中7字符，那么使用一个字符变量接收下一个字符，如果是'7，说明是行注释，接下来那么使用该变量不断接收字符，直到接收到换行符为止，如果该字符变量接收到*字符，说明是块注释，接下来那么使用该变量不断接收字符，直到接收到*字符为止。第二步，写入得到的关键字信息。依次将关键字信息写入到指定的文件中，根据使用方法的不同，写入的操作会不相同，具体可参考附录：源代码。第三步，计算相对距离S。由于散列表中可能存在一些位置中没有关键字存储的情况，因此，需要过滤没有存储关键字的位置，可以另外定义一个关键字结构体数组，来存储真正有效的关键字。存储完成后，应进行排序，可按从小到大的顺序进行排序，便于计算其构成向量的差值，最后根据所给公式计算出相对距离S即可。第四步，统计执行时间。在用户选择某种方法后，就应使用一个变量记录此时的时间，可以调用CIoCk（）函数记录当前时间，调用该函数需要添加头文件time.h。在程序执行完该方法的所需步骤后，记录下此时的时间，二者相减即可得到该方法执行时间。4.5 经验和体会相比于第一次的课程设计，这次较简单些，散列表的知识比拟浅显易懂，因此，在上次课程设计后不久，我就把这题的代码写出来了，虽然后来修改了很屡次，但是这次是靠自己写出来的，没像第一次课程设计那样，得依赖资料才能勉勉强强写出来。应该是因为自己的水平还缺乏吧，对于调试中的一些问题，自己还是没能解决，在帮室友调试这道题的程序时，用C-Free遇到一个段错误（图4.5-1）,但是程序放在ViSUalC+里编译运行却没有问题（图4.5-2）。图4.5L段错误.图 4.5-2VC+下程序运行没有问题回 一 > > > 12 3 4void文件2关键字如下: chrelse floata法面虽然现在还没能找到原因，但是我会努力调试，找出其中的问题，以后也有可能会面对这样的程序，我相信，通过不断地调试，一定能找到问题的所在。这次的课程设计，我收获了许多，对于程序的编写、改良和调试能力有了一些进步，但这些是远远不够的，唯有通过不断地练习、做题，才能真正提高自己的编程能力。所以,在即将到来的寒假，我将利用一些时间去做题，努力强化自己，争取在编程之路上走得更远！加油!5测试结果5.1 简单程序测试（VC+编译，有内联汇编局部代码）测试文件内容程序1文件名：1.CPP程序1文件路径：f：程序1文件内容：图5.1-1LcppC* Source FM 104字节c*2.cppC*SourceF1183,3)2.cpp-iN=>.t三12231*(F)OM(E)msc<)三(V)fJW（三）-voidvoidvoidfloatfloatcharcharcharcharcharififif*ifelsewhilewhile图5.1-1程序1和程序2文件信息程序2文件名：2.cpp程序2文件路径：f:程序2文件内容：图5.1-15.1.2程序输入界面图5.1-2程序输入界面测试运行结果5.1.3.1开放地址法测试结果图5.1-3识别并统计关键字频度结果图5.1-4计算相对距离S结果图5.1-5开放地址法执行时间结果5.1.3. 2微地址法测试结果图5.1-6识别并统计关键字频度结果计算相对距离S结果:3址#王：序间 间字间:2频36度图5.1-8链地址法执行时间结果从以上结果中可以看出，链地址法的执行时间比开放地址法时间要短一些。接下来我们继续验证两种方法的效率。5.2 复杂程序测试（vc+编译，有内联汇编局部代码）5.2.1测试文件内容程序1文件名：3.cpp程序1文件路径：f：程序1文件内容：图5.2-1I HE件交Al23M>e>4:XfKHMK三)3CtOB(V)mt<H*include<k)stream>*include<fstream>*include<cstdk>>tin<!ude<<stdib>tineIude<(String>tinclude<ctime>*include<cmath>usingnamespacestd;<defineHASHLEN100蛤希表长度defineKEYMAXIEN6/关y大长度char*keywocds(KASHLENl-char,double,else.floaf.foctrf,*inf.vokl.wile>4<pp文懦EmiE.三O)»a)：K.tinclude<CStdio>*lude<CString>9include<cmat>Iude<iostream>三inclde<fstrwm>,include<cst(*b>usingnamespaceStdtEdefineMAXWO窑设勖泞符故,在Ifi夫«中做叶子typedefStrUCUchardata;/用前码的字符Wweight;/*509RRtParent.khdjchild:父结点、左茂子指针、右核子擢图5.2-1程序1和程序2文件信息程序2文件名：4.cpp程序2文件路径：f:程序2文件内容：图5.2-15.2.2程序输入界面f:3.txt请输入£：、4.cpp文件数据要存储到的文件路径:fxM.t×tl图5.2-2程序输入界面5.2.3测试运行结果5.2.3.1开放地址法测试结果图5.2-3识别并统计关键字频度结果图5.2-4计算相对距离S结果_'GlJDebug13,e×ee2度间:9印间时间字时物酷三繇针S三执普法面识计盍？！图5.2-5开放地址法执行时间结果5.2.3.2链地址法测试结果G13Debu913.ee图526识别并统计关键字频度结果图5.2-7计算相对距离S结果G13Debug13xen,04度45颉:9字间图3时时天商仃L?若器瞿界智静键字频度王:3法王：应择图5.2-8链地址法执行时间结果从以上两个测试中我们可以看出，两种方法在处理不同大小的程序的执行时间并不是完全优胜的。使用开放地址法处理冲突容易造成关键字的“堆积”问题，但是在处理较少的数据方面有优势；链地址法相比而言要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。参考文献严蔚敏.数据结构M.北京：清华大学出版社附录：源代码（注：VC+编译才能通过）include<iostream>#include<fstream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>usingnamespacestd;#defineHASHLEN100哈希表长度#defineKEYMAXLEN6关键字最大长度char*keywordsHASHLEN="char"j"double","else","float","for","if","int"void","while");开放地址法散列表的存储表示typedefstructHash(charkeywordKEYMAXLEN;关键字名字intcount;关键字频度HTNode,*HashTable;HashTableHTHASHLEN;链地址法散列表的存储表示typedefstructHashNode(charkeywordKEYMAXLEN;关键字名字intcount;"关键字频度structHashNode*next;*HashLink;HashLinkHLHASHLEN;typedefstructkey定义关键字结构体charkeywordKEYMAXLEN;intcount;；keykeylHASHLENjky2HASHLEN,key3HASHLEN;inlineunsigned_int64GetCycleCount()/内联汇编，VC+才能编译通过