资源描述：
《数据结构ppt 第4章 串课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章串4.1串的类型定义4.2串的表示和实现4.3串的模式匹配算法**4.4串的操作应用举例**14.1串的类型定义---概念及术语串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。记为：s=‘a1,a2,……..,an’(n≥0)串名串值（用‘’括起来）24.1串的类型定义---概念及术语串长、空串：串长即串中字符个数n（n≥0）;当n=0时称为空串。空格串：由一个或多个空格符组成的串。子串：串s中任意个连续的字符序列叫s的子串;对应地，s叫主串。子串位置：子串的
2、第一个字符的序号。字符位置：字符在串中的序号。串相等：两串的长度相等，且对应位置上字符相等。34.1串的类型定义---串的抽象数据类型定义ADTString{数据对象：D={ai
3、ai∈CharacterSet,i=1,2,…，n,n≥0}数据关系:R1={
4、ai-1,ai∈D,i=2,…，n}基本操作:StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若S>T，返回值大于0…StrLength(S)//求串长，即返
5、回S的元素个数Concat(&T,S1,S2)//串连接，用T返回S1＋S2的新串SubString(&Sub,S,pos,len)//求S中pos起长度为len的子串……Index(S,T,pos)//返回子串T在pos之后的位置Replace(&S,T,V)//用子串V替换子串T}ADTString44.1串的类型定义---用基本操作实现实位函数IndexintIndex(StringS,StringT,intpos){//T非空，返回主串S中pos之后第一个子串的位置，否则返回0if(pos>
6、0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)i++;elsereturni;//返回子串在主串中的位置}//while}//ifreturn0;//S中不存在与T相等的子串}//Index54.2串的表示和实现定长顺序存储表示——用一组地址连续的存储单元存储串值的字符序列堆分配存储表示——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在
7、程序执行过程中动态分配而得。串的块链存储表示——链式方式存储串有三种机内表示方法：顺序存储链式存储64.2串的表示和实现---定长顺序存储表示定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。#defineMaxstrlen255//用户可用的最大串长typedefunsignedcharSString[Maxstrlen＋1];SStrings;//s是一个可容纳255个字符的顺序串。注：一般用SString[0]来存放串长信息；
8、C语言约定在串尾加结束符‘ ’，以利操作加速，但不计入串长；若字符串超过Maxstrlen则自动截断（因为静态数组存不进去）。74.2串的表示和实现---定长顺序存储表示例：用顺序存储方式实现 求子串函数SubString(&Sub,S,pos,len)将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样）S[0]：串长StatusSubString(SString&sub,SStringS,intpos,intlen){if(pos<1
9、
10、pos>S
11、[0]
12、
13、len<0
14、
15、len>S[0]-pos+1)returnERROR;//参数不合法则告警Sub[1……len]=S[pos……pos+len-1];Sub[0]=len;returnOK;}84.2串的表示和实现---堆分配存储表示堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。思路：利用malloc函数合理预设串长空间。特点：若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。typedefstruct{char*ch;/
16、/若非空串,按串长分配空间;//否则ch=NULLintlength;//串长度}HString94.2串的表示和实现---堆分配存储表示例：用“堆”实现串插入操作StatusStrInsert(HString&S,intpos,HStringT){//在串S的第pos个字符之前（包括尾部）插入串Tif(pos<1
17、
18、pos>S.length+1)returnERROR;//pos不合法则告警if(T.length){//只要串T不空，就需要重新分配S空间，以便插入T
