数据结构课件-第四章-串.ppt

《数据结构课件-第四章-串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串学习要点掌握串的基本操作以及串操作在不同存储结构下的实现。理解串的模式匹配算法。4.1串类型的定义1．串的定义串(string)是由零个或多个字符组成的有限序列，一般记作S=“a1a2a3…an”，其中S为串的名字，用双引号括起来的字符序列是串值，但两边的双引号不算作串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2．空串长度为零的串称为空串(EmptyString)，它不包含任何字符，记为s=“”。通常将仅由一个或多个空格组成的串称为空白串(BlankString)。注意：空串和空白串的不同，例如

2、“”和“”分别表示长度为1的空白串和长度为0的空串。一、串和基本概念3．子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如,串s1=“abcd”，s2=“fabcdef”，则s1为s2的子串，s2相对于s1为主串。再如,串s1=“is”，s2=“Thisisastring”，则s1为s2的子串，s2相对于s1为主串。s1在s2中出现了两次，其中首次出现所对应的主串位置是3。因此，称s1在s2中的序号为3。另

3、外:空串是任意串的子串，任意串是其自身的子串。二、串的基本操作1.串赋值StrAssign(s,t)表示将字符序列t赋给名为s串。2.求子串SubStr(sub,s,i,len)用sub返回串s的第i个字符起长度为len的子串。3.求串长度StrLength(s)求s串的长度，即返回串s中元素的个数。4.串联接StrConcat(s,t)表示将s串和t串联接起来，使t串接入s串的后面。5.串的比较StrCmp(s,t)例如：result=StrCmp(“baker”,”Baker”)result>0result=StrCmp(“12”,”12”);resul

4、t=0result=StrCmp(“Joe”,”Joseph”);result<06.判等StrEqual(s,t)若s和t长度相等，两个串对应位置的字符也相等，返回真值，否则返回假。7.求子串位置StrIndex(s,t)若串t是串s的子串，则返回子串t在主串s中首次出现的位置；若串t不是串s的子串，则返回-1。8.串替换StrRep(s,t,r)将s串中所有的子串t用串r代替。9.串插入StrInsert(s,t,i)在串s的第i个位置插入串t。10.串删除StrDelete(s,i,len)删除串s中从第i个字符开始连续的len个字符。串的存储结构串的

5、定长顺序存储串的块链存储串的堆分配存储由串的定义可知，串是一种特殊的线性表，其中的每一个数据元素均是一个字符。其存储结构与线性表的存储结构类似,只不过由于组成串的结点是单个字符。串的存储结构有静态顺序存储结构、动态顺序存储结构和链式存储结构。4.2串的存储表示4.2.1串的定长顺序存储串的顺序存储结构，也称为顺序串,可以用一组连续的存储单元来存储串的字符序列。#defineMAXLEN256charstr[MAXLEN];1.与第二章介绍的顺序表类似，单独定义一个成员存放串的长度。typedefstruct{chardata[MAXLEN];intlengt

6、h;}SeqString如何标识实际长度？abcde下标：2.在串尾存储一个不会在串中出现的特殊字符作为串的结束符在C语言中以字符‘’作为串的结束标志，这个结束标志不计入串长，但是它要占用一个字符空间。所以在这种定义下，一个串的长度小于等于MAXLEN-1。串s=“abcde”的顺序表示：0123453.用str[0]存放串的长度，charstr[MAXLEN+1];串值存放在str[1]…str[MAXLEN]中，字符的序号与存储位置的下标值一致。1.求串长功能：返回串s中元素的个数顺序存储字符串的基本操作的实现voidStrLength(cha

7、rs[]){inti=0;while(s[i]!=‘’)i++;returni;}2.串的连接功能：把s1和s2连接成一个串，其中s1在前，s2在后voidStrConcat(char*s1,char*s2){inti,len1=StrLength(s1),len2=StrLength(s2);if((len1+len2)>MAXLEN-1)printf(“长度不够!");else{for(i=0;i

8、第i个字符开始，把连续len个字符组成的子串赋给另一