串的基本演示操作系统课程设计

1、课程设计说明书程序设计的主要思路：首先构思所写程序的框架，我在主函数中输入字符串，并调用函数传给定义的顺序串，主函数中运用了do-while语句和switch语句，以此来供使用者选择他所需做的操作。选择所需操作时，调用相应的函数实现功能的应用，输出所需结果。同时为了操作系统的好看，我运用了system（）等改变了运行界面的颜色。1、 需求分析实现串的基本操作，如：（1） 输入两个串，并赋值给顺序串s,t（2） 实现将串t复制给串s（3） 判断两串的大小（4） 求两串的长度（5） 实现两串的连接（6） 求子串（7） 插入（8） 删除（9） 替换（10） 输出串（11） 实现串的匹配，如：非模式匹

2、配、简单模式匹配、KMP匹配（12） 实现串的逆置（13） 查找（14） 转换（将大写字母转换为小写字母，小写字母转换为大写字母）2、 概要设计2.1 主界面设计先设置了一个检测运行环境系统 。如图：为了实现串的各项基本操作，设计了一个含有多个菜单项的主控菜单模式以连接各种基本操作，以方便使用系统。如图：在选项9中我又设计了一个含三个菜单项的小主菜单以连接三个不同的匹配算法。如图： 2.2 数据结构设计 系统采用线性表的顺序存储结构表示，其中存放串字符和串长。此外定义了一个常量max，表示字符串的最大长度。 2.3 系统功能设计 此系统中设置了14个子功能模块，并在第9个功能中又设置了3个子功

3、能模块。 （1）将串t复制给串s模块，由strcopy()函数实现。 （2）比较两串的大小模块。由strcmp()函数实现。 （3）求串的长度模块。由strlength()函数实现。 （4）串的查找模块。由chaz()函数实现。 （5）求子串模块。由substr()函数实现。 （6）串的连接模块。由concat()函数实现。 （7）输出串模块。由dis()函数实现。 （8）将串s2插入到s1的第i个字符中模块。 （9）串的模式匹配模块。可以有三个函数实现：index1()函数、index()函数、kmpindex()函数。 （10）从串s中删除第i个字符开始的长度为j的子串模块。由delstr

4、()函数实现。 （11）在s串中将第i个字符开始的j个字符构成的子串用串t替换模块。由repstr()函数实现。 （12）串的逆序模块。由ReverseSq()函数实现。 （13）串的转换模块。由zhuanh()函数实现。 （14）串的修改模块。由change()函数实现。3.模块设计 整个程序的流程图。如图： 开始输入串cstr,Str并赋值给串s,t1串t复制给s2判断串的大小3求串长4串的连接5求子串6插入7删除8替换9匹配10输出串11串的逆序12串的查找13串的转换14串的修改根据选择输出相应的运行结果结束stra()函数strcmp()函数strlegth()函数Concat()函

5、数substr()函数insstr()函数delstr()函数repstrt()函数pipei()函数dis()函数ReverseSq()函数chaz()函数zhuanh()函数change()函数选择(n!=0)而选择9中还有一个流程，如图：选择9选择（n!=0）1非模式匹配2 BF模式匹配3 KMP模式匹配index1()函数index()函数kmpindex()函数getnext()函数输出相应的结果4.详细设计 4.1数据结构设计 系统采用串的顺序存储结构（顺序串）存储串的基本内容。类型定义如下： typedef struct char datamax; int length; sqs

6、tring; 4.2系统主要模块设计 （1）将字符常量cstr,Str赋值给串s,t模块，由stra()函数实现。该模块的算法思想是：用for循环将cstri赋值给si；并s.length=i。 该模块的算法描述如下： void stra(sqstring &s,char cstr)/将字符串常量赋给串s,s为引用型参数 int i; for(i=0;cstri!='0'i+) s.datai=cstri; s.length=i; （2）将串t复制给串s模块，由strcopy()函数实现。该模块的算法思想是：用for循环将顺序串t的内容复制给顺序串s，并顺序串s的长度为

7、顺序串t的长度。 该模块的算法描述如下： sqstring strcopy(sqstring s,sqstring t)/将串t复制给串s int i;for(i=0;i<t.length;i+)s.datai=t.datai;s.length=t.length;return s; （3）比较两串的大小模块。由strcmp()函数实现。该模块的算法思想是：首先比较s和t两串共同长度范围内的对应字符；若s<t，返回-1；s>t，返回1；s=t，按上述规则继续比较。然后当s和t对应字符均相同时，比较s和t的长度；若s<t，返回-1；s>t，返回1；s=t，返回0。 该

8、模块的算法描述如下： int strcmp(sqstring s,sqstring t)/比较两串的大小int i,com;if(s.length<t.length)com=s.length;/求串s、t的共同长度elsecom=t.length;for(i=0;i<com;i+)/在共同长度内逐个字符比较if(s.datai<t.datai)return -1;else if(s.datai>t.datai)return 1;if(s.length=t.length)/s=treturn 0;else if(s.datai<t.datai)/s<tretu

9、rn -1;elsereturn 1;/s>t （4）求串的长度模块。由strlength()函数实现。该模块的算法思想是：返回串s、t中的字符个数。 该模块的算法描述如下：int strlength(sqstring s)/求串的长度return s.length; （5）串的连接模块。由concat()函数实现。该模块的算法思想是：先定义一个顺序空串str存储连接后的新串，其长度为串s和t的长度之和。先将s的内容赋值给串str，在接着其后将t的内容赋值给它。 该模块的算法描述如下： sqstring concat(sqstring s,sqstring t)/串的连接sqstring

10、 str;int i;str.length=s.length+t.length;for(i=0;i<s.length;i+)/将s.data0.s.length-1复制到strstr.datai=s.datai;for(i=0;i<t.length;i+)/将t.data0.t.length-1复制到strstr.datas.length+i=t.datai;return str; （6）求子串模块。由substr()函数实现。该模块的算法思想是：先定义一空串str存储求的子串，找到所求子串的位置，利用for循环将长度为子串长度的串赋值给串str。若参数不对，返回空串。 该模块的算

11、法描述如下： sqstring substr(sqstring s,int i,int j)/求子串sqstring str;int k;str.length=0;if(i<=0|i>s.length|j<0|i+j-1>s.length)return str;/参数不正确时返回空串for(k=i-1;k<i+j-1;k+)/将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.length=j;return str; （7）将串s2插入到s1的第i个字符中模块。该模块的算法思想是：先定义一个空串str，用for循环将s1的前i-

12、1个字符赋值给str，在接着将串s2的字符赋值给str，最后将s1的i后的字符赋值给str。若参数不对，返回一个空串。 该模块的算法描述如下： sqstring instr(sqstring s1,int i,sqstring s2)/将串s2插入到串s1的第i个字符中int j;sqstring str;str.length=0;if(i<=0|i>s1.length+1)return str;/参数不正确时返回空串for(j=0;j<i-1;j+)/将s1.data0.i-2复制到strstr.dataj=s1.dataj;for(j=0;j<s2.length;j

13、+)/将s2.data0.s2.length-1复制到strstr.datai+j-1=s2.dataj;for(j=i-1;j<s1.length;j+)/将s1.datai-1.s1.length-1复制到strstr.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;（8）从串s中删除第i个字符开始的长度为j的子串模块。由delstr()函数实现。该模块的算法思想是：先定义一个空串str，将s中前i-1个字符赋值给str，再将从i+j-1到s.length-1的字符赋值给str。 该模块的算法描述如

14、下： sqstring delstr(sqstring s,int i,int j)/从串s中删除第i个字符开始的长度为j的子串int k;sqstring str;str.length=0;if(i<=0|i>s.length|i+j>s.length+1)return str;/参数不正确时返回空串for(k=0;k<i-1;k+)/将s.data0.i-2复制到strstr.datak=s.datak;for(k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datak-j=s.datak;str

15、.length=s.length-j;return str;（9）在s串中将第i个字符开始的j个字符构成的子串用串t替换模块。由repstr()函数实现。该模块的算法思想是：先定义一个空串str，将s中前i-1个字符赋值给str，再将串t的字符串赋值给str，最后将从i+j-1到s.length-1的字符赋值给str。 该模块的算法描述如下： sqstring repstr(sqstring s,int i,int j,sqstring t)/在串s中将第i个字符开始的j个字符构成的子串用串t替换int k;sqstring str;str.length=0;if(i<=0|i>s

16、.length|i+j>s.length+1)return str;/参数不正确时返回空串for(k=0;k<i-1;k+)/将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;k<t.length;k+)/将t.data0.t.length-1复制到strstr.datai+k-1=t.datak;for(k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datat.length+k-j=s.datak;str.length=s.length-j+t.length;ret

17、urn str;（10）串的模式匹配模块。可以有三个函数实现：index1()函数、index()函数、kmpindex()函数。该模块的算法思想是：index()函数：从目标串s的第一个字符开始和模式串t中的第一个比较，若相等，则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符比较。以此类推，若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功，并返回位置i；否则，匹配失败，返回-1。 kmpindex()函数：设s为目标串，t为模式串，i指针和j指针分别指示目标串和模式串中正待比较的字符，令i和j的初值为0.若有si=tj，则i和j

18、分别自增1；否则i不变，j退回到j=nextj的位置（即模式串右滑），比较si和tj，若相等则指针个自增1，否则j再退回到下一个j=nextj位置（即模式串继续右滑），再比较si和tj。以此类推，直到出现下列两种情况之一：1、j退回到某个j=nextj位置时有si=tj，则指针各自增1后继续匹配；2、j退回到j=-1时，此时令i、j指针各自增1，即下一次比较si+1和t0。 该模块的算法描述如下： int index(sqstring s,sqstring t)/BF模式匹配int i=0,j=0,k;while(i<s.length&&j<t.length)if(

19、s.datai=t.dataj)/继续匹配下一个字符i+; /主串和子串依次匹配下一个字符j+;else /主串和子串指针回溯重新开始下一次匹配i=i-j+1; /主串从下一个位置开始匹配j=0; /子串从头开始匹配if(j>=t.length) k=i-t.length; /返回匹配的第一个字符的下标elsek=-1;return k; /模式匹配不成功int index1(sqstring s,sqstring t)/非模式匹配int i,j,k;for(i=0;i<s.length;i+)for(j=i,k=0;s.dataj=t.datak;j+,k+);if(k=t.le

20、ngth)return i;/返回匹配的第一个字符的下标return -1;/模式匹配不成功void getnext(sqstring t,int next)/由模式串t求出next的值int j,k;j=0;k=-1;next0=-1;while(j<t.length-1)if(k=-1|t.dataj=t.datak)/k为-1或比较的字符相等j+;k+;nextj=k;elsek=nextk;int kmpindex(sqstring s,sqstring t)/KMP模式匹配int nextmax,i=0,j=0;getnext(t,next);while(i<s.leng

21、th&&j<t.length)if(j=-1|s.datai=t.dataj)i+; /i,j各增j+;elsej=nextj; /i不变，j后退if(j>=t.length)return(i-t.length); /返回匹配模式串的首字符下标elsereturn(-1); /返回不匹配标志（11）串的逆序模块。由ReverseSq()函数实现。该模块的算法思想是：定义两自变量i，j，i=0，j=s.length-1，将其前后对调后，i自增1，j自减1。直至i>=j为止。并输出其对调后的字符串。 该模块的算法描述如下： void ReverseSq(sqstr

22、ing s)int c,i,j;char T;i=0;j=s.length-1;while(i<j) T=s.datai;s.datai=s.dataj;s.dataj=T;i+;j-;for(c=0;c<s.length;c+)printf("%c",s.datac);printf("n");（12）串的查找模块。由chaz()函数实现。该模块的算法思想是：输入一字符与串中字符逐一比较，若相等，则输出其最大下标，并用一个自变量自增1记录其出现的次数。若不等，则输出串中无这个字符！ 该模块的算法描述如下： void chaz(sqstring

23、 s,char m)int i,c=0,flag=0;for(i=s.length-1;i>=0;i-)if(s.datai=m)c+;printf("character出现在串s中对应的最大下标：%dn",i);flag=1;break;if(flag=0)printf("串s中无这个字符！n");printf("该字符在串中出现的次数：%dn",c);（13）串的转换模块。由zhuanh()函数实现。该模块的算法思想是：若字符在az之间，则将字符减去32后输出。若字符在AZ之间，则将字符加上32后输出。 该模块的算法描述如下

24、： void zhuanh(sqstring s)int i;for(i=0;i<s.length;i+)if(s.datai<='z'&&s.datai>='a')printf("%c ",s.datai-32);if(s.datai<='Z'&&s.datai>='A')printf("%c ",s.datai+32);（14）串的修改模块。由change()函数实现。该模块的算法思想是：定义两串cstr，Str，输入其内容，

25、调用函数stra()（将输入串赋值给顺序串）。 该模块的算法描述如下： void change(sqstring &s,sqstring &t)char cstrmax,Strmax;int i;printf("输入串cstr:");i=0;getchar();while(cstri=getchar()!='n')i+;cstri='0'printf("输入串Str:");i=0;while(Stri=getchar()!='n')i+;Stri='0'printf(&quo

26、t;把串cstr赋值给串s:");stra(s,cstr);dis(s); printf("把串Str赋值给串t:");stra(t,Str);dis(t);（15） 串的输出模块。由dis()函数实现。该模块的算法思想是：用for循环在其长度范围内依次输出各字符。 该模块的算法描述如下： void dis(sqstring s)/显示串s中的所有元素int i;if(s.length>0)for(i=0;i<s.length;i+)printf("%c",s.datai);printf("n");5.调试分析

27、6.用户使用说明 用户使用时。先输入你所需用的两串。在根据你所需操作的内容选择其选项，注意输入的是数字，不要输入除数字以外的内容。若想结束程序，只需输入0即可。7.对所设计的软件进行自我评价 我觉得我这次所写的程序很简单，除去模式匹配函数以外其它的所需调用的函数基本可以由大一所学写出来。所以这个程序我用了这学期所学的顺序串来实现这些功能。其中定义了存放串字符和串长度。在顺序串中，串中的字符被依次存放在一组连续的存储单元里。而串的顺序存储有两种方法：非紧缩格式和紧缩格式。非紧缩格式：一个内存单元存储一个字符。紧缩格式：一个内存单元可以存储多个字符。我所写的程序用地是非紧缩格式存储方法。这个软件的

28、功能多，充分应用了do-while语句和switch语句，这样可让使用者随意选择所需操作的功能。其中字符串的匹配更是运用了三个匹配：非模式匹配、BF模式匹配、KMP模式匹配。但是有一个问题尚未得到解决，那就是输入选择时，若不小心输入一个字符，运行时它会无限循环。所以使用时输入数字，输入0时将结束程序。9.程序源代码#include<stdio.h>#include<string.h>#include<stdlib.h>#define max 100typedef structchar datamax;int length;sqstring;void stra

29、(sqstring &s,char cstr)/将字符串常量赋给串s,s为引用型参数int i;for(i=0;cstri!='0'i+)s.datai=cstri;s.length=i;void dis(sqstring s)/显示串s中的所有元素int i;if(s.length>0)for(i=0;i<s.length;i+)printf("%c",s.datai);printf("n");sqstring strcopy(sqstring s,sqstring t)/将串t复制给串s int i;for(i=0

30、;i<t.length;i+)s.datai=t.datai;s.length=t.length;return s;int strcmp(sqstring s,sqstring t)/比较两串的大小int i,com;if(s.length<t.length)com=s.length;/求串s、t的共同长度elsecom=t.length;for(i=0;i<com;i+)/在共同长度内逐个字符比较if(s.datai<t.datai)return -1;else if(s.datai>t.datai)return 1;if(s.length=t.length)/

31、s=treturn 0;else if(s.datai<t.datai)/s<treturn -1;elsereturn 1;/s>tint strlength(sqstring s)/求串的长度return s.length;sqstring concat(sqstring s,sqstring t)/串的连接sqstring str;int i;str.length=s.length+t.length;for(i=0;i<s.length;i+)/将s.data0.s.length-1复制到strstr.datai=s.datai;for(i=0;i<t.le

32、ngth;i+)/将t.data0.t.length-1复制到strstr.datas.length+i=t.datai;return str;sqstring substr(sqstring s,int i,int j)/求子串sqstring str;int k;str.length=0;if(i<=0|i>s.length|j<0|i+j-1>s.length)return str;/参数不正确时返回空串for(k=i-1;k<i+j-1;k+)/将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.length=j;ret

33、urn str;sqstring instr(sqstring s1,int i,sqstring s2)/将串s2插入到串s1的第i个字符中int j;sqstring str;str.length=0;if(i<=0|i>s1.length+1)return str;/参数不正确时返回空串for(j=0;j<i-1;j+)/将s1.data0.i-2复制到strstr.dataj=s1.dataj;for(j=0;j<s2.length;j+)/将s2.data0.s2.length-1复制到strstr.datai+j-1=s2.dataj;for(j=i-1;j

34、<s1.length;j+)/将s1.datai-1.s1.length-1复制到strstr.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;sqstring delstr(sqstring s,int i,int j)/从串s中删除第i个字符开始的长度为j的子串int k;sqstring str;str.length=0;if(i<=0|i>s.length|i+j>s.length+1)return str;/参数不正确时返回空串for(k=0;k<i-1;k+)/将s.

35、data0.i-2复制到strstr.datak=s.datak;for(k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datak-j=s.datak;str.length=s.length-j;return str;sqstring repstr(sqstring s,int i,int j,sqstring t)/在串s中将第i个字符开始的j个字符构成的子串用串t替换int k;sqstring str;str.length=0;if(i<=0|i>s.length|i+j>s.length+1)re

36、turn str;/参数不正确时返回空串for(k=0;k<i-1;k+)/将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;k<t.length;k+)/将t.data0.t.length-1复制到strstr.datai+k-1=t.datak;for(k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datat.length+k-j=s.datak;str.length=s.length-j+t.length;return str;int index(sqstring s

37、,sqstring t)/BF模式匹配int i=0,j=0,k;while(i<s.length&&j<t.length)if(s.datai=t.dataj)/继续匹配下一个字符i+; /主串和子串依次匹配下一个字符j+;else /主串和子串指针回溯重新开始下一次匹配i=i-j+1; /主串从下一个位置开始匹配j=0; /子串从头开始匹配if(j>=t.length) k=i-t.length; /返回匹配的第一个字符的下标elsek=-1;return k; /模式匹配不成功int index1(sqstring s,sqstring t)/非模式匹配

38、int i,j,k;for(i=0;i<s.length;i+)for(j=i,k=0;s.dataj=t.datak;j+,k+);if(k=t.length)return i;/返回匹配的第一个字符的下标return -1;/模式匹配不成功void getnext(sqstring t,int next)/由模式串t求出next的值int j,k;j=0;k=-1;next0=-1;while(j<t.length-1)if(k=-1|t.dataj=t.datak)/k为-1或比较的字符相等j+;k+;nextj=k;elsek=nextk;int kmpindex(sqst

39、ring s,sqstring t)/KMP模式匹配int nextmax,i=0,j=0;getnext(t,next);while(i<s.length&&j<t.length)if(j=-1|s.datai=t.dataj)i+; /i,j各增j+;elsej=nextj; /i不变，j后退if(j>=t.length)return(i-t.length); /返回匹配模式串的首字符下标elsereturn(-1); /返回不匹配标志void pipei(sqstring s,sqstring t)int n;doprintf(" * n&qu

40、ot;);printf(" 1 非模式匹配 2 BF模式匹配 3 KMP模式匹配 n");printf(" * n");scanf("%d",&n);switch(n)case 1:if(index1(s,t)=-1) printf("该顺序串不匹配！n"); else printf("该顺序串匹配，第一匹配位置是：%dn",index1(s,t);break;case 2:if(index(s,t)=-1) printf("该顺序串不匹配！n"); else pri

41、ntf("该顺序串匹配，第一匹配位置是：%dn",index(s,t);break;case 3:if(kmpindex(s,t)=-1) printf("该顺序串不匹配！n"); else printf("该顺序串匹配，第一匹配位置是：%dn",kmpindex(s,t);break;default:break;while(n!=0);void ReverseSq(sqstring s)int c,i,j;char T;i=0;j=s.length-1;while(i<j) T=s.datai;s.datai=s.dataj;

42、s.dataj=T;i+;j-;for(c=0;c<s.length;c+)printf("%c",s.datac);printf("n");void chaz(sqstring s,char m)int i,c=0,flag=0;for(i=s.length-1;i>=0;i-)if(s.datai=m)c+;printf("character出现在串s中对应的最大下标：%dn",i);flag=1;break;if(flag=0)printf("串s中无这个字符！n");printf("该

43、字符在串中出现的次数：%dn",c);void zhuanh(sqstring s)int i;for(i=0;i<s.length;i+)if(s.datai<='z'&&s.datai>='a')printf("%c ",s.datai-32);if(s.datai<='Z'&&s.datai>='A')printf("%c ",s.datai+32);void change(sqstring &s,sqst

44、ring &t)char cstrmax,Strmax;int i;printf("输入串cstr:");i=0;getchar();while(cstri=getchar()!='n')i+;cstri='0'printf("输入串Str:");i=0;while(Stri=getchar()!='n')i+;Stri='0'printf("把串cstr赋值给串s:");stra(s,cstr);dis(s); printf("把串Str赋值给串t:&

45、quot;);stra(t,Str);dis(t);int main()system("color b0");sqstring s,t,s0,s1,s2,s3,s4,s5;int i,j,n,l,k;char m,cstrmax,Strmax;printf("ttt请稍后，正在检测运行环境.n");for(l=0;l<80;l+)for(k=0;k<10000000;k+)if(k<10000000)printf(">");printf ("ttt检测完成按回车键进入系统");getchar

46、();system("cls");printf("输入串cstr:");i=0;while(cstri=getchar()!='n')i+;cstri='0'printf("输入串Str:");i=0;while(Stri=getchar()!='n')i+;Stri='0'printf("把串cstr赋值给串s:");stra(s,cstr);dis(s); printf("把串Str赋值给串t:");stra(t,Str);di

47、s(t);doprintf("*n");printf(" 1:串t复制给串s 2:判断串大小 3:求串长 4:串连接 5:求子串 6:插入n" );printf(" 7:删除 8:替换 9:匹配 10:输出串 11:逆序 12:查找 13:转换 14:修改n" );printf("*n");scanf("%d",&n);switch(n)case 1:printf("将串t复制给串s得到新串s0:n");s0=strcopy(s,t);printf("输出新串s0:");dis(s0);break;case 2:if(strcmp(s,t)=0) printf("两串相等！n");else if(strcmp(s,t)=-1)printf("