文档介绍：课程设计报告题目:字符串匹配算法实测分析课程名称:数据结构专业班级:计科XX学号:UXXXXXXX姓名:FSH指导教师:xxx报告日期::掌握线性结构中的字符串的物理存储结构与基本算法,通过查询阅读文献资料,拓广知识面以及培养学生科研能力。设计内容:结合教材上的字符串匹配算法,查询文献资料检索4种以上的有关精确匹配算法,掌握算法原理并实现。设计要求:(1)查阅相关的文献资料,特别是留意年近些年发表的文献资料;(2)要求对各种算法进行理论分析,同时也对实测结果进行统计分析。测试数据要求有一定规模,比如一本书或不少于50篇的中英文文献。(3)要求界面整洁、美观,操作方便;报告内容:(一),运行界面,及运行结果截图(二),各算法的具体分析,包括起源,基本思路,实例分析,具体实现,和本算法代码。(三),总程序源代码。(四),课程设计心得(一),运行界面,运行结果说明:运行代码显示界面:对于S串可以手动输入字符串检索,也可以选择在计算机里建好的TXT文件,按任意键退出。按2确认,键入一本书的TXT文件,运行如下输入待搜索子串“史记”得到运行结果,各算法均返回子串在母串出现的位置执行算法得运行结果,返回子串在母串所有出现位置。结果显示运行时间用以统计时间效率:另一段检索结果的时间截图结果显示如下:(二),(Bruteforce)算法:.算法起源:此算法思路简单,容易想到,没有确定的提出者‘:之所以成为穷举法,即如名字所言,逐个比较直至穷尽/结束,基本思路为:假设S为母字符串,长度为lengthS,T为子字符串,(从第一位i=1元素开始)开始一次提取长度为lengthT的一串字符挨个与S字符串比较是否相等,若相等,则匹配成功并输出i,然后在S上后移一位继续比较, window::假设母串S:aluhfui子串T:goodboyN=lengthS–length+aluhfuiedgoodb (edgoodb不等于goodboy且i<N,i+1即后移一位比较)dgoodbo (dgoodbo不等于goodboy且i<N,i+1即后移一位比较)goodboy (goodboy等于goodboy且i<N,匹配成功,输出i,后移一位比较)......aluhfui (i!<N,字符相等,输出i; 字符不等,结束i;:字符串的物理存储实现—malloc函数申请空间返回unsignedchar型指针,线性结构;设置参数:i,用以表示检测位,范围为(1,N)用for循环语句判断是否遍历S字符串。其中N=lengthS–length+1;辅助函数:Substring(S,i,n)作用为提取S字符串里从第i位起长度为n的字符串,其返回值为unsignedchar型指针。Substring算法:statussubstring(strings,intpose,intlen)//子字符串提取函数substring;返回值为子str字符串{unsignedchar*sub;sub=malloc(10000*sizeof(unsignedchar));inti=strlen(s);intk=pose+len-1;if(i<0||pose>i||k>i)returnNULL;inta;for(a=0;a<len;a++,pose++)sub[a]=s[pose-1];sub[a]='\0';returnsub;}:voidindex(strings,stringt){intm,n,i;stringtest;test=malloc(10000*sizeof(unsignedchar));n=strlen(s);m=strlen(t);i=1;inta=0;intjishu[1000];//数组用来计数匹配成功的位置printf("\n穷举算法运行得:\n");while(i<=n-m+1){strcpy(test,substring(s,i,m));if(strcmp(test,t)!=0)++i;else{jishu[a]=i;printf("匹配成功输出:%d\n",jishu[a]);++i;++a;}//返回子串在主串中的位置}//while//S中不存在与T相等的子串}//:穷举算法虽然易于理解,也容易实现,但是效率却比较低下,因为该算法对于S字符串上的前N位元素,每个元素都提取字符串并进行挨个比较,比较完全匹配或者出现失配时后移一位继续比较,若S长度m,T长度n,则找到所有匹配位置的时间O