数据结构(C语言版)严尉敏编 第4章课件.ppt

4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 4.5 本章小结 4.6 习题四,4.1 基本概念及串类型的定义 串类型的定义 串、串名、串值、串的长度、空串、子串、主串、序号（位置）、串相等、空格串串(String)是由零个或多个字符组成的有限序列 一般记为：S=a1a2a3an，其中S 是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度长度为零的串称为空串(Empty String)，它不包含任何字符串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串特别地，空串是任意串的子串，任意串是其自身的子串通常称字符在序列中的序号为该字符在串中的位置子串在主串中的位置，则以子串的第一个字符在主串中的位置来表示例如：a,b,c,d为如下的4个串： a= BEI , b=JING c= BEIJING , d=BEI JING,它们的长度分别为：3,4,7和8；并且a和b都是c和d的子串，a在c和d中的位置都是1，而在b在c中的位置是4，在d中的位置是5 称两个字符串是相等的，当且仅当这两个串的值相等。

也就是说，只有当两个串的长度相等，且对应位置上的字符也都相等时才相等例如，上面的串a,b,c,d彼此都不相等由一个或多个空格组成的串被称为空格串空格串不是空串,例； 和不同串的逻辑结构和线性表极为相似，区别仅在于串的数据对象的类型限制为字符4.1.1 串的抽象数据类型的定义如下： ADT String 数据对象：D ai |aiCharacterSet, i=1,2,...,n, n0 数据关系： R1 | ai-1, ai D, i=2,...,n 基本操作：(13种） StrAssign ( 否则函数值为0 StrDelete ( m = StrLength(T); i = pos;,while ( i <= n-m+1), SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ;//返回子串在主串的位置 // while, // if return 0; // S中不存在与T相等的子串 // Index,,又如串的置换函数：,例如：,假设 S = abcaadbcaaabcaaas, T = bca,若 V = x, 则经置换后得到 S = axadxaaxaas ,若 V = bc, 则经置换后得到 S = abcadbcaabcaas,基本思想：,(1) News= pos=1 ;n= StrLength(S);m= StrLength(T);,(2) i=index(S,T,pos); if(i) SubString(sub,s,pos,i-pos); News=News+sub+V ; pos=i+m; ,(3) 重复（2）直到posn-m+1;或i==0; (4) SubString(sub,S,pos,n-pos+1); News=News+sub;,void replace(String m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,while ( pos <= n-m+1 //pos向后滑动m个位置 //if //while,SubString(sub, S, pos, n-pos+1); // 剩余串 Concat( S, news, sub ); // replace,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别 性表的基本操作中，大多以单个元素作为操作对象； 在串的基本操作中，通常以串的整体作为操作对象4.2 串的表示和实现,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可但在多数非数值处理的程序中，串也以变量的形式出现4.2.1 串的定长顺序存储表示,#define MAXSTRLEN 255 // 用户可在255以内定义最大串长度 typedef unsigned char SstringMAXSTRLEN + 1; // 0号单元存放串的长度,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为截断 按这种串的表示方法实现的串的运算时，其基本操作为 字符序列的复制 对于串的长度有两种表示方法：一是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，（如：PASCAL），二是在串值后面加一个不计入串长的结束标记字符（如：C中以0表示串的终结）以下的例子中我们用第一种方法显式的表示串的长度,4.2.1 在定长顺序存储结构上操作的实现,1.串联接 Concat ( TS10+1..S10+S20 = S21..S20; T0 = S10+S20; uncut = TRUE; ,else if (S10

所以也称为动态存储分配的顺序表在C语言中，利用动态存储管理函数malloc( ) 和 free( )根据实际需要动态分配和释放字符数组空间,进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为堆串的堆分配存储表示----------------------- typedef struct char *ch; // 若是非空串，则按串长分配存储区， //否则 ch 为NULL int length;//串长度 HString ;,这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制堆存储分配下时,操作的实现:,HString s,P75算法4.4 插入 基本思想：为S重新分配存储，然后复制； Status StrInsert (Hstring // StrInsert,Status StrAssign(Hstring T, char *chars) //生成一个其值等于串常量chars的串T if(T.ch) free(T.ch);//释放原空间 for(i=0, c=chars; *c ; ++i, ++c); //求串长 if ( !i ) T.ch=NULL; T.length=0; //空串 else if(!(T.ch=(char *)malloc(i*sizeof(char))))//申请存储 exit(overflow); T.ch0..i-1=chars0..i-1; //复制 T.length=i; return OK; // StrAssign,int StrCompare(Hstring S, Hstring T) //ST，返回值0；S==T，返回值0 ；S

因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串 typedef struct node char data; struct node *next; LString; 一个链串由头指针唯一确定这种结构便于进行插入和删除运算，但存储空间利用率太低为了提高存储密度，可使每个结点存放多个字符通常将结点数据域存放的字符个数定义为结点大小，结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结如下图所示：,#define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk // 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 LString; 实际应用时，可以根据问题所需来设置结点的大小例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。

即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接4.3 串的模式匹配算法,4.3.1 求子串位置的定位函数index(S,T,pos) 子串的定位操作通常称做串的模式匹配（其中T称为模式串），是各种串处理系统中的重要操作之一下面给出采用定长顺序存储结构下不依赖于其他串操作的匹配算法 下面讨论以定长顺序结构表示串时的几种模式匹配算法1.简单算法 2.KMP(D.E.Knuth,V.R.Pratt,J.H.Morris) 算法 3.首尾匹配算法,1.简单算法----基本思想：同P72算法4.1 ,回忆一下,例：S=ababcabcacbab T=abcac pos=1,,int Index(SString S, SString T, int pos) // 返回子串T在主串S中第pos个字符之后的位置若不存在， //则函数值为0 其中，T非空，1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; // j=T0+1 ; i-k+1=j ; else return 0; // k=i-T0 // Index,算法优点：算法简单，易懂！,算法缺点：主串指针回溯次数多，算法执行效率低！ 特别是出现子串与主串的较长部分匹配 时，更低！,例如： S=000000000000000000001 T=0000001,,解决办法：考虑回溯有没有必要，改进算法！,前面的例子：第三趟,i指针不用回溯，而是将模式串向右滑动多少 （适当）个字符。

适当的意义？,假设主串S=S1S2S3Sn ，模式串P=P1P2Pm ，在主串中的第i个字符和模式串中的第j个字符比较时失配，即SiPj S1S2S3Si-j+1Si-j+2Si-2Si-1SiSn = 。