数据结构课程设计串基本操作演示系统

1、附件1：学 号： 2010131328课 程 设 计课程名数据结构题 目串基本操作演示系统学 院计信学院专 业计算机班 级10级计算机三班学生姓名指导教师2011 年12月21日课程设计任务书学生姓名： 专业班级： 2010级计算机三班 指导教师： 工作单位： 重庆工商大学 题 目: 串基本操作演示系统已知技术参数和设计要求：基本功能要求：实现若干串的基本操作，如串赋值、求串长、串的比较、串的替换、求子串、串的模式匹配等。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）设计的题目要求达到一定工作量，并具有一定的深度和难度，程序代码不得少于300行。（2）

2、对设计问题进行分析研究，运用所学知识，确定设计思路及方案，并有相应文档产生。（3）要求设计的软件能够正确运行，达到题目要求。（4）编写出课程设计说明书（并附程序源代码），以电子文档方式上交教师批阅。时间安排： 理解所设计的题目，确定初步设计方案 编代码调试和测试 编写设计说明书 指导教师签名： 年 月 日串基本操作演示系统-课程设计说明书重庆工商大学计算机科学与信息工程学院摘要：实现若干串的基本操作，如串赋值、求串长、串的比较、串的替换、求子串、串的模式匹配等。关键字：串，函数调用一.基本任务设计串基本操作演示系统，系统需要实现如下基本功能：（1）给串赋值；（2）判断两个串是否相等；（3）串的

3、复制；（4）求串的长度；（5）求一个串的子串；（6）将两个串连接起来形成一个串；（7）串的插入；（8）串的删除；（9）串的替换；（10）串的比较；（11）串的模式匹配；（12）串的逆序输出；二.设计概要为了完成需求分析的基本任务，主要从以下3个方面进行设计：2.1主界面设计为了实现串基本操作演示系统的各个功能，定义了一个非紧缩式的顺序串，来实现串的基本操作。2.2数据结构设计系统采用顺序表的顺序存储结构表示和存储串的内容。其中顺序表的结构体有2个数据项组成：存放串字符的数组，串长。2.3系统功能设计系统设计了12个子功能模块，12个子功能模块的描述如下：（1）串赋值子模块:可以给串赋予一个字符

4、串常量，该功能由StrAssign()函数实现。 （2）判断两个串是否相等子模块：判断两个串是否相等，相等则返回1，否则返回0，该功能由StrEqual()函数实现。（3）串长度子模块：返回串中的字符个数，该功能由StrLength()函数实现。（4）串的子串子模块：求一个串的子串，该功能由SubStr()函数实现。（5）串的匹配子模块：判断两个串是否模式匹配，该功能由StrIndex（）函数实现。（6）串连接子模块：将两个串连接起来形成一个新的串，该功能由Concat（）函数实现。（7）串替换子模块：将一个串的某一子串用另一个串代替形成新串，该功能由RepStr（）函数实现。（8）串插入子模

5、块：在一个串中插入另一个串形成新串，该功能由InsStr（）函数实现。（9）串删除子模块：将一个串的某一子串删除形成新串，该功能由DelStr（）函数实现。（10）串比较子模块：比较两个串的大小，该功能由Strcmp（）函数实现。（11）串复制子模块：将一个串复制给另一个串，该功能由StrCopy（）函数实现。（12）串逆序子模块：将串逆序输出，该功能由ReverseSq（）函数实现。三.模块设计3.1模块设计系统主要包含主函数模块和其他子函数模块，其调用关系如图所示：子函数模块主函数模块模块函数调用示意图3.2系统子模块及其功能设计本系统包含了12个功能子函数，各程序的函数名及功能如下：（1

6、）StrAssign()函数：给串赋予一个字符串常量。（2）StrEqual()函数：判断两个串是否相等，相等则返回1，否则返0。（3）StrLength()函数：返回串中的字符个数。（4）SubStr()函数：求一个串的子串。（5）StrIndex（）函数：判断两个串是否模式匹配。（6）Concat（）函数：将两个串连接起来形成一个新的串。（7）RepStr（）函数：将一个串的某一子串用另一个串代替形成新串。（8）InsStr（）函数：在一个串中插入另一个串形成新串。（9）DelStr（）函数：将一个串的某一子串删除形成新串。（10）Strcmp（）函数：比较两个串的大小。（11）StrCo

7、py（）函数：将一个串复制给另一个串。（12）ReverseSq（）函数：将串逆序输出。四.详细设计4.1数据结构设计系统采用顺序表的顺序存储结构存储串的信息，其结构体类型定义如下：#define MaxSize 100typedef structchar dataMaxSize;/存放串字符int len; /串长SqString;4.2系统主要模块设计（1）主函数：main（）函数，在其里面调用各个功能函数，以实现他们的功能，算法如下：int main()int i,j,m,n;SqString str1,str2,s1,s2,s3,s4,s5; char cstr180,cstr280;

8、printf("Enter a string1:");/提示用户输入字符串i=0; while(cstr1i=getchar()!='n')i+;cstr1i='0' printf("Enter a string2:");j=0; while(cstr2j=getchar()!='n')j+;cstr2j='0'/1 串的赋值printf("（）串的赋值n");StrAssign(str1,cstr1);StrAssign(str2,cstr2);printf("

9、;str1=");DispStr(str1);printf("str2=");DispStr(str2);/2 判断两个串是否相等printf("(2)判断串str1和str2是否相等：n");m=StrEqual(str1,str2);if(m=0)printf("str1与str2不相等！n");elseprintf("str1与str2相等！n");/3 串的长度printf("（）串的长度n");printf("str1的长度为：%dn",StrLength

10、(str1); printf("str2的长度为：%dn",StrLength(str2);/4 求串的子串printf("（）串的子串：n"); printf("提取串str1的第个字符开始的个字符而产生串s1n");s1=SubStr(str1,2,3);DispStr(s1);/5 串的匹配printf("（）串的匹配n");if(StrIndex(str1,str2)!=-1)printf("匹配成功!n");elseprintf("匹配失败!n"); printf(

11、"n"); /6 串的连接printf("（）串的连接n");printf("将串str1和串str2连接起来形成串s2：n");s2=Concat(str1,str2);DispStr(s2); /7 串的替换printf("（）串的替换n");printf("在串str1中，将第个字符开始的个字符构成的子串用str2替换,形成s3：n");s3=RepStr(str1,3,4,str2);DispStr(s3);/8 串的插入 printf("（）将串str2插入到串str1的第个

12、字符中,形成串s4：n");s4=InsStr(str1,2,str2); DispStr(s4);/9 串的删除printf("(9)从串str1中删去第个字符开始的长度为的子串，形成串s5：n");s5=DelStr(str1,2,3); DispStr(s5);/10 串的比较printf("(10)串的比较:n");n=Strcmp(str1,str2);if(n=0)printf("str1=str2n");else if(n=1)printf("str1>str2n");elseprin

13、tf("str1<str2n"); /11 串的复制printf("(11)串的复制n");StrCopy(str1,str2);printf("复制后的str1为：");DispStr(str1); /12 串逆序printf("(12)将串str1逆序输出：n"); ReverseSq(str1);DispStr(str1); return 0;（2）各个功能函数及其算法实现：实现串赋值的函数：void StrAssign(SqString &s,char cstr) int i; for(i=0

14、;cstri!='0'i+) s.datai=cstri; s.len=i;判断串是否相等的函数：int StrEqual(SqString s,SqString t) int same=1,i; if (s.len!=t.len) /长度不相等时返回 same=0;else for (i=0;i<s.len;i+) if (s.datai!=t.datai)/有一个对应字符不相同时返回 same=0; return same;实现串复制的函数：void StrCopy(SqString &s,SqString t) int i; for(i=0;i<t.l

15、en;i+) s.datai=t.datai; s.len=t.len;求串长的函数：int StrLength(SqString s)return s.len;求子串的函数：SqString SubStr(SqString s,int i,int j) SqString str;int k;str.len=0;if(i<=0|i>s.len|j<0|i+j-1>s.len)return str; /参数不正确时返回空串for(k=i-1;k<i+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.len=j;

16、return str;串的匹配查询的函数：int StrIndex(SqString s,SqString t)/s为主串,t为模式串int i=0,j=0;while(i<s.len&&j<t.len)/是否到末尾if(s.datai=t.dataj)/主串与模式串逐一匹配i+;j+;else/否则，回溯重新开始下一次匹配i=i-j+1;/主串从下一个位置开始j=0;/模式串从头开始 if(j>=t.len) /如果匹配成功return (i-t.len);/返回主串第一个下标elsereturn -1;/匹配失败,返回-1实现串连接的函数SqString

17、Concat(SqString s,SqString t) SqString str;int i;str.len=s.len+t.len;for(i=0;i<s.len;i+) /将s复制到strstr.datai=s.datai;for(i=0;i<t.len;i+) /将t复制到strstr.datas.len+i=t.datai;return str;实现串替换的函数：SqString RepStr(SqString s,int i,int j,SqString t) int k;SqString str;str.len=0;if(i<=0|i>s.len|i+j

18、-1>s.len) /参数不正确时返回空串return str;for(k=0;k<i-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;k<t.len;k+) /将t复制到strstr.datai+k-1=t.datak;for(k=i+j-1;k<s.len;k+) /将s.datai+j-1.s.len-1复制到strstr.datat.len+k-j=s.datak;str.len=s.len-j+t.len;return str;实现串的插入的函数：SqString InsStr(SqString s1,in

19、t i,SqString s2) int j;SqString str;str.len=0;if(i<=0|i>s1.len+1) /参数不正确时返回空串return str; for(j=0;j<i-1;j+) /将s1.data0.i-2复制到strstr.dataj=s1.dataj;for(j=0;j<s2.len;j+) /将s2复制到strstr.datai+j-1=s2.dataj;for(j=i-1;j<s1.len;j+) /将s1.datai-1.s1.len-1复制到strstr.datas2.len+j=s1.dataj;str.len=s

20、1.len+s2.len;return str;实现串的删除的函数：SqString DelStr(SqString s,int i,int j) int k; SqString str; str.len=0; if (i<=0 | i>s.len| i+j>s.len+1) /参数不正确时返回空串printf("参数不正确n"); return str; for (k=0;k<i-1;k+)/将s.data0s.datai-2复制到str str.datak=s.datak; for (k=i+j-1;k<s.len;k+)/将s.datai

21、+j-1datas.length-1复制到str str.datak-j=s.datak; str.len=s.len-j; return str;实现串的比较的函数：int Strcmp(SqString s,SqString t) int i,comlen;if(s.len<t.len)comlen=s.len; /求s和t的共同长度elsecomlen=t.len;for(i=0;i<comlen;i+) /在共同长度内逐个字符比较if(s.datai<t.datai)return -1;else if(s.datai>t.datai)return 1;if(s.

22、len=t.len) return 0; /s=telse if(s.len<t.len) return -1; /s<telse return 1; /s>t实现串逆序输出的函数：void ReverseSq(SqString &str)int i,j;char t;i=0;j=str.len-1;/首尾调换while(i<j) t=str.datai;str.datai=str.dataj;str.dataj=t;i+;j-;五.调试分析系统运行结果如下：六.用户使用说明用户可任意输入两个串，系统将会自动对这两个串进行比较，复制，判断是否相等，删除，插入，替

23、换等一系列串的基本操作。七.参考文献(1)数据结构教程 清华大学出版社 2009年3月第3版(2)C语言程序设计 高等教育出版社 2008年1月第1版(3)数据结构教程上机实验指导 清华大学出版社 (4)数据结构（C语言）实践教程 西安电子科技大学出版社八. 对所设计的软件进行自我评价这个软件所运用了这学期所学的数据结构编写，在要求实现的功能上另外加了功能，如串的插入，删除，连接，逆序输出等。让这个软件的编写方式不仅仅局限于常规的编程思想上。没有未解决的问题。此软件能够正确运行并得到正确结果。创新点应该在于扩大了软件的功能。九.程序源代码#include <stdio.h>#inc

24、lude <stdlib.h>#include <string.h>/定义顺序串#define MaxSize 100typedef structchar dataMaxSize;/存放串字符int len; /串长SqString;/串赋值void StrAssign(SqString &s,char cstr) int i; for(i=0;cstri!='0'i+) s.datai=cstri; s.len=i;/判断串是否相等int StrEqual(SqString s,SqString t) int same=1,i; if (s.l

25、en!=t.len) /长度不相等时返回 same=0; else for (i=0;i<s.len;i+) if (s.datai!=t.datai)/有一个对应字符不相同时返回 same=0; return same;/将串t复制给串svoid StrCopy(SqString &s,SqString t) int i; for(i=0;i<t.len;i+) s.datai=t.datai; s.len=t.len;/求串长int StrLength(SqString s)return s.len;/求子串SqString SubStr(SqString s,int

26、i,int j) SqString str;int k;str.len=0;if(i<=0|i>s.len|j<0|i+j-1>s.len)return str; /参数不正确时返回空串for(k=i-1;k<i+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.len=j;return str;/串的匹配查询(顺序串)int StrIndex(SqString s,SqString t)/s为主串,t为模式串int i=0,j=0;while(i<s.len&&j<t.len)/

27、是否到末尾if(s.datai=t.dataj)/主串与模式串逐一匹配i+;j+;else/否则，回溯重新开始下一次匹配i=i-j+1;/主串从下一个位置开始j=0;/模式串从头开始 if(j>=t.len) /如果匹配成功return (i-t.len);/返回主串第一个下标elsereturn -1;/匹配失败,返回-1/串的连接:返回由两个串连接在一起的新串SqString Concat(SqString s,SqString t) SqString str;int i;str.len=s.len+t.len;for(i=0;i<s.len;i+) /将s复制到strstr.

28、datai=s.datai;for(i=0;i<t.len;i+) /将t复制到strstr.datas.len+i=t.datai;return str;/串的替换SqString RepStr(SqString s,int i,int j,SqString t) int k;SqString str;str.len=0;if(i<=0|i>s.len|i+j-1>s.len) /参数不正确时返回空串return str;for(k=0;k<i-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;k<t.l

29、en;k+) /将t复制到strstr.datai+k-1=t.datak;for(k=i+j-1;k<s.len;k+) /将s.datai+j-1.s.len-1复制到strstr.datat.len+k-j=s.datak;str.len=s.len-j+t.len;return str;/插入串：将串s2插入到串s1的第i个字符中SqString InsStr(SqString s1,int i,SqString s2) int j;SqString str;str.len=0;if(i<=0|i>s1.len+1) /参数不正确时返回空串return str; fo

30、r(j=0;j<i-1;j+) /将s1.data0.i-2复制到strstr.dataj=s1.dataj;for(j=0;j<s2.len;j+) /将s2复制到strstr.datai+j-1=s2.dataj;for(j=i-1;j<s1.len;j+) /将s1.datai-1.s1.len-1复制到strstr.datas2.len+j=s1.dataj;str.len=s1.len+s2.len;return str;/串的删除SqString DelStr(SqString s,int i,int j) int k; SqString str; str.len

31、=0; if (i<=0 | i>s.len| i+j>s.len+1) /参数不正确时返回空串printf("参数不正确n"); return str; for (k=0;k<i-1;k+)/将s.data0s.datai-2复制到str str.datak=s.datak; for (k=i+j-1;k<s.len;k+)/将s.datai+j-1datas.length-1复制到str str.datak-j=s.datak; str.len=s.len-j; return str;/串比较int Strcmp(SqString s,Sq

32、String t) int i,comlen;if(s.len<t.len)comlen=s.len; /求s和t的共同长度elsecomlen=t.len;for(i=0;i<comlen;i+) /在共同长度内逐个字符比较if(s.datai<t.datai)return -1;else if(s.datai>t.datai)return 1;if(s.len=t.len) return 0; /s=telse if(s.len<t.len) return -1; /s<telse return 1; /s>t/串逆序void ReverseSq(

33、SqString &str)int i,j;char t;i=0;j=str.len-1;/首尾调换while(i<j) t=str.datai;str.datai=str.dataj;str.dataj=t;i+;j-;/输出串void DispStr(SqString str) int i; if (str.len>0) for (i=0;i<str.len;i+) printf("%c",str.datai);printf("n"); int main()int i,j,m,n;SqString str1,str2,s1,

34、s2,s3,s4,s5; char cstr180,cstr280;printf("Enter a string1:");/提示用户输入字符串i=0; while(cstr1i=getchar()!='n')i+;cstr1i='0' printf("Enter a string2:");j=0; while(cstr2j=getchar()!='n')j+;cstr2j='0'/1 串的赋值printf("（）串的赋值n");StrAssign(str1,cstr1);StrAssign(str2,cstr2);printf("str1=");DispStr(str1);printf("str2=");DispStr(str2);/2 判断两个串是否相等printf("(2)判断串str1和str2是否相等：n");m=StrEqual(str1,str2);if(m=0)printf("str1与str2不相等！n");elseprintf("str1与str2相等！n");/3 串的长度printf("（）串的长度n