串的基本操作及其应用

广西工学院计算机学院数据结构课程实验报告书实验五 串的基本操作及其应用 学生姓名：1 学 号：2 班级：3 指导老师：4 专 业：计算机学院软件学院提交日期：2013年6月21日1 实验目的1）掌握串的定义、存储结构及基本操作。2.实验内容（1）建立一个串，实现串的基本操作。包括：/1.判串长: 返回串s的元素个数。int StrLength(HString S)/2.判空串: 若串s为空串，则返回trueStatus StrEmpty(HString S)/3.串赋值：现有串s，空串 t,实现将s赋值给t的操作Status StrAssign(HString &T,HString S)/4.串连接：现有串s和 t，实现将t链接到串s之后的操作。（流程图）Status StrConcat(HString &S,HString T)/5.串比较: 依次比较2个串s和t,若长度相同且字符相同，则串相同，返回0，若st,则返回值0, 若st,则返回值0. （流程图）Status StrCompare(HString S,HString T)/6.串替换:在主串s中用子串v替换所有的子串tStatus StrReplace(HString &S,HString V,HString T)/7.串插入：在主串s中的给定位置pos插入子串tStatus StrInsert(HString &S,int pos,HString T)/8.取子串: 将串s中从起始位置pos开始长度len的字符串放入另一个串tStatus SubString(HString &S,int pos,int len,HString &T)/9.串删除: 删除串s中的子串t。Status StrDelete(HString &S,HString T)/10.求子串位置：从主串s中取出从第i个位置开始、长度和串t相同的子串，和t进行比较，若相等，则t在s中的位置值为iStatus StrIndex(HString &S,int i,HString T)/（2）串应用：设有串s，求出它的所有子串,并输出。Status SubString_All(HString S)3实验要求（1） 上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。（2） 用一切你能想到的办法解决遇到的问题，培养解决问题的能力。（3） 实验课上进行答辩。（4） 实验报告当场交。报告内容包括 ：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。串的堆分配存储typedef structchar *ch; /若是非空串，则按串长分配储存区，否则ch为NULLint length; /串长度HString;23主要算法3.1 顺序存储结构（1） 结构定义：#include#include#include#define MAX 255typedef char sstringMAX+1;int strlength(sstring s);/判断串长int strempty(sstring s); /判断空串int strassign(sstring &t,char* s);/串赋值int concat(sstring &t,sstring s1,sstring s2); /串连接int strcompare(sstring s,sstring t);/串的比较void strprint(sstring s);/输出int strinsert(sstring s,int pos,sstring t);/串插入int strdelete(sstring s,int pos,int len);/删除字串int replace(sstring s,sstring t,sstring v);/串的替换int substring(sstring &sub,sstring s,int pos,int len);/取子串int index(sstring s,sstring t,int pos);/字串定位 /串赋值int strassign(sstring &t,char* s)/初始条件：字符串chars已经存在/操作结果：生成一个其值等于chars的串tint i,n;n=strlen(s);if(n=MAX)return 0;else t0=n;for(i=1;i=t0;i+)/依次给串赋值ti=si-1;return 1; /求串长度int strlength(sstring s)/操作结果：返回串s的元素return s0;/判断串是否空int strempty(sstring s) return (s0=0);/返回值/串连接int concat(sstring &t,sstring s1,sstring s2)/初始条件：字符串s1和s2已经存在/操作结果：用T返回s1和s2连接成的新串。int i; if(s10+s20=MAX) for(i=1;i=s10;i+)/依次把串s1中的元素赋值给串t ti=s1i; for(i=1;i=s20;i+) ti+s10=s2i; t0=s10+s20;/计算串t的长度 return 1;else for(i=1;i=s10;i+) ti=s1i; for(i=1;it,则返回值0,若是s=t,则返回值=0,若是st,则返回值0int i;for(i=1;i=ti&i=s0;i+)if(si!=ti)return si-ti;/返回大于的值return s0-t0;/返回大于的值/输出void strprint(sstring s)/初始条件：字符串chars已经存在/操作结果：依次输出串中的元素int i;for(i=1;i=s0;i+)printf(%c,si);printf(nn);/串插入int strinsert(sstring s,int pos,sstring t) /初始条件：字符串chars已经存在/操作结果：在串s第pos个字符之前插入串t，完成插入返回，否则返回int i;if(poss0+1)return 0;if(s0+t0=pos;i-) si+t0=si; for(i=pos;i=pos;i-)si+MAX-s0=si;for(i=pos; i=s0 ;i+)si=ti-pos+1;s0=MAX;return 1;/删除字串int strdelete(sstring s,int pos,int len)/初始条件：字符串chars已经存在/操作结果：在串s第pos个字符起删除长度为len的子串，删除成功返回，否则返回int i;if(poss0-len+1|len0)return 0;for(i=pos+len;i=s0;i+)/依次删除串中指定的元素si-len=si;s0-=len;return 1;/串的替换int replace(sstring s,sstring t,sstring v)/初始条件：字符串chars已经存在/操作结果：串t被s替换，成功返回，否则返回int i=1;int k;if(strempty(t)/判断串t为空return 0;do i=index(s,t,i);printf(%d,i);if(i)strdelete(s,i,t0);/调用函数k=strinsert(s,i,v);/调用函数if(!k)return 0;i+=v0; while(i);return 1;/取子串int substring(sstring &sub,sstring s,int pos,int len)/初始条件：字符串chars已经存在/操作结果：用sub返回串s的第pos个字符起长度为len的子串int i;if(poss0|lens0-pos+1)return 0;for(i=1;i=len;i+)subi=spos+i-1;sub0=len;return 1;/字串定位int index(sstring s,sstring t,int pos)/初始条件：字符串chars已经存在/操作结果：返回子串T在主串S中第pos个字符之后的位置，/若不存在，则函数值为int i,j;if(1=pos&pos=s0)i=pos;j=1;while(i=s0&jt0) return i-t0;elsereturn 0; elsereturn 0;/主函数void main() int i,pos,len; char aMAX,bMAX,cMAX; sstring s,t,v,sews,sub; int k; /设置选项变量 while(1) /system(cls);/清屏 printf(nt*); printf(nt* 串的基本操作及其应用 *); printf(nt*n); printf(t * 1.串的赋值 2.串比较 *n); printf(t * 3.串的长度 4.取子串 * n); printf(t * 5.字符串替换 6.字符串插入 * n); printf(t * 7.字符串连接 8.销毁队列 * n); printf(t * 9.清空队列 0.退出 *n); printf(t*n); printf(请选择选项: );/打印选项功能提示 scanf( %d,&k); if(k9) printf(输入有误，请重新输入!);printf(n); continue; switch(k) /分支结构来调用各功能子函数 case 1: printf(字符串的赋值!n); printf(请输入两个字符串!n); printf(请输入第一个字符串; ); scanf(%s,a); strassign(s,a); printf(n); printf(请输第二个字符串; ); scanf(%s,b); strassign(t,b); printf(第一个字符串为: ); strprint( s); printf(第二个字符串为: ); strprint( t); printf(n); break;/退出并重新进入主菜单 case 2: printf(串的比较!n); i=strcompare( s, t);/调用函数 if(i=0) printf(两个字符串相等!n); else if(i0) printf(第一个字符串比第二个字符串小!n); else printf(第一个字符串比第二个字符串大!n); printf(n); break;/退出并重新进入主菜单 case 3: printf(求串的长度!n); i=strlength(s);/调用函数 printf(串的长度为：%d,i); printf(n); break;/退出并重新进入主菜单 case 4: printf(取子串!n); printf(输入一个字符串: ); scanf(%s,a); strassign(s,a);/调用函数 printf(n); printf(字符串为: ); strprint(s); printf(请输入位置和长度!n); scanf(%d%d,&pos,&len); if(substring(sub,s,pos,len) printf(所取子串为: ); strprint(sub); else printf(取子串失败!); printf(n); break;/退出并重新进入主菜单 case 5: printf(字符串替换!n); printf(请输入主字符串: ); scanf(%s,a); strassign(s,a);/调用函数 printf(n); printf(请输需要替换子串: ); scanf(%s,b); strassign(t,b);/调用函数 printf(请输入需要换成的子串: ); scanf(%s,c); strassign(v,c);/调用函数 printf(主字符串为: ); strprint( s); printf(需要替换子串为: ); strprint( t);/调用函数 printf(需要换成的子串为: ); strprint( v); if( replace( s, t, v) printf(替换后的新串为：); strprint( s); else printf(替换失败n); printf(n); break;/退出并重新进入主菜单 case 6: printf(字符串插入n); printf(请输入主字符串n); scanf(%s,a); strassign(s,a);/调用函数 printf(请输入要插入的字符串n); scanf(%s,b); strassign(t,b);/调用函数 printf(请输入要插入的位置n); scanf(%d,&pos); printf(主字符串为：); strprint( s);/调用函数 printf(要插入的字符串为：); strprint(t); if( strinsert( s, pos, t) printf(插入后的新串为：); strprint(s);/调用函数 printf(n); break;/退出并重新进入主菜单 case 7: printf(字符串连接n); i= concat(sews,s,t);/调用函数 if(i=0) printf(连接失败n); else printf(连接