资源描述：
《数据结构(C语言版) 课件第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章串课前导学4.1串类型的定义4.2串的表示和实现4.3**串的模式匹配算法4.4串操作应用举例4.4.1文本编辑4.4.2**建立词索引表学习目标了解串的相关概念。掌握串的3种机内表示方法和实现，即定长顺序存储、堆分配存储和块链存储。熟悉串的操作应用。4.1串类型的定义串（string，或称字符串）：是由零个或多个字符组成的有限序列。通常记作s=′a1a2a3…an′(n≥0)其中，S是串的名，用单引号括起来的字符序列是串的值。串中字符的数目n称为串的长度。含零个字符的串称为空串(nullstring)，它的长度为零。串的相关概念在各种应用中，空格通常是串的字
2、符集合中的一个元素，可以出现在其他字符之间。由一个或多个空格组成的串称为空格串(blankstring)，例如:′′和′′,它的长度为串中空格字符的个数。注意：空串和空格串的不同，例如′′和′′分别表示长度为1的空格串和长度为0的空串。串的相关概念子串：指串中任意个连续的字符组成的子序列。相应的包含子串的串称为主串。位置：对字符而言是指字符在串中的序号；对子串而言是指子串第一个字符在主串中的序号。相等：当且仅当两个串的值相等。即串长相等，且对应位置的字符相等。下面来看看对于串的抽象数据类型定义:串的抽象数据类型ADTString{数据对象：D＝{ai
3、ai∈Char
4、acterSet,i=1,2,...,n,n≥0}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)初始条件：chars是串常量。操作结果：赋于串T的值为chars。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。串的抽象数据类型DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：
6、若S>T，则返回值>0；若S=T，则返回值=0；若S0显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。串的抽象数据类型StrLength(S)初始条件：串S存在。操作结果：返回串S序列中的字符个数，即串的长度。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的
7、新串。“串联接”操作的结果是生成一个新的串，其值是“将第二的串的第一个字符紧接在第一个串的最后一个字符之后“得到的字符序列。如操作Concat(T,"man","kind")得到的结果是：T="mankind"。串的抽象数据类型SubString(&Sub,S,pos,len)初始条件：串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。“子串”指串中任意个连续的字符组成的子序列。如：操作SubString(Sub,“commander”,4,3)得到的结果
8、是Sub=“man”。显然必须在满足初始条件中规定的“起始位置”和“长度”之间的约束关系时才能求得一个合法的子串。允许len的下限为0是由于空串也是合法串，但实际上求长度为0的子串是没有意义的。串的抽象数据类型Index(S,T,pos)初始条件:串S和T存在,T是非空串，1≤pos≤StrLength(S)。操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。包含子串的串相应地称为主串。“子串在主串中的位置”指的是子串中的第1个字符在主串中的位序。如子串‘man’在主串‘commander’中的位置为4
9、。Index操作类似于线性表的Locate操作，在S中查询和T值相同的子串，pos为查询的起始位置。如：Index(‘Thisisapen’,‘is’,pos)，若pos=1，则查询得结果为3，若pos=4，则得结果为6，若pos=6，则得查询结果为0。串的抽象数据类型Replace(&S,T,V)初始条件：串S，T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。假设S=“abcacabcaca”，T=“abca”和V=“x”，则置换之后的S=“xcxca”。注意定义中“不重叠”三个字，若上例中的V=“ab”时，则置换后的结果应
