数据结构c语言版第4章ppt课件.ppt

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

1、串主要内容：1串的类型定义2串的表示和实现定长顺序存储表示堆分配存储表示串的块链存储表示3串的模式匹配算法串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”，其中S是串名，双引号括起来的字符序列是串值；ai(1≤i≤n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString)，它不包含任何字符。1串类型的定义一、串的基本概念注意：空串和空格串不同，如“”和“”分别表示长度为1的空格串和长度为0的空串（○）。特别地，空串是任意串的子串，任意串是其自身的子串。串中任意个

2、连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时，该子串的首字符在主串中对应的序号，定义为子串在主串中的位置（或序号）。例如：A=“Thisisastring”，B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，B在A中的位置为3。二、串的抽象数据类型定义如下：ADTString{数据对象：D＝{ai

3、ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{

4、ai-1,ai∈D,i=2,...,n}基本操作：}ADTS

5、tring基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars的值赋给T。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回true，否则返回false。StrLength(S)初始条件：串S存在。操作结果：返回S的长度。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0

6、；若ST，则返回值0。例如：StrCompare(data,state)StrCompare(cat,case)>0<0Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：Concate(T,man,kind)求得T=mankindSubString(&Sub,S,pos,len)初始条件：操作结果：用Sub返回串S的第pos个字符起长度为len的子串。串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。例如：S

7、ubString(sub,commander,4,3)求得sub=man;SubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串1≤pos≤StrLength(S)，0≤len≤StrLength(S)-pos+1。Index(S,T,pos)初始条件：串

8、S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设S=abcaabcaaabc,T=bcaIndex(S,T,1)=2;Index(S,T,3)=？;Index(S,T,8)=？;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。60bcabcaReplace(&S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。例如

9、：假设S=abcaabcaaabca,T=bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=abcabcaabcbcabcabca不重叠：假设S=abcabcabcab,T=abcabV=x,则经置换后得到S=xcxabcababcababcabStrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=

10、characterStrDelete(&S,pos,len)初始条件：串S存在1≤pos≤