西北工业大学2011级数据结构课程设计实验报告.doc

2012-2013数据结构课程设计实验报告 学院： 班级： 姓名： 学号： 邮箱： 日期：2013年1月17日 数据结构实验报告实验题目:单词（词组）检索实验内容：现在有一个英文字典（每个单词都是由小写的a-z组成），单词量很大，达到 100多万的单词，而且还有很多重复的单词。此外，我们现在还有一些 Document，每个Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。 1）基本型问题（必须采用字符串哈希，hash散列算法）（1）将所有的英文单词生成一个字典Dictionary。（2）给定一个单词，判断这个单词是否在字典Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。（3）输出Dictionary中出现次数最高的10个单词。（必须采用快速排序或堆排序算法）2）扩展型问题（可选择合适的数据结构）（4）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T=a,aa, aaa, b, ba, 如果你输入 a,那么输出应该为a, aa, aaa。（5）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。对于以下问题，需采用2种不同的数据结构（hash散列与Trie树，并针对以下题目，比较两种数据结构的优缺点。）3）高级型问题 （6）现在我们有一些Document，每个Document 由一些单词组成，现在的问题就是给你一个word，检索出哪些 Document包含这个word，输出这些Document的DocumentID（就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。（7）在第（6）问中，我们只考虑了一个word在哪些Document中的情况，我们进一步考虑2个相邻word的情况，检索出同时包含这两个相邻word的DocumentID。 4）挑战型问题 （8）现在我们再对（7）的问题进行扩展，把（7）中的只检索相邻2个word推广到可以检索多个word（即连续的k个word，其中k=2），检索出同时包含k个连续word的DocumentID。实验目的：学会使用哈希函数检索，运用指定要求算法，解决一系列单词检索问题。1 需求分析 1.本演示程序中，由程序读取文件，根据程序要求自动生成所需要的文件; 2.演示程序执行结束后，由计算机终端显示“提示信息”，以示某一问题完成与否。 3.程序执行的命令包括：（1） 读取文件；（2）构造字典；（3）实现查找；（4）实现排序；（4）写入结果。2 概要设计 为了实现上述操作，采用顺序表存储结构。1.基本操作Create_HashTable（）操作结果：读取文件，生成一个字典Dictionary。Search_Data(HNode Hash)初始条件：存在一个顺序表Hash；操作结果：读取文件，查找单词在字典Dictionary对应的出现次数，并写入另一文件；若不在字典Dictionary中，则写入NO。Sort_Count(HNode Hash)初始条件：存在一个顺序表Hash；操作结果：查找出现次数最高的10个单词，并写入另一文件。Same_PrefixData(HNode Hash)初始条件：存在一个顺序表Hash；操作结果：读取文件中的单词，查找字典Dictionary中以此单词为前缀的所有单词，并以字典序写入另一文件；若不存在，则写入空。2. 本程序包含四个模块 (1)主函数模块； (2)构造字典模块； (3)查找次数模块； (4)前缀匹配模块； (5)排序及写入模块；3.函数调用关系图 主函数模块构造字典模块查找次数模块前缀匹配模块排序及写入模块三详细设计1. 结构体类型#include#include#include#include#define SIZE 10000 /哈希之后的链表数#define len 50 /定义字符串的长度#define MAX 40000 /定义CNode类型CList长度#define MaxSize 10000 /定义CNode类型的PList以及PClist的长度typedef struct CNodechar datalen; /单词int count; /单词出现的次数CNode;CNode CListMAX;CNode PListMaxSize;CNode PCListMaxSize;typedef struct Nodechar datalen; /单词struct Node *next; /链表指针int count; /单词出现的次数Node;typedef struct HNodeNode *right;/头结点指针HNode;HNode HashSIZE;2. 每个模块的分析(1) 主函数模块int main()Create_HashTable();/生成字典Search_data(Hash);/实现查找单词对应次数 j=Sort_Count(Hash);/查找出现单词的次数频数前十的单词Same_PrefixData(Hash);/查找以某单词为前缀的单词并排序Same_PrefixFrequence(Hash);(2) 构造字典模块void Create_HashTable()/链地址法利用哈希函数构造字典Dictionary，单词来自文档vocabulary.txtfor(i=0;idata=data; q-count=1; p=Hashhd.right; if(p=NULL)q-next=NULL;Hashhd.right=q; else while(p!=NULL)r=strcmp(q-data,p-data); if(r=0)p-count+;break;/data相同，次数加1 else if(rnext=p;Hashhd.right=q;break;/q插在p与头结点之间 else if(r0) if(p-next=NULL)p-next=q;q-next=NULL;break;/p-next为空，直接尾部接入 else if(strcmp(q-data,p-next-data)next=p-next;p-next=q;break; elsep=p-next; /while(p) /else /while(fp1)fclose(fp1);/Create_HashTable生成字典Dictionary(3) 查找次数模块void Search_data(HNode Hash) FILE *fp1,*fp2; fp1=fopen(“”,“r”);fp2=fopen(“”,“w”); while(!feof(fp1) fscanf(fp1,%s,ch); m=ELFHash(ch);/ELFHash返回值 p=Hashm.right; while(p) comp=strcmp(ch,p-data);if(comp=0)fprintf(fp2,p-count);break;/查找成功else p=p-next; if(p=NULL)/未找到该单词，CASE i:NOfclose();/Search_data()在查找次数出现最高的10个单词中，我采用了堆排序，参考课本的堆排序算法。(4) 前缀匹配模块void Same_PrefixData(HNode Hash)/查找以某单词为前缀的所有单词，按字典序输出，单词来自文档TotPrefixWord.txtNode *p;FILE *fp1,*fp2;fp1=fopen(,r);fp2=fopen(,w)； while(!feof(fp1) fscanf(fp1,，ch);k=1;strl=strlen(ch); for(j=0;jSIZE;j+) p=Hashj.right; while(p)for(i=0;idatai)continue;else break; if(i=strl)strcpy(PListk.data,p-data);flag=1;k+;/查找成功 p=p-next;if(flag=0)fprintf();/flag=0未找到相关单词else if(flag=1) flag=0;/重置flagquickSort(PList,k-1);/快速排序实现字典序输出单词fprintf(); for(i=1;i0) if(p-next!=NULL) if(strcmp(q-data,p-next-data=0) p-next-count+;break;else if(strcmp(q-data,p-next-data)next=p-next;p-next=q;break;p=p-next;else if(p-next=NULL)p-next=q;q-next=NULL;正确代码：else if(r0) if(p-next=NULL)p-next=q;q-next=NULL;break; else if(strcmp(q-data,p-next-data)next=p-next;p-next=q;break; elsep=p-next;对p以及p-next的情况考虑不全，在同学的帮助下解决。（2） 对堆排序。 考虑题目要求的只需要10位次数最高，构建大顶堆，控制其只调整10次，减少时间的浪费。（3） 对实验题目的第五问。 一个半成品，纵然使用改写的冒泡排序需要30s的运行时间，却仍然无法写入正确的顺序。保证其稳定，选择冒泡。附第五问半成品：void Same_PrefixFrequence(HNode Hash)char chlen;int casel=1;int flag;int i,j,strl,k;Node *p;FILE *fp1,*fp2;fp1=fopen(PrefixFrequence.txt,r); fp2=fopen(PrefixFrequence_Result.txt,w);while(!feof(fp1)/读取文件fscanf(fp1,%s,ch);k=0;strl=strlen(ch);flag=0;for(j=0;jSIZE;j+)p=Hashj.right;while(p)for(i=0;idatai)continue;else break;if(i=strl)flag=1;k+;strcpy(PCListk.data,p-data);PCListk.count=p-count;p=p-next;if(flag=0) fprintf(fp2,CASE);fprintf(fp2, %d:n,casel+);else if(flag=1)flag=0;fprintf(fp2,CASE);fprintf(fp2, %d:n,casel+);MP_Sort(PCList,k);/冒泡排序实现按次数大小写入单词及次数 if(k=10)/按要求查找的单词个数不超过十个，则全部写入 for(i=1;i=k;i+) fprintf(fp2,%s %dn,PCListi.data,PCListi.count );else /超过十个，按出现次数大小取前十个写入 for(i=1;i1;j-)for(i=n;in-j+1;i-)/从尾部开始循环比较，大的数往前移if(CListi.countPCListi-1.count)t=PCListi.count;strcpy(data,PCListi.data);PCListi.count=PCListi-1.count;strcpy(PCListi.data,PCListi-1.data);PCListi-1.count=t;strcpy(PCListi-1.data,data);/MP_Sort在试验了改写的冒泡的正确性时，将其植入原程序中，却依然无法得到正确结果。时间仓促，未能解决。4.运行界面五实验总结本次课程设计主要涉及三个数据结构的知识，一个是Hash表，另一个是Trie Tree，第三个个是在信息检索中普遍使用的Inverted Index。完成本次课程设计的总体感受是，本次课程设计对数据结构的应用要求比较高，在整个设计过程深刻体会从最初编写程序到最终实现题目所要求的执行，这是这个学期以来编写的最大而复杂的程序，综合利用了这个学期所学习到的数据结构知识，发现自己在知识掌握上也并不是想象中那么熟练。由于不够熟练而促使自己回归课本，不断回顾基本知识，在理解题目意义的基础上，合理利用书本及在线提供的资料。第一次接触这种比较大型的单词检索的程序设计，第一步很是关键。俗话说：万事开头难。拿到第一题时，脑袋里掠过很多想法，比如运用字符串的ASCII码来确定单词的储存位置，但是又考虑到单词库中单词量上万，这样巨大的数据必会造成巨大冲突，即使使用线性探测再散列处理冲突也不是很理想。所以最终选用链地址法。跨出了第一步，其实是很让人鼓舞的。这次大作业，只做出来四小问，卡壳在第五问了。有一个重要原因就是对数据结构的选择。要选择既快又准确的，应该要属键树了。但是由于自己对树的知识掌握的不够，所以没有在规定时间内完成。这次编程的突破是学习吸收了在线资料中的哈希字符串经典函数，大大改进了运行速度。在今后编程的道路上有两点体会需要时刻提醒自己：第一、当所编写的代码过长时，一定要注意对变量的取名，以及对注释语句