数据结构(串).ppt

串是计算机非数值处理的主要对象之一。在早期的程序设计语言中，串仅作为输入和输出的常量出现。随着计算机应用的扩展，需要在程序中进行对“串”的操作，如在汇编和编译程序中，源程序和目标程序都是串，又如在事务处理程序中，顾客的姓名和地址等，通常也都作为串处理。从而使众多编程语言增加了串类型，以便程序员可以在程序中对串变量进行操作。,第四章 串,4.1 串的抽象数据类型定义 4.2 串的表示和实现 4.3 串的匹配算法,第四章 串,串的基本概念,串是由零个或多个任意字符组成的字符序列。一般记作：s=a1 a2 an。其中s是串名；在本书中，用单引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1=i=n)是一个任意字符，可以是字母、数字或其它字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为。注意：空串和空白串（通常将仅由一个或多个空格组成的串称为空白串(Blank String)。,串中任意个连续字符组成的子序列称为该串的子串；包含子串的串相应地称为主串；通常将子串在主串中首次出现时的该子串的首字符对应 的主串中的序号，定义为子串在主串中的位置。例如，设A和B分别为 A=This is a string B=is 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。特别地，空串是任意串的子串，任意串是其自身的子串。,串的类型定义,串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量或数的常量混淆而已。如 x=123；表明x是一个串变量名，赋予它的值是字符序列123，而 x=123，则表明x是一个整型变量，赋予它的值为整数123。同样在 aString=aString;中，左边的aString是一个串变量名，而右边的字符序列aString是赋给它的值。,串的类型定义,通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只 能被引用但不能改变其值，即只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。,串的类型定义,ADT String 数据对象：D=ai|ai CharacterSet，i=1，2，n，n 0 数据关系：R=|ai-1，ai D，i=2，n 基本操作：1.结构初始化 StrAssign(&T,chars)初始条件：chars 是串常量。操作结果：生成一个其值等于 chars的串T。,串的抽象数据类型定义,串的抽象数据类型定义,StrCopy(&T,S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。2.销毁结构DestroyString(&S)初始条件：串 S 存在。操作结果：串 S 被销毁。,串的抽象数据类型定义,3.引用型操作StrEmpty(S)初始条件：串 S 存在。操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。StrCompare(S,T)初始条件：串 S 和 T 存在。操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。StrLength(S)初始条件：串 S 存在。操作结果：返回串 S 序列中的字符个数，即串的长度。,串的抽象数据类型定义,SubString(&Sub,S,pos,len)初始条件：串S存在，1posStrLength(S)且 0lenStrLength(S)-pos+1。操作结果：用 Sub 返回串S的第 pos 个字符起长度为 len 的子串。Index(S,T,pos)初始条件：串S和T存在,T是非空串，1posStrLength(S)操作结果：若主串S中存在和串T值相同的子串，则返回它在 主串S中第pos个字符之后第一次出现的位置；否 则函数值为0。,串的抽象数据类型定义,4.加工型操作 ClearString(&S)初始条件：串 S 存在。操作结果：将 S 清为空串。Concat(&T,S1,S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。Replace(&S,T,V)初始条件：串 S，T 和 V 存在，T 是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠 的子串。,串的抽象数据类型定义,StrInsert(&S,pos,T)初始条件：串 S 和 T 存在，1posStrLength(S)1。操作结果：在串 S 的第 pos 个字符之前插入串 T。StrDelete(&S,pos,len)初始条件：串 S 存在，1posStrLength(S)-len+1。操作结果：从串 S 中删除第 pos 个字符起长度为 len 的 子串。ADT String,串的抽象数据类型定义,在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等5种操作构成串类型的最小操作子集。即这些操作不可能利用其它操作来实现，而其它操作均可在这个最小操作子集上实现。例如，可利用判等、求串长和求子串等操作实现串的定位函数 Index(S,T,pos)。,串的抽象数据类型定义,Index(S,T,pos)算法的基本思想：从主串S中取“第 i 个字符起、长度和串T相等的子串”和串T比较，若相等，则求得函数值为 i，否则 i 值增1直 至找到和串T相等的子串或者串S中不存在和T相等的子串 为止。即求使下列等式 StrCompare(SubString(S,i,StrLength(T),T)=0成立的 i 值。i 的初值应为 pos，在找不到的情况下，i 的 终值应该是 n-m+1，其中，n 为S串的长度，m 为T串的 长度。,串的抽象数据类型定义,int Index(String S,String T,int pos)/T为非空串。若主串S中第 pos 个字符之后存在与T相等的子串，/则返回第一个这样的子串在S中的位置，否则返回0。if(pos 0)n=StrLength(S);m=StrLength(T);/求得串长i=pos;while(i=n-m+1)SubString(sub,S,i,m);/取得从第 i 个字符起长度为 m 的子串if(StrCompare(sub,T)!=0)+i;else return i;/找到和 T 相等的子串/while/ifreturn 0;/S 中不存在满足条件的子串/Index,如果在程序设计语言中，串只是作为输入/输出的常量出现，则只需要存储这个串常量值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。则需要根据串操作的特点，合理地选择和设计串值的存储结构及其维护方式。串有三种机内表示方法，下面分别介绍。,串的表示和实现,串的表示和实现,一、定长顺序存储表示；二、串的堆分配存储表示；三、串的块链存储表示；,定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出。#define MAXSTRLEN 255/用户可在255内定义最大串长 typedef unsigned char SStringMAXSTRLEN+1;/零号单元存放串的长度 串的实际长度可在预定义长度的范围内随意，超过 预定义的串值则被舍去，称之为“截断”。,定长顺序存储表示,串长有两种表示方法：1.如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言中采用的串类型采用这种表示方法；2.在串值后面加一个不计入串长的的结束标记字符。如，C语言中以字符0表示串值的终结。此时的串长为隐含值，显然不便于进行某些操作。,定长顺序存储表示,例如C语言中串不是预定义的数据类型，而是以字符数组来表示串。如声明char str10；表明str是一个串变量。C语言中还规定了一个串的结束标志 0，即数组中在该结束标志之前的字符是串变量的有效字符，但结束标志本身要占一个字符的空间，因此串变量str的值（字符序列）的实际长度可在这个定义范围内随意，但最大不能超过9。,定长顺序存储表示,Status Concat(SString else if(S10 MAXSTRLEN)/截断 else/截断(仅取S1)/Concat,串联接操作,Status SubString(SString/SubString,求子串操作,堆分配存储表示仍属于顺序存储表示，它的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。,堆分配存储表示,假设以一维数组heap MAXSIZE 表示可供字符串进行动态分配的存储空间，并设 int free 指向heap 中未分配区域的开始地址(初始化时free=0)。在程序执行过程中，当生成一个新串时，就从free指示的位置起，为新串分配一个所需大小的存储空间，同时建立该串的描述。这种存储结构称为堆结构。此时，堆串可定义如下：typedef struct int start;/串的起始位置 int length;/串长度 HeapSring;,堆分配存储表示,下图是一个堆存储及符号表，其中a=a program，b=string，c=process，free=24：,堆分配存储表示,在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。因此，我们可以直接利用C语言中的“堆”，实现堆串。此时，堆串可定义如下：typedef struct char*ch;/若是非空串，则按串长分配存储区,/否则ch为NULL;int length;/串长度 HeapSring;这类操作的实现算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。,串的堆分配存储表示,以上两种存储表示通常为高级程序设计语言所采用。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。,堆分配存储表示,和线性表的链式存储结构类似，也可用链表来存储串值。但由于串的结构的特殊性，即串的数据元素是一个字符，它只有8位二进制数，因此用链表存储串值时通常采用的办法是在一个结点中存放多个字符，因此称它为块链存储表示。,串的链式存储结构,由于在一般情况下，串的操作都是从前往后进行的，因此串的链表通常不设双链，也不设头结点，但为了便于进行诸如串的联接等操作，链表中还附设有尾指针，并且由于串的长度不一定是结点大小的整数倍（链表中最后一个结点中的字符非都是有效字符），因此还需要一个指示串长的域。称如此定义的存储结构为串的块链存储结构，其定义如下：,串的块链存储表示,#define CHUNKSIZE=80;/可由用户定义的块大小 typedef struct Chunk/结点结构 char chCHUNKSIZE;struct Chunk*next;Chunk;typedef struct/串的链表结构 Chunk*head,*tail;/串的头指针和尾指针int curlen;/串的当前长度 LString;,串的块链存储表示,在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。这就要求我们考虑串值的存储密度。,串的块链存储表示,注意：1、为了提高存储密度，可使每个结点存放多个字符。2、当结点大小大于1时，串的长度不一定正好是结点 大小的整数倍，因此要用特殊字符来填充最后一个 结点，以表示串的终结。,3、虽然提高结点的大小使得存储密度增大，但是 做插入、删除运算时，可能会引起大量字符的 移动，给运算带来不便。串值为“abcdef”的结点大小为4的链串S如下图所示。,在S的第3个字符后插入“xyz”时，要移动原来S中后面4个字符的位置，结果见下图。,串值的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。但串的链式存储表示在应用程序中，还是有很大用处的，如可将串的链表存储结构和串的定长结构结合使用。例如在正文编辑系统中，整个“正文”可以看成是一个串，每一行是一个子串，构成一个结点，即：同一行的串用定长结构（80个字符），而行和行之间用指针相链。串值在链式存储结构时串操作的实现和线性表在链表存储结构中的操作类似，故在此不作详细讨论。,串的块链存储表示,文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。,串操作应用举例-文本编辑,为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为文本串，页是文本串的子串，行是页的子串。我们采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。,串操作应用举例-文本编辑,例如有下列一段源程序：main()float a,b,max;scanf(“%f,%f”,；该程序输入内存后放到一个堆中，如下图所示。其中为换行符。,其中页表为：,其中行表为：,下面我们就来讨论文本的编辑：1）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。,串操作应用举例-文本编辑,2）当插入或删除一行时必须同时对行表也进行插入和删除，若被删除的行是所在页的起始行，则还要修改页表中相应页的起始行号（应修改成下一行的行号）。为了查找方便，行表是按行号递增的顺序安排的，因此对行表进行插入或删除时需移动操作之后的全部表项。对页表的维护与行表类似，在此不再叙述。由于对正文的访问是以页表和行表作为索引的，因此在删除一页或一行时，可以只对页表或行表作相应修改，不必删除所涉及的字符，这可以节省不少时间。注意：在正文编辑中，行表和页表与串值的存储是分开的。行表和页表反映了串值存储情况的扼要信息，相当是串值的一种查找索引，也称为串的存储映象。通过串的存储映象可以更方便地对串值进行大量的同类操作。,是串的一种重要操作，很多软件若有“编辑”菜单项的话，则其中必有“查找”子菜单项。这样的一个查找操作，即为子串定位运算又称为串的模式匹配(Pattern Matching)。,串的模式匹配算法,2023年3月21日,数据结构讲义,41,串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中查找子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。t也称为模式。为了运算方便，设字符串采用定长存储，且串的长度存放在0号单元，串值从1号单元存放，这样字符序号与存储位置一致。,串的模式匹配算法,串匹配的算法很多，下面我们只讨论以定长顺序结构表示串的两种匹配算法：1.简单匹配算法；2.KMP匹配算法；,串的模式匹配算法,算法思想：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1，否则，匹配失败。,简单匹配算法,设主串s=acabaabaabcacaabc，模式t=abaabcac，匹配过程如图所示。,简单匹配算法,int index(sstring s,sstring t,int pos)/返回子串 T在主串 S 中第pos字符之后的位置，若不存在，则/函数值为 0。其中，T非空，1posStrLength(S)i=pos;j=1;while(i T0)return i-T0;/匹配成功 else return 0;/Index,简单匹配算法,下面分析它的时间复杂度，设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：例如：s=”aaaaaaaaaabc”，t=”bc”设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：即最好情况下的时间复杂度是O(n+m)。,2023年3月21日,数据结构讲义,47,在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符：例如：s=”aaaaaaaaaaab”，t=”aaab”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。,对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O(m+n)，因此在多数的实际应用场合下被应用。但对于那些只含0、1两种字符的字符串，算法的效率则非常低，算法的时间复杂度为O(mn)。因此，我们需要引入另一种串的模式匹配算法来处理这类文档。,简单匹配算法,KMP算法,是由三位计算机学者 D.E.Knuth 与 V.R.Pratt 和 J.H.Morris 同时发现的，因此人们通常简称它为 KMP 算法。KMP的时间复杂度为O(m+n)，直观地看，是因为在匹配过程中指针 i 没有回溯。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。,KMP算法思路,从主串s的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后继字符。当一趟匹配过程中出现字符比较不等时，不回溯指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。,KMP算法,思考的开始：假定：主串为 S1S2Sn 模式串为 P1P2Pm无回溯匹配问题变为：当主串中的第i个字符和模式串中的第j个字符出现不匹配（si不等于pj）时，主串中的第i个字符应该和模式串中的哪个字符匹配？,KMP算法,进一步思考：将模式串“向右滑动”，让模式串中第k(kj)个字符和si对齐继续比较。这时有：P1P2Pk-1=Si-k+1Si-k+2Si-1（1）而根据部分匹配成功的结果可知：P1P2Pj-1=Si-j+1Si-k+2Si-1（2）由（2）式 Pj-k+1Pj-k+2Pj-1=Si-k+1Si-k+2Si-1（3）由（1）和（3）有：Pj-k+1Pj-k+2Pj-1=P1P2Pk-1（4）,KMP算法,由（4）可知，若模式串中的前k-1个字符与模式串中pj字符前面的k-1个字符相等时，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式p“向右滑动”至致使Pk和Si对准，此时，模式中头k-1个字符的子串 P1P2Pk-1 必定与主串中第i个字符之前长度为k-1的子串 Si-k+1Si-k+2Si-1 相等。因此，匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。,Next函数的定义,令Nextj k，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下：,/一个配串,/相当于主串中i指针推进一个位置,Next函数值仅取决于模式串本身的结构而和相匹配的主串无关。,Next函数的定义,KMP算法的匹配过程,int Index_KMP(SString S，SString T，int pos)/利用模式串 T的next函数求T在主串 S 中第pos字符之后的位置/的KMP算法。其中，T非空，1posStrLength(S)i=pos;j=1;while(i T0)return i-T0;/匹配成功 else return 0;/Index,KMP算法,Next函数值求解,下一个问题是如何求模式串的 next 函数值？求next函数的过程是一个递推的过程：1.递归基础：首先由定义得 next1=0;2.假设已知 nextj=k，则有：Pj-k+1.Pj-1=P1 P2.Pk-1，则考察nextj+1：1）若Pj=Pk，有：Pj-k+1.Pj=P1 P2.Pk，即：nextj+1=k+1=nextj+1；2）若Pj Pk，表明：Pj-k+1.Pj P1 P2.Pk，,Next函数值求解,此时可把求next函数值的问题看成一个模式匹配的问题，整个模式串又是子串又是模式串。则令 nextk=k，则又是两种情况，pj=pk以及 pj pk；1）pj=pk，有：p1p2pk pj-k+1pj-k+2pj（1kkj)即：nextj1 k+1=nextk 1。2）pj pk，依次类推，直至Pj和模式串中某个 字符匹配成功或者不存在任何k满足p1p2pk pj-k+1pj-k+2pj，则nextj1=1。,Next函数值求解,Next函数算法,Next函数算法,Next函数改进算法,前面定义的next函数在某些情况下尚有缺陷；例如：模式串t=aaaab和主串S=aaabaaaab 匹配时，当i=4、j=4时，s.ch4!=t.4,由nextj的指示还需进行i=4、j=3，i=4、j=2，i=4、j=1这3次的比较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中的第4个字符相比较，而可以将模式一气向右滑动4个字符的位置直接进行i=5、j=1时的比较。因为在Si和Tj不等时，由于Tj=Tk，则Si肯定也不等于Tk，也就是说，Si不应该再去和Tk进行比较（因为纯粹是多余的），而应该直接和Tnextk进行比较。因此，当Tj=Tk时，应该直接取Tk的next函数值作为Tj的 next 函数值。,Next函数改进算法,void get_nextval(SString T,int nextval)/求模式串T的next函数值并存入数组 next。i=1;nextval1=0;j=0;while(j T0)if(j=0|Ti=Tj)+j;+i;if(Tj!=Ti)nextvali=j;else nextvali=nextj;/ifelse j=nextvalj;/while/get_nextval,本章主要知识点,串的两个显著特点是：1、它的数据元素都是字符，因此它的存储结构和线性表有很大不同，例如多数情况下，实现串类型采用的是“堆分配”的存储结构，而当用链表存储串值时，结点中数据域的类型不是“字符”，而是“串”，这种块链结构通常只在应用程序中使用；2、串的基本操作通常以串的整体作为操作对象，而不像线性表是以数据元素作为操作对象。,本章小结,1.熟悉“串”类型定义中各基本操作的特点，并 能正确利用它们进行串的其它操作；2.熟悉串类型的各种存储表示方法；3.理解串匹配的各种算法。,本章小结,本章作业,1.设s=I AM A STUDENT,t=GOOD,q=WORKER。给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,A,4);StrReplace(s,STUDENT,q);StrCat(StrCat(sub1,t),StrCat(sub2,q);2.叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。3.编写算法，实现串的基本操作StrReplace(&S,T,V)。,