西北工业大学数据结构课程方案实验报告

西北工业大学数据结构课程方 案实验报告用2018-2018 数据结构课程设计实验报告学院：班级：姓名：学号：邮箱：日期：2018年1月17日数据结构实验报告实验题目：单词词组）检索实验内容：现在有一个英文字典 每个单词都是由小写的a-z组成），单词量 很大，达到100多万的单词，而且还有很多重复的单词。此外，我们现在还有 一些 Document，每个Document包含一些英语单词。针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。1） 基本型问题 必须采用字符串哈希，hash散列算法）1）将所有的英文单词生成一个字典 Dictionary。2）给定一个单词，判断这个单词是否在字典Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。3）输出Dictionary中出现次数最高的10个单词。必须采用快速排序或堆排 序算法）2）扩展型问题 可选择合适的数据结构）4）给定一个单词，按字典序输出字典Dicti onary中所有以这个单词为前缀的单词。例如，如果字典 T=a,aa, aaa, b, ba,如果你输入 a,那么输出应该为a, aa, aaa。5）给定一个单词，输出在 Dictionary中以这个单词为前缀的单词的出现频率 最高的10个单词，对于具有相同出现次数的情况，按照最近即最后）插入的单词优先级比较高的原则输出。对于以下问题，需采用2种不同的数据结构hash散列与Trie树，并针对以下 题目，比较两种数据结构的优缺点。）3）高级型问题6）现在我们有一些Document，每个Document由一些单词组成，现在的问题 就是给你一个 word，检索出哪些 Document包含这个 word，输出这些Document 的DocumentlD就如同搜索引擎一样，即输入一些关键字，然后检索出和这些 关键字相关的文档）。7）在第6）问中，我们只考虑了一个 word在哪些Document中的情况，我们 进一步考虑 2个相邻 word的情况，检索出同时包含这两个相邻word的DocumentID。4）挑战型冋题8）现在我们再对7）的问题进行扩展，把7）中的只检索相邻2个word推广 到可以检索多个word即连续的k个word，其中k=2），检索出同时包含k个 连续 word 的 DocumentID。实验目的：学会使用哈希函数检索，运用指定要求算法，解决一系列单词检 索问题。一. 需求分析1. 本演示程序中，由程序读取文件，根据程序要求自动生成所需要的文件。2. 演示程序执行结束后，由计算机终端显示“提示信息”，以示某一问题完成 与否。3. 程序执行的命令包括：(1)读取文件；2)构造字典；3)实现查找；4)实现排序；4)写入结果二. 概要设计为了实现上述操作，采用顺序表存储结构。1. 基本操作Create_HashTable )操作结果：读取文件，生成一个字典 Dicti onary。Search_Data(HNode Hash初始条件：存在一个顺序表Hash；操作结果：读取文件，查找单词在字典Dicti onary 对应的出现次数，并写入另一文件；若不在字典 Dictionary 中，则写入NQSort_Cou nt(HNode Hash初始条件：存在一个顺序表Hash；操作结果：查找出现次数最高的10个单词，并写入另一文件。Same_PrefixData(HNode Hash初始条件：存在一个顺序表Hash；操作结果：读取文件中的单词，查找字典Dictio nary 中以此单词为前缀的所有单词，并以字典序写入另一文件；若不存在，则写入空。2. 本程序包含四个模块(1主函数模块；(2构造字典模块；(3查找次数模块；(4前缀匹配模块；(5排序及写入模块；3. 函数调用关系图主函数模块 构造字典模块 查找次数模块 前缀匹配模块 排序及写入模块三. 详细设计3.结构体类型#in clude#in clude#in clude#in clude#defi ne SIZE 10000 II 哈希之后的链表数#defi ne len 50 II定义字符串的长度#define MAX 40000 II 定义 CNode类型 CList长度#define MaxSize 10000 IIPList以及PClist的长度定义CNode类型的typedef struct CNodechar datale n。 II 单词in t cou nt 。 II 单词出现的次数 CNodQCNode CListMAX。CNode PListMaxSize。CNode PCListMaxSize。typedef struct Nodechar datale n 。/ 单词struct Node *n ext 。/ 链表指针int count 。/单词出现的次数Node。typedef struct HNodeNode *right。/头结点指针HNodeHNode HashSIZE。4. 每个模块的分析(1主函数模块int mai n(Create_HashTable(。/ 生成字典Search_data(Hash。/实现查找单词对应次 数j=Sort_Count(Hash 。/查找出现单词的次 数频数前十的单词Same_PrefixData(Hash。/ 查找以某单词为前缀的单词并排序Same_PrefixFrequence(Hash。(2)构造字典模块void Create_HashTable(/链地址法利用哈希函数构造字典Dictionary ，单词来自文档 vocabulary.txtfor(i=0 。ivSIZE。i+Hashi.right=NULL 。 Hash.right 初始化fp仁 fope n( ,r。while(!feof(fp1 fsca nf(fp1,%s,data。hd=ELFHash(data。/ELFHash 返回值 q=new Node ； q-data=data。q-co un t=1。p=Hashhd.right 。if(p=NULLq-n ext=NULL。Hashhd.right=q 。elsewhile(p!=NULL用r=strcmp(q-data,p-data 。if(r=0p-count+。 break。 /data 相同，次数加1elseif(rq-n ext=p。Hashhd.right=q 。 break。/q 插在 p 与头结 点之间else if(r0if(p-n ext=NULLp-n ext=q。q-next=NULL。break。p-next 为空，直接 尾部接入elseif(strcmp(q-data,p-n ext-data插入p与q之间q-next=p-next。 p-next=q 。 break 。 else p=p-next。/while(p/else/while(fp1 fclose(fp1 。/Create_HashTable 生成字典 Dictionary用 查找次数模块void Search_data(HNode HashFILE *fp1,*fp2。fp1=fopen(“” , “ r” 。fp2=fopen(“ W 。while(!feof(fp1fsca nf(fp1,%s,ch。m=ELFHash(ch。/ELFHash 返回值 p=Hashm.right 。while(pcomp=strcmp(ch,p-data 。if(comp=0fprintf(fp2,p-count 。break。/查找成功else p=p-n ext 。if(p=NULL未找到该单词，CASE i:NOfclose( 。/Search_data(在查找次数出现最高的10个单词中，我采用了 堆排序，参考课本的堆排序算法。(4)前缀匹配模块void Same_PrefixData(HNode Hash/查找以某单词为前缀的所有单词，按字典序 输出，单词来自文档 TotPrefixWord.txtNode *p。FILE *fp1,*fp2。fp仁 fope n(,r。fp2=fope n(,w；while(!feof(fp1fscanf(fp1,，ch。k=1。strl=strlen(chfor(j=0 。jp=Hashj.right 。while(p for(i=0。iif(chi=p-dataic on ti nue。 elsebreak。if(i=strlstrcpy(PListk.data,p-data。flag=1。k+。/ 查找成功p=p-nextif(flag=Ofpri ntf(相关单词else if(flag=1 flag=0 。/ 重置 flag quickSort(PList,k-1字典序输出单词fprin tf(。for(i=1。flag=O未找到/快速排序实现ifpri ntf(fp2,%sn,PListi.datafclose( 。/Same_PrefixData在实现字典序输出单词，我采用了快排法，参考 课本快排递归算法。partition( 。qSort(。quikSort(3.函数关系调用图Create HsearcHeaquic4.使用说明、测试分析及结果1. 1 ）本程序的运行环境为 VC6.0;2）进入演示程序后，显示提示信息： 冋题1）完成冋题2）完成-文SearchWordlnVocabulary_Result.txt 问题3）完成见文档 MostFrequenceWord.txt 问题4）完成见文档 TotPrefixWord_Result.txt2. 测试结果与分析详见文件夹内所附文档3. 调试过程中遇到的问题是如何解决以及对设计与实现的回顾讨论与分析 函数中分情况讨论各种插入时，对部分情况考虑 不周而导致的；错误代码：else if(r0if(p-n ext!=NULLif(strcmp(q-data,p-n ext-data=0 p-next-count+ 。 break。 elseif(strcmp(q-data,p-n ext-datanext=p-next 。 p-next=q 。 break 。 p=p-next。else if(p-n ext=NULLp-next=q 。 q-next=NULL。 正确代码：else if(r0 if(p-n ext=NULLp-next=q 。 q-next=NULL。 break 。 elseif(strcmp(q-data,p-n ext-dataq-next=p-next 。 p-next=q 。 break 。 else p=p-next。对p以及p-next的情况考虑不全，在同学的帮 助下解决。(2)对堆排序考虑题目要求的只需要10位次数最高，构 建大顶堆，控制其只调整10次，减少时间的浪 费。(3)对实验题目的第五问。一个半成品，纵然使用改写的冒泡排序需要30s的运行时间，却仍然无法写入正确的顺序。保证其稳定，选择冒泡。附第五问半成品：voidSame_PrefixFreque nce(HNodeHash char chlen 。i nt casel=1 。i nt flag 。i nt i,j,strl,k 。Node *p。FILE *fp1,*fp2。f p1=fope n(PrefixFreque nce.txt,r。fp2=fope n(PrefixFreque nce_Result.txt,wwhile(!feof(fp1/读取文件fsca nf(fp1,%s,ch。k=0。strl=strle n( ch。flag=O。for(j=0 。jvSIZE。j+p=Hashj.right 。 while(pfor(i=0 。 iif(chi=p-dataicontinue。else break 。if(i=strlflag=1。k+ostrcpy(PCListk.data,p-dataPCListk.co un t=p-co unt。p=p-next。if(flag=Ofpri ntf(fp2,CASE 。fprin tf(fp2, %d:n,casel+。else if(flag=1flag=0。fprin tf(fp2,CASE 。fprin tf(fp2, %d:n,casel+。MP_Sort(PCList,k。/ 冒泡排序实现按次数大小写入单词及次数if(k/按要求查找的单词个数不超过十 个，则全部写入f or(i=1 。ifprintf(fp2,%s %dn,PCListi.data,PCLi sti.co unt 。else/超过十个，按出现次数大小取前十 个写入f or(i=1 。ifprin tf(fp2,%s %dn,PCListi.data,PCLi sti.co unt 。f close(fp1 。f close(fp2 。printf(n问题(5 完成-n见文件PrefixFreque nce_Result.txtn/Same_PrefixFreque neevoid MP_Sort(CNode PCList,i ntn/n为数组元素个数/冒泡排序实现单词次数大小有序i nt i,j,t 。char data50。f or( j=n 。 j1 。 j- for( i=n。in-j+1 。i- / 从尾部开始循 环比较，大的数往前移if(CListi.cou ntPCListi-1.cou ntt=PCListi.cou nt 。 strcpy(data,PCListi.data 。PCListi.cou nt=PCListi-1.cou nt。strcpy(PCListi.data,PCListi-1.data。PCListi-1.cou nt=t 。strcpy(PCListi-1.data,data 。/MP_Sort在实验了改写的冒泡的正确性时，将其植入原程 序中，却依然无法得到正确结果。时间仓促，未 能解决。4.运行界面|问题芫成完应见共件 Scare kl/o rd I nUo cahu lary_Res 完成il賁s tFt*&(|un 0 warning(s，运行得到你想要的结果，真的很有成就感！在今后的学习中一定提 高自己对课本上知识的掌握的熟练程度， 并在此 基础上希望能通过可获得渠道拓展视野以丰富 自己的知识储备。教师评语:实验成绩:导教师签名:阅日期: