数据结构与算法：第4章 串实验

第4章串4.1知识点概述串是一种特殊的线性表，它的每个结点仅由一个字符组成。串是计算机中主要的非数值处理的对象，在计算机文字编辑、词法分析等方面有着广泛的应用。串的基本运算有：串赋值、串复制、判断串空否、求串长、串联接、求子串、子串位置、串比较、串置换、插入和删除等。串的存储有顺序存储（定长顺序存储和堆存储）和链式存储。4.2字符串的基本操作一、实验目的掌握字符串的基本操作掌握字符串函数的基本使用方法熟悉串的模式匹配算法和一般的文字处理方法二、实验内容（一）验证实验1、串的模式匹配：设有一目标串s和一模式串s1，判断目标串s中是否包含模式串s1。方法是：从目标串s中的第一个字符开始，按s1模式串的长度s1.len，与s1子串中的字符依次对应比较。若不匹配，则再从目标串s中的第二个字符开始，仍按s1模式串的长度s1.len，与s1子串中的字符依次对应比较。如此反复进行比较。直到匹配成功或者目标串s中剩余的字符少于s1的长度为止。若匹配成功，则返回s1在s中的位置。若匹配不成功，则返回函数值－1。2、串连接：将两个字符串连接。其中一个串接在另一个串的末尾，生成一个新串。（注意：串的末尾有\0)若给出两个串s1和s2，把s2连接在s1之后，生成一个新串s。3、两串相等判断：给定两个串s1和s2，当s1和s2相等时，返回函数值1，否则返回函数值0。实验程序：1、#defineMAXLEN25typedefstruct{charch[MAXLEN];intlen;}string;intindex(strings,stringt,intpos){inti,j;i=pos;j=0;while(i<s.len&&j<t.len){if(s.ch[i]==t.ch[j]){++i;++j;}else{i=i-j+1;j=0;}}if(j>t.len-1)return(i-t.len);elsereturn（-1）;}main(){stringa={"BeijingShanghaiChina",22},a1={"Shanghai",8};intr;r=index(a,a1,0);printf("\n%d",r);}2、#defineMAXLEN14typedefstruct{charch[MAXLEN];intlen;}string;stringconnect(strings1,strings2){strings;inti;if(s1.len+s2.len<=MAXLEN){for(i=0;i<s1.len;i++)s.ch[i]=s1.ch[i];for(i=0;i<s2.len;i++)s.ch[s1.len-1+i]=s2.ch[i];s.len=s1.len+s2.len-1;}elses.len=0;return(s);}main(){stringa1={"Beijing",8},a2={"Ching",6};stringa;a=connect(a1,a2);printf("\n%s\n%d",a.ch,a.len);}3、#defineMAXLEN13typedefstruct{charch[MAXLEN];intlen;}string;intequal(strings1,strings2){inti;if(s1.len!=s2.len)return(0);else{for(i=0;i<s1.len;i++)if(s1.ch[i]!=s2.ch[i])return(0);}return(1);}main(){stringa1={"Beijing",8},a2={"ching",5};intr;r=equal(a1,a2);printf("\n%d",r);}（二）设计实验1、根据串的基本操作完成串查找和替换操作2、用标准c语言实现KMP算法和BM算法。3、实现单模匹配算法BMH、BMHS。1、实验程序：#include<stdio.h>#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];intstrLength(SStringS)//求串的长度{intm;for(m=0;S[m]!='\0';m++);returnm;}voidStringCopy(SStringT,SStringS){inti;for(i=1;i<=strLength(S);i++)T[i]=S[i];T[i]='\0';}voidReplace(SStrings,SStrings1,SStrings2){SStringt;inti,j,f,k=0;if(strLength(s)>=strLength(s1)){for(i=0;i<=strLength(s);){if(i<=strLength(s)-strLength(s1)){f=1;//查找for(j=0;j<strLength(s1);j++)if(s[i+j]!=s1[j]){f=0;break;}}elsef=0;if(f==1){for(j=0;j<strLength(s2);j++,k++)//替换t[k]=s2[j];i=i+strLength(s1);}else{t[k]=s[i];//复制一个字符k++;i++;}}}StringCopy(s,t);//复制字符串}voidmain(){SStringstr;SStringtemp,substr;printf("请输入主串：");scanf("%s",str);printf("请输入查找的字符串");scanf("%s",temp);printf("请输入替换的字符串");scanf("%s",substr);Replace(str,temp,substr