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

《数据结构课程设计(散列表计算程序相近度).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计(散列表计算程序相近度).docx（30页珍藏版）》请在第壹文秘上搜索。

1、数据结构课程设计报告对于两个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 关于程序运行时间的计算12

2、4.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程序，设计并实现两种不同的基于散列表的检测算法，

3、计算两个程序的相近度，并分析比拟两种算法的效率。1.2 课题要求1 .分别读取两个C程序文件(InFiieLCPP,lnFile2.cpp),识别其中的关键字并统计频度,分别生成两个文件，保存关键字名称和对应频度(OutFilel.txt,0utFile2.txt)；2 .自行设计散列函数，分别利用开放地址法和链地址法构建C语言关键字的散列表。在扫描源程序的过程中，每遇到关键字就查找相应散列表，并累加相应关键字出现的频度;3 .根据统计的两个程序中关键字不同频度，可以得到两个向量。1.3 主要功能计算两个程序的相近度，并比拟开放地址法和链地址法两种算法的效率1.4 主要工作1 .读取文件中的字

4、符，并对读到的字符串就是否是关键字进行判别；2 .使用散列表存储从文件中读到的关键字；3 .向指定文件中写入得到的关键字和频度；4 .根据公式计算出向量相对距离s；5 .计算相对距离S所用的时间。1.5重点解决问题1 .过滤注释；2 .读取字符并判断读取到的字符串是否是关键字；3 .关键字的存储。概要设计2.1 抽象数据抽象数据类型定义：ADT数据对象：两个C程序(文件路径需给出)根本操作：InitKey(keykeys)初始条件：关键字结构体数组keys已声明操作结果：初始化关键字结构体数组OInit(HashTable&HT)初始条件：开放地址法散列表HT已声明操作结果：开放地址法初始化散

5、列表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已存在操作结果：开放地址法

6、将关键字参加哈希表1.CreateHashList(HashLink&HL,Char*keyword)初始条件：链地址法散列表HL和关键字字符数组keyword已存在操作结果：链地址法将关键字参加哈希表OpenFile(HashTableSHTjHashLink&HL,Charfilenamejintop)初始条件：开放地址法散列表HT和链地址法散列表HL已初始化，字符数组filename已指定操作结果：使用指定的方法构造对应的哈希表(方法由。P变量指定)OFileWrite(HashTableHT,charfilename,keykeys)初始条件：开放地址法散列表HT已构造，字符数组fil

7、ename已指定，关键字结构体数组keys已初始化操作结果：关键字和其频度写入指定文件同时存储到关键字结构体数组keys中1.FileWrite(HashLinkHL,charfilename,keykeys)初始条件：开放地址法散列表HL已构造，字符数组filename已指定，关键字结构体数组keys已初始化操作结果：关键字和其频度写入指定文件同时存储到关键字结构体数组keys中SortKey(keykeys)初始条件：关键字结构体数组已存在操作结果：对关键字结构体数组进行排序ShowKey(keykey1,keykey2)初始条件：关键字结构体数组keyl和key2已存在操作结果：显示关键

8、字信息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#include#include#include

9、#include#include#includeusingnamespacestd;#defineHASHLEN10。哈希表长度#defineKEYMAXLEN5关键字最大长度char+keywordsHASHLEN=charjdo,else,float,for,if,inf,void,while);typedefstructHaSh开放地址法散列表的存储表示charkeywordKEYMAXLEN;关键字名字intcount;关键字频度HTNode,*HashTable;HashTableHTHASHLEN;typedefstructHaShNode链地址法散列表的存储表示charkeywo

10、rdKEYMAXLEN;关键字名字intcount;关键字频度structHashNode*net;*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 检查字符数组是否是关键字在检查是否是关键字前，需要预设一个关键字数组，因为这里采用二分查找法,因此要求关键字是有

11、序的。由于程序中预设关键字有9个，在此函数中，声明begin变量和end变量并分别置为O和8,即begin代表第一个关键字，end代表最后一个关键字，先取begin和end的中位数，如果待检查字符数组大于该中位数代表的关键字，那么将begin置为中位数加1,否那么，置end为该中位数，之后重复以上步骤，如果最后比拟的关键字仍不等于待检查字符数组，说明待检查字符数组不是关键字，返回0,如果相等，说明是关键字，返回1。模块代码如下：intCheckKeyword(char*s)检查S字符数组是否为关键字inti,begin=0,end=8;while(begin0)end=i-l;elseif(s

12、trcmp(keywordsi,s)0)HTkey.count+;else否那么将关键字存放于OFind函数返回的te叩值对应位置，同时对应计数器加1strcpy(HTtemp.keyword,keyword);HTtemp.count+;)调用的OFind函数代码如下：intOFind(HashTable&HT,Char*keywordjintkey)寻找关键字存放位置intflag;for(i=0；iHASHLEN；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 错地址法构造哈希表链地址法构造哈希表的前几步步骤与开