数据结构第4章串.ppt

第 四 章 串 第 四 章 串 4. 1 串的基本概念 4. 1 串的基本概念 4. 1 串的基本概念 4. 1 串的基本概念 4. 1 串的基本概念 4.2 串存储和实现 4.2 串存储和实现 4.2 串存储和实现 4.3 串的基本运算实现 4.3 串存储和实现 4.3 串存储和实现 4.3 串存储和实现 4.4 串的模式匹配算法 4.4 串的模式匹配算法 4.4 串的模式匹配算法 第 * 页 * 学习要点1 了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法；2 掌握在串的堆分配存储结构下，串的基本操作算法；3 掌握在串的模式匹配算法； 串也叫字符串，它是由零个或多个字符组成的的字符序列。 基本内容1 串的有关概念 串的基本操作2 串的顺序存储结构，堆分配存储结构,链式存储结构；3 串的基本操作算法；4 串的模式匹配算法； 第四章 串 4.1 串的基本概念 4.2 串存储结构 4. 3 串的基本运算实现 4.3 串的匹配算法 1 什么是串 串是一种特殊的线性表，它是由零个或多个字符组成的有限序列， 一般记作 s = “a1,a2, a3, ... an” 其中 s----串名， a1,a2, a3, ... an----串值 串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。 下面是一些串的例子：（1）a = “This is a string” （2）b = “string” （3）c = “ “（4）d = “”（5）e = “你好” 说明： 串中包含的字符个数，称为串的长度。 长度为0的串称为空串，它不包括任何字符; 串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。 2 串的有关术语 1）子串 串中任意连续的字符组成的子序列称为该串的子串;例：c = “ DATA STRUCTURE”，f=“DATA” f是c的子串 2）子串的位置 子串t 在主串S中的位置是指主串s 中第一个与T相同的子串的首字母在主串中的位置; 例：s=“ababcabcac” , t=“abc” 子串T 在主串S中的位置为3 3）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同； 3 串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。 1）串赋值操作assign( s, t) 功能：将串t 的值赋给串变量s ； 2）串相等判断 equal(s,t) 函数 串的联接操作 concat( s , t ) 把串t 接在串 s 后面 求串长操作 lenght(s) 5) 求子串操作sub ( s, start, len, t) 若 0=startlength(s) 0=len=length(s)-start 则t 中值为从串s 的第start个字符, 起长度为len 的字符序列, 并且函数返回值为1, 否则为0； 6）求子串位置操作index( s, t )  功能：如果s中存在与 t 相同的子串, 则返回s中第1个这样的子串的位置，若不存在返回0 7） 替换操作 replace( s, t ,v ) 功能：由串v 替换串s 中出现的所有和 t 相同的不重叠子串；8）复制串操作 strcopy(s, t) 功能：由串变量 s 复制得到串变量 t ； 9）判空操作 empty( s ) 功能：若为空串，则返回1，否则返回0 10）串置空操作 ClearString( s ) 功能：将s 清为空串 11) 串插入操作 StrInsert( s, start , t) 功能：将串t 插入到串s 的第start 字符之前 12）串删除操作 StrDelete( s, start , len) 功能：从串s 中删除第 start 个字符起长度len 为的子串 1 顺序存储结构 顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下： #define MAX 255 char ch[MAX] 0 1 2 3 4