《数据结构串》PPT课件

《《数据结构串》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串陈守孔孟佳娜陈卓本章目录4.1串类型的定义4.2串的表示和实现4.2.1串的顺序存储结构4.2.2串的链式存储结构4.3串的模式匹配4.3.1朴素的模式匹配算法4.3.2KMP算法4.4串的应用举例4.5算法设计举例2知识点和难点重点知识点基本概念串操作模式匹配难点重点根据给定操作，编写其它操作的算法(如，根据前5个基本操作，编写index,replace操作KMP算法模式串的next和nextval函数值手工模拟KMP算法的执行过程串的其它算法。3定义和概念串（String）:由零个或

2、多个字符组成的有限序列。记为：s=’a1a2…an’（n≥0）概念：s为串名‘a1a2…an’为串值n为串的长度ai，字符n=0，空串（NullString），记为：Ф若ai都是‘’，则称为空格串(blankstring)子串：串中任意连续个字符组成的子序列被称为该串的子串，包含子串的串又被称为该子串的主串子串在主串中的位置：串的相等：两个串的串值相等（两个串的长度相等，并且各个对应的字符也都相同）4串的操作串赋值：StringAssign(S,T)求串长：StringLenth(S)串判等：S

3、tringEqual(S,T)串联接：StringConcat(S,T)求子串：SubString(S,start,length)子串定位：Index(S,T)置换：Replace(S,T,V)插入子串：StringInsert(S,start,T)删除子串：StringDelete(S,start,length)（其中，前5个操作为基本操作。）5串运算举例串运算的例子：长度分别为18、7、3、3；且b、c、d都是a的子串；b在a中的位置是1，c在a中的位置是12；c和d两串相等例：a=’Wel

4、cometoBeijing’b=’Welcome’c=’Bei’d=’Bei’6子串定位（index）的实现intIndex(StringS,StringT){∥若主串S第i个字符之后存在与T相等的子串，则返回T串在S中的位置，否则返回0n=StringLength(S);m=StringLength(T);i=1;while(i<=n-m+1)∥当i加上T的长度超过串S的长度结束{StringAssign(sub,SubString(S,i,m));if(StringEqual(sub,T)＝

5、＝0)returni;else++i;}∥whilereturn0;∥S中不存在与T相等的子串}∥Index利用已给操作，求其它操作，是本章的一个重点。下面是利用求串长、取子串和串的判等操作，求子串定位操作。7串的表示和实现串的顺序存储结构:用一组连续的存储单元依次存储串中的字符序列。字符数组表示法事先定义字符串的最大长度在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符（’’）作为字符串的结束标志链式表示每个结点一个字符的单链表表示

6、法每个结点多个字符的块链存储表示8串的表示和实现字符数组表示法#defineMAXSIZE1024∥串的最大容量typedefstruct{charch[MAXSIZE];∥存放串的数组intcurlen;∥curlen是串的当前长度}STring;事先定义字符串的最大长度#defineMAX_STRING256∥0号单元存放串的长度，字符从1号单元开始存放typedefunsignedcharString[MAX_STRING];9串的堆表示法在程序执行过程中，利用标准函数malloc和fre

7、e动态地分配或释放存储字符串的存储单元，并以一个特殊的字符（’’）作为字符串的结束标志。typedefstruct{char*str;intlength;}STRING;10基本操作:串的赋值intStringAssign(STRING*S,*T)∥将串T的值赋给串S{if(S->str)free(S->str);∥若s已经存在，将它占据的空间释放掉len=T->length;∥T串的长度S->length=len;∥赋予字符串长度if(!len)∥空串{S->str=(char*)mall

8、oc(sizeof(char));S->str[0]=’’;}else∥非空串{S->str=(char*)malloc((len+1)*sizeof(char));∥分配空间if(!S->str)returnERROR;for(i=0;i<=len;i++)∥对应的字符赋值S->str[i]=T->str[i];}∥ifreturnOK;}∥StringAssign11基本操作:串联接intStringConcat(STRING*S,*T){∥将串T联接到串S后STRINGtemp;Str