【5A文】数据结构-串

1,数据结构 4 串,2,开始学习本章前要知道：,从数据结构角度看，串也属于线性结构，具有线性结构的共同特征； 学习本章时，要注意到串所具有的线性结构的共性，更要掌握其个性； 串的特殊性主要是：串的元素是字符。,3,主要内容,串的基本概念 串的基本操作 串的存储结构 定长顺序存储 块链存储 串的模式匹配 简单算法 KMP算法,4,串的基本概念,串的定义 串：n个字符的有限序列，n=0 一般记为：S = a1 a2. an 其中，S是串名，a1 a2. an是串S的值，串值必须由一对单引号括起来 串的长度：串中字符的个数,例如,S1=abc S2=FORTRAN_77 S3=(空串),长度为0,5,串的基本概念,几个名词概念,1.子串：串中若干个连续的字符组成的子序列。 例如：S = Beijing&Shanghai T = jing,2.主串：包含子串的串。,特别规定，空串是任意串的子串，任意串是其自身的子串。,6,串的基本概念,例如：S = Beijing&Nanjing&Shanghai T = jing,3.位置： (1)单个字符在主串中的位置被定义为该字符在串中的序号。 (2)子串在主串中的位置被定义为主串中首次出现的该子串的第一个字符在主串中的位置。,位置为4,7,串的基本概念,4.两个字符串相等的充分必要条件为两个字符串的长度相等，并且对应位置上的字符相等。,例如：abcd bacd abcd = abcd,8,串的基本操作,1.给串变量赋值 ASSIGN(S1,S2) 2.判断两个串是否相等EQUAL(S1,S2) 3.两个字符串连接CONCAT(S1,S2) 4.求字符串的长度LEN(S) 5.求子串SUBSTR(S,i,k) 6.求子串在主串中的位置INDEX(S1,S2) 7.串的替换REPLACE(S,S1,S2) 8.串的复制COPY(S1,S2) 9.串的插入INSERTS(S1,i,S2) 10.串的删除DELETES(S,i,k),strcpy(S1,S2) strcmp(S1,S2) strcat(S1,S2) strlen(S) strstr(S1,S2),C函数,模式匹配,9,串的存储结构：定长顺序表示,顺序表示 是用一个字符数组来表示 串长度的表示 C：以0结尾，隐含串长度,#define maxsize 256 /假设串可能的最大长度是256 char smaxsize;,但最多只能存放255个字符，因为必须留一字节来存放串终结符0。,10,串的存储结构：定长顺序表示,若不设置终结符，可用一个整数length来表示串的长度，此时顺序串的类型定义完全和顺序表类似：,s.data,typedef struct char chmaxsize ; /串的存储空间 int curlen ; /当前串的长度 SeqString ;,11,串的表示和实现：定长顺序表示,串的拼接 S10+S20 = maxsize,12,串的表示和实现：定长顺序表示,串的拼接 S10+S20 maxsize S10 maxsize,13,串的表示和实现：定长顺序表示,串的拼接 S10 = maxsize,14,串的表示和实现：定长顺序表示,求子串 串S第i个字符起，长度为j的子串,S,i,j,15,串的表示和实现：链接存储,链接存储,串的链式存储结构简称为链串。其结点数据域为单个字符： typedef struct linknode char data; struct linknode *next; linkstring;,直接使用线性链表来存储字符串：效率太低,16,说明 所谓链结点大小是指每个链结点的数据域中存放的字符的个数。,例如：S=DATA STRUCTURE,串的表示和实现：链接存储,17,在上图中第3个字符后插入“vwxyz“的链串,S1,结点大小为4的链串,S1,串的表示和实现：链接存储,对于结点数据域大于1的链串，其类型定义如下： #define nodesize 80 typedef struct node char datanodesize;/结点存的字符个数 struct node *next; LinkStrNode1;,18,串的表示和实现：链接存储,优点 便于拼接操作 缺点 结点大小需要设置恰当 存储密度 = 结点越小，存储密度越小，操作越方便，但是存储空间浪费大,19,模式匹配(在主串S中定位子串T（模式串）) 回忆一下串匹配的定义： index(S,T) 初始条件：串S和T存在 操作结果：若主串S中存在和串T值相同的子串，返回它在主串S首次出现的位置；否则返回0 例如 主串S = 子串T = CD 则index(S,T)，返回子串T在S中，第一次出现的位置3,串的模式匹配,20,串的模式匹配,Brute-Force算法基本思想： 从目标串s 的第一个字符起和模式串t的第一个字符进行比较 若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。,21,Brute-Force算法的C语言描述如下： int Index(string s,string t) int i=0,j=0; /i,j分别指向串s、t的第1个字符 while( (i=t.curlen ) return( i-t.curlen ); /匹配成功，返回串t在串s中起始位置 else return 0; /匹配失败返回0 ,22,while(is.curlen) ,23,串的模式匹配:简单算法,算法分析 最好的情况 主串S和模式T中的每个字符都只访问了一次 复杂度 = O( n+m ),24,最差的情况 主串S中的每个字符，分别和模式T中的每个字符匹配一次 复杂度 = O( n*m ),串的模式匹配:简单算法,25,由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出了一个改进算法，消除了Brute-Force算法中串s指针的回溯，完成串的模式匹配。 基本思想：在简单算法的基础上，i不要回退，模式串尽量多往右移 时间复杂度为O(s.curlen+t.curlen)，这就是Knuth-Morris-Pratt算法，简称KMP 算法。,串的模式匹配:KMP算法,26,利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。例：,S=ababcabcacbab,T=abcac,aba,abc,S=ababcabcacbab,T=abcac,S=ababcabcacbab,T=abcac,需要讨论两个问题： 如何由当前部分匹配结果确定模式串向右滑动的新比较起点k？ 模式串应该向右滑多远才是高效率的?,27,请抓住部分匹配时的两个特征：,设S的第i字符目前打算与T的第k字符开始比较,k是追求的新起点,则T的k-10=S前i-1i-k位匹配,“T0Tk-1”,(2),刚才肯定是在S的i处和T的第j字符处失配,则T的j-1j-k位=S前i-1i-k位匹配,“Tj-kTj-1”截取一段，但k有限制，0kj,两式联立可得：“T0Tk-1”= “Tj-kTj-1”,注意：j为当前已知的失配位置，我们的目标是计算新起点k。式中仅剩一个未知数k，理论上已可解！,奇妙的结果：k仅与模式串T有关！,28,根据模式串T的规律：“T0Tk-1”=“Tj-k Tj-1” 由当前失配位置j(已知)，归纳计算新起点k的表达式。,新起点k怎么求？,nextj=,0 当j=1时 max k|1kj且T0Tk-1=Tj-k Tj-1 1 其他情况,注意： (1)k值仅取决于模式串本身而与相匹配的主串无关。 (2)k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。 (3)这里两部分子串可以有部分重叠的字符，但不可以全部重叠。,令k = nextj（k与j显然具有函数关系），则,取T首与Tj处最大的相同子串,29,nextj函数表示模式T中最大相同前缀子串和后缀子串（真子串）的长度。 可见，模式中相似部分越多，则nextj函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。 即：nextj越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。,30,i、j分别为指示s(目标串)和t(模式串)的指针，初值均为1。 若 si = tj，则i和j分别增1； 否则，i不变，j退回至j=nextj的位置(即串s不动，模式串t向右移动到 si与tnextj 对齐)； 比较 si 和 tj。若相等则指针各增1；否则j再退回到下一个j=nextj的位置(即模式串继续向右移动)，再比较 si 和 tj 。,KMP算法的基本思想,依次类推，直到下列两种情况之一： 1)j退回到某个j=nextj时有 si = tj，则指针各增1，继续匹配； 2)j退回至j=0，此时令指针各增1，即下一次比较 si+1和 t0 。,31,串的模式匹配：KMP算法,模式串的next函数 意义：j之前的子串中，左起一段=右起一段，最长可以到k,32,串的模式匹配：KMP算法,例如：,33,串的模式匹配：KMP算法,此次匹配失败 让 j = nextj = 3,34,KMP算法,理解 Si!=Tj，说明i之前的字符都匹配 则S45=T45 nextj=3，说明T12=T45 因此T12=S45,S T,35,KMP算法,疑问1：子串T会不会向前走得太多了？ 假设只向前走一个字节可不可能呢？ 如果可以的话，则T14=S25 而刚才已知T15=S15 则S14=S25 也就是T14=T25 那么next6=5，和已知的next6=3矛盾！,S T,36,KMP算法,同理：向前走2个字节也不可能 如果可以的话，则T13=S35 而刚才已知T15=S15 则S13=S35 也就是T13=T35 那么next6=4，和已知的next6=3矛盾！,S T,37,KMP算法,S T,疑问2：可不可以多向前走一些呢？ 主串往往很长，不可能全部分析 因此只能通过分析子串来分析主串 而目前最多知道T12匹配S45 并不能保证T1匹配S5,38,串的模式匹配：KMP算法,next函数的计算 一个递归的过程： 已知 next1=0 若 nextj=k 说明有 p1.pk-1=pj-k+1.pj-1 若pk=pj，则nextj+1=k+1 若pk!=pj，令k=nextk 若pk=pj，则nextj+1=k+1 若pk!=pj，则尝试nextk.,39,串的模式匹配：KMP算法,分析 首先next1=0 假设已知nextj=k nextj+1=?,6,?,40,串的模式匹配：KMP算法,分析 若Tk=Tj 则nextj+1=k+1,7,41,串的模式匹配：KMP算法,分析 若Tk!=Tj 令k=nextk 若Tk=Tj，则nextj+1=k+1,4,42,串的模式匹配：KMP算法,为什么令k=nextk？ next12=6，说明T15=T711 k=nextk=3，说明T12=T45 则T12=T1011 若又有T