计算机数据结构第四章串.pptVIP

第 4 章　串 4.1 串类型的定义 4.2 串的表示和实现 4.3 模式匹配算法 4.4 串操作应用举例 4.1 串类型的定义 1、名词术语 串（String)(或字符串），是由零个或多个字符组成的有限序列。一般记做s=‘a1a2…an’(n=0) 串的长度，串中字符的数目n。 空串（Null string),零个字符的串，它的长度为零。 子串，串中任意个连续的字符组成的子序列称为该串的子串。 主串，包含子串的串。 位置,字符在序列中的序号为该字符在串中的位置. 例:4个串 a=BEI,b=JING, c=BEIJING,d=BEI JING 2、串的抽象数据类型定义 ADT String{数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n, n≥0} 数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,...,n} 基本操作：??????StrAssign(T,chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串T。 StrCompare(S,T) 初始条件：串S和串T存在。??操作结果：若ST,则返回值0;若S=T,则返回值=0;若ST,则返回值0。 StrLength(S) 初始条件：串S存在。 操作结果：返回值S的元素个数，称为串的长度。 Concat（T，S1，S2） 初始条件：串S1和S2存在。 操作结果：用T返回S1和S2联接成的新串。 SubString(Sub,S,pos,len) 初始条件：串S存在，1≤pos≤StrLength(S)且0≤ len ≤StrLength(S)-pos+1 。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 …… } ADT String 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 块链存储表示 4.2.1 定长顺序存储表示 思想:?用一组地址连续的存储单元存储串值的字符序列 #define MAXSTRLEN 255//用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度 串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称为“截断”。 基本运算实现 1.串联接Concat（T，S1，S2） 算法实现 Status Concat(SString T,SString S1,SString S2){ if (S1[0]+S2[0]=MAXSTRLEN){ // 未截断 T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]]; T[0]=S1[0]+S2[0]; uncut =TRUE;} else if(S1[0]MAXSTRLEN){ // 截断 T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; T[0]= MAXSTRLEN; uncut =FALSE;} else{ // 截断(仅取S1) T[0 ..MAXSTRLEN]= S1[0 ..MAXSTRLEN]; uncut =FALSE;} return uncut;} 2.求子串SubString(Sub,S,pos,len) 初始条件：串S存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1 。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 算法思想：求子串的过程即为复制字符序列的过程，将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。 算法实现 Status SubString(SString Sub,SString S,int pos,int len) { if(pos1 || posS[0] || len0 || lenS[0]-pos+1) return ERROR; Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; return OK; } 定长顺序存储结构总结 1.采用此存储结构，实现串操作的原操作为“字符序列的复制”；操作的时间复杂度基于复制的字符序列的长度 2.如果在操作中出现串值序列的长度超过上界MAXSTRLEN时,约定用截尾法处理.克服这点惟有不限定串的最大长度,即动态分配串值的存储空间 4