第4章串 4.1串的基本概念 4.2 串的存储结构 提纲 4.3Java中的字符串 CONTENTS 4.4 串的模式匹配 作业 上机实验题 1/62
CONTENTS 提纲 1/62
串的基本概念4.1什么是串4.1.1串是由零个或多个字符组成的有限序列。记作str="aia2an"（n≥0）。串中所包含的字符个数n称为串长度，当n=0时，称为空串。一个串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。若两个串的长度相等且对应字符都相等，则称两个串相等。2/62
串是由零个或多个字符组成的有限序列。记作str="a1a2.an"（n≥0）。 串中所包含的字符个数n称为串长度，当n=0时，称为空串。 一个串中任意连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。 若两个串的长度相等且对应字符都相等，则称两个串相等。 2/62
【例4.1】设s是一个长度为n的串，其中的字符各不相同，则s中的所有子串个数是多少？空串是其子串，计1个。每个字符构成的串是其子串，计n个。每2个连续的字符构成的串是其子串，计n-1个。子串个数每3个连续的字符构成的串是其子串，计n-2个。=1+n+(n-1)+...+2+1=n(n+1)/2+1每n-1个连续的字符构成的串是其子串，计2个。s是其自身的子串，计1个。例如，S="software"的子串个数=（8×9)/2+1=37。3/62
【例4.1】设s是一个长度为n的串，其中的字符各不相同，则s中的所有子 串个数是多少？ 空串是其子串，计1个。 每个字符构成的串是其子串，计n个。 每2个连续的字符构成的串是其子串，计n-1个。 每3个连续的字符构成的串是其子串，计n-2个。 . 每n-1个连续的字符构成的串是其子串，计2个。 s是其自身的子串，计1个。 例如，s="software"的子串个数=(8×9)/2+1=37。 子串个数 =1+n+(n-1)+.+2+1 =n(n+1)/2+1 3/62
串的抽象数据类型4.1.2ADT String1数据对象：D={a0≤i≤n-1，n≥0，a为char类型}数据关系：R=(r}r=[<ai, ai+1> I ai, ai+1ED, i=0, .", n-2]基本运算：void StrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。chargeti（inti）：返回序号i的字符。void seti(inti，charx)：设置序号i的字符为x。StringStrcopy()：串复制，返回由当前串复制产生一个串。intsize()：求串长，返回当前串中字符个数StringConcat（t)：串连接，返回一个当前串和串t连接后的结果StringSubstr（i，j)：求子串，返回从第i个字符开始的j个连续字符组成的子串。StringInsstr(i，t)：串插入，返回串t插入到当前串的第个位置后的子串。StringDelstr(i，j)：串删除，返回串中删去从第i个字符开始的j个字符后的结果。StringRepstr（i，j，t）：串替换，返回用t替换第i个字符开始的个字符后的结果。StringtoString（)：将串转换为字符串。4/62
ADT String { 数据对象： D={ai | 0≤i≤n-1，n≥0，ai为char类型} 数据关系： R={r} r={<ai，ai+1> | ai，ai+1∈D， i=0，.，n-2} 基本运算： void StrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。 char geti(int i)：返回序号i的字符。 void seti(int i，char x)：设置序号i的字符为x。 String StrCopy()：串复制，返回由当前串复制产生一个串。 int size()：求串长，返回当前串中字符个数。 String Concat(t)：串连接，返回一个当前串和串t连接后的结果。 String SubStr(i，j)：求子串，返回从第i个字符开始的j个连续字符组成的子串。 String InsStr(i，t)：串插入，返回串t插入到当前串的第i个位置后的子串。 String DelStr(i，j)：串删除，返回串中删去从第i个字符开始的j个字符后的结果。 String RepStr(i，j，t)：串替换，返回用t替换第i个字符开始的j个字符后的结果。 String toString()：将串转换为字符串。 } 4/62
串的存储结构4.2串的实现方式逻辑结构U串线性表映射链表顺序串链串顺序表存储结构5/62
串的实现方式 线性表 顺序表 链表 串 顺序串 链串 逻辑结构 存储结构 映射 ∩ 5/62