数据结构__4-5章.ppt

第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 4.1 串类型的定义 在计算机的应用中，非数值处理问题的应用越来越多。 如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。 4.1 串类型的定义 字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。 在线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，线性表和串的操作有很大的不同。 4.1 串类型的定义 串（或字符串）是由零个或多个字符组成的有限序列。一般记作： S=‘a1a2a3…an’，(n≥0) 其中： s为串名，用引号括起来的字符序列是串的值； ci(0≤i≤n-1)可以是字母、数字或其它字符，i为ci在串中的位置； 引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。 4.1 串类型的定义 零个字符的串称为空串，通常以两个相邻的引号来表示空串。如：s=‘’，它的长度为零； 仅由空格组成的的串称为空格串。如：s=‘ ’； 若串中含有空格，在计算串长时，空格应计入串的长度中。 如：s=‘I’m a student’的长度为13。 4.1 串类型的定义 当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。 串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。 例如，’com’、’om’、’a’和’man’都是’commander’的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串’man’在主串’commander’中的位置为4。 4.1 串类型的定义 特别地，空串是任意串的子串，任意串是其自身的子串。 通常在程序中使用的串可分为两种：串变量和串常量。 串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的。 如: const char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。 4.1 串类型的定义 串的抽象数据类型定义： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai ∈D, i=2,...,n } 4.1 串类型的定义 基本操作： StrAssign (*T, chars) 初始条件：chars 是字符串常量。 操作结果：把chars 赋为T 的值。 StrCopy (*T, S) 初始条件：串S 存在。 操作结果：由串S 复制得串T。 //注意：不能T＝S，只能通过函数来实现。 4.1 串类型的定义 StrLength (S) 初始条件：串S 存在。 操作结果：返回S 的元素个数，称为串的长度。 StrEmpty (S) 初始条件：串S 存在。 操作结果：若S 为空串，则返回TRUE，否则返回FALSE。 4.1 串类型的定义 StrCompare (S, T) 初始条件：串S 和T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S = T，则返回值= 0。 Concat (*T, S1, S2) 初始条件：串S1 和S2 存在。 操作结果：用T 返回由S1 和S2 联接而成的新串。 4.1 串类型的定义 SubString (*Sub, S, pos, len) 初始条件：串 S 存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 操作结果：用Sub 返回串S 的第pos 个字符起长度为len 的子串。 4.1 串类型的定义 Index (S, T, pos) 初始条件：串S 和T 存在，T 是非空串，1≤pos≤StrLength(S)。 操作结果：若主串S 中存在和串T 值相同的子串, 则返回它在主串S 中第pos 个字符之后第一次出现的位置; 否则函数值为0。 4.1 串类型的定义 Replace (*S,