中北大学软件学院算法实验报告(附截图)(优选借鉴)

中北大学软件学院

实验报告

专 业：_________________________ 方 向：_________________________ 课程名称：_________________________ 班 级：_________________________ 学 号：_________________________ 姓 名：_________________________ 辅导教师：_________________________

2016年3月制

参11考 1

成绩：

实验时间 1.实验名称 2016年4月7日8时至10时 学时数 2 实验一 串匹配程序设计 2.实验目的 (1) 熟练掌握串匹配的含义 (2) 掌握BF算法匹配的过程并编程实现 (3) 熟悉C++编译环境的基本操作 3.实验内容 给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。请编写程序。 4.实验原理或流程图 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较次数是： n?m?1?i?1pi?(i?m)?n?m?1?i?11n?m?1?(i?m)?m(n?m?2)2 最坏情况是O（n×m）。 或者写书上P39页的伪代码描述。 参11考 2

5.实验过程或源代码 #include int BF(char S[], char T[]){ int index = 0; //主串从下标0开始第一趟匹配 int i = 0, j = 0; //设置比较的起始下标 while ((S[i] != '\\0') && (T[j] != '\\0')){ //模式匹配没有结束 printf(\从主串的第%d个位置开始与模式串进行匹配:（只输出回溯信息）\\n\ if (S[i] == T[j]){ //相同位置字符相同 i++; j++; //向后匹配 } else { //相同位置字符不同 printf(\由于主串下标i为%d的字符%c和模式串下标j为%d的字符%c失配\ index++; i = index; j = 0; //i和j分别回溯 printf(\所以i和j分别回溯到%d,%d重新开始匹配\\n\ } } if (T[j] == '\\0') return index + 1; //返回本趟匹配的开始位置（不是下标） else return 0; } int main(){ char S[100],T[100]; printf(\请输入主串S(不超过100个字符):\scanf(\printf(\请输入子串T(不超过100个字符):\scanf(\int index=BF(S,T); if(index == 0){ printf(\模式匹配失败！\} else{ printf(\模式匹配成功，子串%s在主串%s中首次匹配的位置是%d\ } return 0; 参11考

3