数据结构课设
结题研究报告项目名称： 无线网自动登录器 组 员： 李文勇 组 员： 谢聪 组 员： 温旭东 指导教师： 刘宏 报告日期： 2014-11-14 计算机科学与技术学院目 录 1 序言 1.1项目设计务书. 2 1.2主要研究工作. 3 2 系统设计方案的研究 2.1系统的设计要求. 4 2.2系统实现的原理. 4 2.3系统实现的方案分析与比较. 4 3系统的设计 3.1系统主要模块. 5 3.2系统数据结构用法说明. 9 3.3系统复杂度分析. 10 4系统的实现 4.1 主界面. 10 4.2 功能实现与程序测试. 11 5 总结与展望. 14 参考文献. 14 附录. 15 1 序言 1.1 项目设计目标本项目主要开发一款针对华中科技大学校园无线网PC端登录难的问题的工具软件-无线网自动登录器。实现开机自启动,自动登录校园网以及断网自连接的功能。 1.2 主要研究工作 本课程设计的题目为基于倒排索引的英语单词助手。最主要的工作就是建立单词的倒排索引。倒排索引以字或词为关键字进行索引，索引中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排索引的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排索引。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些，但不会影响整个搜索引擎的效率。目前建立倒排索引的技术较为成熟,有多种实现方式可供选择。 倒排索引的结构图如图2： 2 系统设计方案的研究 2.1系统的设计要求 (1)输入某一个（或若干个）英语单词，要求返回相应的英语例句。 (2)根据单词与语句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次启动程序时不必重新建立索引，只需将索引文件导入内存。 (3）采用图形界面，便于输入单词，例句展现直观，界面布局合理。 2.2系统实现的原理本系统对外部文件中的英语文章进行关键字提取以及词干提取,根据提取的关键字建立倒排索引常驻内存,倒排索引表中保存着关键词所在句子的句首和句尾在外部文件中的位置,查找单词时首先在倒排索引中检索,得到包含关键词的句子在外部文件中的位置,再访问外部文件得到该句子。系统主要由UI界面,倒排索引的建立,词干提取算法等三部分构成。UI界面主要使用GTK图形工具包来创建。GTK+（GIMP Toolkit)是一套源码以LGPL许可协议分发、跨平台的图形工具包。最初是为GIMP写的，已成为一个功能强大、设计灵活的一个通用图形库，是GNU/Linux下开发图形界面的应用程序的主流开发工具之一。并且，GTK+也有Windows版本和Mac OS X版。GTK是用C语言开发图形界面的一个较好的选择。倒排索引有多种建立方法,本系统采用哈希表+链表的方式建立。用目前较为流行的暴雪Hash算法进行Hash编码,采用线性探测的方式处理冲突。词干提取算法采用基于后缀去除的波特词干算法。 2.3系统实现方案分析与比较建立倒排索引的数据结构可采用B+树和哈希表两种方案。B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 B+树在文件索引系统中应用较为广泛,最大优势就是减少了磁盘的I/O。但是本系统倒排索引表中保存的是关键字的句首句尾在文件中的位置,再进行磁盘I/O访问外部文件得到该句子,而且数据量并不大。B+树的检索复杂度为以2为底的对数级,在本系统中体现不出时间优势。 哈希表在检索效率上有很大优势。理想情况下哈希表插入和查找操作的时间复杂度均为O(1)。对字符串的Hash编码有多种方式,不同的Hash编码方式和处理冲突的方法有不同的复杂度。本系统采用目前较为流行的暴雪Hash编码方式以及线性探测的处理冲突的方式。 3 系统的设计 英语单词助手 3.1系统主要模块倒排索引模块英语源文件查询模块分句及词干提取模块 主 界 面 图3 开始外存中是否存在倒排索引文件是将倒排索引文件导入内存否读取英文文件,进行分句及词干提取 建立倒排索引表 主界面,输入查询单词对要查询的单词进行词干提取查询倒排索引表,得到单词在文件中位置读取文件,得到句子并显示是继续查询否 结束1.主界面主界面由一个文本输入框一个搜索按钮和一个文本显示框构成。在输入框中输入所查询的单词,点击搜索按钮,在显示框中显示包含该词干的句子。2.分句及波特词干提取算法对英文文档进行分句,每一句标记句首和句尾的位置,然后对每一句进行词干提取,将词干作为关键字插入到哈希表中。对于一些极特殊的英语单词不规则的形式,无法正常提取词干,因为此部分太多太杂,如要实现更精确的不规则单词词干判定,算法也更为复杂,消耗的时间也就更多,故本系统不作处理。建议用户要查询单词的不规则形式时,直接查询该形式,而不是查询原词干,比如:查询go时,going能正常返回,但是went不行,所以建议用户要查询go的过去式时,直接查询went,这样能正常返回用户所需的句子。3.暴雪Hash算法建立哈希表以下为hash算法的主要代码:/lpszString:字符串的地址 dwHashType:哈希值类型dwHashType = 0时计算的哈希值用于确定字符串在哈希表中的位置；dwHashType = 1，dwHashType = 2时计算的哈希值用于验证字符串,返回值seed1:字符串的哈希值。unsigned long HashString(char *lpszFileName, unsigned long dwHashType) unsigned char *key = (unsigned char *)lpszFileName;unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;int ch;while(*key != 0) ch = toupper(*key+);seed1 = cryptTable(dwHashType << 8) + ch (seed1 + seed2);seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; return seed1; Blizzard的这个算法是非常高效的，被称为"One-Way Hash"。(注：所谓One-Way Hash,就是无法从求得的hash值通过简单的逆运算就得到原来的字符串。类似与加密算法中的message digest.)以下为建立哈希表的主要代码: 参数:Hash返回分配的哈希表的地址,HashLength:哈希表的长度,返回值:0:失败1:成功unsigned int HashTableInit()long i = 0;InitCryptTable(); /预处理CryptTableHash = (HashTable*)malloc(HashLength*sizeof(HashTable); /分配连续存储单元if (Hash = NULL)return 0;fo
