数据结构-第四章幻灯片

《数据结构-第四章幻灯片》由会员分享，可在线阅读，更多相关《数据结构-第四章幻灯片（34页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程的内容,第4章 串（String）,4.2 串的表示和实现 4.3 串的模式匹配算法,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,4.1 串类型的定义,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,说明：串是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符（字母、数字或其他字符），所以，人们经常这样定义串：串是一个有穷字符序列。,4,若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等：,串中字符个数（n0）. n=0 时称为空串 。 由一

2、个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。,注：空串是任意串的子串。任意串是其自身的子串。,5,串常量和串变量 通常在程序中使用的串可分为：串常量和串变量。 串变量：串变量和其它类型的变量一样，其值是可以改变的。 串常量：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。 串常量由直接量来表示的： 【例】Error（“overflow”）中“overflow”是直接量。 串常量命名 有的语言允许对串常量命名，以使程序易读、易写。 【例】C+中，可定义串

3、常量path const char path=“dir/bin/appl“;,练1：串是由 字符组成的序列，一般记为 。,练2：现有以下4个字符串： a =BEI b =JING c = BEIJING d = BEI JING,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,练3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.,0个或多个,S=a1a2an,ADT Sti

4、ng Objects: D=ai | aiCharacterSet, i=1, 2,，n, n0 Relations: R1= | ai-1,ai D, i=2, ，n functions: / 有13种之多 StrAssign(&T, chars) / 串赋值，生成值为chars的串T StrCompare(S,T) / 串比较，若ST，返回值大于0 StrLength(S) / 求串长，即返回S的元素个数 Concat(&T, S1, S2) / 串连接，用T返回S1S2的新串 SubString(&Sub, S, pos, len) / 求S中pos起长度为len的子串 Index(S,

5、 T, pos) / 返回子串T在pos之后的位置 Replace(&S, T,V) / 用子串V替换子串T ADT Sting,串的抽象数据类型定义（参见教材P71）,最小操作子集,设 s =I AM A STUDENT, 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)=,14 4 STUDENT O 3 0 （ s中没有t！） I AM A WORKER,再问：C

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

7、,例如： #define Maxstrlen 255 /用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ; SString s; /s是一个可容纳255个字符的顺序串。,注： 一般用SString0来存放串长信息； C语言约定在串尾加结束符 0，以利操作加速，但不计入串长； 若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。,讨论：想存放超长字符串怎么办？静态数组有缺陷！,实现方式：参见教材P73编程两例，两串连接和求子串,改用动态分配的一维数组,“堆”！,例：用顺序存储方式实现求子串函数SubString(&Sub,

8、S, pos, len),Status SubString(SString ,将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样）,s = a1 , a2 , , an,n串长,pos,len,思路：利用malloc函数合理预设串长空间。 特点： 若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。,Typedef struct char *ch; / 若非空串,按串长分配空间; 否则 ch = NULL int length; /串长度 HString,堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执

9、行过程中动态分配而得。,约定：所有按堆存储的串，其关键信息放置在：,Status StrInsert ( HString /StrInsert,例：用“堆”实现串插入操作(教材P75),Status StrAssign(HString /StrAssign,指针变量C也可以自增！意即每次后移一个数据单元。,附：堆分配存储表示,直到终值为“假”停止，串尾特征是 0NULL=0,显然，若数据元素很多，用法2存储更优称为块链结构,链式存储特点 ：用链表存储串值，易插入和删除。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),16,虽然提高结点的大小使得存储密度增大，

10、但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。,#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域 struct Chunk * next ; /结点中的指针域 Chunk;,块链类型定义：,例略,typedef struct /其次定义用链式存储的串类型 Chunk *head; /头指针 Chunk *tail; /尾指针 int curLen; /结点个数 Lstring;,再次强调：串与线性表的运算有所不同，是以“串的整体”作为操作对

11、象，例如查找某子串，在主串某位置上插入一个子串等。,这类操作中均涉及到定位问题，称为串的模式匹配。它是串处理系统中最重要的操作之一。,19,4.3 串的模式匹配算法,模式匹配(Pattern Matching) 即子串定位运算（Index函数）。,算法目的：确定主串中所含子串第一次出现的位置（定位） 即如何实现 Index(S,T,pos)函数（见教材P72）,初始条件：串S和T存在，T是非空串，1posStrLength(s) 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,注：S称为被匹配的串，T称为模式串。若S包含串T，

12、则称“匹配成功”。否则称 “匹配不成功” 。, BF算法设计思想： 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。,BF算法 （又称古典或经典的、朴素的、穷举的） KMP算法（特点：速度快）,算法 种类：,直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .,Int Index(SString S, SString T, int pos) i=pos; j=1; while ( iT0) return i-T0; /

13、子串结束，说明匹配成功 else return 0; /Index, BF算法的实现即Index（）操作的实现 （见教材P79）,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,例： S=ababcabcacbab，T=abcac，pos=1， 求：串T在串S中第pos个字符之后的位置。,解：,此题的BF算法： int IndexBF(Sstring S,Sstring T) i=1;j=1; while(iT0) return i-T0; else return 0; ,讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字

14、符的总次数为,(n-m+1)*mO(n*m),最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度,但一般情况下BF算法的时间复杂度为O(n+m),KMP算法（特点：速度快）, KMP算法设计思想 KMP算法的推导过程 KMP算法的实现 （关键技术:计算nextj） KMP算法的时间复杂度,能否利用已经部分匹配的结果而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！可提速到O(n+m)！ 例：, KMP算法设计思想： (参见教材P80-84）,S=a b a b c a b c a

15、 c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,Index_kmp的返回值应为i=6,需要讨论两个问题： 如何“记忆”部分匹配结果？ 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.,a b a,a b c, KMP算法的推导过程：（见教材P81）,抓住部分匹配结果的两个特征：,两式联立可得：T1Tk-1=Tj-(k-1) Tj-1 注意：j 为当前已知的失配位置，我们的目标是计算新起点 k， 仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前i-1i-(k-1)位T的j-1j-(k-1)位 即(4-3）式含义,则T的k-11位S前i-1i-(k-1)位 即(4-2）式含义,刚才肯定是在S的i处和T的第j字符 处失