第4章串 4.1串的基本概念 411什么是串 串(或字符串)是由零个或多个字符组成的有限序列。 记作sr="a12…,an"(心0),其中str是串名,用双引号括 起来的字符序列为串值,引号是界限符,1(1≤in)是一 个任意字符(字母、数字或其他字符),它称为串的元素 是构成串的基本单位,串中所包含的字符个数n称为串的长 度,当n=0时,称为空串
第4章 串 4.1 串的基本概念 4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an "（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的长 度，当n=0时，称为空串
个串中任意连续的字符组成的子序列称为该串的子 串,例如,"a"、"ab"、"mbc'和"abcd"等都是" abcde"的子 串。包含子串的串相应地称为主串。 若两个串的长度相等且对应字符都相等,则称两个 串是相等的。当两个串不相等时,可按“字典顺序”区 分大小
一个串中任意连续的字符组成的子序列称为该串的子 串，例如，"a" 、 "ab" 、 "abc"和"abcd"等都是"abcde"的子 串。包含子串的串相应地称为主串。 若两个串的长度相等且对应字符都相等，则称两个 串是相等的。当两个串不相等时，可按“字典顺序”区 分大小
【例4.1】设str是一个长度为n的串,其中的字符各不相 同,则str中的所有子串个数是多少? 解:对于这样的串str,有: 空串是其子串,计1个 每个字符构成的串是其子串,计n个 每2个连续的字符构成的串是其子串,计n-1个 每3个连续的字符构成的串是其子串,计m2个 每n-1个连续的字符构成的串是其子串,计2个 str是其自身的子串,计1个 所有子串个数=1+n+(n-1)++2+1=n(+1)2+1。例如, str="! software"的子串个数=(8×9)/2+1=37
【例4.1】 设str是一个长度为n的串，其中的字符各不相 同，则str中的所有子串个数是多少？ 解：对于这样的串str，有： 空串是其子串，计1个 每个字符构成的串是其子串，计n个 每2个连续的字符构成的串是其子串，计n-1个 每3个连续的字符构成的串是其子串，计n-2个 … 每n-1个连续的字符构成的串是其子串，计2个 str是其自身的子串，计1个 所有子串个数=1+n+(n-1)+…+2+1=n(n+1)/2+1。例如， str="software"的子串个数=(8×9)/2+1=37
412串的抽象数据类型 ADT String 数据对象 D={a11si≤n,n≥0,a为char类型} 数据关系: R={r}r={a;a>|apa+1∈D,i=1,…,n-1} 基本运算 void StrAssign(cstr)):由字符串常量cst创建一个串,即生成其值等于 的串。 void StrCopy(t):串复制,由串复制产生一个串 int StrEngth:求串长,返回当前串中字符个数 String Concat(t)):串连接,返回一个当前串和串接后的结果 String substr(ij):求子串,返回当前串中从第个字符开始的个连续字 符组成的子串。 String lns str(i,s):串插入,返回串插入到当前串的第个位置后的子串 String destr(j):串删除,返回当前串中删去从第个字符开始的个字 符后的结果。 String repstr(ij,s):串替换,返回用串s替换当前串中第个字符开始的 个字符后的结果。 DispStrO:串输出,输出当前串的所有元素值
4.1.2 串的抽象数据类型 ADT String { 数据对象： D={ai | 1≤i≤n,n≥0,ai为char类型} 数据关系： R={r} r={ | ai ,ai+1∈D, i=1,…,n-1} 基本运算： void StrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于 cstr的串。 void StrCopy(t)：串复制，由串t复制产生一个串。 int StrLength()：求串长，返回当前串中字符个数。 String Concat(t)：串连接，返回一个当前串和串t连接后的结果。 String SubStr(i,j)：求子串，返回当前串中从第i个字符开始的j个连续字 符组成的子串。 String InsStr(i,s)：串插入，返回串s插入到当前串的第i个位置后的子串。 String DelStr(i,j)：串删除，返回当前串中删去从第i个字符开始的j个字 符后的结果。 String RepStr(i,j,s)：串替换，返回用串s替换当前串中第i个字符开始的j 个字符后的结果。 DispStr()：串输出，输出当前串的所有元素值。 }
4.2串的存储结构 421串的顺序存储结构-顺序串 和顺序表一样,用一个data数组(大小为 MaxSize)和 一个整型变量 length来表示一个顺序串, length表示data数 组中实际字符的个数。 定义顺序串类 Sqstring class如下: class sqstring class const int MaxSize=100; public charl data 存放串中字符 public int length; /1放串长 public Astring class /构造函数用于顺序串的初始化 data=new char MaxSize length=0 顺序串的基本运算
4.2 串的存储结构 4.2.1 串的顺序存储结构－顺序串 和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下： class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
下面讨论在顺序串上实现串基本运算的算法。 (1)建立串 StrAssign(cr) 白一个字符串常量cstr建立一个串,即生成一个其值等 于cstr的串。对应的算法如下: public void StrAssign(string cstr int i; for(i=0; i<cstr Length; i++) datai=cstr; length=i;
下面讨论在顺序串上实现串基本运算的算法。 （1）建立串StrAssign(cstr) 由一个字符串常量cstr建立一个串，即生成一个其值等 于cstr的串。对应的算法如下： public void StrAssign(string cstr) { int i; for (i=0;i<cstr.Length;i++) data[i]=cstr[i]; length=i; }
例如,cstr=“ abcdef”,执行 Strassign(cstr)方法的结果 如下图所示。 abcdef s.StrAssign(cstr) 串对象:[-6 data length
例如，cstr=“abcdef”，执行StrAssign(cstr)方法的结果 如下图所示。 cstr： 串对象 s： abcdef a b c d e f … 6 s.StrAssign(cstr) data length
(2)串复制 StrCopy(t) 将申复制给当前串对象。对应的算法如下: public void StrCopy(sqString Class t) int i; for (i=0; i<tlength; i++) data lt data; length=t length;
（2）串复制StrCopy(t) 将串t复制给当前串对象。对应的算法如下： public void StrCopy(SqStringClass t) { int i; for (i=0;i<t.length;i++) data[i]=t.data[i]; length=t.length; }
(3)求串长度 Strength 返回当前串中的字符个数。对应的算法如下: public int Strength return length;
（3）求串长度StrLength() 返回当前串中的字符个数。对应的算法如下： public int StrLength() { return length; }
(4)串连接 Concat(t) 将当前串和申t的所有字符连接在一起形成的新串,并返 回这个新串。对应的算法如下: public sqstring class Concat(sqstring Class t) AsTring Class nstr= new SqString Class;/新建一个空串 int i. nstr length=length+t ength: for(i=0;i< length;i计+)∥将当前串data0. str length-1到nsr nstr.dataiFdata; for(i=0; i<t length; i++)//t data O.t. length-1-nstr nstrdata length+i=tdata; return nstr; 返回新串nstr
（4）串连接Concat(t) 将当前串和串t的所有字符连接在一起形成的新串，并返 回这个新串。对应的算法如下： public SqStringClass Concat(SqStringClass t) { SqStringClass nstr=new SqStringClass(); //新建一个空串 int i; nstr.length=length+t.length; for (i=0;i<length;i++)//将当前串data[0..str.length-1]到nstr nstr.data[i]=data[i]; for (i=0;i<t.length;i++)//将t.data[0..t.length-1]nstr nstr.data[length+i]=t.data[i]; return nstr; //返回新串nstr }