数据结构(第4章).ppt

《数据结构(第4章).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第四章串⒈教学内容：4.1串及其基本运算4.2串的定长顺序存储及基本运算4.3串的堆存储结构⒉教学目的：⑴了解串的定义；⑵理解和领会串的存储方式；⑶掌握常用的串运算。1⒊教学重点：⑴串的基本概念、基本运算；⑵串的两种存储方式。⑶串的模式匹配算法。⒋教学难点：⑴串的模式匹配算法；⑵串的基本运算的综合应用⒌学时安排：4学时24.1串及其基本运算串的基本概念串的基本运算34.1.1串的基本概念串是由零个或多个任意字符组成的字符序列。一般记作：s=”s1s2…sn”。其中s是串名；在本书中，用双引号作为串的定界符

2、，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号;n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。4子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串的位置：子串的第一个字符在主串中的序号称为子串的位置。串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。54.1.2串的基本运算⒈求串长StrLength(s)⒉串赋值StrAs

3、sign(s1,s2)s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2是一个串常量时称为串赋值，是一个串变量称为串拷贝），操作结果是将s2的串值赋值给s1，s1原来的值被覆盖掉。⒊连接操作StrConcat(s1,s2,s)或StrConcat(s1,s2)两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变;后者是在s1的后面联接s2的串值，s1改变，s2不改变。⒋求子串SubStr(s,i,len)串s存在并且1≤i≤StrLeng

4、th(s)，0≤len≤StrLength(s)-i+1。操作结果是求得从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。⒌串比较StrCmp(s1,s2)操作结果是若s1==s2，操作返回值为0；若s1s2，返回值>0。6⒍子串定位StrIndex(s,t)s为主串，t为子串，操作结果是若t∈s，则操作返回t在s中首次出现的位置，否则返回值为0。⒎串插入StrInsert(s,i,t)串s,t存在，且1≤i≤StrLength(s)+1。操作结果是将串t插入

5、到串s的第i个字符位置上，s的串值发生改变。⒏串删除StrDelete(s,i,len)串s存在，并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果是删除串s中从第i个字符开始的长度为len的子串，s的串值改变。⒐串替换StrRep(s,t,r)串s,t,r存在且t不为空，操作结果是用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。串的基本操作中前５个操作是最为基本的，它们不能用其他的操作来合成，因此通常将这５个基本操作称为最小操作集。74.2串的

6、定长顺序存储及基本运算串的定长顺序存储定长顺序串的基本运算模式匹配84.2.1串的定长顺序存储用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#defineMAXSIZE256chars[MAXSIZE];则串的最大长度不能超过256。9如何标识实际长度？1.类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;定义一个串

7、变量：SeqStrings;这种存储方式可以直接得到串的长度：s.curlen+1。如图所示。102.在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用’’来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是’’来确定串是否结束，从而求得串的长度。113.设定长串存储空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，串值存放在s[1]~s[MAXSIZE]，字符的序号和存储位置一致，应用更为方

8、便。124.2.2定长顺序串的基本运算主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。设串结束用＇＇来标识。13⒈串连接串连接是把两个串s1和s2首尾连接成一个新串s。【算法4-1】串连接算法intStrConcat1(chars1[],chars2[],chars[]){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength