串的基本操作及其应用

广西工学院计算机学院《数据结构》课程实验报告书实验五串的基本操作及其应用学生姓名：1学号：2班级：3指导老师：4专业：计算机学院软件学院提交日期：2013年6月21日-1-1．实验目的1）掌握串的定义、存储结构及基本操作。2.实验内容（1）建立一个串，实现串的基本操作。包括：//1.判串长:返回串s的元素个数。intStrLength(HStringS)//2.判空串:若串s为空串，则返回trueStatusStrEmpty(HStringS)//3.串赋值：现有串s，空串t,实现将s赋值给t的操作StatusStrAssign(HString&T,HStringS)//4.串连接：现有串s和t，实现将t链接到串s之后的操作。（流程图）StatusStrConcat(HString&S,HStringT)//5.串比较:依次比较2个串s和t,若长度相同且字符相同，则串相同，返回0，若st,则返回值0,若st,则返回值0.（流程图）StatusStrCompare(HStringS,HStringT)//6.串替换:在主串s中用子串v替换所有的子串tStatusStrReplace(HString&S,HStringV,HStringT)//7.串插入：在主串s中的给定位置pos插入子串tStatusStrInsert(HString&S,intpos,HStringT)//8.取子串:将串s中从起始位置pos开始长度len的字符串放入另一个串tStatusSubString(HString&S,intpos,intlen,HString&T)//9.串删除:删除串s中的子串t。StatusStrDelete(HString&S,HStringT)//10.求子串位置：从主串s中取出从第i个位置开始、长度和串t相同的子串，和t进行比较，若相等，则t在s中的位置值为iStatusStrIndex(HString&S,inti,HStringT)//（2）串应用：设有串s，求出它的所有子串,并输出。StatusSubString_All(HStringS)3．实验要求（1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。（2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。（3）实验课上进行答辩。（4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。串的堆分配存储typedefstruct{char*ch;//若是非空串，则按串长分配储存区，否则ch为NULL-2-intlength;//串长度}HString;2．3．主要算法3.1顺序存储结构（1）结构定义：#includestdio.h#includestdlib.h#includestring.h#defineMAX255typedefcharsstring[MAX+1];intstrlength(sstrings);//判断串长intstrempty(sstrings);//判断空串intstrassign(sstring&t,char*s);//串赋值intconcat(sstring&t,sstrings1,sstrings2);//串连接intstrcompare(sstrings,sstringt);//串的比较voidstrprint(sstrings);//输出intstrinsert(sstrings,intpos,sstringt);//串插入intstrdelete(sstrings,intpos,intlen);//删除字串intreplace(sstrings,sstringt,sstringv);//串的替换intsubstring(sstring&sub,sstrings,intpos,intlen);//取子串intindex(sstrings,sstringt,intpos);//字串定位//串赋值intstrassign(sstring&t,char*s){//初始条件：字符串chars已经存在//操作结果：生成一个其值等于chars的串tinti,n;n=strlen(s);if(n=MAX)return0;else{t[0]=n;for(i=1;i=t[0];i++)//依次给串赋值t[i]=s[i-1];return1;}}-3-//求串长度intstrlength(sstrings){//操作结果：返回串s的元素returns[0];}//判断串是否空intstrempty(sstrings){return(s[0]==0);//返回值}//串连接intconcat(sstring&t,sstrings1,sstrings2){//初始条件：字符串s1和s2已经存在//操作结果：用T返回s1和s2连接成的新串。inti;if(s1[0]+s2[0]=MAX){for(i=1;i=s1[0];i++)//依次把串s1中的元素赋值给串tt[i]=s1[i];for(i=1;i=s2[0];i++)t[i+s1[0]]=s2[i];t[0]=s1[0]+s2[0];//计算串t的长度return1;}else{for(i=1;i=s1[0];i++)t[i]=s1[i];for(i=1;i=MAX-s1[0];i++)t[i+s1[0]]=s2[i];t[0]=MAX;return1;}}-4-//串的比较intstrcompare(sstrings,sstringt){//初始条件：字符串chars已经存在//操作结果：若是st,则返回值0,若是s=t,则返回值=0,若是st,则返回值0inti;for(i=1;i=t[i]&&i=s[0];i++)if(s[i]!=t[i])returns[i]-t[i];//返回大于的值returns[0]-t[0];//返回大于的值}//输出voidstrprint(sstrings){//初始条件：字符串chars已经存在//操作结果：依次输出串中的元素inti;for(i=1;i=s[0];i++)printf(%c,s[i]);printf(\n\n);}//串插入intstrinsert(sstrings,intpos,sstringt){//初始条件：字符串chars已经存在//操作结果：在串s第pos个字符之前插入串t，完成插入返回，否则返回inti;if(pos1||poss[0]+1)return0;if(s[0]+t[0]=MAX){for(i=s[0];i=pos;i--)s[i+t[0]]=s[i];for(i=pos;ipos+t[0];i++)s[i]=t[i-pos+1];s[0]+=t[0];return1;}else{for(i=s[0];i=pos;i--)s[i+MAX-s[0]]=s[i];for(i=pos;i=s[0];i++)s[i]=t[i-pos+1];-5-s[0]=MAX;return1;}}//删除字串intstrdelete(sstrings,intpos,intlen){//初始条件：字符串chars已经存在//操作结果：在串s第pos个字符起删除长度为len的子串，删除成功返回，否则返回inti;if(pos1||poss[0]-len+1||len0)return0;for(i=pos+len;i=s[0];i++)//依次删除串中指定的元素s[i-len]=s[i];s[0]-=len;return1;}//串的替换intreplace(sstrings,sstringt,sstringv){//初始条件：字符串chars已经存在//操作结果：串t被s替换，成功返回，否则返回inti=1;intk;if(strempty(t))//判断串t为空return0;do{i=index(s,t,i);printf(%d,i);if(i){strdelete(s,i,t[0]);//调用函数k=strinsert(s,i,v);//调用函数if(!k)return0;i+=v[0];}}while(i);return1;}-6-//取子串intsubstring(sstring&sub,sstrings,intpos,intlen){//初始条件：字符串chars已经存在//操作结果：用sub返回串s的第pos个字符起长度为len的子串inti;if(pos1||poss[0]||len0||lens[0]-pos+1)return0;for(i=1;i=len;i++)sub[i]=s[pos+i-1];sub[0]=len;return1;}//字串定位intindex(sstrings,sstringt,intpos){//初始条件：字符串chars已经存在//操作结果：返回子串T在主串S中第pos个字符之后的位置，//若不存在，则函数值为inti,j;if(1=pos&&pos=s[0]){i=pos;j=1;while(i=s[0]&&j=t[0])if(s[i]==t[j]){i++;j++;}else{i=i-j+2;j=1;}if(jt[0])returni-t[0];elsereturn0;}elsereturn0;}-7-//主函数voidmain(){inti,pos,len;chara[MAX],b[MAX],c[MAX];sstrings,t,v,sews,sub;intk;//设置选项变量while(1){//system(cls);//清屏printf(\n\t***************************************************);printf(\n\t*串的基本操作及其应用*);printf(\n\t***************************************************\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(请选择选项1-9:);//打印选项功能提示scanf(%d,&k);if(k0||k9){printf(输入有误，请重新输入!);printf(\n);continue;}switch(k)//分支结构来调用各功能子函数{case1: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);-8-printf(\n);break;//退出并重新进入主菜单case2:printf(串的比较!\n);i=strcompare(s,t);//调用函数if(i==0)printf(两个字符串相等!\n);elseif(i0)printf(第一个字符串比第二个字符串小!\n);elseprintf(第一个字符串比第二个字符串大!\n);printf(\n);break;//退出并重新进入主菜单case3:printf(求串的长度!\n);i=strlength(s);//调用函数printf(串的长度为：%d,i);printf(\n);break;//