数据结构课件4.ppt

《数据结构课件4.ppt》由会员分享，可在线阅读，更多相关《数据结构课件4.ppt（30页珍藏版）》请在三一文库上搜索。

1、1,第4章 串（String）,4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 4.3 串基本操作的实现,2,记为： s = a1 , a2 , , an (n0 ),定义：串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,隐含结束符0 ，即ASCII码NUL,3,若干术语： 串长： 空白串： 子串： 串相等：,串中字符个数（n0）. n=0 时称为空串 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 串长度相等，且对

2、应位置上字符相等。,附： 1.空串(Null String)是指长度为零的串；而空白串(Blank String)是指包含一个或多个空白字符 (空格键)的字符串. 2. 空串是任意串的子串，任意串是其自身的子串。 3.通常将子串在主串中首次出现时该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。,4,练1：现有以下4个字符串： a =BEI b =JING c = IS BEIJINGBEI d = BEI JING,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 13，d=8,a是c和d的子串，在c中的位置是4, 在d中的位置

3、是1.,串的抽象数据类型定义（参见教材P71）,5,设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：,例2：,StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A,4)= Index( s, t)= Replace(s, STUDENT,q)=,14 4 STUDENT O 6 0 （ s中没有t！） I AM A WORKER,思考：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？,6,4.2 串的表示和

4、实现,注：因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。但是，串与线性表的运算又有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,7,定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列 堆分配存储表示 用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示 链式方式存储,串有三种机内表示方法：,顺序存储,链式存储,8,特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,4.2.1 定长顺序存储表示,注：串长有两种表示 一种以下标为

5、0的数组分量存放串长。,例如： #define Maxstrlen 255 /用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ; SString s; /s是一个可容纳255个字符的顺序串。,串长信息用s0来表示。,9,此时顺序串的类型定义和顺序表类似： typedef struct char chmaxstrlen; int length; SString ; SString s; /其优点是涉及到串长操作时速度快。,注：串长有两种表示 另一种如有的C语言约定在串尾加结束符0，以利操作加速，但不计入串长； 若不设结束符，可用一个整数来表示

6、串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。则：位置。,若字符串超过Maxstrlen 则自动截断（因为静态数组存不进去）。,串长信息用s. length来表示。,10,实现方式： 参见教材P73编程两例，两串连接和求子串,11,例：顺序方式实现求子串函数SubString(&Sub, S, pos, len) /将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中 （注：串Sub的预留长度与S一样）,Status SubString(SString ,s = a1 , a2 , , an,串长,pos,len,12,思考： 超长字符串如何存储静态数组有缺陷！,引

7、入动态分配的一维数组,“堆”！,13,思路： 利用malloc函数合理预设串长空间。若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。约定:堆存储的串，其关键信息放置在基址中。,Typedef struct char *ch; / 若是非空串,按串长分配空间; 否则 ch = NULL int length; /串长度 HString,特点： 仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,4.2.2 堆分配存储表示,14,Status StrInsert ( HString /StrInsert,例：用“堆”实现串插入操作(教材P75),

8、15,Status StrAssign(HString /StrAssign,指针变量C也可以自增！意即每次后移一个数据单元。,例：堆分配存储表示(教材P76),直到终值为“假”停止，串尾特征是 /0NUL=0,16,4.2.3 串的块链存储表示,特点 ： 用链表存储串值，易插入和删除。顺序串上的插入和删除操作不方便，需要移动大量的字符；因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。,说明： 这种结构便于进行插入和删除运算，但存储空间利用率太低。 为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度

9、不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,17,则：法1存储密度为 ；法2存储密度为 ；,显然，若数据元素很多，用法2存储更优称为块链结构,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),1/2,9/15=3/5,18,#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域 struct Chunk * next ; /结点中的指针域 Chunk;,块链类型定义：,例略,typedef stru

10、ct /其次定义用链式存储的串类型 Chunk *head; /串的头指针 Chunk *tail; /串的尾指针 int curLen; /串的当前结点个数（长度） Lstring; /串类型只用一次，前面可以不加Lstring,19,例：用顺序存储方式实现求子串函数SubString (教材P75) 例：用“堆”实现串插入操作(教材P75) 例：堆分配存储表示(教材P76),4.3 串基本操作的实现,20,算法目的：确定主串中所含子串第一次出现的位置（定位） 即如何实现 Index(S,T,pos)函数（见教材P71）,4.4 串的模式匹配算法,模式匹配(Pattern Matching)

11、 即子串定位运算。,初始条件：串S和T存在，T是非空串，1posStrLength(s) 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”。否则称 “匹配不成功” 。,21, BF算法设计思想： 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。,BF算法 （又称古典或经典的、朴素的、穷举的） KMP算法（特点：速度快）,算法：,直到主串的一个连续子串字符序列与模式相等

12、 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .,S=a b a b c a b c a c b a b,T=a b c a c,pos=5,22,Int Index(SString S, SString T, int pos) i=pos; j=1; while ( iT0) return i-T0; /子串结束，说明匹配成功 else return 0; /Index, BF算法的实现即Index（）操作的实现 （见教材P79）,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,23,KMP算法（特点

13、：速度快）, KMP算法设计思想 KMP算法的推导过程 KMP算法的实现 （关键技术:计算nextj） KMP算法的时间复杂度,24,能否利用已经部分匹配的结果而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！可提速到O(n+m)！ 例：, KMP算法设计思想： (参见教材P80-84）,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,S=a b a b c a b c a c b a b,T=a b c a c,Index_kmp的返回值应为i=6,需要讨论两个问题： 如何

14、“记忆”部分匹配结果？ 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.,a b a,a b c,25, 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字符 处失配,设目前应与T的

15、第k字符开始比较,26, KMP算法的推导过程(续）：,根据模式串T的规律： T1Tk-1=Tj-(k-1) Tj-1 和已知的当前失配位置j ，可以归纳出计算新起点 k的表达式。 令k = next j ，则,next j ,0 当j1时 max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况,讨论： next j 有何意义？ 一旦失配，应从模式串T中第next j 个字符开始与S的失配点i 重新匹配! next j 怎么求？ 后面会举例（参见教材P81）,27,第一步，先把模式T所有可能的失配点j所对应的nextj计算出来； 第二步：执行定位函数index_kmp

16、（与BF算法模块非常相似）, KMP算法的实现即Index( )操作的实现 （见教材P82）,Int Index_KMP(SString S, SString T, int pos) i=pos; j=1; while ( iT0) return i-T0; /子串结束，说明匹配成功 else return0; /Index_KMP,28,怎样计算模式T所有可能的失配点 j 所对应的 nextj？,例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 nextj :,0,1,1,2,2,3,1,2,讨论：,j=1时, next j

17、0；因为属于“j=1”; j=2时, next j 1；因为属于“其他情况 ”；,刚才已归纳：,j=3时, k=2，只需查看T1=T2；等式不成立属于“其他情况”,j=4时, k=2，3，要查看T1=T3 和T1T2=T2 T3,j=5时, k=2，3，4，要查看T1=T4 、T1T2=T3T4 和 T1T2T3=T2T3T4,以此类推，可得后续nextj值。,29,讨论两个有关next j 的问题：, 怎样简捷计算nextj？ 可用递推法编程实现！ （参见P83简捷算法） 计算nextj的时间为O(m),void get_next(SString T, int / get_next,void get_nextval(SString T, int / get_nextval, next j 是否完美无缺？ 答：未必，例如当 S=a b a a a a b, T=a a a a b时 仍有多余动作 （参见P84改进算法, 称为nextval j ）,30, KMP算法的时间复杂度,因为计算nextj的时间为O(m); 且Index_KMP函数（没有回溯）的匹配时间为O(n); 所以KMP算法的总时间耗费为： O(n+m) 注意：由于BF算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。,