欢迎来到天天文库
浏览记录
ID:56734498
大小:2.10 MB
页数:49页
时间:2020-07-06
《中北大学软件学院算法实验报告(附截图).doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、.中北大学软件学院实验报告专业:_________________________方向:_________________________课程名称:_________________________班级:_________________________学号:_________________________姓名:_________________________辅导教师:_________________________2016年3月制..成绩:实验时间2016年4月7日8时至10时学时数21.实验名称实验一串匹配程序设计2.实验目的(1)熟练掌握串匹配的含义(2)掌握BF算法匹配的过程
2、并编程实现(3)熟悉C++编译环境的基本操作3.实验容给定两个字符串S和T,用BF算法,在主串S中查找字串T,输出结果,输出时要求有文字说明。请编写程序。4.实验原理或流程图基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹配的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。设串S长度为n,串T长度为m,在匹配成功的情况下,考虑最坏情况,即
3、每趟不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处,则在i-1趟不成功的匹配中共比较了(i-1)×m次,第i趟成功的匹配共比较了m次,所以总共比较了i×m次,因此平均比较次数是:最坏情况是O(n×m)。或者写书上P39页的伪代码描述。..5.实验过程或源代码#includeintBF(charS[],charT[]){intindex=0;//主串从下标0开始第一趟匹配inti=0,j=0;//设置比较的起始下标while((S[i]!=' ')&&(T[j]!=' ')){//模式匹配没有结束printf("->从主串的第%d个位置开始与模式串进行匹
4、配:(只输出回溯信息)",i);if(S[i]==T[j]){//相同位置字符相同i++;j++;//向后匹配}else{//相同位置字符不同printf("由于主串下标i为%d的字符%c和模式串下标j为%d的字符%c失配",i,S[i],j,T[j]);index++;i=index;j=0;//i和j分别回溯printf("所以i和j分别回溯到%d,%d重新开始匹配",i,j);}}if(T[j]==' ')returnindex+1;//返回本趟匹配的开始位置(不是下标)elsereturn0;}intmain(){charS[100],T[100];printf("请输入
5、主串S(不超过100个字符):");scanf("%s",S);printf("请输入子串T(不超过100个字符):");scanf("%s",T);intindex=BF(S,T);if(index==0){printf("模式匹配失败!");}else{printf("模式匹配成功,子串%s在主串%s中首次匹配的位置是%d",T,S,index);}return0;}..6.实验结论及心得通过本次实验我理解了使用蛮力法解决问题的特点,蛮力法的设计思想是直接基于问题本身的描述来设计算法,即不采用任何方法来精简计算过程、运算次数或者设法简化问题本身。所以蛮力法设计的算法虽然简单易懂,但是效
6、率却往往不是很令人满意,比如串的模式匹配问题中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失败就会产生回溯,如果能利用已有的匹配结果来减少回溯就可以提高效率,如KMP算法。..成绩:实验时间2016年4月7日8时至10时学时数21.实验名称实验二排序问题程序设计2.实验目的(1)掌握选择排序和起泡排序的基本思想(2)掌握两种排序方法的具体实现过程(3)在掌握的基础上编程实现两种排序方法3.实验容输入一个待排序的序列,分别用选择排序和起泡排序两种排序方法将其变换成有序的序列,输出结果,输出时要求有文字说明。请编写程序。4.实验原理或流程图书上P42页选择排序想法三点抄上去书
7、上P43页冒泡排序想法三点抄上去..5.实验过程或源代码//----------------------------选择排序----------------------------------#include//对含有n个数的数组进行遍历voidvisit(intr[],intn){for(inti=0;i
此文档下载收益归作者所有