数据结构 第六讲 串

《数据结构 第六讲 串》由会员分享，可在线阅读，更多相关《数据结构 第六讲 串（51页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构 第六讲第六讲 串串 清华大学清华大学 自动化系自动化系 黄双喜黄双喜 博士博士 提纲提纲 1.1. 串的定义串的定义 2.2. 串的表示和实现串的表示和实现 3.3. 串的模式匹配算法串的模式匹配算法 1 1、串的定义、串的定义 串串(String)(String)是由零个或多个字符组成的有限序列。是由零个或多个字符组成的有限序列。 记为：记为：s=s=a a1 1a a2 2a an n (n0)(n0) 其中，其中，s s是串的名，用单引号括起来的字符序列是串的值。是串的名，用单引号括起来的字符序列是串的值。 a ai i(1in)(1in)可以是字母、数字或其它字符。

2、可以是字母、数字或其它字符。 注：注：串值必须用一对单引号括起来，区别于变量名或数的常量。例串值必须用一对单引号括起来，区别于变量名或数的常量。例 如：如：1 1与与1 1 串（即字符串）是一种特殊的线性表，它的数据元素仅串（即字符串）是一种特殊的线性表，它的数据元素仅 由一个字符组成。由一个字符组成。 基本概念基本概念 串的长度串的长度串中字符的数目串中字符的数目n n。 空串空串(Null(Null string)string)长度为零的串长度为零的串。用用“”表示表示。 子串子串串中任意个串中任意个连续连续的字符组成的子序列的字符组成的子序列。 主串主串包含子串的串相应地称为主串包含子串

3、的串相应地称为主串。 位置位置称字符在序列中的序号为该字符在串中的位称字符在序列中的序号为该字符在串中的位 置置。 子串在主串中的位置子串在主串中的位置则以子串的第一个字符在主串则以子串的第一个字符在主串 在的位置来表示在的位置来表示。 例如例如:a,b,c,d :a,b,c,d 四个字符串为四个字符串为 a=a=BEIBEI , b=, b=JINGJING c=c=BEIJINGBEIJING , d=, d=BEI JINGBEI JING 它们的长度分别为它们的长度分别为 ：3,4,7,83,4,7,8 a a和和b b都是都是c c和和d d的的子串子串 a a在在c c和和d d中

4、的位置是中的位置是1 1 b b在在c c中的位置是中的位置是4 4, ,而而b b在在d d中的位置是中的位置是5 5 注意注意: :单引号是为字符串区别于变量名而设单引号是为字符串区别于变量名而设, ,它不是字它不是字 符串的内容符串的内容 如何表示单引号？如何表示单引号？ 空格串和空格串和“空串空串”区别区别: : 空格串的长度是空格的个数空格串的长度是空格的个数。 “空串空串”长度为零长度为零。 串与线性表的区别：串与线性表的区别： 逻辑结构相似：区别仅在于串的数据对象约束为字符集。逻辑结构相似：区别仅在于串的数据对象约束为字符集。 表示与实现差别很大：线性表以表示与实现差别很大：线性

5、表以“单个元素单个元素”作为操作对作为操作对 象；串以象；串以“串的整体串的整体”作为操作对象作为操作对象; ; 串相等串相等只有当两个串的长度相等，并且各个对应位只有当两个串的长度相等，并且各个对应位 置的字符都相等，称两串相等。置的字符都相等，称两串相等。 空格串空格串(blank string)(blank string)由一个或多个由一个或多个空格空格组成的串。组成的串。 串比较大小：串比较大小：比较第一个不相同字符的比较第一个不相同字符的ASCIIASCII码码 串的抽象数据类型定义串的抽象数据类型定义 ADT String ADT String 数据对象数据对象：D=aD=ai i

6、|a|ai iCharacterSetCharacterSet，i=1,2i=1,2n n，n0n0 数据关系数据关系：R= |a |ai i- -1 1，a ai iDD，i=i=2 2,3,3,n,n 基本操作基本操作：ADT StringADT String StrAssignStrAssign( m=Strlength(T); i=pos; While(i 复习：复习：C语言中常用的串运算语言中常用的串运算 Replace( (1)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,“,“); strcat(s3,s2); (2)调用函数strcmp(

7、s1,s2)的返回值是什么? (3)调用函数strcmp( 后，s3的值是“Stocktom,CA“ 在执行strcat(s3,“,“); 后，s3的值变成“Stocktom,Ca,“ 在执行完strcat(s3,s2);后，s3的值就成了“Stocktom,Ca,March 5,1999“ （2）函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较， 返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1 小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符 比较是以ascii码值相比的) （3）首先，我们要知道 /typedef ch

8、ar SStringMAXSTRLEN+1; / 0号单元存放串的长度 用数组表示用数组表示 注：在注：在MAXSTRLENMAXSTRLEN范围之内，串的长度任意范围之内，串的长度任意 串长值存储在串长值存储在SString0SString0中。中。 超过予定义长度的串值则被舍去，称之为“截断”超过予定义长度的串值则被舍去，称之为“截断”.当操当操 作出现串值序列的长度超过上界作出现串值序列的长度超过上界MAXSTRLEN时时(串连接、串连接、 插入、置换插入、置换)，约定用截尾法处理。，约定用截尾法处理。 将超出最大长度的字将超出最大长度的字 符舍去。克服这个弊病唯有不限制串长的最大长度，

9、即符舍去。克服这个弊病唯有不限制串长的最大长度，即 动态分配串值的存储空间。动态分配串值的存储空间。 串连接：串连接：Concat(Sstring 否 则返回0。 if ( S10+S20 s0 | len s0 - pos +1 ) return ERROR; Sub1len = Spospos+len-1; / 示意赋值，非C语句 Sub0 = len; return OK; / SubString n e d u t S MAXSIZE-1 5 4 3 2 1 0 s.data s.curlen n e d I=4 ,len=3 t.data TypedefTypedef structs

10、truct charchar * *chch; ; /若是非空串,则按实际长度分配,否则为NULL; intint lengthlength; ;/串长度 HStringHString; ; 2.2.堆分配存储表示堆分配存储表示动态分配存储空间动态分配存储空间 仍以一组地址连续的存储单元存放串值字符序列，但它们的存仍以一组地址连续的存储单元存放串值字符序列，但它们的存 储空间是在程序执行过程中动态分配而得。储空间是在程序执行过程中动态分配而得。 在C语言中，存在一个称之为“堆”的自由存储区，并由动 态分配函数malloc()和free()来管理。利用函数malloc()为每 个新产生的串分配一

11、块实际串长所需的存储空间，若分配成 功则返回一个指向起始地址的指针，作为串的基址；否则返 回0。 串赋值串赋值 Status StrAssign(HString /释放释放T原有空间原有空间 for(i=0, c=chars; c ; +i,+c) ; /求求chars的长度的长度I if(!i) T.ch = NULL； T.length=0; else if(!(T.ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); T.ch0i-1 = chars0i-1; T.length = i; return OK; 直到终值为直到终值为“假假”停停

12、止，串尾特征是止，串尾特征是 C CNULLNULL或或*C*C /0/0 C C是指针变量，可以自增！是指针变量，可以自增！ 意即每次后移一个数据意即每次后移一个数据 单元。单元。 此处此处T.ch0T.ch0没没 有用来装串长有用来装串长 Int StrCompare(HString S,HString T) For (i=0;iT长度返回正数，S.length|lenS.length-pos+1) return ERROR; if(Sub.ch) free(Sub.ch); if(!len) Sub.ch=NULL; Sub.length=0; else Sub.ch=(char *)m

13、alloc( len*sizeof(char); Sub.ch0len-1=S.chpos-1pos+len-2; Sub.length=len; return OK; 串插入：串插入： StrInsert(HString /pos不合法则告警不合法则告警 if(T.length) /只要串只要串T不空，就需要重新分配不空，就需要重新分配S空间，以便插入空间，以便插入T if (!(S.ch=(char*)realloc(S.ch,(S.length+T.length)* sizeof(char) exit(overflow); for(i=S.length-1;i=pos-1;-i) / 为

14、插入为插入T而腾出而腾出pos之后的位置，之后的位置， 即从即从S的的pos位置起全部字符均后移。这时位置起全部字符均后移。这时S.length？ S.chi+T.length=S.chi; S.chpos-1pos+T.length-2=T.ch0T.length-1; /插入插入T S.length+=T.length; /刷新刷新S串长度串长度 return OK; 串的块链存储表示 顺序串上的插入和删除操作不方便，需要移动大量的字 符。因此，我们可用单链表方式来存储串值，串的这种链式 存储结构简称为链串。 typedeftypedef structstruct nodenode cha

15、r data;char data; structstruct node node *next;*next; lstringlstring; ; 一个链串由头指针唯一确定。 这种结构便于进行插入 和删除运算，但存储空间利存储空间利 用率太低。用率太低。 s d y string1 为了提高存储密度，可使每个结点存放多个字符每个结点存放多个字符。通 常将结点数据域存放的字符个数定义为结点的大小结点的大小，显然， 当结点大小大于1时，串的长度不一定正好是结点的整数 倍，因此要用特殊字符#(#不属于串的字符集)来填充 最后一个结点，以表示串的终结。 head A B C D T A N K E N D # 结点大小为4的链表 存储密度的概念存储密度的概念： 实际分配的存储位 串值所占的存储空间 存储密度 例如: 在编辑系统中，整个文本编辑区可以看成是一个 串，每一行是一个子串，构成一个结点。即: 同一行的串 用定长结构(