《数据结构串》PPT课件.ppt

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

1、1第4章串一、基本内容：本章的基本内容是：串的概念、串的存储结构和串的基本操作。二、学习要点：1.熟悉串的基本操作的定义及利用这些操作实现串的各种操作的方法.2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法.3.掌握串的堆存储结构以及在其上实现串操作的基本方法.4.理解串的模式匹配算法及其改进的KMP算法.24.1串类型的定义串（String）是由零个或多个字符组成的有限序列。通常记作：Ｓ=‘c1c2…cn’(n≥0)其中，Ｓ是串名；串中的ci（１≤i≤n）可以是字母、数字、空格或其他字符。用引号括起来的部分是串值，即串S的内容，注意引号本身

2、不属于串。串的有关概念如下：34.1串类型的定义(1)串的长度串中字符的个数称为串的长度，如上面串Ｓ的长度为n。(2)空串不含有任何字符的串称为空串(ＮullString)，空串的长度为零。本教材用符号“Φ”表示空串。(3)空格串由一个或多个空格构成的串称为空格串（BlankString）,空格串长度为串中空格的个数。注意空格串不等于空串。44.1串类型的定义(4)子串与主串串中任意多个连续字符组成的子序列称为该串的子串；包含子串的串称为主串。(5)串中位置字符在序列中的序号称为该字符在串中的位置。(6)串相等两个字符串相等，是指两个字符串的值相等，也

3、就是说这两个字符串不仅长度相等，而且对应位置上的字符也相等。54.1串类型的定义（７）串比较两个串的比较实际上是ASCII码的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现ASCII码大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为较大者。6注：串的操作是以“串的整体”为操作对象。注：串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。注：子串在主串中的位置以子串的第一个字符在主串中的位置来表示。74.1串类型的定义对于串的基本操作大致有如下几种：（1）StrAssign(&T,c

4、hars)串赋值，将串值chars赋值给串T。（2）StrCopy(&T,S)串复制，将一个串s赋给串T。（3）StrEmpty(s)判串空，判断串s是否为空。84.1串类型的定义（4）StrCompare(s,t)串比较，若s>t，则返回值>0；若s=t，则返回值=0；若s

5、ub,s,pos,len)用Sub返回串s的第pos个字符开始长度为len的子串。（9）Index(s,t,pos)返回子串t在主串S中第pos个字符之后第一次出现的位置；若子串t不在主串S中，则函数值为0。（10）StrInsert(&s,pos,t)将串t插入到s的第pos个位置。104.1串类型的定义（11）StrDelete(&s,pos,len)子串删除，删除串s中第pos个字符开始为len的子串。（12）Replace(&s,t,v)子串替换，将串s中所有串t出现的位置均替换为v。（13）ClearString(&s)将s清为空串。（14）

6、DestroyString(&s)串s被销毁。114.2串的表示和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法:定长顺序存储表示,堆分配存储表示,串的链式存储结构。124.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配。它是用一组连续的存储单元来存放串中的字符序列。每个串预先分配一个固定长度的存储区域。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：#defineMAXSTRLEN255typedefunsignedcharsstring[MA

7、XSTRLEN+1];sstrings;//s是一个可容纳255个字符的顺序串,0号单元存放串的长度。实际串长可在所分配的固定长度区域内变动以下标为0的数组分量存放串的实际长度——PASCAL；在串值后加入””表示结束，此时串长为隐含值——C13串联结StatusConcat(sstring&t,sstrings1,sstrings2){if(s1[0]+s2[0])<=MAXSTRLEN{t.[1..s1[0]]=s1[1..s1[0]];t.[s1[0]+1..s1[0]+s2[0]]=s2[1..s2[0]];t.[0]=s1[0]+s2[0

8、];uncut=TRUE;}elseif(s1[0])<=MAXSTRLEN{t.[1..s1