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

课程设计说明书

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

为了实现串的各项基本操作，设计了一个含有多个菜单项的主控菜单模式以连接各种基本操作，以方便使用系统。如图：

在选项9中我又设计了一个含三个菜单项的小主菜单以连接三个不同的匹配算法。如图：

2.2 数据结构设计
系统采用线性表的顺序存储结构表示，其中存放串字符和串长。此外定义了一个常量max，表示字符串的最大长度。
2.3 系统功能设计
此系统中设置了14个子功能模块，并在第9个功能中又设置了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()函数实现。
（11）在s串中将第i个字符开始的j个字符构成的子串用串t替换模块。由repstr()函数实现。
（12）串的逆序模块。由ReverseSq()函数实现。
（13）串的转换模块。由zhuanh()函数实现。
（14）串的修改模块。由change()函数实现。

3.模块设计
整个程序的流程图。如图：
开始
输入串cstr,Str并赋值给串s,t
1串t复制给s
2判断串的大小
3求串长
4串的连接
5求子串
6插入
7删除
8替换
9匹配
10输出串
11串的逆序
12串的查找
13串的转换
14串的修改
根据选择输出相应的运行结果
结束
stra()函数
strcmp()函数
strlegth()函数
Concat()函数
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 data[max];
int length;
}sqstring;
4.2系统主要模块设计
（1）将字符常量cstr,Str赋值给串s,t模块，由stra()函数实现。该模块的算法思想是：用for循环将cstr[i]赋值给s[i]；并s.length=i。
该模块的算法描述如下：
void stra(sqstring &s,char cstr[])//将字符串常量赋给串s,s为引用型参数
{
int i;
for(i=0;cstr[i]!='\0';i++)
s.data[i]=cstr[i];
s.length=i;
}
（2）将串t复制给串s模块，由strcopy()函数实现。该模块的算法思想是：用for循环将顺序串t的内容复制给顺序串s，并顺序串s的长度为顺序串t的长度。
该模块的算法描述如下：
sqstring strcopy(sqstring s,sqstring t)//将串t复制给串s
{
int i;
for(i=0;i<t.length;i++)
s.data[i]=t.data[i];
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。
该模块的算法描述如下：
int strcmp(sqstring s,sqstring t)//比较两串的大小
{
int i,com;
if(s.length<t.length)
com=s.length;//求串s、t的共同长度
else
com=t.length;
for(i=0;i<com;i++)//在共同长度内逐个字符比较
if(s.data[i]<t.data[i])
return -1;
else if(s.data[i]>t.data[i])
return 1;
if(s.length==t.length)//s==t
return 0;
else if(s.data[i]<t.data[i])//s<t
return -1;
else
return 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 str;
int i;
str.length=s.length+t.length;
for(i=0;i<s.length;i++)//将s.data[0...s.length-1]复制到str
str.data[i]=s.data[i];
for(i=0;i<t.length;i++)//将t.data[0...t.length-1]复制到str
str.data[s.length+i]=t.data[i];
return str;
}
（6）求子串模块。由substr()函数实现。该模块的算法思想是：先定义一空串str存储求的子串，找到所求子串的位置，利用for循环将长度为子串长度的串赋值给串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.data[i...i+j]复制到str
str.data[k-i+1]=s.data[k];
str.length=j;
return str;
}
（7）将串s2插入到s1的第i个字符中模块。该模块的算法思想是：先定义一个空串str，用for循环将s1的前i-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.data[0...i-2]复制到str
str.data[j]=s1.data[j];
for(j=0;j<s2.length;j++)//将s2.data[0...s2.length-1]复制到str
str.data[i+j-1]=s2.data[j];
for(j=i-1;j<s1.length;j++)//将s1.data[i-1...s1.length-1]复制到str
str.data[s2.length+j]=s1.data[j];
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。
该模块的算法描述如下：
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.data[0...i-2]复制到str
str.data[k]=s.data[k];
for(k=i+j-1;k<s.length;k++)//将s.data[i+j-1...s.length-1]复制到str
str.data[k-j]=s.data[k];
str.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.length||i+j>s.length+1)
return str;//参数不正确时返回空串
for(k=0;k<i-1;k++)//将s.data[0...i-2]复制到str
str.data[k]=s.data[k];
for(k=0;k<t.length;k++)//将t.data[0...t.length-1]复制到str
str.data[i+k-1]=t.data[k];
for(k=i+j-1;k<s.length;k++)//将s.data[i+j-1...s.length-1]复制到str
str.data[t.length+k-j]=s.data[k];
str.length=s.length-j+t.length;
return 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分别自增1；否则i不变，j退回到j=next[j]的位置（即模式串右滑），比较si和tj，若相等则指针个自增1，否则j再退回到下一个j=next[j]位置（即模式串继续右滑），再比较si和tj。以此类推，直到出现下列两种情况之一：1、j退回到某个j=next[j]位置时有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(s.data[i]==t.data[j])//继续匹配下一个字符
{
i++; //主串和子串依次匹配下一个字符
j++;
}
else{ //主串和子串指针回溯重新开始下一次匹配
i=i-j+1; //主串从下一个位置开始匹配
j=0; //子串从头开始匹配
}
}
if(j>=t.length)
k=i-t.length; //返回匹配的第一个字符的下标
else
k=-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.data[j]==t.data[k];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;next[0]=-1;
while(j<t.length-1)
{
if(k==-1||t.data[j]==t.data[k])//k为-1或比较的字符相等
{
j++;k++;
next[j]=k;
}
else
k=next[k];
}
}
int kmpindex(sqstring s,sqstring t)//KMP模式匹配
{
int next[max],i=0,j=0;
getnext(t,next);
while(i<s.length&&j<t.length)
{
if(j==-1||s.data[i]==t.data[j])
{
i++; //i,j各增
j++;
}
else
j=next[j]; //i不变，j后退
}
if(j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
（11）串的逆序模块。由ReverseSq()函数实现。该模块的算法思想是：定义两自变量i，j，i=0，j=s.length-1，将其前后对调后，i自增1，j自减1。直至i>=j为止。并输出其对调后的字符串。
该模块的算法描述如下：
void ReverseSq(sqstring s)
{
int c,i,j;
char T;
i=0;
j=s.length-1;
while(i<j)
{
T=s.data[i];
s.data[i]=s.data[j];
s.data[j]=T;
i++;
j--;
}
for(c=0;c<s.length;c++)
printf("%c",s.data[c]);
printf("\n");
}
（12）串的查找模块。由chaz()函数实现。该模块的算法思想是：输入一字符与串中字符逐一比较，若相等，则输出其最大下标，并用一个自变量自增1记录其出现的次数。若不等，则输出串中无这个字符！
该模块的算法描述如下：
void chaz(sqstring s,char m)
{
int i,c=0,flag=0;
for(i=s.length-1;i>=0;i--)
if(s.data[i]==m){
c++;
printf("character出现在串s中对应的最大下标：%d\n",i);
flag=1;
break;
}
if(flag==0)
printf("串s中无这个字符！\n");
printf("该字符在串中出现的次数：%d\n",c);
}
（13）串的转换模块。由zhuanh()函数实现。该模块的算法思想是：若字符在a~z之间，则将字符减去32后输出。若字符在A~Z之间，则将字符加上32后输出。
该模块的算法描述如下：
void zhuanh(sqstring s)
{
int i;
for(i=0;i<s.length;i++){
if(s.data[i]<='z'&&s.data[i]>='a')
printf("%c ",s.data[i]-32);
if(s.data[i]<='Z'&&s.data[i]>='A')
printf("%c ",s.data[i]+32);
}
}
（14）串的修改模块。由change()函数实现。该模块的算法思想是：定义两串cstr，Str，输入其内容，调用函数stra()（将输入串赋值给顺序串）。
该模块的算法描述如下：
void change(sqstring &s,sqstring &t){
char cstr[max],Str[max];
int i;
printf("输入串cstr:");
i=0;
getchar();
while((cstr[i]=getchar())!='\n')
i++;
cstr[i]='\0';
printf("输入串Str:");
i=0;
while((Str[i]=getchar())!='\n')
i++;
Str[i]='\0';
printf("把串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.data[i]);
printf("\n");
}
}
5.调试分析

6.用户使用说明
用户使用时。先输入你所需用的两串。在根据你所需操作的内容选择其选项，注意输入的是数字，不要输入除数字以外的内容。若想结束程序，只需输入0即可。
7.对所设计的软件进行自我评价
我觉得我这次所写的程序很简单，除去模式匹配函数以外其它的所需调用的函数基本可以由大一所学写出来。所以这个程序我用了这学期所学的顺序串来实现这些功能。其中定义了存放串字符和串长度。在顺序串中，串中的字符被依次存放在一组连续的存储单元里。而串的顺序存储有两种方法：非紧缩格式和紧缩格式。非紧缩格式：一个内存单元存储一个字符。紧缩格式：一个内存单元可以存储多个字符。我所写的程序用地是非紧缩格式存储方法。这个软件的功能多，充分应用了do-while语句和switch语句，这样可让使用者随意选择所需操作的功能。其中字符串的匹配更是运用了三个匹配：非模式匹配、BF模式匹配、KMP模式匹配。但是有一个问题尚未得到解决，那就是输入选择时，若不小心输入一个字符，运行时它会无限循环。所以使用时输入数字，输入0时将结束程序。
9.程序源代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 100
typedef struct{
char data[max];
int length;
}sqstring;
void stra(sqstring &s,char cstr[])//将字符串常量赋给串s,s为引用型参数
{
int i;
for(i=0;cstr[i]!='\0';i++)
s.data[i]=cstr[i];
s.length=i;
}
void dis(sqstring s)//显示串s中的所有元素
{
int i;
if(s.length>0){
for(i=0;i<s.length;i++)
printf("%c",s.data[i]);
printf("\n");
}
}
sqstring strcopy(sqstring s,sqstring t)//将串t复制给串s
{
int i;
for(i=0;i<t.length;i++)
s.data[i]=t.data[i];
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的共同长度
else
com=t.length;
for(i=0;i<com;i++)//在共同长度内逐个字符比较
if(s.data[i]<t.data[i])
return -1;
else if(s.data[i]>t.data[i])
return 1;
if(s.length==t.length)//s==t
return 0;
else if(s.data[i]<t.data[i])//s<t
return -1;
else
return 1;//s>t
}
int 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.data[0...s.length-1]复制到str
str.data[i]=s.data[i];
for(i=0;i<t.length;i++)//将t.data[0...t.length-1]复制到str
str.data[s.length+i]=t.data[i];
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.data[i...i+j]复制到str
str.data[k-i+1]=s.data[k];
str.length=j;
return 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.data[0...i-2]复制到str
str.data[j]=s1.data[j];
for(j=0;j<s2.length;j++)//将s2.data[0...s2.length-1]复制到str
str.data[i+j-1]=s2.data[j];
for(j=i-1;j<s1.length;j++)//将s1.data[i-1...s1.length-1]复制到str
str.data[s2.length+j]=s1.data[j];
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.data[0...i-2]复制到str
str.data[k]=s.data[k];
for(k=i+j-1;k<s.length;k++)//将s.data[i+j-1...s.length-1]复制到str
str.data[k-j]=s.data[k];
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)
return str;//参数不正确时返回空串
for(k=0;k<i-1;k++)//将s.data[0...i-2]复制到str
str.data[k]=s.data[k];
for(k=0;k<t.length;k++)//将t.data[0...t.length-1]复制到str
str.data[i+k-1]=t.data[k];
for(k=i+j-1;k<s.length;k++)//将s.data[i+j-1...s.length-1]复制到str
str.data[t.length+k-j]=s.data[k];
str.length=s.length-j+t.length;
return str;
}
int index(sqstring s,sqstring t)//BF模式匹配
{
int i=0,j=0,k;
while(i<s.length&&j<t.length)
{
if(s.data[i]==t.data[j])//继续匹配下一个字符
{
i++; //主串和子串依次匹配下一个字符
j++;
}
else{ //主串和子串指针回溯重新开始下一次匹配
i=i-j+1; //主串从下一个位置开始匹配
j=0; //子串从头开始匹配
}
}
if(j>=t.length)
k=i-t.length; //返回匹配的第一个字符的下标
else
k=-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.data[j]==t.data[k];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;next[0]=-1;
while(j<t.length-1)
{
if(k==-1||t.data[j]==t.data[k])//k为-1或比较的字符相等
{
j++;k++;
next[j]=k;
}
else
k=next[k];
}
}
int kmpindex(sqstring s,sqstring t)//KMP模式匹配
{
int next[max],i=0,j=0;
getnext(t,next);
while(i<s.length&&j<t.length)
{
if(j==-1||s.data[i]==t.data[j])
{
i++; //i,j各增
j++;
}
else
j=next[j]; //i不变，j后退
}
if(j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下标
else
return(-1); //返回不匹配标志
}
void pipei(sqstring s,sqstring t){
int n;
do{
printf(" ***************************************** \n");
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("该顺序串匹配，第一匹配位置是：%d\n",index1(s,t));break;
case 2:if(index(s,t)==-1)
printf("该顺序串不匹配！\n");
else
printf("该顺序串匹配，第一匹配位置是：%d\n",index(s,t));break;
case 3:if(kmpindex(s,t)==-1)
printf("该顺序串不匹配！\n");
else
printf("该顺序串匹配，第一匹配位置是：%d\n",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.data[i];
s.data[i]=s.data[j];
s.data[j]=T;
i++;