河池学院：《数据结构》课程电子教案（PPT教学课件）第4章 串

第4章串 4.1串的基本概念 4.2 串的存储结构 提纲 4.3Java中的字符串 CONTENTS 4.4 串的模式匹配 作业 上机实验题 1/62

CONTENTS 提纲 1/62

串是由零个或多个字符组成的有限序列。记作str="a1a2.an"（n≥0）。 串中所包含的字符个数n称为串长度，当n=0时，称为空串。 一个串中任意连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。 若两个串的长度相等且对应字符都相等，则称两个串相等。 2/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

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

串的实现方式 线性表 顺序表 链表 串 顺序串 链串 逻辑结构 存储结构 映射 ∩ 5/62

和顺序表一样，用一个data数组和一个整型变量size来表示一个顺 序串，size表示data数组中实际字符的个数。 为了简单，data数组采用固定容量为MaxSize（可以模仿顺序表改 为动态容量方式）。 6/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

串对象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

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