文档介绍：第四章串
串类型的定义
串的表示和实现
1 定长顺序存储表示
2 堆分配存储表示
3 串的块链存储表示
串的模式匹配算法
串操作应用举例
一、串和基本概念
串类型的定义
1、串(String)
串是零个或多个字符组成的有限序列。一般记作S= ’a1a2a3…an’,其中S 是串名,单引号括起来的字符序列是串值;ai(1≦i≦n)可以是字母、数字或其它字符;串中所包含的字符个数称为该串的长度。
长度为零的串称为空串(NULL String),它不包含任何字符。
注意:空串和空白串的不同,例如‘’和‘’分别表示长度为1的空白串和长度为0的空串。
通常将仅由一个或多个空格组成的串称为空白串(Blank String)。
串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。
一、串和基本概念
通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号,定义为子串在主串中的序号(或位置)。
例如,设a、b、c、d为如下的四个串:
a=‘BEI’, b=‘JING’, c=‘BEIJING’, d=‘BEI JING’
则它们的长度分别为3、4、7、8;并且a和b都是c和d的子串,a在c和d中的位置都是1,而b在 c的位置是4,在d中的位置则是5。
特别地,空串是任意串的子串,任意串是其自身的子串。
当且仅当两个串的值相等,称两个串是相等。也就是说,只有两个串的长度相等,并且各对应位置的字符都相等时才相等。例如上例中的串a、b、c和d彼此都不是相等。
一、串和基本概念
串值必须用一对单引号扩起来但单引号本身不属于串,它的作用只是为了避免于变量名或数的常量混淆而已。
通常在程序中使用的串可分为两种:串变量和串常量。串常量和整常数、实常数一样,在程序中只能被引用但不能不能改变其值,即只能读不能写。
通常串常量是由直接量来表示的,例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名,以使程序易读、易写。如C++中,可定义
const char path[]=“dir/bin/appl”;
const char path[]=“dir/bin/appl”;
这里path是一个串常量,对它只能读不能写。串变量和其它类型的变量一样,其取值是可以改变的。
一、串和基本概念
串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。然而,串的基本操作和线性表有很大差别。
在线性表中的基本操作中,大多数以“单个元素”作为操作对象。例如在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等;
而在串的基本操作中,通常以“串的整体”作为操作对象,例如在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。
ADT String {
D={ ai |ai∈CharacterSet,i=1,2,...,n, ≥0 }
数据关系:
R1={ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }
二、串的抽象数据定义
基本操作:
StrAssign (&T, chars)//串赋值
初始条件:chars 是字符串常量。
操作结果:把 chars 赋为 T 的值。
StrCopy (&T, S)//串复制
初始条件:串 S 存在。
操作结果:由串S复制到串T。
数据对象:
pare (S, T)//串比较
初始条件:串 S 和 T 存在。
操作结果:若S T,则返回值 0;
若S T,则返回值 0;
若S T,则返回值 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 的子串。
DestroyString (&S)
初始条件:串 S 存在。
操作结果:串 S 被销毁。
二、串的抽象数据定义
StrEmpty (S)
初始条件:串S存在。
操作结果:若 S 为空串,则返回 true,否则返回 false。
ClearString (&S)
初