北京邮电大学自动化学院：《数据结构》第四章 串

第四章串 41串类型的定义 42串的表示和实现 1定长顺序存储表示 2堆分配存储表示 ●3串的块链存储表示 43串的模式匹配算法 44串操作应用举例 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第四章 串 ⚫4.1 串类型的定义 ⚫4.2 串的表示和实现 ⚫ 1 定长顺序存储表示 ⚫ 2 堆分配存储表示 ⚫ 3 串的块链存储表示 ⚫4.3 串的模式匹配算法 ⚫4.4 串操作应用举例

4.1串类型的定义 、串和基本概念 1、串( String) ●串是零个或多个字符组成的有限序列。一般记作 S='a1a2a3an’,其中S是串名,单引号括起来的字符序列 是串值;a(1i≤n)可以是字母、数字或其它字符;串中所包 含的字符个数称为该串的长度。 长度为零的串称为空串 NULL String),它不包含任何字符 通常将仅由一个或多个空格组成的串称为空白串(B|ank String) 注意:空串和空白串的不同,例如,和‘分别表示长度 为1的空白串和长度为0的空串。 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 一、串和基本概念 4.1 串类型的定义 ⚫ 1、串(String) ⚫ 串是零个或多个字符组成的有限序列。一般记作 S= ’a1a2a3…an ’，其中S 是串名，单引号括起来的字符序列 是串值；ai (1≦i≦n)可以是字母、数字或其它字符；串中所包 含的字符个数称为该串的长度。 ⚫ 长度为零的串称为空串(NULL String)，它不包含任何字符。 ⚫ 注意：空串和空白串的不同，例如‘ ’和‘’分别表示长度 为1的空白串和长度为0的空串。 ⚫ 通常将仅由一个或多个空格组成的串称为空白串(Blank String)

串和基本概念 串中任意个连续字符组成的子序列称为该串的子串,包含子串 的串相应地称为主串。 ●通常将子串在主串中首次出现时的该子串的首字符对应的主 串中的序号,定义为子串在主串中的序号(或位置)。 例如,设a、b、c、d为如下的四个串: ●a=BEP,b=fJNG’,c= BEJJING’,d=‘BE|JNG ●则它们的长度分别为3、4、7、8;并且a和b都是c和d的子 串,a在c和d中的位置都是1,而b在c的位置是4,在d中的 位置则是5 特别地,空串是任意串的子串,任意串是其自身的子串。 北京邮电大学自动化学院

北京邮电大学自动化学院 3 ⚫ 串中任意个连续字符组成的子序列称为该串的子串，包含子串 的串相应地称为主串。 一、串和基本概念 ⚫ 通常将子串在主串中首次出现时的该子串的首字符对应的主 串中的序号，定义为子串在主串中的序号（或位置）。 ⚫ 例如，设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彼此都不是相等。 串值必须用一对单引号扩起来但单引号本身不属于串,它的 作用只是为了避免于变量名或数的常量混淆而已 ●通常在程序中使用的串可分为两种:串变量和串常量。串常 量和整常数、实常数一样,在程序中只能被引用但不能不能 改变其值,即只能读不能写 ●通常串常量是由直接量来表示的,例如语句 Eror(“ overflow)中“ overflow"是直接量。但有的语言允 许对串常量命名,以使程序易读、易写。如C++中,可定义 ● const char path=“dir/bin/appl”; 北京邮电大学自动化学院

北京邮电大学自动化学院 4 ⚫ 当且仅当两个串的值相等，称两个串是相等。也就是说，只 有两个串的长度相等，并且各对应位置的字符都相等时才相 等。例如上例中的串a、b、c和d彼此都不是相等。 一、串和基本概念 ⚫ 串值必须用一对单引号扩起来但单引号本身不属于串，它的 作用只是为了避免于变量名或数的常量混淆而已。 ⚫ 通常在程序中使用的串可分为两种：串变量和串常量。串常 量和整常数、实常数一样，在程序中只能被引用但不能不能 改变其值，即只能读不能写。 ⚫ 通常串常量是由直接量来表示的，例如语句 Error(“overflow”)中“overflow”是直接量。但有的语言允 许对串常量命名，以使程序易读、易写。如C++中，可定义 ⚫ const char path[]=“dir/bin/appl”;

串和基本概念 o const char path="dir/bin/appl 这里path是一个串常量,对它只能读不能写。串变量和其它 类型的变量一样,其取值是可以改变的。 串的逻辑结构和线性表极为相似,区别仅在于串的数据对象 约束为字符集。然而,串的基本操作和线性表有很大差别。 在线性表中的基本操作中,大多数以“单个元素”作为操作 对象。例如在线性表中査找某个元素、求取某个元素、在某 个位置上插入一个元素和删除一个元素等; 而在串的基本操作中,通常以“串的整体”作为操作对象, 例如在串中查找某个子串、求取一个子串、在串的某个位置 上插入一个子串以及删除一个子串等。 北京邮电大学自动化学院

北京邮电大学自动化学院 5 ⚫ const char path[]=“dir/bin/appl”; ⚫ 这里path是一个串常量，对它只能读不能写。串变量和其它 类型的变量一样，其取值是可以改变的。 一、串和基本概念 ⚫ 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象 约束为字符集。然而，串的基本操作和线性表有很大差别。 ⚫ 在线性表中的基本操作中，大多数以“单个元素”作为操作 对象。例如在线性表中查找某个元素、求取某个元素、在某 个位置上插入一个元素和删除一个元素等； ⚫ 而在串的基本操作中，通常以“串的整体”作为操作对象， 例如在串中查找某个子串、求取一个子串、在串的某个位置 上插入一个子串以及删除一个子串等

二、串的抽象数据定义 · ADT String{ 数据对象:D={a1|an∈ Character Set. jE=1,2,,n,20} 数据关系:R={|a1,a1∈D,i=2,,ny 基本操作:· StrAssign(&T, chars∥串赋值 初始条件: chars是字符串常量。 ●操作结果:把 chars赋为T的值。 StrCopy(&T,S川∥串复制 初始条件:串S存在。 ●操作结果:由串S复制到串T。 北京邮电大学自动化学院

北京邮电大学自动化学院 6 ⚫ ADT String { D＝{ ai |ai∈CharacterSet,i=1,2,...,n, ≥0 } ⚫ 数据关系： R1＝{ | ai-1 , ai ∈D, i=2,...,n } 二、串的抽象数据定义 ⚫ 基本操作: ⚫ StrAssign (&T, chars)//串赋值 ⚫ 初始条件：chars 是字符串常量。 ⚫ 操作结果：把 chars 赋为 T 的值。 ⚫ StrCopy (&T, S)//串复制 ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：由串S复制到串T。 ⚫ 数据对象：

、串的抽象数据定义 StrCompare(s,T)∥串比较 ●初始条件:串S和T存在。 操作结果:若S>T,则返回值>0; ●若S=T,则返回值=0; 若S<T,则返回值<0。 StrEngth(S)∥求串长 初始条件:串S存在 ●操作结果:返回S的元素个数,称为串的长度。 北京邮电大学自动化学院

北京邮电大学自动化学院 7 ⚫ StrCompare (S, T)//串比较 ⚫初始条件：串 S 和 T 存在。 ⚫ 操作结果：若S  T，则返回值  0； ⚫ 若S = T，则返回值 = 0； ⚫ 若S  T，则返回值  0。 二、串的抽象数据定义 ⚫ StrLength (S) //求串长 ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：返回 S 的元素个数， 称为串的长度

、串的抽象数据定义 Concat(&T,S1S2)∥串连接 ●初始条件:串S1和S2存在 操作结果:用T返回由S1和S2联接而成的新串。 SubString(&Sub, S, pos, len) 初始条件:串S存在,1pos≤ StrEngth(S),且 0sen≤ StrEngth(S)-pos+1。 ●操作结果:用Sub返回串S的第pos个字符起长度 为len的子串。 北京邮电大学自动化学院

北京邮电大学自动化学院 8 ⚫ 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 的子串

、串的抽象数据定义 ● Destroy String(8S) StrEmpty(s) ●初始条件:串S存在。 初始条件:串S存在。 ●操作结果:串S被销毁。 操作结果:若S为空串,则返 回true,否则返回fase e Clear String(&S) ●初始条件:串S存在。 ●操作结果:将S清为空串。 .3ADT String 北京邮电大学自动化学院

北京邮电大学自动化学院 9 ⚫ DestroyString (&S) ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：串 S 被销毁。 二、串的抽象数据定义 ⚫ StrEmpty (S) ⚫ 初始条件：串S存在。 ⚫ 操作结果：若 S 为空串,则返 回 true,否则返回 false。 ⚫ ClearString (&S) ⚫ 初始条件：串S存在。 ⚫ 操作结果：将S清为空串。 ⚫ } ADT String

三、串的基本操作 ●在上述抽象数据类型定义的13种操作中, 求串长 StrEngth 串赋值 StrAssign、 °串联接 Concat ●串比较 StrCompare、 求子串 SubString 等五种操作构成串类型的最小操作子集。即:这些操作不可 能利用其他串操作来实现,反之,其他串操作(除串清除 ClearString和串销毁 Destroy String外)可在这个最小操作 子集上实现。 北京邮电大学自动化学院 10

北京邮电大学自动化学院 10 ⚫ 在上述抽象数据类型定义的13种操作中， 三、串的基本操作 ⚫ 串赋值StrAssign、 ⚫ 串比较StrCompare、 ⚫ 求串长StrLength、 ⚫ 串联接Concat ⚫ 求子串SubString ⚫ 等五种操作构成串类型的最小操作子集。即：这些操作不可 能利用其他串操作来实现，反之，其他串操作（除串清除 ClearString和串销毁DestroyString外）可在这个最小操作 子集上实现