数据结构与算法(C++语言版)串讲

数据结构与算法（C++语言版）第4章串•现实世界中的实体有多种形式，如数值、文字符号序列、图形、图像、声音等，其中文字（符号）序列称为字符串，简称串。串是一种常用的数据结构，用于描述非数值的简单信息，它在现实世界中屡见不鲜，如人名、产品名、事物名称、车牌号、文献、源程序等。从数据元素间的逻辑关系看，串是线性表，但从操作方式与种类看，它与线性表有许多不同。在计算机中，串被认为是一种特殊的线性表——元素为文字符号的线性表。由于现实问题中经常使用串，所以对串应选择合适的存储结构，并提供灵活多样的基本操作。串的逻辑结构•基本概念•串（string）是由零个或多个字符构成的有限序列，一般记为s=‘s1s2…sn’（n≥0）。其中，s是串名，用单引号括起来的字符序列是串的值，但单引号本身并不属于串，si（1≤i≤n）为一个字符，字符是计算机可识别的任意符号（字母、数字或其他符号）。•串的长度：串中字符的数目n。•空串：零个字符的串，其长度为零。•空白串：由一个或多个空格组成的串，其长度为串中空格字符的个数。•子串：串中任意个连续的字符组成的子序列。•主串：包含子串的串相应地称为主串。串的逻辑结构•字符在串中的位置：字符在序列中的序号。•串相等：当且仅当这两个串的值相等，即两个串的长度相等，并且各个对应位置的字符都相等。•通常，在程序中使用的串可分为两类：串变量和串常量。串变量和其他类型的变量一样，其取值是可改变的。串常量和常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。例4-1•假设a、b、c、d为如下的4个串：a=‘Guang’，b=‘Zhou’，c=‘GuangZhou’，d=‘GuangZhou’。它们的长度分别为5、4、9、10；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在c中的位置是6，在d中的位置是7；a、b、c、d彼此都不相等。•显然，若某串的长度为n，则在该串中，长度为1的子串的个数为n，长度为2的子串的个数为n1，……，长度为i的子串的个数为n(i1)，所以长度为n的串中子串总数（包括空串与自身）为1+=1+。串的抽象数据类型定义见以下ADT。例4-1例4-1例4-1串的逻辑结构•串的大小比较•字符的大小•在计算机中，每个字符都有一个唯一的数值表示——字符编码（字符内码），字符间的大小关系就定义为它们的代码之间的大小关系。字符编码可有多种，对英文字母和符号，ASCII码是最常见的一种。本书用字符的ASCII码之间的大小关系代表相应字符的大小关系。•ASCII码即美国信息交换标准编码，是长度为8位二进制符号，所以最多能编28=256个不同的字符。但ASCII码中规定，最高位为1的码代表一些特殊的字符（或命令），所以ASCII码有效的字符编码为128个，其包括英文大、小写字母，数字0～9及一些常用符号（计算机键盘上的字符键）。在字符和数字中，空格编码最小，其次是数字（按0～9的次序）、大写字母（按A～Z的次序）、小写字母（按a～z的次序）等。串的逻辑结构•对于汉字，它们的大小关系也按编码大小确定。汉字的编码也有几种，如我国内地用的国标码（GB2312），我国台湾地区用的Big5等。GB2312（国标码）是针对汉字的16位二进制编码，所以最多能编216=65536个不同的码，足以代表新华字典中所有的汉字。GB2312将汉字分为两级编码，分别称一级字库和二级字库。一级字库包括了日常用的大多数汉字，其汉字的国标码之间的大小关系，与对应的汉语拼音构成的串的大小关系一致（在新华字典中，排在较前面的字，它的国标码也较小）。而二级字库中的汉字码之间的大小关系，与对应汉字的笔画数目的大小关系一致。•要在一个系统中混合使用多种文字，需要一种统一的编码系统，它可以将各种文字的基本字符在同一空间内编码，UniCode就是这样一种编码。串的逻辑结构•字符串间的大小关系•有了字符大小的定义，就可考虑串的大小关系了。设X与Y是两个串，X=‘x1x2…xm’，Y=‘y1y2…yn’，则它们之间的大小关系定义如下。•①当m=n且x1=y1,…,xm=yn时，称X=Y。•②当下列条件之一成立时，称X＜Y：•i．mn，且xi=yi，i=1,2,…,m；•ii．存在某一个k≤MIN(m,n)，使得xi=yi，i=1,2,…,k–1，xk＜yk。•③当不属于情况①与②时，称X＞Y。这种方法定义的串的大小关系，也称字典序。下面给出几个例子说明此定义：‘abac’与‘abac’，相等（=）；‘we’与‘web’，前者小于后者（属于情况i）；‘mouth’与‘move’，前者小于后者（属于情况ii）串的存储结构•与线性表类似，串也有两种基本的存储结构：顺序结构与链式结构。考虑到存储效率与算法实现的方便性，串多采用顺序存储结构。•顺序存储•串的顺序存储结构简称为顺序串。与顺序表类似，顺序串用一组地址连续的存储单元来存储串中的字符序列，可用高级程序语言中字符数组来实现。按存储分配的不同可将顺序串分为静态存储分配的顺序串和动态存储分配的顺序串。串的存储结构•链式存储•用单链表方式存储串的值，这种存储结构简称为链串，链串分为两种形式。①非压缩形式。一个链表结点只存储一个字符。为了操作方便，设置一个指向首元素结点的指针和一个指向尾元素结点的指针，同时仍设置串长度值字段。这种结构类似于线性表的链式存储，其优点是操作方便，但存储利用率很低。②压缩形式。一个链结点存储多个字符，实质上是一种连续存储与链式相结合的结构。这种结构能提高存储利用率，但其对应的操作实现起来较为复杂。例如，在对串长度进行修改时，常涉及链结点的增加与删除操作，如果仅允许不满的结点出现在最后一个结点上，则需要经常移动字符，但如果允许不满结点出现在其他位置，则又会造成串的表示不一致的问题，也会使操作实现复杂化。串函数与串的类定义•常用的C++串函数•C++的串库（string.h）中提供了许多字符串的操作函数，几个常用的C++字符串函数及其使用方法如下。•假设已有以下定义语句：串函数与串的类定义•（1）串拷贝函数•char*strcpy(char*s1,constchar*s2)，将字符串s2复制到字符串数组s1中，返回s1的值。•char*strncpy(char*s1,constchar*s2,size_tn)将字符串s2中最多n个字符复制到字符串数组s1中，返回s1的值。•例如：串函数与串的类定义•（2）串连接函数•char*strcat(char*s1,constchar*s2)，将字符串s2添加到字符串s1的后面，s2的第一个字符重定义s1的null终止符，返回s1的值。•char*strncat(char*s1,constchar*s2,size_tn)将字符串s2中最多n个字符添加到字符串s1的后面，s2的第一个字符重定义s1的null终止符，返回s1的值。•例如：串函数与串的类定义•（3）串比较函数•intstrcmp(constchar*s1,constchar*s2)，比较字符串s1和字符串s2。函数在s1等于、小于或大于s2时，分别返回0、小于0或者大于0的值。•intstrncmp(constchar*s1,constchar*s2,size_tn)比较字符串s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2时，分别返回0、小于0或者大于0的值。•例如：串函数与串的类定义•（4）串长度函数•size_strlen(constchar*s)，确定字符串长度，返回null终止符之前的字符数。例如：•（5）串中字符定位串函数与串的类定义•串的类定义•C++语言提供的丰富的串函数库有很强的串操作功能，但对于一般使用者来说，其使用起来不是很方便。在一些高级程序设计语言中，两个串可用“+”连接，可用赋值号把一个串赋值给另一个串，两个串的比较可直接用“”、“”、“==”等比较运算符。这里可使用重载操作符的办法，使C++语言中的一些运算符具有新的功能。以下程序给出串的类定义。串函数与串的类定义例4-2•求子串算法substr。例4-3•串以链式形式存放的算法。例4-3例4-4•将node串q所指结点中第p个字符后的第i个有效字符送至r。q指针如下图所示。例4-4串模式匹配•这里介绍一个很重要的操作——StrStr的实现，该操作与Index(S,T,pos)一样，也叫串模式匹配。给定两个串T与P：T=‘t0t1…tn–1’，P=‘p0p1…pm–1’，其中0＜m≤n，将在T中寻找最先出现的一个与P相同的子串的过程称为串模式匹配，称T为目标串（主串），P称为模式串（子串），下面介绍的StrStr()函数就属于串模式匹配。•串模式匹配在符号处理中占有十分重要的地位，它是基于规则匹配的逻辑推理的（如Prolog语言的目标执行过程、专家系统中的推理机），所以它的效率十分重要。这里先介绍一种简单的匹配算法，它的时间复杂度较高，然后介绍它的一种改进算法。串模式匹配•简单串模式匹配算法•以下程序是一种带回溯的匹配算法。首先将子串P视为从主串T中第1个字符起与T对齐，从头起依次比较对应字符；若全部对应相等，则表明已匹配成功，终止；否则，将P视为从T中第2个字符起与T对齐，再从头比较对应字符；过程与前类似，如此进行，直至某次匹配成功，或某次T中无足够的剩余字符与P对齐（不能匹配，失败）。串模式匹配•实现时，设置三个指示器i，j，ii，它们的含义如下。•i：指向主串T中当前参加比较的字符。起始时，指向T的首字符，之后，每比较一次，后移一步，一趟匹配失败时，回溯到该趟比较起点的下一位置。•j：指向子串P中当前参加比较的字符。起始时，指向T的首字符，之后，每比较一次，后移一步，一趟匹配失败时，回溯到P的首字符处。•ii：记录每趟比较在主串T中的起点，每趟比较后，后移一步。串模式匹配串模式匹配•下面分析此算法的时间复杂度。显然，此算法的主要工作是do循环，它的循环次数与目标串及模式串相关，所以时间复杂度是个随机量。最理想的情况是，第一趟就得到匹配，此时的循环次数为n（即子串s的长度），而最坏的情况是不存在匹配，且每趟匹配过程都在比较完子串s中最后一个字符时才发现不能匹配，此种情况的循环次数是(m–n+1)×n，这里m为主串的长度。显然，n越大，此式的值越小。当n＜＜m时，此式约等于m×n。串模式匹配•无回溯的匹配算法•在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹配相当于将子串P后移1位再从头与主串中对应字符进行比较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配的起点的下一个位置，这样，主串中每个字符都要与子串中的第1个字符对应一次，再向后比较。因此，主串中每个字符参加比较的次数最多可达n次（n为子串长度），因此时间复杂度为O(nm)。那么，能否使目标串中每个字符只参加一次比较呢？也就是说，能否不回溯i指示器？回答是肯定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时解决的，所以有的文献也称这种思想的串匹配算法为KMP算法。串模式匹配•i指示器之所以可不回溯，是因为重新开始一趟匹配时，可利用上趟匹配的结果。一般而言，一个无回溯匹配法的关键问题是，在匹配过程中一旦发现pj与ti不等，应能确定出从P中的哪个字符起与ti（或ti+1）对齐继续往下比较。这里记这个字符为pk，显然k＜j，且对不同的i，k也不同。Knoth等人发现这个k值仅仅依赖于子串P的前i个字符的构成，而与主串T无关。这是个令人鼓舞的发现，它是实现无回溯的关键。可用一个函数next表示j与k的这种对应关系，它是仅与子串有关的函数，其含义是，在匹配过程中，一旦发现一对不等的字符（设为pj与ti），若next(j)=k（k≥0），则下次的比较应从P中的pk起与T中的ti对齐往下进行；若next(j)＜0，则P中任何字符不必再与ti进行比较，下次比较从P的首字符起与ti+1对齐往下进行。next(j)的取值，应首先保证使匹配过程无遗漏（即不放过任何可能的匹配），其次，应使P串向