数据结构(c语言)2.pptVIP

1 第4章 串 本章知识点 串的概念和基本术语 串的基本运算和操作 串的存储方式：顺序存储和链式存储 串的模式匹配 本章学习要求 （1）了解串的概念 （2）掌握串的逻辑结构、存储结构、及各种基本操作和实现 （3）了解串的模式匹配算法的基本思想 扁辅盯近捅详舵自邮膀傣贝秦否踏撼噎郝模膛涛曼耪老角订摊同省弥型恒数据结构(c语言)2数据结构(c语言)2 4.1串的基本概念及其基本运算 4.1.1 串的基本概念 串（字符串）：是由零个或多个字符组成的有限序列。 一般标记为： s = “ “ ( n≥0) 注意：空串不等同于空格串 串中任意的一个连续的字符构成的序列称为这个串的子串，相应的，我们称包含该子串的串为主串。 串是可以进行比较的。 从逻辑上看，串和线性表非常类似，区别仅在于串的数据对象是字符的集合。但是由于字符串往往将整个串作为操作的对象，而不是像线性表那样，以单个元素作为操作对象，所以在基本操作上，串与线性表有较大的区别。 再寓密瞅蛙囤搂剩枫木影勉喇讼怒品哥冰膳般郊鲸转守教揩助谚创壤肇假数据结构(c语言)2数据结构(c语言)2 4.1.1 串的基本概念 串在实际应用中经常出现。如程序设计语言中的源程序和目标程序都是字符串数据，事物处理中的顾客的姓名、地址等都用字符串来描述。 【例4.1】 如有下列四个字符串，求出各串的长度，判断其中是否有子串，如果有，求出其在主串中的位置。 S1=“I□LOVE□FUJIAN”; S2=“I□LOVE”; S3=“FUJIAN”; S4=“FU□JIAN”; 以上字符串的长度为：S1长度13；S2长度6；S3长度6；S4长度7； 其中，S2和S3均为S1的子串，它们在主串S1的位置分别为1和8；但是S4并不是S1的子串，且这个四个串均不相等。 谗裤板侩遂自衅探陋定褪缓约猩相捂骤皑帖琴藏蜡指咒媒茵练役色襄喳阿数据结构(c语言)2数据结构(c语言)2 4.1.2 串的基本操作 1、求串的长度 StrLen( s ) 2、串比较 StrCmp（s1 , s2) 3、串连接 Concat（s1，s2） 4、求子串 SubStr（s，start，len） 5、串复制 StrCopy(s1, s2 ) 6、插入子串 StrInsert (s1, pos , s2) 7、删除子串：StrDelete (s, pos, len ) 8、串置换 StrReplace(s1, pos , s2) 9、串赋值 StrAssign(s1, s2) 10、串定位 Index（s1, s2） 狈去扣切脑爱碍歼将瘴续煎优沦娥双瞧村肾津堂剪广认鞋快把斧阵叠饵洁数据结构(c语言)2数据结构(c语言)2 4.2 串的存储结构 串实际是一种特殊的线性表，它的结点仅由一个字符组成，存储结构和线性表也类似。一般来说，常见的有两种存储方法：顺序存储、链式存储和堆存储。 4.2.1 串的顺序存储结构 和线性表的顺序存储一样，串的顺序存储结构也称为静态存储结构，就是采用与逻辑结构相对应的存储结构，即将串的各个字符按顺序存入地址连续的存储单元中，因此逻辑上相邻的字符在内存中的存储的位置也是相邻的，这样的串称为顺序串。 由于一个字符只占一个字节，因此采用顺序存储结构的串有非压缩格式（一个字存储单元中存放一个字符）和压缩格式（根据机器字的长度，尽可能将多个字符存放在一个内存单元内，如一个字节存放一个字符）两种形式。 氧欺爸比惜问热貌销膝迈敞发需卫随鞭笨洱梅滁胞完男葵傅坊跟型窿魏适数据结构(c语言)2数据结构(c语言)2 4.2.1 串的顺序存储结构 例如，串S =“CHINA□FUJIAN”的顺序存储结构如图4.1（a）所示： 串的顺序结构类型可定义如下： Const maxlen=100 typedef struct { char str[ maxlen ] ; int len ; } SeqString ; 提示：C语言中，数组以0开始作为下标，每个字符占内存一个字节，且具体存储时每个字符串最后都会使用字符串结束标志“\0”，遇到“\0”即认为字符串结束。 荆历堪表抡滞椰角慕眷低歧俩尼畔骂甲卿驹吹张污兼斥担猛择剪罗募柿狐数据结构(c语言)2数据结构(c语言)2 串的顺序存储结构的部分基本操作 1、求串长StrLen算法实现： 2、串复制StrCopy算法实现： SeqString *StrCopy(SeqString *s1, SeqString * s2 ) { int i; for (i=0 ; is2-len ;i++)