数据结构的第四讲.ppt
《数据结构的第四讲.ppt》由会员分享,可在线阅读,更多相关《数据结构的第四讲.ppt(83页珍藏版)》请在三一办公上搜索。
1、第四讲字符串、String类和 StringBuilder类,引言,字符串对大多数计算机程序而言是很普遍的。像文字处理软件和网页应用程序这些程序类型都广泛采用了字符串。这使得处理这类应用程序的程序员在字符串处理的效率问题上需要花费额外的心思。本讲主要介绍 C#语言处理字符串的方法,分析如何使用 String类,如何使用 StringBuilder类。,2,主要内容,3.1 串类型的定义3.2 串的物理结构 3.3 串的算法3.4 STRING类的应用 3.5 STRINGBUILDER类3.6 STRING类和STRINGBUILDER类性能比较,3.1 串类型的定义,串的定义,串是字符线性的
2、一个有限序列。记作:A=a1a2.an其中:A是串名,引号括起来的部分为串的值,ai(1in)为任一字符,它称为串的元素,n为串的长度,且n0。,5,串的一些概念,若n=0,则此串称为空串,记作:A=“”。若A=“”,则称为空白串,其元素为空格符,常用表示。串的长度一般应有一定的限制。(如不超过 255),6,串的一些概念,串中任意连续的若干字符组成的子序列称为该串的子串。包含子串的串又称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称为子串在主串中的位置。,7,串的抽象数据类型定义,ADT String数据对象:D=ai|aiCharacterSet,i=1,2,.,n,n0数据关
3、系:R1=|ai-1,aiD,i=2,.,n基本操作:StrAssign(若ST,则返回值0。,8,串的抽象数据类型定义,StrLength(S)初始条件:串S存在。操作结果:返回值S的元素个数,称为串的长度。Concat(&T,S1,S2)初始条件:串S1和S2存在。操作结果:用T返回S1和S2联接成的新串。SubString(&Sub,S,pos,len)初始条件:串S存在,1posStrLength(S)且0 len StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为 len的子串。ADT String,9,串的运算,对于串的运算来说,一般都是对多个
4、元素构成的串操作,当然也有对一个元素操作的退化情况。求串长 len(s)功能:求串 s 中字符的个数。如:s=“program”则:len(s)=7,10,串的运算,联接串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)功能
5、:将串 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 个字符(元素)构成的串。如:s=“store”则:delete(s,2,
6、3)后得到 s=“se”,13,串的运算,复制串assign(s,t)功能:将串 t 复制给串 s。如:t=“store”则:assign(s,t)后得到 s=“store”,14,串,既然串的逻辑结构与线性表一致,那么它的物理结构就可以沿用线性表的物理结构,即可以用顺序结构与链式结构来表示,当然串还有其自身的特性,所以又有与线性表不同的物理结构 等量分块结构。,15,3.2 串的物理结构,顺序结构,在顺序存贮结构中,一个串分配一块连续的存贮区。其特点是:、对一个串的操作运算比较灵活,串与串之间是相互独立的;、每个串所分配的空间大小不太好掌握,太大造成浪费,太小造成串存贮不下;、一篇文章的多个
7、串存贮区域分散,不易进行统一操作运算。,17,链式结构,在链式结构中,每个串中的元素为一个基本单位。其特点是:1、不需考虑串需要的存贮空间;2、对串的操作运算比较灵活;3、串占用的存贮空间太大;4、串的元素存贮区域分散,不易统一操作。,18,等量分块结构,这种结构兼有顺序结构与链式结构的特点,是它们的折中方案。一、等量分块的存贮结构,19,其中每个块的大小一样,一个块可存放六个字符,最后两个域分别为标志域表示该等量块的结束,链域指向该块字符的后续字符块。在一块中,若字符未占满,则填上空白符。,等量分块结构,二、等量分块的特点在每一块中字符是连续存贮的,在块与块之间,字符是链式存贮的,所以它有以
8、下特点:、查询串中子串比较方便 对于查询若已知子串首字符的位置,则可根据位置计算它出所在块,便可查询到此子串了。,20,等量分块结构,二、等量分块的特点2、删除运算容易实现 若删除整块,则只需改变块与块之间的链指针即可。若删除非整块,则可将其中需删除的部分字符赋予。如:在串 S=abcdefghijklmnopq 中删除 efghijklm,21,a b c d,等量分块结构,22,二、等量分块的特点、插入运算比较简单 若插入点在块之间,则只需改变链指针。若插入点在块中,则先将含插入点的块,从插入点开始分成两块,然后再用块间插入方法。如:在串 S=abcdefghij 的 e 之前插入串 lm
9、nop,等量分块结构,23,二、等量分块的特点、插入运算比较简单 如:在串 S=abcdefghij 的 e 之前插入串 lmnop,e f,等量分块结构,三、等量分块的结构定义 typedef struct node char s6;char d;struct node*link;CAKE;,24,串和线性表,25,串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。在线性表的基本操作中,大多以“单个元素”作为操作对象;在串的基本操作中,通常以“串的整体”作为操作对象。,3.3 串的算法,顺序结构的算法,27,一、求串长Len(s)/*求串s中
10、除结束符外的字符个数*/char s;int i=0;while(s i!=0);,+,-,return(i);,顺序结构的算法,28,二、联接串void Concat(s,t)/*将t连接到s之后*/char s,t;int n,m,i;n=Len(s);m=Len(t);for(i=0;im;i+)sn+i=ti;sn+m=0;,顺序结构的算法,29,三、求子串 void Substr(s,i,j,t)/*从s的第i个字符(下标为i-1)开始*/char s,t;/*取j个字符,构成的新串送t中*/int i,j;/*若无 j 个字符则只取到串尾*/int k;for(k=0;k+),(k
11、j),tk=si-1+k;tk=0;,顺序结构的算法,30,四、置换子串假设:从 s 串的第 i 个字符(下标为i-1)开始,取出j个字符,用 t 串置换这 j 个字符。若 t 串长为 m,则有如下几种情况:1、mj(新串在原位放不下),需要从下标为 n-1 开始到 i+j-1 的字符向后移动 m-j 位,m-j,顺序结构的算法,31,四、置换子串假设:从 s 串的第 i 个字符(下标为i-1)开始,取出j个字符,用 t 串置换这 j 个字符。若 t 串长为 m,则有如下几种情况:,2、mj(新串在原位放下后还有空位),则需要下标从 i+j-1 开始到 n-1 的字符向前移动 j-m 位,j-
12、m,顺序结构的算法,32,四、置换子串假设:从 s 串的第 i 个字符(下标为i-1)开始,取出j个字符,用 t 串置换这 j 个字符。若 t 串长为 m,则有如下几种情况:,3、m=j新串正好放下,字符不需移位。然后将 t 串的字符依次复制到 s 串的预定字符位上。,顺序结构的算法,33,四、置换子串,void Replace(s,i,j,t)/*从s的第i个字符(下标为i-1)开始*/char s,t;/*取j个字符,置换成t串*/int i,j;int n,m,k;n=Len(s);m=Len(t);if(i+jj)/*若t串长大于j*/for(k=n-1;k=i+j-1;k-)sk+m
13、-j=sk;/*从i+j-1开始依次后移m-j位*/,顺序结构的算法,34,四、置换子串,else if(mj)/*若t串长小于j*/for(k=i+j-1;kn;k+)sk+m-j=sk;/*从i+j-1开始依次前移j-m位*/for(k=0;km;k+)sk+i-1=tk;/*置换进新串*/if(i+jn)sn+m-j=0;else si+m-1=0;,顺序结构的算法,35,五、插入子串假设:将串t插入到串s的第i个字符(下标为i-1)之前,若串t的长度为m,则需要从n-1到i-1的字符向后移动m位。即:,n+m-1,i+m-1,这时,sn-1移至下标为n+m-1,si-1移至下标为i+m
14、-1。,顺序结构的算法,36,五、插入子串假设:将串t插入到串s的第i个字符(下标为i-1)之前,若串t的长度为m,则需要从n-1到i-1的字符向后移动m位。即:,n+m-1,si-1 sn-1,t0,i+m-1,这时,sn-1移至下标为n+m-1,si-1移至下标为i+m-1。,然后,将t0复制到i-1,tm-1移至下标为i+m-2。,顺序结构的算法,37,五、插入子串,void Insert(s,i,t)/*将串t插入到串s的第i个字符前*/char s,t;int i;int n,m,k;n=Len(s);m=Len(t);for(k=n-1;k=i-1;k-)sk+m=sk;/*从i-
15、1开始以后的字符后移m位*/for(k=0;km;k+)sk+i-1=tk;sn+m=0;,顺序结构的算法,38,六、删除子串假设:删除串s中从第i个字符(下标为 i-1)开始的连续j个字符。即:,i+j-1,n-j-1,i-1,这时,si+j-1移至下标为i-1,sn-1移至下标为n-j-1。,顺序结构的算法,39,六、删除子串假设:删除串s中从第i个字符(下标为 i-1)开始的连续j个字符。即:,i+j-1,n-j-1,i-1,这时,si+j-1移至下标为i-1,sn-1移至下标为n-j-1。,si+j-1 sn-1,顺序结构的算法,40,六、删除子串,void Delete(s,i,j)
16、/*删除串s中从第i个字符(下标为 i-1)*/char s;int i,j;/*开始的连续j个字符*/int n,k;/*若无 j 个字符则只删到串尾*/n=Len(s);if(ni+j)si-1=0;/*若删除到串尾,则设定串未符*/else for(k=i+j-1;kn;k+)sk-j=sk;/*从i+j-1开始的字符前移j位*/sn-j=0;,链式结构的算法,41,一、串结点结构typedef struct point char ch;struct point*link;CNODE;,链式结构的算法,42,二、求串长Len(s)CNODE*s;/*s为表头指针*/CNODE*p;int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第四

链接地址:https://www.31ppt.com/p-6578901.html