数据结构 第4章 串和数组课件.ppt

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

1、数据结构与算法第五讲：串和数组内容提要串数组29/07/20212古人玩字符串的本领思妻诗(宋李禺)枯眼望遥山隔水，往来曾几见心知；壶空怕酌一杯酒，笔下难成和韵诗。逢路隔人离别久，讯音无雁寄回迟；孤灯夜守长宁寂，夫忆妻兮父忆儿。思夫诗(宋李禺)儿忆父兮妻忆夫，寂寥长守夜灯孤。迟回寄雁无音讯，久别离人阳路途。诗韵和成难下笔，酒杯一酌怕空壶。知心几见曾往来，水隔山遥望眼枯。29/07/20213串的定义串（string）是由零个或多个字符组成的有限序列，又称字符串。应用举例：29/07/20214字符串的几个概念字符串一般记为s=“

2、a1a2……an”(n≥0)，其中s是串的名称，双引号内是串的值，双引号本身不属于串的内容。ai(1≤i≤n)可以是字母、数字或其他字符，i就是该字符在串中的位置。n为串的长度。空串（nullstring）——零个字符的串。空格串——只包含空格的串（注意与空串的区别）。子串与主串——串中任意个数的连续字符组成的子序列成为该串的子串，相应地，包含子串的串成为主串。子串在主串中的位置就是子串的第一个字符在主串中的序号。Lover&overFriend&endBelieve&lie29/07/20215串的比较给定两个串：s=“a1a

3、2……an”，t=“b1b2……bm”当且仅当n==m，而且a1==b1,a2==b2,……an==bm时，我们认为s==t。当满足下列条件之一时，s

4、较，比如查字典。29/07/20216串的抽象数据类型ADT串(String)Data串中元素仅由一个字符组成，相邻元素具有前驱后继关系。OperationStrAssign(T,*chars)：生成一个值等于字符串常量chars的串T。StrCopy(T,S)：串S存在，由串S复制得串T。ClearString(S)：串S存在，将串清空。StringEmpty(S)：若串S为空，返回true，否则返回false。StrLength(S)：返回串S的元素个数，即串的长度。StrCompare(S,T)：若S>T，返回值>0，若S

5、=T，返回0，若S

6、S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(S,pos,T)：串S和T存在，1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。StrDelete(S,pos,len)：串S存在，1≤pos≤StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串。endADT29/07/20217由若干个基本操作实现Index操作/*T为非空串。若主串S中第pos个字符之后存在于T相等的子串，*//*则返回第一个这样的子串在S中的位置，

7、否则返回0*/intIndex(StringS,StringT,intpos){intn,m,i;Stringsub;if(pos>0){n=StrLength(S);/*得到主串S的长度*/m=StrLength(T);/*得到子串T的长度*/i=pos;while(i<=n-m+1){SubString(sub,S,i,m);/*取主串第i个位置长度与T相等的子串给sub*/if(StrCompare(sub,T)!=0)/*如果两串不相等*/++i;else/*如果两串相等*/returni;/*则返回i值*/}}retu

8、rn0;/*若无子串与T相等，返回0*/}friendendSTm=StrLength(T)n=StrLength(S)i=pos29/07/20218串的顺序存储结构——定长顺序存储f0r1i234下标：56end空闲空间串值，其长度为6两种表示方法以’