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

例4-3串以链式形式存放的算法。例4-3将node串q所指结点中第p个字符后的第i个有效字符送至r。q指针如下图所示。例4-4例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，它们的含义如下。A指向主串T中当前参加比较的字符。起始时，指向T的首字符，之后，每比较一次，后移一步，一趟匹配失败时，回溯到该趟比较起点的下一位置。B指向子串P中当前参加比较的字符。起始时，指向T的首字符，之后，每比较一次，后移一步，一趟匹配失败时，回溯到P的首字符处。Cii：记录每趟比较在主串T中的起点，每趟比较后，后移一步。D串模式匹配串模式匹配***********数据结构与算法

（C++语言版）第4章串现实世界中的实体有多种形式，如数值、文字符号序列、图形、图像、声音等，其中文字（符号）序列称为字符串，简称串。串是一种常用的数据结构，用于描述非数值的简单信息，它在现实世界中屡见不鲜，如人名、产品名、事物名称、车牌号、文献、源程序等。从数据元素间的逻辑关系看，串是线性表，但从操作方式与种类看，它与线性表有许多不同。在计算机中，串被认为是一种特殊的线性表——元素为文字符号的线性表。由于现实问题中经常使用串，所以对串应选择合适的存储结构，并提供灵活多样的基本操作。串的逻辑结构基本概念串（string）是由零个或多个字符构成的有限序列，一般记为s=‘s1s2…sn’（n≥0）。其中，s是串名，用单引号括起来的字符序列是串的值，但单引号本身并不属于串，si（1≤i≤n）为一个字符，字符是计算机可识别的任意符号（字母、数字或其他符号）。串的长度：串中字符的数目n。空串：零个字符的串，其长度为零。空白串：由一个或多个空格组成的串，其长度为串中空格字符的个数。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。字符在串中的位置：字符在序列中的序号。01串相等：当且仅当这两个串的值相等，即两个串的长度相等，并且各个对应位置的字符都相等。01通常，在程序中使用的串可分为两类：串变量和串常量。串变量和其他类型的变量一样，其取值是可改变的。串常量和常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。01串的逻辑结构假设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例4-1串的大小比较1字符的大小2在计算机中，每个字符都有一个唯一的数值表示——字符编码（字符内码），字符间的大小关系就定义为它们的代码之间的大小关系。字符编码可有多种，对英文字母和符号，ASCII码是最常见的一种。本书用字符的ASCII码之间的大小关系代表相应字符的大小关系。3ASCII码即美国信息交换标准编码，是长度为8位二进制符号，所以最多能编28=256个不同的字符。但ASCII码中规定，最高位为1的码代表一些特殊的字符（或命令），所以ASCII码有效的字符编码为128个，其包括英文大、小写字母，数字0～9及一些常用符号