数据结构4串.ppt

第4章 串（String）,2023/3/21,1,4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法,2023/3/21,2,记为：s=a1 a2.an(n0),串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,隐含结束符0，即ASCII码NULL,为何要单独讨论“串”类型？1）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2）程序设计中，处理对象很多都是串类型。,若干术语：,2023/3/21,3,串长：串中字符的个数（n0）.n=0 时称为空串。空格串：由一个或多个空格符组成的串。,问：空串和空格串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空格串(Blank String),是指包含一个或多个空白字符(空格键)的字符串.,2023/3/21,4,子串：子串位置：字符位置：串相等：,例1：现有以下4个字符串：a=BEI b=JING c=BEIJING d=BEI JING,问：他们各自的长度？,a是c和d的子串，在c和d中的位置都是1,串S中任意个连续的字符序列叫S的子串;S叫主串。子串的第一个字符在主串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。,a是哪个串的子串？在主串中的位置是多少？,a=3，b=4，c=7，d=8,“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”数据结构与算法中山大学出版社,空串是哪个串的子串？a是不是自己的子串？,串的抽象数据类型定义（参见教材P71）,2023/3/21,5,C语言中已有类似串运算函数！,ADT StringObjects:D=ai|aiCharacterSet,i=1,2,，n,n0Relations:R1=|ai-1,ai D,i=2,，nfunctions:/至少有13种基本操作StrAssign(&T,chars)/串赋值，生成值为chars的串TStrCompare(S,T)/串比较，若ST，返回值大于0 StrLength(S)/求串长，即返回串S中的元素个数 Concat(&T,S1,S2)/串连接，用T返回S1S2的新串 SubString(&Sub,S,pos,len)/求S中pos起长度为len的子串 StrCopy（&T,S）/由串S复制得到T Index(S,T,pos)/子串定位函数（模式匹配），返回位置 Replace(&S,T,V)/用子串V替换子串TADT String,最小操作子集,复习：C语言中常用的串运算,2023/3/21,6,C串比较：int strcmp(char*s1,char*s2);求串长：int strlen(char*s);串连接：char strcat(char*to,char*from)子串T定位：char strchr(char*s,char*c);参考C语言书,注：用C处理字符串时，要调用标准库函数#include,类CStrCompare(S,T)StrLength(S)Concat(&T,S1,S2)Index(S,T,pos),2023/3/21,7,例如：可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos).,算法基本思想：在主串S中取从第i（i=pos）个字符起，取长度和串T相等的子串和串T比较，若相等，则返回值为i否则i+，直到S中不存在和T相等的子串为止。,StrCompare（SubString（S，i，StrLength（T），T）=？0,2023/3/21,8,Int Index（String S，String T，int pos）/T为非空串，若主串S中第pos个字符之后存在与T相等的子串，/则返回第一个这样的子串在S中的位置，否则返回0；if（pos0）n=StrLength（S）；m=StrLength（T）；i=pos；while(i=n-m+1)if(StrCompare(SubString(S,i,m),T)!=0)+i;else return i;/while/if/Index(),sub,sub,S,n,m,m,i=pos,n-m+1,sub,i,T,T,T,例1：,设 s=I AM A STUDENT,t=GOOD,q=WORKER。求：,2023/3/21,9,Replace(&S,T,V)/用子串V替换子串T,StrLength(s)StrLength(t)SubString(&sub,s,8,7)=SubString(&sub,t,2,1)=Index(s,A)=Index(s,t)=Replace(&s,STUDENT,q)=,14/参见P714STUDENTO,30（s中没有t=GOOD！）,Index(S,T,pos)/返回子串T在pos之后的位置,I AM A WORKER,例2：设 s=I AM A STUDENT,t=GOOD,求：Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)？,2023/3/21,10,解：因为SubString(s,6,2)A；SubString(s,7,8)STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以：Concat(,SubString(s,6,2),Concat(t,SubString(s,7,8)A GOOD STUDENT,串的特点：,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集；串的基本操作和线性表差别很大 串的基本操作中，通常以“串的整体”作为操作对象。,2023/3/21,11,4.2串的表示和实现,2023/3/21,12,定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示链式方式存储,首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。,串有三种机内表示方法：,顺序存储,链式存储,定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,2023/3/21,13,例如：#define Maxstrlen 255/用户可用的最大串长 typedef unsigned char SString Maxstrlen1;/P73 SString s;/s 是一个可容纳255个字符的顺序串。,注：一般用SString0来存放串长信息（如pascal语言）；C语言约定在串尾加结束符 0，以利操作加速，但不计入串长若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。,例：用顺序存储方式编写求子串函数SubString(&Sub,S,pos,len),2023/3/21,14,Status SubString(SString,将串S中从第pos个字符开始、长度为len的字符序列复制到串Sub中。（注：考虑到函数的通用性，应当让串Sub的预留长度与S一样）,子串长度,s=a1 a2.an,pos,len,Sub,讨论：想存放超长字符串怎么办？改用动态分配的一维数组堆,堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,2023/3/21,15,思路：利用malloc函数合理预设串长空间。特点：若在操作中串值改变，还可以利用realloc函数按新串长度增加空间（即动态数组概念）。,Typedef struct char*ch;/若非空串,按串长分配空间;否则ch=NULL int length;/串长度HString,堆T的存储结构描述：,例1：编写建堆函数(参见教材P76）,2023/3/21,16,C是指针变量，可以自增！意即每次后移一个数据单元。,直到终值为“假”停止，串尾特征是c0NULL0,Status StrAssign(HString/求chars的串长度i,此处T.ch0没有用来装串长，因为另有T.length 分量,if(!i)T.ch=NULL;T.length=0;else if(!(T.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);T.ch0.i-1=chars0.i-1;T.length=i;Return OK;/StrAssign,例2：用“堆”方式编写串插入函数(参见教材P75),2023/3/21,17,Status StrInsert(HString/StrInsert,链式存储特点：用链表存储串值，易插入和删除。,2023/3/21,18,讨论：法1存储密度为；法2存储密度为；,显然，若数据元素很多，用法2存储更优称为块链结构,法1：链表结点的数据分量长度取1（个字符）,法2：链表结点（数据域）大小取n(例如n=4),1/2,4/5,串值所占的存储位置存储密度=实际分配的存储位,2023/3/21,19,#define CHUNKSIZE 80/每块大小，可由用户定义typedef struct Chunk/首先定义结点类型 char ch CHUNKSIZE;/每个结点中的数据域 struct Chunk*next;/每个结点中的指针域Chunk;,块链类型定义：,typedef struct/其次定义用链式存储的串类型 Chunk*head;/头指针 Chunk*tail;/尾指针 int curLen;/结点个数 Lstring;,2023/3/21,20,算法目的：确定主串中所含子串第一次出现的位置（定位）,4.3 串的模式匹配算法,BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法,算法种类：,带回溯，速度慢,避免回溯，匹配速度快,定位问题称为串的模式匹配(Pattern Matching)，即子串定位运算，它是串处理系统中最重要的操作之一。典型函数为Index(S,T,pos)，见教材P71,2023/3/21,21,BF算法的实现即编写Index(S,T,pos)函数,例1：S=ababcabcacbab，T=abcac，pos=1，求：串T在串S中第pos个字符之后的位置。,BF算法设计思想：将主串S的第pos个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。,直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0.,2023/3/21,22,讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为,BF算法的时间复杂度,(n-m+1)*mO(n*m),最好的情况是：一配就中！只比较了m 次。,KMP算法（特点：速度快）,KMP算法设计思想KMP算法的时间复杂度,2023/3/21,23,KMP算法设计思想：(参见教材P80-84）,2023/3/21,24,尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。例：,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,Index_kmp的返回值应为i=6,a b a,a b c,i-T0,KMP算法的时间复杂度,注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被广泛采用。,2023/3/21,25,而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算nextj时所用的比较次数m，比较总次数也仅为n+m=O(nm)，大大快于BF算法。,回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为：(n-m+1)*mO(n*m),因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找“流水作业”！,KMP算法的用途：,第4章 小结,2023/3/21,26,串,s=a1a2.an,模式匹配即子串定位运算，即如何实现 Index(S,T,pos)函数,BF算法古典KMP算法快速,本章结束,