第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> | 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; } //顺序串的基本运算 }