数据结构chap串学习教案.pptx

《数据结构chap串学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构chap串学习教案.pptx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(sh j ji u)chap串串第一页，共22页。目录(ml)4.1串的类型串的类型(lixng)的定义的定义4.2 串的表示串的表示(biosh)和实现和实现结束放演第1页/共22页第二页，共22页。4.1串类型串类型(lixng)的定义的定义4.1.1 基本概念 1串的定义串的定义 串串(string)是是由由零零个个或或多多个个字字符符组组成成的的有有限限序序列列，记记作作s=a1a2an（n=0），其其中中s为为串串的的名名字字，用用成成对对的的单单引引号号括括起起来来的的字字符符序序列列为为串串的的值值，但但两两边边的的单单引引号号不不算算串串值值，不不包包含含(b

2、ohn)在在串串中中。ai(1in)可可以以是是字字母母、数数字字或或其其它字符。它字符。n为串中字符的个数，称为串的长度。为串中字符的个数，称为串的长度。2空串空串不不含含任任何何字字符符的的串串称称为为(chn wi)空空串串，它它的的长长度度n=0，记为，记为s=，通常记为，通常记为。第2页/共22页第三页，共22页。3空白串空白串(空格串空格串)含含有有(hn yu)一一个个或或多多个个空空格格的的串串，称称为为空空白白串串，它它的的长长度度n=串中空格字符的个数，例如：串中空格字符的个数，例如：s=，长度为，长度为1。4子串、主串子串、主串 若若一一个个串串是是另另一一个个串串中中连

3、连续续(linx)的的一一段段，则则这这个个串串称称为为另另一一个个串串的的子子串串，而而另另一一个个串串相相对对于于该该串串称称为为主主串串。例例如如,串串s1=“abcdefg”，s2=“fabcdefghxyz”，则则s1为为s2的的子子串串，s2相相对于对于s1为主串。为主串。另外，空串是任意串的子串，任意串是自身的子串。问题：若一个串的长度为n，则它的子串数目(shm)和真子串个数分别为多少(除串本身以外的子串都称为真子串)？第3页/共22页第四页，共22页。5.子串在主串中的位置 既子串的第一个字符在主串中的位置表示(biosh)。例如：串s1=CD在s=ABCDECFG中的位置6

4、.串相等 两个串的长度(chngd)相等当且仅当两个串的值相等 各个对应位置的字符都相等第4页/共22页第五页，共22页。串的基本操作串的基本操作StrAssign(&T,chars)StrAssign(&T,chars)生成一个值等于生成一个值等于charschars的串的串T TSubString(&sub,s,pos,len)SubString(&sub,s,pos,len)用用sub sub 返回串返回串S S的第的第pospos个字符起个字符起长度为长度为len len 的子串的子串Concat(&T,s1,s2)TConcat(&T,s1,s2)T为为s1,s2s1,s2连接而成的

5、新串连接而成的新串Replace(&S,T,V)Replace(&S,T,V)用用V V替换替换S S中出现的所有与中出现的所有与T T相等相等(xingdng)(xingdng)的不重叠子串。的不重叠子串。Index(S,T)Index(S,T)若若S S中存在串中存在串T T值相同的子串，返回其在主串值相同的子串，返回其在主串S S中第一次出现的位置，否则函数返回值为中第一次出现的位置，否则函数返回值为0 0Strcompare(S,T)ST Strcompare(S,T)ST 返回值返回值00 S=T S=T 返回值返回值=0=0 ST ST 返回值返回值00第5页/共22页第六页，共2

6、2页。例:S=I am a Student T=Good Q=workerStrlength(S)=14Strlength(S)=14SubString(S,8,7)=SubString(S,8,7)=StudentStudent Index(S,Index(S,a a)=3 Index(S,T)=0)=3 Index(S,T)=0Replace(S,Replace(S,StudentStudent,Q)=,Q)=I am a workerI am a worker Concat(SubString(S,6,2),Concat(T,SubString(S,7,8)Concat(SubStrin

7、g(S,6,2),Concat(T,SubString(S,7,8)=Concat(=Concat(a a ,Concat(,Concat(GoodGood,Student Student)=a Good Studenta Good Student 第6页/共22页第七页，共22页。4.1.2 串的抽象数据类型的定义描述串的抽象数据类型的定义描述 P71注意：注意：串串的的逻逻辑辑结结构构与与线线性性表表及及相相似似，但但基基本本操操作作(cozu)和和线线性性表表有有很很大大差差别别，操操作作(cozu)对对象象而而言言，线线性性表表为为单单个个对对象象作作为为操操作作(cozu)对对象象，

8、而而串串以以串串的的整整体体（子子串串）作作为为操操作作(cozu)对象。对象。串串类类型型的的最最小小操操作作(cozu)子子集集：StrAssign、StrCompare、StrLength、Concat、SubString 例如：算法例如：算法 4.1第7页/共22页第八页，共22页。4.2 串的表示串的表示(biosh)和实现和实现4.2.1 定长顺序存储表示(biosh)4.2.2 串的指针表示(biosh)4.2.3 串的块链存储表示(biosh)4.2.4 串的堆分配存储表示(biosh)第8页/共22页第九页，共22页。4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示(

9、biosh)(biosh)4.2.1.1 4.2.1.1 定义定义 定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：数组的上界预先给出：#define MAXSTRLEN 255/#define MAXSTRLEN 255/一个固定长度的存储区一个固定长度的存储区 /串的长度在这个范围内随意，超过串的长度在这个范围内随意，超过(chog

10、u)(chogu)这个长这个长 /度的串值则被舍去，既串被截断度的串值则被舍去，既串被截断 typedef unsigned char sstringMAXSTRLEN+1;typedef unsigned char sstringMAXSTRLEN+1;/0 /0号单元存放串的长度号单元存放串的长度 sstring s;/s sstring s;/s是一个可容纳是一个可容纳255255个字符的顺序串个字符的顺序串 第9页/共22页第十页，共22页。01 2345678910.MAXSIZE-110abcdefghij 012345678910.MAXSIZE-1abcdefghijk0 串的

11、顺序存储方式(fngsh)1串的顺序存储方式(fngsh)2 -定长顺序存储方式(fngsh)第10页/共22页第十一页，共22页。4.2.1.2 4.2.1.2 运算运算(yn sun)(yn sun)1.串联(chunlin)接Concat(&T,S1,S2)Status Concat(SString&T,SString S1,SString S2)/用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。if(S10+S20=MAXSTRLEN)/未截断 T1.S10 =S11.S10;TS10+1.S10+S20 =S21.S20;T0=S10+S20;uncut

12、=TRUE;else if(S10MAXSTRLEN)T 1.S10 =S11.S10;T S10+1.MAXSTRLEN =S21.MAXSTRLEN S10 ;T0=MAXSTRLEN;uncut=FLASE;else T 0.MAXSTRLEN =S11.MAXSTRLEN ;/T0=S10=MAXSTRLEN uncut=FLASE;return uncute;/Concat第11页/共22页第十二页，共22页。2.求子串SubString(&Sub,S,pos,len)Status SubString(SString&Sub,SString S,int pod,int len)/用S

13、ub返回(fnhu)串S的第pos个字符起长度为len的子串 /其中，1=pos=StrLengh(S)且0=len=StrLength(S)-pos+1 if(posS0|lenS0 pos+1)return EEROR;Sub1.len=Spos.pos+len-1;Sub0=len;return OK;/SubString第12页/共22页第十三页，共22页。4.2.1.3 优缺点 优点：连续顺序存储，特别适合于子串的搜索 缺点：a.对串进行插入(ch r)或删除子串操作时，要移动大量字符，耗时太多 b.串的长度必须预先确定，这不容易做到。第13页/共22页第十四页，共22页。4.2.2

14、 串的指针(zhzhn)表示 例如：S=“abcdef”的存储结构(jigu)具体形式见图4-4。a S b c d e f 图4-4 S串的链式存储示意图 charnext第14页/共22页第十五页，共22页。优缺点：优点：a.在对串进行子串的插入(ch r)和删除时，只要修改相应的指针就可 以完成 b.对串的长度没有限制，在存储空间足够大的情况下，可以表 示任意长度的串 缺点：a.以增加存储空间为代价 b.沿着指针作在子串的顺序搜索需要比定长顺序表示下子串的 搜索花更多的时间第15页/共22页第十六页，共22页。4.2.3 串的块链存储表示 （很少使用(shyng)，前面两种的折中方式）例

15、如：串S=“abcdef”的存储(cn ch)结构具体形式见图4-5。每块大小为4，划分成两块，并且链表带头结点。a b c d e f S 头结点 图4-5 S串的结点大小为 4的链式存储#第16页/共22页第十七页，共22页。4.2.4 串的堆分配(fnpi)存储表示 （根据串的具体长度分配(fnpi)空间，应用最多）（已分配区域）free（未分配区域）storestoreMAXSIZE;图4.8 堆结构示意图50705021sCh lengthMAXSIZE第17页/共22页第十八页，共22页。1.特点 所有串的串值都存储在地址连续的一个存储单元序列中，而每个串的首地址是在算法执行过程中

16、动态分配的，串的操作仍是基于”字符(z f)序列的复制“进行。2.串的堆分配存储表示(biosh)typedef struct int length;/串长 char*ch;/若是非空串，则按串长分配存储区，否则ch为NULL HString;第18页/共22页第十九页，共22页。Status StrInsert(HString&S,int pos,HString T)Status StrInsert(HString&S,int pos,HString T)/1=pos=StrLength(S)+1,/1=pos=StrLength(S)+1,在串在串S S的第的第pospos个字符之前插入个

17、字符之前插入(ch(ch r)r)串串T T if(posS.lenth+1)return ERROR;/pos if(posS.lenth+1)return ERROR;/pos不合法不合法 if(T.length)if(T.length)if(!(S.ch=if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char);(char*)realloc(S.ch,(S.length+T.length)*sizeof(char);exit(OVERFLOW);exit(OVERFLOW);for(i=S.length-1;i=pos-

18、1;-i)for(i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;S.chi+T.length=S.chi;S.chpos-1.pos+T.length-2=T.ch0.T.length-1;S.chpos-1.pos+T.length-2=T.ch0.T.length-1;S.length+=T.length;S.length+=T.length;return OK;return OK;/StrInsert/StrInsert第19页/共22页第二十页，共22页。注意：第pos个字符的时间(shjin)存储位置：定长顺序 pos 实际串存储位置下标从1开始 堆分配存储 pos-1 下标从0开始第20页/共22页第二十一页，共22页。作业(zuy)：4.5 4.6第21页/共22页第二十二页，共22页。