数据结构课程设计(散列表计算程序相近度).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 错地址法构造哈希表链地址法构造哈希表的前几步步骤与开