《《数据结构》课件(C语言)第04章》由会员分享，可在线阅读，更多相关《《数据结构》课件(C语言)第04章（65页珍藏版）》请在金锄头文库上搜索。
1、第四章 串,数据结构,第2页,主要内容,串的逻辑结构 串的基本操作 串的链式存储结构 串的堆存出结构 串的顺序存储结构 静态结构存储串时的操作,第3页,主要内容, 静态结构存储串时的操作（Index函数） 朴素的模式匹配算法（BF算法） 改进的模式匹配算法（KMP算法） 求模式串next函数值的算法 求模式串next函数值的修正算法 next函数的性质 示例与模式匹配,7.模式匹配（重点）,第4页,第四章 串,串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。 本章将讨论串的有关概念、结构、存储方法和串的基本运算及其实现。,第5页,定义：串（String）是零个或多个字符组成的
2、 有限序列。 一般记为： S=a1a2an (n0). 术语 1）串名：S. 2）串值：a1a2an，ai(1in). 3）串的长度：串中所包含的字符个数，如串abcde的长度为5., 串的逻辑结构,第6页,4）空串：长度为0(n=0)的串，它不包含任何字符，记作S=(或S=). 5）空格串：由空格符(ASCII值32)组成的串，如S= .注意S= 与S=不同，前者是长度为1的非空串，它含有一个空格字符，而后者是长度为0的空串。 6）子串：串中任意个连续的字符组成的子序列。比如abcde中的bcd., 串的逻辑结构,第7页,用二元组的形式来定义串：串是一个二元组, string = ( D,
3、R ) 其中 D=ai|ai字符集,i=1,2,n,n0 R=N 有序偶的集合N=| ai-1,ai D, i=2,3,n 故串的逻辑结构和线性表极为相似。区别仅在D的定义上。线性表的数据对象可以是任意数据类型，而串的数据对象是字符集。 串是几种最简单的数据结构之一。, 串的逻辑结构,第8页,串虽然是一种特殊的线性表，但由于存储结构有所不同，故其基本操作也不同。 1、基本操作子集不同，比如串包含有联接、求子串等操作 2、操作对象不同，线性表的操作通常以数据元素或结点为操作对象，而串的操作主要以串的整体为操作对象。 1）赋值操作 Assign(s,t) s为串名，t为字符串变量。 Create(
4、s,ss) s为串名，ss为字符序列。 2）判等函数 Equal(s,t) 返回布尔值true或false.s,t可为非空串或空串。 3）求串长函数 Length(s) 返回串s字符的个数。 4）联接函数 Concat(s,t) 返回由串s,t相联接而成的新串。联接运算不满足交换律，但满足结合律。, 串的基本操作,第9页,5）求子串函数 Substr(S,start,len) 返回从串S中第start个字符起，长度为len的字符序列。 要求 1startLength(s)+1, 0len Length(s)-start+1. 6）定位函数 Index(s,t) 返回串t在串s中第一次出现时的串
5、首位置，若未出现，则返回值0，要求t不能是空串。 7）置换操作 Replace(s,t,v) 以串v替换所有在串s中出现的和非空串t相等的子串。, 串的基本操作,第10页, 串的基本操作,8）插入（前插）操作 Insert(s,pos,t) 在串s的第pos个字符之前插入串t. 要求1posLength(s)+1。 注. Insert(S,Length(s)+1,t) 与 Concat(s,t)功能相同， 即当pos= Length(s)+1时，t将插入至s的尾部之后。 9）删除操作 Delete(s,pos,len) 从串s中删去从第pos个字符起，长度为len的子串。要求 1posLeng
6、th(s)， 且1lenLength(s)-pos+1。 说明：可将1)至5)定义为串的基本操作，6)至9)可由基本操作加以实现。,第11页,示例1 用串的基本操作(1)至(5)实现定位函数Index(s,t)。 int Index( string s, string t ) /*若串s中存在和t相等的子串，则返回第一个子串在主串中的位置，否则返回零*/ n = Length(s); m = Length(t); i = 1; /m不等于0 while( i n-m+1 ) if( Equal( Substr( s, i, m ), t ) return i; else i+; return
7、0; /index, 串的基本操作,第12页,C中预定义字符串标准函数和标准过程 字符串标准函数 函数名 意 义 结果类型 strcat 连接字符串序列 char * strcpy 复制一个字符串 char * strlen 返回串的动态长度 int 还有：strcmp, strcmpi, strrchr, 参见： String.h, 串的基本操作,第13页,用线性链表的方式存储串值 结点大小问题, 串的链式存储结构,优点：便于实现插入、删除等操作 缺点：浪费存储空间，存储利用率最多1/2,优点：存储效率较高 缺点：实现插入、删除等操作较复杂,第14页,用块链结构存储串值 为便于进行串的操作，
8、当以链表存储串值时，给出头、尾指针，加当前串的长度。称如此定义的串存储结构为块链结构。 设尾指针的目的是为了便于进行联接操作。,块链结构的说明 #define CHUNK_SIZE 1000 /用户定义的结点大小 typedef struct char chCHUNK_SIZE; /块大小 chunk *next; /指针 chunk; typedef struct chunk *head，*tail; /头、尾指针 int length; /长度 LString; LString clst;, 串的链式存储结构,第15页,clst,15,D,A,T,A,S,T,R,U,C,T,U,R,E,S
9、,#,头,尾,长度,块链结构示意图, 串的链式存储结构,用块链结构存储串值,第16页,特点：每个串的串值各存储在一组地址连续的存储单元中，但它们的存储地址是在程序执行过程中动态分配而得。 typedef struct char *ch; int length; HString; 使用时必须分配(malloc)和回收(free)内存。, 串的堆存储结构,用堆结构存储串值,第17页,21,15, A STRING OF LENGTH 21F, DATA STRUCTURES ,Heap,s1,串的动态分配存储结构示意图,起始地址,起始地址,free,length ch,Free是指尚未分配内存地址
10、, 串的堆存储结构,s2,定义 HString s1 HString s2,第18页,1、赋值操作Assign(s,t),Status Assign( HString 算 法 4.9, 串的堆存储结构,第19页,2、联接运算Concat,Status Concat( HString /s2 , 串的堆存储结构,第20页,3、求子串函数Substr,Status SubStr( HString , 串的堆存储结构,第21页,用一组地址连续的存储单元来存储串的字符序列。 每个字符占用一个字节（Byte）。串中相邻的字符顺序地存放在相邻的字节中。, 串的定长顺序存储结构,定长顺序存储结构串定义： #
11、define maxlen 255 /允许最大的长度 typedef unsigned char Stringmaxlen+1; /下标0存放长度 实现：串的联接函数、 求子串的函数 、 求子串位置的定位函数,第22页,其中 L,s,t是String； 分析 相当于求L=s+t，若s与t连接后的串值长度超过maxlen，则 超过部分将被截断。运算结果有三种可能情况。 1) length(s) + length(t) maxlen,定长顺序存储时的操作,1、串的联接函数 Concat(L, s, t),第23页,定长顺序存储时的操作,2) length(s) + length(t) maxlen
12、而 length(s) maxlen 需将t的一部分截断，所得串L中包含s的全部与t的一个子串,第24页,3) length(s)=maxlen 得到的串L是s的串。,定长顺序存储时的操作,第25页,Status Concat( string / 算 法 4.2,定长顺序存储时的操作,第26页,分析 复制字符序列，若1startlength(s)+1且0lenlength(s)-start+1，则将串s从第start个字符起长度为len的子串赋给串sub,并返回函数值true，否则返回函数值false，而sub无确定值，为非法串。 Status Substr( string /substr 算
13、 法 4.3,定长顺序存储时的操作,2、求子串的函数 Substr(sub，s，start，len).,第27页,设有两个串 s = s1s2sn p = p1p2pm (0 0 （2）失败，Index(S,p) = 0 其中Index返回第一个模式为p的子串在主串s中的位置。,定长顺序存储时的操作,3、求子串位置的定位函数 Index(s,p),模式匹配算法，其中p为模式,第28页,定长顺序存储时的操作,3、求子串位置的定位函数 Index(s,p),使用串的基本操作(如Equal，Length，Substr等)实现求子串位置的定位函数Index(s,p)的算法： int Index( st
14、ring s, string p ) n = Length(S); m = Length(p); i = 1; while( i n m + 1 ) if( Equal(Substr(S,i,m),p) return i; else i+; return 0; /index,第29页,根据上面算法的基本思想，可以写出一种不依赖于其他串基本操作的模式匹配算法朴素的模式匹配算法（Brute-Force算法）。 BF算法的基本思想：用p中字符依次与s中字符比较，以指示器i,j分别指向s,p。初始时令i=1,j=1。 若有si=pj，则令i，j分别加1，继续比较。当j=(length(p)+1)，则匹
15、配成功，返回相应的位置值。 若在某时刻有sipj，则i回退到i-(j-1)+1=i-j+2处，令j=1，再进行逐个字符比较。 若直到ilength(s)时尚未匹配成功，则表示匹配失败,返回值0。,定长顺序存储时的操作,3、求子串位置的定位函数 Index(s,p),朴素的模式匹配算法（BF算法）,第30页,定长顺序存储时的操作,3、求子串位置的定位函数 Index(s,p),朴素的模式匹配算法（BF算法）,int Index_BF( string s, string p ) /求模式串t在主串s中位置的定位函数 i=1;j=1; /指针初始化 while( ilength(s) /index_BF 算 法 4.4,第31页,示例1 设s=ababcabcacbab,p=abcac，求函数Index_BF(s,p)的值。 算法Index_BF的匹配过程如下： 第一趟匹配 ababcabcacbab j 返回至1,i返回至i-j+2=3-3+2=2 abc j=3 第二趟匹配 ababcabcacbab j 返回至1, i返回至i-j+2=2-1+2=3 a j=1 第三趟匹配 ababcabcacbab j返回至1,i 返回至i-j+2=7-5+2=4 abcac j=5,i=3,i=2,i=7,朴
