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

《2022年西北工业大学数据结构课程方案实验报告.docx》由会员分享，可在线阅读，更多相关《2022年西北工业大学数据结构课程方案实验报告.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 2022-2022数据结构课程设计试验报告学院：班级：姓名：学号：邮箱：日期： 2022 年 1 月 17 日名师归纳总结 - - - - - - -第 1 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用数据结构试验报告 试验题目 : 单词词组）检索 试验内容： 现在有一个英文字典 每个单词都是由小写的 a-z组成）,单词量 很大,达到 100 多万的单词,而且仍有许多重复的单词；此外,我们现在仍有 一些 Document,每个 Document 包含一些英语单词；针对这

2、个问题,请你挑选合适的数据结构,组织这些数据,使时间复杂度和空间复杂度尽可能低,并且解决下面的问题和分析自己算法的时间复杂度；1）基本型问题 必需采纳字符串哈希, hash散列算法）1）将全部的英文单词生成一个字典 Dictionary；2）给定一个单词,判定这个单词是否在字典 中,输出这个单词总共显现的次数；否就输出Dictionary 中；假如在单词库 NO；3）输出 Dictionary 中显现次数最高的 序算法）10 个单词； 必需采纳快速排序或堆排2）扩展型问题 可挑选合适的数据结构）4）给定一个单词,按字典序输出字典Dictionary 中全部以这个单词为前缀的单词；例如,假如字典

3、 T=a,aa, aaa, b, ba, 假如你输入 a,那么输出应当为 a, aa, aaa；5）给定一个单词,输出在 Dictionary 中以这个单词为前缀的单词的显现频率最高的 10 个单词,对于具有相同显现次数的情形,依据最近 即最终）插入的单词优先级比较高的原就输出；对于以下问题,需采纳2 种不同的数据结构 hash散列与 Trie 树,并针对以下题目,比较两种数据结构的优缺点；）3）高级型问题 6）现在我们有一些Document,每个 Document 由一些单词组成,现在的问题就 是 给 你 一 个 word , 检 索 出 哪 些Document 包 含 这 个 word ,

4、 输 出 这 些Document 的 DocumentID就犹如搜寻引擎一样,即输入一些关键字,然后检索出和这些关键字相关的文档）；7）在第 6）问中,我们只考虑了一个 word 在哪些 Document 中的情形,我们进一步考虑 2 个相邻 word 的情形,检索出同时包含这两个相邻 word 的DocumentID；4）挑战型问题8）现在我们再对 7）的问题进行扩展,把 7）中的只检索相邻 2 个 word 推广到可以检索多个 word=2）,检索出同时包含 k个连续 word 的 DocumentID； 试验目的：学会使用哈希函数检索,运用指定要求算法,解决一系列单词检索问题；一需求分析

5、 1. 本演示程序中,由程序读取文件,依据程序要求自动生成所需要的文件；名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用2. 演示程序执行终止后,由运算机终端显示“ 提示信息” ,以示某一问题完成 与否；3. 程序执行的命令包括：（1）读取文件； 2）构造字典； 3）实现查找； 4）实现排序； 4）写入结 果；二概要设计为了实现上述操作,采纳次序表储备结构；1. 基本操作Create_HashTable 初始条件：存在一个次序表Hash；对应的显现次数,并写入另操作结果：读取文件,查找单词在字典Dict

6、ionary一文件；如不在字典Dictionary中,就写入 NO；Sort_CountHNode Hash 初始条件：存在一个次序表Hash；操作结果：查找显现次数最高的10 个单词,并写入另一文件；Same_PrefixDataHNode Hash 初始条件：存在一个次序表Hash；Dictionary中以此单词为前缀的全部操作结果：读取文件中的单词,查找字典单词,并以字典序写入另一文件；如不存在,就写入空；2. 本程序包含四个模块 1 主函数模块； 2 构造字典模块； 3 查找次数模块； 4 前缀匹配模块； 5 排序及写入模块；3. 函数调用关系图主函数模块构造字典模块查找次数模块前缀匹

7、配模块 排序及写入模块三具体设计名师归纳总结 - - - - - - -第 3 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用3. 结构体类型 #include #include #include #include #define SIZE 10000 /哈希之后的链表数以及 PClist的长度#define len 50 /定义字符串的长度#define MAX 40000 /定义 CNode类型 CList长度#define MaxSize 10000 /定义 CNode类型的 PListtypedef struct CNode char da

8、talen； / 单词int count； / 单词显现的次数 CNode；CNode CListMAX ；CNode PListMaxSize；CNode PCListMaxSizetypedef struct Node char datalen； / 单词 struct Node *next； / 链表指针int count； / 单词显现的次数 Node；typedef struct HNode Node *right；/ 头结点指针 HNode；HNode HashSIZE ；4. 每个模块的分析 1 主函数模块 int main Create_HashTable；/ 生成字典 Sea

9、rch_dataHash ；/ 实现查找单词对应次数；/ 查找显现单词的次数频数前十的单词 j=Sort_CountHash Same_PrefixDataHash ； / 查找以某单词为前缀的单词并排序 Same_PrefixFrequenceHash； 2 构造字典模块 void Create_HashTable 名师归纳总结 - - - - - - -第 4 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用/ 链地址法利用哈希函数构造字典 Dictionary,单词来自文档 vocabulary.txt fori=0；iHashi.right=

10、NULL；/Hash.right初始化fp1=fopen,r； while.feoffp1 fscanffp1,%s,data； hd=ELFHashdata；/ELFHash 返回值 q=new Node；q-data=data； q-count=1； p=Hashhd.right； ifp=NULLq-next=NULL；Hashhd.right=q； else whilep.=NULL r=strcmpq-data,p-data； ifr=0p-count+；break ；/data 相同,次数加 1 else ifrq-next=p；Hashhd.right=q； break ；/q

11、插在 p 与头结点之间 else ifr0 ifp-next=NULLp-next=q； q-next=NULL ；break ；/p-next为空,直接尾部接入 else ifstrcmpq-data,p-next-data/ 插入 p 与 q 之间 q-next=p-next；p-next=q ；break ； else p=p-next； /whilep /else /whilefp1 fclosefp1；/Create_HashTable 生成字典 Dictionary 3 查找次数模块void Search_dataHNode Hash FILE *fp1,*fp2“ ”；, “w”

12、 ； fp1=fopen, “ r ” ；fp2=fopen “ ” while.feoffp1 fscanffp1,%s,ch； m=ELFHashch ；/ELFHash 返回值 p=Hashm.right； whilep 名师归纳总结 - - - - - - -第 5 页,共 12 页精选学习资料 - - - - - - - - - comp=strcmpch,p-data；个人资料整理仅限学习使用ifcomp=0fprintffp2,p-count；break ；/ 查找胜利else p=p-next； ifp=NULL/未找到该单词,CASE i:NO fclose；/Search_

13、data 在查找次数显现最高的 10 个单词中,我采纳了堆排序,参考课本的堆排序算法；4 前缀匹配模块void Same_PrefixDataHNode Hash / 查找以某单词为前缀的全部单词,按字典序输出,单词来自文档 Node *p ；TotPrefixWord.txt FILE *fp1,*fp2；fp1=fopen,r；fp2=fopen,w；while.feoffp1 fscanffp1,ch；k=1；strl=strlench； forj=0； j p=Hashj.right； whilep fori=0； iifchi=p-dataicontinue； else break

14、； ifi=strlstrcpyPListk.data,p-data p=p-next； ；flag=1 ；k+； / 查找胜利ifflag=0fprintf；/flag=0未找到相关单词else ifflag=1 flag=0 ；/ 重置 flag quickSortPList,k-1；/ 快速排序实现字典序输出单词 fprintf；ifprintffp2,%sn,PListi.data； fori=1 fclose；/Same_PrefixData 在实现字典序输出单词,我采纳了快排法,参考课本快排递归算法；名师归纳总结 partition；qSort ；quikSort 第 6 页,共

15、12 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用3. 函数关系调用图 main Create_HashTable Search_data Sort_Count Same_PrefixData HeapSort quickSort 4. 使用说明、测试分析及结果1.1 ）本程序的运行环境为 VC6.0；2）进入演示程序后,显示提示信息：-问题 1）完成 - -问题 2）完成 - 见文档 SearchWordInVocabulary_Result.txt -问题 3）完成 - 见文档 MostFrequenceWord.txt -问题

16、4）完成 - 见文档 TotPrefixWord_Result.txt 2. 测试结果与分析详见文件夹内所附文档3. 调试过程中遇到的问题是如何解决以及对设计与实现的回忆争论与分析0 ifp-next.=NULL ifstrcmpq-data,p-next-data=0 p-next-count+；break ； Create_Hash 名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用else ifstrcmpq-data,p-next-datanext=p-next；p-next=q ；break ；

17、 p=p-next ； else ifp-next=NULL p-next=q；q-next=NULL ； 正确代码：else ifr0 ifp-next=NULL p-next=q；q-next=NULL ；break ； else ifstrcmpq-data,p-next-data ；p-next=q ；break ； q-next=p-next else p=p-next； 对 p 以及 p-next 的情形考虑不全,在同学的帮忙下解决；（2）对堆排序；考虑题目要求的只需要10 位次数最高,构建大顶堆,掌握其只调整10 次,削减时间的铺张；（3）对试验题目的第五问；一个半成品,纵然使用

18、改写的冒泡排序需要 序；保证其稳固,挑选冒泡；附第五问半成品：30s 的运行时间,却仍旧无法写入正确的顺void Same_PrefixFrequenceHNode Hash char chlen；int casel=1；int flag；int i,j,strl,kNode *p ；FILE *fp1,*fp2；fp1=fopenPrefixFrequence.txt,r fp2=fopenPrefixFrequence_Result.txt,wwhile.feoffp1 / 读取文件fscanffp1,%s,ch；k=0；strl=strlench；flag=0 ；forj=0；j 名师归

19、纳总结 - - - - - - -第 8 页,共 12 页精选学习资料 - - - - - - - - - p=Hashj.right个人资料整理仅限学习使用；whilep fori=0；i ifchi=p-dataicontinue；else break； ifi=strl flag=1 ；k+；strcpyPCListk.data,p-data；PCListk.count=p-count p=p-next ； ifflag=0 fprintffp2,CASE；fprintffp2, %d:n,casel+； else ifflag=1 flag=0 ；fprintffp2,CASE；fpr

20、intffp2, %d:n,casel+；MP_SortPCList,k；/ 冒泡排序实现按次数大小写入单词及次数 ifk / 按要求查找的单词个数不超过十个,就全部写入 fori=1；i fprintffp2,%s %dn,PCListi.data,PCListi.count ； else / 超过十个,按显现次数大小取前十个写入 fori=1；i fprintffp2,%s %dn,PCListi.data,PCListi.count； 名师归纳总结 - - - - - - -第 9 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 fclose

21、fp1；问；题5完成-n见文件fclosefp2；printfn-PrefixFrequence_Result.txtn/Same_PrefixFrequence void MP_SortCNode PCList,int n/n 为数组元素个数 / 冒泡排序实现单词次数大小有序 int i,j,t；char data50；for j=n ；j1 ；j- for i=n ；in-j+1； i- / 从尾部开头循环比较,大的数往前移ifCListi.countPCListi-1.count t=PCListi.count；strcpydata,PCListi.data；PCListi.count=

22、PCListi-1.countstrcpyPCListi.data,PCListi-1.dataPCListi-1.count=t；strcpyPCListi-1.data,data； /MP_Sort 在试验了改写的冒泡的正确性时,将其植入原程序中,却依旧无法得到正确结果；时间仓 促,未能解决；4. 运行界面名师归纳总结 - - - - - - -第 10 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用五试验总结本次课程设计主要涉及三个数据结构的学问,一个是Hash 表,另一个是Trie Tree,第三个个是在信息检索中普遍使用的Inverted

23、 Index；完成本次课程设计的总体感受是,本次课程设计对数据结构的应用要求比较高,在整个设计过程深刻体会从最初编写程序到 最终实现题目所要求的执行,这是这个学期以来编写的最大而复杂的程序,综合利用了这 个学期所学习到的数据结构学问,发觉自己在学问把握上也并不是想象中那么娴熟；由于 不够娴熟而促使自己回来课本,不断回忆基本学问,在懂得题目意义的基础上,合理利用 书本及在线供应的资料；第一次接触这种比较大型的单词检索的程序设计,第一步很是关键；俗语说：万事开头难；拿到第一题时,脑袋里拂过许多想法,比如运用字符串的ASCII码来确定单词的储存位置,但是又考虑到单词库中单词量上万,这样庞大的数据必会

24、造成庞大冲突,即使使 用线性探测再散列处理冲突也不是很抱负；所以最终选用链地址法；跨出了第一步,其实 是很让人激励的；这次大作业,只做出来四小问,卡壳在第五问了；有一个重要缘由就是 对数据结构的挑选；要挑选既快又精确的,应当要属键树了；但是由于自己对树的学问掌 握的不够,所以没有在规定时间内完成；这次编程的突破是学习吸取了在线资料中的哈希字符串经典函数,大大改进了运行速 度；在今后编程的道路上有两点体会需要时刻提示自己：第一、当所编写的代码过长时,肯定要留意对变量的取名,以及对注释语句的重视,很简单就被长长的代码搞糊涂,也可 以留意备份；其次、在对程序的检验上不能放松,肯定要尽量确保其正确性,

25、由于一旦步 步联系紧密,一步错,步步错；由于本学期学时较紧,数据结构也重在实践,从理论运用到实际过程中发觉自己的不 足,这些是在仅仅依靠阅读课本基础上完全体会不到的；过程是艰辛的；一次一次遇到障碍,一次次订正,甚至有些痛楚,但当最终显示0 errors 0 warnings,运行得到你想要的结果,真的很有成就感！在今后的学习中肯定提高自己对课本上学问的把握的熟 练程度,并在此基础上期望能通过可获得渠道拓展视野以丰富自己的学问储备；老师评语：试验成果：指导老师签名：名师归纳总结 - - - - - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用批阅日期：名师归纳总结 - - - - - - -第 12 页,共 12 页