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

第4章串

4.1知识点概述

串是一种特殊的线性表，它的每个结点仅由一个字符组

成。串是计算机中主要的非数值处理的对象，在计算机文字

编辑、词法分析等方面有着广泛的应用。串的基本运算有:

串赋值、串复制、判断串空否、求串长、串联接、求子串、

子串位置、串比较、串置换、插入和删除等。串的存储有顺

序存储（定长顺序存储和堆存储）和链式存储。

4.2字符串的基本操作

一、实验目的

1、掌握字符串的基本操作

2、掌握字符串函数的基本使用方法

3、熟悉串的模式匹配算法和一般的文字处理方法

二'实验内容

（一）验证实验

1、串的模式匹配：设有一目标串s和一模式串si,判

断目标串s中是否包含模式串Slo

方法是：从目标串s中的第一个字符开始，按si模式

串的长度si.len,与si子串中的字符依次对应比较。若不

匹配，则再从目标串S中的第二个字符开始，仍按S1模式

串的长度si.len,与si子串中的字符依次对应比较。如此

反复进行比较。直到匹配成功或者目标串s中剩余的字符少

于si的长度为止。若匹配成功，则返回si在s中的位置。

若匹配不成功，则返回函数值一1。

2、串连接：将两个字符串连接。其中一个串接在另一个

串的末尾，生成一个新串。(注意：串的末尾有\0)若给出

两个串si和s2,把s2连接在si之后，生成一个新串s。

3、两串相等判断：给定两个串si和s2,当si和s2相

等时，返回函数值1,否则返回函数值0。

实验程序：

1、#defineMAXLEN25

typedefstruct

{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+l;j=0;}

)

if(j>t.len-l)return(i-t.len);

elsereturn(-1);

)

main()

{stringa={"BeijingShanghai

China",22},al={"Shanghai",8};

intr;

r=index(a,al,O);

printf("\n%d",r);

)

2、#defineMAXLEN14

typedefstruct

{charch[MAXLEN];

intlen;

}string;

stringconnect(stringsi,strings2){

strings;

inti;

if(s1.len+s2.1en<=MAXLEN)

for(i=0;i<s1.len;i++)

s.ch[i]=sl.ch[i];

for(i=0;i<s2.1en;i++)

s.ch[s1.len-l+i]=s2.ch[i];

s.len=sl.len+s2.1en-l;}

else

s.len=O;

return(s);

)

main()

{stringal={"Beijing",8},a2={"Ching",6};

stringa;

a=connect(al,a2);

printf("\n%s\n%d",a.ch,a.len);)

3、#defineMAXLEN13

typedefstruct

{charch[MAXLEN];

intlen;

}string;

intequal(stringsi,strings2){

inti;

if(sl.len!=s2.1en)

return(0);

else

{for(i=0;i<sl.len;i++)

if(sl.ch[i]!=s2.ch[i])

retum(O);

)

return(l);

)

main()

{stringal={"Beijing",8},a2={"ching",5};

intr;

r=equal(al,a2);

printf("\n%d",r);

)

(二)设计实验

1、根据串的基本操作完成串查找和替换操作

2、用标准c语言实现KMP算法和BM算法。

3、实现单模匹配算法BMH、BMHSo

1、实验程序：

#include<stdio.h>

#defineMAXSTRLEN255

typedefunsignedcharSString[MAXSTRLEN+1];

intstrLength(SStringS)〃求串的长度

{intm;

for(m=0;S[m]!='\0';m++);

returnm;

)

voidStringCopy(SStringT,SStringS)

(

inti;

for(i=l;i<=strLength(S);i++)

T[i]=S[i];

T[i]='\0';

)

voidReplace(SStrings,SStringsi,SStrings2)

{SStringt;

inti,j,f,k=O;

if(strLength(s)>=strLength(sl))

{for(i=0;i<=strLength(s);)

{if(i<=strLength(s)-strLength(sl))

{f=l；〃查找

for(j=0;j<strLength(sl);j++)

if(s[i+j]!=sl[j])

{f=0；

break;}

}

elsef=0;

if(f=l)

(

for(j=0;j<strLength(s2);j++,k++)//替换

t[k]=s2[j];

i=i+strLength(sl);

}

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);

print