第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=[ 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∈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
4.2.1串的顺序存储结构-顺序串和顺序表一样，用一个data数组和一个整型变量size来表示一个顺序串，size表示data数组中实际字符的个数。为了简单，data数组采用固定容量为MaxSize（可以模仿顺序表改为动态容量方式）。6/62
和顺序表一样，用一个data数组和一个整型变量size来表示一个顺 序串，size表示data数组中实际字符的个数。 为了简单，data数组采用固定容量为MaxSize（可以模仿顺序表改 为动态容量方式）。 6/62
顺序串类Sgstringclass//顺序串类publicclass Sqstringclassfinal int Maxsize=100;//存放串中字符char [] data;int size;//串中字符个数//构造方法public Sqstringclass()data=new char[Maxsize];size=o;/串的基本运算算法7/62
顺序串类SqStringClass public class SqStringClass //顺序串类 { final int MaxSize=100; char [] data; //存放串中字符 int size; //串中字符个数 public SqStringClass() //构造方法 { data=new char[MaxSize]; size=0; } //串的基本运算算法 } 7/62
顺序串上的基本运算算法设计与顺序表类似，仅以求子串为例说明8/62
顺序串上的基本运算算法设计与顺序表类似，仅以求子串为例说明。 8/62
求子串：对于一个顺序串求序号开始长度为的子串。sizedata串对象5：t=s.Substr(2,4)串对象t：datasize9/62
串对象t： 串对象s： data a b c d 1 2 . 7 t=s.SubStr(2,4) data size d 1 2 . 4 size 3 c 求子串：对于一个顺序串求序号i开始长度为j的子串。 9/62
实现：先创建一个空串s，当参数正确时，s子串的字符序列为data[i..i+j-1],共个字符，当i和i+j-1不在有效序序号0～size-1范围内时，则参数错误，此时返回空串。1/求子串publicSqstringclassSubstr(inti,int j)1/新建一个空串Sqstringclass s=new Sqstringclass();if (i=size Il jsize)//参数不正确时返回空串return s;//将data[i..i+j-1]-sfor(int k=i;k<=i+j;k++)s.data[k-i]=data[k];s.size=j;//返回新建的顺序串return s;大10/62
public SqStringClass SubStr(int i,int j) //求子串 { SqStringClass s=new SqStringClass(); //新建一个空串 if (i=size || jsize) return s; //参数不正确时返回空串 for (int k=i;k<=i+j;k++) //将data[i.i+j-1]→s s.data[k-i]=data[k]; s.size=j; return s; //返回新建的顺序串 } 实现：先创建一个空串s，当参数正确时，s子串的字符序列为data[i.i+j-1]， 共j个字符，当i和i+j-1不在有效序序号0～size-1范围内时，则参数错误，此 时返回空串。 10/62