数据结构第4章PPT讲义课件.ppt

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

1、第四章串本章内容1串的基本概念2串的存储表示3串基本操作的实现4串的模式匹配5串操作应用第四章串4.1串的基本概念和存储结构4.1.1串的基本概念1．串定义：串是零个或多个字符组成的有限序列。一般记作：S=“a1a2a3…an”其中S：串名；“a1a2a3…an”：串值，双引号括起来的字符序列；ai(1≤i≤n)可以是字母、数字或其它字符；n为串的长度，n=0的串称为空串；比较：栈、队列：操作受限的线性表。串：取值范围受限的线性表，数据对象为字符集中的字符。2．串有关术语串长：串中所包含的字符个数；例如：S=“Thisi

2、sastring”，串长为16。空串：长度为零的串，它不包含任何字符。S=“”空白串:仅由一个或多个空格组成的串。S=“”注意：空串和空白串的不同。子串：串中任意个连续字符组成的子序列。主串：包含子串的串相应地称为主串。注意：空串是任意串的子串，任意串是其自身的子串。例如：设S为一长度为n的串，其中的字符各不相同，则S的所有子串的个数为：1＋1＋2＋3＋…＋（n－1）＋n＝n（n＋1）/2＋1子串在主串中的位置：指子串在主串中首次出现时，该子串的首字符对应的主串中的序号。例如：设A和B分别为A=“Thisisastrin

3、g”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。串相等：当且仅当两个串的值相等。即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。3．串的抽象数据类型定义：ADTString{数据对象：D={ai

4、ai属于字符集合，i=1,2,…,n,n>=0}数据关系：R={

5、ai,ai-1属于集合D，i=1,2,…,n}基本操作：串赋值：StrAssign(T,S)串复制：strcopy(T，S)串相等：StrEqual(S，

6、T)判串空：StrEmpty(S)求串长：StrLength(S)串联接:StrConcat(S，T)求子串:SubStr(S，i，j)串插入：InsStr(s1，i，s2)串删除：DelStr(S，i，j)串替换：RepStr(S，i，j，t)串比较：StrCompare(S,T)串输出：DispStr(S)}ADTString4.1.2串的存储结构1.串的顺序存储结构---顺序串用一组连续存储单元存储串。静态分配存储空间。#defineMAXLEN100Typedefstruct{charch[MAXLEN];int

7、length;}SString;2.串的堆式存储结构用一组连续存储单元存储串。动态分配存储空间。Typedefstruct{char*ch;intlength;}HString;3.串的链式存储结构-----略4.2串基本操作的实现1.串赋值voidStrAssign(SString&s,charcstr[]){inti;for(i=0;cstr[i]!=’’;i++)s.ch[i]=cstr[i];s.length=i;}2.串连接假设T,S1,S2都是SString类型的串，T是S1连接S2后得到的串，有3

8、三种情况：（1）S1.length+S2.length<=MAXLEN;（2）S1.length+S2.length>MAXLEN,而S1.length

9、]=S2.ch[i];T.length=S1.length+S2.length;return1;}elseif(S1.length

10、urn0;}}3.求子串intSubStr(SStrings,intpos,intlen,SString&sub){intiif(pos<1

11、

12、pos>s.length

13、

14、len>(s.length-pos+1)

15、

16、len<0)return0;for(i=pos-1;i