数据结构与算法 课件 第4章 串

第4章串串（又称字符串）是一种特殊的线性表，它的每个元素仅由一个字符组成。在文字编辑中的查找和替换，汇编和编译程序中的词法扫描，事务处理程序中的文本类型字段的处理等方面都是串的应用。1【本章重点】①串的定义和串的基本运算；②串的顺序和链式存储结构及基本运算的实现；③简单的模式匹配算法。2【本章难点】①改进的模式匹配算法；②串的应用。3【本章内容】串的概念及基本运算串的顺序存储结构及基本运算的实现串的模式匹配算法习题444.1串的概念及基本运算串的定义：串是由多个或零个字符组成的有限序列，记作S="c1c2c3…cn"(n≥0)。其中，S是串名，由双引号括起来的字符序列称为串值。说明：（1）ci（1≤i≤n）是串中字符，i是字符在串中的位置序号；n是串的长度，表示串中字符的个数，不包含任何字符的串称为空串，例如""是长度为0的空串。5（2）串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应的称为主串。子串在主串中的序号定义为子串在主串中首次出现的位置序号。例如，设S1和S2分别为： S1="Thisisastring"S2="is"则S2是S1的子串，S1是S2的主串。S2在S1中出现了两次，首次出现在主串的第3个位置上，因此S2在S1中的序号是3。（3）串可以分为串变量和串常量。例如使用C语言可以有如下定义：charstr[]="string";constcharstr_const[]="string";str是串变量，而str_const是串符号常量。（4）只含有空格的串称为空格串，例如"凵凵凵"是空格串，长度为36串的常用基本运算（1）StrLength(S)求串长。计算并返回串的长度。（2）StrCopy(S1,S2)串赋值。将S2赋给S1。S1是串变量，S2是串常量或者是串变量。（3）StrCat(S1,S2)串连接。将S2连接在S1的后面。S1是串变量，S2是串常量或者是串变量。例如，S1="ABCD"，S2="1234"，StrCat(S1,S2)运算的结果是S1="ABCD1234"，而S2="1234"。（4）StrCmp(S1,S2)串比较。若S1=S2，则结果为0；若S1>S2，则运算结果大于0；若S1<S2，则结果小于0。两个串的比较，实际上比较的是字符的ASCII码值。从第一个位置上的字符开始逐个字符进行比较，当第一次出现字符不等的情况，即可得到比较的结果。例如"abcd"等于"abcd"，"abc"大于"aBc"，"abc"小于"abcd"。7（5）StrIndex(S,T)子串定位。若串T是串S的子串，则结果为T在S中首次出现的位置，否则运算结果为0。例如StrIndex("DataStructures","ruct")的结果为8。（6）SubStr(Sub,S,i,len)求子串。串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，运算结果是得到S串从第i个字符开始的长度为len的子串，并将其赋给T。如果len为0，则赋给Sub的是空串。例如SubStr(Sub,"student",4,3)的结果是Sub="den"。（7）StrInsert(S,i,T)串插入。串S和T均为非空串，且1≤i≤StrLength(S)+1。结果是将串T插入到串S的第i个字符位置上，串S的值被改变。例如S="Youareastudent"，T="rteacher"，StrInsert(s,4,t)的运算结果是S="Yourteacherareastudent"。（8）StrDelete(S,i,len)串删除。串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，运算结果是删除S串中从第i个字符开始的长度为len的子串，串S的值被改变。8（9）StrRep(S,T,R)串替换。串S、T、R均非空，运算结果是用串R替换串S中所有子串T，串S的值被改变。以上是串的基本运算，其中前5个运算是最基本的，而其余的串运算一般可以由这些最基本的串运算组合而成。94.2

串的顺序存储结构及基本运算的实现1、串的顺序存储结构串的顺序存储结构即顺序串，顺序串用一组地址连续的存储单元（一维字符数组）存储串值的字符序列，其中每个结点是单个字符。串的定长顺序存储

直接使用定长的字符数组来定义，数组的上界预先给出。一般有三种方法表示串的长度：（1）用一个整型变量来表示串的长度。顺序串的类型定义和顺序表类似，其定义如下：#defineMAXSIZE256typedefstruct{charch[MAXSIZE];intlength;}SeqString;SeqStrings; //s为结构体变量顺序串的长度表示为s.length10（2）在串的末尾设置串结束符，例如C语言用转义字符'\0'作为串结束符。这种方式不能直接得到串的长度，而是通过判断当前字符是否为'\0'来确定串是否结束，从而求得串的长度。顺序串的定义如下：#defineMAXSIZE256typedefcharsstring[MAXSIZE];sstrings;//s是一个可容纳255个字符的顺序串。这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放'\0'字符作为串结束符。11注意：串中字符的位序从1开始，字符数组从下标0开始存放字符串（3）顺序串存储空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，而串值存放在s[1]~s[MAXSIZE]中。优点：字符的序号与存储位置的下标一致12串的实际长度在后面的算法中，顺序串采用第2种存储方式，即从数组下标0开始存放字符，并且在串尾存储串结束符'\0'。1、求串长13顺序串基本运算的实现算法4.1 求顺序串的长度，即统计串中字符的个数。intStrLength(char*s){ i=0; while(s[i]!='\0') i++; returni;}2、串赋值（串复制）14算法4.2 将串s2复制给串s1。voidStrCopy(char*s1,char*s2){ i=0; while(s2[i]!='\0') { s1[i]=s2[i]; i++; } //逐个字符赋值 s1[i]='\0'; //置串结束标志}3、串比较15算法4.3 比较两个串s1和s2的大小。若s1>s2，返回值大于0；若s1=s2，返回值等于0；若s1<s2，返回值小于0。intStrCmp(char*s1,char*s2){ i=0; while(s1[i]==s2[i]&&s1[i]!='\0')//两个串对应位置上的字符进行比较 i++; returns1[i]-s2[i];}4、串连接16算法4.4 将两个串s1和s2首尾连接成一个新的串s1。intStrCat(char*s1,char*s2){ len1=StrLength(s1); len2=StrLength(s2); if(len1+len2>MAXSIZE-1) return0; //串s1的存储空间不够，返回错误代码0 i=0;j=0; while(s1[i]!='\0') //找到串s1的串尾 i++; while(s2[j]!='\0') //将串s2的串值复制到串s1的串尾 s1[i++]=s2[j++]; s1[i]='\0'; //置串s1结束标志 return1; //连接成功，返回代码1}复习：常用的C语言字符串处理库函数。教材P79【例4.1】利用C语言的库函数完成取子串运算。取主串s中pos起始的len个字符作为子串sub。例如，主串s=“d:\\user\\wang\\”，pos=8，len=5，sub=“\\wang”17voidSubStr(char*sub,char*s,intpos,intlen){ if(pos<1||pos>strlen(s)||len<0)printf("parametererror!\n"); else{ strncpy(sub,s+pos-1,len);//复制子串字符

strcpy(sub+len,"\0");//添加子串的串结束符 }}4.4串的模式匹配算法子串定位又称为串的模式匹配。设主串称为目标串，子串称为模式串，所谓模式匹配，就是在目标串中查找模式串的出现位置，例如在文本中查找是否存在给定的单词及出现的位置。简单的模式匹配算法（朴素的模式匹配算法，BF算法）

假设T为目标串（主串），P为模式串（子串）。

T="t1,t2,…,tn"P="p1,p2,…,pm"其中0＜m≤n1819算法4.5顺序串简单的模式匹配。intIndex(seqstring*T,seqstring*P,intpos)//顺序串的朴素模式匹配，串的位序从1开始{i=pos;j=1;//目标串从第pos个字符开始与模式串的第一个字符开始进行比较while(i<=T->length&&j<=P->length)if(T->ch[i-1]==P->ch[j-1])//串从数组的0元素开始存放{i++;j++;}//继续比较后面的字符else{i=i-j+2;j=1;}//本趟不匹配，设置下一趟匹配的起始位序if(j>P->length)return(i-P->length);//匹配成功elsereturn(0);//匹配不成功}算法的基本思想是：从目标串T的第pos个字符开始与模式串P的第一个字符进行比较，若相等，则继续比较后面的字符；否则从目标串的下一个字符开始与模式串的第一个字符进行下一趟比较。重复此过程，直至模式串中的每个字