数据结构——第4章串(C#)

《数据结构——第4章串(C#)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串4.1串的基本概念4.1.1什么是串串（或字符串）是由零个或多个字符组成的有限序列。记作str="a1a2…an"（n≥0），其中str是串名，用双引号括起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一个任意字符（字母、数字或其他字符），它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。一个串中任意连续的字符组成的子序列称为该串的子串，例如，"a"、"ab"、"abc"和"abcd"等都是"abcde"的子串。包含子串的串相应地称为主串。若两个串的长度相等且对应字符都相等，则称两个

2、串是相等的。当两个串不相等时，可按“字典顺序”区分大小。【例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。4.1.2串的抽象

3、数据类型ADTString{数据对象：D={ai

4、1≤i≤n,n≥0,ai为char类型}数据关系：R={r}r={

5、ai,ai+1∈D,i=1,…,n-1}基本运算：voidStrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。voidStrCopy(t)：串复制，由串t复制产生一个串。intStrLength()：求串长，返回当前串中字符个数。StringConcat(t)：串连接，返回一个当前串和串t连接后的结果。StringSubStr(i,j)：求子串，返回当前串中从第i个字符

6、开始的j个连续字符组成的子串。StringInsStr(i,s)：串插入，返回串s插入到当前串的第i个位置后的子串。StringDelStr(i,j)：串删除，返回当前串中删去从第i个字符开始的j个字符后的结果。StringRepStr(i,j,s)：串替换，返回用串s替换当前串中第i个字符开始的j个字符后的结果。DispStr()：串输出，输出当前串的所有元素值。}4.2串的存储结构4.2.1串的顺序存储结构－顺序串和顺序表一样，用一个data数组（大小为MaxSize）和一个整型变量length来表示一个顺序串，length表示data数

7、组中实际字符的个数。定义顺序串类SqStringClass如下：classSqStringClass{constintMaxSize=100;publicchar[]data;//存放串中字符publicintlength;//存放串长publicSqStringClass()//构造函数,用于顺序串的初始化{data=newchar[MaxSize];length=0;}//顺序串的基本运算}下面讨论在顺序串上实现串基本运算的算法。（1）建立串StrAssign(cstr)由一个字符串常量cstr建立一个串，即生成一个其值等于cstr的串。

8、对应的算法如下：publicvoidStrAssign(stringcstr){inti;for(i=0;i

9、}（3）求串长度StrLength()返回当前串中的字符个数。对应的算法如下：publicintStrLength(){returnlength;}（4）串连接Concat(t)将当前串和串t的所有字符连接在一起形成的新串，并返回这个新串。对应的算法如下：publicSqStringClassConcat(SqStringClasst){SqStringClassnstr=newSqStringClass();//新建一个空串inti;nstr.length=length+t.length;for(i=0;i

10、串data[0..str.length-1]到nstrnstr.data[i]=data[i];for(i=0;i