《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第四章 串》由会员分享，可在线阅读，更多相关《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第四章 串（25页珍藏版）》请在金锄头文库上搜索。
1、第四章 串,知识教学目标,串的基本概念及串运算函数 串的顺序存储和链式存储 字串定位运算的实现,能力培养目标,串的有关概念和操作 常见C语言串的运算函数 串的存储结构 子串定位运算,4.1 串及其运算,字符串（string）简称串，是一种特殊的线性表，其特殊性主要在于该线性表中的每个结点都是一个字符，故可将字符串定义为由零个或多个字符组成的一个有限序列，一般记为： s =“a1a2a3an” （n0） 其中，s为串的名称；用双引号扩起来的字符序列a1a2a3an是串的值，但引号本身不属于串的内容，它的作用是避免串与常数或标识符相混淆；ai（1 i n）是任意一个字符，称为串的元素，是构成串的基
2、本单位，i为它在整个串中的序号。,4.1.2 串的基本运算,有关串的基本运算主要有： 1) 求串的长度len（s）：返回串s的长度，即串s中所包含的字符个数。 2) 串赋值assign(s,t)：将串t的值赋给串s。 3) 串相等判断equal(s,t)：若串s和串t相等，则函数返回true，否则返回false。 4) 串连接concat(s,t)：串s和串t连接成一个新串，并赋值给串s。 5) 求子串sub(s,start,len,t):当s存在，0startlen(s)，0lenlen(s)start，子串t的值为从串s中第start个字符起，长度为len的字符序列。,6) 子串定位ind
3、ex(s,t)：若主串s中存在和t相等的子串，则返回它在主串s中第一次出现的位置，否则返回0。 7) 置换replace(s,t,v)：用串v置换串s中出现的所有与串t相同的不重叠子串。 8) 子串的插入insert(s,i,t)：当串s和t存在，1ilen(s)+1时，在串s中第i个字符前插入串t。 9) 子串的删除delete(s,i,j)：当串s存在，1ilen(s)j+1时，从串s中删除第i个字符起长度为j的子串。,4.2 串的存储结构,由于串是元素为字符的特殊线性表，因此，其存储结构与线性表的存储结构类似，也可以分别采用顺序存储结构和链式存储结构。但因为字符的特殊性和串经常被作为一个
4、整体来处理的特点，所以串在存储时还有一些特殊技巧。,4.2.1 串的顺序存储,1. 非紧缩格式 在这种格式下，由于一个存储单元仅仅存放一个字符，因而比较浪费存储空间，但它简化了对串的运算。,2. 紧缩格式 为了节省存储空间，也可以用紧缩格式来存储串，即在一个存储单元中存放多个字符，如图4.2所示，在一个存储单元中存放4个字符。,3. 单字节存储方式 有的计算机是以字节进行编址的，其存取的单位是字节。而一个字符正好占一个字节，这就自然形成了每个存储单元存放一个字符的分配方式。,4.2.2 串的链式存储,1数据域为单个字符 2结点的大小为K(K1),其类型定义如下： #define NodeSiz
5、e 4 /结点大小，由用户指定，这里为4 typedef struct node char dataNodeSize; /结点数据域为数组，存放NodeSize个字符 struct node * next; LinkStrNode;,4.3 串运算的实现,顺序存储结构的串的数据类型可定义为： define MaxSize 100 /假定串的最大容量为100 struct string char chMaxSize; /存放串值的一维数组 int curlen; /当前串的长度 SeqString;,串的基本运算的算法如下： 【算法4.1】 串的赋值。 void assign(SeqString
6、 *s,SeqString *t) /将串t的字符逐个赋给串s。 for (int j=0;jcurlen;j+) s-chj=t-chj; s-curlen=t-curlen; ,【算法4.2】 求串的长度。 所谓求串的长度，就是求出串中包括字符的个数。 int len（SeqString *s） return s-curlen; ,【算法4.3】 串相等判断。 要判断两个串是否相等，首先要看两个串的长度是否相等，若长度相等，再看对应位置上的字符是否相等。 int equal(SeqString *s,SeqString *t) int i; if ( s-curlen != t-curlr
7、n ) return (0); for (i=0;icurlen;i+) if ( s-chi != t-chi ) return (0); return (1); ,【算法4.4】 串连接。 串连接就是将两个串s和t首尾相连，构成一个新串。 int concat(SeqString *s,SeqString *t) int i; if (s-curlen+t-curlen) return (0); for ( i=0;icurlen;i+) s-chs-curlen + i = t-chi; s-curlen = s-curlen + t-curlen; return (1); ,【算法4.
8、5】 求子串。 求从s所指的串中第start（start0）个字符开始连续取len个字符所构成的子串，并保存在t中。 int sub(SeqString *s,int start,int len,SeqString *t) int i; if ( start (s-curlen) ) return (0); if ( len (s-curlen) ) return (0); for (i=0;ichi=s-chstart+i; t-curlen=len; return (1); ,【算法4.6】 子串的插入。 将t所指的串插入到s所指的串中（从第i个字符开始插入）。 int insert(Se
9、qString *s,int i,SeqString *t) int j; if (s-curlen)+(t-curlen)MaxSize) return (0); for (j=s-curlen;j=i;j-) s-chj+t-curlen = s-chj; /字符后移 for (j=1;jcurlen;j+) s-chj+i-1=t-chj; /插入字符 s-curlen = s-curlen + t-curlen; return (1); ,【算法4.7】 子串的删除。 在s所指的串中，将从第i个开始，长度为j的子串删除掉。 int delete(SeqString *s,int i,i
10、nt j) int k; if ( is-curlen) return (0); if ( s-curlen-i+1curlen = i-1; /当被删除子串在主串的最后位置，此时不需要移动元素即可直接删除 else for (k=i+j;kcurlen;k+) s-chk-j=s-chk; s-curlen=s-curlen-j; return (1); ,*4.4 串的模式匹配运算,4.4.1有回溯的模式匹配算法（BF算法） 【算法4.8】 BF算法。 int index_BF(SeqString *s,SeqString *t) int i=0,j=0; /i和j分别指向主串s和模式串t
11、中当前正待比较的字符位置 if (s-curlen=0)|(t-curlens-curlen) return 0; /操作非法 while (icurlen) ,4.4.2 无回溯的模式匹配算法（KMP算法）,该算法由Knuth、Morris和Pratt同时发现，因而称为KMP算法，是对BF算法的改进，其基本思路为：每当依次匹配中出现字符不相等时，主串的指针i不需要回溯到原位置加1处，而是利用已经得到的“部分匹配”的结果将模式串向后滑动尽可能远的距离后，继续进行比较。,【算法4.9】 求next 值的算法。 void get_next(SeqString *t,int next,int n)
12、int j,k; j=0; k=-1; next0=-1; while(jchj = t-chk ) j+; k+; nextj=k; else k=nextk; ,【算法4.10】 KMP算法。 int index_KMP(SeqString *s,SeqString *t,int next) int i=0,j=0; if (s-curlen=0)|(t-curlens-curlen) return 0; while ( icurlen) ,4.5 本章小结,串是一种数据类型受到限制的特殊线性表，它规定表中的每一个元素类型只能为字符。一个串所包含字符的个数称为串的长度，长度为零的串称为空串。应注意的是空格也是合法的字符，只有空格的串称为空格串，它不是空串。 串的存储结构主要有顺序存储结构和链式存储结构两种。顺序存储结构的缺点是不便于进行串的插入、删除运算。对于插入、删除运算较多的情况适合于采用链式存储结构。 串的匹配运算是一个比较复杂的串操作，它就是判断某串是否是另一已知串的子串，如是其子串，则给出该串的起始点。该算法在文本编辑程序中经常用到，提出该问题的有效算法能大大提高编辑程序的响应性能。,
