数据结构课件-(4).ppt

1、第第5 5章章 串串知 识 点串的有关概念和术语串的有关概念和术语串的基本运算串的基本运算串的存储方法串的存储方法串的模式匹配运算串的模式匹配运算难 点串的模式匹配运算算法串的模式匹配运算算法要 求 掌握串的逻辑结构掌握串的逻辑结构 掌握串的存储结构掌握串的存储结构 熟练掌握串的基本运算熟练掌握串的基本运算 能设计串的计简单算法能设计串的计简单算法 了解串的匹配运算算法的基本思想了解串的匹配运算算法的基本思想 5-1 串的定义和基本运算串的定义和基本运算5-2 串的表示和实现串的表示和实现5-3 串的基本运算串的基本运算 小小 结结实验实验5 串子系统串子系统习题习题55-1-1 串的定义串的

2、定义1. 串的定义串的定义 串（串（String）是由零个或）是由零个或多个任意字符多个任意字符组成的组成的有限序有限序列列。一般一般记作：记作： s=a1 a2 aian 其中其中s 是串名，用双是串名，用双引号引号括括起来起来的的字符序列字符序列为串值，为串值，但但引号本身并不属于引号本身并不属于串的串的内容内容。ai（1=i=n）是）是一个任意一个任意字符字符，它，它称为称为串的串的元素元素，是构成串的，是构成串的基本单位基本单位，i是它在是它在整整个个串串中的序号中的序号；n为串的为串的长度长度，表示表示串中所串中所包含包含的的字符个字符个数数。 2 2几个术语几个术语（1 1）长度长

3、度串中串中字符字符的的个数个数，称为称为串的串的长度长度。（2）空串空串长度长度为零的为零的字符串称为字符串称为空串。空串。（3）空格串空格串由由一个一个或或多个连续多个连续空格组成的串空格组成的串称为称为空格串。空格串。（4）串相等）串相等两个串是相等的，是指两个串的两个串是相等的，是指两个串的长度长度相等且相等且对对应字符应字符都相等。都相等。（5）子串子串串中串中任意连续任意连续的的字符字符组成的子组成的子序列称为序列称为该串的子该串的子串。串。（6）主串主串包含包含子串的串子串的串称为称为该子串的主串。该子串的主串。（7）模式匹配模式匹配子串的子串的定位运算定位运算又又称为称为串的串的

4、模式匹配模式匹配，是，是一一种种求子串的求子串的第一第一个个字符字符在主串中在主串中序号序号的的运算运算。被被匹配匹配的主串的主串称称为为目标串，子串目标串，子串称为模式称为模式。【例【例5-15-1】字符串字符串的的长度长度及子串的及子串的位置位置。 字符串字符串 字符串长度字符串长度 S1=SHANG 5 S2=HAI 3 S3=SHANGHAI 8 S4=SHANGHAI 9 / 表示表示空格，空格，下同下同 S1是是S3、S4的子串，的子串，S1在在S3、S4中的位置中的位置都为都为1。 S2也是也是S3、S4的子串，的子串，S2在在S3中的位置中的位置为为6； S2在在S4中的位置中

5、的位置为为7。3 3串的串的应用应用 在在汇编语言汇编语言和和高级语言高级语言的的编译程序编译程序中，中，源程源程序序和目标和目标程序都是程序都是以以字符串表示字符串表示的。在的。在事务处理事务处理程序程序中，如中，如客户客户的的姓名姓名、地址地址、邮政编码邮政编码、货物货物名称名称等，等，一般也是作为字符串数据处理一般也是作为字符串数据处理的。的。另外另外，信息信息检索系统，检索系统，文字编辑文字编辑系统，系统，语言翻译语言翻译系统等，系统等，也也都是都是以以字符串字符串数据数据作为处理对象作为处理对象的。的。5-1-2 5-1-2 串的串的输入输入与与输出输出1字符串字符串的的输入输入 在

6、在C语言语言中，中，字符串字符串的的输入输入有有两种两种方法：方法：（1）使用）使用scanf () 函数函数 使用使用scanf () 函数函数时，时，输入格式输入格式中要中要设置设置%s，再再加上字符数组名称加上字符数组名称。【例【例5-25-2】 char strchar str10;10; printfprintf( (Input your strInput your str: : );); scanf scanf( (%s%s,str,str);); 使用使用scanf ()方式输入方式输入时，时，字符串字符串中中不能含有不能含有空格。空格。 在在C+C+中还中还可以可以用用输入输入

7、流流对象对象cincin 。（2）使用）使用gets() 函数函数 格式格式为：为：gets(字符字符数组名数组名);【例【例5-35-3】char str10;char str10;printfprintf( (Input your strInput your str: : ););gets(strgets(str););使用使用getsgets ()方式输入方式输入时，时，字符串字符串中中允许含有允许含有空空格。格。 2字符串字符串的的输出输出 字符串字符串的的输出输出也有也有两种两种方法：方法： （1）使用）使用printf () 函数函数 使用使用printf () 函数函数时，时，输

8、出格式输出格式中要中要设置设置%s，再，再加上字符加上字符数组名。数组名。【例【例5-45-4】 printfprintf( (Your strYour str is %s is %s,str,str););l 在在C+中还中还可以可以用用输出输出流流对象对象cout 。（2）使用）使用puts () 函数函数格式格式为：为：puts (字符字符数组名数组名);【例【例5-55-5】 printfprintf( (Your strYour str is is );); puts (str); 5-1-3 串的基本运算串的基本运算求串长求串长LenStr(s) 操作条件操作条件：串：串s存在存在

9、 操作操作结果：求出串结果：求出串s的的长度长度。串连串连接：接：ConcatStr(s1,s2) 操作条件操作条件：串：串s，s1存在存在。 操作操作结果：新串结果：新串s1是串是串s1和串和串s2连接以后连接以后的新串，的新串，原串原串s2值值不变不变，串，串s1的值则的值则改变改变。 【例【例5-5-6 6】设设 s1=Micsosoft，s2=Office， 求两个求两个串连串连接的结果。接的结果。 操作操作结果结果：s1=MicsosoftOffice； s2=Office。 3. 求子串求子串SubStr (s,i,len)： 操作条件操作条件：串：串s存在存在。 操作操作结果：结

10、果：返回返回从串从串s的第的第i个个字符开始字符开始的的长度长度为为 len 的子串。的子串。len=0得到得到的是空串。的是空串。【例【例5-75-7】 SubStr (abcdefghi,3,4) = cdef” 4. 串串比较比较： EqualStr (s1,s2) 操作条件操作条件：串：串s1,s2存在存在。 操作操作结果：若结果：若s1= =s2，返回，返回值为值为0；若；若s1s2, 返返回回值值s2, 返回返回值值0。 5. 子串查找子串查找 IndexStr (s,t)：找子串：找子串t在主串在主串s中中首次首次出现出现的的位置位置（也称（也称模式匹配模式匹配）。）。 操作条件

11、操作条件：串：串s，t存在存在。 操作操作结果：若结果：若t是是s的子串，则的子串，则返回返回t在在s中中首次出首次出现现的的位置位置，否则返回否则返回值为值为0。【例例5-5-8 8】子串】子串定位定位 IndexStr (abcdebda,bc)=2 IndexStr (abcdebda,ba)= 0 6. 串串插入插入 InsStr (s,t,i) 操作条件操作条件：串：串s，t存在存在 操作操作结果：将串结果：将串t插入插入到串到串s 的第的第i个个字符字符前，前，s的串值的串值发生改变发生改变。 7. 串串删除删除 DelStr(s,i,len) 操作条件操作条件：串：串s存在存在

12、操作操作结果：结果：删除删除串串s 中第中第i个个字符字符起起长度长度为为len的的子串，子串，s的串值的串值改变改变。5-2-1 5-2-1 定长定长顺序存储顺序存储1定长定长存储存储的的描述描述 在在C+语言语言中，中，字符串顺序存储可以字符串顺序存储可以用用一个一个字符字符型数组和型数组和一个一个整型整型变量表示变量表示，其中字符其中字符数组数组存储存储串值，整型串值，整型变量表示变量表示串的串的长度长度。#define MAXLEN 100 typedef Struct char vecMAXLEN; int len; Str ; / 可用可用Str来来定义定义该该类型类型的结构体的结

13、构体变量变量2存储方式存储方式 当计算机按字节（当计算机按字节（Byte）为单位编址时，一个存储单元）为单位编址时，一个存储单元刚好存放一个字符，串中相邻的字符顺序地存储在地址相邻刚好存放一个字符，串中相邻的字符顺序地存储在地址相邻的存储单元中。的存储单元中。 当计算机按字（例如当计算机按字（例如1个字为个字为32位）为单位编址时，一个位）为单位编址时，一个存储单元可以由存储单元可以由4个字节组成。此时顺序存储结构又有非紧凑个字节组成。此时顺序存储结构又有非紧凑格式和紧凑格式两种存储方式。格式和紧凑格式两种存储方式。（1）非紧凑存储）非紧凑存储 设串设串S=String Structure，计

14、算机字长为，计算机字长为32位（位（4个个yte），用非紧凑格式一个地址只能存一个字符，见图），用非紧凑格式一个地址只能存一个字符，见图5-1。其优点是运算处理简单，但缺点是存储空间十分浪费。其优点是运算处理简单，但缺点是存储空间十分浪费。（2）紧凑存储）紧凑存储 同样存储同样存储S=String Structure，用紧凑格式一个地址，用紧凑格式一个地址能存四个字符，见图能存四个字符，见图5-2。 紧凑存储的优点是空间利用率高，缺点是对串中字符处紧凑存储的优点是空间利用率高，缺点是对串中字符处理的效率低。理的效率低。stringureS trin gStr u ct u r e 图图5-1

15、非紧凑格式非紧凑格式 图图5-2 紧凑格式紧凑格式5-2-2 链接存储链接存储 对于长度不确定的字符串的输入，若采用定长字符串存对于长度不确定的字符串的输入，若采用定长字符串存储就会产生这样的问题：存储空间定的大，而实际输入字符储就会产生这样的问题：存储空间定的大，而实际输入字符串长度小，则造成内存空间的浪费；反之，存储空间定的小，串长度小，则造成内存空间的浪费；反之，存储空间定的小，而实际输入字符串长度大，则不够存储。此时可采用链接存而实际输入字符串长度大，则不够存储。此时可采用链接存储的方法。储的方法。1链接存储的描述链接存储的描述 用链表存储字符串，每个结点有两个域：一个数据域用链表存储

16、字符串，每个结点有两个域：一个数据域（data）和一个指针域（）和一个指针域（next）。）。Data Next 其中其中: 数据域（数据域（data） 存放串中的字符；存放串中的字符； 指针域（指针域（next） 存放后继结点的地址。存放后继结点的地址。 仍然以存储仍然以存储S=String Structure为例，链接存储结构为例，链接存储结构如图如图5-3所示所示。 图图5-3 链接存储结构链接存储结构（1）链接存储的优点）链接存储的优点插入、删除运算方便；插入、删除运算方便；（2）链接存储的缺点）链接存储的缺点存储、检索效率较低。存储、检索效率较低。2串的存储密度串的存储密度 在各种串

17、的处理系统中，所处理的串往往很长或很多。在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几百万个字符，情报资料的几千万个条目，例如一本书的几百万个字符，情报资料的几千万个条目，这要求我们必须考虑字符串的存储密度。这要求我们必须考虑字符串的存储密度。 存储密度存储密度 = 串值所占的存储位串值所占的存储位 / 实际分配的存储位。实际分配的存储位。 串链接存储的存储密度小，存储量比较浪费，但运算串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串的连接等操作的实现比较方便。处理，特别是对串的连接等操作的实现比较方便。 S t r r S 图图5-4 大结点结构表示大结点结构表

18、示 这样一来，存储空间利用率明显提高，但插入、删除极这样一来，存储空间利用率明显提高，但插入、删除极不方便，所以链接存储的优点也消失了。由于字符串的特殊不方便，所以链接存储的优点也消失了。由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较性，用链表作为字符串的存储方式也不太实用，因此使用较少。少。3大结点结构大结点结构 为了提高存储空间的利用率，有人提出了大结点的结构为了提高存储空间的利用率，有人提出了大结点的结构（即串的链块表示）。（即串的链块表示）。 所谓大结点，就是一个结点的值域存放多个字符，以减所谓大结点，就是一个结点的值域存放多个字符，以减少链表中的结点数量，从而提

19、高空间的利用率。例如每个结少链表中的结点数量，从而提高空间的利用率。例如每个结点存放四个字符，如图点存放四个字符，如图5-4。st ringstr u ctu r e5-2-3 串的堆分配存储结构串的堆分配存储结构 在实际应用中，往往要定义很多字符串，并且各字符串在实际应用中，往往要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储（也称为索引存储），这是一种动态存储结构。配存储（也称为索引存储），这是一种动态存储结构。1堆分配存储的方法堆分配存储的方法（1）开辟一块地址连续的存储空间，用于存储各串的值，）

20、开辟一块地址连续的存储空间，用于存储各串的值，该存储空间称为该存储空间称为“堆堆”（也称为自由存储区）。（也称为自由存储区）。（2）另外建立一个索引表，用来存储串的名字（）另外建立一个索引表，用来存储串的名字（name）、）、长度（长度（length）和该串在）和该串在“堆堆”中存储的起始地址中存储的起始地址（Stradr）。）。（3）程序执行过程中，每产生一个串，系统就从）程序执行过程中，每产生一个串，系统就从“堆堆”中中分配一块大小与串的长度相同的连续空间，用于存储该串的分配一块大小与串的长度相同的连续空间，用于存储该串的值，值， 并且在索引表中增加一个索引项，用于登记该串的并且在索引表中

21、增加一个索引项，用于登记该串的名字、名字、 长度、和该串的起始地址。长度、和该串的起始地址。 2索引存储的例子索引存储的例子 设字符串：设字符串：A=”Red” B=”Yellow” C=”Blue” D=”White” 用指针用指针free指向堆中未使用空间的首地址。指向堆中未使用空间的首地址。 图图5-5 5-5 带长度的索引表带长度的索引表 Name A B C D Length 3 6 4 5 Stradr 堆堆： R e d Y e l l o w B l u E W h i t e free 索引表：索引表： 考虑到对字符串的插入和删除操作，可能引起串的长度考虑到对字符串的插入和删

22、除操作，可能引起串的长度变化，在变化，在“堆堆”中为串值分配空间时，可预留适当的空间。中为串值分配空间时，可预留适当的空间。这时，索引表的索引项应增加一个域，用于存储该串在这时，索引表的索引项应增加一个域，用于存储该串在“堆堆”中拥有的实际存储单元的数量。当字符串长度等于该串的实中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。际存储单元时，就不能对串进行插入操作。3带长度的索引表的带长度的索引表的C语言描述语言描述 如图如图5-5所示，索引项的结点类型为：所示，索引项的结点类型为： typedef Struct char nameMAXLEN; / 串

23、名串名 int length; / 串长串长 char *Stradr; / 起始地址起始地址 LNode;4 “堆堆”的管理的管理 C语言中用动态分配函数语言中用动态分配函数malloc( )和和free( )来管理来管理“堆堆” 利用函数利用函数malloc( )为每个新串分配一块实际串长所需要的存为每个新串分配一块实际串长所需要的存储空间，分配成功则返回一个指向起始地址的指针，作为串储空间，分配成功则返回一个指向起始地址的指针，作为串的基址，同时，约定的串长也作为存储结构的一部分。函数的基址，同时，约定的串长也作为存储结构的一部分。函数free( )则用来吸收用则用来吸收用malloc(

24、 )分配的存储空间。分配的存储空间。 在在C+语言中语言中malloc( )可用可用new替换，而替换，而free( )也可用也可用delete代替。代替。 在这里，我们仅仅简单的介绍了堆分配存储的基本思想，在这里，我们仅仅简单的介绍了堆分配存储的基本思想，具体的算法及细节尚未涉及。在常用的高级语言及开发环境具体的算法及细节尚未涉及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的库函数，用户可中，许多系统本身都提供了串的类型及串的库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠以直接调用，这样会使算法的设计和调试更方便容易，可靠性也更高。性也更高。 本小节主

25、要讨论定长串连接、求子串、串比较算法，顺本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除等运算。序串的插入和删除等运算。 为了讨论方便我们再次描述定长顺序串的结构如下：为了讨论方便我们再次描述定长顺序串的结构如下： #define MAXLEN 100 / 定义串的最大长度定义串的最大长度 typedef struct char vecMAXLEN; int len; / 串的实际长度串的实际长度 Str ; / 定义一个结构体类型定义一个结构体类型Str 在串尾存储一个不会在串中出现的特殊字符作为串的终在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比

26、如结符，以此表示串的结尾。比如C语言中处理定长串的方法语言中处理定长串的方法就是这样的，它是用就是这样的，它是用0来表示串的结束，如图来表示串的结束，如图5-6所示。所示。图图5-6 串的定长顺序存储串的定长顺序存储1求串的长度求串的长度 用判断当前字符是否是用判断当前字符是否是0来确定串是否结束，若非来确定串是否结束，若非0，则表示字符串长度的则表示字符串长度的i加加1；若是；若是0，则表示字符串结束，则表示字符串结束，跳出循环，跳出循环，i即字符串的长度。即字符串的长度。 int LenStr (Str *r) while(r-veci!= 0)i+;return i; E NG L I

27、S H O 0 1 2 3 4 5 6 7 MAXLEN-12串连接：串连接： 把两个串把两个串r1和和r2首尾连接成一个新串首尾连接成一个新串r1 ，即：，即：r1=r1+r2。 void ConcatStr(Str *r1,Str *r2) if(r1-len+r2-lenMAXLEN) / 连接后的串长超过串的最大长度连接后的串长超过串的最大长度 printf(两个串太长，溢出！两个串太长，溢出！); else for(i=0;ilen;i+) r1-vecr1-len+i=r2-veci; / 进行连接进行连接 r1-vecr1-len+i=0; r1-len=r1-len+r2-le

28、n; / 修改连接后新串的长度修改连接后新串的长度 3求子串求子串 在给定字符串在给定字符串r中从指定位置中从指定位置i开始连续取出开始连续取出j个字符构个字符构成子串成子串r1。 void SubStr(Str *r,int i,int j) if (i+j-1r-len) printf(子串超界子串超界!); return; else for (k=0;kveck=r-veci+k-1; / 从从r中取出子串中取出子串r1-len=j;r1-vecr1-len=0; printf(取出字符为：取出字符为：); puts(r1-vec); 4. 串相等比较串相等比较 两个串的长度相等且各对应

29、位置上的字符都相等时，两两个串的长度相等且各对应位置上的字符都相等时，两个串才相等。个串才相等。 int EqualStr (Str *r1, Str *r2) for (int i=0;r1-veci= =r2-veci&r1-veci;i+); return r1-veci-r2-veci; / 相等返回相等返回0 5 插入子串插入子串 在字符串在字符串r中的指定位置中的指定位置i插入子串插入子串r1。str *InsStr (Str *r, Str *r1,int i) if ( i=r-len | r-len+r1-lenMAXLEN ) printf (不能插入不能插入!); els

30、e for ( k=r-len-1;k=i;k-) r-vecr1-len+k=r-veck; / 后移空出位置后移空出位置 for (k=0;klen;k+) r-veci+k=r1-veck; / 插入子串插入子串r1 r-len=r-len+r1-len; r-vecr-len=0; return r; 6删除子串删除子串 在给定字符串在给定字符串r中删除从指定位置中删除从指定位置i开始连续开始连续j个字符。个字符。 void DelStr(Str *r,int i,int j) / i为指定删除的位置，为指定删除的位置， j为连续删除的字符个数为连续删除的字符个数 if (i+j-1r

31、-len) printf (所要删除的子串超界！所要删除的子串超界！); else for (k=i+j;klen;k+,i+) r-veci=r-veck; / 将后面的字符串前移覆盖将后面的字符串前移覆盖 r-len=r-len-j; r-vecr-len=0; 7. 模式匹配模式匹配 模式匹配即子串定位运算。设模式匹配即子串定位运算。设s和和t是给定的两个串，在是给定的两个串，在主串主串s中找到等于子串中找到等于子串t的过程称为模式匹配。其中被匹配的的过程称为模式匹配。其中被匹配的主串主串s称为目标串，匹配的子串称为目标串，匹配的子串t称为模式。称为模式。 在此，我们只介绍一种最简单的模

32、式匹配算法。在此，我们只介绍一种最简单的模式匹配算法。（1）基本思想：）基本思想： 首先将首先将s1与与t1进行比较，若不同，就将进行比较，若不同，就将s2与与t1进行比较，进行比较，直到直到s的某一个字符的某一个字符si和和t1相同，再将它们之后的字符进行比相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当较，若也相同，则如此继续往下比较，当s的某一个字符的某一个字符si与与t的字符的字符tj不同时，则不同时，则s返回到本趟开始字符的下一个字符，即返回到本趟开始字符的下一个字符，即si-j+2，t返回到返回到t1，继续开始下一趟的比较，重复上述过程。，继续开始下一趟的比较，重

33、复上述过程。若若t中的字符全部比较完，则说明本趟匹配成功，本趟的起中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是始位置是ij+1，否则，匹配失败。，否则，匹配失败。（2）模式匹配的例子）模式匹配的例子 主串主串s=ABABCABCACBAB，模式，模式t=ABCAC“。（3）算法描述：）算法描述： 返回在字符串返回在字符串r中子串中子串r1出现的位置。出现的位置。int IndexStr(Str *r, Str *r1) int i,j,k; for (i=0;r-veci;i+) for (j=i,k=0;r-vecj= =r1-veck;j+,k+)if (!r1-veck+1)

34、 return i;return -1; （4）时间复杂度分析）时间复杂度分析 设串设串s长度为长度为n，串，串t长度为长度为m。匹配成功的情况。匹配成功的情况下，考虑两种极端情况：下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：字符比较时： 例如：例如：s=AAAAAAAAAABC t=BC 设匹配成功发生在设匹配成功发生在si处，则字符比较次数在前面处，则字符比较次数在前面i-1趟匹配中共比较了趟匹配中共比较了i-1次，第次，第i趟成功的匹配共比较趟成功的匹配共比较了了m次，所以总共比较了次，所以总共比较了i-1+m

35、次，所有匹配成功的次，所有匹配成功的可能共有可能共有n-m+1种，设从种，设从si开始与开始与t串匹配成功的概串匹配成功的概率为率为pi，在等概率情况下，在等概率情况下pi=1/(n-m+1)，因此最好情，因此最好情况下的平均比较次数是：况下的平均比较次数是：2)()1()1(111111mnmimipmnimnmnii 即最好情况下的时间复杂度是即最好情况下的时间复杂度是O(n+m)。 在最坏情况下，每趟不成功的匹配都发生在在最坏情况下，每趟不成功的匹配都发生在t的最后一的最后一个字符。个字符。 例如：例如：s=AAAAAAAAAAAB t=AAAB 设匹配成功发生在设匹配成功发生在si处，

36、则在前面处，则在前面i-1趟匹配中共比较了趟匹配中共比较了(i-1)*m次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共比较次，所以总共比较了了i*m次，因此最坏情况下平均比较的次数是：次，因此最坏情况下平均比较的次数是：2)2()()(111111mnmmimipmnimnmnii 因为因为nm，所以最坏情况下的时间复杂度是，所以最坏情况下的时间复杂度是O (n*m)。（1 1）串是）串是有限有限个个字符字符组成的组成的序列序列，一个一个串的串的字字符个数叫做符个数叫做串的串的长度长度，长度长度为零的为零的字符串称为字符串称为空串。空串。（2 2）串是）串是一种一种特殊的

37、线性表，特殊的线性表，规定每个规定每个数据数据元元素素仅由仅由一个字符一个字符组成。组成。（3 3）串的）串的顺序存储顺序存储有非有非紧凑格式紧凑格式和和紧凑格式两紧凑格式两种种，非，非紧凑格式存储操作简单紧凑格式存储操作简单，但，但内存浪费内存浪费；紧凑格式可以节省内存紧凑格式可以节省内存，但，但操作操作却不却不方便方便。（4 4）串的链式）串的链式存储存储结构结构具有插入具有插入、删除方便删除方便的的优点优点，但其但其存储密度存储密度很低；若很低；若采用紧凑采用紧凑的链式的链式存储存储（一一个个结点放结点放多个字符多个字符），），虽然提高虽然提高了了空间利用率空间利用率，但其但其插入插入、

38、删除方便删除方便的的优点优点也随之也随之消失消失。（5 5）串的堆）串的堆分配存储分配存储是是一种动态存储一种动态存储结构，用结构，用一个一个索引索引表来表来存放存放串名，串名，长度长度及在堆及在堆中的起始地址中的起始地址，并用并用一块地址连续一块地址连续的的存储空间存储空间，存放存放各串的值，各串的值，灵活性强。灵活性强。（6）串的串的基本运算包括基本运算包括串的串的连接连接、插入插入、删除删除、比比较较、替换、和、替换、和模式匹配模式匹配等，等，要求重点要求重点掌握串的定掌握串的定长长顺序存储顺序存储的的基本基本算法。算法。1 1实验实验目的目的（1 1）掌握串的特点及掌握串的特点及顺序顺

39、序定长定长存储存储的的方式方式。（2 2）掌握串的）掌握串的创建创建、连接连接、插入插入、删除删除、显示等、显示等操作操作。（3 3）掌握串的查找、取子）掌握串的查找、取子字符串字符串、比较比较串串大小大小的的操作操作。（4 4）掌握）掌握模式匹配模式匹配的的基本基本思想思想及其及其算法。算法。2 2实验内容实验内容（1 1）由用户）由用户通过键盘输入建立一个字符串通过键盘输入建立一个字符串；（2）编写插入编写插入、删除删除、查找、查找、比较比较、取子、取子字符串字符串、连接连接字符串字符串、显示、显示、模式匹配模式匹配等等程序程序。（3）设计一个选择设计一个选择式式菜单菜单，以，以菜单方式选

40、择上述操作菜单方式选择上述操作。 串串 子子 系系 统统* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1- 1-输输 入入 字字 串串 * * * 2- 2-连连 接接 字字 串串 * * * 3- 3-取取 出出 子子 串串 * * * 4- 4-删删 除除 子子 串串 * * * 5- 5-插插 入入 子子 串串 * * * 6- 6-查查 找找 子子 串串 * * * 7- 7-比比 较较 串串 大大 小小 * * * 8- 8-显显 示示 字字 串串 * * * 0- 0-返返 回回 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 请请输入菜单选项输入菜单选项: :（P97P97串子系统参考程序的第串子系统参考程序的第3 3行：行：typedef Struct typedef Struct 改为：改为：typedef typedef s structtruct）返回参见习题答案返回返回