数据结构串学习.pptx

《数据结构串学习.pptx》由会员分享，可在线阅读，更多相关《数据结构串学习.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 4.1 4.1 串类型的定义串类型的定义4.1.1 4.1.1 串的定义 串串(String)(String)是零个或多个字符组成的有限序是零个或多个字符组成的有限序列。一般记作列。一般记作S=S=a a1 1a a2 2a a3 3a an n，其中，其中S S是串名，是串名，单引号单引号括起来的字符序列是串值；括起来的字符序列是串值；a ai i(1in)(1in)可以是字母、数字或其它字符；串中所包含的字可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。符个数称为该串的长度。长度为零的串称为空串长度为零的串称为空串(Empty String)(Empty String)，

2、它，它不包含任何字符，用不包含任何字符，用表示。通常将仅由一个表示。通常将仅由一个或多个空格组成的串称为空白串或多个空格组成的串称为空白串(Blank String)(Blank String)，如，如 表示长度为表示长度为1 1的空白串。的空白串。第1页/共31页 串中任意个连续字符组成的子序列称为该串的串中任意个连续字符组成的子序列称为该串的子串子串，包含子串的串相应地称为，包含子串的串相应地称为主串主串。通常将子串。通常将子串在主串中首次出现时的该子串的首字符对应的主串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为中的序号，定义为子串在主串中的序号子串在主串中的序号（或位置

3、）。（或位置）。例如，设例如，设A A和和B B分别为分别为 A=A=This is a stringThis is a string B=B=isis 则则B B是是A A的子串，的子串，A A为主串。为主串。B B在在A A中出现了两中出现了两次，其中首次出现所对应的主串位置是次，其中首次出现所对应的主串位置是3 3。因此，。因此，称称B B在在A A中的序号（或位置）为中的序号（或位置）为3 3特别地，空串是任意串的子串，任意串是其自身的子串。特别地，空串是任意串的子串，任意串是其自身的子串。第2页/共31页4.1.2 4.1.2 串的抽象数据类型定义串的抽象数据类型定义具体见课本具体见

4、课本 P71P71基本操作函数基本操作函数n串赋值：串赋值：StrAssign(S,T)StrAssign(S,T)n串复制：串复制：Strcopy(S,T)Strcopy(S,T)n求串长：求串长：StrLength(S)StrLength(S)n串联接：串联接：Concat(&T,S1,S2)Concat(&T,S1,S2)n求子串：求子串：SubString(&S,start,length,len)SubString(&S,start,length,len)n子串定位：子串定位：Index(S,T,POS)Index(S,T,POS)n置换：置换：Replace(&S,T,V)Repla

5、ce(&S,T,V)n插入子串：插入子串：StrInsert(&S,S,T)StrInsert(&S,S,T)n删除子串：删除子串：StrDeleteStrDelete(&(&S,pos,lengthS,pos,length)第3页/共31页4.1.3 4.1.3 串的基本操作串的基本操作定义下列几个变量：定义下列几个变量：char s120=dirtreeformat,s220=file.mem;char s330,*p;int result;例如：例如：printf(%d,strlen(s1);/输出输出13(1)求串长求串长(length)int strlen(char s);/求串的长

6、度求串的长度第4页/共31页例如：例如：strcpy(s3,s1);/s3=dirtreeformatchar*strcpy（char to，char from）;该函数将串该函数将串from复制到串复制到串to中，并且返回一个中，并且返回一个指向串指向串to的开始处的指针。的开始处的指针。（2）串复制）串复制(copy)第5页/共31页(3)联接联接(concatenation)char strcat（char to，char from）该函数将串该函数将串from复制到串复制到串to的末尾，并且返回的末尾，并且返回一个指向串一个指向串to的开始处的指针。的开始处的指针。例如：例如：strc

7、at(s3,/)strcat(s3,s2);/s3=dirtreeformat/file.mem第6页/共31页(4)串比较（串比较（compare)int strcmp(chars1,char s2);该函数比较串该函数比较串s1和串和串s2的大小，的大小，当返回值小于当返回值小于0，表示，表示s1s2例如：例如：result1=strcmp(baker,Baker)/result10 result2=strcmp(12,12);/result2=0 result3=strcmp(Joe,Joseph);/result30第7页/共31页（5）字符定位）字符定位(index)char str

8、chr（char s，char c）;该函数是找该函数是找c在字符串中第一次出现的位置，若在字符串中第一次出现的位置，若找到则返回该位置，否则返回找到则返回该位置，否则返回NULL。例如：例如：p=strchr(s2,.);/p 指向指向file之后的位之后的位置置 if(p)strcpy(p,.cpp);/s2=file.cpp第8页/共31页 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制

9、到串SUB中。void substr(string sub,string s,int pos,int len)if(posstrlen(s)|lenstrlen(s)-pos+1)return ERROR;strncpy(sub,&spos,len);return OK;第9页/共31页在主串在主串S S中取从第中取从第i(ii(i的初值为的初值为pos)pos)个字符起、长度和个字符起、长度和串串T T相等的子串和相等的子串和T T比较，若相等，则求得函数值为比较，若相等，则求得函数值为i i，否则值增否则值增1 1直至直至S S中不存在和串中不存在和串T T相等的子串为止。相等的子串为止。

10、例例2 2、串的定位、串的定位index(S,T,pos)index(S,T,pos)int index(string s,string T,int pos)if(pos0)n=strlen(s);m=strlen(t);i=pos;while(i=n-m+1)substr(sub,s,i,m);if(strcmp(sub,T)!=0)+i;else return(i);/while /if return(0);/index第10页/共31页4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示4.2 4.2 串的表示和实现串的表示和实现 定长顺序存储表示定长顺序存储表示,也称为静态存储分配

11、的也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串顺应表。它是用一组连续的存储单元来存放串中的字符序列。中的字符序列。在串的定长顺序存储结构中，按照预定义在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长的大小，为每个定义的串变量分配一个固定长度的存储区，具体描述如下：度的存储区，具体描述如下：#define MAXSTRLEN 255 /用户可定义串长的最大值typedef unsigned char SStringMAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度 第11页/共31页 一般还可使用一个不会出现在串中的特殊一般还可使用一个不

12、会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，字符在串值的尾部来表示串的结束。例如，C C语言中以字符语言中以字符00表示串值的终结。此时，表示串值的终结。此时，串长是一个隐含值，有时不方便进行某些串操串长是一个隐含值，有时不方便进行某些串操作。作。因此在上述定义中，串空间最大值因此在上述定义中，串空间最大值maxstrlenmaxstrlen为为255255，但最多只能存放，但最多只能存放254254个字符个字符的原因，因为必须留一个字节来存放的原因，因为必须留一个字节来存放00字符。若不设终结符，可用一个整数来表示串字符。若不设终结符，可用一个整数来表示串的长度，的长度，那么该长

13、度减那么该长度减1 1的位置就是串值的最的位置就是串值的最后一个字符的位置后一个字符的位置(在在C C语言中语言中)。第12页/共31页例例1 1、串连接、串连接Concat(&TConcat(&T，S1S1，S2)S2)假设假设S1S1、S2S2和和T T都是都是SstringSstring型的串变量，且串型的串变量，且串T T是是由由S1S1联结串联结串S2S2得到的。即串得到的。即串T T的值的前段和串的值的前段和串S1S1的值的值相等，串相等，串T T的值后段和串的值后段和串S2S2的值相等，则只要进行相的值相等，则只要进行相应的应的“串值复制串值复制”操作，但需要对于超长部分实施操作

14、，但需要对于超长部分实施“截断截断”操作。操作。串串T T的值可能出现的三种情况：的值可能出现的三种情况：1.1.S10+S20S10+S20 maxstrlenmaxstrlen，得到正确结果；，得到正确结果；2.2.S10 maxstrlenS10S10+S20 maxstrlenmaxstrlen，串，串T T包含串包含串S1S1和串和串S2S2的一个子串；的一个子串；3.3.S10=maxstrlenS10=maxstrlen，串，串T=T=串串S1S1；第13页/共31页Status Concat(Sstring&T,Sstring S1,Sstring S2)Status Conc

15、at(Sstring&T,Sstring S1,Sstring S2)if(S10+S20=maxstrlen)if(S10+S20=maxstrlen)/情况1未截断 T 1.S10 =S1 1.S10;T 1.S10 =S1 1.S10;T S10+1.S10+S20=S2 1.S20;T S10+1.S10+S20=S2 1.S20;T0=S10+S20;uncut=True;T0=S10+S20;uncut=True;else if(S10 maxstrlen)else if(S10 maxstrlen)/情况2截断：取s1+s2前面子串 T 1.S10 =S1 1.S10;T 1.S

16、10 =S1 1.S10;T S10+1.maxstrlen =S2 1.maxstrlen-T S10+1.maxstrlen =S2 1.maxstrlen-S10;S10;T0=maxstrlen;uncut=False;T0=maxstrlen;uncut=False;else else/情况3截断：仅取串s1 T 0.maxstrlen =S1 0.maxstrlen;T 0.maxstrlen =S1 0.maxstrlen;uncut=False;uncut=False;return uncut;return uncut;/Concat /Concat第14页/共31页例例2 2

17、、求子串、求子串SubString(&Sub,S,pos,len)SubString(&Sub,S,pos,len)void Substring(sstring&Sub,sstring S,int pos,int len)if(posstrlen(s)-1|len0)error(parameter error)Sub1.len=Spos.pos+lin-1;Sub0=len;return ok;/strncpy(sub,&spos,len);求子串的过程即为复制字符序列的过程，将串求子串的过程即为复制字符序列的过程，将串S S中中从第从第pospos个字符开始长度为个字符开始长度为lenlen

18、的字符复制到串的字符复制到串SubSub中。中。第15页/共31页4.2.2 4.2.2 堆分配存储表示堆分配存储表示 这种存储表示的特点是，仍以一组地址连续的这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。存储分配的顺序表。typedef struct char *ch;/若非空串若非空串,按串长分配空间按串长分配空间;否则否则 ch=NULL int length;/串的长度；串的长度；HString;利用

19、函数利用函数malloc()malloc()为每个新产生的串分配一块为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。具体描述个指向起始地址的指针，作为串的基址。具体描述如下：如下：第16页/共31页 以上这种存储结构表示时的串操作仍是基以上这种存储结构表示时的串操作仍是基于于“字符序列的复制字符序列的复制”进行的。进行的。例如，串复制操作例如，串复制操作StrCopyStrCopy（&T,S&T,S）的实现）的实现算法是，若串算法是，若串T T已存在，则先释放串已存在，则先释放串T T所占空间，

20、所占空间，当串当串S S不空时，首先为串不空时，首先为串T T分配大小和串分配大小和串S S长度相长度相等的存储空间，然后将串等的存储空间，然后将串S S的值复制到串的值复制到串T T中；中；又如串插入操作又如串插入操作StrInsertStrInsert（&S,pos,T&S,pos,T）的实现）的实现算法是，利用算法是，利用reallocrealloc函数为串函数为串S S重新分配大小重新分配大小等于串等于串S S和串和串T T长度之和的存储空间，然后进行长度之和的存储空间，然后进行串值复制，如算法串值复制，如算法4.44.4所示。所示。第17页/共31页算法4.4Status StrIn

21、sert(HString&S,int pos,HString T)/在串S的第pos个字符之前（包括尾部）插入串T if(posS.length+1)return ERROR;/pos不合法则出错 if(T.length)/只要串T不空，就需要重新分配S空间，以便插入T if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);for(i=S.length-1;i=pos-1;-i)/为插入T而腾出pos之后的位置 S.chi+T.length=S.chi;/从S的pos位置起全部字符均后移 S.c

22、hpos-1pos+T.length-2=T.ch0T.length-1;/插入T S.length+=T.length;/刷新S串长度return OK;/StrInsert第18页/共31页4.2.3 4.2.3 串的块链存储表串的块链存储表示示 顺序串上的插入和删除操作不方便，需要移动顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。值，串的这种链式存储结构简称为链串。typedef struct node char data;struct node*next;lstring

23、;一个链串由头指针唯一确定，这种结构便于进一个链串由头指针唯一确定，这种结构便于进行插入和删除运算，但存储空间利用率太低。行插入和删除运算，但存储空间利用率太低。第19页/共31页 在链式存储方式中，结点大小的选择和顺序存在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着储方式的格式选择一样都很重要，它直接影响着串处理的效率。这就要求我们考虑串值的存储密串处理的效率。这就要求我们考虑串值的存储密度。度。存储密度存储密度=串值所占的存储位串值所占的存储位/实际分配的存储位实际分配的存储位 存储密度小，运算处理方便，但存储占用量大。存储密度小，运算处理方便，但存储占

24、用量大。串值的链式存储结构对某些串操作，如联接操串值的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的来说不如另外两种作等有一定方便之处，但总的来说不如另外两种存储结构灵活。存储结构灵活。第20页/共31页讨论：法1 1存储密度为 ；法2 2存储密度为 ；显然，若数据元素很多，用法显然，若数据元素很多，用法2 2存储更优存储更优称为块链结构称为块链结构链式存储特点：用链表存储串值，易插入和删除。法1 1：链表结点（数据域）大小取1 1法2 2：链表结点（数据域）大小取n(n(例如n=4)n=4)1/21/29/15=3/59/15=3/5 A B C I NULLheadheadA

25、 B C D E F G H I#NULL第21页/共31页 为了提高存储密度，可使每个结点存放多个字为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为符。通常将结点数据域存放的字符个数定义为结点结点的大小的大小，显然，当结点大小大于，显然，当结点大小大于1 1时，串的长度不时，串的长度不一定正好是结点的整数倍，因此要用特殊字符一定正好是结点的整数倍，因此要用特殊字符(如如“#”)来填充最后一个结点，以表示串的终结。对来填充最后一个结点，以表示串的终结。对于结点大小不为于结点大小不为1 1的链串，其类型定义如下：的链串，其类型定义如下：#define CHUNKS

26、IZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct Chunk *head,*tail;/串的头和尾指针串的头和尾指针 int curlen;/串的当前长度串的当前长度 LString;第22页/共31页 *4.3 串的模式匹配算法 子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，

27、解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：S=s0s1s2sn-1 T=t0t1tm-1 串的匹配实际上是对于合法的位置0in-m依次将目标串中的子串si.i+m-1和模式串t0.m-1进行比较，若si.i+m-1=t0.m-1，第23页/共31页则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若si.i+m-1 t0.m-1，则称从位置i开始的匹配失败。上述的位置i又称为位移，当si.i+m-1=t0.m-1时，i称为有效位移；当si.i+m-1 t0.m-1时，i称为无效位移。这样，串

28、匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0in-m)是否为有效位移，第24页/共31页其算法段为：for(i=0;i=n-m;i+)if(Si.i+m-1=T0.m-1 return i;下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。int index(sstring s,sstring t,int pos)int i,j,k;int m=s.length;int n=t.length;for(i=0;i=n-m;i+)j=0;k=i;第25页/共31页 while(jdata=p-data)q=q-next;p=p-next;else shift=shift-next;q=shift;p=t;第28页/共31页 if(p=null)return shift;else return null;第29页/共31页第30页/共31页感谢您的观看。第31页/共31页