数据结构课件第4章.ppt

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

1、第4章　串返回总目录目　录4.1　串的类型定义4.2　串的表示和实现4.3　串的模式匹配算法4.4　串操作应用举例返回总目录●基本要求：1）了解串的概念、逻辑结构、存储结构；2）掌握串的表示与实现方法；3）掌握串的模式匹配算法；4）学会串的正确应用；●学习重点：1）串的表示与实现方法；2）串的模式匹配算法；4.1　串的类型定义4.1.1串的基本概念返回目录术语：1）串名：S.2）串值：'a1a2···an'，ai(1≤i≤n).3）串的长度：串中所包含的字符个数，如串‘abcde’的长度为5.4）空串：长度为0(n=0)的串，它不包含任

2、何字符，记作S=''(或S=φ).定义：串是由零个或多个任意字符组成的字符序列。一般记作：s='a1a2...an'(n>=0)4.1　串的类型定义4.1.1串的基本概念术语：5）空格串：由空格符(ASCII值32)组成的串，如S=‘’.注意S=‘’与S=‘’不同，前者是长度为1的非空串，它含有一个空格字符，而后者是长度为0的空串。6）子串：串中任意个连续的字符组成的子序列。比如'abcde'中的'bcd'.4.1　串的类型定义4.1.1串的基本概念用二元组的形式来定义串：串是一个二元组,string=(D,R)其中，D={a

3、i

4、ai∈字符集,i=1,2,···,n,n≥0}R={N}有序偶的集合N={

5、ai-1,ai∈D,i=2,3,···n}故串的逻辑结构和线性表极为相似。区别仅在D的定义上。线性表的数据对象可以是任意数据类型，而串的数据对象是字符集。4.1　串的类型定义4.1.2串的ADT定义ADTString{数据对象：D={ai

6、ai(-CharacterSet,i=1,2,...,n,n>=0}数据关系：R1={

7、ai-1,ai(-D,i=2,...,n}基本操作：StrAssign(&T,chars)//ch

8、ars是字符常量。生成一个其值//等于chars的串T。StrCopy(&T,S)//串S存在则由串S复制得串TStrEmpty(S)//串S存在则若S为空串,返回真否则返回假StrCompare(S,T)//串S和T存在,若S>T,则返回值大于0,//若S=T,则返回值=0,若S

9、联接//而成的新串SubString(&Sub,S,pos,len)//串S存在,//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1Index(S,T,pos)//串S和T存在,T是非空。1<=pos<=StrLength(S)//若主串S中存在和串T值相同的子串,则返回它在主串S中//第pos个字符之后第一次出现的位置,否则函数值为0Replace(&S,T,V)//串S,T和V存在,T是非空串,用V替换主串S中//出现的所有与T相等的不重叠的子串StrInsert(&S,pos,T)/

10、/串S和T存在,1<=pos<=StrLength(S)+1,//在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)//串S存在,1<=pos<=StrLength(S)-//len+1从串中删除第pos个字符起长度为len的子串DestroyString(&S)//串S存在,则串S被销毁}ADTString4.1　串的类型定义4.1.2串的ADT定义用一组地址连续的存储单元来存储串的字符序列。每个字符占用一个字节（Byte）。串中相邻的字符顺序地存放在相邻的字节中。4.2　串的表示和实现4.2.1串的定长顺序

11、存储表示DATASTRUCTURES11+11+21+15······图4.1　串的顺序存储结构定长顺序存储结构串定义：#definemaxlen255//允许最大的长度typedefunsignedcharString[maxlen+1];//下标0存放长度实现：串的联接函数、求子串的函数、求子串位置的定位函数返回目录1、串的联接函数Concat(L,s,t)4.2　串的表示和实现4.2.1串的定长顺序存储表示其中，L,s,t是String；[分析]相当于求L=s+t，若s与t连接后的串值长度超过maxlen，则超过部分将被截断。运算

12、结果有三种可能情况。1)length(s)+length(t)≤maxlenLength(s)Length(t)s.cht.chL.chLength(L)maxlen图4.2　串的联结操作示意图（1）1、串