数据结构课程设计-串基本操作的演示.doc

序号：11 数据结构课程设计 题 目 串基本操作的演示 学 院 计算机学院 专 业 网络工程 年级班别 学 号 学生姓名 指导教师 XX 年 XXX 月 XX 日一.、课程设计任务要求 在教科书4.2.2节用堆分配存储表示实现HString串的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。参数合法性检查必须严格。 说明：（在格式中，表示0个、1个或多个空格所组成的串。串标识表示一个内部名或一个串文字。前者是一个串的唯一标识，是一种内部形式的（而不是字符形式的）标识符。后者是两端由单引号括起来的仅可打印字符组成的序列。串内每两个连续的单引号表示一个单引号符。） 利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直至终止程序的命令为止。命令定义如下： （1）赋值。格式：A串标识回车 用串标识所表示的值建立新 串，并显示新串的内部名和串值。如：AHi！ （2） 判相等。 格式：E串标识1串标识2回车 若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。 （3） 联接。 格式：C串标识1串标识2回车 将两串联接产生结果串，它的内部名和串值都显示出来。 （4） 求长度 格式：L串标识回车 显示串的长度。 （5） 求子串 格式：S串标识+数1+数2回车 如果参数合法，则显示子串的内部名和串值。数不带正负号。 （6）子串定位。 格式：I串标识1串标识2回车 显示第二个串在第一个串中首次出现时的位置。 （7）串替换 格式：R串标识1串标识2串标识2回车 将第一个串中出现所有出现的第二个串用第三个串替换，显示结果串的内部名和 串值，原串不变。 （8）显示。格式P回车显示所有在系统中被保持的串的内部名和串值的对照表（9）删除。格式D内部名回车删除该内部名对应的串，即赋值的逆操作。（0）退出 格式：Q回车 结束程序的运行。二、已完成的项目及完成程度 （1） 赋值。 StrAssign（SqString &s,char cstr）（2） 判相等。 StrEqual(SqString s,SqString t)（3） 联接。 Concat(SqString s,SqString t) （4） 求长度 。StrLength(SqString s)（5） 求子串 。SubStr(SqString s,int i,int j)（6）子串定位。 Index(linkstring *s,linkstring *t)（7）串替换 。Replace(linkstring *&s,linkstring *t,linkstring *r) （8）显示。 Dispstr(linkstring *s)（9）删除。 DelStr(SqString s,int i,int j)（0）退出 。Quit()完成了项目要求的大部分所有操作。三、理论依据、用到的数据结构，及举例定义串的基本主结构ADT String 数据对象：D=ai| aicharcaterset,i=1,2,n,n=0 数据关系：R1=|ai-1,aiD, i=1,2,n 基本操作： StrCompare(HString S,HString T) 初始条件：S和T是已存在的Hstring类型。 操作结果：比较其值，显示结果“UNEQUAL”或“EQUAL”。 StrLength(HString S) 初始条件：S是已存在的Hstring类型。 操作结果：返回该串的长度。 Concat(HString S1,HString S2) 初始条件：S1和S2是已存在的Hstring类型。 操作结果：由S1和S2联接成新串。 Index(HString S,HString t) 初始条件：S和T是已存在的Hstring类型。 操作结果：显示第二个串在第一个串中首次出现的起始位置。 Replace(HString M, HString t, HString v) 初始条件：M、t和v是已存在的Hstring类型。 操作结果：将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。 SubString(HString S,int pos,int len) 初始条件：S是已存在的Hstring类型。 操作结果：如果参数合法，则显示子串的内部名和串值 。 Strprint(HString S) 初始条件：S是已存在的Hstring类型。 操作结果：显示串S的内部名和串值 。 getin(int n) 初始条件：处理命令串S1, 操作结果：把串值存入串头表中 Insert(int n) 初始条件：要给指定的串赋值,n为指定的串的内部名 操作结果：为指定内部名的串赋值 show() 初始条件：要求查看输入格式 操作结果：输出各种命令的输入格式ADT Stringtypedef structchar *ch; /若是非空串，则按串长分配存储区，否则ch为NULLint length; /串长度HString;4、 主要算法流程图主函数菜单函数的选择 A Concatenate（）串的连接函数Quit（）退出DelStr（）串的删除函数StrLength（）串的长度函数SubSrt（）提取子串函数RepStr（）串的替代函数StrEqual（）判断相等函数SrtAssign（）赋值函数 E C L S R D Q 5、 主要代码引用的头文件： #include #include #include 使用的结构体： typedef struct char dataMaxSize;/存放串字符 int len; /串长 SqString;关键函数功能实现： void Scanf(char cstrr) / 输入字符串 cstrr100; printf(Enter a string:n);/提示用户输入字符串 int j=0; while(cstrrj=getchar()!=n)j+;cstrrj=0; /串赋值void StrAssign(SqString &s,char cstr) Scanf(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.len!=t.len) /长度不相等时返回 same=0; else for (i=0;is.len;i+) if (s.datai!=t.datai)/有一个对应字符不相同时返回 same=0; return same;/将串t复制给串svoid StrCopy(SqString &s,SqString t) int i; for(i=0;it.len;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(is.len|js.len)return str; /参数不正确时返回空串for(k=i-1;ki+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.len=j;return str;/串的连接:返回由两个串连接在一起的新串SqString Concat(SqString s,SqString t) SqString str;int i;str.len=s.len+t.len;for(i=0;is.len;i+) /将s复制到strstr.datai=s.datai;for(i=0;it.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(is.len|i+j-1s.len) /参数不正确时返回空串return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;kt.len;k+) /将t复制到strstr.datai+k-1=t.datak;for(k=i+j-1;ks.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 DelStr(SqString s,int i,int j) int k; SqString str; str.len=0; if (is.len| i+js.len+1) /参数不正确时返回空串printf(参数不正确n); return str; for (k=0;ki-1;k+)/将s.data0s.datai-2复制到str str.datak=s.datak; for (k=i+j-1;ks.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,SqString t) int i,comlen;if(s.lent.len)comlen=s.len; /求s和t的共同长度elsecomlen=t.len;for(i=0;icomlen;i+) /在共同长度内逐个字符比较if(s.datait.datai)return 1;if(s.len=t.len) return 0; /s=telse if(s.lent.len) return -1; /st/输出串void DispStr(SqString str) int i; if (str.len0) for (i=0;istr.len;i+) printf(%c,str.datai);printf(n); / 菜单函数 void menus() int i,j,m,x,y;char n; printf(*n);printf(* A 赋值 E 判断相等 C 联接*n);printf(* L 求长度 S 求子串 I 子串定位*n);printf(* R 串替换 P 显示 D 删除 *n);printf(* Q 退出 *n);scanf(%c,&n);getchar();switch(n)case A:case a: printf(A 请输入需要赋值的串 n);StrAssign(str1,cstr1); printf(输出str1=); DispStr(str1);menus();break;case E:case e:printf(E 判断串str1和str2是否相等：n);StrAssign(str1,cstr1); StrAssign(str2,cstr2); m=StrEqual(str1,str2); if(m=1) printf(EQUALn); else printf(NUEQUALn);menus(); break;case C:case c:printf(输入要连接的两个串：n); printf(将串str1和串str2连接起来形成串s1：n);StrAssign(str1,cstr1); StrAssign(str2,cstr2); s1=Concat(str1,str2); DispStr(s1);menus();break;case L:case l:printf(输入要求长度的串：n);StrAssign(str1,cstr1); printf(str1的长度为：%dn,StrLength(str1);menus();break;case S:case s: printf(提取串str1的第a个字符开始的b个字符而产生串s2n);StrAssign(str1,cstr1);int a,b;scanf(%d %d,&a,&b); s2=SubStr(str1,a,b); DispStr(s2);menus();break;case R:case r: printf(在串str1中，将第p个字符开始的q个字符构成的子串用str2替换,形成s3：n);StrAssign(str1,cstr1);int p,q;scanf(%d %d,&p,&q);StrAssign(str2,cstr2); s3=RepStr(str1,p,q,str2); DispStr(s3);menus();break; case D:case d: printf(从串str1中删去第i个字符开始的长度为j的子串，形成串s3:n); StrAssign(str1,cstr1);int x,y;scanf(%d %d,&x,&y); s3=DelStr(str1,x,y); DispStr(s3);menus();break; case Q:case q: break; void main() /主函数menus();六、实验截图1. 测试用例 (1) A s = deng ，应显示s = deng ； (2) E “ “ ,应显示 “EQUAL”； (3) E abc abcd ，应显示“UNEQUAL”； (4) I a “ ，应报告：参数非法； (5)R dengbolun 2 4 huizhi，应显示 ba; (6) D dengbolun 2 4，应显示：dolun； （7）D fdhagkjh 3 6 ，应显示：fdjh； （8）C deng bolun ，应显示：dengbolun； （9）L abcdefg，应显示：7；2. 程序截图 3. 实验结果分析 经检验，测试数据预期结果和测试得出结果一致。7、 小结本实验是在Microsoft Visual C+上实现的本次实验学到了很多知识：1）熟悉串的定义和串的基本操作。2）掌握顺序串的基本运算。3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。4）运用到了串的链式存储结构，对链表也有了进一步提高。 附录：源代码 #include #include #include /定义顺序串#define MaxSize 100typedef structchar dataMaxSize;/存放串字符int len; /串长SqString;void menus();void Scanf(char cstrr) cstrr100; printf(Enter a string:n);/提示用户输入字符串 int j=0; while(cstrrj=getchar()!=n)j+;cstrrj=0;/串赋值void StrAssign(SqString &s,char cstr) Scanf(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.len!=t.len) /长度不相等时返回 same=0; else for (i=0;is.len;i+) if (s.datai!=t.datai)/有一个对应字符不相同时返回 same=0; return same;/将串t复制给串svoid StrCopy(SqString &s,SqString t) int i; for(i=0;it.len;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(is.len|js.len)return str; /参数不正确时返回空串for(k=i-1;ki+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.len=j;return str;/串的连接:返回由两个串连接在一起的新串SqString Concat(SqString s,SqString t) SqString str;int i;str.len=s.len+t.len;for(i=0;is.len;i+) /将s复制到strstr.datai=s.datai;for(i=0;it.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(is.len|i+j-1s.len) /参数不正确时返回空串return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;kt.len;k+) /将t复制到strstr.datai+k-1=t.datak;for(k=i+j-1;ks.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 DelStr(SqString s,int i,int j) int k; SqString str; str.len=0; if (is.len| i+js.len+1) /参数不正确时返回空串printf(参数不正确n); return str; for (k=0;ki-1;k+)/将s.data0s.datai-2复制到str str.datak=s.datak; for (k=i+j-1;ks.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,SqString t) int i,comlen;if(s.lent.len)comlen=s.len; /求s和t的共同长度elsecomlen=t.len;for(i=0;icomlen;i+) /在共同长度内逐个字符比较if(s.datait.datai)return 1;if(s.len=t.len) return 0; /s=telse if(s.lent.len) return -1; /st/输出串void DispStr(SqString str) int i; if (str.len0) for (i=0;istr.len;i+) printf(%c,str.datai);printf(n); void main()menus();char cstr180,cstr280;SqString str1,str2,s1,s2,s3;void menus() int i,j,m,x,y;char n; printf(*n);printf(* A 赋值 E 判断相等 C 联接*n);printf(* L 求长度 S 求子串 I 子串定位*n);printf(* R 串替换 P 显示 D 删除 *n);printf(* Q 退出 *n);scanf(%c,&n);getchar();switch(n)case A:case a: printf(A 请输入需要赋值的串 n);StrAssign(str1,cstr1); printf(输出str1=); DispStr(str1);menus();break;case E:case e:p