数据结构市公开课一等奖省赛课获奖课件

数据结构南昌工程学院数据结构第1页

4.1 串类型定义

4.2 串表示和实现

**4.3 串模式匹配算法

**4.4 串操作应用举例

目录第四章串数据结构第2页知识点串相关概念和术语串基本运算功效串次序存放方法（包含紧缩格式和非紧缩格式）和链接存放方法串匹配运算难点串匹配运算算法要求熟练掌握串逻辑结构、存放结构及串上基本运算，并能设计简单算法了解串匹配运算算法基本思想数据结构第3页4.1 串类型定义串基本概念

串(String)是零个或多个字符组成有限序列。普通记作S=“a1a2a3…an”，其中S是串名，双引号括起来字符序列是串值；ai(1≦i≦n)能够是字母、数字或其它字符；串中所包含字符个数称为该串长度。长度为零串称为空串(EmptyString)，它不包含任何字符。通常将仅由一个或多个空格组成串称为空白串(BlankString)注意：空串和空白串不一样，比如“”和“”分别表示长度为1空白串和长度为0空串。串中任意个连续字符组成子序列称为该串子串，包含子串串对应地称为主串。通常将子串在主串中首次出现时该子串首字符对应主串中序号，定义为子串在主串中序号（或位置）。数据结构第4页比如，设A和B分别为A=“Thisisastring”B=“is”则B是A子串，A为主串。B在A中出现了两次，其中首次出现所对应主串位置是3。所以，称B在A中序号（或位置）为3

尤其地，空串是任意串子串，任意串是其本身子串。通常在程序中使用串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示，比如语句Error(“overflow”)中“overflow”是直接量。串变量和其它类型变量一样，其取值是能够改变。数据结构第5页串抽象数据定义

串抽象数据类型定义见书P71串基本操作对于串基本操作，许多高级语言均提供了对应运算或标准库函数来实现。下面仅介绍几个在C语言中惯用串运算。定义以下几个变量：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;（1）求串长(length)intstrlen(chars);//求串长度比如：printf(“%d”,strlen(s1));输出13数据结构第6页（2）串复制(copy)char*strcpy(charto,charfrom);该函数将串from复制到串to中，而且返回一个指向串to开始处指针。比如：strcpy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charstrcat(charto,charfrom)该函数将串from复制到串to末尾，而且返回一个指向串to开始处指针。比如：strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem”数据结构第7页(4)串比较（compare)intstrcmp(chars1,chars2);该函数比较串s1和串s2大小，当返回值小于0，等于0或大于0时分别表示s1<s2\s1=s2或s1>s2比如：result=strcmp(“baker”,”Baker”)result>0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result<0（5）字符定位(index)char*strchr(chars,charc);该函数是找c在字符串中第一次出现位置，若找到则返回该位置，不然返回NULL。比如：p=strchr(s2,”.”);p指向“file”之后位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”

上述串操作是最基本，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串其余操作可由这些基本操作组合而成。数据结构第8页例1、求子串求子串过程即为复制字符序列过程，将串S中第pos个字符开始长度为len字符复制到串T中。voidsubstr(stringsub,strings,intpos,intlen){if(pos<0||pos>strlen(s)-1||len<0)error(“parametererror”)strncpy(sub,&s[pos],len);}例2、串定位index(s,t,pos)在主串中取从第i个字符起、长度和串T相等子串和T比较，若相等，则求得函数值为i，不然值增1直至S中不存在和串T相等子串为止。

数据结构第9页intindex(strings,stringt,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while(i<n-m+1){substr(sub,s,i,m);if(strcmp(sub,t)!=0)++i;elsereturn(i);}}return(0);}数据结构第10页4.2 串表示和实现因为串是特殊线性表，故其存放结构与线性表存放结构类似。只不过因为组成串结点是单个字符。串有三种机内表示方法，下面分别介绍。定长次序存放表示定长次序存放表示,也称为静态存放分配顺应表。它是用一组连续存放单元来存放串中字符序列。所谓定长次序存放结构，是直接使用定长字符数组来定义，数组上界预先给出：

数据结构第11页普通可使用一个不会出现在串中特殊字符在串值尾部来表示串结束。比如，C语言中以字符‵\0′表示串值终止，这就是为何在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符原因，因为必须留一个字节来存放‵\0′字符。若不设终止符，可用一个整数来表示串长度，那么该长度减1位置就是串值最终一个字符位置。此时次序串类型定义和次序表类似：typedefstruct{charch[maxstrlen];intlength;}sstring;//其优点是包括到串长操作时速度快。数据结构第12页堆分配存放表示这种存放表示特点是，仍以一组地址连续存放单元存放串值字符序列，但它们存放空间是在程序执行过程中动态分配而得。所以也称为动态存放分配次序表。在C语言中，利用动态存放管理函数，来依据实际需要动态分配和释放字符数组空间。这么定义次序串类型也有两种形式。

typedefchar*string;//c中串库相当于这类型定义typedefstruct{char*ch;intlength;}hsring;数据结构第13页statussinsert(hstrings,intpos,hstringt){if(pos<1||pos>s.length+1)returnerror;if(t.length){if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)))exit(overflow);for(i=s.length-1;i>=pos-1;--i)s.ch[I+t.length]=s.ch[i];s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];s.length+=t.length;}returnok;}数据结构第14页intstrlen(hstrings){returns.length;}statusclearstring(hstrings){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;}statusstrassign(hstringt,char*chars){//生成一个其值等于串常量chars串tif(t.ch)free(t.ch);for(i=0,(c=chars;c;++i),++c);if(!i){t.ch=null;t.length=0;}else{if(!(t.ch=(char*)malloc(I*sizeof(char))))exit(overflow);t.ch[0..i-1]=chars[0..i-1];t.length=i;}}数据结构第15页intstrcmp(hstrings,hstringt){for(i=0;i<s.length&&i<t.length;++i)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);returns.length-t.length;}statusconcat(hstringt,hstrings1,hstrings2){if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))exit(overflow);t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];}数据结构第16页Statussubstr(hstringsub,hstrings,intpos,intlen){if(pos<1||pos>s.length||len<0||len>s.length-pos+1)returnerror;if(sub.ch)free(sub.ch);if(!len){sub.ch=null;sub.length=0;}else{sub.ch=(char*)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];s.length=len;}}数据结构第17页串链式存放结构

次序串上插入和删除操作不方便，需要移动大量字符。所以，我们可用单链表方式来存放串值，串这种链式存放结构简称为链串。typedefstructnode{chardata;structnode*next;}lstring;

一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存放空间利用率太低。数据结构第18页为了提升存放密度，可使每个结点存放多个字符。通常将结点数据域存放字符个数定义为结点大小，显然，当结点大小大于1时，串长度不一定恰好是结点整数倍，所以要用特殊字符来填充最终一个结点，以表示串终止。

对于结点大小不为1链串，其类型定为义只需对上述结点类型做简单修改即可。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}lstring;数据结构第19页4.3 串模式匹配算法子串定位运算又称为模式匹配(PatternMatching)或串匹配(StringMatching)，此运算应用在非常广泛。比如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现位置。显然，解此问题有效算法能极大地提升文本编辑程序响应性能。在串匹配中，普通将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：S=“s0s1s2…sn-1”T=“t0t1…tm-1”串匹配实际上是对于正当位置0≦i≦n-m依次将目标串中子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，则称从位置i开始匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1]≠t[0..m-1]，则称从位置i开始匹配失败。上述位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1]≠t[0..m-1]时，i称为无效位移。这么，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现有效位移。数据结构第20页串匹配算法很多，首先我们介绍一个朴素匹配算法：BF法模式匹配(见演示）串直接匹配算法功效是:在串S中查找和串T值相同子串。算法思想是：P书79页。

数据结构第21页IntindexBF(SstringS,SstringT){i=1;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])returni-T[0];elsereturn0;}数据结构第22页这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发觉，所以人们称它为克努特—莫里斯—普拉特操作（简称为KMP算法）这种算法改进在于：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到“部分匹配”结果将模式向右“滑动”尽可能远一段距离后，继续进行比较。

模式匹配一个改进算法：KMP法模式匹配数据结构第23页TabbabaPaba(a)P3T3将i右移一位TabbabaPaba(b)P1T2将i右移一位TabbabaPaba(c)P1T3将i右移一位TabbabaPaba(d)匹配成功举例：T=“abbaba”P=“aba”我们仔细分析左边图例：由(a)可知：P1=T1，P2=T2，P3T3又由P1P2能够推出P1T2所以将i右移一位后(b)比较一定不等，所以(b)就没有必要做，这就在利用部分已匹配结果了。再由P1=P3，能够推出P1T3，所以将i再右移一位后（c）比较也一定不等，所以（c）也没有必要做。所以，由(a)便可直接到(d)，从P1和T4开始进行比较，这么匹配过程对T而言就消除了回溯（i值没有回溯）。123456数据结构第24页看书中P80页例子：i=3第一趟匹配ababcabcacbababcacj=3i=3j=7第二趟匹配ababcabcacbababcacj=1j=5i=7第三趟匹配ababcabcacbab(a)bcacj=2数据结构第25页为了实现上述无回溯匹配算法，关键在于当匹配过程中，一旦Pj和Ti比较不等，即substr(P,1,j-1)=substr(T,i-j+1,j-1)PjTi

说明白点就是，当Pj和Ti比较不等时，我们应该用P中哪个字符和Ti进行比较？我们假设一下应该与P中第k个字符比较（记作Pk）,显然有k<j而且对不一样j，k值也不相同。有趣是，Knuth等人发觉这个k值仅依赖于模式P本身前i个字符组成，而与目标T无关。数据结构第26页现在我们利用next[j]表示与j对应k值，其意义在于：若next[j]>0表示一旦匹配过程中Pj与Ti比较不等，可用P中next[j]为下标字符与Ti进行比较；若next[j]=0表示P中任何字符都无须再与Ti进行比较。

对任何模式P，只要我们能确定next[j]值，就能够用来加速匹配过程。当PjTi时，让Tj（或Tj+1）直接与next[j]表示位置继续比较下去。数据结构第27页KMP匹配算法（伪语言表示）初始化：i=1;j=1;循环：当i<=S[0]&&j<=T[0]假如T[i]==S[j]则i=i+1;j=j+1;不然若next[j]>0则j=next[j];不然i=1;i=i+1;见书P82页算法4.6是完整算法。

且看部分显示（后半部匹配显示）数据结构第28页现在大家应该知道，假如要实现KMP算法（快速匹配或无回溯算法）关键就是怎样正确地计算next数组值。为此我们首先来分析next[j]性质，找出next[j]必须满足条件，然后再给出next数组生成算法就比较轻易了解了。（1）从前面引入来看，显然next[j]是一个整数，而且满足0next[j]j（2）匹配过程中，一旦Pj和Ti比较不等，按next[j]意义，让Ti与Pk（若k=next[j]0）继续比较,为确保继续比较是有效，这个k值是关键，也即应有

P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1数据结构第29页TT1T2T3……..Ti-j+1……..Ti-k+1…….Ti-1TiTi+1………….PP1……..Pj-k+1……...Pj-1PjPj+1………….

?P1……..Pk-1PkPk+1………….

P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1因为在Pj

Ti发生之前已经有P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1,所以上述条件等价于

P1=Pj-k+1,P2=Pj-k+2,….,Pk-1=Pj-1也就是说,k取值应使P1P2…Pj-1头尾k-1个字符组成子串相等，即substr(P,1,k-1)=substr(P,j-k+1,k-1)数据结构第30页（3）为了使不丢失任何匹配成功可能，当存在多个满足第（2）条件