字符串的比较供参考

字符串合并、比较、子串定位一 目的利用数据结构课程的相关知识完成一个具有一定难度的综合设计题目，用C/C+设计一个程序，实现字符串合并、比较、子串定位,并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。二 需求分析1、本程序用C+来实现系统以菜单方式工作，分别实现三个功能；第一种功能，提示用户输入两个字符串，然后进行合并，将合并后的字符串显示；第二种功能，提示用户输入两个字符串，然后进行比较，将比较后的结果显示；第三种功能，提示用户输入一个字符串，然后提示输入待定位的子串，给出定位的结果，分别为：不存在，若存在则给出位置。2、演示程序以人与计算机的对话方式执行，即在计算机终端显示提示信息的基础下，用户可以选择执行的功能并输入字符串，每次功能执行完毕，计算机进行结果显示，用户可选择是否继续功能选择。3、用户选择第一种功能时，输入两个不同的字符串，计算机即会输出两个字符串的合并形式用户选择第二种功能时，输入两个相同或者不同的字符串，计算机会按照字典的排序对两个字符串进行比较用户选择第三种功能时，输入字符串即他的子串，计算机会对子串进行自动定位，输出定位结果三 概要设计1、数据类型定义本程序对字符串采用堆分配存储结构，堆分配存储既有定长顺序存储的优点，又可以在执行过程中动态的获得存储空间。串被定义为一个结构体，用函数malloc（）为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时串长也是存储结构的一部分。对串进行子串定位时对模式串创建一个next数组，存放模式串中每个字符的next函数值，其中，nexti表示当模式中第i个字符与主串中国相应字符失配时，在模式中需重新和主串中该字符进行比较的字符的位置。2、本程序包含两个模块（1）主程序模块main()定义及初始化；用户选择功能；用户输入数据，调用子程序，结果显示；（2）功能执行模块-实现对字符串的操作，主程序可以调用子程序 StrCreate(HString &T) T是要生成的字符串。操作结果：返回T字符串StrConcat(HString &T,HString s1,HString s2) T=s1+s2操作结果：实现对字符串的连接，由T传回s1和s2合成的字符串 StrCompare(HString s1,HString s2)s1,s2是两个待比较的字符串操作结果：按照字典顺序比较大小，若s1s2,则j0;若s1s2,则jchars;for(i=0;charsi;)/求字符串的长度+i;if(!i)/当字符串为空时T.ch=NULL;T.length=0;elseif(!(T.ch=(char*)malloc(i*sizeof(char)exit(0);for(j=0;js2,则j0;若s1s2,则j0;若s1=s2,则j=0; for(i=0;is1.length&is2.length;+i)if(s1.chi=!s2.chi)j=s1.chi-s2.chi;j=s1.length-s2.length;输出执行结果；void getnext(HString T,int next)/求模式串T的next函数值并存放在next数组中i=1,j=0;/i=j+1next0=0;/模式串中首个字符的next值为0while(iT.length)if(j=0|T.chi-1=T.chj-1)/若j为0或者模式串中第i-1个字符与第i个字符相同+i;+j;if(T.chi-1!=T.chj-1)nexti-1=j;/若模式串中第i-1个字符与第j-1个字符不相同,第i-1个字符的next函数值即为jelse nexti-1=nextj-1;/则第i-1个字符的next函数值即为第j-1个字符的next函数值 elsej=nextj-1;/模式串中第i-1个字符与第i个字符不相同void StrIndex(HString s,HString t)/利用模式串T的next函数求T在主串S中第一次出现的位置i=1;j=1getnext(t,next);/获取模式串T的next函数值并存放在next数组中，nexti表示当第i+1个字符与主串中相应字符失配时， /在模式中需重新和主串中该字符比较的字符的位置while(i=s.length&jt.length) cout子串在给出字符串中的位置是i-t.lengthendl;/匹配成功else cout匹配失败！endl;3、整个程序的流程图如下：开始输出主菜单选择界面输入choose的值Choose=？1：添加两个串2：比较两个串3：子串定位4：退出调用StrCreateStrConcat连接串StrCompare比较串StrIndex子串定位调用getnext输出结果结束错误输入五 调试分析第一个功能的测试第二个功能的测试：第三个功能的测试：匹配失败的测试：第四个功能的测试：1、通过写改程序，充分认识到字符串不通存储方式之间的区别，以及不同存储方式对字符串操作的影响。2、主函数调用子函数时，设计到传参，要注意程序里面还有局部变量和全局变量的区别，要时刻注意变量的值，循环调用要注意各个子函数的返回值。、3、字符串的定位又称做串的模式匹配，利用KMP算法对其进行匹配，利用递推的方法求的模式串的next函数值，定位函数再调用getnext函数。4、字符串连接和字符串比较模块的设计没有问题，在调试的时候也顺利进行，只有字符串的定位模块在设计时对变量的控制出现了一位的偏移，定位时位置一直出错，后来进行单步跟踪调试，将偏移除去后即顺利进行调试。5、模式匹配算法的时间数量级是（），和分别为主串和模式串的长度。而求函数值算法的时间数量级是（），为模式串的长度。六 测试结果1、测试计划（1）功能一的测试：选择执行功能一，输入任意两个长度小于100的字符串，Eg:abcdeg和hijk输出为：abcdeghijk（2）功能二的测试：选择执行功能二，输入任意两个长度小于100的串，Eg：abc和def输出为：第一个字符串小于第二个字符串（3）功能三的测试：选择执行功能三，输入任意一个长度小于100的字符串，再输入一个他的子串Eg：abcdef和bc输出为：子串的位置是2错误验证：选择执行功能三，输入任意一个长度小于100的字符串，再任意输入一个非子串Eg：abcdef和d输出为：匹配失败七 用户使用说明1、本程序在环境下运行。2、程序运行后，自动执行菜单输出，有输出提示，让用户自己输入字符串，每次当用户输入后，输出结果并询问用户是否继续进行测试，以下为程序运行后的画面，通过菜单方式，使用户能更好的使用该程序。3、功能执行完毕，输入，程序结束执行。 八。课程设计总结1、通过本次课程设计，我学会了对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理，进一步加强课对数据结构课程的认识等。2、在课程设计过程中，我对模式匹配算法有了进一步的认识，对这个算法的有了深入了解，在调试过程中，通过单步跟踪加强了我的程序调试能力。3、通过对算法时间复杂度的分计算，我对算法的精髓有了深入的体会，不同的数据结构有不同的适应之处，不同的存储结构有不同的便利。文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!13 / 13