第四课时串的基本概念.ppt

4.1 串类型的定义 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃a1a2…an〃 (n≥0) 其中：s为串名，用双引号括起来的字符序列是串的值；ai(0≤i≤n)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；串中字符的数目n称为串的长度。 空串——零个字符的串，通常以两个相邻的双引号来表示空串（Null string），如：s=〃〃，它的长度为零； 空格串——仅由空格组成的的串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’m a student〃的长度为13。 第四章 串的基本概念 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 串的抽象数据定义：P71 对于串的基本操作集可以有不同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。 定位算法（P72） —— Index（S，T，pos） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.2 串的表示和实现 对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。 串的3种机内表示方式： 定长顺序存储表示 堆分配存储表示 串的块链存储表示 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.2.1 定长顺序存储表示 实现：用一组地址连续的存储单元存储串值的字符序列。 存储表示 #define MAXSTRLEN 255 Typedef unsigned char String[MAXSTRLEN+1] 截断——超过与定义长度的串值被舍去。 串长的两种表示： 下标为0的分量存放串的实际长度，如：pascal 在串尾加一个不计入串长的结束标记符。如：C中的‘\0’ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 串连接算法Concat（T，S1，S2） Status Concat(SString T, SString S1,SString S2){ //用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。S[0] //保存串的长度,有三种情况(1)S1[0]+S2[0]=MAXSTRLEN;(2)S1[0]MAXSTRLEN //S1[0]+S2[0]MAXSTRLEN;(3)S1[0]=MAXSTRLEN 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]=S