数据结构求最大公共子串

1数据结构课程设计2014-2015年第一学期院系：计算机科学与技术专业：软件工程课题：求最大公共子串年级班：姓名：学号：成绩：指导教师：王爱平2014.10.82目录1课程设计的目的…………………………………………………………32需求分析…………………………………………………………………33课程设计报告内容………………………………………………………33.1概要设计………………………………………………………………33.2详细设计………………………………………………………………33.4调试分析………………………………………………………………53.5用户手册………………………………………………………………53.6测试结果………………………………………………………………63.7程序清单………………………………………………………………64小结……………………………………………………………………75参考文献………………………………………………………………731.课程设计的目的(1)熟练使用C语言编写程序，解决实际问题;(2)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2需求分析以顺序存储结构存储串，求两个字符串的最大的公共子串，约束字符的最大长度是256，同时如果没有的公共的，也会出现提示信息。公共子串指的是字符串U如果既是字符串S的子串又是字符串T的子串，则字符串U是字符串S和T的一个公共子串。最长公共子串：字符串S和T的最长公共子串是指字符串S和T的所有公共后缀中长度最大的后缀。例如：给定3个长度分别为4，4的字符串“abab”，“baba”，它们的公共子串有“”，“a”，“b”，“ab”，“ba”，“aba”，“bab”。其中最长公共子串(LCS)即为“aba”或“bab”。３概要设计３．１主界面的设计３．２存储结构设计顺序存储结构表示串3.3详细设计（1)voidsearch(SStringM,SStringP)//匹配函数{(2)voidmain()3.3.1程序运行的流程图各个函数之间的调用关系Voidmain()Voidsearch()4程序运行的流程图：3.3.2运行截图开始提示输入第一字符串输入第一个字符串提示输入第二个字符串输入第二个字符串求两个字符串的长度调用匹配函数结束53.4调试分析调试的时候，对串的匹配的开始没有弄懂，导致在调试的时候出现了错误。后来自己琢磨以及手工的演算是调试成功。3.5用户手册3.4.1本程序执行文件为“最大公共子串.exe。”3.4.2在进入本系统的主界面后，按照提示输入第一个字符串和第二个字符串3.4.3字符串的最大个数数2563.6测试结果结果运行成功3.7程序清单#includestdio.h#includestdlib.h#includestring.h#defineMax256typedefstruct{charch[Max];intlength;}SString;voidsearch(SStringM,SStringP)//匹配函数{inti,j,k,a,c;intb=1;intm=P.length;intn=M.length;intindex=0;//第一个匹配项intmaxlen=0;//最大的匹配长度intflag;for(i=0;i=n;i++){k=i;for(j=0;j=m;j++)6{a=0;while(jm&&M.ch[k]==P.ch[j]){k++;j++;a++;flag=1;}if(flag==1){if(amaxlen){maxlen=a;index=j-a;//匹配的首项}}}}if(maxlen!=0){printf(\n公共子串最大长度为:%d,最长公共子串为：,maxlen);for(;maxlen0;maxlen--){printf(%c,P.ch[index++]);}printf(\n\n);}elseprintf(\n您输入的两个字符串无公共子串！\n\n);}voidmain(){SStringM1,P1;system(cls);printf(请输入第一个字符串:);gets(M1.ch);printf(请输入第二个字符串:);gets(P1.ch);M1.length=strlen(M1.ch);P1.length=strlen(P1.ch);printf(\n);printf(第一个串为：%s，长度：%d\n,M1.ch,M1.length);7printf(第二个串为：%s，长度：%d\n,P1.ch,P1.length);search(M1,P1);system(pause);}4小结在这次的赶作业的过程中，体会到了要多动手，要注意理论与实际的结合，对平时的知识要求掌握熟练，这样在编程的时候可以快速的实现自己的想法，提高自己完成作业的速度。多注意对资料的查阅，这样能够掌握一些自己不太熟悉的东西，提高自己的知识储备。5参考文献1严蔚敏，吴伟民编著.数据结构(C语言版)--北京:清华大学出版社，2007.2严蔚敏，吴伟民米宁编著.数据结构题集(C语言版)--北京:清华大学出版社，2007