《数据结构第四章学习教案.pptx》由会员分享,可在线阅读,更多相关《数据结构第四章学习教案.pptx(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、会计学1数据结构数据结构(sh j ji u)第四章第四章第一页,共29页。2串中字符个数(串中字符个数(n0n0). n=0 . n=0 时称为空串时称为空串 。由一个或多个空格符组成的串。由一个或多个空格符组成的串。串串s s中任意个连续的字符序列叫中任意个连续的字符序列叫s s的子串的子串; S; S叫主串。叫主串。串长度相等,且对应串长度相等,且对应(duyng)(duyng)位置上字符相等。位置上字符相等。 附:附:1.空串空串(Null String)是指长度为零的串;而空白串是指长度为零的串;而空白串(Blank String)是指包是指包含一个或多个空白字符含一个或多个空白字符
2、 (空格键空格键)的字符串的字符串.2. 空串是任意空串是任意(rny)串的子串,任意串的子串,任意(rny)串是其自身的子串。串是其自身的子串。3.通常将子串在主串中首次出现时该子串的首字符对应的主串中的序号,通常将子串在主串中首次出现时该子串的首字符对应的主串中的序号,定义为子串在主串中的序号(或位置)。定义为子串在主串中的序号(或位置)。第1页/共29页第二页,共29页。3练练1:现有:现有(xin yu)以下以下4个字符串:个字符串:a =BEI b =JING c = BEIJINGBEI d = BEI JING问:问: 他们各自的长度?他们各自的长度? a是哪个串的子串?在主串中
3、的位置是哪个串的子串?在主串中的位置(wi zhi)是多少是多少?a =3,b =4,c = 7,d=8a是是c和和d的子串,在的子串,在c和和d中的位置中的位置(wi zhi)都是都是1串的抽象数据类型定义(串的抽象数据类型定义(参见教材参见教材P71)第2页/共29页第三页,共29页。4 StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A,4)= Index( s, t)=Replace(s, STUDENT,q)=144STUDENTO60 ( s中没有中没有(mi yu)t!)!)I
4、AM A WORKER思考思考(sko):Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ? 第3页/共29页第四页,共29页。5 注:注: 因为串是特殊的线性表,故其存储结因为串是特殊的线性表,故其存储结构构(jigu)(jigu)与线性表的存储结构与线性表的存储结构(jigu)(jigu)类类似。但是,串与线性表的运算又有所不同,似。但是,串与线性表的运算又有所不同,是以是以“串的整体串的整体”作为操作对象,例如查找作为操作对象,例如查找某子串,在主串某位置上插入一个子串等。某子串,在主串某位置上插入一个子串等。第4页/共29页第五页,
5、共29页。6串有三种机内表示串有三种机内表示(biosh)(biosh)方方法:法:顺序顺序存储存储链链式式存存储储(cn ch)第5页/共29页第六页,共29页。7例如:例如:#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长typedef unsigned char SString Maxstrlen1 ;SString s; /s是一个可容纳是一个可容纳(rngn)255个字符个字符的顺序串。的顺序串。4.2.1 定长顺序存储表示定长顺序存储表示(biosh)第6页/共29页第七页,共29页。8注:注: 一般用一般用SString0来存放串长信息;来存放串
6、长信息; C语言约定在串尾加结束符语言约定在串尾加结束符 0,以利操作加速,但不计,以利操作加速,但不计入串长;入串长; 若字符串超过若字符串超过Maxstrlen 则自动截断(因为静态数组存不则自动截断(因为静态数组存不 进去)。进去)。 若不设结束符,可用一个整数来表示若不设结束符,可用一个整数来表示(biosh)串的长度,串的长度,那么该长度减那么该长度减1的位置就是串值的最后一个字符的位置。则的位置就是串值的最后一个字符的位置。则:位置。:位置。此时顺序串的类型定义和顺序表类似:此时顺序串的类型定义和顺序表类似: typedef struct char chmaxstrlen; int
7、 length; sstring; /其优点是涉及到串长操作其优点是涉及到串长操作(cozu)时时速度快。速度快。第7页/共29页第八页,共29页。9实现方式:实现方式:参见教材参见教材(jioci)P73编程两例,两串连接和求编程两例,两串连接和求子串子串第8页/共29页第九页,共29页。10Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法(hf)则警告 Sub1len=Spospos+len-1; Sub0=len; retur
8、n OK;s = a1 , a2 , . , an串长串长poslen第9页/共29页第十页,共29页。11思考:思考:超长字符串如何存储超长字符串如何存储(cn ch)静态数组有静态数组有缺陷!缺陷!引入动态分配的一维数组引入动态分配的一维数组“堆堆”!第10页/共29页第十一页,共29页。12思路:思路: 利用利用mallocmalloc函数合理预设串长空间。若在操作中串值改变,还函数合理预设串长空间。若在操作中串值改变,还可以利用可以利用reallocrealloc函数按新串长度增加函数按新串长度增加( (堆砌堆砌(duq)(duq)空间空间。堆存储的串,其关键信息放置在:。堆存储的串,
9、其关键信息放置在:Typedef struct char *ch; / 若非若非(rufi)空串空串,按串长分配空间按串长分配空间; 否则否则 ch = NULL int length; /串长度串长度HString4.2.2 堆分配存储表示堆分配存储表示第11页/共29页第十二页,共29页。13Status StrInsert ( HString &S, int pos, HString T ) /在串S的第pos个字符之前(包括尾部)插入串Tif (posS.length+1) return ERROR; /pos不合法则警告If (T.length) /只要串T不空,就需要重新分配S的空
10、间,以便插入T if (!(S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) ) exit(OVERFLOW); for ( i=S.length-1; i=pos-1; -i ) /为插入T而腾出(tn ch)pos之后的位置 S.chi+T.length = S.chi; /从S的pos位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入T,忽略/0 S.length + = T.length; /刷新串S的长度 return OK;/StrInsert第12页
11、/共29页第十三页,共29页。14Status StrAssign(HString &T, char *chars) /生成其值等于串常量chars的串Tif (T.ch) free(T.ch); /释放T原有空间for (i=0, c=chars; c; +i, +c); /求串chars的长度iif (!i) T.ch = NULL; T.length = 0; /判断(pndun)chars是否是空串else if (!(T.ch = (char*)malloc(i*sizeof(char) exit(OVERFLOW); /创建大小为i的字符型空间给T.ch T.ch0.i-1 = c
12、hars0.i-1;T.length =i;Return OK;/StrAssign指针指针(zhzhn)变量变量C也可以自增!意即每次后移一个数据单元。也可以自增!意即每次后移一个数据单元。直到终值为直到终值为“假假”停止,串尾特征是停止,串尾特征是/0NUL=0第13页/共29页第十四页,共29页。154.2.3 串的块链存储串的块链存储(cn ch)表示表示特点特点(tdin) : 用链表存储串值,易插入和删除。顺序串用链表存储串值,易插入和删除。顺序串上的插入和删除操作不方便,需要移动大量的字符;因此上的插入和删除操作不方便,需要移动大量的字符;因此,我们可用单链表方式来存储串值,串的
13、这种链式存储结,我们可用单链表方式来存储串值,串的这种链式存储结构简称为链串。构简称为链串。说明:说明: 这种结构便于进行插入和删除运算,但存储空间利用这种结构便于进行插入和删除运算,但存储空间利用率太低。率太低。为了提高存储密度,可使每个结点存放多个字符。通常将结点为了提高存储密度,可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小,显然,当结点大小数据域存放的字符个数定义为结点的大小,显然,当结点大小大于大于1时,串的长度不一定正好时,串的长度不一定正好(zhngho)是结点的整数倍,是结点的整数倍,因此要用特殊字符来填充最后一个结点,以表示串的终结。因此要用特殊字符
14、来填充最后一个结点,以表示串的终结。第14页/共29页第十五页,共29页。16则:法则:法1 1存储密度为存储密度为 ;法;法2 2存储密度为存储密度为 ;显然显然(xinrn)(xinrn),若数据元素很多,用法,若数据元素很多,用法2 2存储更优存储更优称为块链称为块链结构结构法法1 1:链表结点:链表结点(ji din)(ji din)(数据域)(数据域)大小取大小取1 1法法2 2:链表结点(数据:链表结点(数据(shj)(shj)域)大小取域)大小取n(n(例如例如n=4)n=4)1/21/29/15=3/59/15=3/5 A B C I NULLheadheadA B C D E
15、 F G H I # # # NULL第15页/共29页第十六页,共29页。17#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk /首先定义结点类型首先定义结点类型(lixng) char ch CHUNKSIZE ; /结点中的数据域结点中的数据域 struct Chunk * next ; /结点中的指针域结点中的指针域Chunk; 块链类型定义:块链类型定义:例略例略typedef struct /其次定义用链式存储的串类其次定义用链式存储的串类型型 Chunk *head; /串的头指针串的头指针(zhzhn)
16、 Chunk *tail; /串的尾指针串的尾指针(zhzhn) int curLen; /串的当前结点个数(长度串的当前结点个数(长度) Lstring; /串类型只用一次,前面可以不加串类型只用一次,前面可以不加Lstring第16页/共29页第十七页,共29页。184.3 串基本操作的实现串基本操作的实现(shxin)第17页/共29页第十八页,共29页。19算法目的:确定主串中所含子串第一次出现的位置算法目的:确定主串中所含子串第一次出现的位置(wi zhi)(wi zhi)(定(定位)位) 即如何实现即如何实现 Index(S,T,pos) Index(S,T,pos)函数(见教材函
17、数(见教材P71P71)模式匹配模式匹配(Pattern Matching) (Pattern Matching) 即子串定位即子串定位(dngwi)(dngwi)运算。运算。初始条件:初始条件:串串S S和和T T存在,存在,T T是非空串,是非空串,1posStrLength(s)1posStrLength(s)操作结果:操作结果:若主串若主串S S中存在和串中存在和串T T值相同的子串,则返回它在主串值相同的子串,则返回它在主串S S中第中第pospos个字符之后第一次出现的位置;否则函数值为个字符之后第一次出现的位置;否则函数值为0 0。注:注:S S称为称为被匹配的串被匹配的串,T
18、T称为称为模式串模式串。若。若S S包含串包含串T T,则称,则称“匹匹配成功配成功”。否则称。否则称 “匹配不成功匹配不成功” 。第18页/共29页第十九页,共29页。20 BF BF算法设计算法设计(shj)(shj)思想:思想:将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较,个字符比较, 若相等,继续逐个比较后续字符;若相等,继续逐个比较后续字符; 若不等,从主串的下一字符(若不等,从主串的下一字符(pos+1pos+1)起,重新)起,重新与第一个字符比较。与第一个字符比较。 BF算法算法(sun f) (又称古典或经典的、朴素的、(又称古典或经典的、朴
19、素的、穷举的)穷举的) KMP算法算法(sun f)(特点:速度快)(特点:速度快)直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值为。返回值为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号,即匹配成功。,即匹配成功。 否则,匹配失败,返回值否则,匹配失败,返回值 0 .0 .S=a b a b c a b c a c b a bT=T=a b c a cpos=5第19页/共29页第二十页,共29页。21Int Index(SString S, SString T, int pos) i=pos; j=1; while
20、( i=S0 & jT0) return i-T0; /子串结束,说明(shumng)匹配成功 else return0;/IndexS=a b a b c a b c a c b a bT=T=a b c a cpos=5相当于子串向右滑动一个相当于子串向右滑动一个(y )字符位置字符位置匹配成功后指针仍要回溯!因为要返回的是被匹配的首个字符位置。匹配成功后指针仍要回溯!因为要返回的是被匹配的首个字符位置。i ij j第20页/共29页第二十一页,共29页。22第21页/共29页第二十二页,共29页。23能否利用已经能否利用已经(y jing)(y jing)部分匹配的结果而加快模式串的滑动
21、部分匹配的结果而加快模式串的滑动速度?速度?能!而且主串能!而且主串S S的指针的指针i i不必回溯!可提速到不必回溯!可提速到O(n+m)O(n+m)!例:例:S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i=6i=6需要讨论两个问题需要讨论两个问题(wnt)(wnt): 如何如何“记忆记忆”部分匹配结果?部分匹配结果? 如何由如何由“记忆记
22、忆”结果计算出主串结果计算出主串S S第第i i个字符应该与模式个字符应该与模式T T中哪中哪个字符再比较?即确定模式个字符再比较?即确定模式T T中的新比较起点中的新比较起点k.k.i ii ii ik kk k a b aa b c第22页/共29页第二十三页,共29页。24i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c抓住部分匹配抓住部分匹配(ppi)结果的两个特征:结果的两个特征:两式联立可得:两式联立可得:T1Tk-1=Tj-(k-1) Tj-1注意:注意:j 为当前已知的失配为当前已知的失配(sh pi)位置,我们的目标是计算新起
23、点位置,我们的目标是计算新起点 k,仅剩一个未知数仅剩一个未知数k,理论上已可解,且,理论上已可解,且k仅与模式串仅与模式串T有关!有关! 则则S S前前i-1i-1i-(k-1)i-(k-1)位位T T的的j-1j-1j-(k-1)j-(k-1)位位 即即(4-3(4-3)式含义)式含义S=a b a b c a b c a c b a bT=T=a b c a ci ik k则则T T的的k-1k-11 1位位S S前前i-1i-1i-(k-1)i-(k-1)位位 即即(4-2(4-2)式含义)式含义刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符 处失配处失配设目前应与设目前
24、应与T的第的第k字符开始比较字符开始比较第23页/共29页第二十四页,共29页。25根据模式串根据模式串T的规律:的规律: T1Tk-1=Tj-(k-1) Tj-1和已知的当前失配位置和已知的当前失配位置(wi zhi)j ,可以归纳出计算新起点,可以归纳出计算新起点 k的表达的表达式。式。令令k = next j ,则,则next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1) Tj-1 1 其他其他(qt)情况情况讨论:讨论: next j 有何意义?有何意义? 一旦失配,应从模式串一旦失配,应从模式串T中第中第next j 个字符开始与个字符开始与S的失配点
25、的失配点i 重新重新匹配匹配! next j 怎么求?怎么求? 后面会举例后面会举例(参见教材(参见教材P81)第24页/共29页第二十五页,共29页。26Int Index_KMP(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束,说明匹配成功子串结束,说明匹配成功 else return0;/Index_KMP第25页/共29页第二十六页,共29页。27next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其
26、他情况01122312讨论讨论(toln):j=1时时, next j 0;因为属于因为属于“j=1”;j=2时时, next j 1;因为属于因为属于“其他情况其他情况”;刚才已归纳:刚才已归纳:j=3时时, k=2,只需查看只需查看T1=T2 2;j=4时时, k=2,3,要查看要查看T1=T3 3 和和T1T2=T2 2 T3 3 j=5时时, k=2,3,4,要查看要查看T1=T4 4 、T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4以此类推,可得后续以此类推,可得后续nextj值。值。第26页/共29页第二十七页,共29页。28void get_next(SSt
27、ring T, int &next ) /next函数函数(hnsh)值存入数组值存入数组nexti=1; next1=0; j=0;while(iT0 ) if(j= = 0|Ti= = Tj)+i;+j;nexti=j;else j=nextj; / get_nextvoid get_nextval(SString T, int &nextval ) /next函数修正值存入数组函数修正值存入数组nextvali=1; nextval1=0; j=0;while(iT0 ) if(j= = 0|Ti= =Tj ) +i;+j;If(Ti!=Tj ) nextvali=j;else nextvali=nextvalj; else j=nextvalj; / get_nextval next j 是否完美无缺?是否完美无缺?答:未必,例如当答:未必,例如当S=a b a a a a b,T=a a a a b时时仍有多余动作仍有多余动作(参见(参见P84改进算法改进算法, 称为称为nextval j )第27页/共29页第二十八页,共29页。29第28页/共29页第二十九页,共29页。
限制150内