数据结构的第四讲课件.ppt

《数据结构的第四讲课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四讲字符串、String类和StringBuilder类引言字符串对大多数计算机程序而言是很普遍的。像文字处理软件和网页应用程序这些程序类型都广泛采用了字符串。这使得处理这类应用程序的程序员在字符串处理的效率问题上需要花费额外的心思。本讲主要介绍C#语言处理字符串的方法，分析如何使用String类，如何使用StringBuilder类。2主要内容3.1串类型的定义3.2串的物理结构3.3串的算法3.4STRING类的应用3.5STRINGBUILDER类3.6STRING类和STRINGBUILDER类性能

2、比较3.1串类型的定义串的定义串是字符线性的一个有限序列。记作：A="a1a2...an"其中：A是串名，引号括起来的部分为串的值，ai(1≤i≤n)为任一字符，它称为串的元素，n为串的长度，且n≥0。5串的一些概念若n=0，则此串称为空串，记作：A=“”。若A=“”，则称为空白串，其元素为空格符，常用Φ表示。串的长度一般应有一定的限制。（如不超过255）6串的一些概念串中任意连续的若干字符组成的子序列称为该串的子串。包含子串的串又称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称为子串在主串中的位

3、置。7串的抽象数据类型定义ADTString{数据对象：D={ai

4、ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1={

5、ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串T。StrCompare(S,T)初始条件：串S和串T存在。操作结果：若S>T,则返回值>0;若S=T,则返回值=0;若S

6、(S)初始条件：串S存在。操作结果：返回值S的元素个数，称为串的长度。Concat（&T，S1，S2）初始条件：串S1和S2存在。操作结果：用T返回S1和S2联接成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。}ADTString9串的运算对于串的运算来说，一般都是对多个元素构成的串操作，当然也有对一个元素操作的退化情况。求串长

7、——len(s)功能：求串s中字符的个数。如：s=“program”则：len(s)=710串的运算联接串——concat(s,t)功能：将串t联接到串s的未尾形成新串s。如：s=“re”,t=“store”则：concat(s,t)后得到s=“restore”求子串——substr(s,i,j,t)功能：从串s中的第i个字符开始，连续取出j个字符（元素），构成一个新串t。如：s=“store”则：substr(s,2,3,t)后得到t=“tor”11串的运算置换子串——replace(s,i,j,t)功能：

8、将串s从第i个字符开始的连续j个字符（元素）构成的串取出，换成另一个串t。如：s=“store”,t=“patu”则：replace(s,2,3,t)后得到s=“spatue”可以看出，被置换串与置换串长度不一定一致12串的运算插入子串——insert(s,i,t)功能：在串s中的第i个字符之前，插入子串t。如：s=“store”,t=“patu”则：insert(s,3,t)后得到s=“stpatuore”删除子串——delete(s,i,j)功能：删除串s中第i个字符开始的连续j个字符（元素）构成的串。如

9、：s=“store”则：delete(s,2,3)后得到s=“se”13串的运算复制串——assign(s,t)功能：将串t复制给串s。如：t=“store”则：assign(s,t)后得到s=“store”14串既然串的逻辑结构与线性表一致，那么它的物理结构就可以沿用线性表的物理结构，即可以用顺序结构与链式结构来表示，当然串还有其自身的特性，所以又有与线性表不同的物理结构──等量分块结构。153.2串的物理结构顺序结构在顺序存贮结构中，一个串分配一块连续的存贮区。其特点是：１、对一个串的操作运算比较灵活，串

10、与串之间是相互独立的；２、每个串所分配的空间大小不太好掌握，太大造成浪费，太小造成串存贮不下；３、一篇文章的多个串存贮区域分散，不易进行统一操作运算。17链式结构在链式结构中，每个串中的元素为一个基本单位。其特点是：1、不需考虑串需要的存贮空间；2、对串的操作运算比较灵活；3、串占用的存贮空间太大；4、串的元素存贮区域分散，不易统一操作。18等量分块结构这种结构兼有顺序结构与链式结构的特点，是它们的