基本数据结构0904数据结构7串A

1、传智播客数据结构教程（7）,讲师：尹成QQ:77025077博客:,C/C+,算法+实战,传智播客,高薪就业,第2页,数据结构课程的内容,第3页,第4章串（String）,1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式,第4页,记为：s=“a1,a2,.,an”(n0),串中字符个数（n0）.n=0时称为空串。由一个或多个空格符组成的串。!=串s中任意个连续的字符序列叫s的子串;S叫主串。子串的第一个字符的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1串类型的定义,若干术语：串长：空

2、白串：子串：子串位置：字符位置：串相等：,隐含结束符0，即ASCII码NUL,第5页,练1：串是由字符组成的序列，一般记为。,练2：现有以下4个字符串：a=“show”,b=“me”,c=“showmoney”,d=“showmethemoney”,问：它们各自的长度？a是哪个串的子串？在主串中的位置是多少？,a=4，b=2，c=10，d=17,a是c和d的子串，在c和d中的位置都是1,练3：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符(空格键)的字符串.,0个或多个,S=“a1a2an”,练4：

3、空串是任意串的子串，任意串是其自身的子串!,第6页,ADTStingObjects:D=ai|aiCharacterSet,i=1,2,，n,n0Relations:R1=|ai-1,aiD,i=2,，n,串的抽象数据类型定义（参见教材P71）,functions:/有13种之多StrAssign(/StrLengthChar*strcpy(char*s1,constchar*s2);/StrCopyChar*strcat(char*s1,char*s2);/Concatintstrcmp(constchar*s1,constchar*s2);/StrCompare,第8页,串的其余操作可由这

4、些最小操作子集中的操作组合而成。例1、求子串定位函数Index（S，T，pos）子串定位的过程即为依次取主串中与该子串长度相同的子串进行比较的过程。voidIndex(string/Index,第9页,设s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”。求：,练习：,StrLength(s)StrLength(t)SubString(s,8,7)=SubString(t,2,1)=Index(s,A)=Index(s,t)=Replace(s,STUDENT,q)=,144“STUDENT”“O”30（s中没有t！）“IAMAWORKER”,再问：Concat(SubSt

5、ring(s,6,2),Concat(t,SubString(s,7,8)？,第10页,4.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示链式方式存储,首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,串有三种物理存储方法：,顺序存储,链式存储,第11页,定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,例如：#def

6、ineMaxstrlen255/用户可用的最大串长typedefunsignedcharSStringMaxstrlen+1;SStrings;/s是一个可容纳255个字符的顺序串。,注：一般用SString0来存放串长信息；C语言约定在串尾加结束符0，以利操作加速，但不计入串长；若字符串超过Maxstrlen则自动截断（因为静态数组存不进去）。,讨论：想存放超长字符串怎么办？静态数组有缺陷！,实现方式：参见教材P105编程例，两串连接和107求子串,改用动态分配的一维数组,“堆”！,第12页,例：用顺序存储方式实现求子串函数SubString(/若非空串,按串长分配空间;否则ch=NULLi

7、ntlength;/串长度HString,堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,约定：所有按堆存储的串，其关键信息放置在：,第14页,StatusStrAssign(HString/StrAssign,指针变量C也可以自增！即每次后移一个数据单元。,附：堆分配存储表示P77,直到终值为“假”停止，串尾特征是0NULL=0,第15页,StatusStrInsert(HString/StrInsert,例：用“堆”实现串插入操作,第16页,讨论：法1存储密度为；法2存储密度为；,显然，若数据元素很多，用法2存储更优称为块链结构,链式存储特点：用

8、链表存储串值，易插入和删除。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),1/2,9/15=3/5,第17页,#defineCHUNKSIZE80/可由用户定义的块大小typedefstructChunk/首先定义结点类型charchCHUNKSIZE;/结点中的数据域structChunk*next;/结点中的指针域Chunk;,块链类型定义：,typedefstruct/其次定义用链式存储的串类型Chunk*head;/头指针Chunk*tail;/尾指针intcurLen;/结点个数Lstring;/串类型只用一次，前面可以不加Lstring,第18

9、页,再次强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,这类操作中均涉及到定位问题，称为串的模式匹配。它是串处理系统中最重要的操作之一。,第19页,4.3串的模式匹配算法!,第20页,4.3串的模式匹配算法,串的模式匹配：子串定位运算（Index函数）。,算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现Index(S,T,pos)函数,模式(Pattern）:存在于时间和空间种可观察事物中的信息，我们可以区分它们是否相同或相似，都可以称之为模式。,模式匹配(PatternMatching):检验模式是否相同或相似的过程

10、。,第21页,初始条件：串S和T存在，T是非空串，1posS0操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,Index(S,T,pos)函数,算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现Index(S,T,pos)函数（见教材P71）,pos=5,主串S中从pos位置开始起搜索子串T第一次出现的位置是6,第22页,基础知识：两等长串是否相等的比较方法,intIs_Equal(SStringS,SStringT)inti=1;j=1;/定义i，j分别指示两串当前比较字符位置，相当于“指针”while(iT0)

11、return1;/匹配成功时jT0，即T串长度，返回1，匹配成功elsereturn0;/匹配失败时jT0,返回0/Is_Equal,第23页,BF算法（又称古典或经典的、朴素的、穷举的）KMP算法（特点：速度快）,算法种类：,S=ababcabcacbab,T=abcac,问：现在主S串比模式串T长，要找到其中是否包含子串T怎么办？,答：可将主串S中和T串等长的子串与T进行比较，因此需要通过循环实现！,下面介绍两种常用实现算法：,有两种实现方法：T不动，取S的不同子串与其比较S不动，T移动,第24页,BF算法设计思想：将主串的第i个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若

12、不等，从主串的下一字符（i+1）起，重新与第一个字符比较。,直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0.,BF算法的实质：依次将主串中和T串等长的子串与T进行比较，故需要进行一个循环！,如何采用BF算法实现Index(S,T)函数？,可借助演示系统单步执行获得感性认识！,第25页,BF算法特例：S=ababcabcacbab，T=abcac，pos=1，求：串T在串S中第pos个字符之后的位置。,解：因pos=1，可利用演示系统看BF算法执行过程,intIndexBF(SStringS,SStringT)此题的B

13、F算法：inti=1,j=1;/初始“指针”while(iT0)returni-T0;/子串结束，说明匹配成功elsereturn0;/IndexBF注意比较和Is_Equal(SStringS,SStringT)的异同,相当于子串向右滑动一个字符位置,S=ababcabcacbab,T=abcac,pos=1,第26页,IntIndex(SStringS,SStringT,intpos)inti=pos,j=1;while(iT0)returni-T0;/子串结束，说明匹配成功elsereturn0;/Index,BF算法的实现即Index（）操作的实现,相当于子串向右滑动一个字符位置,匹配

14、成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,此函数仅仅就是从第pos个位置开始比较而已!,第27页,最恶劣情况分析：例如：S=aaaaaaab;t=ab;n8，m2（1）主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位都比较了m次，（2）别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度？,(n-m+1)*m,O(n-m+1)*m)O(n*m),第28页,设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：,即最好情况下的时间复杂度是O(n+m)。,最好情况是：（1）主串前面n-m个位置比较时第一位就不等，即这n-m位都只比较了n-m次（2）同样最后m位也各比较了一次，还要加上m！总共比较次数：i1m(设T在S中出现位置是i）,S=ababcabcmbcac,T=mbcac,第29页,S=ababcabcacbab,T=abcac,S=ababca