数据结构实习报告单词查找.docx
- 文档编号:18329025
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:26
- 大小:319.19KB
数据结构实习报告单词查找.docx
《数据结构实习报告单词查找.docx》由会员分享,可在线阅读,更多相关《数据结构实习报告单词查找.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构实习报告单词查找
数据结构课程设计
实习报告
题目:
匹配具有最长前缀的单词
学号:
1210522
姓名:
何厚华
年级:
大二
学院:
计算机与控制工程学院
专业:
计算机科学与技术
完成日期:
2014年4月30日
授课教师:
辛运帏
目录
1.题目.................................................2
2.要求.........................................................................2
3.程序实现...............................................................2
3.1程序运行及编译环境................................................2
3.2程序描述...................................................2
3.3实现功能.......................................................3
3.3.1子功能模块......................................................3
3.3.1.1数组的子功能模块..........................................3
3.3.1.1.1数组的子功能模块1...................................3
3.3.1.1.2数组的子功能模块2...................................3
3.3.1.1.3数组的子功能模块3...................................4
3.3.1.1.4数组的子功能模块4...................................5
3.3.1.1.5数组的子功能模块5...................................6
3.3.1.1.5数组的子功能模块6...................................6
3.3.1.1.5数组的子功能模块7...................................8
3.3.1.2BST的子功能模块..............................................9
3.3.1.2.1数据结构................................................9
3.3.1.2.2BST的子功能模块1..............................10
3.3.1.2.3BST的子功能模块1............................11
3.3.1.2.4BST的子功能模块1..............................12
3.3.1.2.5BST的子功能模块1............................13
3.3.1.3算法及程序说明................................................15
3.4运行结果...........................................................15
3.4.1基本功能......................................................13
3.5尚未解决的问题..........................................................21
4本次作业心得................................................................21
1.题目
设集合S由若干单词(英文)组成,给定字符串K,在S中查找与K最佳匹配的结果。
最佳匹配的结果定义为:
与K有最长共同前缀的字符串。
例:
S={abc,bdef,zhen,zhao,abdd},K1=zhao,K2=abdf,K3=cheng,则与K1最匹配的结果是zhao,与K2最匹配的结果是abdd,与K3最匹配的结果是ε(空串)。
2.要求
使用文件保存初始的单词数据(至少100个),以逗号分隔。
程序中将单词读入到内存中,并据此建立一种数据结构用来保存这些单词。
由键盘输入查找目标,在你定义的结构上进行查找,屏幕上显示出最佳匹配的字符串。
3.程序实现
3.1程序运行及编译环境
程序是用VisualStudio2010即VS10.0编译的。
可以在windows系列的操作系统上运行。
3.2程序描述
该程序主要用于实现单词的匹配,此次试验给出了两种不同的数据结构下插入单词以及查找单词的比较,得出数组存储以及匹配效率均比BST要低的结论,为了衡量他们的优劣,本人在同一个程序了使用了两种方法去生成一个具有100002个互不相同的单词的数据结构,然后比较它们的插入时间以及发出查询请求后的查询时间。
其流程如下:
A).由程序生成一个文件,文件里面全部是互不相同的单词
B).读入文件里的单词,创建单词数组
C)创建单词树
D).查询命令循环,并按要求把词库没有的单词添加到词库中去
E).中序遍历单词树,把单词按照从小到大的顺序排列,以方便查找
F).释放一些空间,完成程序
3.3实现功能
本程序不仅仅是为了实现单词的查找,而且还实现了比较不同的数据结构对于存储以及插入的效率比较。
先由程序生成100000个单词,然后分别用数组和树的方式保存这100000个单词,给出构建它们所需要的时间,单位是毫秒,然后在查询的时候,也通过两种方式查询,计算并比较它们找到所需单词的时间。
如果查找的单词在词库中没有出现,那么可以选择性的把这个单词添加到词库中去。
另外还具有统计词库单词个数的功能。
(当然了,这些功能并不是实验要求的)
3.3.1子功能模块
子功能按照是否对象的方法分类:
数组的处理以及树的处理;
3.3.1.1数组的子功能模块
3.3.1.1.1数组的子功能模块1
/*****************************************************************
函数原型:
intCompare(char*src,char*dst);
函数功能:
将两个字符串比较,返回前缀相同的位数
函数参数:
src:
源字符串,dst:
目的字符串
返回值说明:
例如返回2说明src与dst前两个字符一样,后面的字符不一样
******************************************************************/
intCompare(char*src,char*dst){
intsimilarity=0;
while
(1){
if(*(src+similarity)!
=*(dst+similarity))
returnsimilarity;
similarity++;
}
}
3.3.1.1.2数组的子功能模块2
/*****************************************************************
函数原型:
boolIsSame(data*src,data*dst)
函数功能:
判断两个字符串是否一样
函数参数:
src:
源字符串,dst:
目的字符串
返回值说明:
true表示两个字符串一样;false表示两个字符串不一样
******************************************************************/
boolIsSame(data*src,data*dst){
for(inti=0;;i++){
if(*(src+i)!
=*(dst+i))
returnfalse;
if(*(src+i)==*(dst+i)&&*(src+i)==0)
returntrue;
}
}
3.3.1.1.3数组的子功能模块3
/*****************************************************************
函数原型:
boolStrCmp(data*src,data*dst);
函数功能:
判断两个字符串的大小
函数参数:
src:
源字符串,dst:
目的字符串
返回值说明:
0表示src小于dst,1表示src大于dst
******************************************************************/
boolStrCmp(data*src,data*dst){
for(inti=0;;i++){
if(*(src+i)<*(dst+i))
returnfalse;
if(*(src+i)>*(dst+i))
returntrue;
}
}
3.3.1.1.4数组的子功能模块4
/*****************************************************************
函数原型:
voidCreateWords(intcount,ofstream&fout);
函数功能:
按照一定的顺序创建一定数目的互不相同的单词
函数参数:
count:
生成单词的个数,fout:
文件生成在与之相关联的文本中
实现方法:
生成一个26个字母组成的字符数组,然后按照二十六进制的形式
依次生成不同的字符串表示不同的单词。
不同的十进制数对应的
二十六进制数也不一样,所以,所得单词互不相同。
******************************************************************/
voidCreateWords(intcount,ofstream&fout){
chara[26];
a[0]='a';
for(inti=1;i<26;i++)
a[i]=a[0]+i;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实习 报告 单词 查找
![提示](https://static.bingdoc.com/images/bang_tan.gif)