北邮算法与数据结构4.ppt

1、数据结构-第四章 串,1,第四章 串,串是特殊的线性表，数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象；串的操作主要以“子串”为操作对象。 4.1 串类型的定义 4.2 串的存储结构和操作的实现 4.3 串的模式匹配算法 4.4 串应用示例文本编辑 本章学习要点及习题,数据结构-第四章 串,2,4.1 串类型的定义,4.1.1 串的概念 串（字符串）：是由零个或多个字符组成的有限序列。 记作：s = a1a2an (n0) 串长：串中字符的个数n。 子串和主串：串中任意个连续的字符组成的子序列称 为该串的子串。包含子串的串称为主串。 串相等：两个串长度相等，且对应位置的字符都相等

2、。 空串和空白串：空串不包含任何字符,表示为 ； 空白串由一个或多个空格组成，如 。,数据结构-第四章 串,3,4.1.2 串的常用基本操作,(1)用串常量赋值 StrAssign( s=I am a nurse. (3) StrInsert(s, 8, r) s=I am a good nurse.,数据结构-第四章 串,5,4.2 串的存储结构和操作的实现,4.2.1 串的顺序存储结构 （1）定长顺序存储表示,7 s t u d e n t,0 1 2 3 4 5 6 7 8,MAXSTRLEN,#define MAXSTRLEN 255 /予定义最大串长 typedef unsigned

3、 char SStringMAXSTRLEN+1;,存放串的长度,存储定义,数据结构-第四章 串,6,基本操作实现示例,约定：串值长度上溢时，用“截尾法”处理， 即 “截断”超过予定义长度的部分。,int StrCompare(SString S, SString T) /ST,返回值0；S=T，返回0；ST，返回值 0 for (i=1; i=S0 return S0-T0 / StrCompare,操作基于“字符序列复制”,i,数据结构-第四章 串,7,Status Concat(SString / Concat,数据结构-第四章 串,8,Status SubString(SString

4、/ SubString,0 1 pos,len,S,Sub,数据结构-第四章 串,9,（2）堆分配存储表示,动态分配串值存储空间，避免定长结构的截断现象。,typedef struct char *ch; /串空间基址，按串长申请 int length; /串长度 HString;,存储定义,数据结构-第四章 串,10,基本操作实现示例,int StrCompare(HString S, HString T) /ST,返回值0；S=T，返回0；ST，返回值 0 for (i=0; iS.length / StrCompare,S1,S2,数据结构-第四章 串,11,Status Concat(

5、HString / Concat,S1,S2,T,数据结构-第四章 串,12,Status SubString(HString / SubString,pos-1,0,len,S.length-1,数据结构-第四章 串,13,4.2.2 串的块链存储结构,设置尾指针便于联结操作,#define CHUNKSIZE 4 /由用户定义块大小 typedef struct Chunk char chCHUNKSIZE; struct Chunk * next; Chunk; typedef struct Chunk * head， * tail; /串的、尾头指针 int curlen; /串的当前

6、长度 LString;,占用存储量大且操作不便，实际应用很少。,数据结构-第四章 串,14,4.3 串的模式匹配算法,模式匹配 即子串的定位操作。 是各种串处理系统中最重要的操作之一。 操作定义 Index（S，T， pos） S主串，T子串 pos从该位序字符开始向后寻找匹配 例 S=abcabcdefabcdmn T=efapq 匹配失败 T=bcd 匹配成功，有效位移 =5,以定长顺序存储结构讨论算法实现。,数据结构-第四章 串,15,4.3.1 朴素的模式匹配算法,主串S,子串T,1 pos,n(S0),m(T0),i=pos; j=1;,1,失配,数据结构-第四章 串,16,int

7、Index(SString S, SString T, int pos) /返回子串T在主串S中从第pos个字符开始的位置。 /若不存在，返回值为0。1posStrLength(S) i=pos; j=1; /设定主串、子串字符开始比较的位置 while ( i T0 ) return i-T0 ; /匹配成功 else return 0; / Index,最坏情况字符比较次数为：(n-m+1)m 算法复杂度: O(mn),数据结构-第四章 串,17,4.3.2 模式匹配的一种改进算法(KMP算法),改进之处 在比较过程中，主串的下标i只增不减，不回溯，可使算法复杂度提高到O(m+n) 。 分

8、析 1 2 3 4 5 6 7 8 9 10 11 12 13 主串s a b c d a b c d a b e g h s1s2sn 子串t a b c d a b e g p1p2pm,mn,i=7,j=7,数据结构-第四章 串,18,引入next数组,nextj=k：k是当模式(子串)中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。 0 当 j=1 时 代表下一趟比较i=i+1，j=1 maxk |1kj 且 p1pk-1=pj-k+1pj-1 当此集合不空时 1 其它情况(即j1且上述集合为空) 例 a b c d a b c d a b e

9、 g h a a a a a nextj 0 1 1 1 1 2 3 4 5 6 7 1 1 0 1 2 3 4,nextj=,下一趟比较i不变，j=k,下一趟比较i不变，j=1,k,数据结构-第四章 串,19,KMP算法描述,int index_KMP(SString S, SString T, int pos) i=pos; j=1; while (i T0) return i-T0; else return 0; /index_KMP,数据结构-第四章 串,20,求next数组值,算法思想：利用递推 即已知next1=0, nextj=k; 求nextj+1 主串 p1 . pj-k+1

10、pj-k+2 pj-1 pj pj+1 pm 子串 p1 p2 pk-1 pk . pm 算法描述,p1p2 . pnextk . . . pm,void get_next(SString T, int /get_next,j j+1,k-1,数据结构-第四章 串,21,修正next数组,Next数组的缺陷 s= a b c a b c a x a b c a b c a b b a c t= a b c a b c a b b a c next8=5 a b c a b c a b b a c next5=2 a b c a b c a b b a c next2=1 a b c a b c

11、 a b b a c 存在p8=p5=p2, 因此当s8p8时，s8与p5 、 p2的比较是无意义的。 改进方法 用nextval数组代替next数组 求出Pj处的k值；若Pj=Pk，则nextvalj=nextvalk 否则nextvalj=k,i,j,数据结构-第四章 串,22,例 j 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 a b c a b c a b b a c a a a a b nextj 0 1 1 1 2 3 4 5 6 1 2 0 1 2 3 4 nextvalj 0 1 1 0 1 1 0 1 6 0 2 0 0 0 0 4 算法描述,void

12、 get_nextval(SString T, int /get_nextval,数据结构-第四章 串,23,KMP算法时间复杂度分析, get_nextval（）； index_KMP（）； 通常，模式串长度m主串长度n 求next(nextval)数组：O(m) 主串与模式串匹配： O(n) 整个匹配算法O(m+n),数据结构-第四章 串,24,4.4 串应用示例文本编辑,分析 操作对象 文本串 （行是文本串的子串） 基本操作 查找 插入 删除,轻轻的我走了，正如我轻轻的来； 我轻轻的招手，作别西天的云彩。 那河畔的金柳，是夕阳中的新娘 波光里的艳影，在我的心头荡漾。 软泥上的青荇，油油的

13、在水底招摇； 在康河的柔波里，我甘心做一条水草 那树荫下的一潭，不是清泉， 是天上虹揉碎在浮藻间，沉淀着彩虹似的梦。 寻梦？撑一支长篙，向青草更青处漫溯， 满载一船星辉，在星辉斑斓里放歌 但我不能放歌，悄悄是别离的笙箫； 夏虫也为我沉默，沉默是今晚的康桥！ 悄悄的我走了，正如我悄悄的来； 我挥一挥衣袖，不带走一片云彩。,数据结构-第四章 串,25,存储结构选择,方案一： 简单顺序存储 方案二,行表,堆/块链,0 1 2 n,数据结构-第四章 串,26,方案三,数据结构-第四章 串,27,1. 熟悉串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作。 2. 了解串的各种存储结构的特点及其适用场合。 3. 理解串的两种模式匹配算法。,数据结构-第四章 串,28,习题,1.已知下列字符串： a=an apple, b=other hero, c=her 求(1) SubString(Sub, a, 1, 2); Concat( u, Sub, b) (2) SubString(Sub,a,5,1); Re