《数据结构课程设计(散列表计算程序相近度).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；ikeyword)!=0)当前keyword已存字符WhiIe(P!=NULL)/#找此位置链表是否有与当前关键字相同元素if(strcmp(p-keywordjkeyword)=0)如果相同P
13、-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 读取程序文件字符读取程序文件字符时，需耍使用一个字符数组临时存储接收到的字符，每接收到一个字符就判断此时的字符串是否是关键字，如果不
14、是，那么继续接收，由于关键字是由字母组成的，因此，一旦接收到不是字母的字符，就需要对数组进行清空,同时应注意注释的忽略。注释忽略方法为：如果接收到/字符，那么使用一个字符变量接收下一个字符，如果是7，说明是行注释，接下来那么使用该变量不断接收字符，直到接收到换行符为止，如果该字符变量接收到*字符，说明是块注释，接下来那么使用该变量不断接收字符，直到接收到*字符为止。说明：这里传入参数。P接收选择的方法，开地址法为L链地址法为2。模块代码如下：voidOpenFile(HashTable&HT,HaShLink&HL,CharfilenamejintOP)翻开文件intn,i=0jj=0;FIL
15、E*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(c64&c96&c123)关键字由字母组成tempi+=c;tempi=0;if(strlen(temp)sizeof(temp);字符数组清空i=0;if(!(c64&c96&c123)/读到不是字母，那么字符数组清空memset(temp,0,sizeof(temp);
16、i=0;3.2主程序流程图返回主界面图3.2主程序流程图4调试分析4.1 遇到的问题关于程序运行时间的计算由于是调用clock。函数获取当前时间，通过计算前后时间差得到程序运行时间，但是后来发现,当测试的程序代码比拟短时，计算得到的时间差为。（图4.执行时间为0在网上查找资料后，我发现了一种更精确的方法：利用内联汇编计算时间差（图4.1.1- 2）,它可以精确到纳秒（图4.1.13）。36inlineunsigned_int64GetCycIeCount()3738_asm_emit00F39_asm_emit0x314。I图4.1.1-2内联汇编代码图4.1.1-3时间差精确到纳秒不过，内联
17、汇编只能在ViSUaIC+中使用（好似只有ViSUaIC+）,因为ViSUaIC+内置了内联汇编编译器，如果在C-Free或Codeblocks中编译会报错（图4.1.1-4）o粉宣文件依ft柱.正在编译E:资料作北数据结构基于触列去的程序相近度桧立系统.Opp.三rrrE：资料作业数据结掏基于融列式的程序相近度桧剜系统CPP38:error：expectedCbefore、eitZrrrE：夷料作北载据结构基干散列表的程序相近度检别系统.cpp:38:error：expectedasbodybefore*-eit*ErrorE：爽料作北敦据结构基干散列表的程序相近度检则系绫.cpp：38:e
18、rror:二eitvasnetdeclaredinthis三epeZrrerE：资料作北数据结构基于散列表的程序相近度检测系统.cpp：38：error：expected,beforenaericconsta*t4.2 程序代码改良4.2.1- 翻开文件接收字符局部一开始我使用的方法是先接收字符，如果字符为字母，那么利用一个循环并设置一个临时字符数组接收后面的字母，当接收到不是字母的字符时，退出循环并清空临时字符数组，每接收到一个字符就判断临时字符数组里的字符串是否是关键字，当到达最大关键字字符长度但此时又不是关键字时清空临时字符数组。对于注释过滤，那么先判断读取的字符是否为7字符，如果是，那
19、么读取下一个字符进行判断属于哪一种注释，如果是*，说明接下来的内容是块注释的内容；如果是/，说明接下来的内容是行注释的内容，之后进行相应的处理即可。代码如下(主要局部)：Whil.e(!feof(rf)c=fgetc(rf)jif(c64&c96&3：123)关键字由字母组成tempi+=c;临时存储字符if(strlen(temp)sizeof(temp);；青空字符数组i=0;)c=fgetc(rf);接收字符if(!(c64&c96&c123)读到不是字母，那么字符数组清memset(tempJ0SiZeOf(temp);i=0;if(c=/)去除注释读取下一个字符：，如果是/说明是行注
20、释，如果是*那么是块注释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循环位置的接收字符语句后都有排除注释的操作，重复的代码使得这一模块显得很臃肿，而且，其中还有一个漏洞：在判断块注释结尾时，只判断是否出现*字符是行不通的，因为注释中可能有指针
21、声明或定义，如(int*a;)o因此，为使该模块显得更简洁并纠正其中的错误，我做了如下更改：1.字符接收语句只在函数开始位置，while循环中不添加字符接收语句。2.使用WhiIe循环控制块注释结尾的判断，一旦接收到*字符，就判断下一个字符是否是/字符修改代码如下：While(!feof(rf)一c=fgetc(rf);if(c64&c91)I|(c)96&c123)关键字由字母组成(tempi+=c;临时存储字符if(strlen(temp)64&c96&cj,n=0jkeytemp;while(strlen(keysn.keyword)!=0)n+;for(i=0;in-l;i+)for(
22、j=0;j0)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；iHASHLEN；i+)由于可能有多种情况，所以必须全部比拟一次if(strcmp(HTi.keyword,keyword)=0)returni;如果找到相同关键字那么返回位置for(i=key;iHASHLEN;i+)未找到那么向后
23、搜索空位if(strlen(HTi.keyword)=0)returni;返回空位的位置for(i=0;ikey;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(begin0)end=i-l;elseif(strcmp(keyword
24、si,s) 12 3 4void文件2关键字如下: chrelse floata法面虽然现在还没能找到原因，但是我会努力调试，找出其中的问题，以后也有可能会面对这样的程序，我相信，通过不断地调试，一定能找到问题的所在。这次的课程设计，我收获了许多，对于程序的编写、改良和调试能力有了一些进步，但这些是远远不够的，唯有通过不断地练习、做题，才能真正提高自己的编程能力。所以,在即将到来的寒假，我将利用一些时间去做题，努力强化自己，争取在编程之路上走得更远！加油!5测试结果5.1 简单程序测试（VC+编译，有内联汇编局部代码）测试文件内容程序1文件名：1.CPP程序1文件路径：f：程序1文件内容：图5
25、.1-1LcppC* Source FM 104字节c*2.cppC*SourceF1183,3)2.cpp-iN=.t三12231*(F)OM(E)msce4:XfKHMK三)3CtOB(V)mtH*include*include*includetin!udetineIudetinclude*includeusingnamespacestd;4pp文懦EmiE.三O)a)：K.tinclude*lude9includeIude三inclde,includeusingnamespaceStdtEdefineMAXWO窑设勖泞符故,在Ifi夫中做叶子typedefStrUCUchardata;/
26、用前码的字符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.ttl图5.2-2程序输入界面5.2.3测试运行结果5.2.3.1开放地址法测试结果图5.2-3识别并统计关键字频度结果图5.2-4计算相对距离S结果_GlJDebug13,eee2度间:9印间时间字时物酷三繇针S三执普法面识计盍？！图5.2-5开放地址法执行时间结果5.2.3.2链地址法测试结
27、果G13Debu913.ee图526识别并统计关键字频度结果图5.2-7计算相对距离S结果G13Debug13xen,04度45颉:9字间图3时时天商仃L?若器瞿界智静键字频度王:3法王：应择图5.2-8链地址法执行时间结果从以上两个测试中我们可以看出，两种方法在处理不同大小的程序的执行时间并不是完全优胜的。使用开放地址法处理冲突容易造成关键字的“堆积”问题，但是在处理较少的数据方面有优势；链地址法相比而言要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。参考文献严蔚敏.数据结构M.北京：清华大学出版社附录：源代码（注：VC+编译才能通过）include#include#in
28、clude#include#include#include#includeusingnamespacestd;#defineHASHLEN100哈希表长度#defineKEYMAXLEN6关键字最大长度char*keywordsHASHLEN=charjdouble,else,float,for,if,intvoid,while);开放地址法散列表的存储表示typedefstructHash(charkeywordKEYMAXLEN;关键字名字intcount;关键字频度HTNode,*HashTable;HashTableHTHASHLEN;链地址法散列表的存储表示typedefstructHashNode(charkeywordKEYMAXLEN;关键字名字intcount;关键字频度structHashNode*next;*HashLink;HashLinkHLHASHLEN;typedefstructkey定义关键字结构体charkeywordKEYMAXLEN;intcount;；keykeylHASHLENjky2HASHLEN,key3HASHLEN;inlineunsigned_int64GetCycleCount()/内联汇编，VC+才能编译通过
