数据结构第四章串.

1第4章串（String）4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法2记为：s=‘a1a2……..an’(n≥0)串名串值（用‘’括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。4.1串类型的定义隐含结束符‘\0’，即ASCII码NUL为何要单独讨论“串”类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。3若干术语：串长：串中字符的个数（n≥0）.n=0时称为空串。空白串：由一个或多个空格符组成的串。问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.4子串：子串位置：字符位置：串相等：例1：现有以下4个字符串：a=‘BEI’b=‘JING’c=‘BEIJING’d=‘BEIJING’问：①他们各自的长度？a是a,c和d的子串，在a,c和d中的位置都是1串S中任意个连续的字符序列叫S的子串;S叫主串。子串的第一个字符在主串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。②a是哪个串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”③空串是哪个串的子串？a是不是自己的子串？5C语言中已有类似串运算函数！ADTString{Objects:D={ai|ai∈CharacterSet,i=1,2,…，n,n≥0}Relations:R1={ai-1,ai|ai-1,ai∈D,i=2,…，n}functions://至少有13种基本操作StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若ST，返回值大于0…StrLength(S)//求串长，即返回串S中的元素个数Concat(&T,S1,S2)//串连接，用T返回S1＋S2的新串SubString(&Sub,S,pos,len)//求S中pos起长度为len的子串……Index(S,T)//子串定位函数（模式匹配），返回位置Replace(&S,T,V)//用子串V替换子串T}ADTString串的抽象数据类型定义最小操作子集6注：Concat操作＝concatenation，把多个短字符串合并为长字符串复习：C语言中常用的串运算C串比较：intstrcmp(char*s1,char*s2);求串长：intstrlen(char*s);串连接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,char*c);……注：用C处理字符串时，要调用标准库函数#includestring.h类CStrCompare(S,T)StrLength(S)Concat(&T,S1,S2)Index(S,T)7Replace(&S,T,V)//用子串V替换子串T设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。求：例1：StrLength(s)＝StrLength(t)＝SubString(&sub,s,8,7)=SubString(&sub,t,2,1)=Index(s,‘A’)=Index(s,t)=Replace(s,‘STUDENT’,q)=144‘STUDENT’‘O’30（s中没有t=’GOOD’！）Index(S,T,pos)//返回子串T在pos之后的位置’IAMAWORKER’8提问：当s=’IAMASTUDENT’时,INDEX（s,’A’，pos）=3，若想搜索后面那个‘A’怎么办？答:INDEX（s,’A’）返回的只是“第一次”出现的位置。如果还要搜索后面的A，则pos变量要跟着变才行。也就是说，要把得到的“第一次”位置再代入INDEX（s,’A’，pos）函数中循环操作才行。即INDEX（s,’A’，3）=69解：因为SubString(s,6,2)＝‘A’；SubString(s,7,8)＝‘STUDENT’Concat(,t,SubString(s,7,8))＝’GOODSTUDENT’所以：Concat(,SubString(s,6,2),Concat(t,SubString(s,7,8)))＝‘AGOODSTUDENT’例2：设s=’IAMASTUDENT’,t=’GOOD’,求：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？104.2串的表示和实现•定长顺序存储表示——用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。•串的块链存储表示——链式方式存储首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有两种机内表示方法：顺序存储链式存储11定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。例如：#defineMaxstrlen255//用户可用的最大串长typedefcharSString[Maxstrlen＋1]SString;SStrings;//s是一个可容纳255个字符的顺序串。注：•一般用SString[0]来存放串长信息；•C语言约定在串尾加结束符‘\0’，以利操作加速，但不计入串长（用首址和串长、或首址和尾标记来描述串数组）•若字符串超过Maxstrlen则自动截断（因为静态数组存不进去）。12例：用顺序存储方式编写求子串函数SubString(&Sub,S,pos,len)StatusSubString(SString&sub,SStringS,intpos,intlen){if(pos1||posS[0]||len0||lenS[0]-pos+1)returnERROR;//若pos和len参数越界，则告警，S[0]为S的串长Sub[1……len]=S[pos……pos+len-1];Sub[0]=len;returnOK;}将串S中从第pos个字符开始、长度为len的字符序列复制到串Sub中。（注：考虑到函数通用性，应当让串Sub的预留长度与S一样）子串长度s=‘a1a2……..an’poslenSub[]13讨论：法1存储密度为；法2存储密度为；显然，若数据元素很多，用法2存储更优—称为块链结构链式存储特点：用链表存储串值，易插入和删除。法1：链表结点的数据分量长度取1（个字符）法2：链表结点（数据域）大小取n(例如n=4)1/29/15=3/5ABCINULLheadheadABCDEFGHI###NULL14对块链表的整体描述#defineCHUNKSIZE80//每块大小，可由用户定义typedefstructChunk{//首先定义结点类型charch[CHUNKSIZE];//每个结点中的数据域structChunk*next;//每个结点中的指针域}Chunk;块链类型定义：typedefstruct{//其次定义用链式存储的串类型Chunk*head;//头指针Chunk*tail;//尾指针intcurLen;//结点个数}Lstring;对每个结点的描述15算法目的：确定主串中所含子串第一次出现的位置（定位）4.3串的模式匹配算法•BF算法（又称古典的、经典的、朴素的、穷举的）•KMP算法算法种类：带回溯，速度慢避免回溯，匹配速度快定位问题称为串的模式匹配(PatternMatching)，即子串定位运算，它是串处理系统中最重要的操作之一。被匹配的主串称为目标串；子串称为模式。典型函数为Index(S,T,pos)16BF算法的实现—即编写Index(S,T,pos)函数例1：S=‘abbaba’，T=‘aba’，pos=1，求：串T在串S中第pos个字符之后的位置。BF算法设计思想：•将主串S的第pos个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。•直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0.17IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i=S[0]&&j=T[0]){if(S[i]==T[j]){++i,++j}//继续比较后续字符else{i=i-j+2;j=1;}//指针回溯到下一首位，重新开始匹配}if(jT[0])returni-T[0];//子串结束，说明匹配成功elsereturn0;}//Index例2：S=‘ababcabcacbab’，T=‘abcac’，求Index(S,T,5)相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。T[0]是T的串长ijS=‘ababcabcacbab’T=‘abcac’pos=518讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m)一般的情况是：O(n+m)推导方法：要从最好到最坏情况统计总的比较次数，然后取平均。BF算法的时间复杂度最好的情况是：一配就中！只比较了m次。能否利用已部分匹配过的信息而加快模式串的滑动速度？能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m)请看KMP算法！最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！所以总次数为：(n-m)*m+m＝(n-m+1)*m19KMP算法（特点：速度快）①KMP算法设计思想②KMP算法的推导过程③KMP算法的实现（关键技术:计算next[j]）④KMP算法的时间复杂度20尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。例：①KMP算法设计思想：S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’Index_kmp的返回值应为i=6需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是高效率的?iiikkabaabckiii-T[0]21奇妙的结果：k仅与模式串T有关！②KMP算法的推导过程：请抓住部分匹配时的两个特征：两式联立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’则T的k-1～1位＝S前i-1～i-(k-1)位即(4-2）式含义设目前打算与T的第k字符开始比较S=‘ababcabcacbab’T=‘abcac’ik(1)(2)‘T1…Tk-1’则T的j-1～j-(k-1)位＝S前i-1～i-(k-1)位即(4-3）式含义ikjS=‘ababcabcacbab’T=‘abcac’刚才肯定是在S的i处和T的第j字符处失配‘Tj-(k-1)…Tj-1’截取一段，但k有限制，1kjk是追求的新起点加速的前提：T首与Tj处有相同子串注意：j为当前已知的失配位置，我们的目标是计算新起点k。式中仅剩一个未知数k，理论上已可解！22根据模式串T的规律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’由当前失配位置j(已知)，可以归纳出计算新起点k的表达式。next[j]＝0当j＝1时//不比较max{k|1kj且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况讨论：（1）next[j]的物理意义是什么？（2）next[j]具体怎么求？—即KMP算法的实现令k=next[j]（k与j显然具有函数关系），则取T首与Tj处最大的相同子串新起点k怎么求？23（1）next[j]有