chap4弟四章串.ppt

第 四 章 串 4. 1 串的基本概念 4.2 串存储和实现 4.3 串的模式匹配算法 * 结束 第 * 页 * 学习要点1 了解串的基本操作，了解利用这些基本操作实现串的其它操作的方法；2 掌握在串的堆分配存储结构下，串的基本操作算法；3 掌握在串的模式匹配算法； 串也叫字符串，它是由零个或多个字符组成的的字符序列。 基本内容1 串的有关概念 串的基本操作2 串的定长顺序存储结构，堆分配存储结构；3 串的基本操作算法；4 串的模式匹配算法； 第四章 串 4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 一、串的定义1 什么是串 串是一种特殊的线性表，它是由零个或多个字符组成的有限序列， 一般记作 s = ‘a1,a2, a3, ... an’ 其中 s----串名， a1,a2, a3, ... an----串值 串的应用非常广泛，许多高级语言中都把串的作为基本数据类型。在事务处理程序中，顾客的姓名、地址货物的名称、产地可作为字符串处理，文本文件中的每一行字符等也可作为字符串处理。 下面是一些串的例子：（1）a = ‘ LIMING’（2）b = ‘ PEJING UNIUERCITY’（3）c = ‘ DATA STRUCTURE’（4）d = ‘’（5）e = ‘ ’说明： 1) 串中包含的字符个数，称为串的长度。 长度为0的串称为空串，它不包括任何字符，上面（4）中的串d是空串,，(5)中的e 是包含一个空格符的空格串；2）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。 2 串的有关术语 1）子串 串中任意个连续的字符组成的子序列称为该串的子串 例：c = ‘ DATA STRUCTURE’，f=‘DATA’ f是c的子串 2）子串的位置 子串T 在主串S中的位置是指主串S中第一个与T相同的子串的首字母 在主串中的位置。 例：S=‘ababcabcac’ , T=‘abc’ 子串T 在主串S中的位置为3 3）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都 相同； 3 串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。 1）串赋值操作StrAssign( T, chars)  功能：将串常量char的值赋给串变量T； 2）复制串操作 StrCopy(T,S) 功能：由串变量S复制得到串变量T； 3）判空操作 StrEmpty(S) 功能：若为空串，则返回TRUE，否则返回FALSE 4） 串比较操作 StrCompare( S, T) 功能若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0 5）串置空操作 ClearString( S) 功能：将S清为空串 6） 求串长操作 StrLenght( S) 功能：略; 7） 串连接操作 Concat( T, S1, S2) 功能：由S1和S2连接组成的新串，用T返回新串；8） 求子串操作SubString( Sub, S, pos, len) 功能：用Sub返回串S的第pos个字符起长度len 为子串；9） 求子串位置操作Index( S, T, pos )  功能：返回S中第pos个字符之后与T相同的子串的位置，若不存在返回0 10) 串插入操作 StrInsert( S, pos , T) 功能：将串T插入到串S的第pos字符之前 11）串删除操作 StrDelete( S, pos , len) 功能：从串S中删除第pos个字符起长度len 为子串 一、串的存储（三种） 1 定长顺序存储结构 定长顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下： #define MAXSTRLEN 255 Typedef unsigned char SString[MAXSTRLEN+1] 2、堆分配存储 堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间是在程序执行过程中动态分配的。 在C语言中，存在一个称之为“堆”的自由存储区，并由C