【精品数据结构】字符串

1、第4章 字符串,4.2 字符串的存储方式,4.3 字符串的模式匹配算法,4.4 本章小结,4.1 字符串的基本概念,4.1 字符串的基本概念,1. 基本概念 字符串：字符组成的有限序列，用一对双引号的分界符括起来 。 字符串的长度：字符串中包含的字符数目。 空字符串：简称空串，长度为零的字符串。可用“”表示。,请注意：字符的界符为单引号,子串：一个串中的任意连续字符组成的子序列。 主串:相应的，称包含子串的那个串为主串。 字符在串中的位置：指该字符在字符序列中的位置。 串相等：长度相等，并且这两个串对应位置上的字符全部相等。 2.串的ADT声明 从逻辑结构上看，串非常类似于线性表；在基本操作上

2、，串与线性表有较大的区别：,ADT String 数据对象内容限定为字符集合： D=ai | ai 字符集合，i=1,2, ,n , n0 数据间的线性关系： R=| ai D，i=1,2, ,n-1 几种基本操作： strAssign ( char *content; void strCopy(int offset1, char *origin, int offset2, int len); public: FLString(); FLString(char *origin);,从字符数组origin偏移量为offset2的字符开始，连续拷贝len个字符到本串从偏移量offset1处开始的地

3、方,构造函数，用于创建一个空串,构造函数，由origin字符数组的内容构造串,int strCompare(FLString str); int strLength(); bool strConcatenate(FLString str1, FLString str2);,/当前串与串str比较大小,当前串与串str比较大小,将串str1与串str2拼接后存入当前串中,bool strSubstring(int pos, int len, FLString ,从当前串偏移量为offset的字符开始，将长度为len的一段连续字符复制到串sub中,串的清空操作,析构函数，用于销毁串,定长顺序存储表

4、示的不足： 只要在操作中发现字符串长度大于预定义的最大容量，就采取“截断”的方法，这样操作的结果会引起信息的损失。 如果字符串长度远远小于预定义的最大容量，则又会浪费空间。,改进方法： 不再事先预定好串的存储空间，而是根据串的大小实时分配空间。这种更灵活的连续存储方式就是“堆分配存储表示”。,4.2.2 串的堆分配存储表示,基本思想： “按需分配”。 当字符串有效内容的长度发生变化，原来的空间就会释放掉，同时重新开辟一个和新内容长度一样的字符数组来存储新的字符串。,串的“堆分配存储表示” 与“定长顺序存储表示 ”同属采用数组进行的连续存储方式，实现方法类似，其区别体现在以下方法的实现过程：,/

5、HeapString.h class HString private: . public: /构造函数，用于创建一个空串 HString(); /构造函数，由origin字符数组的内容构造串 HString(char *origin);,/当前串与串str比较大小 int strCompare(HString str); . /将串str1与串str2拼接后存入当前串中 void strConcatenate(HString str1, HString str2); /从当前串偏移量为offset的字符开始，将长度为len的一段连续字符复制到串sub中 void strSubstring(in

6、t pos, int len, HString ,顺序存储表示小结： 对于以数组连续存储的字符串来说，其实现一种是预先定义好的定长方式，即定长存储，其特点在于：灵活性较差，但是较简单； 另一种方式则是根据字符串长度动态分配的，即堆分配存储，其特点在于：不会造成空间的浪费，但实现的时候要麻烦一些。,说明： 上面两种方式在实现时都使用了内存的动态分配方式，是在运行时为相应的变量分配的空间；相对应的，在编译时就已经能够确定变量存储空间大小的，叫做内存的静态分配方式。,4.2.3 块链存储表示,基本思想： 按照链表的方式进行存储 。 考虑使用链表后，指针所占的空间会增加一定的空间开销。因此，为了减少开

7、销，应该尽量做到在一个节点中多存储一些字符。这时，节点当中好像存储的是一“块”数据，而不再是一“个”数据，所以形象地称其为“块链”。,引入“存储密度”这个概念来衡量开销的大小： 存储密度=串中内容所占的存储位/实际分配的存储位 节点大小不同的块链存储方式:,块链存储方式表示的优劣分析： 优点：存取灵活 不足：空间开销相对较大，而且实现也是相当复杂繁琐的。,一般只有在特殊的应用场合（如所处理的字符串平均长度非常大时）才会使用块链存储。,4.3 字符串的模式匹配算法,4.3.1 串模式匹配的基本算法 4.3.2 串模式匹配的改进算法,关于串的模式匹配的相关术语： 字符串的模式匹配：在目标区域内的字

8、符串中进行从前到后的扫描，看有没有一段连续的字符与待查找的字符串完全匹配。 其中： 主串：查找的目标区域的字符串。 模式：相应地，待查找的串可以称为“模式”。,4.3.1 串模式匹配的基本算法,匹配算法功能： 找到在主串中第一次出现模式串的位置。,基本思想： 模式串从字符串首位置开始，依次与主串相应位置比较，不成功则整体后移一位。即对于主串来说，第一趟从第一个字符开始，第二趟从第二个字符开始，依此类推。,分析可知： 如果主串长度为m，模式串长度为n，则最多的比较趟数为m-n+1。在最差情况下，这种算法的复杂度为(m-n+1)*n，属于O(N2)级别。,4.3.2 串模式匹配的改进算法,串模式匹

9、配的基本算法简单易懂，但是由于某趟比较失败而进入下一趟比较时，主串有可能会回退到以前比较过的某个字符以便重新和模式串比较，这就在很大程度上影响了算法的效率。 为解决主串的回退问题，可以对算法进行改进：,假设主串为s=s1s2sm-1sm，模式串为t=t1t2tn-1tn，其中si（1im）和tj（1jn）都是字符元素，在图4.5中描述了匹配过程中字符串的比较情况。,引入标记nextq表示：当模式串偏移量为q的字符与主串字符比较不等时，应该用模式串偏移量为newq的字符与主串原字符比较。则有：,串模式匹配的改进算法实例：,此改进算法是由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，我们简称此算法为KMP算法。由于匹配过程中主串不会出现回退的情况，所以此算法的算法复杂度的数量级为O（m+n），其中m和n分别为主串与模式串的长度。,4.4 本章小结,基本内容： 1.字符串的基本概念 2. 字符串的三种表示形式及相应的典型操作的实现 3. 字符串的基本模式匹配算法及其改进