实用数据结构基础(中国铁道出版社第三版)第5章串

《实用数据结构基础(中国铁道出版社第三版)第5章串》由会员分享，可在线阅读，更多相关《实用数据结构基础(中国铁道出版社第三版)第5章串（44页珍藏版）》请在装配图网上搜索。

1、2011年5月11日星期三1第 5 5 章 串 知 识 点串的有关概念和术语串的有关概念和术语串的基本运算串的基本运算串的存储方法串的存储方法串的模式匹配运算串的模式匹配运算 难 点串的模式匹配运算算法串的模式匹配运算算法 要 求 掌握串的逻辑结构掌握串的逻辑结构 掌握串的存储结构掌握串的存储结构 熟练掌握串的基本运算熟练掌握串的基本运算 能设计串的计简单算法能设计串的计简单算法 了解串的匹配运算算法的基本思想了解串的匹配运算算法的基本思想 第 5 章 目录 5-1 串的定义和基本运算串的定义和基本运算 5-2 串的表示和实现串的表示和实现 5-3 串的基本运算串的基本运算 小小 结结 验证性

2、实验验证性实验5 串子系统串子系统 自主设计实验字符串分割处理自主设计实验字符串分割处理 单元练习单元练习5-1 串的定义和基本运算5-1-1 串的定义串的定义1.串的定义串的定义 串（串（String）是由零个或多个任意字符组成的有限序是由零个或多个任意字符组成的有限序列。一般记作：列。一般记作：s=a1 a2 aian 其中其中s 是串名，用双引号括起来的字符序列为串值，是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。但引号本身并不属于串的内容。ai（1=i=n）是一个任是一个任意字符，它称为串的元素，是构成串的基本单位，意字符，它称为串的元素，是构成串的基本单位，i是

3、它在是它在整个串中的序号；整个串中的序号；n为串的长度，表示串中所包含的字符为串的长度，表示串中所包含的字符个数。个数。2 2几个术语几个术语（1 1）长度长度串中字符的个数，称为串的长度。串中字符的个数，称为串的长度。（2）空串空串长度为零的字符串称为空串。长度为零的字符串称为空串。（3）空格串空格串由一个或多个连续空格组成的串称为空格串。由一个或多个连续空格组成的串称为空格串。（4）串相等串相等两个串是相等的，是指两个串的长度相等且对应字符两个串是相等的，是指两个串的长度相等且对应字符都相等。都相等。（5）子串子串串中任意连续的字符组成的子序列称为该串的子串。串中任意连续的字符组成的子序列

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

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

6、言翻译系统等，也都是以字符串数据作为处理对象的。等，也都是以字符串数据作为处理对象的。5-1-2 5-1-2 串的输入与输出串的输入与输出1字符串的输入字符串的输入 在在C语言中，字符串的输入有两种方法：语言中，字符串的输入有两种方法：（1）使用使用scanf()函数函数 使用使用scanf()函数时，输入格式中要设置函数时，输入格式中要设置%s，再加上字符数组名称。再加上字符数组名称。【例【例5-25-2】char str10;char str10;printf(printf(Input your str:Input your str:););scanf(scanf(%s%s,str);,s

7、tr);使用使用scanf()方式输入时，字符串中不能含有空格方式输入时，字符串中不能含有空格 在在C+C+中还可以用输入流对象中还可以用输入流对象cin cin。（2）使用使用gets()函数函数 格式为：格式为：gets(字符数组名字符数组名);【例【例5-35-3】char str10;char str10;printf(printf(Input your str:Input your str:););gets(str);gets(str);使用使用getsgets()方式输入时，字符串中允许含有空格。方式输入时，字符串中允许含有空格。2字符串的输出字符串的输出 字符串的输出也有两种方法

8、：字符串的输出也有两种方法：（1）使用使用printf()函数函数 使用使用printf()函数时，输出格式中要设置函数时，输出格式中要设置%s，再再加上字符数组名。加上字符数组名。【例【例5-45-4】printf(printf(Your str is%sYour str is%s,str);,str);在在C+中还可以用输出流对象中还可以用输出流对象cout。（2）使用使用puts()函数函数格式为：格式为：puts(字符数组名字符数组名);【例【例5-55-5】printf(printf(Your str is Your str is););puts(str);5-1-3 串的基本运算串

9、的基本运算（）求串长求串长LenStr(s)操作条件：串操作条件：串s存在存在 操作结果：求出串操作结果：求出串s的长度。的长度。（）串连接：串连接：ConcatStr(s1,s2)操作条件：串操作条件：串s1，s2存在。存在。操作结果：新串操作结果：新串s1是串是串s1和串和串s2连接以后的新串，原串连接以后的新串，原串s2值不变，串值不变，串s1的值则改变。的值则改变。【例【例5-5-6 6】设】设 s1=Microsoft，s2=Office，求两个串连接的结果。求两个串连接的结果。操作结果操作结果：s1=MicrosoftOffice；s2=Office。（3）求子串求子串SubStr

10、(s,i,len)：操作条件：串操作条件：串s存在。存在。操作结果：返回从串操作结果：返回从串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)操作条件

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

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

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

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

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

17、2串的存储密度串的存储密度 在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几百万个字符，情报资料的几千万个条目，这要求我们必须考虑字符串的存储密百万个字符，情报资料的几千万个条目，这要求我们必须考虑字符串的存储密度。度。存储密度存储密度=串值所占的存储位串值所占的存储位/实际分配的存储位。实际分配的存储位。串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串的连接等操作的实现比较方便。的连接等操作的实现比较方便。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 带长度的索引表带长度的索引表 考虑到对字符串的插入和删除操作，可能引起串的长度变化，在考虑到对字符串的插入和删除操作，可能引起串的长度变化，在“堆堆”中为串值分配空间时，可预留适当的空间。这时，索引表的索引项应增加一个中为串值分配空间时，可预留适当的空间。这时，索引表的索引

22、项应增加一个域，用于存储该串在域，用于存储该串在“堆堆”中拥有的实际存储单元的数量。当字符串长度等于中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。该串的实际存储单元时，就不能对串进行插入操作。3带长度的索引表的带长度的索引表的C语言描述语言描述 如图如图5-5所示，索引项的结点类型为：所示，索引项的结点类型为：typedef Struct char nameMAXLEN;/串名串名 int length;/串长串长 char *Stardt;/起始地址起始地址 LNode;4C语言中用动态分配函数语言中用动态分配函数malloc()和和free()来

23、管理来管理“堆堆”利用函数利用函数malloc()为每个新串分配一块实际串长所需要的存储空间，分配为每个新串分配一块实际串长所需要的存储空间，分配成功则返回一个指向起始地址的指针作为串的基址，同时，约定的串长也作为成功则返回一个指向起始地址的指针作为串的基址，同时，约定的串长也作为存储结构的一部分。函数存储结构的一部分。函数free()则用来吸收用则用来吸收用malloc()分配的存储空间。分配的存储空间。在在C+语言中语言中malloc()可以用可以用new替换，而替换，而free()也可以用也可以用delete代替。代替。在这里，只简单介绍了堆分配存储的基本思想，具体的算法及细节尚未涉在这

24、里，只简单介绍了堆分配存储的基本思想，具体的算法及细节尚未涉及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠性库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠性也更高。也更高。本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除等运算。等运算。为了讨论方便我们再次描述定长顺序串的结构如下：为了讨论方便我们再次描述定长顺序串的结构如下：#define

25、MAXLEN 100 /定义串的最大长度定义串的最大长度 typedef struct char vecMAXLEN;int len;/串的实际长度串的实际长度 Str;/定义一个结构体类型定义一个结构体类型Str 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如的结尾。比如C语言中处理定长串的方法就是这样的，它是用语言中处理定长串的方法就是这样的，它是用0来表示串的结来表示串的结束，如图束，如图5-6所示。所示。图图5-6 串的定长顺序存储串的定长顺序存储1求串的长度求串的长度 用判断当前字符是否是用

26、判断当前字符是否是0来确定串是否结束，若非来确定串是否结束，若非0，则表示字符，则表示字符串长度的串长度的i加加1；若是；若是0，则表示字符串结束，跳出循环，则表示字符串结束，跳出循环，i即字符串的长度。即字符串的长度。int LenStr(Str*r)while(r-veci!=0)i+;return i;E N G L IS 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-lenMA

27、XLEN)/连接后的串长超过串的最大长度连接后的串长超过串的最大长度 printf(两个串太长，溢出！两个串太长，溢出！);else for(i=0;ilen;i+)r1-vecr1-len+i=r2-veci;/进行连接进行连接 r1-vecr1-len+i=0;r1-len=r1-len+r2-len;/修改连接后新串的长度修改连接后新串的长度 3求子串求子串 在给定字符串在给定字符串r中从指定位置中从指定位置i开始连续取出开始连续取出j个字符构成子串个字符构成子串r1。void SubStr(Str*r,int i,int j)if(i+j-1r-len)printf(子串超界子串超界!

28、);return;else for(k=0;kveck=r-veci+k-1;/从从r中取出子串中取出子串 r1-len=j;r1-vecr1-len=0;printf(取出字符为：取出字符为：);puts(r1-vec);4.4.串比较串比较int EqualStr(Str*r1,Str*r2)/串比较串比较 for(int i=0;r1-veci=r2-veci&r1-veci;i+);return r1-veci-r2-veci;Void main()printf(ntt请输入第一个串：请输入第一个串：);gets(c.vec);printf(ntt请输入第二个串：请输入第二个串：);g

29、ets(d.vec);int k=EqualStr(&c,&d);/调用串比较函数调用串比较函数 if(k0)/k0，第一个串大，第一个串大 printf(ntt第一个串大！第一个串大！n);else if(k0)/k=r-len|r-len+r1-lenMAXLEN)printf(不能插入不能插入!);else 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;

30、6删除子串删除子串 在给定字符串在给定字符串r中删除从指定位置中删除从指定位置i开始连续开始连续j个字符。个字符。void DelStr(Str*r,int i,int j)/i为指定删除的位置，为指定删除的位置，j为连续删除的字符个数为连续删除的字符个数 if(i+j-1r-len)printf(所要删除的子串超界！所要删除的子串超界！);else for(k=i+j;klen;k+,i+)r-veci=r-veck;/将后面的字符串前移覆盖将后面的字符串前移覆盖 r-len=r-len-j;r-vecr-len=0;7.模式匹配模式匹配 模式匹配即子串定位运算。设模式匹配即子串定位运算。设

31、s和和t是给定的两个串，在主串是给定的两个串，在主串s中找到等于子中找到等于子串串t的过程称为模式匹配。其中被匹配的主串的过程称为模式匹配。其中被匹配的主串s称为目标串，匹配的子串称为目标串，匹配的子串t称为模称为模式。式。（1）基本思想：）基本思想：首先将首先将s1与与t1进行比较，若不同，就将进行比较，若不同，就将s2与与t1进行比较，直到进行比较，直到s的某一个字符的某一个字符si和和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当当s的某一个字符的某一个字符si与与t的字符的字符tj不同时，则不同时，

32、则s返回到本趟开始字符的下一个字符，返回到本趟开始字符的下一个字符，即即si-j+2，t返回到返回到t1，继续开始下一趟的比较，重复上述过程。若，继续开始下一趟的比较，重复上述过程。若t中的字符全部中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是比较完，则说明本趟匹配成功，本趟的起始位置是ij+1，否则，匹配失败。，否则，匹配失败。（2）模式匹配的例子）模式匹配的例子 主串主串s=ABABCABCACBAB，模式，模式t=ABCAC“。动画演示2动画演示1（3）算法描述：）算法描述：返回在字符串返回在字符串r中子串中子串r1出现的位置。出现的位置。int IndexStr(Str*r,

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

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

35、：s=AAAAAAAAAAAB t=AAAB 设匹配成功发生在设匹配成功发生在si处，则在前面处，则在前面i-1趟匹配中共比较趟匹配中共比较了了(i-1)*m次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共比次，所以总共比较了较了i*m次，因此最坏情况下平均比较的次数是：次，因此最坏情况下平均比较的次数是：因为因为nm，所以最坏情况下的时间复杂度是，所以最坏情况下的时间复杂度是O(n*m)。11111()(1)(1)12n mn miiinmpimimnm 11111(2)()()12n mn miiim nmpi mi mnm 小 结（1 1）串是有限个字符组成的序列，一

36、个串的字符个数叫）串是有限个字符组成的序列，一个串的字符个数叫做串的长度，长度为零的字符串称为空串。做串的长度，长度为零的字符串称为空串。（2 2）串是一种特殊的线性表，规定每个数据元素仅由一）串是一种特殊的线性表，规定每个数据元素仅由一个字符组成。个字符组成。（3 3）串的顺序存储有非紧凑格式和紧凑格式两种，非紧）串的顺序存储有非紧凑格式和紧凑格式两种，非紧凑格式存储操作简单，但内存浪费；紧凑格式可以节凑格式存储操作简单，但内存浪费；紧凑格式可以节省内存，但操作却不方便。省内存，但操作却不方便。（4 4）串的链式存储结构具有插入、删除方便的优点，但其）串的链式存储结构具有插入、删除方便的优点

37、，但其存储密度很低；若采用紧凑的链式存储（一个结点放多个存储密度很低；若采用紧凑的链式存储（一个结点放多个字符），虽然提高了空间利用率，但其插入、删除方便的字符），虽然提高了空间利用率，但其插入、删除方便的优点也随之消失。优点也随之消失。（5 5）串的堆分配存储是一种动态存储结构，用一个索引表）串的堆分配存储是一种动态存储结构，用一个索引表来存放串名，长度及在堆中的起始地址，并用一块地址连来存放串名，长度及在堆中的起始地址，并用一块地址连续的存储空间，存放各串的值，灵活性强。续的存储空间，存放各串的值，灵活性强。（6）串的基本运算包括串的连接、插入、删除、比较、替串的基本运算包括串的连接、插入

38、、删除、比较、替换、和模式匹配等，要求重点掌握串的定长顺序存储的基换、和模式匹配等，要求重点掌握串的定长顺序存储的基本算法。本算法。1 1实验目的实验目的（1 1）掌握串的特点及顺序定长存储的方式。掌握串的特点及顺序定长存储的方式。（2 2）掌握串的创建、连接、插入、删除、显示等操作。掌握串的创建、连接、插入、删除、显示等操作。（3 3）掌握串的查找、取子字符串、比较串大小的操作掌握串的查找、取子字符串、比较串大小的操作。（4 4）掌握模式匹配的基本思想及其算法。掌握模式匹配的基本思想及其算法。2 2实验内容实验内容（1 1）由用户通过键盘输入建立一个字符串；由用户通过键盘输入建立一个字符串；

39、（2）编写插入、删除、查找、比较、取子字符串、连接编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。字符串、显示、模式匹配等程序。（3）设计一个选择式菜单，以菜单方式选择上述操作。设计一个选择式菜单，以菜单方式选择上述操作。验证性实验5 串子系统 串串 子子 系系 统统*1-1-输输 入入 字字 串串 *2-2-连连 接接 字字 串串 *3-3-取取 出出 子子 串串 *4-4-删删 除除 子子 串串 *5-5-插插 入入 子子 串串 *6-6-查查 找找 子子 串串 *7-7-比比 较较 串串 大大 小小 *8-8-显显 示示 字字 串串 *0-0-返返 回回 *请输

40、入菜单选项请输入菜单选项:自主设计实验5 字符串分割处理1实验目的实验目的（1）掌握字符串的存储方法。）掌握字符串的存储方法。（2）掌握英文句子按单词和标点符号分割的方法。）掌握英文句子按单词和标点符号分割的方法。（3）掌握算术表达式按运算对象和运算符（只涉及）掌握算术表达式按运算对象和运算符（只涉及+、-、*、/）分割的方法。）分割的方法。2实验内容实验内容（1）输入英文句子，如）输入英文句子，如This is a string 存入数组：存入数组：3实验要求实验要求（1）利用）利用C或或C+完成程序设计。完成程序设计。（2）上机调试通过实验程序，并检验程序运行）上机调试通过实验程序，并检验程序运行的正确性的正确性（3）分别输入英语句子和算术表达式记录程序）分别输入英语句子和算术表达式记录程序运行结果。运行结果。（4）进行算法的时间复杂度和空间复杂度分析）进行算法的时间复杂度和空间复杂度分析。（5）撰写实验报告。）撰写实验报告。