第5章-串

数据结构第5章串第5章串•知识点串的有关概念和术语串的基本运算串的存储方法串的模式匹配运算•难点串的模式匹配运算算法•要求掌握串的逻辑结构掌握串的存储结构熟练掌握串的基本运算能设计串的计简单算法了解串的匹配运算算法的基本思想第5章目录•5-1串的定义和基本运算•5-2串的表示和实现•5-3串的基本运算•小结•实验5串子系统•习题55-1串的定义和基本运算5-1-1串的定义1.串的定义串（String）是由零个或多个任意字符组成的有限序列。一般记作：s=＂a1a2…ai…an＂其中s是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。ai（1=i=n）是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。2．几个术语（1）长度——串中字符的个数，称为串的长度。（2）空串——长度为零的字符串称为空串。（3）空格串——由一个或多个连续空格组成的串称为空格串。（4）串相等——两个串是相等的，是指两个串的长度相等且对应字符都相等。（5）子串——串中任意连续的字符组成的子序列称为该串的子串。（6）主串——包含子串的串称为该子串的主串。（7）模式匹配——子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。【例5-1】字符串的长度及子串的位置。字符串字符串长度S1=＂SHANG＂5S2=＂HAI＂3S3=＂SHANGHAI＂8S4=＂SHANG□HAI＂9//□表示空格，下同S1是S3、S4的子串，S1在S3、S4中的位置都为1。S2也是S3、S4的子串，S2在S3中的位置为6；S2在S4中的位置为7。3．串的应用在汇编语言和高级语言的编译程序中，源程序和目标程序都是以字符串表示的。在事务处理程序中，如客户的姓名、地址、邮政编码、货物名称等，一般也是作为字符串数据处理的。另外，信息检索系统，文字编辑系统，语言翻译系统等，也都是以字符串数据作为处理对象的。5-1-2串的输入与输出1．字符串的输入在C语言中，字符串的输入有两种方法：（1）使用scanf()函数使用scanf()函数时，输入格式中要设置＂%s＂，再加上字符数组名称。【例5-2】charstr[10];printf(＂Inputyourstr:＂);scanf(＂%s＂,str);•使用scanf()方式输入时，字符串中不能含有空格。•在C++中还可以用输入流对象cin。（2）使用gets()函数格式为：gets(字符数组名);【例5-3】charstr[10];printf(＂Inputyourstr:＂);gets(str);•使用gets()方式输入时，字符串中允许含有空格。2．字符串的输出字符串的输出也有两种方法：（1）使用printf()函数使用printf()函数时，输出格式中要设置＂%s＂，再加上字符数组名。【例5-4】printf(＂Yourstris%s＂,str);在C++中还可以用输出流对象cout。（2）使用puts()函数格式为：puts(字符数组名);【例5-5】printf(＂Yourstris＂);puts(str);5-1-3串的基本运算１．求串长LenStr(s)操作条件：串s存在操作结果：求出串s的长度。２．串连接：ConcatStr(s1,s2)操作条件：串s，s1存在。操作结果：新串s1是串s1和串s2连接以后的新串，原串s2值不变，串s1的值则改变。【例5-6】设s1=＂Micsosoft□＂，s2=＂Office＂，求两个串连接的结果。操作结果：s1=＂Micsosoft□Office＂；s2=＂Office＂。3.求子串SubStr(s,i,len)：操作条件：串s存在。操作结果：返回从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。【例5-7】SubStr(＂abcdefghi＂,3,4)=＂cdef”4.串比较：EqualStr(s1,s2)操作条件：串s1,s2存在。操作结果：若s1==s2，返回值为0；若s1s2,返回值0；若s1s2,返回值0。5.子串查找IndexStr(s,t)：找子串t在主串s中首次出现的位置（也称模式匹配）。操作条件：串s，t存在。操作结果：若t是s的子串，则返回t在s中首次出现的位置，否则返回值为0。【例5-8】子串定位IndexStr(＂abcdebda＂,＂bc＂)=2IndexStr(＂abcdebda＂,＂ba＂)=06.串插入InsStr(s,t,i)操作条件：串s，t存在操作结果：将串t插入到串s的第i个字符前，s的串值发生改变。7.串删除DelStr(s,i,len)操作条件：串s存在操作结果：删除串s中第i个字符起长度为len的子串，s的串值改变。5-2串的表示和实现5-2-1定长顺序存储1．定长存储的描述在C++语言中，字符串顺序存储可以用一个字符型数组和一个整型变量表示，其中字符数组存储串值，整型变量表示串的长度。#defineMAXLEN100typedefStruct{charvec[MAXLEN];intlen;}Str;//可用Str来定义该类型的结构体变量2．存储方式当计算机按字节（Byte）为单位编址时，一个存储单元刚好存放一个字符，串中相邻的字符顺序地存储在地址相邻的存储单元中。当计算机按字（例如1个字为32位）为单位编址时，一个存储单元可以由4个字节组成。此时顺序存储结构又有非紧凑格式和紧凑格式两种存储方式。（1）非紧凑存储设串S=＂StringStructure＂，计算机字长为32位（4个yte），用非紧凑格式一个地址只能存一个字符，见图5-1。其优点是运算处理简单，但缺点是存储空间十分浪费。（2）紧凑存储同样存储S=＂StringStructure＂，用紧凑格式一个地址能存四个字符，见图5-2。紧凑存储的优点是空间利用率高，缺点是对串中字符处理的效率低。string……ureStringStructure图5-1非紧凑格式图5-2紧凑格式5-2-2链接存储对于长度不确定的字符串的输入，若采用定长字符串存储就会产生这样的问题：存储空间定的大，而实际输入字符串长度小，则造成内存空间的浪费；反之，存储空间定的小，而实际输入字符串长度大，则不够存储。此时可采用链接存储的方法。1．链接存储的描述用链表存储字符串，每个结点有两个域：一个数据域（data）和一个指针域（next）。其中:数据域（data）——存放串中的字符；指针域（next）——存放后继结点的地址。仍然以存储S=＂StringStructure＂为例，链接存储结构如图5-3所示。图5-3链接存储结构（1）链接存储的优点——插入、删除运算方便；（2）链接存储的缺点——存储、检索效率较低。2．串的存储密度在各种串的处理系统中，所处理的串往往很长或很多。例如一本书的几百万个字符，情报资料的几千万个条目，这要求我们必须考虑字符串的存储密度。存储密度=串值所占的存储位/实际分配的存储位。串链接存储的存储密度小，存储量比较浪费，但运算处理，特别是对串的连接等操作的实现比较方便。StrrS∧…图5-4大结点结构表示这样一来，存储空间利用率明显提高，但插入、删除极不方便，所以链接存储的优点也消失了。由于字符串的特殊性，用链表作为字符串的存储方式也不太实用，因此使用较少。3．大结点结构为了提高存储空间的利用率，有人提出了大结点的结构（即串的链块表示）。所谓大结点，就是一个结点的值域存放多个字符，以减少链表中的结点数量，从而提高空间的利用率。例如每个结点存放四个字符，如图5-4。stringstructure∧5-2-3串的堆分配存储结构在实际应用中，往往要定义很多字符串，并且各字符串长度在定义之前又无法确定。在这种情况下，可以采用堆分配存储（也称为索引存储），这是一种动态存储结构。1．堆分配存储的方法（1）开辟一块地址连续的存储空间，用于存储各串的值，该存储空间称为“堆”（也称为自由存储区）。（2）另外建立一个索引表，用来存储串的名字（name）、长度（length）和该串在“堆”中存储的起始地址（Stradr）。（3）程序执行过程中，每产生一个串，系统就从“堆”中分配一块大小与串的长度相同的连续空间，用于存储该串的值，并且在索引表中增加一个索引项，用于登记该串的名字、长度、和该串的起始地址。2．索引存储的例子设字符串：A=”Red”B=”Yellow”C=”Blue”D=”White”用指针free指向堆中未使用空间的首地址。图5-5带长度的索引表NameABCD……Length3645……Stradr……堆：RedYellowBluEWhite…free索引表：考虑到对字符串的插入和删除操作，可能引起串的长度变化，在“堆”中为串值分配空间时，可预留适当的空间。这时，索引表的索引项应增加一个域，用于存储该串在“堆”中拥有的实际存储单元的数量。当字符串长度等于该串的实际存储单元时，就不能对串进行插入操作。3．带长度的索引表的C语言描述如图5-5所示，索引项的结点类型为：typedefStruct{charname[MAXLEN];//串名intlength;//串长char*Stradr;//起始地址}LNode;4．“堆”的管理C语言中用动态分配函数malloc()和free()来管理“堆”利用函数malloc()为每个新串分配一块实际串长所需要的存储空间，分配成功则返回一个指向起始地址的指针，作为串的基址，同时，约定的串长也作为存储结构的一部分。函数free()则用来吸收用malloc()分配的存储空间。在C++语言中malloc()可用new替换，而free()也可用delete代替。在这里，我们仅仅简单的介绍了堆分配存储的基本思想，具体的算法及细节尚未涉及。在常用的高级语言及开发环境中，许多系统本身都提供了串的类型及串的库函数，用户可以直接调用，这样会使算法的设计和调试更方便容易，可靠性也更高。本小节主要讨论定长串连接、求子串、串比较算法，顺序串的插入和删除等运算。为了讨论方便我们再次描述定长顺序串的结构如下：#defineMAXLEN100//定义串的最大长度typedefstruct{charvec[MAXLEN];intlen;//串的实际长度}Str;//定义一个结构体类型Str在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用'\0'来表示串的结束，如图5-6所示。5-3串的基本运算图5-6串的定长顺序存储1．求串的长度用判断当前字符是否是‘\0’来确定串是否结束，若非‘\0’，则表示字符串长度的i加1；若是‘\0’，则表示字符串结束，跳出循环，i即字符串的长度。intLenStr(Str*r){while(r-vec[i]!='\0')i++;returni;}ENGLISHO…01234567MAXLEN-12．串连接：把两个串r1和r2首尾连接成一个新串r1，即：r1=r1+r2。voidConcatStr(Str*r1,Str*r2){if(r1-len+r2-lenMAXLEN)//连接后的串长超过串的最大长度printf(两个串太长，溢出！);else{for(i=0;ir2-len;i++)r1-vec[r1-len+i]=r2-vec[i];//进行连接r1-vec[r1-len+i]='\0';r1-len=r1-len+r2-len;//修改连接后新串的长度}}3．求子串在给定字符串r中从指定位置i开始连续取出j个字符构成子串r1。voidSubStr(Str*r,inti,intj){if(i+j-1r-len){printf(子串超界!);return;}else{for(k=0;kj;k++)r1-vec[k]=r-vec[i+k-1];//从r中取出子串r1-len=j;r1-vec[