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

《数据结构与算法(C语言版)串讲》由会员分享，可在线阅读，更多相关《数据结构与算法(C语言版)串讲（41页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法 （C+语言版）第4章 串现实世界中的实体有多种形式，如数值、文字符号序列、 图形、图像、声音等，其中文字（符号）序列称为字符串 ，简称串。串是一种常用的数据结构，用于描述非数值的 简单信息，它在现实世界中屡见不鲜，如人名、产品名、 事物名称、车牌号、文献、源程序等。从数据元素间的逻 辑关系看，串是线性表，但从操作方式与种类看，它与线 性表有许多不同。在计算机中，串被认为是一种特殊的线 性表元素为文字符号的线性表。由于现实问题中经常 使用串，所以对串应选择合适的存储结构，并提供灵活多 样的基本操作。串的逻辑结构基本概念 串（string）是由零个或多个字符构成的有限序列，一般记

2、为s=s1s2sn（n0）。其中，s是串名，用单引号括起来的 字符序列是串的值，但单引号本身并不属于串，si（1in ）为一个字符，字符是计算机可识别的任意符号（字母、 数字或其他符号）。 串的长度：串中字符的数目n。空串：零个字符的串，其长度为零。 空白串：由一个或多个空格组成的串，其长度为串中空格 字符的个数。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。串的逻辑结构字符在串中的位置：字符在序列中的序号。 串相等：当且仅当这两个串的值相等，即两个串的长度相 等，并且各个对应位置的字符都相等。 通常，在程序中使用的串可分为两类：串变量和串常量。 串变量和其他类

3、型的变量一样，其取值是可改变的。串常 量和常数一样，在程序中只能被引用但不能改变其值，即 只能读不能写。例4-1假设a、b、c、d为如下的4个串：a=Guang，b=Zhou， c=GuangZhou，d=Guang Zhou。它们的长度分别为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的子串的个数为n1，长度为i的子 串的个数为n(i1)，所以长度为n的串中子串总数（包括空 串与自身）为1+ =1+ 。串的抽象数据类型

4、定义 见以下ADT 。例4-1例4-1例4-1串的逻辑结构串的大小比较 字符的大小 在计算机中，每个字符都有一个唯一的数值表示字符 编码（字符内码），字符间的大小关系就定义为它们的代 码之间的大小关系。字符编码可有多种，对英文字母和符 号，ASCII码是最常见的一种。本书用字符的ASCII码之间 的大小关系代表相应字符的大小关系。 ASCII码即美国信息交换标准编码，是长度为8位二进制符 号，所以最多能编28=256个不同的字符。但ASCII码中规定 ，最高位为1的码代表一些特殊的字符（或命令），所以 ASCII码有效的字符编码为128个，其包括英文大、小写字 母，数字09及一些常用符号（计算

5、机键盘上的字符键） 。在字符和数字中，空格编码最小，其次是数字（按09 的次序）、大写字母（按AZ的次序）、小写字母（按a z的次序）等。串的逻辑结构对于汉字，它们的大小关系也按编码大小确定。汉字的编 码也有几种，如我国内地用的国标码（GB2312），我国台 湾地区用的Big5等。GB2312（国标码）是针对汉字的16位 二进制编码，所以最多能编216=65536个不同的码，足以代 表新华字典中所有的汉字。GB2312将汉字分为两级编码， 分别称一级字库和二级字库。一级字库包括了日常用的大 多数汉字，其汉字的国标码之间的大小关系，与对应的汉 语拼音构成的串的大小关系一致（在新华字典中，排在较

6、前面的字，它的国标码也较小）。而二级字库中的汉字码 之间的大小关系，与对应汉字的笔画数目的大小关系一致 。 要在一个系统中混合使用多种文字，需要一种统一的编码 系统，它可以将各种文字的基本字符在同一空间内编码， UniCode就是这样一种编码。串的逻辑结构字符串间的大小关系 有了字符大小的定义，就可考虑串的大小关系了。设X与Y 是两个串，X=x1 x2xm，Y=y1y2yn，则它们之间的大 小关系定义如下。 当m=n且x1=y1, , xm=yn时，称X=Y。 当下列条件之一成立时，称XY： im”、 “=”等比较运算符。这里可使用重载操作符的办法，使C+ 语言中的一些运算符具有新的功能。以下

7、程序给出串的类 定义。串函数与串的类定义例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=t0t1tn1，P=p0p1pm1，其中0mn，将在T中寻找 最先出现的一个与P相同的子串的过程称为串模式匹配，称 T为目标串（主串），P称为模式串（子串），下面介绍的 StrStr( )函数就属于串模式匹配。串模式匹配在符号处理中占有十分重要的地位，它

8、是基于 规则匹配的逻辑推理的（如Prolog语言的目标执行过程、专 家系统中的推理机），所以它的效率十分重要。这里先介 绍一种简单的匹配算法，它的时间复杂度较高，然后介绍 它的一种改进算法。串模式匹配简单串模式匹配算法 以下程序是一种带回溯的匹配算法。首先将子串P视为从主 串T中第1个字符起与T对齐，从头起依次比较对应字符；若 全部对应相等，则表明已匹配成功，终止；否则，将P视为 从T中第2个字符起与T对齐，再从头比较对应字符；过程与 前类似，如此进行，直至某次匹配成功，或某次T中无足够 的剩余字符与P对齐（不能匹配，失败）。串模式匹配实现时，设置三个指示器i，j，ii，它们的含义如下。 i：

9、指向主串T中当前参加比较的字符。起始时，指向T的首 字符，之后，每比较一次，后移一步，一趟匹配失败时， 回溯到该趟比较起点的下一位置。 j：指向子串P中当前参加比较的字符。起始时，指向T的首 字符，之后，每比较一次，后移一步，一趟匹配失败时， 回溯到P的首字符处。 ii：记录每趟比较在主串T中的起点，每趟比较后，后移一 步。串模式匹配串模式匹配下面分析此算法的时间复杂度。显然，此算法的主要工作 是do循环，它的循环次数与目标串及模式串相关，所以时 间复杂度是个随机量。最理想的情况是，第一趟就得到匹 配，此时的循环次数为n（即子串s的长度），而最坏的情 况是不存在匹配，且每趟匹配过程都在比较完子

10、串s中最后 一个字符时才发现不能匹配，此种情况的循环次数是(m n+1)n，这里m为主串的长度。显然，n越大，此式的值越 小。当n m时，此式约等于mn。串模式匹配无回溯的匹配算法 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示

11、器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。串模式匹配i指示器之所以可不回溯，是因为重新开始一趟匹配时，可 利用上趟匹配的结果。一般而言，一个无回溯匹配法的关 键问题是，在匹配过程中一旦发现pj与ti不等，应能确定出 从P中的哪个字符起与ti（或ti+1）对齐继续往下比较。这里 记这个字符为pk，显然kj，且对不同的i，k也不同。Knoth 等人发现这个k值仅仅依赖于子串P的前i个字符的构成，而 与主串T无关。这是个令人鼓舞的发现，它是实现无回溯的 关键。可用一个函数next表示j

12、与k的这种对应关系，它是仅 与子串有关的函数，其含义是，在匹配过程中，一旦发现 一对不等的字符（设为pj与ti），若next(j)=k（k0），则下 次的比较应从P中的pk起与T中的ti对齐往下进行；若next(j) 0，则P中任何字符不必再与ti进行比较，下次比较从P的 首字符起与ti+1对齐往下进行。next(j)的取值，应首先保证使 匹配过程无遗漏（即不放过任何可能的匹配），其次，应 使P串向后滑动尽可能长的距离。函数next( )称为失败函数 。串模式匹配下面假定对给定的子串，它的next函数已确立，则串模式匹 配算法可描述为以下程序的形式，它也是KMP算法的基本 部分。串模式匹配以上

13、程序中，用一维数组next 表示失败函数next()，变量i 只增不减，其初值为0，在循环中一直保持in，所以i加1 的语句i+至多执行n次，又因为nextjj，且ljm，故语 句j=nextj至多执行m次，由于循环中只存在分别含有i+与 j=nextj的两个互斥分支，故循环次数不超过MAX(m, n)， 因此算法的时间复杂度为O(MAX(m, n)。通常mn，故时 间复杂度为O(n)。串的应用文本编辑在办公室自动化、企业的现代化管理等许多领域中，文本 编辑（程序）正发挥着越来越大的作用。文本编辑的实质 是修改字符数据的形式或格式，如Microsoft Word，汉字信 息处理系统（激光排版系

14、统）等。虽然这些系统的功能不 太一样，但基本操作一般都包括串的查找、插入和删除等 操作，主要用于源程序的输入和修改，报刊和书籍的编辑 排版及公文书信的起草与润色等。通常，整个文本可看成 是一个字符串，其中，页是文本的子串，行又是页的子串 。例如，以下程序便可看成是一个文本串：串的应用文本编辑在该程序的输入过程中，由文本编辑程序为文本串建立相 应的页表和行表，即建立各子串的存储映射。页表的每一 项给出了页号和该页的起始行号，而行表的每一项则指示 每一行的行号、起始地址和该行子串的长度。每输入的一 行都可作为一个新的字符串加到文本中，串的值放在文本 区中，行号、串值的存储地址及串长度则登记到表中。

15、通 过这个行表，新的一行可放到文本工作区的任何一个自由 区中。设下图所示的文本串只占一页，且起始行号为200， 则该文本串的行表如图所示。串的应用文本编辑串的应用文本编辑下面讨论3种文本编辑的操作。 （1）插入。把新插入的行存到文本的末尾，并按行号的次 序把新行的行号、起始位置及该行字符串的长度信息插入 到行表的合适位置。 （2）删除。把被删除行的行号、起始位置及该行字符串的 长度信息从行表中删去（若存储空间较紧张，则应同时从 内存中删去该行）。若被删除的行是所在页的起始行，则 还要修改页表中相应页的起始行号（修改为下一行的行号 ）。 （3）修改。若新行长小于等于原行长，则把新行字符串 仍存于

16、原行字符串的位置，并修改行表中该行子串的长度 信息即可；若新行长大于等于原行长，则把新行字符串 存于文本末尾，即为该行重新分配存储空间（并可删去文 本中的原行），并修改行表中该行的起始位置及行长信息 。本 章 总 结学习要点 本章主要介绍串的基本概念、基本运算、静态存储结构与 动态存储结构，以及基本操作的实现方法，串操作的综合 应用程序设计。主要学习要点如下： 串的逻辑结构定义 和串的连接、求子串、定位、置换、插入、删除等基本运 算的功能； 串的静态存储和动态存储的基本思想和实现 方法； 串操作在文本编辑、文本格式化处理中的应用。本 章 总 结基本要求 （1）深入领会串运算的定义和基本算法以及综合应用程序 设计； （2）知道（字符）串的有关术语、逻辑结构、