第四章串、数组和广义表A.ppt

1、,第四章 串、数组和广义表,(之一),4.1串（String）,4.1.2 串类的定义和实现 4.1.3 串的模式匹配算法,定义 逻辑结构 存储结构 运算规则 实现方式,4.1.1 串的定义,记为： s =a1 a2 . an (n0 ),1）串的定义 串(String)即字符串，是由(n0)零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1.1串的定义,隐含结束符0 ，即ASCII码NULL,ai(1in):字母、数字或其他字符。 i称为字符ai在串中的位置; 思考：“w” 与 w两概念相同吗？ 答：不同，前者是字符串，后者是字符。,若干术语： 串长：串中字符个数（n0

2、）. n=0 时称为空串 。 空白串：由一个或多个空格符组成的串。 空串：（null string）零个字符的串，长度为0。 子串：串s中任意个连续的字符序列叫s的子串; s叫主串。 子串位置：子串在主串中的位置，即子串的第一个字符在主串中的位置。 字符位置：字符在串中的序号。 串相等：串长度相等，且对应位置上字符相等。,练习1：串是由 字符组成的序列，一般记 。,练习2：现有以下4个字符串： a =BEI b =JING c = BEIJING d =BEI JING,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，

3、在c和d中的位置都是1,练习3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空格字符的字符串。,0个或多个,s=a1a2an,2)串的逻辑结构：线性结构 3)串的操作及相应C+库函数中的串操作函数 串的实例： s1=She is a teacher s2=teacher s3=student char s420,*p;int result;,求串的长度 int strlen(char *str); cout串拷贝:把一个串的值赋值给另一串。 char * strcpy(char *str1,char

4、 *str2); strcpy(s4,s2); /s4= teacher,串连接：把两个串连接形成一个长度为两个串长度之和的新串。 char * strcat(char *str1,char *str2); strcat(s2,s3); /s2= teacherstudent 串比较:比较两个串的ASCII码值的大小。 int strcmp(char *str1,char *str2); result=strcmp(s2,s3); /reault0 result=strcmp(s2,s2); /reault=0 result=strcmp(s3,s2); /reault0,串中字符定位：在主串

5、中查找是否存在该字符。找到返回该字符的位置，否则返回-1。 char * strchr(char *str1,char ch); p=strchr(s1, t); /p指在s1中字符t首次出现的位置。 strcpy(p,s3); /s1=She is a student 求子串的位置：在一个主串中查找是否存在和另一个串相等的子串，并给出子串在主串首次出现的位置指针。若不在，则返回为空。 char * strstr(char *str1,char *str2); p=strstr(s1,s2); /其它类似常定义函数名如index(s1,s2); /p指向teacher的首字符在主串中出现的位置

6、。,其它常用串操作： 求子串：截取子串形成一个新串。 设如函数 char * substr(char *str,int pos,int length); p=substr(s1,4,2);/从第5个字符开始，取长度为2的子串 /p= is 在一个串中插入另一个串，操作方法：把串str21插入到串str1中，pos为要插入的起始位置，则操作结果形成的新串长度为str1和str2之和。 如：char * subinsert(char *str1,char *str2,int pos) p=subinsert(s1,s2,5); /p= =She teacheris a teacher,从一个串中删

7、除一个子串，操作方法：在串str中删除长度为length的子串，pos为要删除的子串在str中的起始位置，则删除后的新串长为原长度减去length。 输入串：从键盘输入一个字符序列 C+流库： cins4; /若输入Hello!,则s4=Hello! 输出串：在屏幕上显示一个字符序列 cout功能强大，略。 4）串的抽象数据类型的定义（参见p116-117）,设 s =“I AM A STUDENT”, t =“GOOD”, q=“WORKER”。求：,练习：,StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= i

8、ndex(s, A)= index(s, t)= Replace(s, STUDENT,q)=,14 4 STUDENT O 3 0 （ s中没有t！） I AM A WORKER,再问：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？,A GOOD STUDENT,定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列 堆分配存储表示 用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示 链式方式存储,首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子

9、串，在主串某位置上插入一个子串等。,串有三种表示方法：,顺序存储,链式存储,串的存储结构,如：串的定长顺序存储（常用） char str =“teacher ”； char st 10=“teacher ”；,str,st,如何改造数组实现串的顺序存储？,非压缩形式,存储密度:串值所占的存储单元数/实际分配的存储单元数 如：存储单元数为10，则该存储方法存储密度为 7/10,方案1：用一个变量来表示串的实际长度。,如何表示串的长度？,方案2：在串尾存储串的终结符，写算法计算串长。,方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。,如何实现定长顺序存储串的连接操作？,串连接StrC

10、oncat操作基本算法思想： 设s0、T0放串长,S数据最大值为max 求S=S+T； 注:超长部分实施“截断”操作： 1) S0+T0max: T直接添在S串之后。 2)S 0 max,而S 0+T0 max 时，S中只能追加T串的部分元素值。 3)S10=max,T无法加入。 算法实现(略),串的链式存储,存储密度: 串值所占的存储单元数/实际分配的存储单元数 如：3/8,（1）非压缩形式,如何改造链表实现串的链接存储？,存储密度: 串值所占的存储单元数/实际分配的存储单元数 如：一个数据域存放4个字符，共5*3=15个存储单元 占用了7，则存储密度为7/15。 思考：采用非压缩方式，存储

11、密度为多少？ 共8*2=16,存储密度为7/16。 小结：若数据元素很多，用方法2存储更优,（2）压缩形式,4.1.2串类的定义和实现 1、堆串的类定义： 参考p117 #ifndef String_H #define String_H #include template /定义模板类String class String public: String( ); /无参构造函数 String(T1 *str); /用C+串来初始化 String(const String /析构函数为空,void clearString();/释放串空间 int Length(); /获得串长度 void Str

12、Concat(const String /在S串中pos位开始查找与串T相同的子串，若找到返回其位置 /（首次出现），否则返回-1；(模式匹配),friend ostream #endif,2、堆串的操作实现：,堆串无参构造函数实现(构造一个空的串) String( ); 基本算法思想: 串长为0; 申请存储串的空间, 大小为1。 3)赋串尾标识符：0,template String: String( ) /构造一个空串 length=0; s=new charlength+1; if (s=NULL) cout分配错误endl; exit(1); *s=0; ,利用C+串构造实现堆串 Str

13、ing(T1 *str) 基本算法思想: 求出str串长赋给length; 申请存储串的空间, 大小为length+1。 3)将串str赋于s。,template String: String(T1 *str) int i=0; while(stri!=0) i+; length=i; s=new charlength+1; /需存放0 for(i=0;i库 ,利用已存在的堆串构造实现新堆串 String(const String 2)申请存储串的空间, 大小为length+1。 3)将串ob赋于s。,template String:String(const String /0 ,释放堆串空间

14、函数实现clearString() 基本算法思想: 如果串S存在，则释放所占空间; 串长赋于0;,template void String:clearString() /释放串空间 if (s) delete s; length =0; ,串长函数实现Length() 基本算法思想: 如果串s不存在，则给出错误信息; 返回串长;,template int String:Length() if(!s) throw 串不存在！; return length; ,堆串连接实现 操作接口： template StrConcat(const String 5) 释放s所占空间，将s指向s1，改串长为新串

15、长length=L；,length = 7,length = 7,s,T.s,s1,L=7+7=14,template void String:StrConcat(const String /赋新串长 ,串对象赋值实现String operator =(String 返回当前串对象；,template String String:operator =(String ,串比较函数实现 template int String:StrCmp(String T) 基本算法思想: 将串s与T.s串逐各元素进行比较，当不相等时，返回si-T.si。(即负值：小于；正值：大于;0：等于) 若两串相对应字符相

16、同，则看其串长，返回length-T.length；(即负值：小于；正值：大于;0：等于),template int String:StrCmp(String T) /将串S与串T比较，看是相等，还是大于或小于 int i; /若sT,则返回值0;若s=T,则返回值=0;若sT,则返回 for(i=0;ilength ,串插入函数实现 template void String:StrInsert(int pos, String T) 基本算法思想: 1）判定pos是否合法，1=pos=length+1合法;不合法，给出错误信息。 2）只要串T不空，就需要重新分配s空间，以便插入T；设置新串串长

17、L=length+T.length; 3）为新串s1重新申请存储空间，大小为L+1； 4）将串s的第1位到第pos-1位的串值复制到s1中； 5）将T插入s1 6）将串s的第pos位后面的串值复制到s1中； 7）s1L=0 8）设s串长为新值length=T.length+length 9）释放s的存储空间，并让其指向s1串。,template void String:StrInsert(int pos, String T) /在串s的第pos位置（包括尾部）插入串 int i,j; if (poslength+1) throw pos不合法!; if (T.length) /只要串T不空，就

18、需要重新分配s空间，以便插入T char *s1;int L=length+T.length; s1=new charL+1; if (s1=NULL) throw 空间分配失败！; /复制第1位到第pos-1位的串值 for(i=0;ipos-1;i+) s1i=si; /将T插入s for(j=0;j=T.length-1;j+,i+) s1i=T.sj; /插入s而腾出pos之后串值 for ( j=pos-1;jlength; j+,i+) s1i=sj; s1L=0; length+=T.length; delete s; s=s1;/s新值 ,串删除函数实现 template vo

19、id String:StrDelete(int pos,int len) 基本算法思想: 1）先判pos和len是否合法； 不合法条件：poslength|len length-pos+1 2）设置新串串长L=lengthlen; 3）为新串s1重新申请存储空间，大小为L+1； 4）将串s的第1位到第pos-1位的串值复制到s1中； 5）将串s的第pos+len位开始，到串尾复制到s1串中； 6）设s串长为新值length=length-len; 7）释放s的存储空间，并让其指向s1串。,template void String:StrDelete(int pos,int len) int i

20、,j; if (poslength|len length-pos+1) throw “pos或length不合法！; int L=length-len; char *s1=new charL+1; for(i=0;i=pos-2;i+) s1i=si; for(j=pos+len;j=length+1;j+,i+) /从第pos+len位开始，到串尾复制到s1串中 s1i=sj-1; length-=len; delete s; s=s1;/s新串 ,求子串实现 template String String:SubString(int pos,int len) 基本算法思想: 1）判pos和l

21、en是否合法： poslength|len length-pos+1 2）生成新的串对象ob; 3）设置子串的长度为ob.length=len; 4）为子串ob.s重新申请存储空间，大小为len+1； 5）将串s的第pos位开始，连续len长度的串值复制到子串ob.s中； 6）设置子串结束符ob.sob.length=0; 7）返回子串ob;,template String String:SubString(int pos,int len) /将串s从pos位开始，连续取len位的子串。 if (poslength|len length-pos+1) throw pos不合法！; String

22、 ob; int i; ob.length=len; ob.s=new charlen+1; for(i=pos;i=pos+len-1;i+) ob.si-pos=si-1; ob.sob.length=0; return ob; ,输出运算符重载实现 template ostream ,for(len=0;len254;len+) stream.get(clen);/输入一个字符给clen if (clen=n)break; /输入的是换行符，表示串对象的结束 if (clen=b) /若输入的是退格键 if(len!=0) /并且输入的串长度非0，删除最后输入的一字符 len-;/相应的

23、长度减1 coutb; clen=0;,if (ob.length) /length!=0，则需释放原存储空间 delete ob.s; ob.s=new charlen+1; if (ob.s=NULL) cout分配失败！endl; exit(1); ob.length=len; for(int i=0;i=len;i+) ob.si=ci; /把输入流拷贝到串对象ob中。 return stream; ,4.1.3模式匹配 （Pattern Matching）,定义：给定主串S=“s1s2sn”和模式T=“t1t2tm”，在S中寻找T 的过程称为模式匹配。如果匹配成功，返回T 在S中的位

24、置，如果匹配失败，返回0。 算法目的：确定主串中所含子串第一次出现的位置。 如int index(const String /同书上find函数类似,初始条件：串S和T存在，T是非空串， 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。,模式匹配问题的特点： 算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配； 算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。,BF算法 （又称古典或经典的、朴素的、穷举的） KMP算法（特点：速度快）,算法种类：,基本思想： 、将主串的第pos个字符

25、和模式的第1个字符比较，若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 、直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 。,模式匹配BF(Brute-Force)算法,si ,主串S,模式T,tj,模式匹配BF算法 图示,i=pos-1;,串匹配方法的演示,template int String:index(const String ,模式匹配BF算法,模式匹配BF算法评估,设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：, 最好：不成功的匹

26、配都发生在串T的第一个字符。,例如：S=aaaaaaaaaabcdccccc T=bcd ,设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：,最坏情况：不成功的匹配都发生在串T的最后一个字符。,实例如：S=aaaaaaaaaaabccccc T=aaab,设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)m次，第i趟成功的匹配共比较了m次，所以总共比较了im次，所有匹配成功的可能情况共有n-m+1种，因此,为什么BF算法时间性能低？,在每趟匹配不成功时存在

27、大量回溯，没有利用已经部分匹配的结果。,如何在匹配不成功时主串不回溯？,主串不回溯，模式就需要向右滑动一段距离。,需要讨论两个问题： 如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ 模式应该向右滑多远才是最高效率的?,结论： i可以不回溯，模式向右滑动到的新比较起点k ，并且k 仅与模式串T有关！,模式匹配KMP算法,模式匹配KMP算法实例演示,请抓住部分匹配时的两个特征：,两式联立可得：T0Tk-1Tj-k Tj-1,（2）则Tj-k Tj-1 Si-k Si-1,（1）设模式滑动到第k个字符，则T0Tk-1 Si-k Si-1,(0kj),T1Tk-1Tj-(k-1) Tj-1说明

28、了什么？ （1） k 与 j 具有函数关系，由当前失配位置 j ，可以计算出滑动位置 k（即比较的新起点）； （2）滑动位置k 仅与模式串T有关。,从第1位往右 经过k-1位,从j-1位往左 经过k-1位,T1Tk-1Tj-(k-1) Tj-1的物理意义是什么？,模式应该向右滑多远?,一般,主串中第i个字符与模式串中第j个字符“失配”，主串i不动，应于模式串中的哪个字符再比较呢？ 已存在：”si-jsi-j+1si-1”=“t0t1tj-1” 可分两种情况讨论: 1)若模式串中存在: “t0t1tk-1”=“tj-ktj-K+1tj-1” (0Kj) 则说明模式串中的子串 “t0t1tk-1”

29、=”sj-Ksj-K+1sj-1”,下一次比较直接比较s j=tk;即j=k;,2)若模式串中不存在相互重叠的真子串，则说明在模式串不存在 “t0t1tk-1”=”sj-Ksj-K+1sj-1”, (0Kj) 下一次比较直接比较s j=t0;即j=0;,kmax k |1kj 且T1Tk-1Tj-(k-1) Tj-1 ,模式应该向右滑多远才是最高效率的?,next j ,-1 当j0时 /不比较 max k | 0kj 且T0Tk-1=Tj-k Tj-1 /非空 0 其他情况,令k = next j ，则：,nextj函数表征着模式T中最大相同子串长度。 可见，模式中相似部分越多，则nextj函数越大，它既表示模式 T 字符之间的相关度越高，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。 二进制流较合适！,（1）next函数:,模 式 串 T： a b a a b c a c 可能失配位 j： 0 1 2 3 4 5 6 7 新匹配位k=nextj :,-1,0,2,0,1,j=0时, next j -1； j=1时, next j 0；,j=2时, k可取1,T0T1，因此，k=0；,j=3时,k可取