数据结构课件(串).ppt

《数据结构课件(串).ppt》由会员分享，可在线阅读，更多相关《数据结构课件(串).ppt（41页珍藏版）》请在三一办公上搜索。

1、数据结构第四章 串,2023/11/14,第四章 串,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,4.1 串的定义,是由零个或多个字符组成的有限序列，一般记为s=“a1a2an”(n0)其中，s是串名，用单引号（也可以是用双引号括起来的）括起来的字符序列是串的值

2、。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。注意区分空串与空格串的区别。,4.1 串的定义,串的逻辑结构和线性表的区别:,1.串的数据对象约束为字符集。2.线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。对于串可以定义以下运算：1.置串为一个空串；2.判断一个串是否为空串3.求一个串的长度；4.将两个串拼接在一起构成一个新串

3、；5.在一个串中，求从串的第i个字符开始连续j个字符所构成的子串；6.如果串S2是S1的子串，则可求串S2在串S1中第一次出现的位置。,4.1 串的定义,串的抽象数据类型的定义,ADT String 数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。Str

4、Empty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。,4.1 串的定义,串的抽象数据类型的定义,StrCompare(S,T)初始条件：串S和T存在。操作结果：若S T，则返回值 0；若S=T，则返回值=0；若S T，则返回值0。StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，1posStrLength(S)且0lenStrLength(S)

5、-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len 的子串。,4.1 串的定义,串的抽象数据类型的定义,Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。Replace(&S,T,V)初始条件：串S,T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前

6、插入串T。,4.1 串的定义,串的抽象数据类型的定义,StrDelete(&S,pos,len)初始条件：串S存在，1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。ADT String,4.1 串的定义,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求

7、子串SubString等六种操作构成串类型的最小操作子集。例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为：在主串S中取从第i(i的初值为pos)个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。,4.1 串的定义,int Index(String S,String T,int pos)/T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0if(pos 0)n=StrLength(S);m=StrLength(T);i=pos

8、;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/while/ifreturn 0;/S中不存在与T相等的子串/Index,4.2 串的表示和实现,串的顺序存储结构,PROGRAM PEX1;,存储密度=串值所占存储字节实际分配的存储字节,4.2 串的表示和实现,一、串的定长顺序存储表示,#define MAXSTRLEN 255/用户可在255以内定义最大串长typedef unsigned char SStringMAXSTRLEN+1;/0号单元存放串的长度串的实际长度可在这个予定义

9、长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。需预先定义一个串允许的最大字符个数浪费空间、插入删除操作不便,一、串的定长顺序存储表示,例如：串的联接算法中需分三种情况处理：,Status Concat(SString S1,SString S2,SString/Concat,4.2 串的表示和实现,二、串的堆分配存储表示（半动态存储结构）,typedef struct char*ch;/若是非空串,则按串长分配存储区,否则ch为NULLint length;/串长度 HString;通常，C语言中提供的串

10、类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。,二、串的堆分配存储表示,操作的实现,void StrAssign(HString/StrAssign,二、串的堆分配存储表示,操作的实现,int StrLength(Hstring S)/返回串S的长度return S.length;/StrLengthint StrCompare(HString S,HString T)/若ST,则返回值0;若S=T返回值=0，若ST返回值0;fo

11、r(i=0;iS.length,三、串的块链存储表示,三、串的块链存储表示,类C语言描述,#define CHUNKSIZE 80/可由用户定义的块大小typedef struct chunk/结点结构char chCUNKSIZE;struct Chunk*next;Chunk;typedef struct/串的链表结构Chunk*head,*tail;/串的头和尾指针int curlen;/串的当前长度 LString;,4.3 串的模式匹配算法,模式匹配,模式匹配：子串（又称模式串）在主串中的定位操作。这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。首

12、先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)初始条件：串S和T存在,T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,4.3 串的模式匹配算法,1.简单算法,设主串S=“ababcabcacbab”,模式串T=“abcac”。则普通算法的匹配过程如下：,4.3 串的模式匹配算法,1.简单算法,int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。其中，T非空，1posStr

13、Length(S)。i=pos;j=1;while(i T0)return i-T0;else return 0;/Index,4.3 串的模式匹配算法,2.首尾匹配算法,先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。abcba主串:a b a b c a b c a a a b c b a a b c 模式串:a a(2 次)a a a(1+2 次)a a a b b a(2+4 次)a a a a(2+2 次)a a(2次)a b c b a(5 次),上述两种算法的时间复杂度为O(mn),4.3 串的模式匹配算法,3、KMP(D.E.Kn

14、uth,V.R.Pratt,J.H.Morris)算法,设主串S=“ababcabcacbab”,模式串T=“abcac”。则普通算法的匹配过程如下：,改进后的匹配情况：,改进后的模式匹配算法,KMP算法,希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk 对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：t1 t2 tk-1=si-k+1 si-k+2 si-1(4.1)(4.1)式左边是t

15、k前面的k-1个字符，右边是si 前面的k-1个字符。,改进后的模式匹配算法,KMP算法,而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：t1 t2 tj-1=si-j+1 si-j+2 si-1(4.2)因为kj，所以有：tj-k+1 tj-k+2 tj-1=si-k+1 si-k+2 si-1(4.3)(4.3)式左边是 tj前面的k-1个字符，右边是si 前面的k-1个字符，通过(4.1)和(4.3)得到关系：t1 t2 tk-1=tj-k+1 tj-k+2 tj-1(4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符

16、与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。,改进后的模式匹配算法,（2）next函数,模式中的每一个tj都对应一个k值，由(4.4)式可知，这个k值仅依赖与模式t本身字符序列的构成，而与主串s无关。我们用nextj表示tj对应的k值，根据以上分析，next函数有如下性质：nextj是一个整数，且0nextjj为了使t的右移不丢失任何匹配成功的可能，当存在多个满足(4.4)式的k 值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个。如果在tj前不存在满足(4.4)式的子串，此时若t1tj，则k=1;若t

17、1=tj，则k=0;这时“滑动”的最远，为j-1个字符即用t1 和sj+1继续比较。,改进后的模式匹配算法,（2）next函数,next函数定义如下：,设有模式串：t=abaabcac，则它的next函数值为：,改进后的模式匹配算法,(3)KMP算法,在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中si=tj，则i和j分别增，若sitj 匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字

18、符比较相等，则i和j分别增继续进行匹配;另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增，表明从主串的下一个字符起和模式重新开始匹配。,改进后的模式匹配算法,(3)KMP算法,在假设已有next函数情况下，KMP算法如下：int StrIndex_KMP(char*s,char*t,int pos)/*从串s的第pos个字符开始找首次与串t相等的子串*/int i=pos,j=1,slen,tlen;while(it0)return i-t0;/*匹配成功，返回存储位置*/else return 1;/StrIndex_KMP,void get_next(SString

19、T,int*next)/算法4.7 int i=1;next1=0;int j=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;,Next函数的缺陷,根据前面定义的Next函数对模式串aaaab和主串aaabaaaab,改进后的模式匹配算法,（2）next函数,nextval函数定义如下：,设有模式串：t=abcaababc，则它的next函数值为：,第一趟第二趟第三趟第四趟,4.4 串应用文本编辑软件,文本编辑软件：,基本操作：串的输入、修改、删除（行或子串）、查找、输出；早期多采用静态存储结构，适应性差；现在多采用链式存储结构：按屏幕

20、宽度每个结点设计成存放80个字符;每行的结点（任意多个）构成一个结点链（块链）;头结点中存放行号和该行字符数;各行（任意多个）的头结点自上而下构成链。需要：页表、行表等,4.4 串应用文本编辑软件,链式存储结构：,4.4 串应用文本编辑软件,链式存储结构（类型定义）：,typedef struct nodechar data80;struct node*next;nodetype;typedef struct hnodeint num;int len;struct hnode*hnext;nodetype*next;headtype;,4.4 串应用文本编辑软件,代码段,main()float a,b,max;scanf(“%f,%f”,201,4.4 串应用文本编辑软件,行表和页表,分别设立页指针、行指针和字符指针分别指向当前操作的页、行和字符。,本章小结,1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆存储结构以及在其上实现串操作的基本方法。4.了解串操作的应用方法和特点。,Thank you!,