《串类型的定义》PPT课件.ppt

《《串类型的定义》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配算法4.4串操作应用举例—文本编辑10/6/20211第四章串4.1串类型的定义基本概念串(String)是由零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’，其中S是串名，单引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。空串(EmptyString)：长度为零的串。它不包含任何字符。空格串(BlankString)：由一个或多个空格组成的串。注意：空串和空格串的不同。10

2、/6/20212第四章串基本概念（续）子串：串中任意个连续字符组成的子序列。主串：包含子串的串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“Thisisastring”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。特别地，空串是任意串的子串，任意串是其自身的子串。10/6/20213第四章串基本概念（续）通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不

3、能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义constcharpath[]=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。10/6/20214第四章串串的抽象数据类型定义串的抽象数据类型定义见教材P71串的基本操作(13个)：StrAssign,Strcopy,StrEmpty,StrCompare,StrLength,ClearString,Concat,SubString,Inde

4、x,Replace,StrInsert,StrDelete,DestroyString许多高级语言均提供了串基本操作相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见教材及参考书。10/6/20215第四章串串变量及基本操作：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;求串长(length)intstrlen(chars);//求串的长度例如：cout<

5、copy(charto,charfrom);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcopy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charconcat(charto,charfrom)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。10/6/20217第四章串基本操作（续）例如：concat(s3,”/”)concat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比较（compare)intstrcompare(chars1,

6、chars2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2例如：result=strcompare(“baker”,”Baker”)result>0result=strcompare(“12”,”12”);result=0result=strcompare(“Joe”,”Joseph”);result<010/6/20218第四章串基本操作（续）（5）字符定位(index)charstrchr(chars,charc);该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,

7、”.”);p指向“file”之后的位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”最小操作子集：串赋值StrAssign、串比较Strcompare、求串长StrLength、串联接concat和求子串SubString。串的其余操作可由这些基本操作组合而成。10/6/20219第四章串4.2串的表示和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符