数据结构课件5.pptVIP

begin i:=i+1;  j:=j+1;  end else {若当前位置上的字符不相同， 则指针i, j后退，重新开始匹配} begin i:=i-j+2;  j:=1;  end; {若j已到t的串尾，则匹配成功，返回子串位置，否则返回0} if j t.curlen then position:=i-t.curlen else position:=0;  end;  图 5.9 模式匹配过程 5. 替换操作 替换操作可将源串s中某一特定子串用另外一个串替换。要成功实现替换操作，必须首先查找t在s中的位置。这可通过以上模式匹配函数实现。若匹配成功，下一步则是进行替换。替换可通过在s中先删除子串t，然后再插入串s来实现。  设源串s: strtp已在外部说明， 被要求替换的串为t: strtp， 替换串为r: strtp，则替换操作过程如下：  procedure replace(t, r : strtp);  功能： 在串s中用子串r替换子串t。 处理过程：  (1) 查找子串t在s中的位置。  (2) 在s中删除子串t。  (3) 在s中原来t的位置上插入子串r。  程序清单如下：  procedure replace(t, r : strtp); {在源串s中， 用串r替换子串t} var pos: integer;  begin {调用模式匹配函数求子串t的位置} pos:= position(t); {若匹配失败则显示出错信息} if pos = 0 then showmessage(’can not find substring’) else  begin delete(pos, t.curlen); {删除子串t} insert(pos-1, r); {插入串r， 完成替换} end;  end; 5.4 串的ADT定义及类定义 5.4.1 串的ADT定义 根据面向对象程序设计的原则，实现部分与接口部分两者应该分离。 接口部分可以用ADT定义即抽象数据类型定义来进行描述。一种数据类型的ADT定义由数据元素、结构及操作三部分组成。以下是串的ADT定义：  元素： ai同属于字符类型，i=1, 2, …, n n≥0。  结构： 元素间呈线性关系。 操作：常用的串的基本操作有以下几种：  (1) create(s, ss)： 初始化操作。 建立一个串s， 其值为字符序列ss。 (2) equal(s, t)： 判等函数。 若s和t相等， 则返回true， 否则返回false。  (3) length(s)： 求长函数。 其函数值为s中字符的个数。  (4)substring(s, start, len)：求子串操作。若 1≤start≤length(s)+1且 0≤len≤length(s)-start+1,则返回函数值为串s中第start个字符起， 长度为len的字符序列；否则返回一个特殊的串常量。 (5) delete(s, pos, len)： 删除操作。 当 1≤pos≤length(s)且0≤len≤length(s)-pos+1 时, 从串s中删去第pos个字符起长度为len的子串。  (6) insert(s, pos, t): 插入操作。当 1≤pos≤length(s) +1 时, 在串s的第pos个字符之前插入串t。  (7) position(s, t)： 定位函数。若在主串s中存在和t相等的子串，则返回s中第一个这样的子串在主串s中的位置， 否则函数值为 0。  (8