数据结构名师课件3

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

1、第四章串(string)4.1定义和运算一、定义串（或字符串），是由零个或多个字符组成的有限序列。一般记为：s="a1a2...an"(n>=0)其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Nullstring），如：s=""，它的长度为零；仅由空格组成的的串称为空格串，如：s="└┘"；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s="I’mastudent"的长度为13。串中任意个连续的字符组成的

2、子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。当一个字符在串中多次出现时，以该字符第一次在主串中出现的位置为该字符在串中的位置。例：a="BEI",b="JING",c="BEIJING",d="BEIJING"串长分别为3,4,7,8,且a,b都是c,d的子串。若称两个串是相等的，当且仅当这两个串的值相等。注意：在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如s1=‘a’与s2=〃

3、a〃两者是不同的，s1表示字符，而s2表示字符串。二、运算1、基本运算赋值（＝）连接（＋）求长度length（S）求子串substr（S，i，j）比较strcmp（S1，S2）2、常用运算插入insert（S，i，S1）删除delete（S，i，j）替换replace（S，i，j，S1）——把S中不满意的变量换为需要的变量。检索index（S，S1）——若找到，即S1是S的子串，则返回S中S1第一次出现的位置；否则，为0（或－1）。插入：在S中插入S1S="a1a2a3…ai-1ai…an"S1S=su

4、bstr(S,1,i-1)+S1+substr(S,i,length(S)-i-1)删除：S="a1a2a3…ai-1ai…ai+j-1ai+j…an"S=substr(S,1,i-1)+substr(S,i+j,length(S)-(i+j-1))索引：从S中取长度相等的元素与S1比较，否则后移。index("substring","str")=4index("substring","sr")=0替换：先删除后插入Replace（A,B,C）若B是A的子串，用C取代A中所有B。例：A＝"monday"

5、B＝"mon"C＝"thur"Repl（A,B,C）="thurday"Repl(A,"mon"，C)＝"monday"4.2串的存储对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。实现串名到串值的访问，在C语言中可以有两种方式：一是可以将串定义为字符型数组，数组名就是串名，串的存储空间分配在编译时完成，程序运行时不能更改。这种方式为

6、串的静态存储结构。另一种是定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分配是在程序运行时动态分配的，这种方式称为串的动态存储结构。串是一种特殊的线性表，因此串的存储结构表示也有两种方法：静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。一、串的静态存储结构类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式有两种

7、：（1）紧缩格式：即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分地利用了存储空间。但在串的操作运算时，若要分离某一部分字符时，则变得非常麻烦。data└┘structure此图是以4个字节为一个存储单元的存储结构，每个存储单元可以存放4个字符。对于给定的串s=〃data└┘structure〃，在C语言中采用字符＇＇作串值的结束符。串s的串值连同结束符的长度共15，只需4个存储单元。串值的紧缩格式存储用字符数组存放字符串时，其结构用C语言定义如下：#defineMAX

8、NUM<允许的最大的字符数>typedefstruct{charstr[MAXNUM];intlength;/*串长度*/}stringtype;/*串类型定义*/由上述讨论可知，串的顺序存储结构有两大不足之处：一是需事先预定义串的最大长度，这在程序运行前是很难估计的。二是由于定义了串的最大长度，使得串的某些操作受限，如串的联接运算等。（2）非紧缩格式：这种方式是以一个存储单元为单位，每个存储单元仅存放一个字符。这种存储方式的空间利用率较低